How to specify lifetime bounds for nested generic associated types

help
1

Hi,

I have these traits that describe a multi-level tree, Trunk -> Branch -> Leaf. When you fetch a sub-level it is bound to the lifetime of the level above it.

/// Trunks contain branches
pub trait Trunk {
    /// The Branch type for this trunk.
    ///
    /// Branches can contain a reference back to the trunk.
    type Branch<'t>: Branch where Self: 't;

    /// Fetch a branch
    fn branch(&self) -> Self::Branch<'_>;
}

/// Branches contain leaves
pub trait Branch {
    /// The Leaf type for this branch.
    ///
    /// Leaves can contain a reference back to the branch.
    type Leaf<'b>: where Self: 'b;

    /// Fetch a leaf, converting it to the specified type `T`.
    ///
    /// `T` must implement From<Self::Leaf>
    fn leaf_as<'b, T>(&'b self) -> T
    where
        T: From<Self::Leaf<'b>>;
}

I then want to be able to act on these trees in a general sense:

pub fn use_generic_trunk<T>(trunk: T) -> String
where
    T: Trunk,
    // XXX: What lifetimes can I put here?
    for<'t, 'b> String: From<<T::Branch<'t> as Branch>::Leaf<'b>>,
{
    trunk.branch().leaf_as()
}

But I can't find a way to make the compiler happy with the String: From<...> bound.

For instance, given this specific implementation of the traits:

mod specific_impl {
    pub struct Trunk {
        pub text: String,
    }

    impl super::Trunk for Trunk {
        type Branch<'t> = Branch<'t>;

        fn branch(&self) -> Self::Branch<'_> {
            Branch {
                trunk: self,
            }
        }
    }

    pub struct Branch<'t> {
        trunk: &'t Trunk,
    }

    impl<'t> super::Branch for Branch<'t> {
        type Leaf<'b> = Leaf<'t, 'b> where Self: 'b;

        fn leaf_as<'b, T>(&'b self) -> T
        where
            T: From<Self::Leaf<'b>>,
        {
            T::from(Leaf { branch: self })
        }
    }

    pub struct Leaf<'t, 'b> {
        branch: &'b Branch<'t>,
    }

    impl<'t, 'b> From<Leaf<'t, 'b>> for String {
        fn from(leaf: Leaf<'t, 'b>) -> Self {
            leaf.branch.trunk.text.clone()
        }
    }

    pub fn use_specific_trunk(trunk: Trunk) -> String {
        super::use_generic_trunk::<Trunk>(trunk)
    }
}

The super::use_generic_trunk::<Trunk>(trunk) line produces this compiler error:

error: implementation of `Branch` is not general enough
  --> crate/src/lib.rs:77:9
   |
77 |         super::use_generic_trunk::<Trunk>(trunk)
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ implementation of `Branch` is not general enough
   |
   = note: `Branch` would have to be implemented for the type `specific_impl::Branch<'0>`, for any lifetime `'0`...
   = note: ...but `Branch` is actually implemented for the type `specific_impl::Branch<'1>`, for some specific lifetime `'1`

This approach works with only one level of nesting, I.E. if I was trying to write use_generic_branch rather than use_generic_trunk, but doesn't work with more than one level of nesting.

Is what I'm trying to do possible? Thanks in advance for any help!

2

You probably need an alternative to GATs. Here's what I came up with:

(I got there mechanically and didn't try anything out once it compiled.)

3

Thanks for the pointer, that's an interesting read.

I understand now why naive HRTBs don't work, and I can understand how the implicit bound introduced by reference types can constrain them. I just need to stare at it a bit longer to really understand how it all fits together.

4

Once you get your head around it, there are some cleanups you can do so writing bounds aren't so painful.

The names are nicer if you add traits to encapsulate for<'t> TrunkLt<'t> like the article does. I didn't move the method so that implementors only had to implement one trait.

You could then add another trait for for<'t> TrunkLt<'t, Branch: Branch> to simplify some more. But if you're never going to have a <_ as TrunkLt>::Branch that doesn't meet that bound, you might as well add it to the base trait. And you can also add some handy type aliases for accessing the associated types in shorter form.

Then altogether you get:

 pub fn use_generic_trunk<T>(trunk: T) -> String
 where
-    for<'t> T: TrunkLt<'t, Branch: for<'b> BranchLt<'b>>,
-    for<'t, 'b> String: From<<<T as TrunkLt<'t>>::Branch as BranchLt<'b>>::Leaf>,
+    T: Trunk,
+    for<'t, 'b> String: From<LeafOf<'t, 'b, T>>,
 {
5

Thanks for that, I can see how it all fits together now, and with the extra type aliases it isn't too bad for generic callers to have to express bounds.

Thanks for the help!

1 Like