Saturday, December 11, 2021

Less Painful Linear Types

I’ve advocated for Linear Types in Rust for some time, most recently, arguing that it can resolve an important foot-gun for accidental future cancellation. Beyond that, I think these can be a useful tool for many other purposes, a few of which I mention in the RFC linked above. Rust caters to those who aim to write industrial-strength low-level software… Sometimes, in this area, resource finalization requires more care than simply letting a variable fall out of scope. Linear types address these cases.

That said, linear types can also cause some pain:

  1. Linear types are naturally viral: once a field in a structure (or variant in an enum) is linear, the containing structure will, itself, become linear.
  2. Linear types want API changes to generic containers. These will be annoying (at best) for the ecosystem to incorporate.
  3. Linear types don’t interact well with panic-based unwinding.
  4. Linear types don’t interact well with ? syntax.

Whether linear types are worth it for Rust depends on whether the benefits outweigh the costs. The perception in Rust seems to have been that the costs of linear types are too high. Here, I’d like to suggest that they can be lower than we thought.

Design Approach

This linear types proposal aims to address the pain points above head-on:

  1. We provide an escape hatch, that allows structures that contain linear types to become affine again.
  2. We define lints and automated code refactoring tools to make updating generic container types to support linear types less painful.
  3. We only apply linear-types constraints to linear control flow. Drop can still be invoked during panic-based unwinding.
  4. We define library facilities, to make ? interaction easier.

Proposal

ScopeDrop OIBIT

We define a new unsafe marker trait, called ScopeDrop. This is as it sounds: when a type implements ScopeDrop, then variables of the type are allowed to be cleaned up when they fall out of scope. (We do not affect panic-based clean-up with this trait: even if your type does not implement ScopeDrop, drop-glue can still be created to support panic-based unwinding.) Much like Send and Sync, this trait is auto-derived: if all fields of a structure or variants of an enum implement ScopeDrop, then the structure itself implements ScopeDrop.

We define a single marker type, PhantomLinear, which does not implement ScopeDrop. A user makes her type linear by including a PhantomLinear field, and this now virally infects all containers that might include her type.

So this code:

#[derive(Default)]
struct MyLinear {
    _linear_marker: std::marker::PhantomLinear,
    data: (),
}
fn oops() {
    let _oops: MyLinear = Default::default();
    // ^^^ generates a compilation failure, `_oops` is not allowed
    // to simply fall out of scope.
}

One is allowed to unsafe impl ScopeDrop on a type that would otherwise be linear. With the following code, the example above would compile successfully (though why you would want to write code like this is unclear to me):

unsafe impl ScopeDrop for MyLinear {}

It can make sense to impl Drop for a !ScopeDrop type. Generally, though, the only way that code would be invoked would be by unwinding the stack.

Affine Escape Hatch

Linear types are naturally viral, and limit available API surface area (that is, APIs that assume types are affine cannot work with variables of linear type, see here for details), so there’s a risk that a crate author will label a type as linear, in a way that makes it difficult for external users to consume the type. In this proposal, we define an escape hatch, that allows variables that do not implement ScopeDrop to be safely wrapped by variables that do. We can do this with a trait and a generic type:

// wrap a !ScopeDrop type into a ScopeDrop container.
struct ReScopeDrop<T: Consume>(ManuallyDrop<T>);
unsafe impl<T: Consume> ScopeDrop for ReScopeDrop<T> {}

impl<T: Consume> ReScopeDrop {
    pub fn new(value: T) -> Self {
        ReScopeDrop(value)
    }
    // private function, to support `Drop` implementation.
    unsafe fn take(&mut self) -> T {
        ManuallyDrop::<T>::take(&mut self.0)
    }
    pub fn into_inner(self) -> T {
        self.0
    }
}
// not shown: AsRef, AsMut, etc. for `ReScopeDrop`.

trait Consume {
    fn consume(self);
}
impl<T: Consume> Drop for ReScopeDrop<T>
{
    fn drop(&mut self) {
        unsafe { self.take() }.consume()
    }
}

With these additions, one can wrap an externally-defined !ScopeDrop type in such a way that ScopeDrop works again:

// externally defined type is linear.
struct ExternalLinear {
    _linear: PhantomLinear,
}
impl ExternalLinear {
    pub fn clean_up(self) {
        let ExternalLinear { _linear } = self;
        forget(_linear);
    }
}

