As someone who doesn't write any Rust I'd like to understand this more. Is it the ownership model that makes trees weird? Is there something you guys do instead? I was working on an R-tree yesterday for something and I'm slightly surprised to read this but obviously Armin knows what he's talking about :)
The problem however comes when you want to reference the parent from a child. In the ownership/reference graph that would also count as an edge, and hence creates a cycle with the parent-to-child edge. There are workarounds like using weak reference counted pointers or indexes into arrays, but ultimately they don't offer the same ergonomics as other languages and it's better to design with only parent-to-child links.
In this case using `Rc` for the children and `Weak` for references to the parent does exactly this and is included in the stdlib, so I guess I'm missing your previous point of using "bare pointer". Did you mean that the safe interface should be built around the whole tree rather than just the parent reference?
Yes, it's true. Most of the time I had logic errors only in safe code and segfaults caused by unsafe code. But it's not a problem after C, where segfaults and memory leaks are norm.
> Did you mean that the safe interface should be built around the whole tree rather than just the parent reference?
Safe and sound (bulletproof) façade for the pointer and the tree. Safety is overloaded term in Rust. For example, when indices are used instead of references, it easy to make memory management mistakes invisible to rust compiler. Such code is "safe" in Rust terms, but unsound.
That doesn't really answer my question, the façade should be either:
- at the level of the pointer, meaning it offers the user all the functionality they need to code the tree data structure; - at the level of the tree, meaning the tree externally offers the user all the functionality they wanted from the tree, but the tree internally uses `unsafe` and maintains invariants that make its use sound.
> Such code is "safe" in Rust terms, but unsound.
You might not want to use unsound here, since that's overloaded too. The way I usually see and use those terms in a Rust context is:
- safe: code that does not use `unsafe` - sound: a safe interface (i.e. callable from safe code) that internally uses `unsafe`, but there is no way for the safe side to produce UB when calling it.
I would refer to the index code as "incorrect", "erroneous" or "buggy" instead to avoid the overload in this context.
I want to debug my code less, so I use sound interface to arrays: iterators. Other than that, both interfaces are equal.
If there is no ready to use method for my usage pattern, I can write unsound code directly, or I can write sound interface and then write sound code using it, so compiler will not allow me to write stupid mistakes. Unsound version will be faster to write, but may require more time to debug and support.
In programming language theory soundness is a property of a type system for which the safety theorem hold. In other words, if some program is well-typed according to such type systems then its execution following the rules of the language abstract machine reduces to some terminal value. "Undefined behaviour" is the opposite situation, where some program reaches a non-terminal state where no abstract machine rules applies to make progress, meaning the abstract machine does not describe or define the behaviour of that program and state pair.
In Rust's case the claim is that this holds only as long as you use its safe subset, in other words "rust's type system is sound for `unsafe`-less programs". This can then be extended to some particular `unsafe` code, making the claim "rust's type system is sound for `unsafe`-less programs plus this particular function/code", which is what is generally meant with "this unsafe code is sound".
Most (all?) type systems don't try to define what it means for a program to "work (properly)", that is generally left to the programmer. For those that do, then yes, unsoundness would mean that an accepted program does not work properly. I find it hard to imagine such a programming languages, though surely I will expect this to be parameterized over some specification that the type system assumes to be the final desired property. In any case this is far from what Rust promises.
> This arena tree structure is using just a single `Vec` and numerical identifiers (indices in the vector) instead of reference counted pointers. This means there is no `RefCell` and mutability is handled in a way much more idiomatic to Rust through unique (`&mut`) access to the arena. The tree can be sent or shared across threads like a `Vec`. This enables general multiprocessing support like parallel tree traversals.
Similarly getting a mutable reference to a leaf while parents have references to children is awkward
smarter sources: https://rust-unofficial.github.io/too-many-lists/ https://softsilverwind.github.io/rust/2019/01/11/Rust-Linked...
In this particular case, borrow checker does it job as designed. So, why to fight it?
The solution is to use an alternative automatic garbage collector instead of compiler built-in: arenas, RC with weak references, or Mark&Sweep GC. Arenas have better performance, because they drop all nodes at once. The easiest way to quickly implement an arena in safe Rust is to use vector (array) of nodes and used indices instead of direct references.
Rust by default forbids cyclic references, by forcing to use trees, which completely avoids the problem.
Linux kernel uses doubly linked lists, Redis uses doubly linked lists, V8 JS engine uses doubly linked lists. Have their authors chosen something obviously wrong?