[Pre-RFC] Substructural Type System

language design
1

Summary

Rust has parts of a substructural type system, but it is incomplete. A substructural type system is extremely important to correctly capture the behavior of real computer systems in the absence of garbage collection and presence of non-memory resources. As Rust has grown, the incomplete nature of Rust’s substructural type system has caused more and more problems, such as the Leakpocalypse, endless Rc cloning problems, and the scoped task trilemma. We can resolve many very thorny correctness and ergonomics problems throughout the language and library ecosystem by finishing the substructural features.

Motivation

Rust's incomplete implementation of substructural traits continues to cause problems in more and more cases. Leak/Forget is the most well-known, and pin! is the consequence of not having a Move trait. However, there is still debate over whether Move should ever allow non-trivial move behavior, or if there needs to be a separate trait to handle it. Likewise, while Clone captures non-trivial copy behavior, there is now a proposal for "cheap" (or implicit) clones in the Ergonomic ref-counting proposal (possibly using a Handle trait). It seems Rust's efforts to fix the type system is unknowingly working towards a substructural type system. It doesn't seem like Rust realizes all these traits have corresponding substructural operations, as we can see in this table:

Explicit Implicit Trivial
Contraction Clone Handle Copy
Weakening Delete Drop Leak/Forget
Exchange Transfer Relocate Move

A substructural type system provides ways to restrict three specific (and usually implicit) operations, known as Contraction, Weakening, and Exchange.

  • Contraction means that if you can do an operation with two of something, you can also do it with one of that thing by using it for both, or in other words it’s possible to copy something.
  • Weakening means that if you can do an operation without something, you can also do it with that thing, or in other words you can discard things you don’t need. This is vaguely similar to Drop.
  • Exchange means that if you can do an operation with an A and a B then you can also do it with a B and an A, or in other words you can rearrange and move things around.

As we can see from the table above, Rust has implemented traits for explicit Contraction, implicit Drop, and trivial Contraction. Current proposals are trying to add a concept of implicit Contraction (possibly as a Handle trait), and to create explicit marker traits for concepts the Compiler currently unconditionally assumes: trivial Weakening (in the form of a Forget trait) and trivial Move (which is currently worked around using the pin! construction).

  • Explicit operations require an explicit method call in the source code, and as such may do arbitrary expensive things that we would conventionally expect to be visible, for example cloning a large vec may have to do arbitrary amount of copies (or other computation) to handle every element of the vector.
  • Implicit operations are ones that require custom code but only have to do a small constant amount of work, like copying an Rc which needs to only write to memory a small constant amount of data. (in my benchmarking it costs about as much as copying a struct with four fields on the stack).
  • Trivial operations are ones that entirely elide into a standard memcpy, memmove, or memdrop, like copying primitives or structs of primitives.

Currently, Contraction is reified as the Copy-Clone hierarchy and sort of implements Weakening with Drop (Rust unconditionally assumes that all types can be dropped, the Drop trait actually just represents performing logic at the time of the drop, which causes problems we will discuss later). Rust's only concept of Exchange is the compiler's assumption of all types having a trivial Move, which still has no proposal yet for being extracted into a marker trait.

If we were to abandon Rust's current naming scheme to more closely match each trait to their substructural equivalents, our table would look like this:

Explicit Implicit Trivial
Contraction Clone Copy TrivialCopy
Weakening Delete Drop TrivialDrop
Exchange Transfer Move TrivialMove

Such a renaming is likely impossible for backwards compatibility reasons, so we will be sticking with the existing traits, and the proposed traits Handle, Forget. To minimize confusion, we will use our theoretical Delete, Transfer, Relocate and Move traits, since most current discussions around a Move trait assume it represents a trivial move operation, although no move RFC has yet been proposed.

With this implementation, Rc becomes Handle and Move unconditionally, Drop if the thing it contains is Drop, and Delete if the thing it contains is Delete. Similarly, Box is Clone if the thing it contains is Clone, Handle if the thing it contains is Handle, Delete if the thing it contains is Delete, Drop if the thing it contains is Drop, and Move unconditionally.

pin! is no longer needed for futures, which can simply not provide an Exchange implementation, by not implementing Transfer, Relocate, or Move. The Handle trait then makes using Arc/Rc smart pointers easier by providing a clear implicit operation.

