How to design around unconstrained lifetime parameters?

Hi,

I am trying to implement a subgraph trait for my abstract graph crate.
A subgraph should have a reference to its parent graph, and otherwise behave like any other graph.

A simplified version of the trait structure I would wish for is the following:

trait Graph {
    type NodeData;
}

trait Subgraph<'a> {
    type ParentGraph: Graph;
    
    fn new(parent: &'a Self::ParentGraph) -> Self;
    
    fn get_parent(&self) -> &'a Self::ParentGraph;
}

impl<'a, T: Subgraph<'a>> Graph for T {
    type NodeData = <<Self as Subgraph<'a>>::ParentGraph as Graph>::NodeData;
}

(Playground)

Ideally, implementing Subgraph on any type should forward certain functions and associated types of the corresponding parent graph type. Therefore, I would like to implement Graph for any type that implements Subgraph.

Sadly, the compiler rejects that because of an unconstrained lifetime:

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
  --> src/lib.rs:13:6
   |
13 | impl<'a, T: Subgraph<'a>> Graph for T {
   |      ^^ unconstrained lifetime parameter

error: aborting due to previous error

For more information about this error, try `rustc --explain E0207`.
error: could not compile `playground`.

To learn more, run the command again with --verbose.

I already managed to design around unconstrained type parameters using associated types (originally, I planned ParentGraph to be a generic type parameter, instead of an associated type). However, for lifetimes that does not seem to be possible, apparently because 'GATs' are not implemented.

Is there a way to design the abstractions around this? Or do I need to copy&paste the implementation of Graph for each type implementing Subgraph, instead of having one abstract implementation for all Subgraphs?

You can lift the lifetime parameter out of Subgraph to the individual implementatons by doing something like this, which will also support more complicated reference types, like Rc:

trait Graph {
    type NodeData;
}

trait Subgraph {
    type ParentGraph: Graph;
    type ParentRef: core::borrow::Borrow<Self::ParentGraph>;

    fn new(parent: Self::ParentRef) -> Self;

    fn get_parent(&self) -> Self::ParentRef;
}

impl<T: Subgraph> Graph for T {
    type NodeData = <<Self as Subgraph>::ParentGraph as Graph>::NodeData;
}

trait TempSubgraph<'a, G: Graph + 'a>: Subgraph<ParentGraph = G, ParentRef = &'a G> {}

impl<'a, G: Graph + 'a, S> TempSubgraph<'a, G> for S where
    S: Subgraph<ParentGraph = G, ParentRef = &'a G>
{
}

(Playground)

2 Likes

Thank you very much, that worked very well in my code!