sfackler/streaming-iterator

An alternate design for `StreamingIterator` based on HRTBs

Closed this issue · 8 comments

Kestrer commented

The design is this:

pub trait StreamingIterator<'s, ImplicitBound: sealed::Sealed = sealed::ImplicitBounds<'s, Self>> {
    type Item;
    fn next(&'s mut self) -> Option<Self::Item>;
}

mod sealed {
    pub trait Sealed {}
    pub struct ImplicitBounds<'a, T: ?Sized>(&'a T); // T: 'a
    impl<T: ?Sized> Sealed for ImplicitBounds<'_, T> {}
}

Here is a playground of it being used to implement WindowsMut. Note that it is working when neither the iterator nor the iterator's item are 'static.

Note that I have only a vague idea of how this actually works, I'm not an expert on rustc. But the general idea is that the hidden type parameter on the trait effectively gives a where Self: 's bound to the trait, but in a special way that works with HRTBs.

cuviper commented

Yes, that's a possibility that you'll see discussed in some of the background for Generic Associated Types (GATs), like in the RFC here:
https://rust-lang.github.io/rfcs/1598-generic_associated_types.html#push-hrtbs-harder-without-associated-type-constructors

It tends to infect HRTB lifetimes into in every place that wants to use it, especially when you build more APIs on top of it.

Kestrer commented

That's true, although it's not like GATs avoid that in a significant way. You'll still see them everywhere:

where
    T: StreamingIterator,
    for<'a> <T as StreamingIterator>::Item<'a>: Clone,

versus the non-GAT version:

where
    T: for<'a> StreamingIterator<'a>,
    for<'a> <T as StreamingIterator<'a>>::Item: Clone,

Or this comparison:

// with GATs
T: for<'a> StreamingIterator<Item<'a> = &'a u32>,
// no GATs
T: for<'a> StreamingIterator<'a, Item = &'a u32>,

It's basically identical. It's also possible that this library could provide a trait alias for for<'a> StreamingIterator<'a> in case that gets too tedious to type out, making the number of scenarios you have to type out more HRTBs than with the GAT version very small.

cuviper commented

Ok, well this library isn't using GATs yet either. The limitation of using &Item does also let us avoid lifetimes at all in many cases, and with #23 it should be possible to implement WindowsMut, albeit with additional traits.

Kestrer commented

well this library isn't using GATs yet either

I was assuming you'd eventually want to switch to using GATs once they stabilize rather than keep the &Item version. But I might be mistaken.

The limitation of using &Item does also let us avoid lifetimes at all in many cases

That's true, although this helper could exist to avoid lifetimes in the &Item case:

pub trait RefStreamingIterator
where
    Self: for<'a> StreamingIterator<'a, Item = &'a <Self as RefStreamingIterator>::RefItem>,
{
    type RefItem: ?Sized;
}

impl<I: ?Sized, T: ?Sized> RefStreamingIterator for I
where
    Self: for<'a> StreamingIterator<'a, Item = &'a T>,
{
    type RefItem = T;
}

with #23 it should be possible to implement WindowsMut, albeit with additional traits.

One of the reasons I wanted this design was to avoid having additional traits, because otherwise we'd end up having all of:

  • StreamingIterator
  • DoubleEndedStreamingIterator
  • StreamingIteratorMut
  • DoubleEndedStreamingIteratorMut
  • FallibleStreamingIterator
  • DoubleEndedFallibleStreamingIterator
  • FallibleStreamingIteratorMut
  • DoubleEndedFallibleStreamingIteratorMut

Which is really quite excessive, and only increases exponentially if we ever want to represent more properties.

cuviper commented

I was assuming you'd eventually want to switch to using GATs once they stabilize rather than keep the &Item version. But I might be mistaken.

It's unclear. I'm helping maintain this crate, but I'm not the owner. There's also talk of adding a GAT LendingIterator to the standard library, so if that happens we can just let this one fade away as-is.

  • 👍1
Kestrer commented

Okay, so recently I've been working a lot with GAT-like traits and I've come to the conclusion that out of all the designs, the following one is definitely the best:

pub trait StreamingIteratorLifetime<'a, ImplicitBounds: sealed::Sealed = sealed::Bounds<&'a Self>> {
    type Item;
}
pub type Item<'a, I> = <I as StreamingIteratorLifetime<'a>>::Item;
pub trait StreamingIterator: for<'a> StreamingIteratorLifetime<'a> {
    fn next(&mut self) -> Option<Item<'_, Self>>;
}

mod sealed {
    pub trait Sealed {}
    pub struct Bounds<T>(T);
    impl<T> Sealed for Bounds<T> {}
}

For the following reasons:

  1. The dyn for<'a> GenericItem<'a, T> method pretty quickly runs into some pretty annoying compiler bugs calling methods on a streaming iterator that my version completely avoids.
  2. The "true GAT" version also has significant limitations in many cases like as defining a RefStreamingIterator type, which once again my version does not have.
  3. I have been working enough with traits defined using the above technique that I'm fairly confident in saying there are unlikely to be any major issues with it, like there were with real GATs and GivesItem-based GATs.
  4. By having the main trait not feature a lifetime parameter, it reduces the amount of HRTBs that users have to write in normal code: where T: StreamingIterator would just work and is shorter than where T: for<'a> StreamingIterator<'a>.
  5. By forcing users to implement both the lifetime-less subtrait (StreamingIterator) and the lifetimed supertrait (StreamingIteratorLifetime), the docs page for StreamingIterator becomes more useful since it actually lists implementations instead of an opaque blanket implementation (impl<T: ?Sized + for<'a> StreamingIteratorLifetime<'a>> StreamingIterator for T {} or something).
  6. By having all the streaming iterator trait methods be on StreamingIterator rather than StreamingIteratorLifetime there is consistency achieved between methods that can be on either trait (like next) and methods that can only be on StreamingIterator (like for_each, since its signature required access to the item type of the iterator for any given lifetime).

The primary disadvantage of this approach is the lack of dyn-safety. However, that can be worked around by providing a separate trait used for trait objects only, similar to how erased_serde::Serialize works. This other trait can use the dyn for<'a> GenericItem<'a. T> design which of course does lead to the aforementioned issues when calling trait methods in concrete contexts, but there's really not much we can do about that and it's better than having the problem even without type erasure.

Because of the issues with real GATs (that are unlikely to be fixed without a major addition in syntax that even hasn't been formally suggested at all), I do think that it would be best to actually push this idea forward, since it looks like even when real GATs land it will be the best option to achieve lifetime GATs.

@sfackler @cuviper what do you think?

Kestrer commented

Now that https://docs.rs/lending-iterator exists I can close this issue.

  • 👍1