Support rewinding of generators

php.internals

Nikita Popov

6 years ago
Hi internals, Generators currently do not support rewinding -- or rather, only support it if the generator is at/before the first yield, in which case rewinding is a no-op. Generators make it real breeze to implement primitives like function map(callable $function, iterable $iterable): \Iterator { foreach ($iterable as $key => $value) { yield $key => $function($value); } } without having to do through the whole Iterator boilerplate. However, if you do this, you end up with an iterator that is not rewindable. If you want to make map() rewindable, you need to go back to a manual Iterator implementation. As iterators in PHP are assumed to be rewindable by default, this is somewhat annoying. There is a relatively simple (at least conceptually) way to make generators rewindable: Remember the original arguments of the function, and basically "re-invoke" it on rewind(). I'm wondering what people think about adding this functionality. I think the main argument against it is that not all generators may behave sensibly if you re-run their code -- there's probably a reasonable expectation that an iterator will return the same sequence of values are rewinding, something which we cannot guarantee with generators, but also don't enforce with normal iterators either. Regards, Nikita

Judah Wright

6 years ago
Perhaps an easy userland implementation could be type-hinting a new generator type, to indicate that the generator should be rewindable by simply re-calling the function? // Safe to rewind function fooRange(int $from, int $to): RewindableGenerator { for ($i = $from; $i <= $to; $i++) { yield $i; } } That should be safe to re-call again, but my concern is with generators that modify some external state that should not be called twice. In these cases having a fatal error is a handy feature to prevent re-iterating over things that might cause issues. ~Judah On Wed, Feb 26, 2020 at 12:47 pm, Nikita Popov <nikita.ppv@gmail.com> wrote:

Rowan Collins

6 years ago
Hi Nikita, On 26 February 2020 11:47:14 GMT+00:00, Nikita Popov <nikita.ppv@gmail.com> wrote:
>There is a relatively simple (at least conceptually) way to make generators >rewindable: Remember the original arguments of the function, and basically >"re-invoke" it on rewind().
This is an interesting idea. There is a gotcha though, neatly demonstrated by your example:
>function map(callable $function, iterable $iterable): \Iterator { > foreach ($iterable as $key => $value) { > yield $key => $function($value); > } >}
If the $iterable passed in is anything other than an array, re-invoking the function won't actually rewind it. That can be fixed by explicitly rewinding at the start: function map(callable $function, iterable $iterable): \Iterator { reset($iterable); foreach ($iterable as $key => $value) { yield $key => $function($value); } } But now we have a different problem: if we pass an iterator that doesn't support rewinding, we'll get an error immediately. In other cases, the side-effects of running the "constructor" itself might be undesirable. For instance, it might re-run an SQL query, rather than rewinding a cursor: public function getResultsIterator($sql) { $cursor = $this->runQuery($sql); foreach ( $cursor->getNext() as $row ) { yield $this->formatRow($row); } } I think the fix would be to return a generator rather than yielding directly, like this: public function getResultsIterator($sql) { $generator = function($cursor) { $cursor->rewind(); foreach ( $cursor->getNext() as $row ) { yield $this->formatRow($row); } }; $cursor = $this->runQuery($sql); return $generator($cursor); } In general, it feels like it would be useful for generators that knew it was going to happen, but a foot-gun for generators that weren't expecting it, so I like Judah's suggestion of an opt-in mechanism of some sort. Regards,
-- Rowan Tommins [IMSoP]

Nikita Popov

6 years ago
On Wed, Feb 26, 2020 at 4:03 PM Rowan Tommins <rowan.collins@gmail.com> wrote:
> Hi Nikita, > > On 26 February 2020 11:47:14 GMT+00:00, Nikita Popov > <nikita.ppv@gmail.com> wrote: > >There is a relatively simple (at least conceptually) way to make > generators > >rewindable: Remember the original arguments of the function, and basically > >"re-invoke" it on rewind(). > > This is an interesting idea. > > There is a gotcha though, neatly demonstrated by your example: > > >function map(callable $function, iterable $iterable): \Iterator { > > foreach ($iterable as $key => $value) { > > yield $key => $function($value); > > } > >} > > If the $iterable passed in is anything other than an array, > re-invoking the function won't actually rewind it.
Point of order: foreach() always rewinds the array / Iterator it gets. The code does work correctly under the proposed scheme. Nikita

Rowan Collins

