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.