Ещё раз об ImmutableList в Java

В своей предыдущей статье "Рукоблудие вокруг ImmutableList в Java" я предложил вариант решения поднятой в статье "Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо" проблемы отсутствия в Java неизменяемых списков.

Решение тогда было проработано только на уровне «есть такая идея», а реализация в коде была кривовата, поэтому и воспринято всё было несколько скептически. В данной статье предлагаю доработанный вариант решения. Логика использования и API доведены до приемлемого уровня. Реализация в коде – до уровня бета-версии.

Постановка задачи

Будем использовать определения из исходной статьи. В частности, это означает, что ImmutableList представляет собой неизменяемый список ссылок на какие-то объекты. Если эти объекты окажутся не immutable, то и список тоже не будет являться immutable объектом, несмотря на название. На практике это вряд ли кому-то помешает, но во избежание неоправданных ожиданий упомянуть надо.

Также понятно, что неизменяемость списка может быть «хакнута» посредством reflections, или создания своих классов в том же package с последующим залезанием в protected поля списка, или ещё чего-то подобного.

В отличие от исходной статьи, не будем придерживаться принципа «всё или ничего»: там автор, похоже, считает, что если проблема не может быть решена на уровне JDK, то и не стоит ничего делать. (На самом деле, ещё вопрос, «не может быть решена» или «у авторов Java не возникло желания её решить». Как мне кажется, всё-таки было бы возможно добавлением дополнительных интерфейсов, классов и методов привести существующие коллекции в более близкий к желаемому вид, хотя и менее красивый, чем если бы об этом задумались сразу. Но сейчас речь не об этом.)

Будем делать библиотеку, которая может успешно сосуществовать с имеющимися в Java коллекциями.

Основные идеи библиотеки:

• Есть интерфейсы ImmutableList и MutableList. Приведением типов получить один из другого невозможно.
• В своём проекте, который мы хотим улучшить с использованием библиотеки, все List-ы заменяем на один из этих двух интерфейсов. Если в какой-то момент без List-а обойтись не удаётся, то при первой же возможности преобразуем List из / в один из двух интерфейсов. То же относится к моментам получения / передачи данных в сторонние использующие List библиотеки.
• Взаимные преобразования между ImmutableList, MutableList, List должны выполняться как можно более быстро (то есть, без копирования списков, если это возможно). Без «дешёвых» преобразований туда-обратно вся затея начинает выглядеть сомнительно.

Следует отметить, что рассматриваются только List-ы, поскольку на данный момент в библиотеке реализованы только они. Но ничто не мешает дополнить библиотеку Set-ами и Map-ами.

API

ImmutableList

ImmutableList является наследником ReadOnlyList (который, как и в предыдущей статье, представляет собой скопированный интерфейс List, из которого выкинуты все изменяющие методы). Добавлены методы:

List<E> toList();
MutableList<E> mutable();
boolean contentEquals(Iterable<? extends E> iterable);

Метод toList обеспечивает возможность передачи ImmutableList в куски кода, ожидающие List. Возвращается обёртка, в которой все изменяющие методы возвращают UnsupportedOperationException, а остальные методы переадресуются к исходному ImmutableList.

Метод mutable преобразует ImmutableList в MutableList. Возвращается обёртка, в которой все методы переадресуются к исходному ImmutableList до момента первого изменения. Перед изменением обёртка отвязывается от исходного ImmutableList, копируя его содержимое во внутренний ArrayList, к которому далее и переадресуются все операции.

Метод contentEquals предназначен для сравнения содержимого списка с содержимым произвольного переданного Iterable (разумеется, осмысленной эта операция является только для тех реализаций Iterable, у которых есть какой-то внятный порядок элементов).

Отметим, что у нашей реализации ReadOnlyList методы iterator и listIterator возвращают стандартные java.util.Iterator / java.util.ListIterator. Эти итераторы содержат изменяющие методы, которые придётся глушить выдачей UnsupportedOperationException. Красивее было бы сделать свои ReadOnlyIterator, но в этом случае мы не смогли бы написать for (Object item : immutableList), что сразу испортило бы всё удовольствие от использования библиотеки.

MutableList

MutableList является наследником обычного List. Добавлены методы:

ImmutableList<E> snapshot();
void releaseSnapshot();
boolean contentEquals(Iterable<? extends E> iterable);

Метод snapshot предназначен для получения «снимка» текущего состояния MutableList в виде ImmutableList. «Снимок» сохраняется внутри MutableList, и если на момент следующего вызова метода состояние не изменилось, возвращается тот же экземпляр ImmutableList. Сохранённый внутри «снимок» сбрасывается при первом вызове любого изменяющего метода, либо при вызове releaseSnapshot. Метод releaseSnapshot может использоваться для экономии памяти, если есть уверенность, что «снимок» больше никому не понадобится, но изменяющие методы будут вызваны ещё не скоро.

Mutabor

Класс Mutabor предоставляет набор статических методов, являющихся «точками входа» в библиотеку.

Да, проект теперь называется «mutabor» (оно и созвучно с «mutable», и в переводе означает «я превращусь», что неплохо согласуется с идеей быстрых «превращений» одних типов коллекций в другие).

public static <E> ImmutableList<E> copyToImmutableList(E[] original);
public static <E> ImmutableList<E> copyToImmutableList(Collection<? extends E> original);
public static <E> ImmutableList<E> convertToImmutableList(Collection<? extends E> original);
public static <E> MutableList<E> copyToMutableList(Collection<? extends E> original);
public static <E> MutableList<E> convertToMutableList(List<E> original);