Currently, Drop requires performing arbitrary amounts of compute or IO at a region of the program that doesn’t even name the thing causing it. By separating Delete from Drop, providing the Forget trait to mark the trivial case, and enforcing the Contraction requirement, it becomes much more clear when expensive operations are being used and when guard drop operations could be expensive. This solves the problem of guard types potentially being implicitly dropped instead of needing to be explicitly dropped - by only implementing Delete, a guard type for a lock would always have to be explicitly dropped by the user.

Guide-level explanation

We will skip examples from the current Handle and Forget proposals, which focus on Rc ergonomics and scoped APIs, respectively. It is well-known that an implementation of Move would allow simplifying async APIs:

impl<A, B> Future for Either<A, B>
where
    A: Future,
    B: Future<Output = A::Output>,
{
    type Output = A::Output;

    // No more `pin` needed
    fn poll(self: &mut Self, cx: &mut core::task::Context<'_>) -> Poll<Self::Output> {
        match self {
            Either::A(x) => x.poll(cx),
            Either::B(x) => x.poll(cx),
        }
    }
}

What's also interesting is that a non-trivial move actually allows moving self-referential types around, because now code can be run to re-assign the internal pointers (but this would require allowing users to construct self-referential data types in the first place, which is still up in the air).

struct ParseState {
    data: String, // This should probably get some kind of marker that a borrow into the contents already exists, but that can be decided later
    pos: &'self str,  // points into `data` (using imaginary method of user-accessible self-referential structs)
}

impl !Move for ParseState {}
impl !Relocate for ParseState {}
impl Transfer for ParseState {
  // Imaginary example of what an explicit move function might look like using a magic calling convention
  extern "inline-self" fn transfer(self) -> Self {
    let mut r: MaybeUninit::<Self>::uninit();
    let offset: isize = unsafe { (self.pos as *const str).offset_from(&self.data as *const str) };
    let ptr = r.as_mut_ptr();
    unsafe {
      std::ptr::addr_of_mut!((*ptr).data).write(self.data);
      std::ptr::addr_of_mut!((*ptr).pos).write(&(&(*ptr).data)[offset as usize..]);
    }
    unsafe { r.assume_init() }
  }
  
  // Alternative imaginary example of what an explicit move function might look like using &own and &construct references with safe code
  fn transfer(self: &own Self, target: &construct Self) {
    let offset: isize = unsafe { (self.pos as *const str).offset_from(&self.data as *const str) };
    std::mem::drop(self.pos);
    std::mem::transfer(&own self.data, &construct target.data);
    target.pos = &target.data[offset as usize..];
  }
}

It is also possible to solve the implicit drop problem with guard types on locks, by implementing the explicit Delete trait (and opting out of the default Forget trait):

use std::ops::Deref;

struct Foo {}

struct Mutex<T> {
    // We keep a reference to our data: T here.
}

struct MutexGuard<'a, T: 'a> {
    data: &'a T,
}

// Locking the mutex is explicit.
impl<T> Mutex<T> {
    fn lock(&self) -> MutexGuard<T> {
        // Lock the underlying OS mutex and return a guard
        MutexGuard {
            data: self,
        }
    }
}

// Disallow implicitly dropping MutexGuard
impl !Forget for MutexGuard {}

// Explicit Destructor for unlocking the mutex.
impl<'a, T> Delete for MutexGuard<'a, T> {
    fn delete(&mut self) {
        // Unlock the underlying OS mutex.
        //..
    }
}

// Implement Deref so we can treat MutexGuard like a pointer to T.
impl<'a, T> Deref for MutexGuard<'a, T> {
    type Target = T;

    fn deref(&self) -> &T {
        self.data
    }
}

fn baz(x: Mutex<Foo>) {
  {
    let xx = x.lock();
    xx.foo();
    // Compiler error! Cannot implicitly drop MutexGuard when it goes out of scope!
  }
  {
    let xx = x.lock();
    xx.foo();
    std::mem::delete(xx) // not using .delete() to avoid confusion due to Deref
    // Compiles because xx is now deleted before going out of scope.
  }
}

Making the ability to destroy something an explicit trait also allows us to create types that cannot be destroyed unless manually disassembled. Such types are, by definition, not UnwindSafe, so they can't be safely used in contexts where unwinding might occur. This is extremely useful for creating reservation types that track some underlying resource without needing to bundle an Rc pointer to it. Instead, forgetting to call a function that consumes the reservation type will always result in a compiler error.


struct Wrap(usize);

impl !Forget for Wrap {}

