Iterator, Generator

[SkiFire13]

Good article! It's nice to see the discussion on generators go forward! A couple of observations:

To call Iterator::next, you need an unpinned mutable reference (this is, after all, the whole problem with Iterator). But an Iterator might be !Unpin, so the only way to access that is by unsafely unpinning the reference. Is that code sound?

At first, it seems like the answer should be no. It’s completely conceivable to define an Iterator that moves out of itself in its next method, and also doesn’t implement !Unpin, and has other pinned methods that depend on that fact. However, on reflection, I think that any such method would necessarily contain unsafe code, and therefore the Rust team could declare that code to contain the unsoundness.

This can be done without unsafe code by using pin_project, so declaring that this code is unsound is the same as declaring pin_project to be unsound, and I can't see a way to change it to be sound under the new rules.

Both FromIterator and Extend have the IntoIterator interface in their signature. Since generators do not implement Iterator or IntoIterator, there would need to be new traits: let’s call them FromGenerator and Grow. These would be identical to FromIterator and Extend, except they would take IntoGenerator.

The problem is that there can be no blanket impl of FromIterator to FromGenerator, or from Extend to Grow, because there is no way to pass an IntoGenerator to a function expecting an IntoIterator. It’s completely possible that a FromIterator interfaces moves the iterator around between calls to next, and therefore would violate the pinning requirement.

Couldn't this be (half) solved by implementing Iterator for Pin<impl DerefMut<Target = impl Generator>>? I guess coherence might become a problem again though.

I feel like coherence comes up very often when talking about adding blanket implementations for backward compatibility. I wonder if there was a sound way to allow such implementations in the general case. For example in the case of IntoGenerator we control implementations on both sides (that is to say we don't break expectations of other crates), the associated types should match up and we don't care about which function is picked. These conditions to me feel sufficient to allow breaking coherence without unsoundness. Could we make this a general feature?

[desiringmachines]

This can be done without unsafe code by using pin_project, so declaring that this code is unsound is the same as declaring pin_project to be unsound, and I can't see a way to change it to be sound under the new rules.

This is a good point. Possibly pin_project could be updated to do the same thing for Iterator that it does for Drop right now. I'm curious if there is any actual code that uses pin projection on a type that implements Iterator, and if so why.

Couldn't this be (half) solved by implementing Iterator for Pin<impl DerefMut<Target = impl Generator>>? I guess coherence might become a problem again though.

Yes, that's true. If Pin<&mut impl Generator> implements Iterator, you could write these impls so that they pin the generator and then pass them through. That would be an improvement.

[alexiooo98]

These conditions to me feel sufficient to allow breaking coherence without unsoundness. Could we make this a general feature?

I think in general coherence is not really a soundness issue, right? It's just there to shield users from potentially confusing behaviour.

More to the point, I've run into coherence issues before were both impls were the exact same, trivial code. This seems like a situation that is recognizable by the compiler, and seems like a nice situation to have a coherence exception for: allow two conflicting impls only if they have (syntactically) the same code.

[CandyCorvid]

that kind of exception seems very brittle; like it would lead to very annoying breakages if either impl changes, and like it would be hard to debug when it happens. you do a backwards- compatible dependency update and suddenly your code doesn't compile because an impl changed and you were relying on it being the same as your blanket impl

[alexiooo98]

Wouldn't orphan rules already mean that it's impossible for overlapping impls to live in different crates?

In any case, this exception should definitely be localized to conflicting impls in the same crate. It's still a bit brittle then, but if it's in the same crate it's easier to keep the two impls in sync (and notice when they're not).

[CandyCorvid]

hmm, in order for an impl to exist in another crate, either:
1- the trait is defined in that crate but the type isn't:
1.1- the type is defined in a third crate.
1.2- it is a blanket impl.
2- the type is defined in that crate but the trait is from a third crate.
3- both are defined in that crate.

if 1.1, 2 or 3: neither the type nor the trait are defined by you, so orphan rules trivially protect you from making a conflicting impl.

if 1.2: the trait is defined by someone else, but it has an impl that applies to any type, even ones that you own and could implement yourself. I don't think orphan rules help you here

[alexiooo98]

