Encapsulating Lifetime of the Field

This is a post about an annoying Rust pattern and an annoying workaround, without a good solution :)

Problem Statement

Suppose you have some struct which holds some references inside. Now, you want to store a reference to this structure inside some larger struct. It could look like this:

struct Foo<'a> {
    buff: &'a String
}

struct Context<'f> {
    foo: &'f Foo
}

The code, as written, does not compile:

error[E0106]: missing lifetime specifier
 --> src/main.rs:8:14
  |
8 |     foo: &'f Foo
  |              ^^^ expected lifetime parameter

To fix it, we need to get Foo an additional lifetime:

struct Foo<'a> {
    buff: &'a String
}

struct Context<'f, 'a: 'f> {
    foo: &'f Foo<'a>
}

And this is the problem which is the subject of this post. Although Foo is supposed to be an implementation detail, its lifetime, 'a, bleeds to Contexts interface, so most of the clients of Context would need to name this lifetime together with 'a: 'f bound. Note that this effect is transitive: in general, rust struct has to name lifetimes of contained types, and their contained types, and their contained types, But lets concentrate on this two-level example!

The question is, can we somehow hide this 'a from users of Context? Its interesting that Ive first distilled this problem about half a year ago in this urlo post, and today, while refactoring some of Cargo internals in #5476 with @dwijnand, Ive stumbled upon something, which could be called a solution, if you squint hard enough.

Extended Example

Lets create a somewhat longer example to check that lifetime setup actually works out in practice.

struct Foo<'a> {
    buff: &'a String
}

impl<'a> Foo<'a> {
    fn len(&self) -> usize {
        self.buff.len()
    }
}

struct Context<'f, 'a: 'f> {
    foo: &'f Foo<'a>
}

// Note how we have to repeat ugly `'a: 'f` bound here!
impl<'f, 'a: 'f> Context<'f, 'a> {
    fn new(foo: &'f Foo<'a>) -> Self {
        Context { foo }
    }

    fn len(&self) -> usize {
        self.foo.len()
    }
}

// Check, that we actually can create a `Context`
// from `Foo` and call a method.
fn test<'f, 'a>(foo: &'f Foo<'a>) {
    let ctx = Context::new(foo);
    ctx.len();
}

playground

First fix

The first natural idea is to try to use the same lifetime, 'f for both & and Foo: it fits syntactically, so why not give it a try?

struct Foo<'a> {
    buff: &'a String
}

impl<'a> Foo<'a> {
    fn len(&self) -> usize {
        self.buff.len()
    }
}

struct Context<'f> {
    foo: &'f Foo<'f>
}

impl<'f> Context<'f> {
    fn new<'a>(foo: &'f Foo<'a>) -> Self {
        Context { foo }
    }

    fn len(&self) -> usize {
        self.foo.len()
    }
}

fn test<'f, 'a>(foo: &'f Foo<'a>) {
    let ctx = Context::new(foo);
    ctx.len();
}

playground

Surprisingly, it works! Ill show a case where this approach breaks down in a moment, but lets first understand why this works. The magic happens in the new method, which could be written more explicitly as

fn new<'a: 'f>(foo: &'f Foo<'a>) -> Self {
    let foo1: &'f Foo<'f> = foo;
    Context { foo: foo1 }
}

Here, we assign a &'f Foo<'a> to a variable of a different type &'f Foo<'f>. Why is this allowed? We use 'a lifetime in Foo only for a shared reference. That means that Foo is covariant over 'a. And that means that the compiler can use Foo<'a> instead of Foo<'f> if 'a: 'f. In other words rustc is allowed to shorten the lifetime.

Its interesting to note that the original new function didnt say that 'a: 'f, although we had to add this bound to the impl block explicitly. For functions, the compiler infers such bounds from parameters.

Hopefully, Ive mixed polarity an even number of times in this variance discussion :-)

Going invariant

Lets throw a wrench in the works by adding some unique references:

struct Foo<'a> {
    buff: &'a mut String
}

impl<'a> Foo<'a> {
    fn push(&mut self, c: char) {
        self.buff.push(c)
    }
}

struct Context<'f, 'a: 'f> {
    foo: &'f mut  Foo<'a>
}

impl<'f, 'a: 'f> Context<'f, 'a> {
    fn new(foo: &'f mut Foo<'a>) -> Self {
        Context { foo }
    }

    fn push(&mut self, c: char) {
        self.foo.push(c)
    }
}

fn test<'f, 'a>(foo: &'f mut Foo<'a>) {
    let mut ctx = Context::new(foo);
    ctx.push('9');
}

playground

Foo is now invariant, so the previous solution does not work:

struct Context<'f> {
    foo: &'f mut  Foo<'f>
}

