5 ms·

Do you have any thoughts on how it might even begin to be possible to do back pointers safely, in ways that don't already exist in Rust? I find it very confusi

• Animats 9y ago
  Do you have any thoughts on how it might even begin to be possible to do back pointers safely, in ways that don't already exist in Rust? First, you need to be able to talk about them. A forward ref/back ref pair has to be identified with some form of declaration at compile time. The forward pointer is an ordinary owning pointer. The back pointer is special. So add a variable attribute "back", to be used like much like "mut", but only on a reference field of a struct. Let's see if that's enough. The invariants to be enforced are: - If b.bak points to a, a.fwd must point to b. - If a.fwd points to b, b.bak must be Option(None) or point to a. These can be enforced by some simple update checks when a.fwd or b.bak is updated. The normal sequence of events is something like: a.fwd = &mut b; b.bak = &back a; or, when breaking a link, b.bak = Option(None); a.fwd = None; // drop ownership of b, which deallocates it. You have to clear the back reference before dropping the object, to avoid a dangling pointer situation. The compiler might optimize that out, observing that b is dead at deallocation. If you try to change b.bak to anything but Option(None) or a, that's an error. If you try to change a.fwd while b.bak is not Option(None), that's an error. This can usually be checked at compile time. Open questions: - Can the compiler figure out which field of a is the forward ref? That's the ref that owns b. Or is syntax needed in the declaration of the a struct for that. - What about arrays of forward refs?
  • dbaupp 9y ago
    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 a.fwd = Some(b); a.fwd.as_mut().unwrap().bak = Some(&back a); 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).
    • Animats 9y ago
      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.
      • dbaupp 9y ago
        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>)`.