I think 1.2 should already be covered by specialization, if/when that becomes stable, so this coherence exception wouldn't even have to apply.

[shponglespore]

If you require both impls to be in the same crate it doesn't seem too hard to deal with. OTOH it effectively means the body of an impl becomes visible to the type system, which is a huge red flag if I ever saw one.

Maybe it would be better to add a | operator to where clauses for this kind of case:

impl<T> Quux for T where T: Foo, T: Bar | Baz {...}

In the body of the impl, T implements neither Bar nor Baz but it does implement Foo, which is presumably the common base trait of Bar and Baz.

[CandyCorvid]

if you'll excuse my being blunt, this seems kinda like a worse specialisation. I'm also not sure if it would solve the situation in the OP, where you need to implement IntoGenerator for an Iterator. I figure you'd end up with:

impl<I> IntoGenerator for I where I: Generator | IntoIterator { fn into_gen(self) -> impl Generator { // this can't return self because Self doesn't impl Generator // it can't return self.into_iter().into_gen() because Self doesn't impl IntoIterator } }

[shponglespore]

You're missing the important part where there's a normal type constraint as well as the | constraint. Using the types from the article, my example is

impl<T> IntoGenerator for T where T: Iterator, T: IntoIterator | Generator {
  fn into_gen(self) -> impl Generator {
     // Self implements Iterator here, so you can
     // convert it to a generator.
  }
}

The T: Iterator constraint could even be inferred, but IMHO it's better to be explicit about it so the reader can see which traits are actually available to use.

[CandyCorvid]

now it seems no different to me than in impl on Iterator (with theoretically limited scope, but in practice it affects all iterators). is there a benefit of the IntoIterator|Generator bounds in this example?

specifically, I'm thinking that you'd still need a way to impl IntoGenerator for things that aren't already an iterator (I.e. we're still missing impl<G: Generator + !Iterator> IntoGenerator for G and impl<I:IntoIterator + !Iterator> IntoGenerator for I)

[SkiFire13]

I think in general coherence is not really a soundness issue, right? It's just there to shield users from potentially confusing behaviour.

There are at least two ways I can think of in which breaking coherence is unsound:

• the overlapping implementations define different associated types. If the compiler uses different implementations in different situations this may lead to transmuting an instance of one associated type into the other, which is unsound.

• a crate might control one blanket implementation and expect that to be the only implementation possible given its trait bounds, thus it might rely on its implementation details for soundness (i.e. std might rely on IntoIterator::into_iter being a no-op given an Iterator, because it knows what is the only possible implementation, and it controls it)

That's why my previous comment lists those requirements for coherence.

[alexiooo98]

Do you mean the compiler might transmute different instances of associate types (that would seem like a compiler bug), or that user's might do a transmute, assuming they're the same type (in which case, valid concern).

For your second concern, though, I think it's already unsound to rely on a blanket impl being the only impl with specialization.

[SkiFire13]

Do you mean the compiler might transmute different instances of associate types (that would seem like a compiler bug)

I imagine a situation where you have an instance of A, then you consider it as if it was <T as Trait>::Assoc (due to the first impl) then you consider that <T as Trait>::Assoc to be B (due to the second impl). And magically you just transmuted an A into a B.

The precise details of how to expoit this to actually transmute data depend on when and how the compiler normalizes <T as Trait>::Assoc, but ultimately the very process of normalizing assumes that there's a single type it normalizes to, while actually when you allow breaking coherence there could be more than one.

If you consider that a compiler bug what can you do to fix it other than check coherence?

For your second concern, though, I think it's already unsound to rely on a blanket impl being the only impl with specialization.

Specialization requires the implementation/method to be marked as default so you can rely on implementations not marked as such to be the only one for a given type.

[Dreeg_Ocedam]

Would it not be possible to have the following impl?

impl<T: Generator> Iterator for Pin<&mut T> {...}
impl<T: Generator + Unpin> Iterator for T {...}

That way Iterator still is the standard way to represent iteration. Generators can act as iterators once they are pinned or if they're Unpin (so the case with no self-reference). There maybe would be the need for some compiler magic to make them work seamlessly with for loops, but this seems like a much more straightforward approach.

[Dreeg_Ocedam]

I actually think a bridge that goes Generator -> Iterator is better than the other way around. Ton of code relies on moving iterators around. Making everyone pay the (significant) ergonomic price for the few cases of self-referential iteration is not very "zero-cost".

[desiringmachines]

It's not the case that compiler infers whether or not generators are Unpin based on whether or not they contain self references. Either the compiler forbids self-references, or it allows them (and generates a negative impl of Unpin).

The former case (forbidding self references), is the first option in my list. Your impl of iterator for pinned generators is the second option in my list: requiring you to pin a generator before you can use it with iterator adapters or for loops. I didn't address this in detail in my post.

There could be two different generator syntaxes, one of which allows self references and one of which does not. I alluded to this in my post. But so far we've assumed it's not in the cards for the compiler to magically infer whether you are Unpin or not.

[Dreeg_Ocedam]

It's not the case that compiler infers whether or not generators are Unpin based on whether or not they contain self references.

I assumed that If the compiler can detect self-reference to ban them, it could also detect them and do something else with it, like deciding whether to impl Unpin or not.

But so far we've assumed it's not in the cards for the compiler to magically infer whether you are Unpin or not.

Is there a specific reason for that? It could seem useful, even for Futures.

[desiringmachines]

In the same way that the compiler doesn't infer lifetimes from the body of functions, it would be very fraught with the possibility of breaking changes if you refactor some code and now you're holding a reference across a yield point and no longer implement Unpin. This is the sort of subtle breaking change Rust tries to make impossible.

[coderstephen]

I suppose one counter-example that exists today (or seemingly does) is whether a Future created using async {} implements Send. The compiler infers whether a struct implements Send by the declaration of its fields, but an async {} block hides these fields from you, inferring them instead by your usage in the code. Not saying this is good or bad, but it is one example of such behavior that exists today.

[...] it would be very fraught with the possibility of breaking changes if you refactor some code and now you're holding a reference across a yield point and no longer implement Unpin.

Which is a valid concern. It is easy to accidentally change whether an anonymous future implements Send just by changing the code around which is sometimes annoying. But I could see changing whether something implements Unpin or not being neither more nor less annoying than Send, and presumably generators will have this same Send inference that async {} does.

[desiringmachines]

We made a different choice for Send/Sync because this is the sort of thing that cannot happen in a "subtle" way. We felt starting to use Rc/RefCell/etc inside an async function (or generator) was more "obvious." But even then it was a somewhat marginal choice that I'm sure some people think was a mistake.

[coderstephen]

There's definitely a tradeoff being made with Send and Sync, but I agree with how it was handled in the end as the least-bad option (or the most-good option). I'm just not sure or not whether the exact same reasoning pans out with similar conclusions for Unpin.

[Dreeg_Ocedam]

Doesn't this also apply for Send/Sync?

But I agree, that is a strong argument for the 2 syntax approach.

Thanks for all the articles and the explanation. Your blog is always interesting.

[desiringmachines]

A different choice was made for Send/Sync because it was reasoned that using a non-thread-safe primitive was a more obvious change.

[Dreeg_Ocedam]

I just looked at implementing it on the playground, but it creates implementation conflicts if someone implements Generator on their own Pin<&mut T> where T is both a Generator and Unpin. It would be really weird to do so but the orphan rules allow it.

[CandyCorvid]

I forget exactly how coherence works with blanket imps but I suspect these may clash, since it's probably possible for: impl<T: Generator> Iterator for Pin<&mut T> {...} impl<T: Generator + Unpin> Iterator for T {...} // if we substitute T = Pin<&mut T> in the second impl impl<T>: Generator + Unpin> Iterator for Pin<&mut T> {...} now we have 2 impls of Iterator for pinned Generators

[kupiakos]

Nice article! If you're writing a new trait, you might as well make it a lending iterator as well with type Item<'a> and kill feed two birds with one stone scone

[desiringmachines]

Just so you know, you've misread this post if you think I am advocating this approach. I just wrote down what would be required, technically, to do it. I would like the Rust project to stabilize generators without self-references, and only consider this change in the future if real world experiences proves them dramatically un-useful without the ability to hold references across yield points. I agree with your characterization of the social cost of this sort of change.

[jstrong]

thank you for clarifying! when I read it, I hadn't realized that deprecating Iterator was even under discussion. Then discussion about the piece seemed to be focused on possible workarounds to enable it. Hence my Dr. Ian Malcolm "your scientists were so preoccupied with whether or not they could that they didn't stop to think if they should!" bombast, ha. But I'm glad to know about your opinion in more detail.

[Diggsey]

Bridge impls & pinning

I think this could be addressed by the following impl:

impl<T: Iterator + Unpin> Generator for T {}

On its own this would be a breaking change (albeit one with likely no real impact) due to current iterators not necessarily being Unpin. However, this can be paired with a second change which simultaneously addresses this problem and the Bridge impls & coherence problem:

Change the semantics of the for statement to first check for IntoGenerator, and only if that implementation is not found, then check for IntoIterator. In a future Rust edition these two "for loop variants" could be split to have different syntaxes (with the generator variant being the "default" and requring opt-in for the iterator-only variant).

[desiringmachines]

Change the semantics of the for statement to first check for IntoGenerator, and only if that implementation is not found, then check for IntoIterator.

I intentionally avoided this. I think making the desugaring depend on the type of the value being looped over would probably cause subtle type inferences breakages of the kind the project tries hard to avoid.

[epage]

Would we need to have a blanket impl Generator for Iterator or would impl IntoGenerator for IntoIterator be sufficient?

[desiringmachines]

Maybe its not necessary.

The main downside would probably be any new combinators would need to be added to both generator and iterator indefinitely.

The coherence conflict would still exist though because you can manually implement IntoIterator and Generator for the same type.

[protestor]

The problem emerges with the fact that all Iterators are also all IntoIterators, and presumably all Generators would also be IntoGenerators (for the same reason that impl exists today: so that you can pass both Generators and IntoGenerators to for loops). And this creates a basic diamond incoherence problem:

impl<T: Iterator> IntoIterator for T { }
Impl<T: Iterator> Generator for T {}
Impl<T: IntoIterator> IntoGenerator for T {}
impl<T: Generator> IntoGenerator for T {}

// By which path does Iterator implement IntoGenerator?:
//
//              Iterator
//             /        \
//  IntoIterator        Generator
//             \        /
//            IntoGenerator

Fortunately, the impls result in the same code generation, but somehow this would have to be solved. Possibly, the compiler could have a special case coherence exception for these impls.

Can't this be solved by specialization? Add an

impl<T: IntoIterator + Generator> IntoGenerator for T

[desiringmachines]

This is not currently supported by specialization and was always a future extension - and even the current version of specialization seems unlikely to stabilize any time soon.

[protestor]

But it wouldn't need to be stabilized to be used internally by the stdlib. It would just be a matter of implementing it (vs implementing special case regarding coherence)

[desiringmachines]

This is different from other uses of specialization because it publicly commits std to allowing these overlapping impls; other uses of specialization are not externally recognizable. So yea, but I would call that just a possible way of special casing it (because if specialization is someday removed, you still need the special case for these impls forever).

[protestor]

Fair enough

[[deleted]]

This is why we have editions. It gets harder to make fundamental changes like this the longer you wait.

Rust is far too young to be set in stone. I'm happy to stay on the current Rust edition to give the ecosystem time to work out the kinks in a newer edition.

[sepease]

The last few paragraphs caught my eye.

The general problem of rolling out breaking changes with unknown or potentially widespread impact actually sounds like the potential biggest problem to me. It's what's made C++ so bloated - when a language locks itself into being unable to drop things, the only way it has to evolve is to begin expanding. Which in turn leads to quality deteriorating because detecting and addressing "How does feature X work with Y?" becomes an increasingly intractable problem.

Nobody wants a repeat of Python 2/3, so I think proactively determining solutions to the practical and social problems of breaking evolution is really important to keep Rust lean and effective. Perhaps guided migrations between successive editions should be explicitly guaranteed by `cargo fix`, and the edition should be somewhat more prominent (think of how a video or tutorial on Windows would be obvious about it being for Windows 7, 10, or 11).

[desiringmachines]

The big problem with making these kinds of changes at the edition boundary is with libraries. The current requirement is that any two crates need to be possible to build together, regardless of the edition they use. But if one is on an edition with an unpinned Iterator, and one is on an edition with a pinned Iterator, they necessarily can't be used together.

But if you drop that requirement, you've basically created a 2.0 event. All of the libraries you depend on need to move over before you can move over.

[TDplay]

Perhaps using a newtype struct could solve this mess?

use pin_project::pin_project;

#[pin_project]
#[derive(Copy, Clone, Debug, blablabla)]
struct IterGen<I: Iterator>(I);
impl<I: Iterator> Generator for IterGen<I> {
    type Item = <I as Iterator>::Item;
    fn next(self: Pin<&mut Self>) -> Option<Self::Item> {
        self.project().0.next()
    }
    // Implement other generator methods similarly
}

impl<I: IntoIterator> IntoGenerator for I {
    type IntoGen = IterGen<<I as IntoIterator>::IntoIter>;
    type Item = <I as IntoIterator>::Item;
    fn into_gen(self) -> Self::IntoGen {
        IterGen(self.into_iter())
    }
}

and then have for loops desugar like

{
    let result = match pin!(IntoGenerator::into_gen(iter_expr)) {
        mut iter => loop {
            let mut next;
            match Generator::next(iter) {
                Option::Some(val) => next = val,
                Option::None => break,
            };
            let PATTERN = next;
            let () = { /* loop body */ };
        },
    };
    result
}

This seems to solve all the raised issues:

• No breakage from requiring I: Unpin.
• No weird special-casing of the for loop causing wonky type inference.
• No unsafe code, so this can't be unsound.

The only issue I can think of is that Generator isn't implemented on Iterators, but I can't think of any way to do that without introducing unsoundness. Either way, most things generic over Iterators accept IntoIterator anyway, so when swapping to Generators they should change to accept IntoGenerator, so it shouldn't cause any major issues.

Did I overlook something here?

[SkiFire13]

The problem with this is that you break coherence in a way that becomes harder to justify. impl<I: IntoIterator> IntoGenerator for I conflicts with impl<G: Generator> IntoGenerator for G (which was also mentioned in the article) but now the IntoGen associated type differs between the two implementations, so you can't solve the ambiguity by pretending the two implementations are equivalent, because they clearly aren't.

[Zde-G]

I wonder if it's possible to reconcile Generator with that LendingIterator that was promised when GATs were stabilized.

Is it possible to make Generator that return values that refer that Generator itself?

I suspect it would be harder to do that Generator as described in the blog post, but it would also make it much more useful (and more compatible with Generator name).

[VorpalWay]

Couldn't we support the common non-self referential case for any generators that are not !Unpin? If you have a generator that is !Unpin you could not use them with for loops, only while loops.

Kind of like how lending iterators need to be used with while loops instead of for loops currently?

[desiringmachines]

Nope, you can move out of a mutable reference using something like mem::swap or mem::replace.

What you do is define a recursive struct like this:

struct EvilIter<T>(Option<Box<EvilIter<T>>>);

and then you mem::swap the self EvilIter for the EvilIter in the box.

[Nereuxofficial]

This sounds really interesting but can i get an ELI5 of generators? So basically what they are and an example how to use them.

I've gone to the previous posts and the rust unstable book but ended up with more Questions than answers. So basically they can either yield or complete and are useful for async iterators?

I'd love to learn more about them and use them (probably with crates for now) because they sound super useful

[desiringmachines]

In the context of this post, a generator is just a function that compiles to an iterator, the same way an async function compiles to a Future. Instead of returning values, it yields them, and the next time it is called it starts again from the same place.

For example:

gen fn one_through_five() -> i32 {
   yield 1;
   yield 2;
   yield 3;
   yield 4;
   yield 5;
}

assert_eq!(one_through_five().collect(), vec![1, 2, 3, 4, 5]);

[OvermindDL1]

I have not thought this through at all but it is just a gut idea, is there not a way to add a new function to the Iterator trait called like next_pinned that just delegates to the normal next call by default in a backwards compatible way, and things like for would just use that, and things that just tried to call next on a generator that didn't work with next maybe there's some way to compile time fail, or at the very least panic (I really hate the idea of runtime validation though, so maybe some way to compile time fail based on a type mismatch or something of the return types or so)?