Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116960
To: "internals@lists.php.net" <internals@lists.php.net>
Thread-Topic: [PHP-DEV] Adding `final class Deque` to PHP
Thread-Index:
 AQHXraUxaK1dZ0niuECOJlLUpHNcpaut5O0AgAA5JgCAAJnxgIAABFYAgAAl9YCAABrsgIAT13AAgACw9q+AAJy5AIC6sYRh
Date: Tue, 1 Feb 2022 03:31:36 +0000
Message-ID:
 <DM6PR14MB41552CC4E70356D9BA73A40BF9269@DM6PR14MB4155.namprd14.prod.outlook.com>
References:
 <DM6PR07MB66185E23B803C5E5BF858B30F9DF9@DM6PR07MB6618.namprd07.prod.outlook.com>
 <A59125BE-AF91-44D1-9B47-82046B51EE8F@newclarity.net>
 <CAEZPtU7+hgcHwRfaa7-CR9SVv2=HfH46kDVu0pDYm5M=WeFPVg@mail.gmail.com>
 <67BFE5C6-3C3F-4309-97A2-14CA0D8C3B3B@newclarity.net>
 <CAEZPtU62gfKb-xODqm_yk-BE_ycLshuD2_ps733_ReFgksLqaQ@mail.gmail.com>
 <7BEE0406-3CAE-4E83-A196-F9F608BE8D17@newclarity.net>
 <CAAKU0uk6Wvd5aPQ4qzJTQiHpuLCM999Wsm7qrjWMonF7q+SuDw@mail.gmail.com>
 <CAF+90c84NGyL2Kq1k0d=V_G0K96wCvdfqsvtrTYkneVvpHSFmw@mail.gmail.com>
 <DM5PR17MB1481CB947F6D5412FC474D80F9AE9@DM5PR17MB1481.namprd17.prod.outlook.com>
 <CAF+90c-kdmoDz-TzdaPGaHq_5x7qgp=mi4AnS13UCQme2c2OMw@mail.gmail.com>
In-Reply-To:
 <CAF+90c-kdmoDz-TzdaPGaHq_5x7qgp=mi4AnS13UCQme2c2OMw@mail.gmail.com>
