yeah, this is a bug. And yes, it should be fixed. But I don't think it will affect many users, I mean who has a 32000 -evels deep directory on their system?
It's a stack overflow which means it's using recursion and for historical reasons that don't make sense any more, stacks are teeny tiny on 64-bit Linux - apparently only 8 MB on Linux! I'm not sure why they don't raise it to something reasonable like 4 GB. I guess because they want consistency with 32-bit? Maybe we can finally change it if/when they phase out support for 32-bit Linux. Apparently it might not be that far away:
8MB is the default per-thread stack size from glibc, also seems to be the default "ulimit" from pam or the kernel, I'm not sure. So for the main/default thread (or if not using threads) the process can use setrlimit() and for threads it can use pthread_attr_setstacksize() to get bigger stacks if it knows it may need them.
8MB is pretty huge though; musl libc is famous for defaulting to much smaller per-thread stack size of 128KB (to avoid over-committing lots of memory when there are many threads - the main dev is really principled/opinionated on this topic, but again there are a few ways for applications to explicitly size their stacks as large as they need). Linux kernel threads get a bit less than 16KB!
8MB is huge compared to the stacks we used to have when address spaces were 32-bit, but it's tiny compared to how much memory we can actually make use of now. The only real argument I can think of for having such a small stack is that large stack usage is often indicative of an infinite recursion bug and it catches them earlier.
But I don't really buy that for the same reason most programming languages don't limit loops to 8 million iterations (or whatever) by default - it would make catching infinite loop bugs easier!
I say most, because I know of at least one language that did do that - QuakeC! It made lots of sense in that context though.
For what it's worth there's reasonably active [1] work on implementing opt-in guaranteed tail calls - but it's not particularly fast going. LLVM (the backend rust uses) needs better support for musttail (e.g. some architectures just don't support it [2]).
By-default guaranteed tail calls really isn't rust's style, because it means subtle changes (introducing a destructor, re-ordering code, etc) can change semantics without you realizing it. If you want to guarantee that a call can't allocate a new stack frame you should have to say it.
Not so familiar with this area, but isn't the existing behavior of implicitly creating new stacks more of a problem than implicit tail-call elimination? Seems the latter is a kind of compiler-level optimization, of which there are already many (I think) that change the semantics internally but guarantee the outward behavior stays the same.
But I can understand the preference for an explicit opt-in, to make clear that it is enforced and not assumed.
I'd argue that it's explicit - that's what a function call does and you don't have implicit function calls in rust.
> Seems the latter is a kind of compiler-level optimization, of which there are already many (I think) that change the semantics internally but guarantee the outward behavior stays the same.
What you're asking for here already exists. Tail calls might be optimized into not allocating extra stack frames, the rust compiler just doesn't guarantee that it will perform that optimization (and almost certainly won't when code is compiled without optimizations... for instance).
What people want is the semantic guarantee that the stack frame won't be allocated. Not just a compiler that often performs the optimization. Otherwise you can't be sure that your code will keep working with new compiler flags/versions/architectures/... You could say "whenever the code is the right shape we'll guarantee the optimization" (C++ famously did this for things like copy elision)... but now the shape of code comes with non-obvious semantic guarantees and that's not rust's style. Hence the proposal for a keyword instead.
I see it, certain algorithms need guaranteed tail-call elimination, otherwise they are too inefficient and must be manually unrolled or rewritten to avoid blowing the stack. So a compiler optimization that is "nice to have" is not good enough.
I can see how it might require an explicit state machine (keep a mutable state number and switch over the inlined bodies of what could be functions), but I'm not seeing how it could require `goto`.
Are there more-complex relationships that might require it?
> because it means subtle changes (introducing a destructor, re-ordering code, etc) can change semantics without you realizing it.
No, it won't change semantics - if you say @musttail or similar, it will simply fail to compile if you, say, introduce a destructor - the semantics will not subtly change.
Uh, yes, if you guarantee the semantics only when the code explicitly opts in and not by default then semantics will not subtly change, that is the point of my comment
Guaranteeing an optimization that otherwise only might run is a change in semantics. The attribute doesn't allow (in any sensible language) the code to simply not compile because the optimizer doesn't feel like it today (or you compiled with -O0), it forces the compiler to not allocate a stack frame wherever the code fits the structure that makes that definitely possible and fails to compile wherever it doesn't (even if after other optimization passes it happens to fit a structure that makes it possible).
I don't think that's related? The bug alluded to looks something like
function rm(node) {
for (const child of ls(node))
rm(child);
unlink(node);
}
and no amount of tail call optimization will save you here, because this isn't tail recursion. Of course you could rewrite it using an explicit stack + tail recursion, but then you might as well be using a while loop.
So it's enumerating all the subdirectories first and unlinks the tree afterwards?
I get that this isn't transactional and inherently prone to race conditions, but if this is indeed the problem, it's rediculous. A single while loop could do the job correctly and use less RAM. It'd probably also be faster. But that wouldn't be a rusty thing to do?
I look at code from the heirloom project and, despite its warts, I think we've lost something in the past 45 years or so.
> A single while loop could do the job correctly and use less RAM. It'd
probably also be faster. But that wouldn't be a rusty thing to do?
No, the "single while loop" is just harder to implement than a naive
recursion, because recursion is a natural way to implement tree traversal.
With a while loop, you need an explicit stack, which is more complex.
(A stackless traversal seems unrealistic here, as getting the succeeding
node would be too expensive. Not that I've tried...)
> I look at code from the heirloom project and, despite its warts, I think
we've lost something in the past 45 years or so.
I've just tried and heirloom rm segfaults on the same test too. Which is
no wonder, seeing how that code also recurses.
(It's mentioned somewhere else in the thread, but this is exactly the
reason why GNU had to specify "no hard limits" as a policy. Unix used to
be full of such bugs.)
How interesting. I'd seen LISP(y) implementations like Scheme guarantee tail-call since recursion is a very common technique in that language family. But I didn't know Zig supported it.
They have an @call built-in that guarantees: always/never tail, as well as always/never inline. That's neat, I can see how that would be useful in various situations.
The point is that such bugs shouldn't exist in the first place.
Using recursion on unbounded inputs on a programming language that doesn't support that (which are most) is an extremely classical mistake that really should be known to all programmers, especially those of low level languages that care about safety.
Every time you call something recursively you should be thinking "how deep is this?".
By that logic, why even spend effort migrating from a known-working implementation to one which is known to have outstanding bugs that there isn't enough bandwidth to fix?
Hard to say, but there are legitimate reasons. One of which being they think Rust is growing while C is a shrinking language. Other could be safety (yes, yes the audit did surface bugs). Or even that having a single lib work seamlessly on Windows/Linux/MacOS/Redux/Web.
The problem there is that this is exactly the class of bug that does not exist in GNU coreutils because of philosophy of that project. Non-existence of such bugs proves that the impementation is not copied from AT&T code.
This isn't a port - it's a re-implementation without any use of the original source.
That's also not all that's happening. It's also making improvements like better internalization support, better error messages, and a small handful of other extensions.
I have had to tell them repeatedly to stop copying tests verbatim, including the original comments from GNU coreutils. So I doubt this is true, which is frustrating.
If they followed the license nothing. My uninformed knowledge is that the rust based rewrite is MIT, the originals are GPL, and you can't include GPL code in a MIT licensed project without making it GPL.
Ehh... Technically yes but when you don't own the copyright on the tests you need to be very careful against creating derivative works, and you need to preserve both licenses in the distributed source.
Nah, people should (and do) fix small issues as well as big issues. Lying about the scale of issues and calling them "big" when they aren't just leads to no ability to prioritize or evaluate.
Incidentally someone submitted a PR for this issue about 3 hours before the first comment about it in this thread - https://github.com/uutils/coreutils/pull/14554 (and 2 hours before this link was submitted to HN)