struct Reserved {
    id: Wrap,
    pub area: f32,
}

// Disallow destroying Reserved (also implies !UnwindSafe)
impl !Delete for Reserved {}

// May or may not be necessary depending on how the Drop fiasco is handled
impl !Forget for Reserved {}

struct TextureAtlas {
  areas: HashMap<usize, f32>,
  count: u64,
}

impl TextureAtlas {
  pub fn reserve(&mut self, area: f32) -> Reserved {
    let id = count;
    count += 1;
    self.areas.insert(id, area);
    Reserved {
      id: Wrap(id),
      area,
    }
  }
  
  pub fn release(&mut self, reservation: Reserved) {
    // Move all !Forget elements out of reservation
    let id = reservation.id;
    
    let old = self.areas.remove(id.0).unwrap();
    assert_eq(old, area);
    
    // As long as all non-forgettable fields in `reservation` have been moved out of, this will compile. If we had missed any fields, this would fail to compile.
    // Optionally, the compiler could also error on any forgettable fields that have custom drop logic.
  }
}

More formally, uninitialized memory is trivially droppable, or Forgettable. A custom deletion can be accomplished by moving or deleting all non-Forget members of the type, leaving only uninitialized memory or Forgettable types. This is how &own and &construct connect to substructural typing, because they represent references to a region that must become uninitialized or become initialized before the end of the function. &construct can allow making self-referential structs by writing fields into the region one at a time and has the normal borrow checker guarantees of not being able to access an uninitialized field. &own facilitates custom destruction or consumption logic to operate in place.

Reference-level explanation

Some of the technical details of this RFC are covered by its prerequisites, like new auto-traits and Forget. However, the move traits would introduce a unique auto-trait situation, covered below.

Just like how Copy currently implies Clone, the insertion of an implicit Handle trait would imply Copy: Handle and Handle: Clone. The rest of the traits should follow a similar hierarchy, except we run into a problem with the Drop related traits (more on that later):

Explicit Implicit Trivial
Clone Handle: Clone Copy: Handle
Transfer Relocate: Transfer Move: Relocate
Delete Drop: Delete Forget: ???

Note that UnwindSafe must also imply Delete.

Move Trait Requirements

In order to satisfy the substructural trait hierarchy, the set of Move traits (Move, Relocate and Transfer) should mimic the trait inheritance pattern of the Clone traits. However, unlike Copy/Handle/Clone, Move is an auto-trait, and if Move implies Relocate and Relocate implies Transfer, then both Relocate and Transfer must therefore also be auto-traits. This by itself isn't a problem, it's the fact that Transfer must be an auto-trait despite not being a marker trait.

To handle the novel situation of a non-marker auto-trait, the trait could simply provide a default implementation of fn move() that is mapped to or corresponds to the compiler's internal move operation. This would require relaxing restrictions on auto traits and ensuring the compiler move operation still behaved correctly even with the autotrait.

Because of this complication, a Move trait proposal is likely to first limit itself to only the trivial case. However, this is potentially problematic for future compatibility reasons unless handled very carefully. Consider the following situation with a Move marker trait for the trivial case:

struct Unmovable {
    bar: i32
}

impl !Move for Unmovable {}

fn requires_move<T: Move>(x: &T) {}

fn foo() {
  let y = 3;
  requires_move(y); // Success, y implements Move
  let x = Unmovable{ bar: 2 };
  requires_move(x); // compile error, x does not implement Move
}

Now, in a later RFC, we want to split Move into an explicit, implicit, and trivial case. The only way to handle this correctly is to change Move from representing a trivial move to representing a fully explicit move, because implicit and trivial both imply an explicit move due to the trait hierarchy. This means that the final set of traits will need to a different name for implicit and trivial move traits, because Move will have to mean an explicit move. Luckily, the change from Move being a marker auto-trait to being a trait with a function with a default implementation isn't a problem, because you don't need to specify the function if it has a default implementation.

However, without modifying how auto-traits work, making something unmovable would require removing three traits, which is both annoying, and makes the migration a breaking change:

struct Unmovable {
    bar: i32
}

// Have to do explicit negative impls for all 3 move traits!
impl !Transfer for Unmovable {} // This should ideally just imply the other two.
impl !Relocate for Unmovable {}
impl !Move for Unmovable {}

