Дженерик коллекции в PHP

Столкнулся с проблемой нормальной реализации коллекций в PHP. Доктриновские коллекции мутабельны и инвариантны. PSL коллекции инвариантны. Нигде не видел непустых коллекций. Везде меня что-то не устраивало и было принято решение написать свою open source реализацию иммутабельных коллекций с ковариантными темплейт-параметрами и выстроенной иерархией пустых и непустых коллекций. В качестве статического анализатора был выбран Psalm.

Иерархия коллекций

Коллекции делятся по возможности содержать пустой список элементов на Collection и NonEmptyCollection.

Получается две иерархии коллекций: обычные коллекции и непустые коллекции.

Обычные коллекции (интерфейс Collection) делятся на интерфейсы Seq, Map и Set.

• Seq — это сокращение от Sequence. Упорядоченный набор элементов с порядковым номером в рамках коллекции. Типичный представитель Seq — это связный список LinkedList.

• Map представляет набор пар ключ-значение. Типичный представитель HashMap.

• Set — это множество уникальных элементов. Типичный представитель HashSet.

Непустые коллекции (интерфейс NonEmptyCollection) делятся на интерфейсы по такому же принципу, как и обычные коллекции, но у них добавляется префикс NonEmpty к соответствующим названиям классов и интерфейсов.

Обычные коллекции

Collection<TV> -> Seq<TV>     -> LinearSeq<TV>   -> LinkedList<TV> Collection<TV> -> Seq<TV>     -> IndexedSeq<TV>  -> ArrayList<TV> Collection<TV> -> Set<TV>     -> HashSet<TV> Collection<TV> -> Map<TK, TV> -> HashMap<TK, TV>

Непустые коллекции

NonEmptyCollection<TV> -> NonEmptySeq<TV> -> NonEmptyLinearSeq<TV>  -> NonEmptyLinkedList<TV> NonEmptyCollection<TV> -> NonEmptySeq<TV> -> NonEmptyIndexedSeq<TV> -> NonEmptyArrayList<TV> NonEmptyCollection<TV> -> NonEmptySet<TV> -> NonEmptyHashSet<TV>

Типобезопасность

В библиотеке написаны плагины для статического анализатора Psalm, которые позволяют производить рефайнинг типов элементов и ключей коллекций при выполнении таких операций, как filter и filterNotNull.

<?php  /**  * Выведенный тип NonEmptyLinkedList<1|2|3>  */ $collection = NonEmptyLinkedList::collectNonEmpty([1, 2, 3]);  /**  * Выведенный тип NonEmptyLinkedList<int>  *   * Литеральные типы пропали после трансформации элементов коллекции   * Но NonEmpty префикс коллекции сохранился,   * Т.к. количество элементов в коллекции не изменилось  */ $mappedCollection = $collection->map(fn($elem) => $elem - 1);  /**  * Выведенный тип LinkedList<positive-int>  *   * NonEmpty префикс пропал после фильтрации  * Т.к. количество элементов могло уменьшиться   * И коллекция могла стать пустой   */ $filteredCollection = $mappedCollection->filter(fn(int $elem) => $elem > 0);

<?php  /**  * Выведенный тип non-empty-list<Foo|null|Bar>  */ $source = [new Foo(1), null, new Bar(2)];  /**  * Выведенный тип ArrayList<Foo|Bar>  *   * Null был исключен из типа элементов коллекции  *   * NonEmpty префикс коллекции так же пропал после фильтрации  * Т.к. количество элементов могло уменьшиться   * И коллекция могла стать пустой   */ $withoutNulls = NonEmptyArrayList::collectNonEmpty($source)->filterNotNull();  /**  * Выведенный тип ArrayList<Foo>  *   * Bar был исключен из типа элементов коллекции  */ $onlyFoos = $withoutNulls->filter(fn($elem) => $elem instanceof Foo);

Ковариантность

Тайп-параметры коллекций ковариантны, в отличие от коллекций доктрины и PHP Standart Library (PSL).

<?php  class User {} class Admin extends User {}  /** * @param NonEmptyCollection<User> $collection */ function acceptUsers(NonEmptyCollection $collection): void {}  /**   * @var NonEmptyLinkedList<Admin> $collection   */ $collection = NonEmptyLinkedList::collectNonEmpty([new Admin()]);  /**  * Можно передавать коллекцию админов вместо коллекции пользователей  * Из-за ковариантности тайп-параметра коллекции  */ acceptUsers($collection);

Иммутабельность

Коллекции не изменяются после создания. Все мутирующие операции над коллекциями возвращают новые независимые коллекции.

<?php  $originalCollection = LinkedList::collect([1, 2, 3]);  /**  * $originalCollection не модифицируется  * И создаётся новая коллекция на основе предыдущей  */ $prependedCollection = $originalCollection->prepended(0);  /**  * $prependedCollection не модифицируется  * И создаётся новая коллекция на основе предыдущей  */ $mappedCollection = $prependedCollection->map(fn(int $elem) => $elem + 1);

