[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!/Unpin 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 Destruct 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 the Destruct trait.
  • 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 (as Destruct), 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!/Unpin 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 implements Weakening with Destruct, although the current PR assumes it would only ever be useful in const contexts. 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, Destruct if the thing it contains is Destruct, 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, Destruct if the thing it contains is Destruct, and Move unconditionally.

pin! and Unpin are 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, Destruct allows performing arbitrary amounts of compute or IO at a region of the program that doesn’t even name the thing causing it, via a Drop implementation. By separating Delete from the implicit Destruct case, 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 !Destruct for MutexGuard {}

// Provide custom drop logic
impl<'a, T> Drop for MutexGuard<'a, T> {
    fn drop(&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);

// Nonsensical usage of !Forget to provide an example of non-forgettable regions
impl !Forget for Wrap {}

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

// Disallow destroying Reserved (also implies !UnwindSafe, !Destruct, and !Forget)
impl !Delete 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, if the move traits are implemented in a similar manner to Copy/Clone, this would introduce a unique auto-trait situation, covered below. This situation does not arise if custom move logic is implemented in the same way Drop is.

Just like how Copy currently implies Clone, the insertion of an implicit Handle trait would imply Copy: Handle and Handle: Clone. The other traits will follow a similar pattern:

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

Note that UnwindSafe must also imply Delete. There may be other internal compiler traits with additional implications that are currently ignored becuase all traits must implement them anyway.

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. There is a workaround discussed below that avoids this construction, but complicates the usage.

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 auto-trait.

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.

Delete and Destruct Migration Path

Rust currently represents, via an internal compiler trait (that might be exposed in the future), the concept of being destructable via the Destruct trait. Because Rust currently has no concept of an explicit drop, this trait represents the ability for a type to be implicitly dropped. If Destruct is first stabilized only for const contexts, its semantics will need to be expanded so that it can be meaningfully negated outside of const contexts before introducing Delete.

The most obvious way to implement an explicit drop is via a Clone style trait with a delete function, but the existence of Drop means it's not possible to put the custom drop logic in the explicit case without at least some compiler magic (which also creates a non-marker auto-trait):

auto trait Delete {
  fn delete(&mut self) {
    std::magic::drop(self); // Must call the custom drop code, if it exists for this type.
  }
}

Given that implementing explicit dropping would require some compiler magic anyway, because it breaks the assumption that all drops happen as a result of compiler lifetime analysis, we can simply provide a magic function std::mem::delete() that explicitly deletes something. Then, Delete can simply be a marker trait, and the compiler can invoke the drop() logic whenever it deems appropriate.

auto trait Delete {}
auto trait Destruct: Delete {}
auto trait Forget: Destruct {}

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

This is much easier to implement from the perspective of the compiler, but adding the Delete trait as the explicit case isn't the only option. Another option would be to change Destruct to instead represent explicit drop instead of Delete, and a new trait Destroy can represent the implicit case. This allows more code in the compiler to remain the same - any checks that are trying to see if something can be dropped at all can remain the same, and only places that need to be aware of the difference between an implicit and explicit drop would need to be changed to look for the new Destroy trait.

auto trait Destruct {}
auto trait Destroy: Destruct {}
auto trait Forget: Destroy {}

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

This shouldn't conflict with the way Destruct is currently being used in const contexts, since it only represents the ability to drop something, not whether it can be implicitly dropped or not. However, if parts of the compiler are not actually using Destruct with these kinds of semantics, it wouldn't actually save much work.

Summary

This RFC is not intended to provide a fully fleshed out implementation of either Move or Delete. Instead, it provides guidance for future RFCs that might implement those traits. This RFC only points out that the following novel concepts will be necessary in the future to support a proper substructural treatment of Move and Delete.

  • Allowing auto-traits to have supertraits.
  • Expanding Destroy to apply to non-const contexts.
  • Modifying the internal drop logic to look for the explicit Delete trait, and introducing some method of explicitly dropping an item before it is implicitly dropped.
  • Adding trait bounds to existing auto-traits to correctly express the substructural hierarchy.
  • Any proposed Move trait RFC must either restrict itself to the trivial case, or implement the full substructural hierarchy if it wants to allow non-trivial moves.
  • If no way of adding blanket impls for Transfer and Relocate are found, a future Move RFC tackling non-trivial moves may require support for auto-traits that are not marker traits.

These concepts do not need to be immediately implemented. They should be implemented only when needed to support a future RFC, or after the type solver can handle the extra auto-traits without significant performance losses.

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.

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, by using a Drop trait analogue, 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 name should be chosen for ComplexMove to minimize confusion?

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.

21 Likes
2

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

2 Likes
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.

5

If the supertraits of Move are not also auto-traits, then every single type would, by default, require an explicit implementation of the supertraits, because that's how supertrait bounds work in Rust. They do not provide an implementation of the trait, they simply require that an implementation exist. So, if we have:

trait Transfer {}
trait Relocate: Transfer {}
auto trait Move: Relocate {}

Then every single type that doesn't opt-out of Move would have to provide implementations of Relocate and Transfer. The only way to automatically provide implementations of Relocate and Transfer is by making them auto-traits.

6

The "Exchange" being mentioned here is different from the actual concept of "Exchange" in a substructural type system. Substructural type systems basically limit what you can do with your "free variables" (a mathematical term which in Rust corresponds to variables/function arguments that are live). The definition of contraction is correct (allowing you to use a value multiple times); and the definition of weakening is mostly correct (mathematically, it allows you to let a value to go out of scope without doing anything with it, but this corresponds to a forget in Rust rather than a drop).

However, the definition of Exchange doesn't match the mathematical term at all – "Exchange" mathematically is the rule that allows you to use variables in a different order from the order they were declared. For example, without an Exchange rule, you can't do this:

let x = 4;
let y = 5;
println!("{}", y - x);

because x was declared before y and thus has to be used earlier. (Unlike Weakening and Contraction, I have never seen a practical programming language that omits the Exchange rule – it is very hard to imagine an advantage from doing so. I think the rule mostly only exists in the first place because people like to design their type theories using lists of free variables rather than sets. Some stack-based esoteric languages force variables to be used in the reverse of the order in which they were introduced, but it tends to be a very hard restriction to work under in practice.)

I think the concept of having unmovable values is an important one that's worth studying, but I also don't think it makes sense to try to connect it to an unrelated (and mostly not very relevant) concept in substructural type theory. I also think the pattern you're showing here is possibly hiding relevant details. For example, the concept of "can be moved" is different from the concept of "can be overwritten" and yet they're both potentially relevant – to make some things work you need to ban moves altogether, but others just need to ban overwrites. (Note that a type that can't be moved also can't be overwritten because you have nothing to overwrite it with.) So for moves, you have a four-stage hierarchy rather than three.

Also bear in mind rules like "anything that can be trivially copied can be trivially dropped" (this is true in current Rust and linear logic type theory suggests that it's an important rule for the logic to internally make sense), which in turn implies "anything that can be trivially copied can be trivially moved" (copy it, then drop the original). There's definitely value in looking at the patterns and the traits that would be needed to represent them, but I disagree with trying to fit them into a neat matrix rather than working out what the actual rules are.

(Also, I think Transfer doesn't work without adding extra features to Rust first – in current Rust there is no way to write the method signature, because none of the existing parameter passing modes work.)

3 Likes
7

They're definitely related; nikomatsakis has written a blog post covering the connection, which you might be interested in (although the suggested Unpin replacement bans overwrites – i.e. writing through an &mut reference to overwrite the value stored at its target – rather than moves generally, which can also be done using let a = b or the like).

It's also worth noting that (much to my annoyance) Pin::set exists, meaning that Pin doesn't currently (and can't without breaking a stable guarantee) protect the pinned place from being overwritten (as long as the pinned value was dropped first). I think that this was a mistake, because it somewhat limits the places in which Pin was useful – but it also complicates the relationship between Unpin and overwriting somewhat.

8

Does the blanket impl trick not work for auto traits? The following works in the playground:

trait Transfer {}
trait Relocate: Transfer {}
trait Move: Relocate {}
impl<T: Move> Relocate for T {}
impl<T: Relocate> Transfer for T {}
9

I think the trick in question doesn't work when people start implementing the traits conditionally. It's reasonable to do impl<T: Relocate> Relocate for MyWrapper<T> {} and impl<T: Move> Move for MyWrapper<T> {}, but that's incoherent with your blanket implementation because you get two implementations of Relocate for MyWrapper<T> when T: Move. So the blanket implementations force wrapper types to decide which level of the hierarchy they're going to inherit from the wrapped type, and they can't inherit any of the others.

This sort of thing is also why, much though I'd like it (having to worry about malicious Clone impls for Copy types is frustrating), Rust can't have

impl<T: Copy> Clone for T {
    fn clone(&self) -> Self { *self }
}

because it's incoherent with #[derive(Clone, Copy)].

2 Likes
10

Exchange here is exactly the concept of exchange from a substructural type system. Exchange doesn't exactly mean "you can use variables in any order" it means "changing the order of variables in the context has no meaning". In rust, "the order of variables in the context" corresponds to the memory layout within a function stack frame, and by extension the memory layout of a tuple or struct. In rust right now, it's illegal to move out from under a reference. This means that there are cases right now where rust isn't allowed to use variables in a different order from the order they were declared.

Given the following declarations:

struct A (i32);
struct B<'a> (&'a A, i32);

fn use_a(a: A) {
    println!("{}", a.0);
}

fn use_b(b: B) {
    println!("{}, {}", (*b.0).0, b.1);
}

This code compiles

fn main() {
    let a = A(1);
    let b = B(&a, 2);
    use_b(b);
    use_a(a);
}

but this code does not.

fn main() {
    let a = A(1);
    let b = B(&a, 2);
    use_a(a);
    use_b(b);
}

despite the only difference between these programs being the order that variables are used in, which is exchange.

Rust tracks the initialization and state of borrowing on variables in the context, and calls some of this information lifetimes. This tracking is very close to the formal concept of coeffects in type theory. Rust doesn't allow writing type annotations with most of the coeffect information it internally uses, which is inconvenient in a variety of ways, but it is what it is.

The logic of rust requires that particular variables be consumed before others, which means you cannot reorder either usages of them in the source, or the memory layout of the stack frame.

Here's a sketch of a guard which is trivially copyable but not trivially dropable, off the top of my head. Rust doesn't currently accept this because Rust requires trivial drop for trivial copy as you said, but it could potentially accept this in the future because that constraint isn't inherent to the calculus.

struct InternalHolder(SomeHeavyweightOperation);

#[derive(Clone, Copy)]
struct Handle<'a>(&'a Mutex<Option<InternalHolder>>);
impl<'a> Drop for Handle<'a> {
    fn drop(&mut self) {
        let mut operation = self.0.lock().expect("something panicked?");
        if let Some(op) = operation.take() {
            op.0.do_heavy_thing();
        }
    }
}

It represents a pending expensive operation which something must do but that can be delegated freely up until it reaches things that depend on it finishing (the end of lifetime a). It's sort of the opposite of an Arc, where it will dispose of the content as soon as anyone is done with it rather than when everyone is done with it. This is admittedly a rather situational thing, and perhaps would be better served by implementing tasks with work stealing correctly, but I don't feel comfortable ruling out that there isn't anything more useful or harder to work around than this example. It might be essential in implementing cilk style hyperobjects, which have very similar usage patterns, for instance (the object handle can be trivially copied into new tasks, when when the handle is dropped from a particular task it performs some bookkeeping inside the object the handle refers to).

"Can be overwritten" is just Forget, because only things that don't require any deconstruction behavior can be safely transmuted to uninitialized, and only uninitialized locations can be moved into safely. If your "move" operation requires reading from memory in the destination before writing to it, that's not a move operation.

You are correct about Transfer requiring additional features to do safely, which is why the examples in the original post demonstrate two possible sets of features that would permit it: the &own and &construct reference qualifiers that have already seen discussion about adding to rust, or a less elegant magic calling convention that makes the argument and return be in-place operations.

5 Likes
11

Are you referring to what's discussed in this article: Safe Manual Memory Management with Coeffects - Ryan Brewer or something else?

Anyway thanks for mentioning that, coeffects seem interesting.

1 Like
12

I continue to disagree. Rust's "this is borrowed, and so you can't move it" rule is represented in a type judgement by a modality on the type, not by reordering the order of variables in the context.

Using the order of variables in the context as a method of determining places immediately breaks down with code like this:

let a = unmoveable_vec![1,2];
let b = vec![3,4];
let c = unmoveable_vec![5,6];
let d = &a;
let e = &c;
drop(b);

Before the drop, the first and third variables were borrowed. Now, the first and second variables were borrowed. So is the drop illegal because it moves a or c? All removing Exchange does is that it gives you is a "this is the nth variable" concept. This concept is entirely irrelevant to Rust and it doesn't make any sense to try to enforce it.

There are logics (and their corresponding type theories) that do handle Rust-like lifetimes and borrows, but those logics still have the Exchange rule because removing it wouldn't be helpful for their goal. For example, this paper implements a region-based logic that is very reminiscent of Rust borrowing (although at the level of arenas rather than single variables) – it even has an explicit stack of regions, which imposes an order to the borrows. But it doesn't have an order to the variables – the type judgements are based on an unordered map, which implicitly admits the Exchange rule.

I'm referring to dropping/swapping overwrites, which drop the object being overwritten before the new object is moved in, or which swap it out in order to avoid dropping it. (For example, *a = b; or mem::replace(a, b), where a is an &mut T.)

2 Likes
13

Yes, it is the same kind of thing. Here's a nice introduction to coeffects Coeffects: Context-aware programming languages

1 Like
14

I realize there are things to work out to make it possible. Currently auto traits simply cannot have supertraits (according to auto_traits - The Rust Unstable Book). My point was that Transfer and Relocate should not be auto traits. Unlike Move, these are properties that you should opt into, not out of. I wouldn't want the compiler provide a trivial impl of Transfer if I wrote impl !Move but forgot to impl !Transfer.

Negative bounds could help: impl<T: Relocate + !Move> would be disjoint with impl<T: Move>, though I suppose that's going even further out into language features that don't exist yet.

15

Your RFC looks interesting, but at the end of the day I don't exactly see a clear benefit written. Yes, it will make things more explicit and formal, but we would need a lot of hands to make this happen. We already struggle to make something like Forget not ruin compiler performance :sweat_smile:

Some notes on misunderstandings of Forget RFC:

In the context of Forget RFC, having 'static !Forget type doesn't really make a lot of sense, as it doesn't provide any additional guarantees to the unsafe code.

It may be useful for other purposes, sure, but the RFC is not pointed at preventing leaking, it is actually a whole other can of worms that consumed other Leak proposals, it is just talking about scopes.

This is related to the previous one. Uninitiated memory can still be pointed at by another thread and be written to. What matters is a lifetime.

16

This almost works, but as ais523 pointed out, it doesn't work if traits want to conditionally implement two or more of the marker traits at once, because then the implementations conflict.

It's not clear if there is an alternative way to express these blanket implementations that would be implemented closer to how auto-traits work, where the implementation only exist if not already provided. There doesn't seem to be any pathway to this in the current trait solver, so I don't see a way out of auto-traits, unless a novel approach can be suggested.

17

I admit I'm very confused by what you're saying here. Maybe you instead meant that we should use a blanket impl approach for Transfer and Relocate as suggested by @pitaj? That would be an elegant solution, if not for the conditional implementation problem that ais523 pointed out, which makes it non-viable, at least unless the trait solver gets some new tricks.

18

Just to be clear, the !Forget example provided was completely nonsensical, it was only meant to illustrate non-forgettable regions in a potential move() implementation.

I am trying very hard to avoid introducing too much new work. Almost everything in this proposal is already being worked on, and one of the reasons we wrote it is precisely because someone has started working on a Move trait proposal and we wanted to make sure it didn't accidentally recreate the problem that Handle is currently trying to fix. No real changes need to be made to Handle or Forget, since the additional auto-trait bounds can always be added later.

I can modify the RFC to add a section that clearly states the new things that this proposal is suggesting. Depending on whether there's a way to make blanket implementations work, there are now only 5 actual novel suggestions in this proposal:

  • auto-traits with supertraits
  • Expanding Destroy to apply to non-const contexts
  • Adding Delete and the relevant logic necessary to check if a type is allowed to be implicitly dropped, plus a magic delete function.
  • Adding some trait bounds to existing auto-traits to correctly express the substructural bounds.
  • Potentially supporting non-marker auto-traits.

Everything else is already being proposed. The biggest obstacle, as you mentioned, is that the compiler struggles with trait evaluation, and this could be especially problematic with a non-marker auto-trait, if those end up being unavoidable. I think it's fine if this RFC isn't actually implemented for quite some time - it is meant as a guide, to ensure that future proposals don't accidentally cause avoidable problems by ignoring parts of the substructural type system. As long as future proposals (such as const_destruct and non-trivial Move) leave room for the rest of the substructural traits, that would suffice. This isn't something that needs to be implemented right now, it's just something for proposals to keep in mind.

6 Likes
19

Cross-linking to the related Zulip thread: #t-lang > Pre-RFC: Substructural Type System

20

I spent some time reading the cited paper. The paper you cited does have exchange, because it doesn't have (exclusive) borrows; no mechanism in that paper produces a requirement that a variable not be used until a lifetime ends as far as I can tell. Rust borrows produce this requirement, the regions in that paper do not. Rust doesn't have full exchange in consequence, whereas that paper's lambda-CBV calculus does.

If there is any mechanism in the language which restricts the order in which variables can be used, then the language doesn't take the full exchange rule. By definition, the exchange rule permits any change in ordering of consumption of variables, which forbids any judgement restricting ordering. If you have an "exchange rule" that only permits some ordering changes, that isn't a full exchange rule and is instead a restricted exchange.

Rust's restriction of exchange doesn't involve a total ordering of stack usage the way the example ordered type system the way the example from this textbook does. Rust instead uses a partial order, meaning that ordering is transitive and reflexive and antisymmetric but not total. It could also be a preorder if the antisymmetry constraint isn't required. Technically, it's also a semilattice, given the additional bound ('static) and the binary operator, but those guarantees aren't required for this discussion.

The proposed move trait doesn't give a fully general mechanism for interacting with exchange, doing that effectively would require even more changes to rust's type system and I don't feel like trying to fit things like "higher kinded types", "changing type indices on a reference to a region", or "custom coeffect annotations" into rust's syntax and semantics. This proposal provides a complementary mechanism to the existing lifetime based restrictions.

An alternative sort of exchange operation might be something like (in agda-like syntax)

record Exchange (L : Lifetime -> Type) (R : Lifetime -> Type): Type where
  exchange: forall {a b : Lifetime} (l : L a) (r : R b) -> (L b ⨯ R a)

or in a made up rust-like syntax

trait Exchange<for<'c> R<'c>: 'c> for<'c> Self<'c>: 'c {
  fn exchange<'a, 'b>(l: Self<'a>, r: R<'b>) -> (Self<'b>, R<'a>);
}

This operation swaps the remaining lifetimes of L and R (ignoring whatever kind of references would be required to make this actually generally work in rust semantics), it expresses "there is some way to modify L and R to change which one must outlive the other". (in trivial cases, the modification is "do nothing, they're already independent")

However this alternative exchange operation, while it does allow changing the lifetimes of values to swap them, it can't handle changing the lifetimes of the regions those values live in, so it wouldn't be able to apply to values that are already stored in a specific region.

So, let's explore Rust's restricted exchange:

  • Rust permits reordering usages of anything which isn't borrowed.
  • Rust permits reordering usages that don't have a lifetime constraint between them.
  • Rust currently permits reordering a usage of a value past the usage of its region if and only if the region isn't the magic type Pin and the value doesn't provide unpin.

For the sake of examples:

struct Alpha(i32);
struct Beta{idx: i32, a: A };
fn foo() {
  let b = Beta{idx: 1, a: Alpha(1)}; // the remaining lifetime of the object "alpha 1" is constrained by the lifetime of "beta 1"
  let a2 = Alpha(2);
  let a1 = b.a; // the uninitialized region `a1` and the initialized region `b.a` swap the lifetimes of their contents, resulting in object "alpha 1" having the lifetime of region `a1` and region `b.a` being uninitialized.
  b.a = a2; // exchange `a2` into `b.a`, giving the object "alpha 2" the lifetime of the region `b.a`, restoring the region to initialized state. 
  drop(b); // ending the lifetime of region `b` also ends the lifetime of object "alpha 2" which is constrained to be within it.
 // object "alpha 1" is still alive despite being originally constrained by the lifetime of object "beta 1"
  drop(a1prime); // we can now consume the object "alpha 1" despite outliving its original bound, because rust's restricted exchange permits this.
}

Moving objects between locations can change their position in the lifetime ordering, and thus is a component of Exchange. Within Rust, we can factor exchange out of "exchange the lifetimes of A and B" and into "move A into an uninitialized position and adopt its lifetime, leaving its prior position uninitialized" which can reconstruct the more classic exchange by doing the classic "swap with three moves and a temporary" construction. The move operation is unary rather than binary and avoids some usage of higher kinded types so it's easier to type and represent in Rust's type system.