Everything

php

Proposal: Adding a RewindableKeyValueIterator type allowing mixed/repeated keys

php.internals

tyson andre

5 years ago

Hi internals,

Currently, there don't seem to be any internal classes that can be used to store a copy of the keys and values of an arbitrary Traversable.

- This would help in eagerly evaluating the result of a generator in a memory efficient way that could be exactly stored and reused 
  e.g. `return $this->cachedResults ??= new \RewindableKeyValueIterator($this->innerResultsGenerator());`
  https://externals.io/message/108767#108797
- This would be useful to exactly represent the keys of sequences with repeated keys (e.g. `yield 'first'; yield 'second';` implicitly uses the key `0` twice.)
- This would be convenient to have to differentiate between 1, '1', and true.
- This would be useful if php were to add internal global functions that act on iterables and return Traversables with potentially repeated keys based on those iterables,
   e.g. map(), filter(), take(), flip(), etc
- If PHP were to add more iterable methods, being able to save an immutable copy of a traversable's result would be useful for end users.
- If PHP were to add a Map (ordered hash map with null/any scalar/arrays/objects as keys) class type in the future,
  and that implemented IteratorAggregate, the return type of getIterator() would need something like RewindableKeyValueIterator.
- The lack of a relevant datatype is among the reasons why classes such as SplObjectStorage are still an Iterator instead of an IteratorAggregate. (and backwards compatibility)

```
final class KeyValueSequenceIterator implements Iterator {
    // loop over all values in $values and store a copy, converting
    // references in top-level array values to non-references
    public function __construct(iterable $values) {...}
    public static function fromKeyValuePairs(iterable $entries): self {...} // fromKeyValuePairs([[$key1, $value1]])
    public function rewind(): void {...}
    public function next(): void {...}
    public function current(): mixed {...}
    public function key(): mixed {...}
    public function valid(): bool {...}
    // and __debugInfo, __clone(), etc.
}
```

Thanks,
- Tyson

Unnamed Person

5 years ago

On Sat, Jan 30, 2021 at 5:37 PM tyson andre <tysonandre775@hotmail.com> wrote:

>
> Hi internals,
>
> Currently, there don't seem to be any internal classes that can be used to store a copy of the keys and values of an arbitrary Traversable.
>
> - This would help in eagerly evaluating the result of a generator in a memory efficient way that could be exactly stored and reused
>   e.g. `return $this->cachedResults ??= new \RewindableKeyValueIterator($this->innerResultsGenerator());`
>   https://externals.io/message/108767#108797
> - This would be useful to exactly represent the keys of sequences with repeated keys (e.g. `yield 'first'; yield 'second';` implicitly uses the key `0` twice.)
> - This would be convenient to have to differentiate between 1, '1', and true.
> - This would be useful if php were to add internal global functions that act on iterables and return Traversables with potentially repeated keys based on those iterables,
>    e.g. map(), filter(), take(), flip(), etc
> - If PHP were to add more iterable methods, being able to save an immutable copy of a traversable's result would be useful for end users.
> - If PHP were to add a Map (ordered hash map with null/any scalar/arrays/objects as keys) class type in the future,
>   and that implemented IteratorAggregate, the return type of getIterator() would need something like RewindableKeyValueIterator.
> - The lack of a relevant datatype is among the reasons why classes such as SplObjectStorage are still an Iterator instead of an IteratorAggregate. (and backwards compatibility)
>
> ```
> final class KeyValueSequenceIterator implements Iterator {
>     // loop over all values in $values and store a copy, converting
>     // references in top-level array values to non-references
>     public function __construct(iterable $values) {...}
>     public static function fromKeyValuePairs(iterable $entries): self {...} // fromKeyValuePairs([[$key1, $value1]])
>     public function rewind(): void {...}
>     public function next(): void {...}
>     public function current(): mixed {...}
>     public function key(): mixed {...}
>     public function valid(): bool {...}
>     // and __debugInfo, __clone(), etc.
> }
> ```
>
> Thanks,
> - Tyson
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: https://www.php.net/unsub.php
>