Accept-Language: en-CA, en-US
Content-Language: en-CA
suggested_attachment_session_id: 3234aefa-c7b9-cb64-693c-b813dcfd55c4
x-ms-exchange-messagesentrepresentingtype: 1
x-tmn:
 [KwlJ6/B+pJokVy0zoM32lyjeiIXSJnw9rmt9nAuMWps1xPSbg6ANQovO3jnAFYlUil6+MUS4sqg=]
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: f9692ee0-4297-47b7-7f9b-08d9e5335a0b
x-ms-traffictypediagnostic: SJ0PR14MB4380:EE_
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info:
 DO86xE7zl10e/fEKJ50Q/hE/G1qVeD8A0B6rqzsZsdVgVCogYfqAHseSmlOuSHHKD1AY1McTwIj0WoLkvrWUkkFZJCx8OW3oEZ8A1HRMjKNw4I3HOTopukILuAQnlTLEdfWZ8cAvLJQaAN/+McaZRJItsb8VafkN4SijsdU6BkUS7hJWaWwrUYbHnTvd5lsCD1OUGNfDH5u2Fzfsg1gst3mJ2jh0lYd6TagNE+/icYP1Y03+8doZuKgqz2/g/zY+jkNcL/lWUjeRLF5lPdMQkEb3tqq0eYFMu4Db0dWDY25qfCsEnjbaMe9mvGFUlm/51GBDbPQYgQCCytxhBJVZSeeZ+2A97SY+i0koL8c6hc7fgeSw4dCLbiubROMavvQj5GYAPXlhKZPh4lOPxN14DQ1lOXD/EpqLPQ9jMbcsIpfMQiSZnykizAu0CtNt0oYeugtXMhlt2XEF2E2TLs5NgiUmcBWCPiHCxYN36UOV7kKcCQQ8Z/ncSPBbhc3KIMZHlGh3aZ7PzvJpbXMVrTOvZIxbdft/9rxlWxYXkfPI/ieF1IyGNEMkLCLEmaByLH3sJWYx/z2xKzqw+k5XMf/qrL3dQi1H69qQa60HitYasbJOPcQYFvmLyJedhH1gkR3oNyg+D0Rvd3JMJr7WtMsNQ1Y6UuBgCW2NfsjZ4B1MXYo=
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0:
 =?iso-8859-1?Q?1Nwq2Z0sC4vBpSZcdsP+pjMpMnoWchDzQWNBnonIlEG+S2aP6r03xxb+Im?=
 =?iso-8859-1?Q?Tj3RDKsKn9zAMT9GtsZMjZWVhFDC+rCCxZVFMonW3OYpliWDELuu/YYIPT?=
 =?iso-8859-1?Q?gh6SSMOpruw3BA0vSAaDsGAs7AvuXp4B5//5VjvQYEUiTTUP2nJCQGPMWh?=
 =?iso-8859-1?Q?a8HPsuu/JVaCPBSQimTp6GX97RE7T404pmPIrmr2GAJqFAfRJgLucp597S?=
 =?iso-8859-1?Q?Z33X5biop/EA9qh751ptMVPSPqaaGBy+tESxq1KjRYAD8A5s4el0sP1Abk?=
 =?iso-8859-1?Q?5Azr6cOnk4iohE+EtyjKlAarA4iW6qdC2qznqWiej1hb3dMGBhUmTXVt8g?=
 =?iso-8859-1?Q?KfDIOHKqqhC6ZJuoNeXEborJMg8oabbmFiFYFNubXrtVFqHUxOIAIYCCud?=
 =?iso-8859-1?Q?0Tf5KO3ZU31uz6ieZbHpq4jAE8sBrTZnJ3COf9c7dGuS4GipwQKTUrRpb8?=
 =?iso-8859-1?Q?Sc4+e7NBWBGoYvFAQ8qxVIYnhy6JurA8/SCYZVWirQpo0p1Lw7wHeqlkNb?=
 =?iso-8859-1?Q?Pez25utFAJb2GJNqUVfXvnz1A9/i0MXpGmn7N1DB2/VZdOOFm9ApYei+Ka?=
 =?iso-8859-1?Q?RitcErgECvGFBHSDtOnVEQKe2hJtCt01Y26GcKfpl15GY0PL2wbDwBtqt/?=
 =?iso-8859-1?Q?7iHHzmkrWDnMnT+9OjHabgzl9SSdUL6FOTB00ac9xK6D5CdhM009oSSuRR?=
 =?iso-8859-1?Q?x+AVh7pCLZ3jd2yWWvGN1PE5qiLGrceEjB1aqlUm2xMYpCHXHComyDt5Qj?=
 =?iso-8859-1?Q?9rpwARlDO2zy7Lf1phn2Ovlvy/TY26+5zmYugcTcRwH4lwoUIxPbbzt5vH?=
 =?iso-8859-1?Q?tgWXWssm4lIgma6ANK1XgFc8cVP12Yxv/0f662fKBt5JhgiuFLMQj9ePYS?=
 =?iso-8859-1?Q?eJoD9ZEqcKquyRJ9/vCY3lRbQAfZk0Qkvwu9AEHh0MQSRlmGTxZhlpGzFT?=
 =?iso-8859-1?Q?7EI5rES0pFiPC16m4KrI1zPKEmNBrq12rvSSNE6T5xJOClO2ooSq4Rsvx7?=
 =?iso-8859-1?Q?oB3cTgoX3MAF/vyY9cqqen9g7bnTOnwQDI9iGeM+yRKXhclacD7aCb2Djm?=
 =?iso-8859-1?Q?NA=3D=3D?=
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: sct-15-20-4755-11-msonline-outlook-cd57b.templateTenant
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: DM6PR14MB4155.namprd14.prod.outlook.com
X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000
X-MS-Exchange-CrossTenant-Network-Message-Id: f9692ee0-4297-47b7-7f9b-08d9e5335a0b
X-MS-Exchange-CrossTenant-originalarrivaltime: 01 Feb 2022 03:31:36.5650
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 84df9e7f-e9f6-40af-b435-aaaaaaaaaaaa
X-MS-Exchange-CrossTenant-rms-persistedconsumerorg: 00000000-0000-0000-0000-000000000000
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR14MB4380
Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP
From: tysonandre775@hotmail.com (tyson andre)

