Contexts and capabilities in Rust

I recently worked out a promising idea with Niko Matsakis and Yoshua Wuyts to solve what I’ll call the “context problem” in Rust. The idea takes inspiration from features in other languages like implicit arguments, effects, and object capabilities. While this is very much at the early stages of development, I’m sharing it here to hopefully get more perspectives and ideas from the Rust community.

The problem

Very often in programming we find ourselves needing access to some context object in many places in our code. Some examples of context objects:

• Arena allocator
• String interner
• Logging scope
• Async executor
• Capability object

Today we have two main approaches to using these context objects.

One is to add the context as a parameter to every function that transitively depends on it. This is inconvenient (though it can sometimes be made easier by storing it in a struct and smuggling it through the self parameter). Worse than the inconvenience is that if you need to thread the context through code you don’t control, you’re stuck – unless the author of that code provided a generic way to pass context.¹

The second way of passing contexts is to use a kind of global variable, most often thread-local variables.

thread_local!(static RUNTIME: Option<async_std::Executor> = None);

This makes passing context much easier, including through code you don’t control. For many use cases this is a great solution. But there are many problems with thread locals:

• Stack allocation is not supported
• They require platform support
• Destructors often aren’t run
• They often aren’t appropriate for libraries to use
• They aren’t inherited by logically nested code running on other threads, like tasks in a rayon scope
• They require interior mutability
• They require static initialization, which in practice means storing the context in an Option and unwrapping, or using something like lazy_static!
• They aren’t ergonomic: every use requires introducing a closure; there’s no general-purpose “scoped setter”

Declaring your context

What if Rust code could instead declare the context it needs, and the compiler took care of making sure that context was provided?

This general concept is addressed by a few different approaches in other languages:

• Dependency injection²
• Implicit arguments³
• Effects⁴

The approach proposed here works like implicit arguments, with some syntactic and conceptual similarities to effects in other languages that make it both more convenient and integrate better into Rust’s type system. It can also be used to implement dependency injection. This approach:

• Has zero runtime overhead; it compiles down to the code you would write anyway
• Statically guarantees that any context you need is available
• Allows passing references to objects on the stack
• Integrates with the trait system
• Follows simple rules

So what does it look like?

Context bounds: with clauses

Let’s say you’re writing some deserialization code that needs access to an arena. You could write something like this:

mod arena {
    /// Simple bump arena.
    struct BasicArena { .. }

    capability basic_arena<'a> = &'a BasicArena;
}

// Notice that we can use arena::basic_arena here - and return
// a reference to it - without it appearing in our argument list.
fn deserialize<'a>(bytes: &[u8]) -> Result<&'a Foo, Error>
with
    arena::basic_arena: &'a arena::BasicArena,
{
    arena::basic_arena.alloc(Foo::from_bytes(bytes)?)
}

We define a new kind of item, capability, creating a common name to be used by the code that provides the arena as well as the code that uses the arena. with is another new keyword used to denote the context your code needs to run.⁵

In reality, arena::basic_arena is just another function argument that you don’t have to pass explicitly. Calling code would provide the arena like this:

fn main() -> Result<(), Error> {
    let bytes = read_some_bytes()?;
    with arena::basic_arena = &arena::BasicArena::new() {
        let foo: &Foo = deserialize(bytes)?;
        println!("foo: {:?}", foo);
    }
    Ok(())
}

Here with is being used in an expression context, which means it is being used to provide context rather than require it. Anytime deserialize is called, the compiler will check that a value of type BasicArena has been provided. Forgetting to do so will result in a compiler error.

fn main() -> Result<(), Error> {
    let bytes = read_some_bytes()?;
    let some_arena = arena::BasicArena::new();
    let foo: &mut Foo = deserialize(bytes)?;
//                      ^^^^^^^^^^^
// ERROR: Calling `deserialize` requires the capability
//        `arena::basic_arena`
// help: There is a variable of the required type in scope:
//       `some_arena`
// help: Use `with` to provide the context:
//           with arena::basic_arena = &some_arena {
//               let foo: &mut Foo = deserialize(bytes)?;
//           }
    println!("foo: {:?}", foo);
    Ok(())
}

