Why does a function body compile in a struct, but not in a trait?

Question

This code defines a very simple trait for representing binary trees and a struct implementing that trait:

pub trait BTree<T> {
    fn all(&self) -> Option<(&Self, &Self, &T)>;
    fn left(&self) -> Option<&Self>;
    fn right(&self) -> Option<&Self>;
    fn value(&self) -> Option<&T>;
}

pub struct MyBTree<T> {
    opt: Option<Box<(MyBTree<T>, MyBTree<T>, T)>>,
}

impl<T> BTree<T> for MyBTree<T> {
    fn all(&self) -> Option<(&Self, &Self, &T)> {
        match self.opt {
            None => None,
            Some(ref tuple) => Some((&tuple.0, &tuple.1, &tuple.2)),
        }
    }

    fn left(&self) -> Option<&Self> {
        match self.all() {
            None => None,
            Some((left, _, _)) => Some(left),
        }
    }

    fn right(&self) -> Option<&Self> {
        match self.all() {
            None => None,
            Some((right, _, _)) => Some(right),
        }
    }

    fn value(&self) -> Option<&T> {
        match self.all() {
            None => None,
            Some((_, _, value)) => Some(value),
        }
    }
}

The implementations of left, right and value could be moved inside the trait as they only depend on the all method defined by the trait, and not on implementation details.

This works fine with value, but not with left and right. For example, if I try to move the implementation of left in the body of the trait, I get the following compilation error:

error[E0311]: the parameter type `T` may not live long enough
--> src/lib.rs:6:24
  |
6 |             match self.all() {
  |                        ^^^
  |
= help: consider adding an explicit lifetime bound for `T`
note: the parameter type `T` must be valid for the anonymous lifetime #1 defined on the method body at 5:9...
--> src/lib.rs:5:9
  |
5 | /         fn left(&self) -> Option<&Self> {
6 | |             match self.all() {
7 | |                 None => None,
8 | |                 Some((left, _, _)) => Some(left),
9 | |             }
10| |         }
  | |_________^
note: ...so that the reference type `&T` does not outlive the data it points at
--> src/lib.rs:6:24
  |
6 |             match self.all() {
  |

Why does this problem occur in the trait but not in the implementation for MyBTree?

Why does the compiler complain about the lifetime of T in the methods who ignore the T value -- while it works with the method value which does mention T in its return type?

Answer 1

How come this problem occurs in the trait, but not in its implementation for MyBTree?

These method signatures become more nuanced when you consider implementing BTree<T> for a type that has a lifetime. My general advice for all lifetime errors involving a generic type parameter or a Self type is: focus on the case when the type is a borrowed type.

The trouble with borrowed types is you can never have a reference with a longer lifetime than the data it refers to. The simplest example of this principle is:

fn f<'a, 'b>() {
    // error[E0491]: in type `&'a &'b ()`, reference has a longer
    // lifetime than the data it references
    let _: &'a &'b ();
}

Rust forces us to guarantee that the data referred to by the reference outlives the reference, in this case 'b outlives 'a.

fn f<'a, 'b: 'a>() {
    let _: &'a &'b ();
}

Now let's apply this to your BTree situation by considering what goes wrong if T is a borrowed type like &(). First, looking at the following two methods which you placed in impl<T> BTree<T> for MyBTree<T>. I have written the elided lifetimes explicitly to clarify the discussion.

impl<T> BTree<T> for MyBTree<T> {
    fn left<'a>(&'a self) -> Option<&'a Self> { /* ... */ }
    fn value<'a>(&'a self) -> Option<&'a T> { /* ... */ }
}

In order for the caller to invoke left, they must know that Self outlives lifetime 'a. And in order for the caller to invoke value they must know that Self outlives lifetime 'a and T outlives lifetime 'a (in order for &'a T to be a meaningful type, as we saw above). The borrow checker will not let them call these methods unless those requirements are met, and so the implementation can assume those requirements are met.

Further, the borrow checker can see that if Self outlives 'a then also T outlives 'a because MyBTree<T> contains a value of type T.

This is why there was no problem implementing left and value within impl<T> BTree<T> for MyBTree<T>. The caller and the MyBTree<T> structure together guarantee that everything lives as long as we need.

Now in the case that we had these methods in the BTree<T> trait definition.

trait BTree<T> {
    fn left<'a>(&'a self) -> Option<&'a Self> { /* ... */ }
    fn value<'a>(&'a self) -> Option<&'a T> { /* ... */ }
}

Things go wrong here because if the caller invokes left they must know that Self outlives 'a, but they have not guaranteed that T outlives 'a. For example they could have T=&'b () for some totally unrelated shorter lifetime 'b. As we saw above, that would make &'a T equal to &'a &'b () which would not be a legal type.

The reason Rust is happy with value defined in the trait is that the caller guarantees both Self and T outlive the input lifetime 'a. The reason Rust is not happy with left defined in the trait is that the caller guarantees only Self outlives 'a, not T outlives 'a which the implementation assumes.

And how come the compiler complains about the lifetime of T in the methods who ignore the T value -- while it works with the method value which does mention T in its return type?

Well the error is not about the return value, it is about the call to all(). Look closely.

error[E0311]: the parameter type `T` may not live long enough
--> src/lib.rs:6:24
  |
6 |             match self.all() {
  |                        ^^^

In order to call all(), the caller is responsible for proving that the input and output types are valid types. But in the case that T is something like &'b (), this may not be true. The all() would return &'a &'b () so the borrow checker prevents the call.

We can fix this by making explicit the guarantees that our implementation assumes, in this case that T outlives 'a.

trait BTree<T> {
    fn left<'a>(&'a self) -> Option<&'a Self>
    where
        T: 'a,
    { 
        /* ... */ 
    }
}