Back references - any progress?

help
1

This keeps coming up. Any progress?

The usual workarounds are:

  • Weak back references. Then you get run time errors at borrow_mut.
  • Putting everything in an array and using array indices. Then you get the equivalent of dangling pointer errors, expressed with index numbers.
  • Using unsafe code. That seldom ends well in when complicated data references are involved.

Every time I've had to use a debugger on Rust code in four years, it's been one of the last two in someone else's crate.

The elegant solution would be something like this:

  • Use Rc, RefCell, and Weak to create the data structures.
  • Have a static checker prove that no Weak upgrade or Rc borrow_mut can fail.
  • Convert safely to hard references.

This is very similar to statically checking that a thread can't deadlock itself by locking the same lock twice, something that's being worked on.

Any work going on in this area?

1 Like
2

Have a static checker prove that no Weak upgrade or Rc borrow_mut can fail.

Static checking across function boundaries will either require an analyzer that infers a lot automatically (which probably would be very slow and lead to spooky action at a distance) or aid from the language (such as lifetime annotations). So ISTM that you're asking for a more powerful lifetime system? I assume alternatives like arenas or garbage collectors are out?

There has been a cluster of blog-posts by various people about improving the situation for self-referential data (e.g. Further simplifying self-referential types for Rust) recently, often in the context of async code but this should also be useful in other contexts. But your problem statement is general enough that it's hard to tell if that would be sufficient for you or if you'd need something even more powerful.

2 Likes
3

That's a good paper.

It's more ambitious than what I had in mind. They want objects with back-references to still be moveable. That's hard, because something has to update the back-references. So they need move constructors and more heavy machinery to make that go.

I'd settle for pinning objects with back-references. That makes this much simpler.

The global analysis required is much like scope oriented borrow checking. The basic rule is that you can't have two conflicting references in active use at the same time. That's a scope overlap kind of problem.

I need to work up some examples. You can write back references now with Rc, RefCell, Weak, upgrade, borrow, and borrow_mut. It's hard to tell if you're going to have a failed upgrade or borrow at run-time, which is a source of bugs. The goal is to check that at compile time.

4

move constructors could also possibly allow fancy things like having two cursors into the same linked list.

5

Backreferences are fundamentally in contention with a core proposition of the language (everything is movable), so don't hold your breath. They should be the exception rather than the rule when designing your data structures, therefore, given good enough workarounds (such as Weak or index-based indirection), the enormous added complexity and overhaul required to support them as a language feature is 100% "the juice is not worth the squeeze" territory.

6

It depends on what the actual problem is. The problem description is overly general because back-references (i.e. cycles) essentially amounts to fully automatic memory management (e.g. garbage collection).
Constrained subsets of the problem may be more tractable with extensions to borrowchecking such as better support for self-referential types, ghost-cell or maybe Vale's region-based borrow checking (though I'm not sure if I understand correctly where it gets its claimed advantages).

2 Likes
7

The Ghost Cell and Static Rc approaches do roughly the right thing. But both projects are abandoned. The European Union funding ran out.

static-rc has the key idea: "the exact number of aliases is known at compile-time". That's enough to handle the case where A owns B and B needs a back-reference to A.
Anyone looked at that? It's experimental and abandoned, but seems to be a good idea.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.