Context-dependent impls

So far this looks kind of like regular function arguments, but with more steps. So what’s cool about it?

Crucially, a goal of the design is to enable you to write with clauses on trait impls. Let’s say we have a trait called Deserialize declared in a library somewhere.

trait Deserialize {
    fn deserialize(
        deserializer: &mut Deserializer
    ) -> Result<Self, Error>;
}

Even though we don’t control the trait definition and that trait knows nothing about arenas, our code can still declare the context we need in order to fulfill the impl.

use arena::{basic_arena, BasicArena};

struct Foo {
    // ..some complicated type..
}

// We use `basic_arena` below from the impl with clause.
impl<'a> Deserialize for &'a Foo
with
    basic_arena: &'a BasicArena,
{
    fn deserialize(
        deserializer: &mut Deserializer
    ) -> Result<Self, Error> {
        let foo = Foo::from_bytes(deserializer.get_bytes())?;
        basic_arena.alloc(foo)
    }
}

The context can be “passed along” via other with clauses:

use arena::{basic_arena, BasicArena};

struct Bar<'a> {
    version: i32,
    foo: &'a Foo,
}

// Here the `with` clause is used only for invoking the `Deserialize`
// impl for Foo; we never use `basic_arena` directly.
impl<'a> Deserialize for Bar<'a>
with
    basic_arena: &'a BasicArena,
{
    fn deserialize(
        deserializer: &mut Deserializer
    ) -> Result<Self, Error> {
        let version = deserializer.get_key("version")?;
        let foo = deserializer.get_key("foo")?;
        Ok(Bar { version, foo })
    }
}

Proving a with clause on an impl or fn item works exactly like proving a where clause on one of those items. When the item is used (e.g. for function dispatch), the compiler checks that all clauses hold for the dispatch to be valid.

In the simple cases where all types are known, it’s easy to see how this can work for impls just as easily as in our bare fn item above. But what happens when generic code tries to invoke deserialize?

fn deserialize_and_print<T: Deserialize + Debug>(
    deserializer: &mut Deserializer,
    bytes: &[u8],
) -> T
    let object = T::deserialize(deserializer)?;
    println!("Successfully deserialized an object: {:?}", object);
    object
}

When the compiler type checks this code, it doesn’t know about the with requirement on our impl above. All it sees is a requirement that T: Deserialize is met, and that it is therefore safe to call the deserialize function on the trait.

To guarantee that the needed context is provided, a check needs to happen “upstream” of this function. In particular, when the function is called and the requirement that T: Deserialize is checked:

fn main() -> Result<(), Error> {
    let deserializer = Deserializer::init_from_stdin()?;

    let foo: &Foo = deserialize_and_print(&mut deserializer)?;
//                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// ERROR: Calling `deserialize_and_print` requires capability
//        `arena::basic_arena`
// note: Required by `impl Deserialize for &'a mut Foo`
// note: Required because of `T: Deserialize` bound on
//       `deserialize_and_print`

    // But later...
    with arena::basic_arena = &BasicArena::new() {
        // This works!
        let _foo: &Foo = deserialize_and_print(deserializer)?;
    }
    Ok(())
}

What’s interesting about this is at one point in the function our type does not implement Deserialize, but at another moment it does! Rust doesn’t have such a concept of context-dependent implementations today.

The example highlights a major benefit to this approach, however. Even though our generic function deserialize_and_print didn’t know anything about the arena context, we were able to use it and “sneak” the arena in to our impl just fine! In this way context parameters can be much more powerful than function arguments.⁶

Adding this concept has some other interesting implications for generic code. In particular, what would happen if we did this?

