Actually, Rust's rules really wants your data to look like trees. Requiring each value to have exactly one owner is not really different than requiring each node of tree to have exactly one parent.

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.

Why you want to create cyclic reference from child to parent instead of a bare pointer?

Because dereferencing a raw pointer in Rust requires unsafe.

Everything in Rust requires unsafe code at some point. Encapsulate unsafe code under safe and sound façade, and hide it in a library. Or use an existing library for memory management: arenas, RC, or a Mark&Sweep GC (rust-gc, pgc), etc.

Encapsulating unsafe code behind a safe interface is not so easy (especially when cycles like these are involved) and there's always the danger of getting it wrong, so you generally want to avoid doing that.

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?

> Encapsulating unsafe code behind a safe interface is not so easy (especially when cycles like these are involved) and there's always the danger of getting it wrong, so you generally want to avoid doing that.

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.

> Safe and sound (bulletproof) façade for the pointer and the tree

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.

UB and unsoundness are different things. "If it compiles, then it works (properly)" is true for sound code only. Direct indexing of arrays with `for` loop is unsound, because of typical errors with indexes, such as off by one. Iterators are sound.

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.

> UB and unsoundness are different things. "If it compiles, then it works (properly)" is true for sound code only.

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.

I agree completely, but I should point to a problem: it's easy to implement unsound virtual machine on top of sound language. When developers uses indices to simulate references, to circumvent borrow checker, they are doing exactly that. Then again, a sound façade can be built around unsound code, like `indextree` crate does:

> 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.

it's a pain if you want children to reference their parents while their parents reference them

Similarly getting a mutable reference to a leaf while parents have references to children is awkward

I know just Rust basics, what specifically makes it awkward? I'm not a heavy Rust user, so I'm having a hard time following, do you have any simple pseudo-Rust code you could share? I'm also a basic CRUD app dev by day, hobbyist by night.

I'm not a rust expert by any means, but I believe there's a problem with lifetimes. There are many ways to implement double-linked lists (think C++ smart pointers), but when you try to squeeze performance and use references, then it's a fight against borrow checker, which ends with the need to use unsafe rust.

smarter sources: https://rust-unofficial.github.io/too-many-lists/ https://softsilverwind.github.io/rust/2019/01/11/Rust-Linked...

Borrow checker is just a checker, which ensures that programmer doesn't write obviously wrong programs. It's obviously wrong to create cyclic references, even in a language with garbage collector, such as JavaScript. Why you need to fight with checker?

Regarding the borrow checker, what you say is not correct. The borrow checker's rules are stricter than absolutely necessary. It is designed to reject all invalid programs, but it also rejects some valid programs.

Yes, rust compiler team improves borrow checker from time, to allow more valid programs to pass the checker. However, in practice, it's always possible to use unsafe code to do the job, and then build a safe façade for it.

In this particular case, borrow checker does it job as designed. So, why to fight it?

garbage collectors detect cycles. you may be thinking of reference counting. CPython includes a gc for cycle detection

Some GC detects cycles, some not (reference counting is example of GC which does not), but even those which detects cycles, may not able to detect all of them or it can be expensive as, for example, in typical Mark&Sweep GC, because it may require to stop the world to perform GC, which is unacceptable for system programming languages, like C, C++, Rust.

You can have completely pauseless GC tracking, also in Rust.

Why would it be obviously wrong?

When tree will go out of scope, their nodes memory will be reclaimed automatically ("dropping" in Rust terms) by automatic garbage collector built-in into compiler: `drop(root)->drop(leaf_a),drop(leaf_b)`. However, if leaf will have reference to its parent, then an infinite loop occurs: `drop(root)->drop(leaf_a)->drop(root)->drop(leaf_a)...`

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.

You've said it would be obviously wrong "even in a language with garbage collector, such as JavaScript." But, obviously, most modern GC can handle cyclic references just fine.

But even languages with Tricolour Mark&Sweep GC, which handles cyclic references just fine, it's still possible to make memory leak via a dangling reference to a node in a complex cross-linked graph, because language and GC allows that.

Rust by default forbids cyclic references, by forcing to use trees, which completely avoids the problem.

You can leak memory in any complex project, even if you only use safe Rust.

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?

Rust uses double linked lists, they are not harder to implement in Rust than in any other language. Moreover, built-in borrow checker will help to implement them properly, without memory leaks or use-after-free. What is your point?

My point is that it's not obviously wrong to create cyclic references.

OK, it's was obviously wrong to create cyclic references few years ago.

But doubly linked lists use cyclic references…

Double linked lists use double links.

Some people are trying to use references everywhere everytime, instead of (safely wrapped) pointers. It's a mental lock.