More help for more complex lifetime situation

We are stuck again with problems related to lenders. The playground is here (sorry, it is a bit long):

In a nutshell: the Lender interface comes from the Lender crate, and is inspired by this famous blog post by Sabrina Jewson. In the Lender interface you specify the type of object lent using HRTBs (see the post as to why). The problem is that it is not possible to have where clauses for higher-rank trait bounds (RFC: extended_hrtbs by tema3210 · Pull Request #3261 · rust-lang/rfcs · GitHub).

In the SequentialLabelling trait we want to have a type for Successors (an Iterator), and a type for Iterator. Iterator is a Lender returning pairs (usize, Successors). In a fully lazy implementation based on a Read, both Iterator and Successor depend on the Read. The problem is that we have to specify a lifetime for the Read as a parameter to both, and we can only use 'succ for the type Successors, and 'node for the type Iterator. We have no way to explain to Rust that 'node outlives 'succ.

If we had RFC: extended_hrtbs by tema3210 · Pull Request #3261 · rust-lang/rfcs · GitHub we could modify the Lender implementation so that 'succ is not arbitrary. But lacking that, can anybody suggest a workaround?

Does the HRTB here:

pub trait SequentialLabelling {
    type Iterator<'node>: Lender
        + for<'succ> Lending<'succ, Lend = (usize, Self::Successors<'succ>)>

serve any particular need? This compiles.

 pub trait SequentialLabelling {
     type Value;
     type Successors<'succ>: IntoIterator<Item = Self::Value>
-    ;
+    where
+        Self: 'succ;
    
     type Iterator<'node>: Lender
-        + for<'succ> Lending<'succ, Lend = (usize, Self::Successors<'succ>)>
+        + Lending<'node, Lend = (usize, Self::Successors<'node>)>
     where
         Self: 'node;
 }
2 Likes

Incidentally, the error is valid and not just a compiler short-coming. Consider this notional desugaring:

/*
impl<'succ, R> Lending<'succ> for Iterator<R> {
    type Lend = (usize, Labels<'succ, R>);
}
*/
impl<'succ, 'node> Lending<'succ> for Iterator<RB::Reader<'node>> 
where
    RB: ReaderBuilder,
{
    type Lend = (usize, Labels<'succ, RB::Reader<'node>>);
}

But you then implemented

impl<RB: ReaderBuilder + 'static> SequentialLabelling for SwhLabels<RB> {
    type Value = Vec<u64>;
    type Successors<'succ> = Labels<'succ, RB::Reader<'succ>>;
    type Iterator<'node> = Iterator<RB::Reader<'node>>
    where
        Self: 'node;
}

And indeed, these two types are only the same when 'node = 'succ exactly.

Labels<'succ, RB::Reader<'node>> // From the Lending<'succ> impl
Labels<'succ, RB::Reader<'succ>> // From Successors<'succ>

(Type equality doesn't care about variance, and lifetimes in unnormalized GAT's are invariant to boot.)


But I didn't get it to work when taking that into account, either.

3 Likes

You can read Sabrina Jewson's post I quoted for a detailed answer.

But then the compiler does not complain about invariance—rather, about lifetimes outliving other lifetimes. I'm confused.

I'm familiar with the post. I'm not going to try to dig out exactly what you mean though. Provide some code that fails with the compiling version, perhaps?

The op does complain about lifetimes being unequal. Can you be more specific about your confusion?

Well, it says

   = note: expected tuple `(_, Labels<'_, <RB as ReaderBuilder>::Reader<'node>>)`
              found tuple `(_, Labels<'_, <RB as ReaderBuilder>::Reader<'succ>>)`
note: the required lifetime does not necessarily outlive the lifetime `'node` as defined here

The way I understand it, it is complaining about 'succ not outliving 'node. Am I getting it wrong?

Oh, I see. At a guess that's pointed out to try to get the programmer to understand why things couldn't work. But the associated type equality bound can't succeed if the lifetimes are different, no matter which is longer or shorter.

If you change the bound like showen below, the note changes to pointing out that node isn't long enough instead of 'succ not being long enough, but the core problem remains the same: the lifetimes don't match exactly.

    type Iterator<'node>: Lender
        + for<'succ> Lending<'succ, Lend = (usize, Self::Successors<'static>)>

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. ↩︎

Well, first of all thanks for taking the time to write this—I'll need some time to digest it. And thanks also for pointing out your documentation on lifetimes—it seems really enlightening. I had toyed with the idea of eliminating Successors, but I didn't know where to start.

One shallow observation: from what you write, it seems like we want to call multiple times iter.next_lend(). No, that's the starting point of all this—we want a lender, something in which you cannot hold a reference to the returned element and get another. You can have a loop around a lender, but you cannot do let labels = iter.next_lend(); twice in a row.

Additionally, __Seal is a sealed trait of the Lender crate, so we cannot change it. I'm trying to work around the issue.

UPDATE: It works! I got fooled about next_lend because of non-lexical lifetimes—indeed, if you try to do anything with a result after you get another one the code does not compile anymore. Phew!

The only problem is how to work around the sealed trait. But this is really a big progress.

I didn't change the seal from the OP. I did rename the method for ease of developent; that was the only change to the Lend* parts.

The two lifetime version still has that property - any &mut self method whose return captures the lifetime does. The "borrowed forever" antipattern is more severe. You can't use a loop because you can't use it twice, period.

Or I don't still don't understand the end goal, in which case I doubt I will without an example.


Here's a version without the rename and with another (commented) example showing how the single lifetime annotations is incompatible with a lending iterator loop.

Yes, you're right, but the playground is a simplified version of the Lender trait in the Lender crate. The Lender crate use a sealed trait and associated structure to avoid that user can change the value of __Seal. This is the part I need to work around.

When preparing examples in a playground there's always a tension between two forces—making it enough simple to be compilable in isolation and understandable, and reproducing fully the constraints of the problem. In this case I left out the sealing part for simplicity.

It might be argued, given this example, and provided there's no other solution, that sealing the trait/structure is a bad idea, as it prevents people from propagating it in certain useful cases.

As I wrote in the last message, I got fooled by NLL about the behavior of the trait: it works correctly as a lender, and, if you need Successors, the two-lifetime version, as you say, is the correct one. I must add that in the entire codebase I never needed to use explicitly the Successors type, so I did not even look into the matter in detail.

BTW, I think that at Advice to add a static bound - Learning Rust the link to the issue links the wrong issue.

We've been able to use your solution by relaxing a bit the sealing in Lender. It seems it is actually useful to be able to fiddle with the implicit bound.

We would like to credit your contribution to the trait design in the documentation. If you're Ok with that please send me your name in private (sebastiano.vigna@gmail.com).

1 Like