impl<'f> Context<'f> {
    fn new<'a: 'f>(foo: &'f mut Foo<'a>) -> Self {
        let foo1: &'f mut Foo<'f> = foo;
        Context { foo: foo1 }
    }

    fn push(&mut self, c: char) {
        self.foo.push(c)
    }
}
error[E0308]: mismatched types
  --> src/main.rs:17:37
   |
17 |         let foo1: &'f mut Foo<'f> = foo;
   |                                     ^^^ lifetime mismatch
   |
   = note: expected type `&'f mut Foo<'f>`
              found type `&'f mut Foo<'a>`

playground

Unsheathing existentials

Lets look again at the Context type:

struct Context<'f, 'a: 'f> {
    foo: &'f mut  Foo<'a>
}

What we want to say is that, inside the Context, there is some lifetime 'a which the consumers of Context need not care about, because it outlives 'f anyway. I think that the syntax for that would be something like

struct Context<'f> {
    foo: &'f mut for<'a: f> Foo<'a>
}

Alas, for is supported only for traits and function pointers, and there it has the opposite polarity of for all instead of exists, so using it for a struct gives

error[E0404]: expected trait, found struct `Foo`
  --> src/main.rs:12:30
   |
12 |     foo: &'f mut for<'a: 'f> Foo<'a>
   |                              ^^^^^^^ not a trait

A hack

However, and this is what I realized reading the Cargos source code, we can use a trait here!

struct Foo<'a> {
    buff: &'a mut String
}

impl<'a> Foo<'a> {
    fn push(&mut self, c: char) {
        self.buff.push(c)
    }
}

trait Push {
    fn push(&mut self, c: char);
}

impl<'a> Push for Foo<'a> {
    fn push(&mut self, c: char) {
        self.push(c)
    }
}

struct Context<'f> {
    foo: &'f mut (Push + 'f)
}

impl<'f> Context<'f> {
    fn new<'a>(foo: &'f mut Foo<'a>) -> Self {
        let foo: &'f mut Push = foo;
        Context { foo }
    }

    fn push(&mut self, c: char) {
        self.foo.push(c)
    }
}

fn test<'f, 'a>(foo: &'f mut Foo<'a>) {
    let mut ctx = Context::new(foo);
    ctx.push('9');
}

playground

Weve added a Push trait, which has the same interface as the Foo struct, but is not parametrized over the lifetime. This is possible because Foos interface doesnt actually depend on the 'a lifetime. And this allows us to magically write foo: &'f mut (Push + 'f). This + 'f is what hides 'a as some unknown lifetime, which outlives 'f.

A hack, refined

There are many problems with the previous solution: it is ugly, complicated and introduces dynamic dispatch. I dont know how to solve those problems, so lets talk about something I know how to deal with :-)

The Push trait duplicated the interface of the Foo struct. It wasnt that bad, because Foo had only one method. But what if Bar has a dozen of methods? Could we write a more general trait, which gives us access to Foo directly? Looks like it is possible, at least to some extent:

struct Foo<'a> {
    buff: &'a mut String
}

impl<'a> Foo<'a> {
    fn push(&mut self, c: char) {
        self.buff.push(c)
    }
}

trait WithFoo {
    fn with_foo<'f>(&'f mut self, f: &mut FnMut(&'f mut Foo));
}

impl<'a> WithFoo for Foo<'a> {
    fn with_foo<'f>(&'f mut self, f: &mut FnMut(&'f mut Foo)) {
        f(self)
    }
}

struct Context<'f> {
    foo: &'f mut (WithFoo + 'f)
}

impl<'f> Context<'f> {
    fn new<'a>(foo: &'f mut Foo<'a>) -> Self {
        let foo: &'f mut WithFoo = foo;
        Context { foo }
    }

    fn push(&mut self, c: char) {
        self.foo.with_foo(&mut |foo| foo.push(c))
    }
}

fn test<'f, 'a>(foo: &'f mut Foo<'a>) {
    let mut ctx = Context::new(foo);
    ctx.push('9');
}

playground

How does this work? Generally, we want to say that there exists some lifetime 'a, which we know nothing about except that 'a: 'f. Rust supports similar constructions only for functions, where for<'a> fn foo(&'a i32) means that a function works for all lifetimes 'a. The trick is to turn one into another! The desugared type of callback f, is &mut for<'x> FnMut(&'f mut Foo<'x>). That is, it is a function which accepts Foo with any lifetime. Given that callback, we are able to feed our Foo with a particular lifetime to it.

Conclusion

While the code examples in the post juggled Foos and Bars, the core problem is real and greatly affects the design of Rust code. When you add a lifetime to a struct, you poison it, and all structs which contain it as a member need to declare this lifetime as well. I would love to know a proper solution for this problem: the described trait object workaround is closer to code golf than to the practical approach.

Discussion on /r/rust.