Unbounded stack usage when dropping deep trees

[DerickEddington]

The recent commit 2855098 prevents stack overflows only when dropping long lists. Similar stack overflows when dropping other shapes of trees are still possible, e.g. with Conss with depth down a car side, or with Vectors with depth.

A fully-general solution for arbitrary shapes of trees is more involved due to needing to be able to traverse back up parent nodes to then traverse down their additional branches.

I've already made a crate, deep_safe_drop, that provides this solution generically, efficiently, without using extra space, by reusing the existing space in a tree. I've now integrated it into lexpr:

https://github.com/DerickEddington/lexpr-rs/tree/deep-safe-drop Or: https://github.com/DerickEddington/lexpr-rs/tree/deep-safe-drop--only

I worked on this in response to the issue #104 reported by @BobAdamsEE .

A reproducible example of such stack overflow still occurring is the test case I made with a tree of Vectors with some depth, along with a test case of how my contribution fixes this:

https://github.com/DerickEddington/lexpr-rs/blob/a6d3153a026bef6a661fb4b97edc2a1da4e2db46/lexpr/src/value/tests.rs#L147-L194

With Windows sometimes (often?) having a main-thread stack size of only 1 MB, or with other scenarios like microcontrollers or fibers sometimes having much smaller stack sizes, the concern is more pronounced. A depth of 6_000 for debug builds, or 17_000 for release builds, is enough to blow a 1 MB stack, and less would be a problem with smaller stacks.

While depth down Cons cars or Vectors is less common, I think it should be supported. I made deep_safe_drop years ago because I'd encountered the same problem with data types similar to S-expressions and with non-list deep shapes that I'd want to have if I were to use S-expressions instead (which would be reasonable) for such applications. Even though the lexpr parser currently might not be able to parse textual representations of such depth without error, the drop handling should still not blow up, because it's possible and maybe reasonable for users to construct such depth for only in-memory usages. Even if the only application is for test cases to exercise some other thing's ability to handle depth. The dropping shouldn't cause crashes which are often confusing and unintuitive because the dropping is implicit (the same problem exists with trees of many other various types in Rust, which is why I made a generic solution for Rust).

If you're interested in the fully-general solution I've already integrated into lexpr, I'll create a Pull Request, and I'm totally open to revising what I've made according to your preferences, my old friend. My contribution has comments in the source and commit messages, and the new 0.1.0 version of the deep_safe_drop crate is now better documented. I'm not totally familiar with all of lexpr-rs, but I think the scope of what I've done is limited and small enough that I hopefully didn't break anything.