[tyg13]

I don't think anyone was claiming the author was being intentionally deceiving, just that they're not very good at writing idiomatic Rust.

The first thing I'd suggest, as someone who's done their fair share of Rust compiler dev, is to stop using `Box` and `Ref` everywhere. Terms should not own their child terms; the idiomatic way to handle this is to use an arena and typed IDs, and pass a reference to the arena when you need access to the underlying data from the ID.

[foldr]

IIRC The Rust compiler just uses Cell<&’a> for child terms, which is a somewhat lighter weight solution that still allows mutation.

Edit: Either I remembered wrong or it's changed. Now it uses some kind of custom wrapper around Box: https://github.com/rust-lang/rust/blob/master/compiler/rustc... So actually, the Rust compiler itself uses owned children in its AST!

[solomonb]

So the solution to writing idiomatic code in the language whose essential feature is the ownership semantics and borrow checker is to not use the ownership semantics and borrow checker?

[tyg13]

This is sort of a flippant response, but I'll answer it seriously.

The premise of this question is incorrect: you can't not use the borrow checker in Rust. Instead, you are satisfying the borrow checker by ensuring at the point of use (deref of the ID) that there is valid data by providing a provably-live reference to the arena in which it was allocated.

In another language like C/C++, you'd just use a raw pointer, which is ergonomically-nice, but there's no guarantee that it actually points to a valid object. Rust forces you toward a solution that is guaranteed to be safe, and logically makes sense when you think about it -- nodes in a graph should not own other nodes in the graph; instead, they should be owned by the graph itself, and other nodes should simply hold references to each other. This is how you tend to implement safe and efficient graphs in C++ anyways, the only difference being that in Rust your references are indices, whereas in C++ your references are raw pointers.

[funcDropShadow]

But compilers deal usually with trees not general graphs.

[tyg13]

Even with a tree structure, you probably don't want your nodes owning their children just for the sake of being efficient with your allocations.