Traversing heterogenous tree with stack

[crabjuice]

Hi all,

I'm trying to build something similar to Cursor for Trees, where I traverse a mutable tree and build a stack of the nodes in the path as I perform a DFS. The difference is that my tree is heterogenous: nodes are of different types but they share a common trait. The nodes also take a type parameter S. Unfortunately, trying to implement the linked solution gives me a compiler error (detailed below). Primarily, I'd like to know what's causing the compiler error and how to fix it and, secondarily, alternative solutions to the problem.

The following code is the minimal code I could find that created the error while still retaining the heterogenous feature of my tree.

Here's a minimal example of what I'm working with:

trait Node<S> {
    fn get_val(&self) -> &S;
}

struct NodeA<S> {
    val: S,
    a: Option<Box<NodeA<S>>>,
    b: Option<Box<NodeB<S>>>,
}

struct NodeB<S> {
    val: S,
    b: Option<Box<NodeB<S>>>,
}

impl<S> Node<S> for NodeA<S> {
    fn get_val(&self) -> &S {
        &self.val
    }
}

impl<S> Node<S> for NodeB<S> {
    fn get_val(&self) -> &S {
        &self.val
    }
}

Here's the traversal implementation based upon Cursor for Trees, since the tree is heterogenous, I used the common trait for the raw pointer:

struct TraverseMut<S> {
    stack: Vec<*mut dyn Node<S>>,
}

impl<S> TraverseMut<S> {
    fn map_a(&mut self, na: &mut NodeA<S>) {
        self.stack.push(na as *mut dyn Node<S>);

        // Do stuff to mutate node

        if let Some(ca) = &mut na.a {
            self.map_a(ca.as_mut());
        }
        if let Some(ba) = &mut na.b {
            self.map_b(ba.as_mut());
        }
        self.stack.pop();
    }

    fn map_b(&mut self, na: &mut NodeB<S>) {
        self.stack.push(na as *mut dyn Node<S>);

        // do stuff to mutate node

        if let Some(ba) = &mut na.b {
            self.map_b(ba.as_mut());
        }
        self.stack.pop();
    }
}

However, this gives me the compiler error:

error[E0310]: the parameter type `S` may not live long enough
  --> src/main.rs:38:25
   |
36 | impl<S> Traverse<S> {
   |      - help: consider adding an explicit lifetime bound...: `S: 'static`
37 |     fn visit_a(&mut self, na: &NodeA<S>) {
38 |         self.stack.push(na as *const dyn Node<S>);
   |                         ^^ ...so that the type `NodeA<S>` will meet its required lifetime bounds

I'm not sure why S needs a lifetime for a trait object or how to fix it as it's unclear to me where the lifetime specifier would go.

[arnaudgolfouse]

The lifetime would need to go on the trait object, else it is assumed to be 'static:

struct TraverseMut<'a, S> {
    stack: Vec<*mut (dyn Node<S> + 'a)>,
}

impl<'a, S> TraverseMut<'a, S> where S: 'a {
    // same as before
}

[crabjuice]

Thanks, that solved the lifetime error.

But there must be something that I'm missing because why do I need a lifetime for a raw pointer to a trait object but not for a raw pointer to an object?

For example, the following code has no errors:

struct MyS<A> {
    a: A,
}

struct Thing<A> {
    stack: Vec<*const MyS<A>>,
}

impl<A> Thing<A> {
    fn test(&mut self, ms: &mut MyS<A>) {
        self.stack.push(ms as *const MyS<A>);
    }   
}

Having a raw pointer point to a trait object also works without a lifetime when the underlying object does not have a type parameter:

struct MyS {}

trait MyTrait {}

impl MyTrait for MyS {}

struct Thing {
    stack: Vec<*const dyn MyTrait>,
}

impl Thing {
    fn test(&mut self, ms: &mut MyS) {
        self.stack.push(ms as *const dyn MyTrait);
    }   
}

So the raw pointer only requires a lifetime when it's pointing to a trait object whose underlying implementation takes a type parameter. But I don't understand why that would require a lifetime when having a raw pointer to the implementing object doesn't require a lifetime.

[alice]

The lifetime on a trait object is used to encode information about any references that is stored in the underlying struct.

In your first snippet, it points at a specific struct, so the compiler knows whether it contains a reference — just look at the struct definition.

In the second snippet, you are converting a known type MyS, and the compiler can look at that type to verify that it contains no references, hence a trait object with no lifetime (i.e. + 'static by default) is appropriate.

However in the original situation, depending on what S is, the NodeA<S> struct may indeed contain a reference, so + 'static would not be appropriate in that case.