This is an old revision of the document!
Straw poll: Naming pattern to use for Deque
- Version: 0.1
- Date: 2022-01-05
- Author: Tyson Andre, email@example.com
- Status: Under Discussion
- First Published at: http://wiki.php.net/rfc/deque_straw_poll
Because the naming choice for new datastructures is a question that has been asked about many times, this straw poll has been created to gather feedback on the naming pattern to use for future additions of datastructures to PHP, with the arguments for and against the naming pattern.
https://wiki.php.net/rfc/namespaces_in_bundled_extensions recently passed. It permits using the same namespace that is already used in an extension, but offers guidance in choosing namespace names and allows for using namespaces in new categories of functionality.
The planned options are:
\Deque, the name currently used in the RFC/implementation. See https://wiki.php.net/rfc/deque#global_namespace
This was my preference because it was short, making it easy to remember and convenient to use.
\Collections\Deque- the singular form is proposed because this might grow long-term to contain not just collections, but also functionality related to collections in the future(e.g. helper classes for building classes (e.g. ImmutableSequenceBuilder for building an ImmutableSequence), global functions, traits/interfaces, collections of static methods, etc.
(especially since https://wiki.php.net/rfc/namespaces_in_bundled_extensions prevents more than one level of namespaces)
\SplDeque, similar to datastructures added to the Spl in PHP 5.3.
(I don't prefer that name because SplDoublyLinkedList, SplStack, and SplQueue are subclasses of a doubly linked list with poor performance, and this name would easily get confused with them. Also, historically, none of the functionality with that naming pattern has been final.
However, good documentation (e.g. suggesting *Deque instead where possible in the manual) would make that less of an issue.)
See https://wiki.php.net/rfc/deque#lack_of_name_prefix (and arguments for https://externals.io/message/116100#116111)
While there is considerable division in whether or not members of internals want to adopt namespaces, I hope that the final outcome of the poll will be accepted by members of internals as what the representative of the majority of the members of internals (from diverse backgrounds such as contributors/leaders of userland applications/frameworks/composer libraries written in PHP, documentation contributors, PECL authors, php-src maintainers, etc. (all of which I expect are also end users of php)) want to use as a naming choice in future datastructure additions to PHP. (and I hope there is a clear majority)
What is the Deque RFC?
In computer science, a double-ended queue (abbreviated to deque, pronounced deck, like “cheque”) is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail).
(omitted sections, see article)
The dynamic array approach uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant-time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant-time insertion/removal at both ends, instead of just one end. Three common implementations include:
- Storing deque contents in a circular buffer, and only resizing when the buffer becomes full. This decreases the frequency of resizings.
- (omitted, see article)
Similarly to deques in other languages (such as Python collections.deque, C++ std::deque, Rust std::collections::VecDeque, etc.) this is backed by a memory-efficient representation with good cache locality and provides constant amortized-time push/pop/shift/unshift operations. (this RFC's implementation is a circular buffer represented as a raw C array of values with a size, offset, and capacity)
What is the planned future scope?
The planned future scope is to add new more efficient datastructures such as Deque, Vector, Set, Map, SortedSet/SortedMap, and potentially immutable data structures to php. Those would differ from existing classes in the spl in several ways:
- Be final classes and avoid unpredictable behaviors. Extensibility has been a cause of performance issues and unexpected bugs historically, and makes code harder to reason about.
- Forbid dynamic properties.
Arguments for/against Deque
This was my preference because it was short, making it easy to remember and convenient to use. The majority of existing functionality uses the global namespace.
https://wiki.php.net/rfc/namespaces_in_bundled_extensions recently passed. It permits using the same namespace that is already used in an extension (in this case, the global namespace), but offers guidance in choosing namespace names and allows for using namespaces in new categories of functionality.
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
Arguments for/against Collections\Deque
This seems like a reasonable choice of name for collections (Deque, and possible future additions such as Vector, Set, Map, Sorted Sets/Maps, etc.
https://wiki.php.net/rfc/namespaces_in_bundled_extensions also allows using sub-namespaces and that may be used for things that aren't strictly collections, e.g.
Arguments for/against SplDeque
This would follow the naming convention used by other collections already existing in the SPL.
I believe this would be detrimental, though - a
SplDeque would be confused way too easily with SplDoublyLinkedList and it subclasses SplQueue/SplStack - switching from a SplDeque to a SplStack (linked list) would suddenly make operations such as ArrayAccess much slower and use more memory due to needing to traverse a linked list. See https://wiki.php.net/rfc/deque#benchmarks
This vote will influence the name choice for the Deque RFC
This is a ranked-choice poll (following STV) between the naming alternatives.
With STV you SHOULD rank all the choices in order (but are not required to). Don't pick the same option more than once, as that invalidates your vote.
Several suggestions that have been brought up in the past are forbidden by the accepted policy RFC (https://wiki.php.net/rfc/namespaces_in_bundled_extensions) and can't be used in an RFC.
Standard\are forbidden: “Because these extensions combine a lot of unrelated or only tangentially related functionality, symbols should not be namespaced under the Core, Standard or Spl namespaces.
Instead, these extensions should be considered as a collection of different components, and should be namespaced according to these.”
- Namespace names should generally follow CamelCase.
DataStructureseems overly generic, and includes much more than collections of values. See https://en.wikipedia.org/wiki/Data_structure
Ds\is already used by the php-ds extension.