Прочитал статью "Неизменяемых коллекций в 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 не будет» ошибочен.
Если есть желание, то вполне можно использовать подобный подход. Да, с небольшими костылями. Да, не в рамках всей системы, а только в своих проектах (хотя если многие проникнутся, то и в библиотеки оно постепенно подтянется).
Одно но: если есть желание… (Таити, Таити… Не были мы ни в какой Таити! Нас и здесь неплохо кормят.)
Комментарии (17)
smple
06.10.2019 00:38к сожалению это не совсем имутабельный объект получится.
Дело в том что объект имутабельный если он не меняет свое состояние, элементы списка это тоже часть состояния и они должны быть неизменны то есть тоже имутабельны, если на это забить то получится следующее
# в виде псевдо кода 1. создадим текущую дату в переменную current 2. поместим current в ImmutableList 3. достаним первый элемент списка и выведем дату 4. обратимся к переменной current и изменим дату 5. повторим пункт 3 и получим другой результат
И мы получили что наш "имутабельный" объект вызывая один и тот же метод с одинаковыми аргументами возвращает разное, чего быть не должно.
Это еще не считая шаманств с рефлекшен.
TheShock
06.10.2019 00:48Настоящий иммутабельный список работает только с иммутабельными данными, это да
zzzzzzzzzzzz Автор
06.10.2019 09:29Да, получается не полностью иммутабельный объект, а иммутабельный список потенциально мутабельных объектов (как в определениях исходной статьи).
Получить «иммутабельный список иммутабельных объектов» — задача интересная, но вряд ли на Java решаемая. Хотя если в списке лежат только голые данные в виде POJO, то можно было бы сделать для них иммутабельные копии через рефлекшены. Но это очень долго и уже поэтому не нужно.smple
07.10.2019 13:52ну я не совсем согласен в изначальной статье на тему имутабельный список может содержать мутабельные объекты, тогда зачем нужен такой "имутабельный" список? вопрос конечно же философский.
Мне привычней классическая терминалогия, мутабельных или имутабельных объектов.
VolCh
09.10.2019 09:11Есть вполне практические применения у иммутабельной коллекции мутабельных объектов — не нужно отслеживать добавление-удаление элементов (как правило путём клонирования оригинальной коллекции и хранения её где-то под капотом) — эти операции выносятся наружу и инвалидируют исходную коллекцию, а иммутабельность гарнтирует, что обойти их нельзя.
lam0x86
06.10.2019 01:13+21) Если не указано обратного, по умолчанию считается, что код не предназначен для вызова в многопоточном режиме. Поэтому, вы можете принимать на вход UnmodifiableList, не боясь, что он изменится извне. Если он изменяется, то тот программист, что вызывает ваш метод, сам дурак, что не смог предоставить стабильную коллекцию, это не ваша проблема.
2) Ваша реализация похожа на грабительство — Вы отбираете массив у вызывающего объекта. Это антипаттерн.
3) На самом деле, ImmutableList-ы в большинстве библиотек построены на основе сбалансированных деревьев, поэтому, изменение листа проходит за O(log(N)).
4) «Можно считать, что посыл исходной статьи «неизменяемых коллекций в Java не будет» ошибочен.»
На основе Вашей статьи такого вывода сделать нельзя. Вы придумали кривой велосипед, который никто в здравом уме не примет за стандарт. Поэтому, изначальный посыл автора статьи остаётся актуальным.zzzzzzzzzzzz Автор
06.10.2019 09:482) Ваша реализация похожа на грабительство — Вы отбираете массив у вызывающего объекта. Это антипаттерн.
Обоснуете, почему «анти»? Например, из ORM вы получилиArrayList<MyEntity>, понимаете, что меняться он не будет, и хотите дальше в своём коде использовать его какImmutableList<MyEntity>. Преобразовали, старый список ушёл, новый появился. Чем плохо?
3) На самом деле, ImmutableList-ы в большинстве библиотек построены на основе сбалансированных деревьев, поэтому, изменение листа проходит за O(log(N)).
Вот это вообще не понял. Какие изменения ImmutableList-а?
4) Вы придумали кривой велосипед, который никто в здравом уме не примет за стандарт.
Кривой он только тем, что использует рефлекшены (если вдруг поменяют название поляArrayList#elementData— поломается). Естественно, если бы это делали авторы Java, можно было бы без рефлекшенов обойтись.mayorovp
06.10.2019 15:54Вот это вообще не понял. Какие изменения ImmutableList-а?
Ну хотя бы вот такие:
interface ImmutableList<E> extends ReadOnlyList<E> { ImmutableList<E> add(E item); ImmutableList<E> add(int index, E item); ImmutableList<E> remove(E item); ImmutableList<E> remove(int index); ImmutableList<E> set(int index, E item); }zzzzzzzzzzzz Автор
06.10.2019 21:54-1Это «создать копию списка с добавленным элементом»? Нет-нет, вот такого точно не надо. А то потом это обязательно будет по запарке / рукозадости запихнуто в какой-нибудь гигантский элементодобавительный цикл, и наступит всеобщее счастье. Считаю, что подобные сомнительные моменты должны более явно в API выражаться: нужны изменения — сконвертировали ImmutableList в MutableList, внесли изменения, потом сконвертировали обратно (если в итоге ImmutableList нужен).
mayorovp
06.10.2019 22:09А в чём проблема вызвать в цикле метод, работающий за O(log N)?
zzzzzzzzzzzz Автор
06.10.2019 22:41Если он будет работать за O(log N), то не проблема (хотя всё равно менее приятно, чем О(1) в обычном списке). Вот только и написать такое очень не просто, и реализация получится, видимо, на базе деревьев, а это означает, что памяти на «накладные расходы» уйдёт в разы больше по сравнению с простым массивом ссылок. А пользы — пшик.
mayorovp
06.10.2019 15:58Например, из ORM вы получили
ArrayList<MyEntity>, понимаете, что меняться он не будет, и хотите дальше в своём коде использовать его какImmutableList<MyEntity>. Преобразовали, старый список ушёл, новый появился. Чем плохо?Основное что плохо — неочевидность того, что простой вызов
new ImmutableList<MyEntity>(x)может очиститьx.zzzzzzzzzzzz Автор
06.10.2019 21:43Да, вы правы. От конструктора такого не очень ожидаешь. Поэтому в следующей версии будет специальный метод. (Зуд не прошёл, поэтому следующая версия, похоже, всё-таки будет)
Throwable
06.10.2019 20:37А еще можно просто взять Vavr...
public interface ReadOnlyCollection extends Iterable
Как я уже писал, Iterable не дает гарантии ReadOnly, т.к. в Iterator-е есть метод remove(). Впринципе на этом можно ставить точку. Нужен ReadOnlyIterable и ReadOnlyIterator.
метод получает UnmodifiableList, сам его менять не может, но знает, что содержимое может быть изменено другой нитью (и умеет это корректно обрабатывать)
Нити здесь ни при чем. UnmodifiableList — это только гарантии того, что консьюмер не может изменить список, то же самое, что и Collections.unmodifiableList(), только на уровне деклараций. Для полностью неизменяемого списка служит именно ImmutableList.
ImmutableList и List не должны быть связаны отношениями наследования. Почему так – разбирается в исходной статье.
Изначально вопрос стоял именно в этом: что будет, если наследовать и что при этом отвалится. Всегда можно нагородить своих библиотек, не связанных напрямую со стандартными коллекциями (это как один из вариантов решения — сделать новый java.collections и добавить конвертеров), но изначальная идея — это исправить уже существующие. И основной кейс использования — это при возврате кастить именно в UnmodifiableCollection:
public class Department { private List<Person> persons; /** мы не хотим, чтобы консьюмер изменял список, и въявную это декларируем */ public UnmodifiableList<Person> getPersons() { // кастится, поскольку List должен наследоваться от UnmodifiableList // в противном случае пришлось бы врапить new UnmodifiableList(persons) return persons; } /** потому что добавление в список должно быть контролируемым, и только через этот метод. типичный кейс для JPA */ public void addPerson(Person person) { person.setDepartment(this); persons.add(person); } public void setPersons(UnmodifiableList<Persons> persons) { // Так вообще нельзя делать, т.к. клиент ничего не должен знать о внутренней реализации списка // this.persons = persons; // Так тоже нельзя, потому как может быть persons == this.persons // this.persons.clear(); this.persons = new ArrayList<>(); persons.stream().forEach(this::addPerson); }
Остальное — детали реализации, которые впринципе не важны.
zzzzzzzzzzzz Автор
06.10.2019 22:24Iterable не дает гарантии ReadOnly, т.к. в Iterator-е есть метод remove()
Ну так Iterator-то мы сами пишем… Метод remove() кидает UnsupportedOperationException. Безусловно, с ReadOnlyIterator было бы красивее, но приходится подстраиваться под существующую Java — Iterable нужен, чтобы можно было написатьfor (Item item : ImmutableList<Item>)
сделать новый java.collections и добавить конвертеров
Это непрактично, т.к. все библиотеки используют «старые» коллекции, а конвертация — тяжёлая операция. Основная идея того, что я описал в статье — как раз «дешёвая» конвертация туда-обратно.
VolCh
Первый вариант, по-моему, для того, чтобы вызывающий метод имел гарантии, что вызываемый его не поменяет. Не знаю, можно ли это реализовать конкретно в Java, но в некоторых случаях може быть полезным, например запустить три таких "чистых" метода параллельно или просто сначала выполнить самый важный для юзера, не боясь, что от порядка что-то изменится
zzzzzzzzzzzz Автор
В Java для такого есть готовый
Collections.unmodifiableList. Просто он для такой ситуации ничем не лучше, чем по-настоящему immutable список (если последний достаточно быстрый). Зато с immutable взаимные ожидания методов более явно задекларированы. Хотя возможны и ситуации, когда immutable не подходит — как раз когда изменяемость нужна — вызываемый метод не может менять список, но знает, что его может менять вызывающий метод, и умеет это обрабатывать. Но это отдельные случаи, редкие и неприятные как раз необходимостью этой особой обработки.