6 years ago
On Wed, 26 Feb 2020 at 15:23, Nikita Popov <nikita.ppv@gmail.com> wrote:
> Point of order: foreach() always rewinds the array / Iterator it gets. The > code does work correctly under the proposed scheme. >
Ah, I'd missed that, sorry; that makes the entire first half of my e-mail irrelevant. :) The proposed behaviour is actually closer to current behaviour than I thought, because the initial code before the first yield actually runs when you first rewind the iterator: function foo() { echo 'Begin'; yield 42; } $f = foo(); // Doesn't echo yet $f->rewind(); // Now echoes 'Begin' $f2 = foo(); foreach ( $f2 as $x ) { // echoes 'Begin' before first loop echo $x; } Just to check, would the proposed behaviour still special-case a generator which hasn't been progressed? $f = foo(); $f->rewind(); // echoes 'Begin' $f->rewind(); // this would still do nothing? $f->next(); $f->rewind(); // this currently throws an error, and would echo 'Begin' again? Regards,
-- Rowan Tommins [IMSoP]

Unnamed Person

6 years ago
On Wed, Feb 26, 2020 at 4:47 AM Nikita Popov <nikita.ppv@gmail.com> wrote:
> > Hi internals, > > Generators currently do not support rewinding -- or rather, only support it > if the generator is at/before the first yield, in which case rewinding is a > no-op. > > Generators make it real breeze to implement primitives like > > function map(callable $function, iterable $iterable): \Iterator { > foreach ($iterable as $key => $value) { > yield $key => $function($value); > } > } > > without having to do through the whole Iterator boilerplate. However, if > you do this, you end up with an iterator that is not rewindable. If you > want to make map() rewindable, you need to go back to a manual Iterator > implementation. As iterators in PHP are assumed to be rewindable by > default, this is somewhat annoying. > > There is a relatively simple (at least conceptually) way to make generators > rewindable: Remember the original arguments of the function, and basically > "re-invoke" it on rewind(). > > I'm wondering what people think about adding this functionality. I think > the main argument against it is that not all generators may behave sensibly > if you re-run their code -- there's probably a reasonable expectation that > an iterator will return the same sequence of values are rewinding, > something which we cannot guarantee with generators, but also don't enforce > with normal iterators either. > > Regards, > Nikita
Making generators "rewindable but don't really know if it's going to work" is worse than "not rewindable," in my opinion. It is true that it isn't very different from other iterators; you aren't going to know if it's going to work. At risk of hijacking the thread: can we extend the ability to always rewind an iterator as long as it has not been progressed to _all_ iterators? It's not something I've seen discussed much, but it actually has a really important characteristic: you can find out if the iterator will yield at least 1 value (aka it's not empty) if the iterator has this characteristic. Generators have this characteristic but there are iterators in core that don't do this, and I'm sure there are userland iterators that also don't do this. I'm wondering if we can somehow force it to occur so nobody has to actually code that semantic into every iterator. To me that would be even more valuable than making generators semi-rewindable.

Stas Malyshev

6 years ago
Hi!
> There is a relatively simple (at least conceptually) way to make generators > rewindable: Remember the original arguments of the function, and basically > "re-invoke" it on rewind().
That is provided that: 1. The original arguments of the function can be "remembered" - those can be complex object with a lot of state, not always visible to PHP, preserving which may be impossible. 2. The generator function is pure and does not have side effects - or at least side effects of rewinding are expected and desirable. It also means that we'd have to always preserve the arguments of the generator function in the state they were when it was called or at least try to - not sure what performance impact this implies. That or explicitly declare the generator rewindable with the implication that once we declare that we shouldn't pass any arguments to it that can't be or shouldn't be preserved.
-- Stas Malyshev smalyshev@gmail.com

Andrew Faulds

6 years ago
Hi, Nikita Popov wrote:
> There is a relatively simple (at least conceptually) way to make generators > rewindable: Remember the original arguments of the function, and basically > "re-invoke" it on rewind(). > > I'm wondering what people think about adding this functionality. I think > the main argument against it is that not all generators may behave sensibly > if you re-run their code -- there's probably a reasonable expectation that > an iterator will return the same sequence of values are rewinding, > something which we cannot guarantee with generators, but also don't enforce > with normal iterators either.
I am not sure if I think this is a good idea… for one thing it may not be necessary to add support in core for this, because you could easily write a userland Iterator class that wraps a generator-returning closure and (re-)invokes it for you. If you do it yourself that way, it's clear what's actually happening behind the scenes at least. If it must be done, perhaps the code must explicitly opt-in to being rewindable somehow? That would avoid problems with rewinding generators which aren't designed for it. Thanks, Andrea

Andrew Faulds

6 years ago
Hi again, Andrea Faulds wrote:
> I am not sure if I think this is a good idea… for one thing it may not > be necessary to add support in core for this, because you could easily > write a userland Iterator class that wraps a generator-returning closure > and (re-)invokes it for you. If you do it yourself that way, it's clear > what's actually happening behind the scenes at least. > > If it must be done, perhaps the code must explicitly opt-in to being > rewindable somehow? That would avoid problems with rewinding generators > which aren't designed for it.
Now that I think about it, such a wrapper class could be part of the PHP standard library. Spl already provides InfiniteIterator and NoRewindIterator, so an InfiniteGenerator class would feel right at home, I think! Thanks, Andrea