Support for intrusive data structures and unmoveable types

[glaebhoerl]

Rust currently has very poor support for intrusive data structures: it is extremely difficult or impossible to define a safe interface for them. This is because all types in Rust are moveable, and moving invalidates any pointers into the given value. Rust's current assumption is that values only have pointers pointing out from them, and any pointers into them are known statically and have their validity enforced at compile time by borrow checker restrictions. But this fails to accomodate the case where the validity of pointers into values is maintained by runtime code, as is the case for intrusive data structures.

We would like to be able to have a type such as:

pub struct IntListNode {
    value: int,
    prev: *IntListNode,
    next: *IntListNode
}

and allow client code to deal in instances of IntListNode directly and store them wherever, such as on the stack, with e.g. the Drop impl written to patch up prev.next and next.prev. The implementation would almost certainly require unsafe code, but we would like to at least expose a safe interface. This requires that IntListNode not be implicitly movable.

We could also have a trait such as:

trait Relocate {
    fn relocate(from: &move Self, to: &out Self);
}

for explicit moves of normally nonmoveable types, using &move and &out references to avoid the paradox of passing nonmoveable types by value. But we need nonmoveable types first. (relocate() should be equivalent to a clone() followed by a drop() on the original, except likely more efficient, and clone() itself may not be available.)

An "interesting" question arising from nonmoveable types is how to acquaint them with the generics system. (Do we have a Move bound, a la Copy? Do we require it to be explicitly specified? Or explicitly waived?)

[Kimundi]

Its already kinda possible to create unmovable types by borrowing self, see this as an example: https://gist.github.com/Kimundi/d846f1da490ef4e9b0d9

Or here a bit more integrated solution: https://gist.github.com/Kimundi/81b9944a896052b5407f

[reem]

I think what is desired here is not just the ability to mark types as not moveable, but to actually control the process of moving. I was thinking that this could be accomplished with @Kimundi's scheme if we require &'a mut self for the move, since that would lock the data forever, but then you can't move if you have updated, since the update borrow also lasts forever, &c.

[arielb1]

@Kimundi

Sure you can have non-movable types by not giving the user &mut references, but then you lose the benefits of ownership. What would help is user types that behave like &mut T - i.e. can be reborrowed, but don't allow moving the inner type.

I don't think a compiler-supported but user-defined Relocate trait would help – non-trivial move constructors are terrible. A Sized?-style explicit-waive Move could work, however.

[reem]

@arielb1 You could just have types which do non-trivial moves such as a Vec resize do a needs_move::<T>() check, which the compiler could optimize out after monomorphization.

I imagine we would introduce a new rule: types are either Copy or Move, and there is a blanket impl of Move for all non-Copy types which is just memcpy.

[glaebhoerl]

@arielb1, @reem Relocate wouldn't be compiler-supported (at least not in the sense of being implicitly invoked, which I'm assuming you meant), just a normal trait like Clone. The critical part is having nonmoveable types, and the Relocate trait is just something we could add once we do. (This is what I personally meant by what I wrote - of course other people may have different ideas.)

What I meant by Move was implicit movability, a la Copy. In other words Relocate is to Clone as Move is to Copy. But requiring explicit Move bounds might be onerous.

@Kimundi That's interesting and clever... I wonder if it's adequate for intrusive structures like IntListNode? But even if it currently is, I suspect that it won't be once we have new destructor semantics. I'm pretty sure doing this trick on types with destructors (as IntListNode would be) is precisely what would be forbidden - things with lifetimes you store in it must have lifetime strictly greater than the thing itself. (But maybe you could still do it with unsafe code?)

[arielb1]

@reem

Non-trivial move is a nightmare to work with, because it inserts user-defined operations to rather arbitrary places. A Move bound that works like Sized would work pretty well.

[glaebhoerl]

It strikes me that for an intrusive doubly-linked list type like IntListNode above to work well with the type system (i.e. not lead to undefined behavior), &mut borrows of it likely also have to be ruled out. The presentation above was simplified for exposition, but suppose we had value: Cell<int> rather than value: int, and allowed traversing the list and getting &Cell<int> references to the contained values. But this is not enough for safety, because we cannot rule out the possibility that another node has been &mut borrowed, and having &mut and & references to the same thing at the same time is undefined.

This is eerily similar to the restrictions on global statics: no moving, no &mut borrowing. It's probably not a coincidence: in both cases we lack the ability to statically keep track of potential references.

These restrictions also happen to correspond to the restrictions on things which are &-borrowed... which again makes sense: we essentially have the presumption that they are always shared.

[glaebhoerl]

Some more thoughts:

First, the fact that we seem to want essentially the same restrictions as which an & borrow has means that Kimundi's technique is a better fit than I thought at first. But is there any way to "lock" the variable from the get-go, or to work around the fact that it can be moved beforehand, without some kind of ugly runtime hacks?

This also reveals a deeper conundrum. Shared borrow restrictions prevent moving, even via relocate(). But this is for a reason! When is it safe to relocate()? If there can exist shared references to a given IntListNode at any time without you knowing about it, by traversing from other nodes, then it is never (provably) safe.

But it seems like being able to explicitly move is a capability you would want sometimes?

I don't have a great deal of experience with intrusive data structures. Can someone who does perhaps shed some light on how this sort of thing is usually reasoned about in other languages?

[pythonesque]

What would help is user types that behave like &mut T - i.e. can be reborrowed, but don't allow moving the inner type.

Like this? https://gist.github.com/pythonesque/d002384c29f83f9efd09

Pretty sure NoMoveGuard is unmovable in safe code.

_Edit:_ https://gist.github.com/pythonesque/d002384c29f83f9efd09#file-intlist-rs proof of concept.

[reem]

@pythonesque Just a note, but line 15 is undefined behavior due to undefined struct layout. You should construct it explicitly then transmute the lifetime only.

[pythonesque]

@reem: The NoMoveGuard is zero sized and markers have no alignment / size requirements. Is the behavior not defined in this context?

(Also, the lifetime doesn't actually change).

[reem]

I'm almost 100% sure that struct layout is always undefined, i.e. even going from T -> NewType(T) through transmute is UB.

[pythonesque]

Okay, updated to remove UB: https://gist.github.com/pythonesque/d002384c29f83f9efd09.

_Edit_ I'm not quite sure what about this requires completely immovable types: https://gist.github.com/pythonesque/d002384c29f83f9efd09#file-intlist2-rs is basically identical and doesn't use any unsafe code. So maybe I'm approaching this incorrectly.

[aidancully]

For what it's worth, I've done a lot of work with movable intrusive types. Generally in these cases, I use the intrusive structure to manage ownership of its container. That is, moving the intrusive structure moves the container at the same time. For example, if I use a linked-list to pass ownership of a structure from one thread to another, then I can use an intrusive link on the list to represent ownership of the containing structure. I'm not sure if I expressed that idea clearly, but it's a hope of mine that Rust will support code like that safely.

[glaebhoerl]

I went with the IntListNode example here because I thought it was simpler, but it's possible that this wasn't actually such a hot idea, and that this example can actually be expressed with lifetimes as they exist, as @pythonesque shows.

The use case which actually made me start thinking about intrusive data structures and unmoveable types was "a weak reference for any type" (not just Rc): you'd have a WeakEnabled<T>, from which you can form WeakRef<T>s, which has a method something like fn get(self: &WeakRef<T>) -> Option<&T>. And it's implemented (potentially) by threading a doubly-linked list through the WeakEnabled and all of its WeakRefs; when a WeakRef is moved or dropped (or cloned), the list is patched up around it in the obvious way; each WeakRef additionally contains a nullable pointer back to the WeakEnabled; and when the WeakEnabled is dropped, its destructor traverses the list and sets all of the back-pointers in the WeakRefs to null (after which get() will return None). Which sounds like a splendid plan right up until you realize that both the WeakEnabled and the WeakRefs can be moved at any time, invalidating the links. Perhaps this example can serve as better motivation than the previous one did?

@aidancully Unfortunately I don't understand what you're trying to say, even though I'd like to. What do you mean by "the intrusive structure" and "its container"? What does it mean to use a linked list to "pass ownership"?