lambdaclass
Recursion depth check
tl; dr Inject recursion limit checks into generated code.
In some cases, generated programs may still blow the stack depth limit despite gas and TCO.
- Find some such cases and use them to test.
- Change the implementation of function calls so that in these cases, each function has a global counter initialized to a configurable (upon program execution, as an input value) maximum depth limit which is decremented on each recursive function call. When the depth is exceeded the program should "sierra-panic" (instead of segfaulting or rust-panicking)
- Allow a mechanism to set up the compiler with a default stack depth on startup.
All recursive programs of a certain depth which are not tail-recursve will blow up the stack (there's an example of such program in programs/sample.cairo). This is not specific of Cairo, it will happen in any general purpose language (which doesn't have dedicated safety features against stack overflow, of course). The VM handles this differently since it doesn't use the stack, but segments: it'll keep allocating larger and larger segments and will potentially crash the host OS when it runs out of memory. Caution is advised when testing the VM's behavior with this kind of programs.
I think Sierra-panicking is not the solution since it'd change the behaviour versus the VM. Maybe it would be better to have a special kind of error (separate from Sierra; something with similar behavior to Rust's results). Regardless of the final choice, it should be easily implemented with a metadata (ex. StackDepthMeta) and the call_function libfunc implementation.
The mechanism to set the compiler would be inserting the StackDepthMeta metadata before compiling. The call_function libfunc builder may check whether the metadata exists and act accordingly.
Note that the behavior of this safety mechanism should also be defined for tail-recursive function calls. Do they count towards the limit? My guess is that they don't since they won't be consuming stack. This will also need to be coded.
