Newsgroups: php.internals Path: news.php.net Xref: news.php.net php.internals:116222 Return-Path: Delivered-To: mailing list internals@lists.php.net Received: (qmail 56823 invoked from network); 4 Oct 2021 22:03:06 -0000 Received: from unknown (HELO php-smtp4.php.net) (45.112.84.5) by pb1.pair.com with SMTP; 4 Oct 2021 22:03:06 -0000 Received: from php-smtp4.php.net (localhost [127.0.0.1]) by php-smtp4.php.net (Postfix) with ESMTP id EE1661804C5 for ; Mon, 4 Oct 2021 15:47:24 -0700 (PDT) X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on php-smtp4.php.net X-Spam-Level: X-Spam-Status: No, score=-1.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FORGED_HOTMAIL_RCVD2, FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,RCVD_IN_MSPIKE_H2, SPF_HELO_PASS,SPF_PASS autolearn=no autolearn_force=no version=3.4.2 X-Spam-ASN: AS8075 40.80.0.0/12 X-Spam-Virus: No X-Envelope-From: Received: from NAM12-BN8-obe.outbound.protection.outlook.com (mail-bn8nam12olkn2016.outbound.protection.outlook.com [40.92.21.16]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by php-smtp4.php.net (Postfix) with ESMTPS for ; Mon, 4 Oct 2021 15:47:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=m0dd0wIG6Q2irB3yWl0hYO98iXPWrY5oFMHYJpj006IvXXJObgw36vLATmNP4xig1zwqDG2DbIAbZ8yHbvU8vY+sGknQeaCSzyHa5GmnViNnp+HBGbDLAnMgncKIE2+rgrNaMwKVONGuyuXUzSGKmEnwWZaFLdFYgdil4Qs2N0aeiSpaxS6ovEPLZx3sJc7iJV08tOgFHcbLLzG9PBy9VTrEFyYrKUExUNzGYOUJUzMJZpq9UffBURg/3a6ymwyAIYpNk6SPvlv5uBf0+Cuulwi20ckYvMB5+Xl5I3T+MWuCaPv1WtBAYMHySxcZsb8kYzMCin4TyE+Zuu23PP58Sw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=RNjShPUYnnxCeQlG1XATZHTDwOwU5pML1Ax+Xz0bBdk=; b=L3g3G3hueBiGfefIR9YcBxjrff2sNFAPWtI4JRyTNmDn0wKsbvgXJJy5n/OKHaiOflLenh8b7vMxlSZJztTkghnTqsLQmj4YOG5HKMCkR/kKbQM1QGzXtroGB6nqrKqrv50kYSQt1tiYBhejuALk+MWmd/RcSbtbaFjttwIdgtXR5he25+fqhcgIExThN8W0RK5qBtA/lk4FAyWbvdliW6VY9ISMXlR5MO/7zpQi0ZTIhmXIcw2xrKsnRDC9OsDdPDVaZ1f6D1xNrPsUFWQnwG+LuZfKo2bBRzik/zFhQu50yToGu5+7LYO+AJ16g6BcKS4iJeUb17wbqAkwrVVExw== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=none; dmarc=none; dkim=none; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=hotmail.com; s=selector1; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=RNjShPUYnnxCeQlG1XATZHTDwOwU5pML1Ax+Xz0bBdk=; b=dMWpY+ZCZ6nLAX6Fllg16fkrYD9LdkjIG8qj7twX1Swk8oxt3GKKKG6cJB8yXaRJGexZP2yQWwT1o33DHIto2TDJAU3R4AtiO3b6REwmRDq+G2JujX0JaekUA7KTMItJO8NPdUcTohub/C/kgFCnfkE+wn7sNUwrcWg+Lu6q6mV4/ieBz/7Ga9dpNh+V7ZmFHKTQUWBTfzBRbzMeirCy3BSUWaHCf2fH1mNjZ+bk1bNZ6HsD4tGhnyITNzDtE7eQeGbfmSKkPflvS/UUW7+ymgEYOJhrBtn7T5M4FmYa3Wqldfkeitnpeo1UiboC8oNHiQdWftY7GKvPPhF3WlPYCw== Received: from DM5PR17MB1481.namprd17.prod.outlook.com (2603:10b6:3:147::17) by DM6PR17MB2347.namprd17.prod.outlook.com (2603:10b6:5:ad::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4566.16; Mon, 4 Oct 2021 22:47:20 +0000 Received: from DM5PR17MB1481.namprd17.prod.outlook.com ([fe80::e832:bd41:4114:64d2]) by DM5PR17MB1481.namprd17.prod.outlook.com ([fe80::e832:bd41:4114:64d2%11]) with mapi id 15.20.4566.022; Mon, 4 Oct 2021 22:47:20 +0000 To: "internals@lists.php.net" Thread-Topic: [PHP-DEV] Adding `final class Deque` to PHP Thread-Index: AQHXraUxaK1dZ0niuECOJlLUpHNcpaut5O0AgAA5JgCAAJnxgIAABFYAgAAl9YCAABrsgIAT13AAgACw9q8= Date: Mon, 4 Oct 2021 22:47:20 +0000 Message-ID: References: <67BFE5C6-3C3F-4309-97A2-14CA0D8C3B3B@newclarity.net> <7BEE0406-3CAE-4E83-A196-F9F608BE8D17@newclarity.net> In-Reply-To: Accept-Language: en-CA, en-US Content-Language: en-CA X-MS-Has-Attach: X-MS-TNEF-Correlator: suggested_attachment_session_id: 85ee47f0-4b3e-a1cd-9778-57a7fb506f3c x-ms-exchange-messagesentrepresentingtype: 1 x-tmn: [l0V9ioI6YIR05FYNHSgeQap0CjQBCoFdFoOgU1g7M45Bm6lIMsftJMcVWf6R7VMhsYTlcVxiE+0=] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: d0f8ce77-b01d-43e8-8fb2-08d98788ecaf x-ms-traffictypediagnostic: DM6PR17MB2347: x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 8piJlRuCacIgLIEKoLSIWpSLjJycNCLCLM0n1HpjQ0IFzcDAVUbXsqp5IVct/hKf3PtDtSxMITbM0qTvIh0TdAYyU49EgYd3q7bMtgRQnrVR9DpIKLOuGsUTwji5vY3TDtTdc1MXene/8TLzBYtq56v/ldI8CA8NsONj3M1NKegZw0KktlDsOtUymyAOGymU28PUZYRpbKuxxdK/TT6yK6B/UhnB6DX8I2vgiI8StOqWIJdEN2XRjiqwkQCTdvzEGzRLeoU6sKm733Pdn8HO/Y3sZKbLvgfdmD/iq9jrcBA+kQDKke4BCSjY0GyJsCBF094/u5etlsuYjQP+QCdrza4IkbYhQSeg77HTfno6dzcs3XZTV5ka4nOqtiPhoiPbq6yEzHQaYtDOUyg0IE0Obv39/5cENojV01Ejsys0qqeK/axmjKALZtOz0K9PkPsZH+ejzQbhikLAAYFloahXahvjdPuTtmynBGryvEK6hkAkGS5K8G+OFuEkT4H/Ogo+stykb8RPTG2HKqH/pbUyoQ== x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: FR7JWaOpv4aPomBMb1rCpoLVxgdjqYsOh/gF6kcyrBF3L2KwJT5Gpt6hl2vNGeACnKcgDoqXeABnDgWWUe9q15ztKo0mGoHk08b7aDvA5xuZBGKUF9ZfTsHQvE2GNKqLrElv0YPKplw25Gjxbumh7IbmKHy3IkP6CVrJDLtLGnYr0OJMIpNOSHduS9PhHU8vKg3vVQxhmrVRju1h6hY6zg== x-ms-exchange-transport-forked: True Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: sct-15-20-3174-20-msonline-outlook-21df5.templateTenant X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: DM5PR17MB1481.namprd17.prod.outlook.com X-MS-Exchange-CrossTenant-RMS-PersistedConsumerOrg: 00000000-0000-0000-0000-000000000000 X-MS-Exchange-CrossTenant-Network-Message-Id: d0f8ce77-b01d-43e8-8fb2-08d98788ecaf X-MS-Exchange-CrossTenant-originalarrivaltime: 04 Oct 2021 22:47:20.5056 (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: DM6PR17MB2347 Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP From: tysonandre775@hotmail.com (tyson andre) Hi Nikita Popov,=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= Do you mean ArrayDeque for a hardcoded max capacity?=0A= I'm also not convinced there's a use case.=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= It isn't possible to set an out of range index - both throws `\OutOfBoundsE= xception`=0A= =0A= In order to support the ArrayAccess `$deque[$offset] =3D $value;` or `$dequ= e[$offset]` shorthand,=0A= the offsetGet/offsetSet needed to be implemented to follow conventions.=0A= (because of ArrayAccess, offsetGet must accept mixed offsets)=0A= =0A= Those aren't type safe, though, so get()/set() are provided for a type safe= alternative=0A= that will throw a TypeError for use cases that would benefit from runtime t= ype safety.=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= https://www.php.net/manual/en/class.splqueue.php didn't offer that function= ality. =0A= =0A= https://www.php.net/manual/en/class.ds-deque.php did, apparently.=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= =A0=0A= The original plan was to copy the entire array on iterator creation,=0A= to imitate the immediate copy nature of foreach on arrays.=0A= =0A= This was assuming that `foreach` over a Deque without removing elements wou= ld be a rare use case.=0A= =0A= That may have been a mistake since `foreach (clone $deque as $key =3D> $val= ue)` can be done to explicitly do that.=0A= There're around 4 approaches I could take with different tradeoffs=0A= =0A= 1. Iterate over $offset =3D 0 and increment offset in calls to InternalIter= ator->next() until exceeding the size of the deque, not copying the deque.= =0A= =0A= =A0 =A0That's the **actual** current implementation, but would be unintuiti= ve with shift()/unshift()=0A= =0A= =A0 =A0This would repeat elements on unshift(), or skip over elements when = shift() is called.=0A= =0A= =A0 =A0The current implementation of `Ds\Deque` seems to do the same thing,= but there's a similar discussion in its issue tracker in=A0https://github.= com/php-ds/ext-ds/issues/17=0A= =0A= =0A= 2. Similar iteration behavior, but also have it relative to a uint64 indica= ting the number of times elements were added to the front of the deque minu= s the number of elements were removed from the back of the deque.=0A= =0A= =A0 =A0 (e.g. if the current Deque internalOffset is 123, the InternalItera= tor returned by getOffset would start with an offset of 123 and increase it= when advancing.=0A= =A0 =A0 Calls to shift would raise the Deque internalOffset, calls to unshi= ft would decrease it (by the number of elements).=0A= =A0 =A0 This would be independent of the circular buffer offset.=0A= =A0 =A0 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)=0A= =0A= 3. Behave as if the entire Deque was copied when iteration starts (either b= y actually copying everything or by copy on write).=0A= =0A= =A0 =A0That was the **planned** implementation documented in the RFC, but w= ould be inefficient for iterations that end early and use a lot of memory f= or large Deques.=0A= =0A= 4. Throw if attempting to change the size of the `Deque` while a foreach is= in progress.=0A= =0A= =A0 =A0The semantics of that would be annoying, e.g. handling `clear()` or = `shift()`, and the exception getting thrown would be unexpected.=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= My original name idea was pushBack/popBack/pushFront/popFront but I had dec= ided against proposing brand new terms=0A= for functionality that already had terms in php-src.=0A= It would also be inconsistent with proposed names for `Vector` if that was = also added.=0A= =0A= https://www.php.net/manual/en/class.ds-deque.php and SplDoublyLinkedList ha= d done the same thing=0A= =0A= enqueue and dequeue don't have a good term for enqueueing on the opposite s= ide.=0A= =0A= - It would make it easier to learn the language to have fewer terms and mig= rate code using SplDoublyLinkedList or arrays=0A= - push()/shift() are also shorter names than pushBack/popFront()=0A= =0A= Thanks,=0A= Tyson=0A= =0A= =0A= From: Nikita Popov =0A= Sent: October 4, 2021 8:04 AM=0A= To: Levi Morrison =0A= Cc: PHP internals =0A= Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP =0A= =A0=0A= On Tue, Sep 21, 2021 at 11:05 PM Levi Morrison via internals <=0A= internals@lists.php.net> wrote:=0A= =0A= > 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 same= =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 only= =0A= realize a small part of it in this version.=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= 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 assum= e=0A= that throws, but want to make sure. On a related note, why do we need both= =0A= get()/set() and offsetGet()/offsetSet()? These APIs seem redundant.=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= 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 unspecified.= =0A= I would also like to know how this will look like on a technical level (it= =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= 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. SplQueue= =0A= has enqueue() and dequeue(). Another popular option from other languages=0A= (which I would personally favor) is pushFront() and popFront().=0A= =0A= Regards,=0A= Nikita=