The names `RewindableKeyValueIterator` and `KeyValueSequenceIterator`
are just long-form descriptions of the Iterator API. I don't think we
need such long names. The name should focus on what it brings.

What it brings is a caching iterator around another iterator, that
includes re-windability. The SPL provides a `CachingIterator`, but I
assume it is inadequate somehow (it is basically SPL tradition). Can
you specifically discuss the shortcomings of `CachingIterator` and how
you will address them? To that end, have you implemented a
proof-of-concept for the proposed iterator?

tyson andre

5 years ago

Hi Levi Morrison,

> > Currently, there don't seem to be any internal classes that can be used to store a copy of the keys and values of an arbitrary Traversable.
> >
> > - This would help in eagerly evaluating the result of a generator in a memory efficient way that could be exactly stored and reused
> >   e.g. `return $this->cachedResults ??= new \RewindableKeyValueIterator($this->innerResultsGenerator());`
> >   https://externals.io/message/108767#108797
> > - This would be useful to exactly represent the keys of sequences with repeated keys (e.g. `yield 'first'; yield 'second';` implicitly uses the key `0` twice.)
> > - This would be convenient to have to differentiate between 1, '1', and true.
> > - This would be useful if php were to add internal global functions that act on iterables and return Traversables with potentially repeated keys based on those iterables,
> >    e.g. map(), filter(), take(), flip(), etc
> > - If PHP were to add more iterable methods, being able to save an immutable copy of a traversable's result would be useful for end users.
> > - If PHP were to add a Map (ordered hash map with null/any scalar/arrays/objects as keys) class type in the future,
> >   and that implemented IteratorAggregate, the return type of getIterator() would need something like RewindableKeyValueIterator.
> > - The lack of a relevant datatype is among the reasons why classes such as SplObjectStorage are still an Iterator instead of an IteratorAggregate. (and backwards compatibility)
> >
> > ```
> > final class KeyValueSequenceIterator implements Iterator {
> >     // loop over all values in $values and store a copy, converting
> >     // references in top-level array values to non-references
> >     public function __construct(iterable $values) {...}
> >     public static function fromKeyValuePairs(iterable $entries): self {...} // fromKeyValuePairs([[$key1, $value1]])
> >     public function rewind(): void {...}
> >     public function next(): void {...}
> >     public function current(): mixed {...}
> >     public function key(): mixed {...}
> >     public function valid(): bool {...}
> >     // and __debugInfo, __clone(), etc.
> > }
> > ```
>
> The names `RewindableKeyValueIterator` and `KeyValueSequenceIterator`
> are just long-form descriptions of the Iterator API. I don't think we
> need such long names. The name should focus on what it brings.
>
> What it brings is a caching iterator around another iterator, that
> includes re-windability. The SPL provides a `CachingIterator`, but I
> assume it is inadequate somehow (it is basically SPL tradition). Can
> you specifically discuss the shortcomings of `CachingIterator` and how
> you will address them? To that end, have you implemented a
> proof-of-concept for the proposed iterator?

It caches the results by coercing keys and inserting them into an array, which is a different use case.
If you rewind a CachingIterator, it rewinds the iterator that it wraps,
which throws for Generators and other types of iterators.

For RewindableKeyValueIterator, it needs to store keys that can't be used as array keys.

I was planning to implement a proof of concept if there wasn't widespread opposition
and if nobody pointed out the functionality already existed.

