Support for intrusive data structures and unmoveable types

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?)

No file, test, or entry point is named. Start by separating the requested nonmoveable-type, relocation, and generics questions in the issue; done requires a decided design and an RFC-ready specification.