More help for more complex lifetime situation

10

Here's another approach: avoid the need for your Successors bound.

Make a trait at the deeper levels that enforces the constraints you want:

pub trait TupleLending<'lend, __Seal = &'lend Self>
where
    Self: Lending<'lend, __Seal, Lend = (usize, <Self as TupleLending<'lend, __Seal>>::TupleLend)>
{
    type SingleValue;
    type TupleLend: IntoIterator<Item = Self::SingleValue>;
}

<_ as TupleLending<'lend>>::TupleLend takes the role of Successors<'lend>, and thus we've moved that bound here. The supertrait bound enforces the type's "shape" that was part of the associated type bound between Successors and Iterator. SingleValue we'll use in a moment.

Types will have to implement this either in addition to or instead of[1] Lending.

impl<'succ, R: std::io::Read> TupleLending<'succ> for Iterator<R> {
    type SingleValue = Vec<u64>;
    type TupleLend = Labels<'succ, R>;
}
Optional: Remove some boilerplate

Unfortunately a blanket implementation here seems to run into HRTB problems still, so we can't have this.

impl<'lend, S, T: ?Sized, Lend> TupleLending<'lend, S> for T
where
    T: Lending<'lend, __Seal, Lend = (usize, Lend)>,
    Lend: IntoIterator,

But we can go the other direction:

impl<'lend, S, T: TupleLending<'lend, S>> Lending<'lend, S> for T {
    type Lend = (usize, T::TupleLend);
}

And this way implementors only need to implement TupleLending and not Lending.

-impl<'succ, R> Lending<'succ> for Iterator<R> {
-    type Lend = (usize, Labels<'succ, R>);
-}

...but maybe that's not tenable for your use case? For example, I had to add the R: Read constraint to the TupleLending implementation, so it covers less types. If this is unacceptable, types will have to implement both.

Then also make and blanket-implement a higher-ranked subtrait:

pub trait TupleLender
where
    Self: Lender,
    Self: for<'all> TupleLending<'all, SingleValue = <Self as TupleLender>::Value>,
{
    type Value;
}

impl<T: ?Sized, Value> TupleLender for T
where
    T: Lender,
    T: for<'all> TupleLending<'all, SingleValue = Value>
{
    type Value = Value;
}

Here we use a supertrait bound to make sure all the SingleValues unify into the same type (Value).

With these in place, SequentialLabelling can look like so:

pub trait SequentialLabelling {
    type Value;
    type Iterator<'node>: TupleLender<Value = Self::Value>
    where
        Self: 'node;
}

If you need to refer to the types that Successors used to be, that corresponds to

pub type Successors<'succ, 'node, This> =
    <
      <This as SequentialLabelling>::Iterator<'node> 
        as TupleLending<'succ>
    >::TupleLend;

I suspect any attempt to get that into a GAT with enforced type equality (analogous to how Value is "uplifted") will run into Rust's HRTB limitations for now.

You may be thinking, why can't we use this?

pub type SuccessorsOne<'succ, This> =
    <
      <This as SequentialLabelling>::Iterator<'succ> 
        as TupleLending<'succ>
    >::TupleLend;

Well, you sort-of can, but don't think you really want to. Here's how I presume you're going to want to use this:[2]

    let swh = SwhLabels { builder: SomeReader };
    // Get an SwhLabels::Iterator<SomeReader::Reader<'node>>
    let mut iter = swh.factory();
    // Get a `(usize, Labels<'succ, Reader<'node>>)`
    // This requires exclusively borrowing `iter` for `'succ`
    let labels = iter.next_lend();
    // Do it again a few more times...
    let labels = iter.next_lend();
    let labels = iter.next_lend();

If you tried to use SuccessorsOne to dial in the type here:

    let labels: Option<(usize, SuccessorsOne<'_, _>)> = iter.next_lend();

Then you force 'succ = 'node. Then because 'node is in an invariant position (under a &mut), you are forced to take a &'node mut Iterator<Reader<'node>>. That makes iter be exclusively borrowed for its entire validity, i.e. unusable afterwards. Once you call iter.next_lend() once with the single-lifetime annotation, you can never use iter again; further attempts to call next_lend will fail.[3]

(This also illustrates that a single-parameter GAT was probably not what you wanted, even if the bounds could somehow be stated. I tried to pinpoint an issue for my two-lifetime GAT attempt, but I'm not sure which issue that compiler error corresponds to.)

  1. see the optional section below ↩︎

  2. I renamed your next method on Lender to next_lend to reduce overlap with Iterator ↩︎

  3. There's a commented out example at the bottom of the playground link. ↩︎