Halfway through your comment I was going to say you were wrong, that ASTs aren't self-referential and that you can easily allocate them in a single block using a bump allocator, but then obviously you say so yourself in the second part of the post. This is exactly what this post proposes to do when it proposes to remove the safeguards and says it can't show a Rust version (the "AstContext" is just a sort of bad bump allocator), except of course that in Rust it's completely memory safe.
> Box<T> generally ruins your ability to do pattern matching, which is a deal-breaker when working with ASTs.
For what it's worth I find that I never want to pass ownership when traversing ASTs with pattern matching, so I just bind everything by reference and don't experience this problem. YMMV.
OK, I didn't actually read the "I give up on doing this in Rust" section very carefully.
The article capitulates:
> last time I asked how to do that in my company’s Slack channel, the responses I received were something like “don’t” and “why would you do that?” and “someone please call security.” It should not have been a surprise, as an AST is basically a linked list with extra steps, and Rust hates linked lists.
If I didn't tell myself "go find a good solution", I might have not found someone suggesting "Just use a bump allocator and make your nodes live until one exact, shared lifetime."
The article does agree in principle with this solution:
> In my experience, it’s quite easy to do away with the ceremony of making each node hold a reference count altogether, and instead decide on a more disciplined approach to ownership.
I think this is one of those examples where you get a principled, elegant and safe solution.
You just gotta find it first.
But here it is.
(Also, I read about it on a forum when searching for a better solution than box_patterns.)
You either have to explicitly mark every node in the tree with a Box<T>, or nodes in the tree has to share lifetimes.
But since you're building the tree gradually by recursively scanning over some concrete syntax, that won't work.
Box<T> generally ruins your ability to do pattern matching, which is a deal-breaker when working with ASTs.
You can overcome some of the inconveniency by using a compiler extension called box patterns:
https://doc.rust-lang.org/beta/unstable-book/language-featur...
But the nicest solution I've found is to use a bump allocator (specifically, bumpalo).
You allocate a big chunk of memory for your AST, for which the lifetime is that of the bump allocator's handle.
And you tie the lifetime of all nodes of your AST with that lifetime.
The "drawback" is that you must free your entire AST at once. But you probably were going to anyways.
https://manishearth.github.io/blog/2021/03/15/arenas-in-rust...