// internally-defined type is affine.
struct AffineWrapperImpl(ExternalLinear);
type AffineWrapper = ReScopeDrop<AffineWrapperImpl>;

impl Consume for AffineWrapperImpl {
    fn consume(self) {
        self.0.clean_up();
    }
}

It’s a bit wordy to declare the wrapper type, which is unfortunate, but once this is done, it’s basically as easy to work with AffineWrapperImpl variables as it would be for any other affine variable. We have a reasonable mitigation for the viral aspect of linear types.

Early Return Helpers

Rust’s ? facility relies on early return, which facility – by intention – doesn’t interact well with linear types: any variable of linear type introduced before a ? will require some mechanism to allow early return, while not violating the type’s contract. I think we can handle these cases reasonably ergonomically by defining early return helpers:

struct CleanupImpl<F, T>
where:
    F: FnMut(T) -> ()
{
    var: T,
    cleanup: F,
}
// where clauses not repeated
impl<F, T> CleanupImpl<F, T> {
    fn new(var: T, cleanup: F) -> Self {
        CleanupImpl { var, cleanup }
    }
}
impl<F, T> Consume for CleanupImpl<F, T>
{
    fn consume(self) {
        let { var, cleanup } = self;
        cleanup(var);
    }
}
type Cleanup<F, T> = ReScopeDrop<CleanupImpl<F, T>>;

and maybe a macro to make constructing such a variable easy:

    let myvar = MyLinearType::new();
    let myvar = cleanup!(linear, move |linear| {
        // invoke linear-type specific clean-up function.
        myvar.cleanup();
    });

Updating the ecosystem

Linear types would be a large change to the language, with large implications for the standard library, and for large parts of the ecosystem. Making this as easy as possible, and as foolproof as possible is hugely important… I’d like to hear your thoughts about everything in this proposal, but especially this part.

To assist in ecosystem updates, we can define compiler or clippy lints to detect when code already satisfies linear type constraints, but is not written to understand linear types. Applying this lint to, say, the Option type would result in warnings on functions like map:

impl<T> Option<T> {
    fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> {
        match self {
            Some(x) => Some(f(x)),
            None => None,
        }
    }
}

The lint detects that self is consumed, but the !ScopeDrop field won’t have drop glue generated in this function, so the function is linear-safe. The warning can be addressed by relaxing the T type to be ?ScopeDrop:

impl<T: ?ScopeDrop> Option<T> {
    fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> ...
}

Or, perhaps we can add other syntax to make this less disruptive to the code structure:

impl<T> Option<T> {
    impl<T: ?ScopeDrop> fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> {
        match self {
            Some(x) => Some(f(x)),
            None => None,
        }
    }
}

For this to be broadly consumed by the Rust community, we can make a tool (call it cargo-linearize) to automatically perform this refactoring.

Discussion

This proposal tries to make linear types support palatable to Rust in at least the following ways:

  1. We emphasize an affine escape hatch.
  2. We “punt” on the panic-unwind question.
  3. We define a mechanism to simplify updating generic types to be linear-aware.

These changes should have the effect of making linear types easier to integrate into existing Rust code-bases. They do not eliminate the pain of linear types in Rust. On the other hand, to me, trying to eliminate the pain of linear types is like trying to eliminate the pain of the borrow-checker: if code correctness depends on the fact that resources can’t just be unintelligently dropped, then sometimes you’d rather have pain (compilation errors that can be annoying to placate) when you try to drop such a resource, than incorrect behavior.

When would such a facility be useful? Well, we’re talking about something like linear types quite a bit for async Rust, but I proposed something like this feature prior to Rust 1.0, well before async Rust was a thing. When I was an embedded systems developer, I used something akin to a “drop bomb” (i.e., a Drop implementation that causes a panic) to make sure that our resource ownership semantics were honored – these enforce linear type constraints at runtime, I would have preferred they be enforced at compile time. Browsing the set of issues that have linked to that postponed issue, others have regularly come reached a similar place. This is evidence that Rust’s core audience is interested in this feature. If we can keep the pain of linear types small enough, and this generally addresses important use cases, then perhaps it’s time to look seriously at linear types again?

No comments:

Post a Comment