Методы copyTo* предназначены для создания соответствующих коллекций путём копирования предоставленных данных. Методы convertTo* предусматривают быстрое преобразование переданной коллекции в нужный тип, а если быстро преобразовать не удалось, то выполняют медленное копирование. Если быстрое преобразование прошло успешно, то исходная коллекция очищается, и предполагается, что в дальнейшем она не будет использоваться (хотя и может, но в этом вряд ли есть смысл).

Вызовы конструкторов объектов-реализаций ImmutableList / MutableList спрятаны. Предполагается, что пользователь имеет дело только с интерфейсами, сам такие объекты не создаёт, а для преобразования коллекций использует описанные выше методы.

Детали реализации

ImmutableListImpl

Инкапсулирует массив объектов. Реализация примерно соответствует реализации ArrayList, из которой выкинуты все изменяющие методы и проверки на concurrent modification.

Реализация методов toList и contentEquals также достаточно тривиальна. Метод toList возвращает обёртку, перенаправляющую вызовы к данному ImmutableList, медленного копирования данных не происходит.

Метод mutable возвращает MutableListImpl, созданный на базе данного ImmutableList. Копирования данных не происходит до тех пор, пока у полученного MutableList не будет вызван какой-либо изменяющий метод.

MutableListImpl

Инкапсулирует ссылки на ImmutableList и List. При создании объекта заполняется всегда только одна из этих двух ссылок, другая остаётся null.

protected ImmutableList<E> immutable;
protected List<E> list;

Неизменяющие методы перенаправляют вызовы к ImmutableList, если он не null, и к List в противном случае.

Изменяющие методы перенаправляют вызовы к List, предварительно выполнив инициализацию:

protected void beforeChange() {
    if (list == null) {
        list = new ArrayList<>(immutable.toList());
    }
    immutable = null;
}

Метод snapshot выглядит так:

public ImmutableList<E> snapshot() {
    if (immutable != null) {
        return immutable;
    }

    immutable = InternalUtils.convertToImmutableList(list);
    if (immutable != null) { //удалось выполнить быстрое преобразование
        //Преобразование очистило исходный список, обнуляем ссылку.
        //Список потом будет пересоздан копированием immutable в случае вызова изменяющего метода.
        list = null;
        return immutable;
    }

    immutable = InternalUtils.copyToImmutableList(list);
    return immutable; 
}

Реализация методов releaseSnapshot и contentEquals тривиальна.

Такой подход позволяет свести к минимуму количество копирований данных при «обыкновенном» использовании, заменив копирования на быстрые преобразования.

Быстрое преобразование списков

Быстрые преобразования возможны для классов ArrayList или Arrays$ArrayList (результат метода Arrays.asList()). На практике в подавляющем большинстве случаев попадаются именно эти классы.

Внутри данные классы содержат массив элементов. Суть быстрого преобразования состоит в получении ссылки на этот массив через reflections (это private поле) и замене её ссылкой на пустой массив. Это гарантирует, что единственная ссылка на массив останется у нашего объекта, и массив останется неизменным.

В прошлой версии библиотеки быстрые преобразования типов коллекций осуществлялись вызовом конструктора. При этом исходный объект коллекции портился (становился непригодным для дальнейшего использования), чего от конструктора подсознательно не ожидаешь. Теперь для преобразования используется специальный статический метод, а исходная коллекция не портится, а просто очищается. Таким образом, пугающее необычное поведение было устранено.

Проблемы с equals / hashCode

В коллекциях Java используется очень странный подход к реализации методов equals и hashCode.

Сравнение осуществляется по содержимому, что вроде бы и логично, но при этом не учитывается класс самого списка. Поэтому, например, ArrayList и LinkedList с одинаковым содержимым будут equals.

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator e2 = ((List) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

Таким образом, теперь абсолютно все реализации List обязаны иметь аналогичную реализацию equals (и, как следствие, hashCode). В противном случае можно получить ситуации, когда a.equals(b) && !b.equals(a), что нехорошо. Аналогичная ситуация и с Set-ами и Map-ами.

В приложении к библиотеке это означает, что реализация equals и hashCode для MutableList предопределена, и в такой реализации ImmutableList и MutableList с одинаковым содержимым не могут быть equals (поскольку ImmutableList не является List). Поэтому для сравнения содержимого были добавлены методы contentEquals.

Реализация методов equals и hashCode для ImmutableList сделана полностью аналогичной варианту из AbstractList, но с заменой List на ReadOnlyList.

Итого

Исходники библиотеки и тесты выложены по ссылке в виде maven-овского проекта.

На случай, если кто-то захочет использовать библиотеку, завёл группу в контактике для «обратной связи».

Использование библиотеки довольно очевидно, вот короткий пример:

private boolean myBusinessProcess() {
    List<Entity> tempFromDb = queryEntitiesFromDatabase("SELECT * FROM my_table");
    ImmutableList<Entity> fromDb = Mutabor.convertToImmutableList(tempFromDb);
    if (fromDb.isEmpty() || !someChecksPassed(fromDb)) { return false; }
    //...
    MutableList<Entity> list = fromDb.mutable(); //time to change
    list.remove(1);
    ImmutableList<Entity> processed = list.snapshot(); //time to change ended
    //...
    if (!callSideLibraryExpectsListParameter(processed.toList())) { return false; }
    for (Entity entity : processed) { outputToUI(entity); }
    return true;
}

Всем удачи! Шлите багрепорты!