Am I forced to use GATs for this?

I have the following code, link to playground:

use std::rc::Rc;

pub trait Being {
    type Ancestors;
    fn get_name(&self) -> &str;
    fn get_ancestors(&self) -> Self::Ancestors;
}

struct Child<T: Being, U: Being> {
    name: String,
    mother: Rc<T>,
    father: Rc<U>,
}

impl<T, U> Child<T, U>
where
    T: Being,
    U: Being,
{
    pub fn new(mother: Rc<T>, father: Rc<U>, name: &str) -> Self {
        Self {
            name: name.to_string(),
            mother,
            father,
        }
    }
}

impl<T, U> Being for Child<T, U>
where
    U: Being,
    T: Being,
{
    type Ancestors = (Rc<T>, Rc<U>);

    fn get_name(&self) -> &str {
        &self.name
    }

    fn get_ancestors(&self) -> Self::Ancestors {
        (Rc::clone(&self.mother), Rc::clone(&self.father))
    }
}

struct God {
    name: String,
}

impl God {
    pub fn new(name: &str) -> Self {
        God {
            name: name.to_string(),
        }
    }
}

impl Being for God {
    type Ancestors = ();

    fn get_name(&self) -> &str {
        &self.name
    }

    fn get_ancestors(&self) -> Self::Ancestors {
        ()
    }
}

fn main() {
    let ni = Rc::new(God::new("Ni"));
    let no = Rc::new(God::new("No"));
    let nino = Child::new(ni, no, "Nino");
    let (ni_, no_) = nino.get_ancestors();
    println!("Mother name: {} -  Father name: {}", ni_.name, no_.name);

    let ancestry: Vec<Rc<dyn Being>> = Vec::new(); // Build a Being ancestry and put it there
}

For the past week I've tried to iteratively build an ancestry of Beings, but I couldn't reach my goal. Any suggestions before I give up?

1 Like

I'm not sure what you are trying to do is possible, nor that it has anything to do with GATs. You can't dynamically change the associated type behind a dyn Trait, since all dyn Trait does is use indirect calls through a vtable; it erases all other type information. In particular, it doesn't hold pointers to dynamic type descriptors of associated types, so those must be known at compile time. So you can't quite make that part of the structure dynamic.

Depending on your use case, I can imagine two ways out:

  • If all you want is a dynamic tree/DAG of Beings, get rid of the Ancestors associated type and substitute it with Vec<Rc<dyn Being>> everywhere.
  • If you need to store the types, you will only be able to do that with some (rather straightforward) compile-time metaprogramming, namely, by tracking and composing ancestor types in children. You can then include a method to "reify" such a compile-time structure into a dynamic tree described in the previous point.
1 Like

Since you're creating a graph of beings, I'd highly recommend looking at crates like petgraph. It will handle all of this for you.

1 Like
  • If you need to store the types, you will only be able to do that with some (rather straightforward) compile-time metaprogramming, namely, by tracking and composing ancestor types in children. You can then include a method to "reify" such a compile-time structure into a dynamic tree described in the previous point.

I am completely lost. Would you be so kind to provide an example?

Sure, I meant something like this.

3 Likes

I looked at the code, nice work. Only for my understanding, where in the code are you “composing ancestor types”? Is it by definition of God, Child and () implementing the Ancestor trait?

If you guys like studying “fun” generic code and “solutions” to this problem, kind of similar to what @H2CO3 posted (and also somewhat different), then you can also take a look at what I did here.

But this is, to my understanding, recursive.

Would it be possible an iterative solution?

Sure. The recursive use case was probably even harder to get to work than an iterative approach..

1 Like

I feel incredibly stupid lol, I can't think think of an iterative solution that preserve the Ancestors type. Will appreciate one!

No problem. I was also going to write one after saying that it is possible, anyways. Here you go

fn for_all_ancestors_loop<'a, F: FnMut(Rc<dyn DynBeing<'a> + 'a>)>(b: Rc<dyn DynBeing<'a> + 'a>, mut f: F) {
    let mut stack = vec![b];
    while let Some(b) = stack.pop() {
        b.dyn_visit_ancestors(&mut |anc| {
            stack.push(anc)
        });
        f(b)
    }
}

(in the playground)

The order in which the ancestors are processed seems to be a bit different to the recursive approach.

2 Likes

Oh, so by "iteratively building" in your OP, you meant that you wanted to avoid recursion? Sorry I didn't get that. But yeah, as @steffahn demonstrated, most "natural"/useful kinds of recursion can be transformed into iteration.

Here’s a version where I removed the lifetimes from the Being trait again, in effect completely restoring your original code.

(playground)

no worries, no worries at all, also thank you very much for replying!

This may be the solution to my problem, I'll report back, thank you a lot!

@steffahn @H2CO3. In you opinion, could this be done with an HList without using dyn?

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.