What is pure on-the-stack-but-still-movable intrusive linked lists?

Question

I am reading The Rustonomicon. There is a sentence which mentions the pure on-the-stack-but-still-movable intrusive linked lists:

Move constructors are meaningless in Rust because we don't enable types to "care" about their location in memory. Every type must be ready for it to be blindly memcopied to somewhere else in memory. This means pure on-the-stack-but-still-movable intrusive linked lists are simply not happening in Rust (safely).

What's the meaning?

Answer 1

Key terms:

• "intrusive": An intrusive collection is one that requires the elements themselves to hold some data on behalf of the collection. Often this can be done with graph-based structures like linked lists, trees, some kinds of hash maps.

  For our purposes, lets say we have a Person type with many fields:

  struct Person {
      name: String,
      age: u32,
      favorite_food: Option<String>,
      next_person: *const Person,
  }
  

  Notice the next_person pointer; the Person type knows that it is part of some linked-list structure and is storing a pointer to the next person on its behalf.

  • What does it mean for a data structure to be "intrusive"?
  • intrusive-collections crate

• "on-the-stack": means that the data is stored in-place within a local variable and is not in a heap-allocating type (Box, Rc, Arc, etc). What is important here is that moving a heap-allocating type like Box does not move its contents; the contents are address-stable (unless they are moved explicitly via dereference or swap/replace call).

  • What and where are the stack and heap?

With that knowledge combined with what is said earlier in the paragraph (that types don't know when they are moved) means that, if you were to make an intrusive linked-list that was not able to use the heap, any move of an element in the list would break the list because a previous pointer would now be invalid and there is no mechanism to fix it automatically.

Answer 2

A move constructor is one which moves an object to a different location in memory, instead of copying it. For example, if an object is allocated on the stack but its lifetime needs to be longer than the current stack frame (e.g. if the function wants to return it, or pass it somewhere that wants to store it), it would need to be copied to the heap. This also means that pointers to the object's old location must be updated (or, typically, wiped); this is why C++ move constructor arguments are of type T&&, because they need to know where the old pointer is stored so they can overwrite it, i.e. they need a pointer to a pointer. However, a problem arises if there is more than one pointer to the old location, because the move constructor will only fix one of them.

An intrusive linked list is one where the list elements themselves contain a pointer to the next item in the list, instead of having "list node" objects which each hold a list element plus a pointer to the next node. (This is done to save memory by reducing the number of different objects.) This isn't inherently more dangerous than a regular linked list, but it makes it more likely that some object can have multiple pointers to it, because the object serves two different purposes.

So, what this paragraph is saying is that you don't need move constructors in Rust, because the borrow checker will ensure that there won't be any remaining (usable) pointers to the old location of an object after it is moved. The mention of intrusive linked lists is merely an example of where this safety matters.