fn deserialize_and_print_later<T: Deserialize + Debug>(
    deserializer: &mut Deserializer,
    bytes: &[u8],
) {
    thread::spawn(|| {
        thread::sleep(1);
        let object = T::deserialize(deserializer)?;
        println!("Successfully deserialized an object: {:?}", object);
    });
}

This could lead to serious problems. The compiler would dutifully thread our reference to BasicArena through this function and the closure running on another thread to get to deserialize. But what if a BasicArena is not Sync? And how do we know the arena will even be around by the time this code runs?

Scoped bounds

Solving this problem requires introducing a new concept in the type system, which I alluded to above. Where clauses and bounds like T: Deserialize can no longer be taken for granted as being always true! Instead, we must have a way of expressing bounds which are true at certain times.

Rust already has the concept of lifetimes for expressing values and types that are only sometimes valid. What if in addition to values and their types, we could use lifetimes to scope where clauses?

Let’s map out what that looks like. To start, the kinds of where clauses we write today are always true. That has a clear analogue in the space of lifetimes: 'static. We need that to hold in order to use the clause in our closure. We also need our closure to be Send, which means our context must also be Send. So let’s say in some future version of Rust, we had to write our function like this:

fn deserialize_and_print_later<T>(deserializer: &mut Deserializer)
where with('static + Send) T: Deserialize + Debug
{
    std::thread::spawn(|| {
        // ...
    });
}

Attempting to call this function with our Foo type would then fail, because it does not always implement Deserialize.

use arena::{basic_arena, BasicArena};

fn main() -> Result<(), Error> {
    let deserializer = Deserializer::init_from_stdin()?;
    with basic_arena = &BasicArena::new() {
        deserialize_and_print_later(&mut deserializer);
//      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
// ERROR: `deserialize_and_print_later` requires that
//            &mut Foo: Deserialize
//        always holds, but it does not
// note:      with &BasicArena::new() {
//            -----------------------
// note:  the bound only holds within the scope of this
//        `with` expression
// note:      where in('static + Send) T: Deserialize + Debug
//                     -------
// note:  required because of this clause on
//        `deserialize_and_print_later`
    }
    Ok(())
}

Adding generics

It would be nice if with requirements didn’t require the exact type you wrote, just one close to it. Fortunately, there’s a natural way of writing that:

trait Allocator { ... }

capability alloc: Allocator;

Here we’ve dropped the = and chosen not to specify the exact type, adding a trait bound instead. There’s another way of writing this capability, which the above syntax desugars to:

capability alloc where Self: Allocator;

This desugaring reveals another aspect of capabilities: at their core they are only a name. They just happen to often carry a where clause that describes the type of any value associated with that name.

Users of capabilities are allowed to expand the set of where clauses on that capability, as long as the compiler can prove they are true. In fact, we could choose to declare a capabilty as only a name, and always rely on functions declaring the bounds they need:

capability alloc;

fn deserialize<'a>(bytes: &[u8]) -> Result<&'a Foo, Error>
with
    alloc: impl Allocator,
{ ... }

You could also write the above function signature using a where clause:

fn deserialize<'a, T>(bytes: &[u8]) -> Result<&'a Foo, Error>
with
    arena: T,
where
    T: Allocator,
{ ... }

In this way impl Trait on capabilities behaves exactly like with function arguments.

Conclusion

In this post we saw a new approach to sharing context in Rust. It allows passing context without polluting callsites and even through code you don’t control. It can be used in both application code and library code. It requires an advanced extension to the type system, but one that uses already-familiar concepts like lifetimes, and in return we get to model important patterns like capabilities using the Rust language.

There are more aspects of capabilities to dig into, including usage patterns, how it could be implemented in the compiler, and how it interacts with dyn. I hope to explore those in future posts. But I’d also love to see other, potentially better ideas spring out of this post. Visit the internals thread for feedback.

Thanks to Yoshua Wuyts, Niko Matsakis, and David Koloski for reviewing earlier drafts of this post.