Use stacker to prevent stack overflow from depth-first query evaluation.

[eddyb]

stacker is:

A library to help grow the stack when it runs out of space.

This is an implementation of manually instrumented segmented stacks where points in a program's control flow are annotated with "maybe grow the stack here". Each point of annotation indicates how far away from the end of the stack it's allowed to be, plus the amount of stack to allocate if it does reach the end.

Once a program has reached the end of its stack, a temporary stack on the heap is allocated and is switched to for the duration of a closure.

Recent PRs that might be relevant: #41625 (MIR inlining) and #41676 (macro expansion).

Also related: #40161, a meta issue for places where deep recursion arise.

cc @rust-lang/compiler

[eddyb]

(Blocked on #41847 which will make it easier to use crates.io libraries in the compiler)

[jonas-schievink]

Stacker only seems to support i686 and x86-64 at the moment

[jonas-schievink]

(did GitHub eat my previous comment?)

Note that stacker only supports i686 and x86-64 at the moment. While this does cover all tier 1 platforms, it might make maintaining the lower tiers harder.

[nikomatsakis]

@jonas-schievink presumably we could gracefully fall back to the current solution of "really big stack", and encourage lower tiers to extend stacker.

[alexcrichton]

Ah yeah only i686/x86_64 are supported, but that's just because of the assembly routines, which should hopefully be very easy to port to new platforms! (they're quite small).

I think @nikomatsakis has a good point though that we'd just want to disable it on non-supported platforms beacause there's also OS-specific logic for discovering the stack limit in addition to arch-specific logic for the assembly.

PRs are of course always welcome to improve it!

A few side notes for the library as well:

• Panics may or may not work currently, but wrapping everything in catch_unwind with a propagate shouldn't be too hard
• I'm not sure if this strategy is sound on Windows, which historically I think has weird restrictions about stack pointers. I'm not sure though, it may be just fine!