Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:116214
MIME-Version: 1.0
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>
In-Reply-To: <CAAKU0uk6Wvd5aPQ4qzJTQiHpuLCM999Wsm7qrjWMonF7q+SuDw@mail.gmail.com>
Date: Mon, 4 Oct 2021 14:04:28 +0200
Message-ID: <CAF+90c84NGyL2Kq1k0d=V_G0K96wCvdfqsvtrTYkneVvpHSFmw@mail.gmail.com>
To: Levi Morrison <levi.morrison@datadoghq.com>
Cc: PHP internals <internals@lists.php.net>
Content-Type: multipart/alternative; boundary="000000000000fc947b05cd85b7bb"
Subject: Re: [PHP-DEV] Adding `final class Deque` to PHP
From: nikita.ppv@gmail.com (Nikita Popov)

--000000000000fc947b05cd85b7bb
Content-Type: text/plain; charset="UTF-8"

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

--000000000000fc947b05cd85b7bb--