3 ms·

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

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/rustbacklinks.md https://github.com/John-Nagle/technotes/blob/main/docs/rust/...

mustache_kimono 1y ago
> But it's really wordy and there's a lot of run time overhead. I'm curious: what do the benchmarks say about this?
kurante 1y ago
Have you seen GhostCell[1]? Seems like this could be a solution to your problem. [1]: https://plv.mpi-sws.org/rustbelt/ghostcell/ https://plv.mpi-sws.org/rustbelt/ghostcell/
- Animats 1y ago
  Yes. There's an implementation at https://github.com/matthieu-m/ghost-cell 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.
- zozbot234 1y ago
  The qcell crate is perhaps the most popular implementation of GhostCell-like patterns. But the ergonomics is a bit of a challenge still.
  - Animats 1y ago
    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.
zozbot234 1y ago
> 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.
SkiFire13 1y ago
> when what's happening under the hood is > sometype.upgrade().unwrap().borrow().name I suspect a hidden `.unwrap()` like that will be highly controversial.
- Animats 1y ago
  .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.
  - SkiFire13 1y ago
    `.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.
    - Animats 1y ago
      > `.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.

mustache_kimono 1y ago

> But it's really wordy and there's a lot of run time overhead. I'm curious: what do the benchmarks say about this?

kurante 1y ago

Have you seen GhostCell[1]? Seems like this could be a solution to your problem. [1]: https://plv.mpi-sws.org/rustbelt/ghostcell/ https://plv.mpi-sws.org/rustbelt/ghostcell/

Animats 1y ago
Yes. There's an implementation at https://github.com/matthieu-m/ghost-cell 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.
zozbot234 1y ago
The qcell crate is perhaps the most popular implementation of GhostCell-like patterns. But the ergonomics is a bit of a challenge still.
- Animats 1y ago
  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.

zozbot234 1y ago

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

SkiFire13 1y ago

> when what's happening under the hood is > sometype.upgrade().unwrap().borrow().name I suspect a hidden `.unwrap()` like that will be highly controversial.

Animats 1y ago
.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.
- SkiFire13 1y ago
  `.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.
  - Animats 1y ago
    > `.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.