How to design around unconstrained lifetime parameters?

help
#1

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?

#2

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
#3

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