To facilitate a smooth transition (and to make it less annoying to create unmovable objects), negative trait impls will have to be modified so that, at least for auto-traits, a negative trait impl for Foo would automatically imply a negative trait impl for any auto-trait that has Foo as a supertrait. This would ensure that a negative trait impl for the explicit case would automatically provide negative trait impls for the implicit case and the trivial case. This may naturally arise from simply adding support for auto-traits that have supertraits, but we are explicitly calling it out here regardless.

Logic Should Live in the Explicit Case

Just like how Clone contains the only actual code that controls how copying works, regardless of whether Marker or Copy are implemented, the explicit trait for move must contain the move logic, because the other traits have it as a supertrait. In our previous treatment, the explicit case was Transfer, but as discussed before, the migration pathway for Move means that the explicit case will likely have to be called Move, which must then contain the actual move logic, and two other marker traits for implicit and trivial will need to be created.

Note that one possible implementation of Marker has a separate handle() function, which actually just calls clone(), but allows for making the user's intention more clear:

trait Handle: Clone {
    final fn handle(&self) -> Self {
        Clone::clone(self)
    }
}

This reinforces the idea that the actual non-trivial copy, move, or drop logic should ideally live in the explicit trait. A Move trait proposal should ideally mimic this structure if it provides a seperate implicit non-trivial move trait. However, because Drop already exists, Delete can't mimic this behavior, at least not without some layers of migration.

Drop prevents fully substructural Weakening traits

Rust's Drop trait is either incorrectly implemented, or poorly named. It does not represent the ability for a type to be implicitly dropped - it represents having custom drop logic. This is not the same thing, since plenty of types in current Rust code don't implement Drop, yet can be implicitly dropped. As a result, currently it is not possible for Drop to be a supertrait of Forget, which is what we would expect.

There are a few migration pathways available here. One is to lean into the fact that Drop is already a "magical" trait, with the compiler implementing drop-specific rules. When something implements Drop, the compiler generates a Delete trait with a delete() function implementation that directly calls the drop() function. Drop is then simultaneously turned into an auto-trait with an empty default drop() implementation, and Forget can then imply Drop as a supertrait without breaking everything. This achieves backwards compatibility at the cost of the Drop trait now having an optional drop() function (although Delete would always have an optional delete() function since it must be an auto-trait).

auto trait Delete {
  fn delete(&mut self) {}
}

auto trait Drop: Delete {
  fn drop(&mut self) {}
}

auto trait Forget: Drop {}

Note that this situation inevitably allows for drop() to do something different from delete(). However, since this is already true for traits that implement Copy (nothing forces you to implement the "correct" clone() behavior), this apparently isn't a big deal.

A second option is to stop trying to pretend that Drop actually means a type is implicitly droppable and instead enshrine it as simply "providing custom cleanup behavior". Then, a separate marker trait ImplicitDrop is introduced, and we can then implement the proper trait hierarchy with just the marker traits. In this case, Drop would only imply Delete, which is conceptually a bit unintuitive, but in practice isn't a problem, because Forget is an autotrait, and so all three markers will always be implemented on all types anyway unless opted out of. Then, whenever anything is dropped for any reason, the compiler checks for a Drop implementation, but uses the marker traits to determine what kinds of drops are acceptable. This would require a special function to explicitly drop values, since Delete would just be a marker trait.

auto trait Delete {}
auto trait ImplicitDrop: Delete {}
auto trait Forget: ImplicitDrop {}

trait Drop : Delete {
  fn drop(&mut self);
}

This approach has the advantage of no longer needing the concept of an auto-trait that isn't a marker trait, which would reduce implementation complexity.

Drawbacks

Attempting to implement this entire RFC all at once would be a considerable undertaking, and is not advised. Instead, this RFC is intended as a guide for more tightly scoped RFCs that each introduce just one or two new traits at a time. It is intended as a roadmap for future changes, and the drawbacks of this RFC can be considered the drawbacks of the child RFCs for each individual trait proposal.

There is a chance that this RFC could be used to bikeshed other proposals and delay their introduction. This is not the purpose of the RFC - what is important is that people are aware of the overarching structure that these traits fit into, which might make it easier to select appropriate names. So far, neither the Forget nor the Handle proposals would need any significant modifications to fit into this RFC. This RFC does put significant constraints on a future Move trait.

Because Delete must be an auto-trait, in the implementation pathway where it isn't a marker trait, it must provide a default implementation for delete() that invokes the default drop behavior. This means that implementers of Delete could "forget" to actually implement the delete() function, which is not possible with the current Drop trait, where drop() is a required function. This drawback is not present in the case of custom drop behavior being kept inside a Drop trait that is kept separate from the marker traits.

