Yeah, trying to translate code from OCaml the number one most annoying thing was limitations around pattern matching. I think in general you run into this sort of thing a lot if you try to either treat Rust as a functional programming language like OCaml, or are writing the sort of thing that inherently benefits from garbage collection. However, there is actually a trick that can (if you don't need cleanup) both improve your performance and give you back pattern matching: allocate your nodes in something like https://docs.rs/typed-arena/2.0.1/typed_arena/ instead of as Rcs. Doing this (especially if you tend to stick to immutable stuff, but even if you don't if you're careful) can make using Rust for manipulating ASTs and stuff a lot more pleasant (though it does have other tradeoffs, obviously, and you usually end up needing both kinds of representation at different points--which I guess speaks to your point about there being way too many ways to do things and too many rules about how to do them).
To put it very simply, it sort of provides a way to make everything 'static, except for it's actually arena's lifetime, 'a. So you no longer care who outlives who because all the objects will die together when the arena dies. And you're dealing with simple references, &, and not some wrappers.
The below is much too long, so yeah, just listen to the sibling comment. That's the essence of it, the below are mostly technical details.
---
When you allocate nodes in an arena, instead of getting back something like a Box<T>, or Rc<T>, you get a plain Rust reference--&'a mut T or &'a T.
Obviously, the first benefit is that these work well with pattern matching, field projection, and other useful language features,
They are also "zero cost" in a way that Box, Rc, and Arc are not--everything in any particular arena gets freed at the same time,
so there's no need for precise ownership tracking. In fact, &T in particular is Copy, aka freely duplicable, so you can pretty
much treat these &T references exactly like garbage collected pointers in a functional language!
Arenas have some other benefits, too. They have great locality of reference, are tightly packed (almost as tightly packed as
a vector), and in many cases let you allocate slices in addition to single references (so even if you think you need a Vec of
nodes, you can still often stick with pure arenas; and slices are, again, Copy, meaning they work well with pattern matching
and other parts of the language).
In the context of writing a compiler, arenas have another extremely useful property: they make it easy to efficiently create
recursive data structures (particularly immutable ones, but even ones with cycles if you are willing to use interior
mutability like `Cell<T>`). These recursive structures can use ordinary Rust references in the exact same way you would
managed pointers in a GC'd language. The only restrictions are that whatever nodes you point to should be allocated
in the same arena (or older), and a more complex type-related rule for safety that in practice doesn't hurt much.
The exact details are a little complicated, and it involves some subtle areas of the compiler, so feel free to skip this part (the tl;dr is that these rules usually apply). Essentially Rust can reason as follows:
* For safety, all references to values within a TypedArena must be accessible for at most as long as the TypedArena itself.
* Before the arena is dropped, its nodes are always accessible, meaning there are no restrictions on how they can be used.
So the problem case only occurs when not only do the node types stored in the arena include references to other nodes within
the arena (more conservatively, with the same lifetime as the arena), they also have destructors that actually follow that
field. It turns out that this almost never occurs in practice, so in theory virtually all Rust types should be usable with
cycles; but the language can't reason directly about field usage in that way at the moment. Instead, Rust provides three
mechanisms to make all this work out:
* Many types (all Rust primitives, many zero-sized types, and other "plain old data") simply lack drop glue altogether. Notably,
regular Rust references (&mut T and &T) fall into this category, but the "smart" constructors that are annoying to use with
pattern matching (Box<T>, Arc<T>, Rc<T>) do not. This is by far the best kind of type to use with arenas because it
maximizes their strengths--as there is no per-element drop code to run, Rust can do no per-element processing whatsoever
on destruction, allowing effective use of arenas to equal or even surpass the speed of the young generation of a
generational GC in the right circumstances.
There are some arenas that even go further, exploiting the fact that with
no drop glue you don't need to know what types are allocated to define an arena that lets you allocate heterogeneous types
into the same structure--the only restriction is that the types must be `Copy` (a proxy for not having a destructor, in
this case, as any type which has drop glue is prevented by Rust from also implementing `Copy`).
* Many other types in Rust have drop glue, but their own destructors are automatically generated by Rust. The Rust
autogenerateD destructor code is very straightforward and just recursively calls drop on all the subfields / variant data,
so as long as all of these are known not to use any fields with the lifetime of the arena, we can assume the parent type
doesn't, either.
* Finally, there are the cases of Rust types that do have a destructor, do have a field with the lifetime of the arena,
but don't try to follow that field within the destructor. While in reality this probably encompasses virtually all
remaining types, Rust can't currently deal with lifetimes that are in scope, but not alive (though this is a useful
concept in some other scenarios too). And in practice, the most likely scenario for encountering this involves using
a type like Vec<T>, Box<T>, Rc<T>, Arc<T>, etc. inside an arena, where T satisfies one of the other two rules, but
the outer container doesn't (since it has a destructor).
As Rust can't verify these scenarios itself, instead it provides an unsafe escape hatch, #[may_dangle], which can be
applied to a lifetime that isn't dereferenced in the destructor, or to a generic type parameter that is only used in
order to run its destructor manually somehow. Using this attribute in a `Drop` implementation makes the implementation
require `unsafe impl` and can only be done on nightly for new types, but it's implemented for all the types I just
mentioned, and more besides. This means that Rust immediately knows that Box<T> is safe to use in such a cyclic arena
as long as T is, and same with Arc<T>, Rc<T>, Vec<T>, etc.
So ultimately what this amounts to is, that if you put recursive types in an arena, nine times out of ten it will "just
work" and basically feel like you've turned Rust's ownership rules completely off, as long as the arena can manage to
stay in scope.
Obviously, there's no free lunch, and you can see that this approach gets a lot less attractive if you're talking
about storing things with unpredictable or highly irregular lifetimes (in an object lifetime sense), or if you want
to package things up as owned data, or be able to allocate them in a function that doesn't accept a context (that
library ecosystem is indeed great as you mentioned, but if you start using weird enough patterns it stops working
so well). But my experience, having done this sort of thing for a long time now, is that the tradeoffs for arenas
are usually worth it for at least some parts of a compiler, both for aesthetic and performance reasons. Their
relative lack of popularity is, I think, more a product of poor marketing than anything else (as you can see, the
arena story does fit into the borrows, ownership, and lifetime paradigm, but not in a straightforward way).
What a great writeup, thank you! I think I followed all that . Two things leap out at me:
- I can see arenas for a compiler, but I'm not so sure for an interpreter. While most of the memory allocated in Dark will be done within a single HTTP call (and so an arena might actually be appropriate), there are contexts where a GC cycle or two to cleanup might be appropriate. I'm guessing that arena's are an all-or-nothing approach?
- I'm using `im`, which I think also gets in the way of my nice pattern matching, right? Any solutions to that?
I also realized I should specifically address your "all or nothing" question, though: arenas absolutely aren't all or nothing :) In particular, a very common (well, by writing-a-compiler-in-Rust standards) pattern is to have two representations for your elements: one that uses Rc, that you use for longer-lived stuff, and another based on references, that you use for arena-scoped stuff. An extra term is added to the younger version that marks the use of a wrapper around an Rc type (recall that you can downcast Rc to reference, so you do not necessarily have to lose Copy to be able to do this, depending on your implementation). You can then implement a variant of generational collection by (prior to dropping your arena, i.e. the young generation), scanning any live objects using the young term type, and converting whatever you find to Rc nodes. The Rc nodes then persist as the older generation.
This kind of hybrid strategy is much more effective than using Rc for everything, and while it's still not as efficient as a proper garbage collector it still has roughly the kinds of properties you want from one. My experience (like that of many others) is that almost any workload you want to use this with will satisfy the generational hypothesis, especially in Rust where you only use GC for things that really need it, so hopefully you can see why it's sometimes worth going to the extra trouble to maintain several versions of the same type.
(Obviously, in OCaml, you can piggyback off the existing garbage collector and this is a nonissue).
- Well, it depends on how you intend your interpreter to be used, but if it's for long running programs, a garbage collector of some kind is essential. Rc<T> is a primitive garbage collector that happens to be provided by Rust, but it's not very efficient, so if you're concerned with performance you'd probably want to build your own (or try your luck with a community GC--I haven't tried them in a while, so maybe they've improved since I last looked, but there didn't seem to be a lot of promising options for automating this).
- I don't think so, unfortunately. Your best bet would probably be a macro, which I'm sure you've already considered. You might want to talk to the author though, as I'm sure she has thought about this a lot more than I have.