Null-безопасность

Использование монады Option позволяет избежать null pointer исключений. В либе вместо null возвращается всегда либо Some, либо None .

<?php  /**  * @var Collection<int> $emptyCollection   */ $emptyCollection = getEmptyCollection();  /**  * Операция reduce предполагает работу с непустой коллекцией  *   * Вместо того, чтобы кидать исключение или возвращать null,   * если в коллекции нет элементов,   * в библиотеке в таких случаях возвращается   * экземпляр монады Option<T> (Some<T>|None)  *  * Такой подход позволяет получить значение   * или продолжить вычисление без проверок на null    */ $resultWithDefaultValue = $emptyCollection     ->reduce(fn(int $accumulator, int $element) => $accumulator + $element)     ->getOrElse(0);

<?php  class Order {     public function __construct(public int $id, public int $price) {} }  /**  * In-memory хранилище проиндексированных по ID заказов  */ $ordersInMemoryStorage = HashMap::collect([     [$orderId1 = rand(), new Order(id: $orderId1, price: 0)],     [$orderId2 = rand(), new Order(id: $orderId2, price: 999)], ]);  /**  * Безопасное деление  *   * Эту операцию можно вставить в качестве промежуточного элемента   * цепочки вычислений с помощью метода Option::flatMap  *   * @return Option<float>  */ function div(int $dividend, int $divisor): Option {     return 0 === $divisor         ? Option::none()         : Option::some($dividend / $divisor); }  /**  * Поиск по ключу в Map-коллекции возвращает монаду Option  *   * Это позволяет продолжить описывать цепочку вычислений   * с помощью map, flatMap и подобных методов класса Option.  *   * Цепочка вычислений не продолжится,   * если элемент не найден в хранилище  * или если произошло деление на ноль  *   * В случае, если на каком-то этапе вычисления произошла ошибка,  * то при вызове getOrElse(0) возвратится 0,   * вместо успешного результата вычисления  */ $ordersInMemoryStorage     ->get($orderId1)     ->map(fn(Order $order): int => $order->price)     ->flatMap(fn(int $price): Option => div(1, $price))     ->getOrElse(0);

Связь HashSet, HashMap и HashContract

HashSet под капотом использует HashMap.

Чем отличается HashMap от обычного массива в PHP? Ключи массивов в PHP могут быть целыми числами или строками. Тип ключей в HashMap ничем не ограничен. Это вполне могут быть экземпляры классов. Numeric-string ключи в массивах PHP преобразуются в целочисленные ключи. В HashMap такого не происходит и элемент с ключем "1" нельзя достать по ключу 1.

HashMap проверяет, не реализует ли объект, который используется в качестве ключа, интерфейс HashContract. Если реализует, то используются реализуемые в классе ключа-объекта методы hashCode и equals, чтобы находить элементы коллекции по ключам.

<?php  /**  * Если реализовать HashContract (методы hashCode и equals),  * то можно использовать объекты класса  * в качестве ключей в HashMap   * и в качестве элементов коллекции HashSet  */ class Foo implements HashContract {     public function __construct(public int $a, public bool $b = true)     {     }      /**      * Сравнивает на равенство текущий объект       * с переданным аргументом      * по типу и значимым полям класса      *      * Используется, чтобы находить элементы в бакете       * по ключу-объекту данного класса      */     public function equals(mixed $rhs): bool     {         return $rhs instanceof self             && $this->a === $rhs->a             && $this->b === $rhs->b;     }      /**      * Хэш значимых полей класса      *       * Используется, чтобы попадать в нужный бакет       * в HashMap'е      */      public function hashCode(): string     {         return md5(implode(',', [$this->a, $this->b]));     } }  /**  * Сборка коллекции происходит с помощью пар ключ-значение,  * которые передаются в виде массивов вида array{TKey, TValue}  */ $hashMap = HashMap::collect([     [new Foo(1), 1], [new Foo(2), 2],     [new Foo(3), 3], [new Foo(4), 4] ]);  /**  * Пример использования коллекции HashMap  * и чейнинга операций над коллекцией  */ $hashMap     ->map(fn($elem) => $elem + 1)     ->filter(fn($elem) => $elem > 2)     ->reindex(fn($elem, Foo $key) => $key->a)     ->fold(0, fn(int $acc, array $pair) => $acc + $pair[1]); // 3+4+5=12  /**  * При сборке коллекции  * дублирующиеся элементы будут удалены  *   * Останутся только Foo(1), Foo(2), Foo(3), Foo(4)  */ $hashSet = HashSet::collect([     new Foo(1), new Foo(2), new Foo(2),      new Foo(3), new Foo(3), new Foo(4), ]);  /**  * Пример использования коллекции HashSet  * и чейнинга операций над коллекцией  */ $hashSet     ->map(fn(Foo $elem) => $elem->a)     ->filter(fn(int $elem) => $elem > 1)     ->reduce(fn($acc, $elem) => $acc + $elem)     ->getOrElse(0); // 9