```
<?php
function dump_iterable(iterable $x) {
    foreach ($x as $key => $value) {
        printf("Key: %s\nValue: %s\n", json_encode($key), json_encode($value));
    }
}
function yields_values(): Generator { yield 0 => 'first'; yield '0' => 'second'; }
$c = new CachingIterator(yields_values(), CachingIterator::FULL_CACHE);
echo "First CachingIterator iteration\n";
dump_iterable($c);
var_export($c->getCache()); echo "\n"; // array(0 => 'second') does not represent that data
echo "Second CachingIterator iteration\n";
// Fatal error: Uncaught Exception: Cannot rewind a generator that was already run
dump_iterable($c);
```

Thanks,
- Tyson

tyson andre

5 years ago

Hi Levi Morrison,

> > > Currently, there don't seem to be any internal classes that can be used to store a copy of the keys and values of an arbitrary Traversable.
> > >
> > > - This would help in eagerly evaluating the result of a generator in a memory efficient way that could be exactly stored and reused
> > >   e.g. `return $this->cachedResults ??= new \RewindableKeyValueIterator($this->innerResultsGenerator());`
> > >   https://externals.io/message/108767#108797
> > > - This would be useful to exactly represent the keys of sequences with repeated keys (e.g. `yield 'first'; yield 'second';` implicitly uses the key `0` twice.)
> > > - This would be convenient to have to differentiate between 1, '1', and true.
> > > - This would be useful if php were to add internal global functions that act on iterables and return Traversables with potentially repeated keys based on those iterables,
> > >    e.g. map(), filter(), take(), flip(), etc
> > > - If PHP were to add more iterable methods, being able to save an immutable copy of a traversable's result would be useful for end users.
> > > - If PHP were to add a Map (ordered hash map with null/any scalar/arrays/objects as keys) class type in the future,
> > >   and that implemented IteratorAggregate, the return type of getIterator() would need something like RewindableKeyValueIterator.
> > > - The lack of a relevant datatype is among the reasons why classes such as SplObjectStorage are still an Iterator instead of an IteratorAggregate. (and backwards compatibility)
> > >
> > > ```
> > > final class KeyValueSequenceIterator implements Iterator {
> > >     // loop over all values in $values and store a copy, converting
> > >     // references in top-level array values to non-references
> > >     public function __construct(iterable $values) {...}
> > >     public static function fromKeyValuePairs(iterable $entries): self {...} // fromKeyValuePairs([[$key1, $value1]])
> > >     public function rewind(): void {...}
> > >     public function next(): void {...}
> > >     public function current(): mixed {...}
> > >     public function key(): mixed {...}
> > >     public function valid(): bool {...}
> > >     // and __debugInfo, __clone(), etc.
> > > }
> > > ```
> >
> > The names `RewindableKeyValueIterator` and `KeyValueSequenceIterator`
> > are just long-form descriptions of the Iterator API. I don't think we
> > need such long names. The name should focus on what it brings.
> >
> > What it brings is a caching iterator around another iterator, that
> > includes re-windability. The SPL provides a `CachingIterator`, but I
> > assume it is inadequate somehow (it is basically SPL tradition). Can
> > you specifically discuss the shortcomings of `CachingIterator` and how
> > you will address them? To that end, have you implemented a
> > proof-of-concept for the proposed iterator?
> 
> It caches the results by coercing keys and inserting them into an array, which is a different use case.
> If you rewind a CachingIterator, it rewinds the iterator that it wraps,
> which throws for Generators and other types of iterators.
> 
> For RewindableKeyValueIterator, it needs to store keys that can't be used as array keys.
> 
> I was planning to implement a proof of concept if there wasn't widespread opposition
> and if nobody pointed out the functionality already existed.
> 
> ```
> <?php
> function dump_iterable(iterable $x) {
>     foreach ($x as $key => $value) {
>         printf("Key: %s\nValue: %s\n", json_encode($key), json_encode($value));
>     }
> }
> function yields_values(): Generator { yield 0 => 'first'; yield '0' => 'second'; }
> $c = new CachingIterator(yields_values(), CachingIterator::FULL_CACHE);
> echo "First CachingIterator iteration\n";
> dump_iterable($c);
> var_export($c->getCache()); echo "\n"; // array(0 => 'second') does not represent that data
> echo "Second CachingIterator iteration\n";
> // Fatal error: Uncaught Exception: Cannot rewind a generator that was already run
> dump_iterable($c);
> ```

