# Adding `final class Deque` to PHP

- Thread: https://externals.io/message/116100
- Original archive: https://news-web.php.net/php.internals/116100
- Started by tyson andre on 2021-09-20T00:03:33+00:00
- Messages: 35
- RFC: final class Deque (Inactive) — https://externals.io/rfc/deque.md
- Page 1 of 2: messages 1 to 25 (25 per page, add `?page=N` to the URL)
- Next page: https://externals.io/message/116100.md?page=2
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · RFCs at https://externals.io/rfc.md · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #116100 — tyson andre — 2021-09-20T00:03:33+00:00

URL: https://externals.io/message/116100#116100

Hi internals,

I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class Deque`

This is based on the `Teds\Deque` implementation I've worked on
for the https://github.com/TysonAndre/pecl-teds PECL.

While `SplDoublyLinkedList` and its subclass `SplQueue`/`SplStack` exist in the SPL, they have several drawbacks
that are addressed by this RFC to add a `Deque` class (to use instead of those):

1. `SplDoublyLinkedList` is internally represented by a doubly linked list,
   making it use roughly twice as much memory as the proposed `Deque`
2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower due to
   needing to allocate or free the linked list nodes.
3. Reading values in the middle of the `SplDoublyLinkedList` is proportional to the length of the list,
   due to needing to traverse the linked list nodes.
4. `foreach` Iteration behavior cannot be understood without knowing what constructed the
   `SplDoublyLinkedList` instance or set the flags.

It would be useful to have an efficient `Deque` container in the standard library
to provide an alternative without those drawbacks,
as well as for the following reasons:

1. To save memory in applications or libraries that may need to store many lists of values or run for long periods of time.
   Notably, PHP's `array` type will never release allocated capacity.
   See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html
2. To provide a better alternative to `SplDoublyLinkedList`, `SplStack`, and `SplQueue`
   for use cases that require stacks or queues.
3. As a more efficient option than `array` and `SplDoublyLinkedList`
   as a queue or `Deque`, especially for `unshift`.

A `Deque` is more efficient than an `array` when used as a queue, more readable, and easier to use correctly.
While it is possible to efficiently remove elements from the start of an `array` (in terms of insertion order),
it is very inefficient to prepend elements to the start of a large `array` due to needing to either copy the array
or move all elements in the internal array representation,
and an `array` would use much more memory than a `Deque` when used that way (and be slower).

There are also several pitfalls to using an array as a queue for larger queue sizes,
some of which are not obvious and discovered while writing the benchmarks.
(Having a better (double-ended) queue datastructure (`Deque`) than the `SplDoublyLinkedList`
would save users from needing to write code with these pitfalls):

1. `array_key_first()` takes time proportional to the number of elements `unset` from the start of an array,
   causing it to unexpectedly be extremely slow (quadratic time) after unsetting many elements at the start of the queue.
   (when the array infrequently runs out of capacity, buckets are moved to the front)
2. `reset()` or `end()` will convert a variable to a reference,
   and php is significantly less efficient at reading or writing to reference.
   Opcache is also less efficient at optimizing uses of variables using references.
3. More obviously, `array_unshift` and `array_shift` will take time proportional to the number of elements in the array
   (to reindex and move existing/remaining elements).

After the discussion period ends, I currently plan to start voting on the `Deque` RFC and await the results
to determine next steps for the `Vector` RFC.

----

The thread for my other open proposal `final class Vector` (https://externals.io/message/116048) has prior discussion on implementation choices,
naming choices, and motivation for adding datastructures to php-src.

- E.g. the question of why we should add general-purpose datastructures
  to php-src itself rather than have users rely on PECLs,
  and why this proposal doesn't and can't use `php-ds`/`ext-ds`.

Thanks,
Tyson

---

## #116101 — Pierre — 2021-09-20T08:36:09+00:00

URL: https://externals.io/message/116100#116101 · In reply to: #116100

Le 20/09/2021 à 02:03, tyson andre a écrit :
> Hi internals,
>
> I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class Deque`

Hello,

It seems that you are writing more than one RFC to add many data 
structures. I love that you're doing that, but I suggest that you'd 
normalize them all and place all new classes in a single new dedicated 
namespace.

Regards,

--

Pierre

---

## #116104 — Christian Schneider — 2021-09-20T08:59:48+00:00

URL: https://externals.io/message/116100#116104 · In reply to: #116101

Am 20.09.2021 um 10:36 schrieb Pierre <pierre-php@processus.org>:
> Le 20/09/2021 à 02:03, tyson andre a écrit :
> > […]
> 
> It seems that you are writing more than one RFC to add many data structures. I love that you're doing that, but I suggest that you'd normalize them all and place all new classes in a single new dedicated namespace.

+1

- Chris

---

## #116108 — tyson andre — 2021-09-20T13:46:34+00:00

URL: https://externals.io/message/116100#116108 · In reply to: #116101

Hi Pierre,

> It seems that you are writing more than one RFC to add many data 
> structures. I love that you're doing that, but I suggest that you'd 
> normalize them all

I'm not certain what you mean by "normalize".
https://www.merriam-webster.com/dictionary/normalize mentions

1. "to make conform to or reduce to a norm or standard"
2. https://www.freetext.org/Introduction_to_Linear_Algebra/Basic_Vector_Operations/Normalization/
   (no pun intended)
3. "to bring or restore to a normal condition"

If you mean to make Vector and Queue's APIs consistent with each other,
I plan to make changes to Vector (e.g. remove $preserveKeys, add isEmpty), but the Vector RFC is currently on hold.

If you also mean all datastructure RFCs should be combined into a single RFC,
I'd considered combining the Vector RFC with https://wiki.php.net/rfc/deque,
but decided against combining the RFCs in this instance, because of:

1. Current discussion about whether or not to choose an alternate name for a `Vector`
2. The fact that `Deque` has much better performance for various queue workloads
   on both time and memory usage than `array`
   (and significantly better performance than `SplDoublyLinkedList`).

Still, I may consider the approach for future RFCs, given that

