Comment by Animats | Hacker News Reader

Comment by Animats | Hacker News Reader

This is going to take some serious reading.

I've been struggling with a related problem over at [1]. Feel free to read this, but it's nowhere near finished. I'm trying to figure out how to do back references cleanly and safely. The basic approach I'm taking is

- We can do just about everything useful with Rc, Weak, RefCell, borrow(), borrow_mut(), upgrade, and downgrade. But it's really wordy and there's a lot of run time overhead. Can we fix the ergonomics, for at least the single-owner case? Probably. The general idea is to be able to write a field access to a weak link as

    sometype.name

when what's happening under the hood is

    sometype.upgrade().unwrap().borrow().name

- After fixing the ergonomics, can we fix the performance by hoisting some of the checking? Probably. It's possible to check at the drop of sometype whether anybody is using it, strongly or weakly. That allows removing some of the per-reference checking. With compiler support, we can do even more.

What I've discovered so far is that the way to write about this is to come up with real-word use cases, then work on the machinery. Otherwise you get lost in type theory. The "Why" has to precede the "How" to get buy-in.

I notice this paper is (2024). Any progress?

[1] https://github.com/John-Nagle/technotes/blob/main/docs/rust/...

Have you seen GhostCell[1]? Seems like this could be a solution to your problem.

[1]: https://plv.mpi-sws.org/rustbelt/ghostcell/

Yes. There's an implementation at https://github.com/matthieu-m/ghost-cell

Not clear why it never caught on.

There have been many attempts to solve the Rust back reference problem, but nothing has become popular.

The qcell crate is perhaps the most popular implementation of GhostCell-like patterns. But the ergonomics is a bit of a challenge still.

Right. The whole problem with all this is ergonomics, from the point of view of programmers who don't want to obsess over ownership and type theory. We sort of know how to make this work. It works fine with enough Rc/Weak/etc. But it's a huge pain.

I appreciate people arguing over this. It helps. We've seen proposals from people who are too much into the type theory and not enough into ease of use. I used to do proof of correctness work, where the problem is that proof of correctness people are too into the formalism and not enough into killing bugs.

> The general idea is to be able to write a field access to a weak link as

  sometype.name

> when what's happening under the hood is

  sometype.upgrade().unwrap().borrow().name

You could easily implement this with no language-level changes as an auto-fixable compiler diagnostic. The compiler would error out when it sees the type-mismatched .name, but it would give you an easy way of changing it to its proper form. You just avoid making the .name form permanent syntactic sugar (which is way too opaque for a low-level language like Rust), it gets replaced in development.

> when what's happening under the hood is

> sometype.upgrade().unwrap().borrow().name

I suspect a hidden `.unwrap()` like that will be highly controversial.

.borrow() already has a hidden unwrap. There's try-borrow(), but the assumption for .borrow() is that it will always succeed.

What I'd like to do is move as much of the checking as possible to the drop() of the owning object, and possibly to compile time. If .borrow() calls are very local, it's not too hard to determine that the lifetimes of the borrowed objects don't overlap.

Upgrade is easy to check cheaply at run time for Rc-type cells. Upgrade only fails if the owning object has been dropped. At drop, if weak_count == 0, no dangling weak references outlive the object. If there are more strong references, drop would not be called. With that check, .upgrade() will never fail.

After all, when a programmer codes a potentially fatal .borrow(), they presumably have some reason to be confident the panic won't trigger.

`.borrow()` is also a function call and thus it's not totally unexpected that it may panic.

What you're propositing however is to have the *`.name` syntax* do a lot of work and even potentially panic. That's the controversial part.

> If .borrow() calls are very local, it's not too hard to determine that the lifetimes of the borrowed objects don't overlap.

It's not too hard when you see the `.borrow()` and `.borrow_mut()`, but it becomes much harder when they become invisible and you have to check all `.field` accesses for this.

> Upgrade only fails if the owning object has been dropped. At drop, if weak_count == 0, no dangling weak references outlive the object. If there are more strong references, drop would not be called. With that check, .upgrade() will never fail.

I'm not sure what's your point here. `.upgrade()` will fail if all the owning `Rc`s have been dropped, and that's enough for this to be problematic.

> `.upgrade()` will fail if all the owning `Rc`s have been dropped, and that's enough for this to be problematic.

Want to catch that where the Rc is dropped, not at .upgrade time(). And maybe at compile time eventually.

> It's not too hard when you see the `.borrow()` and `.borrow_mut()`, but it becomes much harder when they become invisible and you have to check all `.field` accesses for this.

Good point. This is checkable at run time, but the error messages will be terrible, because you don't know who's got the conflicting borrow. You only know it exists. It's very similar to finding double-lock mutex deadlocks, though. Post-mortem analyzers can help. Maybe in debug mode, save enough into to produce messages such as "PANIC - double borrow at foo.rs, line 121. Conflicting borrow of the same item was at bar.rs, line 212." That's useful for locks, too. Problems of this class are all of the form "this thing here conflicts with that thing way over there", and users need to know both ends of the conflict. The Rust borrow checker is good about that.

This works much better if we have borrow lifetime checking at compile time. I've written a bit about that, and need to overhaul what I've written.

> Want to catch that where the Rc is dropped, not at .upgrade time(). And maybe at compile time eventually.

Catching that at compile time will require something that looks more like a reference into the `Rc` than a `Weak`. Most likely not the ergonomics that you want.

Catching at runtime is IMO not much different than panicking on the field access and IMO it's not enough.

> This is checkable at run time

Not sure how you check that a panic cannot occur at runtime without panicking in the first place...

> It's very similar to finding double-lock mutex deadlocks, though.

I'm not sure how they are similar. Last time I checked mutexes still required an explicit `.lock()` to be locked.

> Problems of this class are all of the form "this thing here conflicts with that thing way over there", and users need to know both ends of the conflict. The Rust borrow checker is good about that.

The last sentence doesn't make sense. You wanted to use `Rc`, `Weak` and `RefCell` precisely to avoid the kind of restrictions that are needed for the borrow checker to perform its analysis. Either you keep those restrictions and you have reference semantics or you discard them and are forced to perform runtime checks. There's no free lunch.

Your arguments basically boil down to hypothetical compile time check that doesn't exist or to arguing that hidden runtime checks are fine because you can test the code in debug mode to hopefully catch them failing. Neither of them are convincing enough.

> But it's really wordy and there's a lot of run time overhead.

I'm curious: what do the benchmarks say about this?

Reply on news.ycombinator.com