---
title: "Contexts and capabilities in Rust"
date: 2021-12-21
---

# 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.[^deser-seed]

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](https://docs.rs/rayon/latest/rayon/fn.scope.html)
* 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"

[^deser-seed]: `serde` maintains the more advanced [`DeserializeSeed`] API, in addition to the more commonly used `Deserialize`, for this reason.

[`DeserializeSeed`]: https://docs.serde.rs/serde/de/trait.DeserializeSeed.html

## 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[^depinj]
* Implicit arguments[^implicits]
* Effects[^effects]

[^depinj]: [Dagger](https://dagger.dev/dev-guide/) is an example of a dependency injection framework in Java.
[^implicits]: Implicit arguments are supported in [Coq](https://coq.inria.fr/refman/language/extensions/implicit-arguments.html), [Agda](https://agda.readthedocs.io/en/v2.6.2.1/language/implicit-arguments.html), and [Scala](https://docs.scala-lang.org/tour/implicit-parameters.html).
[^effects]: See [Effect system](https://en.wikipedia.org/wiki/Effect_system) on Wikipedia. One example is the [Koka programming language](https://koka-lang.github.io/koka/doc/book.html).

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.[^from-bytes]

[^from-bytes]: I'm hiding the actual details of deserialization behind the `from_bytes` associated function, since they aren't relevant to this example.

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.

<!-- TODO: Make sure the lifetime variance strategy actually works here,
including in the generic case. -->

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:

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 `impl`s 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],
) -> R
    let object = T::deserialize(deserializer)?;
    println!("Successfully deserialized an 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.[^monomorphization]

[^monomorphization]: A note on performance: When using static dispatch, we can still compile everything down to regular function arguments. At monomorphization time the compiler knows all the types and therefore can determine what context arguments a function *transitively* needs.

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:

<!--
for dyn, we can make `with(ContextFree)` the default like we do with 'static'
-->

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`.

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) 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.

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