by Animats | 2025-10-04 18:14:46+00:00
There are two main cases:

- Single ownership with back references that never outlive the owning reference

This requires a construct that manages the forward and back references together, preserving the invariant that A->B->A. It's also necessary to insure that no non-weak back reference from B to A exists when A is dropped.

- True multiple ownership with weak back references

This is the hard case. It might be solveable for complicated situations. See the example in my tech note that links to a Rust Playground file.[1] That's not a contrived example; it's code in actual use. It builds a set where all elements of the set can find the set itself. If two sets are merged (union), all elements move to one set struct, and the other now-empty set struct is discarded. All the back references are maintained during this operation.

Most back references seem to fall into one of those two cases. In fact, the second includes the first. The first is so common that it's worth handling separately.

The core problem is finding an approach which is 1) powerful enough to be useful on real code, and 2) not too hard to check at compile time. The second case requires some restrictions on coding style.

The preferred coding style is short borrows with very narrow scope, typically within one statement. That's normally considered bad, because it means extra time checking for double borrows. But if this kind of borrow can be made compile-time, it's free. The compiler is going to have to check for overlapping borrow scopes, and the more local the borrow scope, the less compile time work is involved. Storing a borrowed link in a structure or a static requires too much compile-time analysis, but if the lifetime of the borrow is very local, the analysis isn't hard. Borrow scopes which include a function call imply the need for cross-function call tree analysis. It's been pointed out to me that traits and generics make this especially hard, because you don't know what the instantiation can do before generics are instantiated. That might require some kind of annotation that says to the compiler "Implementations of function foo for trait Foobar are not allowed to do an upgrade of an Rc<Bar>". Then, at the call, the compiler can tell it's OK for a borrow scope to include that call, and in an implementation of the called function, upgrade of Rc<Bar> is prohibited. In fact, if this is done for all functions that receive an Rc<Bar> parameter, it might be possible to do all this without call tree analysis. It's becomes a type constraint. Need to talk to the type theorists, of which I am not one.

All those .borrow() calls are annoying. It might be possible to elide them most of the time, in the same way that you can refer to the item within an Rc without explicitly de-referencing the Rc. That would be nice from an ergonomic perspective. But it runs the risk of generating confusing compiler messages when a problem is detected. It would be like those confusing error messages that arise when type inference can't figure something out or the borrow checker needs explicit lifetime info to resolve an ambiguity.

[1] https://play.rust-lang.org/?version=stable&mode=debug&editio...