A proof of concept is available at https://github.com/php/php-src/pull/6655

The implementation is similar to SplFixedArray, but instead of an array of `n` zvals,
it's an array of `n` pairs of zvals for keys and values.

It's an `Iterator` because IteratorAggregator->getIterator() must eventually return an Iterator,
but I'm consider also proposing an IteratorAggregate such as KeyValueSequence 
that can share the same immutable storage (or copy it).

For example, `someprefix_map(iterable, callable $mapper): KeyValueSequence` could be useful internally to handle
Traversables that could be repeated or use non-scalar keys.

Thanks,
- Tyson

tyson andre

5 years ago

Hi internals,

> Currently, there don't seem to be any internal classes that can be used to store a copy of the keys and values of an arbitrary Traversable.
> 
> - This would help in eagerly evaluating the result of a generator in a memory efficient way that could be exactly stored and reused 
>   e.g. `return $this->cachedResults ??= new \RewindableKeyValueIterator($this->innerResultsGenerator());`
>   https://externals.io/message/108767#108797
> - This would be useful to exactly represent the keys of sequences with repeated keys (e.g. `yield 'first'; yield 'second';` implicitly uses the key `0` twice.)
> - This would be convenient to have to differentiate between 1, '1', and true.
> - This would be useful if php were to add internal global functions that act on iterables and return Traversables with potentially repeated keys based on those iterables,
>    e.g. map(), filter(), take(), flip(), etc
> - If PHP were to add more iterable methods, being able to save an immutable copy of a traversable's result would be useful for end users.
> - If PHP were to add a Map (ordered hash map with null/any scalar/arrays/objects as keys) class type in the future,
>   and that implemented IteratorAggregate, the return type of getIterator() would need something like RewindableKeyValueIterator.
> - The lack of a relevant datatype is among the reasons why classes such as SplObjectStorage are still an Iterator instead of an IteratorAggregate. (and backwards compatibility)
> 
> ```
> final class KeyValueSequenceIterator implements Iterator {
>     // loop over all values in $values and store a copy, converting
>     // references in top-level array values to non-references
>     public function __construct(iterable $values) {...}
>     public static function fromKeyValuePairs(iterable $entries): self {...} // fromKeyValuePairs([[$key1, $value1]])
>     public function rewind(): void {...}
>     public function next(): void {...}
>     public function current(): mixed {...}
>     public function key(): mixed {...}
>     public function valid(): bool {...}
>     // and __debugInfo, __clone(), etc.
> }
> ```

This has been updated - the preferred name is CachedIterable.
It turns out InternalIterator is generally more efficient, 
and SplFixedArray is already using that.
The implementation is pretty much done - https://github.com/php/php-src/pull/6655

```
/**
 * Internal class that can be used to eagerly evaluate and store a copy
 * of the keys and values of an arbitrary Traversable.
 * Keys can be any type, and keys can be repeated.
 */
final class CachedIterable implements IteratorAggregate, Countable
{
    public function __construct(iterable $iterator) {}
    public function getIterator(): InternalIterator {}
    public function count(): int {}
    public static function fromPairs(array $pairs): CachedIterable;

    public function __serialize(): array {}  // [$k1, $v1, $k2, $v2,...]
    public function __unserialize(array $data): void {}

    // useful for converting iterables back to values
    public function keys(): array {}
    public function values(): array {}
    // useful to efficiently get offsets at the middle/end of a long iterable.
    public function keyAt(int $offset): mixed {}
    public function valueAt(int $offset): mixed {}
    // dynamic properties are forbidden
}
```

Any other comments?

Thanks,
- Tyson