All these new autotraits may put some strain on the type checker, but this is already going to happen even with just Forget. The problem is that the compiler is making a lot of assumptions that are not properly formalized, and formalizing them means making them autotraits, because they express properties that the compiler previously assumed applied to all types.

Rationale and alternatives

The rationale here is that Rust is already doing this, just accidentally. The engineering forces are pressuring the Rust ecosystem into slowly and unknowingly building up the table of substructural traits. This RFC simply offers a unifying framework that explains why all these traits are necessary, and to inform current RFC proposals about deep connections between their proposals so they can better coordinate their efforts. Failing to do this will simply mean that the substructural traits will happen anyway - just in a more haphazard and uncoordinated manner.

The greatest risk is currently with the Move trait, especially if a non-trivial implicit move trait is introduced without a corresponding explicit trait. Doing this would effectively make it impossible to ever have an explicit move in the language. A move trait proposal must either implement only a marker trait, or it must jump straight to explicit, implicit, and trivial traits if Rust wants to support non-trivial move logic, otherwise it could trap itself in a type corner.

Potentially avoiding non-marker auto traits

There is an alternative to the move trait hierarchy. As we discussed before, one way of handling Drop is by removing it from the trait hierarchy completely, instead using Delete, ImplicitDrop and Forget marker traits to control how the drop happens, and simply using Drop to provide custom cleanup behavior. The same approach could be taken for Move, by creating a fourth new trait, ComplexMove, which represents custom move behavior, which is independent from the marker traits that control when a move is permissible.

-- For consistency, Move here still represents the trivial move case, but for practical reasons, it will likely need to represent the explicit case instead.
auto trait Transfer {}
auto trait Relocate: Transfer {}
auto trait Move: Relocate {}

trait ComplexMove : Transfer {
  fn move(self: &own Self, rhs: &construct Self);
}

This is arguably less than ideal, but it would avoid the problem of needing auto-traits that are not marker traits. There is no way to avoid handling supertraits on auto-traits, however.

Prior art

Many other languages that implement linear or affine types have some form of substructural type system, or pieces of one. Examples include Idris, Haskell, and Mercury. There is currently no non-garbage-collected systems programming language that intentionally implements a substructural type system. C++ has a different subset, where it implements implicit copies but explicit moves (except in certain cases where implicit moves are allowed):

Explicit Implicit Trivial
Contraction N/A copyable is_trivially_copyable
Weakening N/A is_destructible is_trivially_destructible
Exchange movable N/A is_trivially_move_assignable

Importantly, C++ actually lets you delete the destructor, and will simply refuse to compile any code that would have invoked the destructor. This is a lot easier to do in C++ because new freely allows you to leak memory, and provides prior art for a removable Delete trait.

Unresolved questions

  • How to handle auto-traits that have other auto-traits as supertraits? Can we efficiently make impl !Foo imply impl !Bar if trait Bar : Foo without blowing up the compiler?
  • How to handle auto-traits that aren't marker traits? Are any modifications necessary to ensure the default implementation of a non-trivial move trait maps to the compiler's trivial move operation?
  • If making auto-traits that aren't marker traits is infeasible, what names should be chosen for ComplexMove and ImplicitDrop to minimize confusion? How can we make sure the ImplicitDrop trait doesn't get confused with Drop?

Future possibilities

This RFC offers a pathway to a (nearly) proper substructural type system in Rust, so there are no relevant future possibilities that weren't already discussed.

1 Like
2

Rc, Box, etc need to implement Drop for any Forget type, otherwise they have no method of deallocating when going out of scope.

3

Move would be an auto-trait, and must be assumed by default (like Sized), but I don't think the supertraits would need to be. In bounds, opting out with T: ?Move would also lose the implied supertraits. Similarly, impl !Move would also remove the automatic impls for the supertraits, so a transferable type without implicit moves might be implemented as

impl !Move for Foo {}
impl Transfer for Foo {
    fn transfer(...) { ... }
}

I think it's generally better this way: Most types are Move so it's a reasonable thing to assume implicitly, but opting out also opts out of the implications of that assumption.

4

You mentioned the Pin warpper, but is Move a more general + conceptual version of Unpin? Unpin in core::marker - Rust

Apologies for the simple question -- I'm not all that familiar with the concept of a substructural type system.