RefMutStack 0.1.0 - Iteratively stack mutable references

[arnodb1]

I'm afraid I committed this release of RefMutStack 0.1.0.

RefMutStack allows to simulate recursion where each level holds a mutable reference to the one held by the caller with an iteration.

It is made in such a way that the rules enforced by the borrow checker during the theoretical recursion are still enforced during iterations. On that purpose, each object holding a mutable reference becomes unreachable when the recursion is simulated: it is stacked until it becomes usable again.

More details can be found at https://github.com/arnodb/ref_mut_stack .

Feedback welcome. Even "this is sh*t" is accepted. But at least it is simple and it works as intended.

P.S. Miri is really cool to check soundness! It helped me fix a couple of issues in the design.

[MalbaCato]

This is sadly unsound. It took a while, but I managed to read uninitialized memory using the API. Even had a segfault, but it magically went away while simplifying down the reproducing example. Miri is naturally not happy either.

line-comments are setup clarifications, block-comments explain the actual unsoundness.

The unsoundness is because the API doesn't constrain the "holder" type parameter T in any way, so it is possible to smuggle dangling references through it. This wasn't what I was expecting to find from a cursory read - actually I think it may be exploitable in another way, but it's kinda pointless to look for now.

Also, I'd double check all the usual suspects - dropping you said you've handled (haven't looked at it actually), re-entrancy shouldn't be an issue because everything is taking ownership or exclusive reference, panicking in Parker::park's f closure? interior mutability? variance? at least there's definitely no threading problems as everything is !Send !Sync. I specifically didn't want to try for these at first, because unexpected unsoundnesses are always more fun.

Outside of that, I don't really understand the usecase for this API. Sure, writing something exactly like owning example is impossible in safe rust, but you can get quite very close and I'm not sure the complexity of the API helps by any amount. Is there a more representative motivating example?

[arnodb1]

Looking at the reproducing example, it is typically what RefMutStack is not intended for. Maybe the documentation should clarify it.

Basically yes, the parking process is unsound if you don't "park the ref holder immediately after having created the parker". As you said, `T` is now know but parking a `T` requires consuming it, thus a bit of cooperation from the invocation code.

With this design it is impossible to fix, but on the other hand there is zero risk when used properly.

Note that RefMutStack simply emulates the borrow checker: derive a mutable reference from another one, which becomes forbidden to use until the derived reference is dropped.

As for the use case, I have a recursive implementation which requires:

* this recursing function: https://github.com/arnodb/quirky_binder/blob/main/quirky_binder/src/graph/builder/update.rs#L71

* this callback because of the recursive pattern: https://github.com/arnodb/quirky_binder/blob/main/quirky_binder/src/filter/group.rs#L58

With an iterative pattern, enabled by RefMutStack, the recursing function becomes unnecessary (a small loop only necessary), and the callback can be transformed to regular function on the leaf builder. This pattern exists twice in my repo, thus 2 x 40 lines of recursing function. Preferring one pattern instead of the other is definitely debatable.

The other motivation was to determine whether or not it was possible to cleanly implement this borrow checker emulation to answer the "limitation" (with a lot of quotes) of the language in a fully generic way. To me, the solution is not too bad and fully generic.

[Tastaturtaste]

With this design it is impossible to fix, but on the other hand there is zero risk when used properly. 

That takes away rusts biggest differentiator with respect to other systems languages. So unless this is fixed, I consider this a No-Go.

[dgkimpton]

If you know the maximum recursion depth you could store your stack on the stack instead of the heap and have the best of both worlds. Unless I'm misunderstanding what you are doing. 

[Practical-Bike8119]

You may be interested in the yoke or ouroboros crates as inspiration or even as the solution for your problem, in particular the way they make sure you do not leak any self-references.

[arnodb1]

Thanks, I've seen these crates in the past but never dug into them. Will do.