8 ms·
Ask not what the compiler can do for you
- Nars088 3y agoIs this the case with all statically typed languages? I think I have faced the same issue with PureScript (PS: I'm a contributor)
- kibwen 3y agoWith exclusively static dispatch I feel like it should be possible to unconditionally detect at least the presence of recursion at compile-time, but in the presence of dynamic dispatch (as in the article) I think it might be impossible for a compiler to guarantee that it can statically detect recursion. (I have no basis for these claims other than gut feeling.)
- duped 3y ago> With exclusively static dispatch I feel like it should be possible to unconditionally detect at least the presence of recursion at compile-time, This is equivalent to solving the halting problem, and therefore impossible in the general case. Tools can use heuristics to make a guess. Dynamic dispatching to mutually recursive functions is one example where those tools fail. But that also includes things like checking a conditional before calling a function. The tool can check unconditional infinite recursion, but it can't tell you for certain that a branch that may be infinite is always taken.
- kibwen 3y agoWhether or not the recursion ever successfully reaches the base case in order to terminate is certainly equivalent to the halting problem, and thus undecidable for Turing-complete languages. However, I was making a much weaker claim, which is that if you have exclusively statically-dispatched function calls, it should be possible for a compiler to detect the possibility of recursion 100% of the time. For every function, you should be able to make a complete list of every other function that it calls directly (including branches that may never actually be taken at runtime (which it cannot know, because of the halting problem), making this overly conservative, like any type system). This list is both perfectly precise (because of static dispatch) and finite. With this, you can then construct a graph and run a cycle detector over the graph.
- dunham 3y agoYou can also determine that _some_ programs terminate. That is, there is a class of recursive programs that the compiler can look at and say "yes this terminates". Where it fails is that the programs that it says "no" to may still terminate. (So it's a "yes" or "maybe".) Languages that I've worked with that do this are Lean4, Idris2, and Agda. It's needed for dependent type checking as you only want to run total functions at the type level (to ensure type checking terminates). Idris will build the call graph as you described and analyze whether values get structurally smaller as they pass through any cycles in the graph. (Also lexicographical stuff like "arg1 gets smaller or arg1 stays the same and arg2 gets smaller".) I don't know the details of Agda. Lean has a couple of things that it tries: detect straight up structural recursion, detect general recursion where an argument gets smaller, and it also lets you provide a function on the args for what gets smaller (e.g. length - ix) and a proof that it gets smaller. I gave this a try with a heap implementation that I wrote. I worked through the proof and hit a wall having to show 0 < 0. It turned out that I had an off-by-one error (I was doing the math for a starts at 1 array). Once I fixed that, I got my proof and the compiler certified that it was total. Writing proofs is not something your average programmer would want to do for the average program, but I think there is some utility in the compiler being able to say "yes this terminates" or "maybe this doesn't terminate".
- munificent 3y agoEven without object-oriented dynamic dispatch, if the language supports closures or function pointers, you still lose the ability to statically analyze all call targets.
- kibwen 3y agoI'm comfortable saying that any direct use of function pointers counts as dynamic dispatch, unless your language's semantics for function pointers are especially strict or static. :) As for closures, I'm not entirely convinced; closures in Rust don't support recursion because they're lexically-scoped (unless "something something y-combinator", which I confess I don't grasp), and otherwise closures are (usually) just as statically-dispatched as any other function call.
- munificent 3y agoYes, I wasn't sure if by "dynamic dispatch" you mean "object-oriented polymorphic method calls" or more generally any kind of indirect calls which would include calls through function pointers. Once you have callsites where you can't resolve the target function statically, you've lost the ability to statically prove the absense of stack overflows. With Rust, I think methods on trait objects should be enough dynamic dispatch to make it impossible to prove the absence of stack overflows. But I'm not enough of a Rust programmer to know for sure.
- kibwen 3y agoYes, perhaps "indirect call" would better capture my thinking here rather than "dynamically dispatched". :) > With Rust, I think methods on trait objects should be enough dynamic dispatch to make it impossible to prove the absence of stack overflows. Well, trait objects are absolutely dynamically-sized types, but in order to store them on the stack you'd need to stuff them behind a Sized pointer type. But there might be other strange edge cases that prevent the ability to guarantee the absence of stack overflows (to say nothing of the fact that stack size differs between platforms).
- hoosieree 3y agoI'm not an expert on fuzzing, but I think a fuzzer would be able to discover this issue.
- richardwhiuk 3y agoAny UT of the function would have caught this issue.
- kibwen 3y agoSure, but fuzzers are best-effort heuristics, rather than a static guarantee of correctness.
- loeg 3y agoI don't think the recursion in this case is dynamically dispatched. It returns a dyn Future, but that isn't the same thing.
- kibwen 3y agoI haven't thought about it closely enough to know whether or not it's feasible to detect recursion in this specific case of dynamic dispatch (compilers are certainly capable of devirtualization, after all). However, any time you see a `dyn Foo` in Rust, any method called on it will be dynamically-dispatched (unless the aforementioned devirtualization optimization happens to kick in): https://doc.rust-lang.org/std/keyword.dyn.html https://doc.rust-lang.org/std/keyword.dyn.html
- loeg 3y agoWe are not calling a method on a `dyn Foo`. The type in the original example is statically known to be `KafkaWrapper`. The reduced example case isn't even a method -- it's just an ordinary function: fn do_something() -> Pin<Box<dyn Future<Output = ()>>> { Box::pin(async { do_something().await }) } (The infinite recursion happens before anything is ever returned --- the return type is irrelevant.)
- thethirdone 3y ago> (The infinite recursion happens before anything is ever returned --- the return type is irrelevant.) This is not true, the closure is not actually called until the future is awaited. Each instance of do_something does actually return.
- cat-whisperer 3y ago> With exclusively static dispatch I feel like it should be possible to unconditionally detect at least the presence of recursion at compile-time, That's true, and Rust as a language does do so, but in case of recursion for `async` function rust itself suggests to go the `dyn` route. Adding more to the post, it seems that the use of `async-trait` was the reason that they didn't have any choice in the matter to choose static dispatch, as the language as a whole doesn't support async traits, (just yet! ^-^)
- thala 3y agoAre there any tools to identify stack sizes and function traces?
- Atlas22 3y agoHave not used it myself but looks like there is StackAnalyzer[0]. Have done it myself by adding analysis to angr[1] but it pretty much boils down to trying to solving the halting problem for many large programs (an unbounded recursion or alloca makes the max stack size infinite) [0] https://www.absint.com/stackanalyzer/index.htm https://www.absint.com/stackanalyzer/index.htm [1] https://angr.io/ https://angr.io/
- hra5th 3y agoFor rust code, I have found https://github.com/japaric/cargo-call-stack https://github.com/japaric/cargo-call-stack to be the best available option, as it does take advantage of how Rust types are implemented in LLVM-IR to handle function pointers / dynamic dispatch a little better. An even better solution would try to use MIR type information as well to further narrow down targets of dynamic calls in a Rust-specific way, but no such tool exists that I know of.
- pdimitar 3y agoNot sure rustc can do a lot about this case but maybe a static analysis tool can complement it.
- richardwhiuk 3y agoTo some extent, all compilers are static analysis tools. I think clippy could be enhanced to spot this.
- pdimitar 3y agoYep, it likely could. Spotting something that usually is an error now being wrapped in `Pin<Box<...>>` would hopefully be not too hard.
- loeg 3y agoIf it can detect the recursion in the non-dyn return case, it seems like it ought to be able to do the same once dyn is added.
- munificent 3y agoI don't mean this to sound superior or critical. I found this article a little surprising because the authors seem to have an intuition about the compiler that I have never had. I've never expected potential stack overflows from unbounded recursion to be caught by the compiler. I've been delighted every now and then when a compiler gives me a warning when it can detect it. But I have always had stack overflows in my mental bucket of "stuff it's my responsibility to think about". Maybe this says something about how compilers have gotten smarter and more helpful since I first cut my teeth on them.
- humanrebar 3y agoThe branding (or at least the zeitgeist) around Rust is that it is a "safe language", which implies that bugs are all logic bugs or somehow the fault of the programmer for doing something "unsafe" (hence the keyword). Anyone who thinks about it for a bit knows there are limits to guarantees of safety. It's notoriously impossible to prove that a program terminates appropriately, for instance. So I can understand some shock to run into the arcane all of a sudden. It must be especially shocking because it feels especially out of place.
- ecshafer 3y agoRust is a safe language for a specific definition of safe regarding a class of memory errors.
- pa7ch 3y agoRegarding multiple classes of memory errors I think. Many languages are memory safe from control flow takeover, rust extends this to data races corrupting data.
- Georgelemental 3y agoRust (without `unsafe`) protects you from Undefined Behavior. Behavior that is defined as crashing your program doesn't fall under that.
- 3y ago
- stefanos82 3y agoIs there any flag in Rust's compiler, like GCC's `-fstack-check` that checks for such behavior?
- LegionMammal978 3y agorustc already tells LLVM to use stack probing for sufficiently large stack frames, so it can give a short error message on stderr ("thread 'whatever' has overflowed its stack") before aborting the program. But the author is looking for a backtrace here. The problem is that printing a backtrace is the responsibility of the program, as part of the global panic hook. But running arbitrary user code (e.g., Backtrace::capture()) during a stack overflow would be extremely unsafe, since the thread could be in the middle of some operation that does not expect to be interrupted. The soundness criteria would likely be very similar to those for async signal handlers, which are extremely platform-dependent, so it would be a challenge to document all the safety preconditions. An alternative would be to especially bless backtrace-rs for stack overflows alongside the default panic hook, but I don't think even it can guarantee complete safety on all supported OSes.
- loeg 3y ago> The problem is that printing a backtrace is the responsibility of the program, as part of the global panic hook. But running arbitrary user code (e.g., Backtrace::capture()) during a stack overflow would be extremely unsafe, since the thread could be in the middle of some operation that does not expect to be interrupted. > The soundness criteria would likely be very similar to those for async signal handlers, which are extremely platform-dependent This is more or less exactly the same as any stack-print-on-crash handler you might be familiar with. In theory you should be able to unwind using DWARF eh_frame data from anywhere. In practice this stuff isn't always perfect and it's much easier to rely on framepointers, if your compiler emits them. But switching to an alternative signal handler stack and unwinding your main stack is mostly worth trying -- worst case, you're already crashing.
- LegionMammal978 3y ago
- cat-whisperer 3y agoI don't fully understand the context or the overview of the problem, but for a large codebase, if you are using `tokio` runtime, which most rust based application go with. `tokio-console` is good for profiling and debugging, have you folks looked into that during the whole debugging process? I personally trust debuggers and debugging tools in such circumstances, as they can easily help zeroing down on such issues.
- flooow 3y agoFortunately this particular problem should go away soon. Async-fn-in-traits is due to be stabilized in the next few months [1], which means that the use of #[async_trait] will no longer be necessary, which means the compiler will correctly surface a warning for unbounded recursion. [1] https://blog.rust-lang.org/inside-rust/2023/05/03/stabilizing-async-fn-in-trait.html https://blog.rust-lang.org/inside-rust/2023/05/03/stabilizin...
- Nars088 3y agoCheck this out: https://github.com/rust-lang/rust/issues/111177 https://github.com/rust-lang/rust/issues/111177
- loeg 3y agoThe lack of warning does not seem to be related to #[async_trait] -- it's reproducible on a bare function, as shown in the post and in sibling comment's 2nd link.
- Arnavion 3y agoThe lack of warning is from returning `Box<dyn Future>`, which `#[async_trait]` emits. ( https://news.ycombinator.com/item?id=35834091 https://news.ycombinator.com/item?id=35834091 ) With async-fn-in-trait that flooow linked to (and more generally type-alias-impl-trait) there won't be a motication to use `Box<dyn Future>` in the first place.
- nurettin 3y agoIs this what happens when we are too complicit and entirely depend on our tooling to find mistakes?
- lsampras 3y agoI guess we can never expect the tools to find all the mistakes only the straight-forward ones (which seems to be a moving target)... This could be an example of when things fall through the crack, while rust & its tooling eliminates most of the errors during compile time, it's not entirely impervious... Overall I'd prefer depending on tooling to catch a subset of errors (which could miss 1 out of 20 times), rather than the added manual review effort with each change...
- lukebitts 3y agoWhat happens? We debug and find the error exactly like we would have to if the tooling was “worse”
- Nars088 3y agoWe spent decades trying to invent a sufficiently smart compiler when we should have been inventing a sufficiently empathetic one - @ekuber It all makes sense now
- xiaodai 3y agoask what ChatGPT can do for you instead.