How do I implement the Chain of Responsibility pattern using a chain of trait objects?

Question

I'm trying to implement the Chain of Responsibility design pattern in Rust:

pub trait Policeman<'a> {
    fn set_next(&'a mut self, next: &'a Policeman<'a>);
}

pub struct Officer<'a> {
    deduction: u8,
    next: Option<&'a Policeman<'a>>,
}

impl<'a> Officer<'a> {
    pub fn new(deduction: u8) -> Officer<'a> {
        Officer {deduction, next: None}
    }
}

impl<'a> Policeman<'a> for Officer<'a> {
    fn set_next(&'a mut self, next: &'a Policeman<'a>) {
        self.next = Some(next);
    }
}

fn main() {
    let vincent = Officer::new(8);    // -+ vincent enters the scope
    let mut john = Officer::new(5);   // -+ john enters the scope
    let mut martin = Officer::new(3); // -+ martin enters the scope
                                      //  |
    john.set_next(&vincent);          //  |
    martin.set_next(&john);           //  |
}                                     // martin, john, vincent out of scope

This produces the error message:

error[E0597]: `john` does not live long enough
  --> src\main.rs:29:1
   |
27 |     john.set_next(&vincent);
   |     ---- borrow occurs here
28 |     martin.set_next(&john);
29 | }
   | ^ `john` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `martin` does not live long enough
  --> src\main.rs:29:1
   |
28 |     martin.set_next(&john);
   |     ------ borrow occurs here
29 | }
   | ^ `martin` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error[E0597]: `john` does not live long enough
  --> src\main.rs:29:1
   |
28 |     martin.set_next(&john);
   |                      ---- borrow occurs here
29 | }
   | ^ `john` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

Why does john not live long enough?

1. Created vincent
2. Created john
3. Created martin
4. john refers to vincent (vincent in scope)
5. martin refers to john (john in scope)
6. martin out of scope (john still in scope)
7. john out of scope (vincent still in scope)
8. vincent out of scope

How do I need to change the lifetimes or the code to correctly implement the Chain of Responsibility pattern in Rust?

Answer 1

Detailed explanation

Your problem is quite interesting and it's certainly hard to understand directly why it doesn't work. It helps a lot if you understand how the compiler does unification. We will walk through all steps the compiler does in order to find out types.

In order to make it a bit easier, we use this simplified example:

let vincent = Officer::new(8);
let mut john = Officer::new(5);

john.set_next(&vincent);

This results in the same error message:

error[E0597]: `john` does not live long enough
  --> src/main.rs:26:1
   |
25 |     john.set_next(&vincent);
   |     ---- borrow occurs here
26 | }  
   | ^ `john` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

First, let's transform the code in a form that's more explicit, lifetime wise:

{ // start 'v
    let vincent = Officer::new(8);   

    { // start 'j
        let mut john = Officer::new(5);  

        john.set_next(&vincent);    
    } // end 'j
} // end 'v

---

Ok, now we're prepared to see what the compiler is thinking, step by step:

{ // start 'v
    let vincent = Officer::new(8); // : Officer<'?arg_vincent>

Rust doesn't know the lifetime parameter yet, thus it can only deduce an incomplete type here. Hopefully we can fill out the details later! When the compiler wants to show missing type information, it prints an underscore (e.g. Vec<_>). In this example I've written the missing information as '?arg_vincent. That way we can refer to it later.

    { // start 'j
        let mut john = Officer::new(5); // : Officer<'?arg_john>

The same as above.

        john.set_next(&vincent);

Now it get's interesting! The compiler has this function signature:

fn set_next(&'a mut self, next: &'a Policeman<'a>)

Now, the compiler's job is to find a fitting lifetime 'a that satisfies a bunch of conditions:

• We have &'a mut self and john is self here. So 'a can't live longer than john. In other words: 'j outlives 'a, denoted 'j: 'a.
• We have next: &'a ... and next is vincent, so (just like above), 'a can't live longer than vincent. 'v outlives 'a => 'v: 'a`.
• Lastly, the 'a in Policeman<'a> refers to the (yet to be determined) lifetime parameter '?arg_vincent (since that's what we pass as argument). But '?arg_vincent is not yet fixed and totally unbounded. So this doesn't impose a restriction on 'a (unlike the previous two points). Instead, our choice for 'a determines'?arg_vincent later: '?arg_vincent := 'a.

So in short:

'j: 'a    and
'v: 'a

So what's a lifetime which lives at most as long as john and as most as long as vincent? 'v isn't sufficient, since it outlives john. 'j is fine; it satisfied the conditions above.

So everything is fine? No! We chose the lifetime 'a = 'j now. Thus we also know that '?arg_vincent = 'j! So the full type of vincent is Officer<'j>. This in turn tells the compiler that vincent borrowed something with the lifetime j. But vincent lives longer than 'j, so it outlives its borrow! That's bad. That's why the compiler complains.

This whole thing is really rather complex, and I guess that after reading my explanation, most people feel exactly like I feel after reading most math proofs: each step made sense, but the result isn't intuitive. Maybe this improves the situation slightly:

Since the set_next() function requires all lifetimes to be 'a, we impose a lot of restrictions on all lifetimes in our program. This quickly leads to contradictions in restrictions, as it happened here.

A quick fix for my small example

... is to remove the 'a from the self parameter:

fn set_next(&mut self, next: &'a Policeman<'a>)

By doing that we remove unnecessary restrictions. Unfortunately, this isn't enough to make your whole example compile.

A more general solution

I'm not very familiar with the design pattern you mentions, but from the looks of it, it's close to impossible to track the involved lifetimes at compile time. Thus I'd use Rc or Arc instead of references. With those smartpointers, you don't need to annotate lifetimes and everything "just works". Only disadvantage: a tiny bit of runtime cost.

But it's impossible to tell you the best solution: it really depends on the problem at hand.

Answer 2

Lukas's excellent answer explains why this won't work and you should consider using smart pointers -- either Box for single ownership, or Rc/Arc for shared ownership.

That said, you can do something similar (although not very useful) by getting rid of the Policeman trait and making set_next inherent to Officer:

pub struct Officer<'a> {
    deduction: u8,
    next: Option<&'a Officer<'a>>,
}

impl<'a> Officer<'a> {
    pub fn new(deduction: u8) -> Officer<'a> {
        Officer {deduction, next: None}
    }
    fn set_next(&mut self, next: &'a Officer<'a>) {
        self.next = Some(next);
    }
}

fn main() {
    let vincent = Officer::new(8);    // -+ vincent enters the scope
    let mut john = Officer::new(5);   // -+ john enters the scope
    let mut martin = Officer::new(3); // -+ martin enters the scope
                                      //  |
    john.set_next(&vincent);          //  |
    martin.set_next(&john);           //  |
}                                     // martin, john, vincent out of scope

This works (playground) because the struct Officer is covariant with respect to 'a. That means that if you have an Officer<'a>, you can treat it like an Officer<'b> as long as 'a: 'b; that is, when 'a outlives 'b, Officer<'a> is a subtype of Officer<'b>. This knowledge lets the compiler shrink the lifetimes of each reference in the way you probably expected at first. (There's another really good Q&A about variance that you may enjoy, although it doesn't quite apply to your situation.)

Traits, on the other hand, are always invariant with respect to their parameters, so Policeman<'a> is not a subtype of Policeman<'b>. This robs the compiler of the ability to adjust lifetimes: the reference &'_ john could perhaps have a shorter lifetime, but the Policeman<'_> trait can't. That's why even Lukas's "quick fix" won't work on your whole example.

There's at least one more way to make the original example work by adding a lifetime parameter so that set_next doesn't unify the two lifetimes in &'?first Policeman<'?second>, but from that change you get only one extra layer of indirection -- i.e., it would make the example work, but if you added michael who reports to martin, you'd be back where you started.