Trait problem: Borrowed data escapes outside of associated function

Question

I am trying to implement a binary tree. I want the node data to be separate, because there are many different ways in which this can be implemented, while algorithms on the tree should be generic and independent of how the data is stored.

But I am running into a weird issue with the borrow checker. Basically, when I switch impl<TValue> Display for dyn Tree<TValue> with impl<TValue> Display for TreeNode<TValue>, the problem goes away. But I have no idea why. Why is the Trait causing this issue?

My code is this:

use std::fmt::{Display, Formatter};

struct TreeNode<TValue> {
    value: TValue,
    left: Option<Box<TreeNode<TValue>>>,
    right: Option<Box<TreeNode<TValue>>>,
}

trait Tree<TValue> {
    fn value(&self) -> &TValue;
    fn left(&self) -> Option<&dyn Tree<TValue>>;
    fn right(&self) -> Option<&dyn Tree<TValue>>;
}

impl<TValue> Display for dyn Tree<TValue>
where
    TValue: Display,
{
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_str("(")?;
        Display::fmt(self.value(), f)?;
        f.write_str(", ")?;

        match self.left() {
            Some(ref x) => x.fmt(f)?,
            None => f.write_str("None")?,
        }

        f.write_str(", ")?;

        match self.right().as_ref() {
            Some(x) => x.fmt(f)?,
            None => f.write_str("None")?,
        }

        f.write_str(")")
    }
}

impl<TValue> Tree<TValue> for TreeNode<TValue>
where
    TValue: Display,
{
    fn value(&self) -> &TValue {
        &self.value
    }

    fn left(&self) -> Option<&dyn Tree<TValue>> {
        self.left.as_ref().map(|x| &**x as &dyn Tree<TValue>)
    }

    fn right(&self) -> Option<&dyn Tree<TValue>> {
        self.right.as_ref().map(|x| &**x as &dyn Tree<TValue>)
    }
}

fn main() {
    let tree = Box::new(TreeNode {
        value: 1,
        left: Some(Box::new(TreeNode {
            value: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(TreeNode {
            value: 3,
            left: None,
            right: None,
        })),
    }) as Box<dyn Tree<i32>>;

    println!("{}", tree);
}

And the compiler prints:

error[E0521]: borrowed data escapes outside of associated function
  --> src\main.rs:24:15
   |
19 |     fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
   |            -----
   |            |
   |            `self` declared here, outside of the associated function body
   |            `self` is a reference that is only valid in the associated function body
   |            let's call the lifetime of this reference `'1`
...
24 |         match self.left() {
   |               ^^^^^^^^^^^
   |               |
   |               `self` escapes the associated function body here
   |               argument requires that `'1` must outlive `'static`

To me, this makes no sense. Nothing in the function body captures this value and tries to keep it beyond the scope of this function. Is this some borrow checker limitation?

Vitovitoria

This is a very confusing diagnostic so I think an issue should be filed regardless of the reason – Parhe

other than the weird diagnostic, why do you need everything to be dyn ? should a left branch of a tree be able to be a tree of another type ? – Kortneykoruna

also, from my testing, the error is introduced when you try to call fmt on x, not when you do self.left(). – Kortneykoruna

@Kortneykoruna it's not a want. The compiler seems to force me to make this a trait object. I am not sure why. But if I don't use dyn in the Trait itself, then all other places will require dyn and dyn won't be usable because then Tree is not a trait object. It's weird. I believe there still are many blind spots in Rust's compiler messages. – Vitovitoria

not saying dynamic dispatch is bad, but is there something that prevent you from doing it this way: playground ? – Kortneykoruna

@Kortneykoruna I am not sure why this didn't work for me, you seem to be trying what I was also trying. I will check tomorrow. Dynamic dispatch is actually bad in this case, because it isn't a zero-cost abstraction. And my tree algorithms should not force dynamic dispatch on everything. – Vitovitoria

only thing I could see to hold ypu back is that you wanted to implement Display for all types that impl Tree, and you can't do it with static dispatch, because you don't own the Display trait. note that the dyn way only implements Display for dyn Tree, not all types that implement Tree. – Kortneykoruna

Answer 1

There are some mental hoops that the compiler has to jump through to reason about your code. Spoilers, the reason is that when you have dyn Tree<TValue> (where you are implementing Display), the lifetime constraining the type defaults to 'static. So when you call x.fmt(f), the x type must be 'static in order to implement the fmt method, and looking backwards means that the self used in self.left() to get x must be 'static as well. But it's not, and thus the error.

The simple fix is to implement Display for dyn Tree<TValue> with any lifetime:

impl<'a, TValue> Display for dyn Tree<TValue> + 'a

Parhe

Can be for dyn Tree<TValue> + '_. But what I don't understand here is that self is not &'static dyn Tree, it's &'_ (dyn Tree + 'static) and so this should work fine. – Chad

@ChayimFriedman because the signature of .left() is fn<'a>(&'a self) -> Option<&'a (dyn Tree<TValue> + 'a)> (elided lifetimes expanded). So even if self is &'a (dyn Tree + 'static), the result of .left() is &'a (dyn Tree + 'a) (not 'static). I lament that the elided lifetimes of trait objects are different depending on where they are written. – Parhe

Oh true, I forgot that trait objects are invariant. – Chad