> > The name "deque" is used in the standard library of these languages:=0A=
> >=0A=
> >=A0 - C++: std::deque=0A=
> >=A0 - Java: java.util.Deque (interface)=0A=
> >=A0 - Python: collections.deque=0A=
> >=A0 - Swift: Collections.Deque (not standard lib, apparently, but Apple=
=0A=
> > official? Don't know Swift)=0A=
> >=A0 - Rust: std::collections::VecDeque=0A=
> >=0A=
> > And these don't have it in the standard library:=0A=
> >=A0 - Go=0A=
> >=A0 - C#=0A=
> >=A0 - C=0A=
> >=A0 - JavaScript=0A=
> >=0A=
> > Anyway, it's pretty decent evidence that:=0A=
> >=A0 1. This functionality is pretty widely used across languages.=0A=
> >=A0 2. This functionality should have "deque" be in the name, or be the=
=0A=
> > complete name.=0A=
> >=0A=
> > Discussion naming for "vector" I can understand, as it's less widely=0A=
> > used or sometimes means something specific to numbers, but there's=0A=
> > little point in discussing the name "deque." It's well established in=
=0A=
> > programming, whether PHP programmers are aware of it or not.=0A=
> >=0A=
> > As I see it, the discussion should be centered around:=0A=
> >=A0 1. The API Deque provides.=0A=
> >=A0 2. The package that provides it.=0A=
> >=A0 3. Whether Deque's API is consistent with other structures in the sa=
me=0A=
> > package.=0A=
> >=A0 4. Whether this should be included in php-src or left to extensions.=
=0A=
> >=0A=
> > I suggest that we try to make PHP as homogenous in each bullet as we=0A=
> > can with other languages:=0A=
> >=A0 1. Name it "Deque."=0A=
> >=A0 2. Put it in the namespace "Collections" (and if included in core,=
=0A=
> > then "ext/collections").=0A=
> >=A0 3. Support common operations on Deque (pushing and popping items to=
=0A=
> > both front and back, subscript operator works, iteration, size, etc)=0A=
> > and add little else (don't be novel here). To me, the biggest thing=0A=
> > left to discuss is a notion of a maximum size, which in my own=0A=
> > experience is common for circular buffers (the implementation chosen=0A=
> > for Deque) but not all languages have this.=0A=
> >=A0 4. This is less clear, but I'm in favor as long as we can provide a=
=0A=
> > few other data structures at the same time. Obviously, this a voter=0A=
> > judgement call on the yes/no.=0A=
> >=0A=
> > Given that I've suggested the most common options for these across=0A=
> > many languages, it shouldn't be very controversial. The worst bit=0A=
> > seems like picking the namespace "Collections" as this will break at=0A=
> > least one package: https://github.com/danielgsims/php-collections. We=
=0A=
> > should suggest that they vendor it anyway, as "collections" is common=
=0A=
> > e.g. "Ramsey\Collections", "Doctrine\Common\Collections". I don't see=
=0A=
> > a good alternative here to "Collections", as we haven't agreed on very=
=0A=
> > much on past namespace proposals.=0A=
> >=0A=
> > Anyway, that's what I suggest.=0A=
> >=0A=
> =0A=
> I generally agree with everything Levi has said here. I think that adding=
 a=0A=
> deque structure generally makes sense, and that putting it into a new=0A=
> ext/collections extension under the corresponding namespace would be=0A=
> appropriate. I wouldn't insist on introducing it together with other=0A=
> structures (I'm a lot more sceptical about your Vector proposal), but do=
=0A=
> think there should be at least some overarching plan here, even if we onl=
y=0A=
> realize a small part of it in this version.=0A=
 =0A=
https://wiki.php.net/rfc/deque has been updated after https://wiki.php.net/=
rfc/deque_straw_poll.=0A=
It's now going in the namespace `Collections\`, and a new always-enabled ex=
tension `collections` =0A=
is added in `php-src/ext/collections` in that RFC (for end users, that woul=
d mainly affect php.net manual organization).=0A=
=0A=
I plan to start voting in a few days.=0A=
=0A=
Also, iteration behavior has changed to https://wiki.php.net/rfc/deque#iter=
ation_behavior=0A=
=0A=
I also set up a WebAssembly demo to make it easier to look up how it curren=
tly behaves:=0A=
https://tysonandre.github.io/php-rfc-demo/deque/=0A=
=0A=
> A few questions for the particular API proposed here:=0A=
> =0A=
> 1. There would be the possibility of having an interface Deque that is=0A=
> backed by a VecDeque/ArrayDeque implementation. I'm not convinced this=0A=
> would actually make sense, but I wanted to throw it out there, given that=
=0A=
> the class is final (which is without any doubt the correct decision).=0A=
=0A=
Would `ArrayDeque` be referring to something with a hardcoded maximum size?=
=0A=
I can't think of a strong use case for that, and it's possible in userland =
by =0A=
wrapping `Collections\Deque` (with composition) and checking size on add op=
erations.=0A=
=0A=
> 2. How do set() / offsetSet() work with an out of range index? Is it=0A=
> possible to push an element with $deque[count($deque)] =3D x? I would ass=
ume=0A=
> that throws, but want to make sure. On a related note, why do we need bot=
h=0A=
> get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.=0A=
=0A=
They throw for out of range indexes. Offsets between 0 and count-1 are in r=
ange.=0A=
=0A=
offsetSet/offsetGet attempt to coerce values to integers to act as a drop-i=
n replacement =0A=
for arrays and Spl datastructures (e.g. for applications that deal with str=
ing inputs).=0A=
They throw TypeError if coercion fails, OutOfBoundsException for invalid of=
fsets.=0A=
=0A=
> 3. I believe it's pretty standard for Deque implementations to provide=0A=
> insert() / remove() methods to insert at any position (these would be O(n=
)).=0A=
=0A=
I agree it's pretty standard and something I'd want, =0A=
I was concerned about increasing the scope too much (before seeing if new c=
ollections would succeed)=0A=
and making this harder to review (and with more methods added to the design=
,=0A=
more possible objections to API decisions)=0A=
 =0A=
> 4. The design of getIterator() here is rather unusual, and deserves some=
=0A=
> additional justification. Normally, we let getIterator() see concurrent=
=0A=
> modifications to the structure, though the precise behavior is unspecifie=
d.=0A=
> I would also like to know how this will look like on a technical level (i=
t=0A=
> doesn't seem to be implemented yet?) This seems like something that will=
=0A=
> require a check on every write operation, to potentially separate the=0A=
> structure in some form.=0A=
=0A=
You have a good point - the proposed and implemented behavior have been upd=
ated.=0A=
It's now iterating over the original Deque, not an eager copy. https://wiki=
.php.net/rfc/deque#iteration_behavior=0A=
The Deque now tracks how the position of the front is moved by shift()/unsh=
ift() operations.=0A=
Iterators have their own positions that are unconditionally advanced by 1 i=
n `$iterator->next()` and the delta is =0A=
the iterator offset (`$iterator->key()`).=0A=
=0A=
The implemented behavior can be seen at https://tysonandre.github.io/php-rf=
c-demo/deque/=0A=
=0A=
> 5. The shift/unshift terminology is already used by our array API, but I'=
m=0A=
> not sure it's the most intuitive choice in the context of a deque. SplQue=
ue=0A=
> has enqueue() and dequeue(). Another popular option from other languages=
=0A=
> (which I would personally favor) is pushFront() and popFront().=0A=
=0A=
enqueue() is the same as push(), dequeue is the same as shift(). =0A=
It's still using the inherited unshift for adding to the front of the deque=
.=0A=
=0A=
In isolation, I'd prefer pushFront/popFront as names, but introducing more =
than one name for common operations=0A=
seemed like it wouldn't be worth the inconvenience for the potential of int=
roducing bugs in userland code when switching between collection objects,=
=0A=
making the standard library harder to learn/remember, etc.=0A=
=0A=
Thanks,=0A=
Tyson=0A=