You've missed a far more fundamental question: how does this interact with aliasing XOR mutability? That's the core reason why back pointers are hard: they result in complicated relationships between things, in that an &mut pointer to a child may not be independent of its owner. I suspect one would need annotations for different ways to handle this, like single threaded checking of mutability (which already exists: Cell and RefCell) or multi-threaded (Mutex, RWLock), essentially meaning that this would be inserting into the language things things that don't need to be there.
In any case, even switching to the correct Option::None syntax, your example doesn't actually make sense: &mut isn't an owning pointer, so it doesn't make sense to try to construct an owning tree with it. Maybe something like
is what you're trying to get at? In either example, the mutability question appears: in yours, b is mutated while an outstanding &mut borrow exists, and in mine, a is mutated while an outstanding &back borrow exists.
This all seems like it might be possible to solve for some special cases, but pointer aliasing is one of the hardest parts of static analysis. It's essentially impossible to do in the general case, and my intuition is that back pointers get you very close to the general case. It's not even obvious to me how one can get a binary tree with back pointers to work well.
> The compiler might optimize that out, observing that b is dead at deallocation.
Only if b doesn't have a destructor (or has a destructor that can be sufficiently inlined).
That's the core reason why back pointers are hard: they result in complicated relationships between things.
That's why they need built-in checking, rather than hacks using "unsafe". Use of back references is going to have to be restricted so you can't get two mutable handles to the same object. The trick is making that work through restrictions which can be checked locally.
That's not my point. A general built-in checking scheme that handles all the variations of linked lists and trees will likely have to have quite a few nobs to tweak for the various trade-offs one might want to make, and will likely have to be very general to handle all the variations, making that general infrastructure significantly more complicated (both to implement in the unsafe block that is the compiler, and, likely, for users to understand) than focused `unsafe` blocks, which can, and often are, packaged up into safe interfaces (like reference counting with weak pointers).
> Use of back references is going to have to be restricted so you can't get two mutable handles to the same object. The trick is making that work through restrictions which can be checked locally.
Talk is cheap, and I'm not sure this talk actually says anything of note. Those "ideas" seem to be the most obvious first considerations for working out how this feature might even work:
- disallowing two mutable handles is the fundamental rule of Rust,
- the ability to check locally is a strong convention for programming language implementations, and a very strong one for Rust.
Having some concrete idea that addresses just those two points (no need to worry about syntax or anything like that) would be an improvement on the current situation: I haven't see any for this other than "runtime checking" (already exists in Rust) and "no back references".
---
In other words, vague assertions like "Rust should support back pointers" with syntax ideas are jumping way ahead. The language typically tries to provide building blocks to allow things to be built in libraries, rather than lumping opinionated features into the language. These features will often then require unsafe to create safe abstractions, but this isn't bad: the compiler itself is essentially one large unsafe block.
The place to start would be trying to create a safe back-pointer interface in a library, and seeing if there's anything that is too hard to make truly safe. This has in fact already been done, with Rc/Weak and Arc/Weak, but for zero-overhead/non-reference-counted scenarios, I think a good place to start would be a smart pointer pair like Rc but with a constructor `fn make<T>(val: T) -> (Forward<T>, Back<T>)`.
In any case, even switching to the correct Option::None syntax, your example doesn't actually make sense: &mut isn't an owning pointer, so it doesn't make sense to try to construct an owning tree with it. Maybe something like
is what you're trying to get at? In either example, the mutability question appears: in yours, b is mutated while an outstanding &mut borrow exists, and in mine, a is mutated while an outstanding &back borrow exists.This all seems like it might be possible to solve for some special cases, but pointer aliasing is one of the hardest parts of static analysis. It's essentially impossible to do in the general case, and my intuition is that back pointers get you very close to the general case. It's not even obvious to me how one can get a binary tree with back pointers to work well.
> The compiler might optimize that out, observing that b is dead at deallocation.
Only if b doesn't have a destructor (or has a destructor that can be sufficiently inlined).