1. Many developers in internals have expressed a desire for having a significantly 
   larger data structure library in core along the lines of what php-ds provides,
   but may be uninterested in some of the individual datastructures or design choices.

   E.g. if 60% of developers were in favor of a sorted set and its proposed API/name 
   (along the lines of https://cplusplus.com/reference/set/set/),
   60% were in favor of an immutable sequence and its proposed API/name (of values) (similar to https://docs.python.org/3/tutorial/datastructures.html#tuples-and-sequences),
   then with the 2/3 voting threshold,
   neither of those RFCs would pass but a proposal combining those two would pass,
   despite ~95% of developers wanting some type of improved datastructures added to core in general (I would guess).
2. This would allow seeing how datastructures compare to each other.

Combining RFCs has the drawback of significantly increasing the implementation, discussion, review,
delays, and time involvement for the volunteer RFC authors and voters,
and may lead to a larger number of last-minute concerns raised after voting has started when more time 
is spent trying out the new code and looking at the RFC.

> and place all new classes in a single new dedicated 
> namespace.

My rationale for deciding against a dedicated namespace is in https://wiki.php.net/rfc/deque#global_namespace
which I've recently expanded on.

The `Deque` proposal is normalized with respect to the namespace choice of data structures that already exist.

The choice of global namespace maintains consistency with the namespace used for general-purpose collections already in the SPL 
(as well as relatively recent additions such as ''WeakReference'' (PHP 7.4) and ''WeakMap'' (PHP 8.0)).
Other recent additions to PHP such as ''ReflectionIntersectionType'' in PHP 8.1 have 
also continued to use the global namespace when adding classes with functionality related to other classes.

Additionally, prior polls for namespacing choices of other datastructure functionality showed preferences 
for namespacing and not namespacing were evenly split in a straw poll for a new iterable type
(https://wiki.php.net/rfc/cachediterable_straw_poll#namespace_choices)

Introducing a new namespace for data structures would also raise the question of whether existing datastructures 
should be moved to that new namespace (for consistency), and that process would:

1. Raise the amount of work needed for end users or library/framework/application authors to migrate to new PHP versions.
2. Cause confusion and inconvenience for years about which namespace can or should be used in an application 
   (''SplObjectStorage'' vs ''Xyz\SplObjectStorage''), especially for developers working on projects supporting different php version ranges.
3. Prevent applications/libraries from easily supporting as wide of a range of php versions as they otherwise could.
4. Cause serialization/unserialization issues when migrating to different php versions,
   if the old or new class name in the serialized data did not exist in the other php version and was not aliased.
   For example, if the older PHP version could not ''unserialize()'' ''Xyz\SplObjectStorage'' 
   and would silently create a `__PHP_Incomplete_Class_Name` 
   (see https://www.php.net/manual/en/language.oop5.serialization.php#language.oop5.serialization)
   without any warnings or notices.

Thanks,
Tyson

---

## #116110 — Pierre — 2021-09-20T15:41:27+00:00

URL: https://externals.io/message/116100#116110 · In reply to: #116108

Le 20/09/2021 à 15:46, tyson andre a écrit :
> Hi Pierre,
> I'm not certain what you mean by "normalize".
> https://www.merriam-webster.com/dictionary/normalize mentions

At least please try to make it serious, I think you understood what I 
meant. I'm in no place in arguing about technical details about how it 
should be implemented because the C language is not a place where I 
shine and I trust people like you for doing it best.

Nevertheless, my only point was, please put all data structures 
altogether, and please, just don't throw them in global namespace. 
Otherwise, as we said in french "ça va être un sacré bordel là dedans" 
(actually, it already is "un sacré bordel").

I'll let someone better in english than me translate, I'm not a native 
english speaker I could get it wrong.

> If you also mean all datastructure RFCs should be combined into a single RFC,
> I'd considered combining the Vector RFC with https://wiki.php.net/rfc/deque,
> but decided against combining the RFCs in this instance, because of:

No, not necessarily, they don't need to be in the same RFC, having one 
per data structure is probably the way to go you'll maximize chances 
that each one pass vote. Nevertheless, many RFC's exist and if there's 
many other to come, no matter in which order they'll happen and no 
matter at which pace, they still can be seen as a "whole", and a 
namespace is a in my opinion still a good idea.

I won't debate on the rest, because you are much more both involved and 
technically competent than I am, and as being someone stupid, I need 
things to be well-organized to find them easily, that's the only 
constructive argument I have to bring to this discussion.

Regards,

--

Pierre

---

## #116111 — Rowan Tommins — 2021-09-20T20:25:01+00:00

URL: https://externals.io/message/116100#116111 · In reply to: #116108

> The choice of global namespace maintains consistency with the namespace used for general-purpose collections already in the SPL


I find this argument unconvincing. If the intention is for this to fit 
with existing classes in the SPL, it should be called "SplDeque", or 
more consistently "SplDoubleEndedQueue", and the RFC should talk about 
how the design aligns with those existing classes.

If it is intended to be the first of a new set of data structures which 
are *not* aligned with the existing SPL types, then putting it in a new 
namespace would make most sense.

In the RFC and the list you've mentioned a few comparisons, but I don't 
think any of them hold:

* ArrayObject, WeakReference, and WeakMap are all classes for binding to 
specific engine behaviour, not generic data structures
* Iterators all have an "Iterator" suffix (leading to some quite awkward 
names)
* Reflection classes all have a "Reflection" prefix
* Having both "Queue" and "SplQueue", or both "Stack" and "SplStack" 
would be a terrible idea, and is a pretty strong argument *not* to add 
data structures with such plain names


Regards,

-- 
Rowan Tommins
[IMSoP]

---

## #116113 — Mike Schinkel — 2021-09-21T04:21:12+00:00

URL: https://externals.io/message/116100#116113 · In reply to: #116100

> 
> 
> Hi internals,
> 
> I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class Deque`
> 
> This is based on the `Teds\Deque` implementation I've worked on
> for the https://github.com/TysonAndre/pecl-teds PECL.

With one caveat, this is a much stronger RFC than the Vector one.  Good job!

However...

> 
> 
> 
> > […]
> 
> I find this argument unconvincing. If the intention is for this to fit with existing classes in the SPL, it should be called "SplDeque", or more consistently "SplDoubleEndedQueue", and the RFC should talk about how the design aligns with those existing classes.
> 
> If it is intended to be the first of a new set of data structures which are *not* aligned with the existing SPL types, then putting it in a new namespace would make most sense.
> 
> In the RFC and the list you've mentioned a few comparisons, but I don't think any of them hold:
> 
> * ArrayObject, WeakReference, and WeakMap are all classes for binding to specific engine behaviour, not generic data structures
> * Iterators all have an "Iterator" suffix (leading to some quite awkward names)
> * Reflection classes all have a "Reflection" prefix
> * Having both "Queue" and "SplQueue", or both "Stack" and "SplStack" would be a terrible idea, and is a pretty strong argument *not* to add data structures with such plain names

I am in complete agreement with Rowan.  

Honestly, at first I confused `Deque` with `Dequeue` and was wondering why we would name a class with a verb?  It wasn't until Rowan's comment that I realized `Deque` is an abbreviation.  

Which begs the question: how many other PHP developers will know computer science terms like this well enough to know `Deque` is a noun when they see it, and more importantly how many PHP developers will think to search for `Deque` when they need a queue?

So here is a straw man argument; name the class one of:

- DataStruct\DoubleEndedQueue, or
- DataStruct\DE_Queue

Let the bike-shedding begin! 

(Or is that "Let it continue?")

-Mike

P.S. BTW re: https://github.com/TysonAndre/pecl-teds <https://github.com/TysonAndre/pecl-teds>, who is Ted? (pun intended)

---

## #116114 — Pierre Joye — 2021-09-21T07:45:44+00:00

URL: https://externals.io/message/116100#116114 · In reply to: #116113

> Honestly, at first I confused `Deque` with `Dequeue` and was wondering why we would name a class with a verb?  It wasn't until Rowan's comment that I realized `Deque` is an abbreviation.
>
> Which begs the question: how many other PHP developers will know computer science terms like this well enough to know `Deque` is a noun when they see it, and more importantly how many PHP developers will think to search for `Deque` when they need a queue?

Unlike the Vector name which is really confusing as it is not a
vector, Deque is actually relatively known for anyone needing a double
ended queue. It even comes first in google search, wikipedia or java
implementations, which matches this implementation. We expect our
users to know all weird names of different patterns, I trust them to
be able to learn what a Deque is. :)

best,
-- 
Pierre

@pierrejoye | http://www.libgd.org

---

## #116115 — Mike Schinkel — 2021-09-21T16:56:43+00:00

URL: https://externals.io/message/116100#116115 · In reply to: #116114

> 
> 
> 
> 
> > […]
> 
> Unlike the Vector name which is really confusing as it is not a
> vector, Deque is actually relatively known for anyone needing a double
> ended queue. It even comes first in google search, wikipedia or java
> implementations, which matches this implementation.

Being able to google what Deque means is one thing, but thinking to search for it when you don't know it exists *and* you don't know that Deque is the term you would need to be searching for.

> We expect our
> users to know all weird names of different patterns, I trust them to
> be able to learn what a Deque is. :)

So we expect PHP developers to have a computer science background? Maybe you are assuming everyone minimally has your expertise?  Have we as a group decided to forsake beginners?  

-Mike

---

## #116116 — Pierre Joye — 2021-09-21T17:12:14+00:00

URL: https://externals.io/message/116100#116116 · In reply to: #116115

> > […]
> wrote:
> > […]
> why we would name a class with a verb?  It wasn't until Rowan's comment
> that I realized `Deque` is an abbreviation.
> > […]
> computer science terms like this well enough to know `Deque` is a noun when
> they see it, and more importantly how many PHP developers will think to
> search for `Deque` when they need a queue?
> > […]
>
> Being able to google what Deque means is one thing, but thinking to search
> for it when you don't know it exists *and* you don't know that Deque is the
> term you would need to be searching for.
>
> > […]
>
> So we expect PHP developers to have a computer science background? Maybe
> you are assuming everyone minimally has your expertise?  Have we as a group
> decided to forsake beginners?



It is not what I was trying to explain.

However if one looks at the php documentation looking for specific things
like these, the Deque will be there.

So I am not expecting anyone to have a CS background (btw, I don't),
however I do have a minimal trust in users reading the docs and doing a
minimum of research.

best,

---

## #116118 — Mike Schinkel — 2021-09-21T19:28:05+00:00

URL: https://externals.io/message/116100#116118 · In reply to: #116116

> 
> 
> > […]
> 
> Being able to google what Deque means is one thing, but thinking to search for it when you don't know it exists *and* you don't know that Deque is the term you would need to be searching for.
> 
> > […]
> 
> So we expect PHP developers to have a computer science background? Maybe you are assuming everyone minimally has your expertise?  Have we as a group decided to forsake beginners? 
> 
> 
> It is not what I was trying to explain.
> 
> However if one looks at the php documentation looking for specific things like these, the Deque will be there. 
> 
> So I am not expecting anyone to have a CS background (btw, I don't), however I do have a minimal trust in users reading the docs and doing a minimum of research. 

And what I was trying to explain is that given my past experience working with other PHP developers, I believe that trust is misplaced for many.  

And why make it harder than it needs to be? For PHP, jargon is Bad(tm), IMHO anyway.

-Mike

---

## #116119 — Levi Morrison via internals — 2021-09-21T21:04:27+00:00

URL: https://externals.io/message/116100#116119 · In reply to: #116118

The name "deque" is used in the standard library of these languages:

 - C++: std::deque
 - Java: java.util.Deque (interface)
 - Python: collections.deque
 - Swift: Collections.Deque (not standard lib, apparently, but Apple
official? Don't know Swift)
 - Rust: std::collections::VecDeque

And these don't have it in the standard library:
 - Go
 - C#
 - C
 - JavaScript

Anyway, it's pretty decent evidence that:
 1. This functionality is pretty widely used across languages.
 2. This functionality should have "deque" be in the name, or be the
complete name.

Discussion naming for "vector" I can understand, as it's less widely
used or sometimes means something specific to numbers, but there's
little point in discussing the name "deque." It's well established in
programming, whether PHP programmers are aware of it or not.

As I see it, the discussion should be centered around:
 1. The API Deque provides.
 2. The package that provides it.
 3. Whether Deque's API is consistent with other structures in the same package.
 4. Whether this should be included in php-src or left to extensions.

I suggest that we try to make PHP as homogenous in each bullet as we
can with other languages:
 1. Name it "Deque."
 2. Put it in the namespace "Collections" (and if included in core,
then "ext/collections").
 3. Support common operations on Deque (pushing and popping items to
both front and back, subscript operator works, iteration, size, etc)
and add little else (don't be novel here). To me, the biggest thing
left to discuss is a notion of a maximum size, which in my own
experience is common for circular buffers (the implementation chosen
for Deque) but not all languages have this.
 4. This is less clear, but I'm in favor as long as we can provide a
few other data structures at the same time. Obviously, this a voter
judgement call on the yes/no.

Given that I've suggested the most common options for these across
many languages, it shouldn't be very controversial. The worst bit
seems like picking the namespace "Collections" as this will break at
least one package: https://github.com/danielgsims/php-collections. We
should suggest that they vendor it anyway, as "collections" is common
e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
a good alternative here to "Collections", as we haven't agreed on very
much on past namespace proposals.

Anyway, that's what I suggest.

---

## #116120 — tyson andre — 2021-09-22T02:02:51+00:00

URL: https://externals.io/message/116100#116120 · In reply to: #116119

Hi Levi Morrison,

> The name "deque" is used in the standard library of these languages:
> 
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
> 
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.

Thanks for putting that together.

For anyone wondering about the languages that don't have it:
The first 3 are compiled languages so there's the same performance for a standard library 
and third-party library code written in those libraries. 
For C and Go, the standard libraries of C and Go are written in C and Go.
C and Go also have a very minimal standard library as a design goal.
Everything in C and Go is a "native library", so a third-party library and a standard library would have the same performance.
(The standard library of C and Go use or allow embedding assembly for platform-dependent functionality or optimizations. 
Third party libraries in C or Go can also use inline assembly https://stackoverflow.com/a/23796420)
(Not familiar with C#'s standard library, I assume it's similar?)

And browser vendors have put immense amounts of effort on optimizing JavaScript
and the JIT compilers for JavaScript for low memory usage,
supporting inlining, working efficiently on various platforms, etc.

> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.

Yes, I'd agree.

It's a well established term in programming, and using a non-standard or more verbose term
would make it harder to find/remember this functionality for users moving to php from 
other programming languages, 
or for users moving from php to other programming languages.

Learning programming inevitably has unfamiliar terms such as `array`, `printf`, etc.
that are not commonly used in mathematics or daily life.

> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same package.
>  4. Whether this should be included in php-src or left to extensions.
> 
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
few other data structures at the same time. Obviously, this a voter
judgement call on the yes/no.

I had planned on a minimal API for Deque.

"Maximum size" shouldn't be an issue for `Deque` specifically, it's a `size_t`. It isn't an issue for SplFixedArray and ArrayObject.
(or for 
PHP would just encounter a fatal error due to either

1. Hitting the `memory_limit` or available memory limit
while constructing or appending to the `Deque`
2. Seeing a fatal error due to integer overflow, which would only matter on 32-bit php.
   (The `Deque` API doesn't have a setSize)
   The `safe_erealloc` macros allow you to do that.

For additions such as `Vector` and `Deque`, because we **can** choose a `size_t` (type large enough to store any size of memory) (and because 32-bit systems are increasingly rare),
I currently think always emitting an uncatchable fatal error (and exiting immediately) for impossibly large values
would be the most consistent (e.g. applications wouldn't reach `catch (Throwable $t)` 
blocks meant for a different purpose in an unexpected way, if they failed to validate inputs).
This is already done in array and SPL types.

```
php > var_dump(new SplFixedArray(PHP_INT_MAX));
Fatal error: Possible integer overflow in memory allocation (9223372036854775807 * 16 + 0) in php shell code on line 1

php > var_dump(array_fill(0, 2**31 - 2, null));

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 68719476744 bytes) in php shell code on line 1
php > var_dump(array_fill(0, 2**31, null));

Warning: Uncaught ValueError: `array_fill()`: Argument #2 ($count) is too large in php shell code:1
...

// Without memory_limit
php > ini_set('memory_limit', -1);
php > $x = array_fill(0, 2**31 - 1, null);

mmap() failed: [12] Cannot allocate memory

mmap() failed: [12] Cannot allocate memory

Fatal error: Out of memory (allocated 2097152) (tried to allocate 68719476744 bytes) in php shell code on line 1
```

(If anyone's wondering about the error handling, php arrays have a size of signed `int32_t` (i.e. at most ~2 billion elements)
to support common use cases and many array instances, in a memory efficient way, while still being efficient in the engine's internals)

- If someone's application or library unexpectedly has users that end up needing to process more than 2 billion values
  (64GB of RAM in php 7.0-8.1), e.g. in reading/computing statistics from large binary files,
  the addition of `Deque` and `Vector` which don't have arbitrary size limits would be useful to them,
  and would reduce complaints or feature requests related to the ValueError.

> Given that I've suggested the most common options for these across
> many languages, it shouldn't be very controversial. The worst bit
> seems like picking the namespace "Collections" as this will break at
> least one package: https://github.com/danielgsims/php-collections. We
> should suggest that they vendor it anyway, as "collections" is common
> e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
> a good alternative here to "Collections", as we haven't agreed on very
> much on past namespace proposals.

I don't plan to use any of the class names currently found in https://github.com/danielgsims/php-collections/tree/2.X/src
for future proposals, so that's less of an issue.

I also don't see good alternatives to "Collections". On a side note, other programming languages linked keep referring to collections packages as the plural `Collections\`,
and I also keep using the name `Collections` when thinking about it and find `use Collection\Deque;` unnatural for a reason I'm not sure about,
so the plural `Collections\` makes more sense.

I'd announced https://externals.io/message/116112 in case anyone had any ideas

- `DataStructures` was mentioned but I consider it too broad.
  https://en.m.wikipedia.org/wiki/List_of_data_structures is a massive list of which collections of objects is just a small part.
  It'd make more sense if everything was distributed as a single package such as a PECL, though

I also misread https://wiki.php.net/rfc/namespaces_in_bundled_extensions#proposal .
Sub-namespaces are allowed and could be used for functions/classlikes that were not
collections or ancestor types of collections in the future, if needed (`Collections\Xyz\function_dealing_with_collections()`).

Thanks,
Tyson

---

## #116121 — Levi Morrison via internals — 2021-09-22T03:17:23+00:00

URL: https://externals.io/message/116100#116121 · In reply to: #116120

> "Maximum size" shouldn't be an issue for `Deque` specifically, it's a `size_t`. It isn't an issue for SplFixedArray and ArrayObject.
> (or for
> PHP would just encounter a fatal error due to either

You wrote a lot, but unfortunately it was based on a misunderstanding.
In some languages you can set the maximum allowed number of items a
specific Deque can hold. For example (pseudo-code):

    let deque = new Deque<int>(max_capacity: 3)
    deque.push_back(1)
    deque.push_back(2)
    deque.push_back(3) # okay, it's now full

    deque.push_back(4) # !

In this condition, they either error or remove the earliest.

It's okay if the proposed Deque doesn't add this capability, but it's
the only remaining major functionality which some languages have but
not the others; it should at least be discussed, I think.

---

## #116123 — tyson andre — 2021-09-22T04:03:11+00:00

URL: https://externals.io/message/116100#116123 · In reply to: #116121

Hi Levi Morrison,

> > […]
> 
> You wrote a lot, but unfortunately it was based on a misunderstanding.
> In some languages you can set the maximum allowed number of items a
> specific Deque can hold. For example (pseudo-code):
> 
>     let deque = new Deque<int>(max_capacity: 3)
>     deque.push_back(1)
>     deque.push_back(2)
>     deque.push_back(3) # okay, it's now full
> 
>     deque.push_back(4) # !
> 
> In this condition, they either error or remove the earliest.
> 
> It's okay if the proposed Deque doesn't add this capability, but it's
> the only remaining major functionality which some languages have but
> not the others; it should at least be discussed, I think.

Oh, I hadn't remembered seeing that before. That makes sense.
All of the implementations I'd remembered were unlimited.
(https://cplusplus.com/reference/deque/deque/max_size/ was a system limit, for example)

I can't think of a common use case for that in php.
If there was one, though, I strongly believe it shouldn't be the same class (and shouldn't be a subclass),
in order to ensure the behavior of push or other operations remains easy to reason about.
This can be done in userland as a userland class.

- (e.g. with a Deque instance property and runtime `count() < $this->maxCapacity` checks,
  to choose their own desired return value or Throwable subclass (or manual array and circular buffer in PHP)

Thanks,
Tyson

---

## #116214 — Nikita Popov — 2021-10-04T12:04:28+00:00

URL: https://externals.io/message/116100#116214 · In reply to: #116119

On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <
internals@lists.php.net> wrote:

> The name "deque" is used in the standard library of these languages:
>
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
>
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.
>
> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.
>
> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same
> package.
>  4. Whether this should be included in php-src or left to extensions.
>
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
> few other data structures at the same time. Obviously, this a voter
> judgement call on the yes/no.
>
> Given that I've suggested the most common options for these across
> many languages, it shouldn't be very controversial. The worst bit
> seems like picking the namespace "Collections" as this will break at
> least one package: https://github.com/danielgsims/php-collections. We
> should suggest that they vendor it anyway, as "collections" is common
> e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
> a good alternative here to "Collections", as we haven't agreed on very
> much on past namespace proposals.
>
> Anyway, that's what I suggest.
>

I generally agree with everything Levi has said here. I think that adding a
deque structure generally makes sense, and that putting it into a new
ext/collections extension under the corresponding namespace would be
appropriate. I wouldn't insist on introducing it together with other
structures (I'm a lot more sceptical about your Vector proposal), but do
think there should be at least some overarching plan here, even if we only
realize a small part of it in this version.

A few questions for the particular API proposed here:

1. There would be the possibility of having an interface Deque that is
backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
would actually make sense, but I wanted to throw it out there, given that
the class is final (which is without any doubt the correct decision).

2. How do set() / offsetSet() work with an out of range index? Is it
possible to push an element with $deque[count($deque)] = x? I would assume
that throws, but want to make sure. On a related note, why do we need both
get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

3. I believe it's pretty standard for Deque implementations to provide
insert() / remove() methods to insert at any position (these would be O(n)).

4. The design of getIterator() here is rather unusual, and deserves some
additional justification. Normally, we let getIterator() see concurrent
modifications to the structure, though the precise behavior is unspecified.
I would also like to know how this will look like on a technical level (it
doesn't seem to be implemented yet?) This seems like something that will
require a check on every write operation, to potentially separate the
structure in some form.

5. The shift/unshift terminology is already used by our array API, but I'm
not sure it's the most intuitive choice in the context of a deque. SplQueue
has enqueue() and dequeue(). Another popular option from other languages
(which I would personally favor) is pushFront() and popFront().

Regards,
Nikita

---

## #116222 — tyson andre — 2021-10-04T22:47:20+00:00

URL: https://externals.io/message/116100#116222 · In reply to: #116214

Hi Nikita Popov,

> 1. There would be the possibility of having an interface Deque that is
> backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
> would actually make sense, but I wanted to throw it out there, given that
> the class is final (which is without any doubt the correct decision).

Do you mean ArrayDeque for a hardcoded max capacity?
I'm also not convinced there's a use case.

> 2. How do set() / offsetSet() work with an out of range index? Is it
> possible to push an element with $deque[count($deque)] = x? I would assume
> that throws, but want to make sure. On a related note, why do we need both
> get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

It isn't possible to set an out of range index - both throws `\OutOfBoundsException`

In order to support the ArrayAccess `$deque[$offset] = $value;` or `$deque[$offset]` shorthand,
the offsetGet/offsetSet needed to be implemented to follow conventions.
(because of ArrayAccess, offsetGet must accept mixed offsets)

Those aren't type safe, though, so get()/set() are provided for a type safe alternative
that will throw a TypeError for use cases that would benefit from runtime type safety.

> 3. I believe it's pretty standard for Deque implementations to provide
> insert() / remove() methods to insert at any position (these would be O(n)).

https://www.php.net/manual/en/class.splqueue.php didn't offer that functionality. 

https://www.php.net/manual/en/class.ds-deque.php did, apparently.

> 4. The design of getIterator() here is rather unusual, and deserves some
> additional justification. Normally, we let getIterator() see concurrent
> modifications to the structure, though the precise behavior is unspecified.
> I would also like to know how this will look like on a technical level (it
> doesn't seem to be implemented yet?) This seems like something that will
> require a check on every write operation, to potentially separate the
> structure in some form.
 
The original plan was to copy the entire array on iterator creation,
to imitate the immediate copy nature of foreach on arrays.

This was assuming that `foreach` over a Deque without removing elements would be a rare use case.

That may have been a mistake since `foreach (clone $deque as $key => $value)` can be done to explicitly do that.
There're around 4 approaches I could take with different tradeoffs

1. Iterate over $offset = 0 and increment offset in calls to InternalIterator->next() until exceeding the size of the deque, not copying the deque.

   That's the **actual** current implementation, but would be unintuitive with shift()/unshift()

   This would repeat elements on unshift(), or skip over elements when shift() is called.

   The current implementation of `Ds\Deque` seems to do the same thing, but there's a similar discussion in its issue tracker in https://github.com/php-ds/ext-ds/issues/17


2. Similar iteration behavior, but also have it relative to a uint64 indicating the number of times elements were added to the front of the deque minus the number of elements were removed from the back of the deque.

    (e.g. if the current Deque internalOffset is 123, the InternalIterator returned by getOffset would start with an offset of 123 and increase it when advancing.
    Calls to shift would raise the Deque internalOffset, calls to unshift would decrease it (by the number of elements).
    This would be independent of the circular buffer offset.
    And the InternalIterator would increase the internalOffset to catch up if the signed offset difference became negative, e.g. by calling shift() twice in a foreach block)

3. Behave as if the entire Deque was copied when iteration starts (either by actually copying everything or by copy on write).

   That was the **planned** implementation documented in the RFC, but would be inefficient for iterations that end early and use a lot of memory for large Deques.

4. Throw if attempting to change the size of the `Deque` while a foreach is in progress.

   The semantics of that would be annoying, e.g. handling `clear()` or `shift()`, and the exception getting thrown would be unexpected.

> 5. The shift/unshift terminology is already used by our array API, but I'm
> not sure it's the most intuitive choice in the context of a deque. SplQueue
> has enqueue() and dequeue(). Another popular option from other languages
> (which I would personally favor) is pushFront() and popFront().

My original name idea was pushBack/popBack/pushFront/popFront but I had decided against proposing brand new terms
for functionality that already had terms in php-src.
It would also be inconsistent with proposed names for `Vector` if that was also added.

https://www.php.net/manual/en/class.ds-deque.php and SplDoublyLinkedList had done the same thing

enqueue and dequeue don't have a good term for enqueueing on the opposite side.

- It would make it easier to learn the language to have fewer terms and migrate code using SplDoublyLinkedList or arrays
- push()/shift() are also shorter names than pushBack/popFront()

Thanks,
Tyson


From: Nikita Popov <nikita.ppv@gmail.com>
Sent: October 4, 2021 8:04 AM
To: Levi Morrison <levi.morrison@datadoghq.com>
Cc: PHP internals <internals@lists.php.net>
Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP 
 
On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <
internals@lists.php.net> wrote:

> The name "deque" is used in the standard library of these languages:
>
>  - C++: std::deque
>  - Java: java.util.Deque (interface)
>  - Python: collections.deque
>  - Swift: Collections.Deque (not standard lib, apparently, but Apple
> official? Don't know Swift)
>  - Rust: std::collections::VecDeque
>
> And these don't have it in the standard library:
>  - Go
>  - C#
>  - C
>  - JavaScript
>
> Anyway, it's pretty decent evidence that:
>  1. This functionality is pretty widely used across languages.
>  2. This functionality should have "deque" be in the name, or be the
> complete name.
>
> Discussion naming for "vector" I can understand, as it's less widely
> used or sometimes means something specific to numbers, but there's
> little point in discussing the name "deque." It's well established in
> programming, whether PHP programmers are aware of it or not.
>
> As I see it, the discussion should be centered around:
>  1. The API Deque provides.
>  2. The package that provides it.
>  3. Whether Deque's API is consistent with other structures in the same
> package.
>  4. Whether this should be included in php-src or left to extensions.
>
> I suggest that we try to make PHP as homogenous in each bullet as we
> can with other languages:
>  1. Name it "Deque."
>  2. Put it in the namespace "Collections" (and if included in core,
> then "ext/collections").
>  3. Support common operations on Deque (pushing and popping items to
> both front and back, subscript operator works, iteration, size, etc)
> and add little else (don't be novel here). To me, the biggest thing
> left to discuss is a notion of a maximum size, which in my own
> experience is common for circular buffers (the implementation chosen
> for Deque) but not all languages have this.
>  4. This is less clear, but I'm in favor as long as we can provide a
> few other data structures at the same time. Obviously, this a voter
> judgement call on the yes/no.
>
> Given that I've suggested the most common options for these across
> many languages, it shouldn't be very controversial. The worst bit
> seems like picking the namespace "Collections" as this will break at
> least one package: https://github.com/danielgsims/php-collections. We
> should suggest that they vendor it anyway, as "collections" is common
> e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see
> a good alternative here to "Collections", as we haven't agreed on very
> much on past namespace proposals.
>
> Anyway, that's what I suggest.
>

I generally agree with everything Levi has said here. I think that adding a
deque structure generally makes sense, and that putting it into a new
ext/collections extension under the corresponding namespace would be
appropriate. I wouldn't insist on introducing it together with other
structures (I'm a lot more sceptical about your Vector proposal), but do
think there should be at least some overarching plan here, even if we only
realize a small part of it in this version.

A few questions for the particular API proposed here:

1. There would be the possibility of having an interface Deque that is
backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
would actually make sense, but I wanted to throw it out there, given that
the class is final (which is without any doubt the correct decision).

2. How do set() / offsetSet() work with an out of range index? Is it
possible to push an element with $deque[count($deque)] = x? I would assume
that throws, but want to make sure. On a related note, why do we need both
get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

3. I believe it's pretty standard for Deque implementations to provide
insert() / remove() methods to insert at any position (these would be O(n)).

4. The design of getIterator() here is rather unusual, and deserves some
additional justification. Normally, we let getIterator() see concurrent
modifications to the structure, though the precise behavior is unspecified.
I would also like to know how this will look like on a technical level (it
doesn't seem to be implemented yet?) This seems like something that will
require a check on every write operation, to potentially separate the
structure in some form.

5. The shift/unshift terminology is already used by our array API, but I'm
not sure it's the most intuitive choice in the context of a deque. SplQueue
has enqueue() and dequeue(). Another popular option from other languages
(which I would personally favor) is pushFront() and popFront().

Regards,
Nikita

---

## #116223 — Nikita Popov — 2021-10-05T07:58:46+00:00

URL: https://externals.io/message/116100#116223 · In reply to: #116222

On Tue, Oct 5, 2021 at 12:47 AM tyson andre <tysonandre775@hotmail.com>
wrote:

> Hi Nikita Popov,
>
> > […]
>
> Do you mean ArrayDeque for a hardcoded max capacity?
> I'm also not convinced there's a use case.
>
> > […]
> assume
> > […]
> both
> > […]
>
> It isn't possible to set an out of range index - both throws
> `\OutOfBoundsException`
>
> In order to support the ArrayAccess `$deque[$offset] = $value;` or
> `$deque[$offset]` shorthand,
> the offsetGet/offsetSet needed to be implemented to follow conventions.
> (because of ArrayAccess, offsetGet must accept mixed offsets)
>
> Those aren't type safe, though, so get()/set() are provided for a type
> safe alternative
> that will throw a TypeError for use cases that would benefit from runtime
> type safety.
>

offsetGet() and offsetSet() can (and should) still throw if the offset is
not an integer. We just can't actually declare that type. This is a
weakness of the PHP type system, so nominally "violating" LSP is fine here.


> > […]
> O(n)).
>
> https://www.php.net/manual/en/class.splqueue.php didn't offer that
> functionality.
>
> https://www.php.net/manual/en/class.ds-deque.php did, apparently.
>
> > […]
> unspecified.
> > […]
> (it
> > […]
>
> The original plan was to copy the entire array on iterator creation,
> to imitate the immediate copy nature of foreach on arrays.
>

There is no immediate copy with arrays though. The copy is just a refcount
increment and no actual copy will happen unless the array is modified
during iteration, which is a rare case. I'd expect the Deque implementation
(with those semantics) to do the same -- but we don't have a convenient
mechanism for it. Adding an indirection and a refcount to the underlying
storage would be possible, but also feels like overkill. The other approach
I see would be to track all the registered iterators, so we can explicitly
separate them on write.


> This was assuming that `foreach` over a Deque without removing elements
> would be a rare use case.
>
> That may have been a mistake since `foreach (clone $deque as $key =>
> $value)` can be done to explicitly do that.
> There're around 4 approaches I could take with different tradeoffs
>
> 1. Iterate over $offset = 0 and increment offset in calls to
> InternalIterator->next() until exceeding the size of the deque, not copying
> the deque.
>
>    That's the **actual** current implementation, but would be unintuitive
> with shift()/unshift()
>
>    This would repeat elements on unshift(), or skip over elements when
> shift() is called.
>
>    The current implementation of `Ds\Deque` seems to do the same thing,
> but there's a similar discussion in its issue tracker in
> https://github.com/php-ds/ext-ds/issues/17
>
>
> 2. Similar iteration behavior, but also have it relative to a uint64
> indicating the number of times elements were added to the front of the
> deque minus the number of elements were removed from the back of the deque.
>
>     (e.g. if the current Deque internalOffset is 123, the InternalIterator
> returned by getOffset would start with an offset of 123 and increase it
> when advancing.
>     Calls to shift would raise the Deque internalOffset, calls to unshift
> would decrease it (by the number of elements).
>     This would be independent of the circular buffer offset.
>     And the InternalIterator would increase the internalOffset to catch up
> if the signed offset difference became negative, e.g. by calling shift()
> twice in a foreach block)
>

Something to keep in mind here is that there might be multiple iterators at
the same time, so I don't think the suggestion from the last sentence would
work. Though I think the general idea does work, as long as we're working
with a delta between the offset in the iterator and the deque.


> 3. Behave as if the entire Deque was copied when iteration starts (either
> by actually copying everything or by copy on write).
>
>    That was the **planned** implementation documented in the RFC, but
> would be inefficient for iterations that end early and use a lot of memory
> for large Deques.
>
> 4. Throw if attempting to change the size of the `Deque` while a foreach
> is in progress.
>
>    The semantics of that would be annoying, e.g. handling `clear()` or
> `shift()`, and the exception getting thrown would be unexpected.
>
> > […]
> I'm
> > […]
> SplQueue
> > […]
>
> My original name idea was pushBack/popBack/pushFront/popFront but I had
> decided against proposing brand new terms
> for functionality that already had terms in php-src.
> It would also be inconsistent with proposed names for `Vector` if that was
> also added.
>
> https://www.php.net/manual/en/class.ds-deque.php and SplDoublyLinkedList
> had done the same thing
>
> enqueue and dequeue don't have a good term for enqueueing on the opposite
> side.
>
> - It would make it easier to learn the language to have fewer terms and
> migrate code using SplDoublyLinkedList or arrays
> - push()/shift() are also shorter names than pushBack/popFront()
>
> Thanks,
> Tyson
>
>
> From: Nikita Popov <nikita.ppv@gmail.com>
> Sent: October 4, 2021 8:04 AM
> To: Levi Morrison <levi.morrison@datadoghq.com>
> Cc: PHP internals <internals@lists.php.net>
> Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP
>
> On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <
> internals@lists.php.net> wrote:
>
> > […]
>
> I generally agree with everything Levi has said here. I think that adding a
> deque structure generally makes sense, and that putting it into a new
> ext/collections extension under the corresponding namespace would be
> appropriate. I wouldn't insist on introducing it together with other
> structures (I'm a lot more sceptical about your Vector proposal), but do
> think there should be at least some overarching plan here, even if we only
> realize a small part of it in this version.
>
> A few questions for the particular API proposed here:
>
> 1. There would be the possibility of having an interface Deque that is
> backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
> would actually make sense, but I wanted to throw it out there, given that
> the class is final (which is without any doubt the correct decision).
>
> 2. How do set() / offsetSet() work with an out of range index? Is it
> possible to push an element with $deque[count($deque)] = x? I would assume
> that throws, but want to make sure. On a related note, why do we need both
> get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.
>
> 3. I believe it's pretty standard for Deque implementations to provide
> insert() / remove() methods to insert at any position (these would be
> O(n)).
>
> 4. The design of getIterator() here is rather unusual, and deserves some
> additional justification. Normally, we let getIterator() see concurrent
> modifications to the structure, though the precise behavior is unspecified.
> I would also like to know how this will look like on a technical level (it
> doesn't seem to be implemented yet?) This seems like something that will
> require a check on every write operation, to potentially separate the
> structure in some form.
>
> 5. The shift/unshift terminology is already used by our array API, but I'm
> not sure it's the most intuitive choice in the context of a deque. SplQueue
> has enqueue() and dequeue(). Another popular option from other languages
> (which I would personally favor) is pushFront() and popFront().
>
> Regards,
> Nikita
> --
> 
> To unsubscribe, visit: https://www.php.net/unsub.php

---

## #116960 — tyson andre — 2022-02-01T03:31:36+00:00

URL: https://externals.io/message/116100#116960 · In reply to: #116223

> > […]
> 
> I generally agree with everything Levi has said here. I think that adding a
> deque structure generally makes sense, and that putting it into a new
> ext/collections extension under the corresponding namespace would be
> appropriate. I wouldn't insist on introducing it together with other
> structures (I'm a lot more sceptical about your Vector proposal), but do
> think there should be at least some overarching plan here, even if we only
> realize a small part of it in this version.
 
https://wiki.php.net/rfc/deque has been updated after https://wiki.php.net/rfc/deque_straw_poll.
It's now going in the namespace `Collections\`, and a new always-enabled extension `collections` 
is added in `php-src/ext/collections` in that RFC (for end users, that would mainly affect php.net manual organization).

I plan to start voting in a few days.

Also, iteration behavior has changed to https://wiki.php.net/rfc/deque#iteration_behavior

I also set up a WebAssembly demo to make it easier to look up how it currently behaves:
https://tysonandre.github.io/php-rfc-demo/deque/

> A few questions for the particular API proposed here:
> 
> 1. There would be the possibility of having an interface Deque that is
> backed by a VecDeque/ArrayDeque implementation. I'm not convinced this
> would actually make sense, but I wanted to throw it out there, given that
> the class is final (which is without any doubt the correct decision).

Would `ArrayDeque` be referring to something with a hardcoded maximum size?
I can't think of a strong use case for that, and it's possible in userland by 
wrapping `Collections\Deque` (with composition) and checking size on add operations.

> 2. How do set() / offsetSet() work with an out of range index? Is it
> possible to push an element with $deque[count($deque)] = x? I would assume
> that throws, but want to make sure. On a related note, why do we need both
> get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.

They throw for out of range indexes. Offsets between 0 and count-1 are in range.

offsetSet/offsetGet attempt to coerce values to integers to act as a drop-in replacement 
for arrays and Spl datastructures (e.g. for applications that deal with string inputs).
They throw TypeError if coercion fails, OutOfBoundsException for invalid offsets.

> 3. I believe it's pretty standard for Deque implementations to provide
> insert() / remove() methods to insert at any position (these would be O(n)).

I agree it's pretty standard and something I'd want, 
I was concerned about increasing the scope too much (before seeing if new collections would succeed)
and making this harder to review (and with more methods added to the design,
more possible objections to API decisions)
 
> 4. The design of getIterator() here is rather unusual, and deserves some
> additional justification. Normally, we let getIterator() see concurrent
> modifications to the structure, though the precise behavior is unspecified.
> I would also like to know how this will look like on a technical level (it
> doesn't seem to be implemented yet?) This seems like something that will
> require a check on every write operation, to potentially separate the
> structure in some form.

You have a good point - the proposed and implemented behavior have been updated.
It's now iterating over the original Deque, not an eager copy. https://wiki.php.net/rfc/deque#iteration_behavior
The Deque now tracks how the position of the front is moved by shift()/unshift() operations.
Iterators have their own positions that are unconditionally advanced by 1 in `$iterator->next()` and the delta is 
the iterator offset (`$iterator->key()`).

The implemented behavior can be seen at https://tysonandre.github.io/php-rfc-demo/deque/

> 5. The shift/unshift terminology is already used by our array API, but I'm
> not sure it's the most intuitive choice in the context of a deque. SplQueue
> has enqueue() and dequeue(). Another popular option from other languages
> (which I would personally favor) is pushFront() and popFront().

enqueue() is the same as push(), dequeue is the same as shift(). 
It's still using the inherited unshift for adding to the front of the deque.

In isolation, I'd prefer pushFront/popFront as names, but introducing more than one name for common operations
seemed like it wouldn't be worth the inconvenience for the potential of introducing bugs in userland code when switching between collection objects,
making the standard library harder to learn/remember, etc.

Thanks,
Tyson

---

## #116961 — Levi Morrison via internals — 2022-02-01T03:40:47+00:00

URL: https://externals.io/message/116100#116961 · In reply to: #116960

I think this RFC is in much better shape now.

The last thing I'll personally push for is dropping `get` and `set`.
I'm not sure about those names, and the functionality is already
provided by `offsetGet` and `offsetSet`, albeit through `mixed`
instead of `int`, but I think this sort of cleanup should be done en
masse at some point, rather than having this one type doing something
different from the others.

---

## #116964 — tyson andre — 2022-02-01T13:47:45+00:00

URL: https://externals.io/message/116100#116964 · In reply to: #116961

Hi Levi Morrison,

> I think this RFC is in much better shape now.
> 
> The last thing I'll personally push for is dropping `get` and `set`.
> I'm not sure about those names, and the functionality is already
> provided by `offsetGet` and `offsetSet`, albeit through `mixed`
> instead of `int`, but I think this sort of cleanup should be done en
> masse at some point, rather than having this one type doing something
> different from the others.

The get/set methods have been removed. I've updated the RFC and implementation.

Thanks,
Tyson

---

## #116965 — tyson andre — 2022-02-01T14:46:19+00:00

URL: https://externals.io/message/116100#116965 · In reply to: #116100

Hi internals,

> I've created a new RFC https://wiki.php.net/rfc/deque to add a `final class Deque`
> 
> This is based on the `Teds\Deque` implementation I've worked on
> for the https://github.com/TysonAndre/pecl-teds PECL.
> 
> While `SplDoublyLinkedList` and its subclass `SplQueue`/`SplStack` exist in the SPL, they have several drawbacks
> that are addressed by this RFC to add a `Deque` class (to use instead of those):
> 
> 1. `SplDoublyLinkedList` is internally represented by a doubly linked list,
>    making it use roughly twice as much memory as the proposed `Deque`
> 2. `push`/`pop`/`unshift`/`shift` from `SplDoublyLinkedList` are slower due to
>    needing to allocate or free the linked list nodes.
> 3. Reading values in the middle of the `SplDoublyLinkedList` is proportional to the length of the list,
>    due to needing to traverse the linked list nodes.
> 4. `foreach` Iteration behavior cannot be understood without knowing what constructed the
>    `SplDoublyLinkedList` instance or set the flags.
> 
> It would be useful to have an efficient `Deque` container in the standard library
> to provide an alternative without those drawbacks,
> as well as for the following reasons:
> 
> 1. To save memory in applications or libraries that may need to store many lists of values or run for long periods of time.
>    Notably, PHP's `array` type will never release allocated capacity.
>    See https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html
> 2. To provide a better alternative to `SplDoublyLinkedList`, `SplStack`, and `SplQueue`
>    for use cases that require stacks or queues.
> 3. As a more efficient option than `array` and `SplDoublyLinkedList`
>    as a queue or `Deque`, especially for `unshift`.
> 
> A `Deque` is more efficient than an `array` when used as a queue, more readable, and easier to use correctly.
> While it is possible to efficiently remove elements from the start of an `array` (in terms of insertion order) (though this makes `reset()`/array_key_first() inefficient),
> it is very inefficient to prepend elements to the start of a large `array` due to needing to either copy the array
> or move all elements in the internal array representation,
> and an `array` would use much more memory than a `Deque` when used that way (and be slower).
> 
> There are also several pitfalls to using an array as a queue for larger queue sizes,
> some of which are not obvious and discovered while writing the benchmarks.
> (Having a better (double-ended) queue datastructure (`Deque`) than the `SplDoublyLinkedList`
> would save users from needing to write code with these pitfalls):
> 
> 1. `array_key_first()` and `reset()``takes time proportional to the number of elements `unset` from the start of an array,
>    causing it to unexpectedly be extremely slow (quadratic time) after unsetting many elements at the start of the queue.
>    (when the array infrequently runs out of capacity, buckets are moved to the front)
> 2. `reset()` or `end()` will convert a variable to a reference,
>    and php is less efficient at reading or writing to reference.
>    Opcache is also less efficient at optimizing uses of variables using references.
> 3. More obviously, `array_unshift` and `array_shift` will take time proportional to the number of elements in the array
>    (to reindex and move existing/remaining elements).

I plan to start voting on https://wiki.php.net/rfc/deque on Friday, February 4th.

Several changes have been made to https://wiki.php.net/rfc/deque#changelog
after the feedback in https://externals.io/message/116100

- The class is now named `Collections\Deque`
- The api documentation in https://wiki.php.net/rfc/deque#proposal was expanded for methods.
- Benchmarks were updated.
- Like other standard datastructures, iteration over the deque is now over the original object (instead of creating a copy), 
  and mutating the deque will be reflected in `$iterator->current()` (and moving the end with push()/pop() will affect where iteration ends).
- Iteration will account for calls to shift/unshift moving the start of the deque.
  the offsets will be corrected and values won't be skipped or iterated over multiple times.
  (no matter how many iterators were created by `Deque->getIterator()`)
  See https://wiki.php.net/rfc/deque#iteration_behavior
- The get()/set() methods were removed, after feedback in https://externals.io/message/116100#116214

A WebAssembly demo is available at https://tysonandre.github.io/php-rfc-demo/deque/

Thanks,
Tyson

---

## #116966 — Stephen Reay — 2022-02-01T16:06:59+00:00

URL: https://externals.io/message/116100#116966 · In reply to: #116965

> 
> 
> Hi internals,
> 
> > […]
> 
> I plan to start voting on https://wiki.php.net/rfc/deque on Friday, February 4th.
> 
> Several changes have been made to https://wiki.php.net/rfc/deque#changelog
> after the feedback in https://externals.io/message/116100
> 
> - The class is now named `Collections\Deque`
> - The api documentation in https://wiki.php.net/rfc/deque#proposal was expanded for methods.
> - Benchmarks were updated.
> - Like other standard datastructures, iteration over the deque is now over the original object (instead of creating a copy), 
>  and mutating the deque will be reflected in `$iterator->current()` (and moving the end with push()/pop() will affect where iteration ends).
> - Iteration will account for calls to shift/unshift moving the start of the deque.
>  the offsets will be corrected and values won't be skipped or iterated over multiple times.
>  (no matter how many iterators were created by `Deque->getIterator()`)
>  See https://wiki.php.net/rfc/deque#iteration_behavior
> - The get()/set() methods were removed, after feedback in https://externals.io/message/116100#116214
> 
> A WebAssembly demo is available at https://tysonandre.github.io/php-rfc-demo/deque/
> 
> Thanks,
> Tyson
> 
> --
> 
> To unsubscribe, visit: https://www.php.net/unsub.php
> 

Hi Tyson,

As a userland dev & library author it’s nice to see some progression on basic data structures, so thank you for your efforts on this!


Two little things in the RFC:

The proposed API switches between terms `front`, `back`, `start` and `end` in comments - is there meant to be a conceptual difference between front/start and end/back ?


In the "Why use this instead of array?” Section, the 3rd point seems cut off:
> Note that starting in php 8.2, array


Cheers

Stephen

---

## #116967 — Larry Garfield — 2022-02-01T16:26:42+00:00

URL: https://externals.io/message/116100#116967 · In reply to: #116965

> I plan to start voting on https://wiki.php.net/rfc/deque on Friday, 
> February 4th.
>
> Several changes have been made to https://wiki.php.net/rfc/deque#changelog
> after the feedback in https://externals.io/message/116100
>
> - The class is now named `Collections\Deque`
> - The api documentation in https://wiki.php.net/rfc/deque#proposal was 
> expanded for methods.
> - Benchmarks were updated.
> - Like other standard datastructures, iteration over the deque is now 
> over the original object (instead of creating a copy), 
>   and mutating the deque will be reflected in `$iterator->current()` 
> (and moving the end with push()/pop() will affect where iteration ends).
> - Iteration will account for calls to shift/unshift moving the start of 
> the deque.
>   the offsets will be corrected and values won't be skipped or iterated 
> over multiple times.
>   (no matter how many iterators were created by `Deque->getIterator()`)
>   See https://wiki.php.net/rfc/deque#iteration_behavior
> - The get()/set() methods were removed, after feedback in 
> https://externals.io/message/116100#116214
>
> A WebAssembly demo is available at 
> https://tysonandre.github.io/php-rfc-demo/deque/

Request:

push() and unshift() currently return void.  That's not helpful.  It would be vastly more useful if they both returned $this.  Not as much for chaining, but more so that you can add a value to a queue and pass it as an argument to another call (often recursive, but not necessarily) in a single operation.  

Example: I was doing last year's Advent of Code in functional PHP, and had a stack walker that looked like this:

function parse(string $line, $pos = 0, array $stack = []): Result|string
{
    $next = $line[$pos] ?? null;
    $head = $stack[0] ?? null;

    return match ($next) {
        // Opening brace, push an "expected" onto the stack.
        '{' => parse($line, $pos + 1, ['}', ...$stack]),
        '<' => parse($line, $pos + 1, ['>', ...$stack]),
        '(' => parse($line, $pos + 1, [')', ...$stack]),
        '[' => parse($line, $pos + 1, [']', ...$stack]),
        '}', '>', ')', ']' => $next === $head ? parse($line, $pos + 1, array_slice($stack, 1)) : $next,
        null => count($stack) ? Result::Incomplete : Result::OK,
    };
}

The interesting part is the ['<', ...$stack], to pass on a modified version of an array-as-stack.  That's of course annoyingly slow with arrays right now, and a Deque would be better, but only if it could be "modified and passed" like that.  If not, it would be incompatible with single-expression usages (match statements, short lambdas, etc.)

Returning $this would resolve that, I think.  (Making it return a new, immutable copy of the Deque would be even nicer, but I realize that's probably not an argument I'm going to win at this point on this RFC.)

Also, typo:

"By introducing a data structure (Deque) that's even faster and more memory usage than an array for use as a double-ended queue, even more applications would benefit from it. "

I think you mean "less memory usage", or possibly "more memory efficient", or something like that.

--Larry Garfield

---

## #116968 — Mel Dafert — 2022-02-01T17:07:16+00:00

URL: https://externals.io/message/116100#116968 · In reply to: #116966

>
>The proposed API switches between terms `front`, `back`, `start` and `end` in comments - is there meant to be a conceptual difference between front/start and end/back ?

On a similar note, why are the methods for getting the first/last value called
`top()`/`bottom()`? Off the top of my head, it is hard for me to imagine which side is
the top and which side is the bottom.
I would prefer if it was called something more intuitive, possibly `first()`/`last()` in
accordance with `array_key_first()`/`array_key_last()`.

Regards,
Mel

---

Next page: https://externals.io/message/116100.md?page=2