zzzzzzzzzzzz Oct 5 2019 at 21:21

Рукоблудие вокруг ImmutableList в Java

5 min

12K

Прочитал статью "Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо" и подумал, что проблема отсутствия в Java неизменяемых списков, из-за которой грустит автор статьи, вполне решаема в ограниченных масштабах. Предлагаю свои мысли и куски кода на этот счёт.

(Это статья-ответ, прочитайте сначала исходную статью.)

UnmodifiableList vs ImmutableList

Первый возникший вопрос: для чего нужен UnmodifiableList, если есть ImmutableList? По итогам обсуждения в комментариях исходной статьи видятся две идеи касательно смысла UnmodifiableList:

метод получает UnmodifiableList, сам его менять не может, но знает, что содержимое может быть изменено другой нитью (и умеет это корректно обрабатывать)
другие нити не влияют, UnmodifiableList и ImmutableList получаются равнозначны для метода, но UnmodifiableList используется как более «легковесный».

Первый вариант представляется слишком редким на практике. Таким образом, если удастся сделать «лёгкую» реализацию ImmutableList, то UnmodifiableList становится не особо нужным. Поэтому в дальнейшем забудем про него и будем реализовывать только ImmutableList.

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

Будем реализовывать вариант ImmutableList:

API должно быть идентично API обычного List в «читающей» части. «Пишущая» часть должна отсутствовать.
ImmutableList и List не должны быть связаны отношениями наследования. Почему так – разбирается в исходной статье.
Реализацию имеет смысл делать по аналогии с ArrayList. Это самый простой вариант.
Реализация должна по возможности избегать операций копирования массивов.

Реализация ImmutableList

Сначала разбираемся с API. Исследуем интерфейсы Collection и List и копируем из них «читающую» часть в свои новые интерфейсы.

public interface ReadOnlyCollection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean containsAll(Collection<?> c);
}

public interface ReadOnlyList<E> extends ReadOnlyCollection<E> {
    E get(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    ReadOnlyList<E> subList(int fromIndex, int toIndex);
}

Далее создаём класс ImmutableList. Сигнатура аналогична ArrayList (но реализует интерфейс ReadOnlyList вместо List).

public class ImmutableList<E> implements ReadOnlyList<E>, RandomAccess, Cloneable, Serializable

Реализацию класса копируем из ArrayList и жёстко рефакторим, выкидывая оттуда всё связанное с «пишущей» частью, проверки на concurrent modification и т.д.

Конструкторы будут такие:

public ImmutableList()
public ImmutableList(E[] original)
public ImmutableList(Collection<? extends E> original)

Первый создаёт пустой список. Второй создаёт список, копируя массив. Без копирования тут не обойтись, если уж мы хотим добиться immutable. С третьим интереснее. Аналогичный конструктор ArrayList также копирует данные из коллекции. Мы будем поступать так же, за исключением случаев, когда orginal является экземпляром ArrayList или Arrays$ArrayList (это то, что возвращается методом Arrays.asList()). Можно смело считать, что эти случаи покроют 90% вызовов конструктора.

В этих случаях мы будем «красть» у original массив через reflections (есть надежда, что это быстрее, чем копировать гигабайтные массивы). Суть «кражи»:

добираемся до private поля original, хранящего массив (ArrayList.elementData)
копируем ссылку на массив к себе
помещаем в исходное поле null

protected static final Field data_ArrayList;
static {
    try {
        data_ArrayList = ArrayList.class.getDeclaredField("elementData");
        data_ArrayList.setAccessible(true);
    } catch (NoSuchFieldException | SecurityException e) {
        throw new IllegalStateException(e);
    }
}

public ImmutableList(Collection<? extends E> original) {
    Object[] arr = null;
    if (original instanceof ArrayList) {
        try {
            arr = (Object[]) data_ArrayList.get(original);
            data_ArrayList.set(original, null);
        } catch (@SuppressWarnings("unused") IllegalArgumentException | IllegalAccessException e) {
            arr = null;
        }
    }

    if (arr == null) {
        //либо получили не ArrayList, либо украсть массив не получилось - копируем
        arr = original.toArray();
    }

    this.data = arr;
}

В качестве контракта примем, что при вызове конструктора происходит конвертация изменяемого списка в ImmutableList. Исходный список после этого использовать нельзя. При попытке использования прилетает NullPointerException. Это гарантирует, что «украденный» массив не будет меняться и наш список будет действительно immutable (за исключением варианта, когда некто доберётся до массива через reflections).

Прочие классы

Предположим, что мы решили использовать ImmutableList в реальном проекте.

Проект взаимодействует с библиотеками: получает от них и отправляет им различные списки. В подавляющем большинстве случаев этими списками окажутся ArrayList. Описанная реализация ImmutableList позволяет быстро конвертировать получаемые ArrayList в ImmutableList. Требуется также реализовать конвертацию для отправляемых в библиотеки списков: ImmutableList в List. Для быстрой конвертации нужна обёртка ImmutableList, реализующая List, выкидывающая исключения при попытке записи в список (по аналогии с Collections.unmodifiableList).

Также проект сам как-то обрабатывает списки. Имеет смысл создать класс MutableList, представляющий изменяемый список, с реализацией на основе ArrayList. В этом случае можно отрефакторить проект, подставив вместо всех ArrayList класс, явно декларирующий намерения: либо ImmutableList, либо MutableList.

Нужна быстрая конвертация из ImmutableList в MutableList и обратно. При этом, в отличие от преобразования ArrayList в ImmutableList, исходный список портить мы уже не можем.

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

Конвертация «обратно» подразумевает получение snapshot-а содержимого MutableList на момент вызова метода. Опять же, в большинстве случаев без копирования массива не обойтись, но можно сделать обёртку для оптимизации случаев нескольких конвертаций, между которыми содержимое MutableList не менялось. Ещё один вариант конвертации «обратно»: некие данные собираются в MutableList, и когда сбор данных завершён, MutableList требуется преобразовать навсегда в ImmutableList. Реализуется также без проблем ещё одной обёрткой.

Итого

Результаты эксперимента в виде кода выложены тут

Реализован сам ImmutableList, описанное в разделе «Прочие классы» (пока?) не реализовано.

Можно считать, что посыл исходной статьи «неизменяемых коллекций в Java не будет» ошибочен.

Если есть желание, то вполне можно использовать подобный подход. Да, с небольшими костылями. Да, не в рамках всей системы, а только в своих проектах (хотя если многие проникнутся, то и в библиотеки оно постепенно подтянется).

Одно но: если есть желание… (Таити, Таити… Не были мы ни в какой Таити! Нас и здесь неплохо кормят.)

Tags:

Hubs: