В своей предыдущей статье "Рукоблудие вокруг 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;
}Всем удачи! Шлите багрепорты!
Комментарии (22)
dopusteam
13.10.2019 23:30Метод toList обеспечивает возможность передачи ImmutableList в куски кода, ожидающие List. Возвращается обёртка, в которой все изменяющие методы возвращают UnsupportedOperationException, а остальные методы переадресуются к исходному ImmutableList.
Вам не кажется, что с таким подходом нарушается принцип подстановки Лисков?
Метод contentEquals предназначен для сравнения содержимого списка с содержимым произвольного переданного Iterable (разумеется, осмысленной эта операция является только для тех реализаций Iterable, у которых есть какой-то внятный порядок элементов).
Может стоит явно указать ограничение это в интерфейсе?
zzzzzzzzzzzz Автор
14.10.2019 01:07Вам не кажется, что с таким подходом нарушается принцип подстановки Лисков?
Нет. Например, в контракте методаList.addявно прописано:throws UnsupportedOperationException if the add operation is not supported by this list. То есть, вызывающая сторона должна быть к такому готова. На практике в «родных» коллекциях такое исключение можно получить, например, от списка, возвращённогоCollections.unmodifiableList.
Может стоит явно указать ограничение это в интерфейсе?
Хотелось бы, но не знаю, как. Например,TreeSet.iteratorвернёт итератор с элементами в порядке возрастания. И как (кроме как захардкодить) мне его отличить отHashSet?dopusteam
14.10.2019 09:33Нет. Например, в контракте метода List.add явно прописано: throws UnsupportedOperationException if the add operation is not supported by this list.
Спасибо за пояснение.
Но по мне, все ещё выглядит странно. Если Collections.unmodifiableList не реализует List.add, то и реализовывать его не стоит. Разделили бы на два интерфейса.
Это не к Вам, конечно, а просто недоумение)
mayorovp
14.10.2019 09:07Может стоит явно указать ограничение это в интерфейсе?
Тот случай, когда это ограничение очевидно.
dopusteam
14.10.2019 09:28Тем не менее, если бы был тип аргумента OrderedList (не просто Iterable) или какой то подобный (не очень знаком с Java), то ИМХО было бы приятнее.
Но в целом, да, согласен, посмотрел ещё документацию, так очевидно
reforms
14.10.2019 11:06Меня восхищает Ваша напористость и желание сделать SDK лучше.
Сразу скажу, что я согласен с автором поста Неизменяемых коллекций в Java не будет – ни сейчас, ни когда-либо
И это согласие есть результат статьи, которую я практически написал, но в последний момент отказался публиковать — так как изменил свое мнение на мнение автора :)
Вот совсем кратко мои рассуждения на тему списков:
…
Чтобы ответить на этот вопрос, сначала нужно поискать уже существующие решения в самом SDK, а во-вторых, посмотреть на потенциальное решение с практической точки зрения. Начнем с поиска.
Классическим представителем неизменяемых объектов в SDK являются экземпляры класса java.lang.String. Строки спроектированы таким образом, что поменять их через публичное API — невозможно. Строки имеют отношение к поиску истины и потому, что их можно рассматривать через призму коллекций. Фактически, строка — это набор символов. Но сейчас вернемся к самому типу String. Важно понять, что в SDK нет MutableString. Или перефразировав, прийти к тому, что нет такой полной иерархии как ImmutableString, UnmodifiableString и MutableString. Плохо это или хорошо — каждый решает сам.
Что касается иерархии, то я немного слукавил — иерархия есть, только не для типа String, как чего-то целого и завершенного, а для набора символов. Это всем известные StringBuilder и StringBuffer, которые как и String растут от CharSequence. Фактически, у нас есть 2 ветки: изменяемые и неизменяемые последовательности символов. Причем во главу угла поставлен контракт на чтение данных, так как CharSequence содержит только методы получения данных.
После ознакомления с готовым решением по строкам в SDK можно сделать несколько важных выводов про mutable и immutable:
1) Каждая реализация сохраняет свое свойство навсегда — нет перехода от immutable к mutable или обратно внутри одной реализации.
2) В любой части программы, работая с реализацией, мы можем точно сказать о ее свойствах — изменяемая (StringBuilder/StringBuffer) или неизменяемая (String).
3) В любой части программы, работая с абстракцией (CharSequence), мы не можем сказать, какими свойствами данное представление обладает и какие гарантии может обеспечить (в общем случае).
4) Логичным и подтвержденным реализацией подходом является переход от mutable к immutable, т.е. изменяемый набор порождает неизменяемый, но не наоборот.
Выводы как постулаты мы будем использовать для реализации неизменяемых списков. Но сначала, я хотел бы проанализировать сами выводы и понять их сильные и слабые стороны. Мой любимый — это пункт 3. На мой взгляд, для проектирования безопасного api — это огромный недостаток. Когда мы спускаем в engine некоторую абстракцию, вполне логичным, для меня, является то, что этот engine имеет право потребовать определенные гарантии надежности от источника, взамен, обещает сделать свою работу должным образом. Такие отношения можно формализовать с помощью простого метода, спросив с помощью него, какие гарантии несет реализация. В плоскости рассматриваемой проблемы им может стать контрактный метод isImmutable;
boolean isImmutable();
Если мы используем фундаментальные принципы проектирования, то делать такой метод — неправильно. Но если мы ищем больше практичное решение, нежели фундаментальное — то допустимо.
Так как пункт 1 гласит, что свойство immutable/mutable сохраняется навсегда, то вмести с ним сохраняется и гарантия неизменяемости/изменяемости тоже — навсегда.
Рассматривая пункт 3, мы столкнулись с первой дилеммой — фундаментальность или практичность?
Пункт 2, можно интерпретировать и по-другому, что не должна одна реализация рости от второй. Т.е. ссылочное присвоение в обе стороны запрещены (ошибка компиляции).
Пункт 4, опять таки заставляет нас разобраться с дилеммой: фундаментальность или практичность? Потому что требует, наличие метода toImmutable в общем контракте. Можно читать toImmutable здесь как метод toString в классе CharSequence, с одной оговоркой.
List<T> toImmutable();
Я утверждаю, что пункт 4 больше рожден из практической плоскости, нежели фундаментальной. И это важно. В противном случае, неизменяемая реализация должна порождать изменяемую, но на примере String, мы видим, что такого нет.
Есть еще одна особенность в типах String, StringBuilder и StringBuffer, если рассматривать их как набор символов, про которую я нарочно умолчал. Мы всегда работаем с реализацией, что сильно упрощает контекст восприятия.
Это недопустимо для списков в общем случае.
Если подытожить выше изложенную философию мысли, для решения проблемы с неизменяемыми коллекциями нам требуются в арсенале 2 метода isImmutable и toImmutable. Разумеется, исходим из того, что по факту сейчас есть в SDK.
interface Collection<E> extends Iterable<E> { // ... boolean isImmutable(); Collection<E> toImmutable(); // ... }
Правильно? Не совсем. Потому что toImmutable возвращает контракт совместимый по апи с коллекциями в оба направления, что делает не возможным ограничение по типу.
…
И так далее, пока я не пришел к выводу, что новых коллекций не появится.
Если попытаться выдать желаемое за действительное — то в SDK все же неизменяемые коллекции могут быть и мне точно известно время — когда в java появится система типов, подобная TypeScript. Тогда различия между 2мя коллекциями будет в наличие значение у поля mutable: или true или false;
Но это совсем другая история, не находите?
mayorovp
14.10.2019 13:28Простите, но откуда взялся метод isImmutable, с которым вы спорите?
reforms
14.10.2019 14:07Во-первых, с методом я не спорю (только с людьми)
А во-вторых:
>> 3) В любой части программы, работая с абстракцией (CharSequence), мы не можем сказать, какими свойствами данное представление обладает и какие гарантии может обеспечить (в общем случае)
Метод isImmutable — это следствие моих рассуждений по части пункта 3 и в контексте статьи, которую в качестве исходного материала я указал в начале.mayorovp
14.10.2019 14:13Вот именно, мы это не можем сказать. Так зачем тогда нужен метод?
Если кому-то нужны гарантии — пусть явно попросит неизменяемый вариант коллекции.
reforms
14.10.2019 14:24Вы чертовски проницательны: Если кому-то нужны гарантии — пусть явно попросит неизменяемый вариант коллекции.
Так эта одна из ключевых проблем, в которую упирается автор первоначальной статьи, автор этой и я с Вами. И за кажущейся простотой, скрывается далеко непростая задача.mayorovp
14.10.2019 14:39Так в чём проблема-то?
reforms
14.10.2019 15:12Добро пожаловать в наш клуб.
1) В java SDK нет контракта на неизменяемую (немодифицируемую) коллекцию, пожалуй основная проблема.
2) Если такой контракт добавлять, то неизбежно придется ответить на вопросы:
2.1) Какой интерфейс должен быть у неизменяемой коллекции?
2.2) Должен ли этот интерфейс/контракт наследоваться от Collection/List?
2.3) Должен ли Collection/List наследоваться от неизменяемой коллекции?
2.4) Можно ли ввести понятие неизменяемой коллекции, не сломав обратную совместимость с ранними версиями?
2.5) Должна ли неизменяемая коллекция порождать новую в методах add/remove и т.д. или бросать исключение?
Я осветил ключевые вопросы и проблемы. У каждого ответа есть свои последствия, которые могут влиять на всю эко систему SDK.mayorovp
14.10.2019 17:03В рамках данного поста у вас есть конкретная реализация, где так или иначе даны ответы на почти все эти вопросы.
dShell
14.10.2019 22:55-1Я возмоно пропустил это, но почему нельзя использовать маркерные интерфейсы?
Два интерфейса с операциями (Read, Write), один маркерный (Immutable), оригинальный List (extends Read, Write), и нужный ImmutableList (extends Read, Immutable).zzzzzzzzzzzz Автор
14.10.2019 23:21Основное, почему нельзя — это наличие существующих List. Если бы переделывать коллекции Java с нуля, то так можно было бы сделать. А в текущей реальности из такого подхода получится просто альтернативный Collections Framework, который не взлетит, поскольку все сторонние библиотеки под List заточены.
zzzzzzzzzzzz Автор
14.10.2019 23:48Если честно, далеко не все ваши мысли понял, но:
— Одной из основных идей описанной в статье реализации было именно что не «сделать SDK лучше» (это да, близко к невозможному), а реализовать компромиссный вариант между существующим SDK и «как оно могло бы быть в идеале».
— Вот вы говорите «работая с абстракцией (CharSequence), мы не можем сказать, какими свойствами данное представление обладает и какие гарантии может обеспечить». На самом деле, CharSequence описывает только read-only методы. То есть, если метод на входе принимает CharSequence, то трудно ожидать, что увидев, что ему передали StringBuilder, он сделает приведение типов и начнёт что-то менять (и даже лучше, если бы такое приведение типов не позволял сделать компилятор).
— Аналогично и для коллекций: да, вариант с флажком isImmutable возможен, но гораздо лучше, если интерфейсы для read-only и для read-write операций разные. Тогда глянув на сигнатуру метода вы сразу понимаете, будет он что-то менять, или нет.
— Хотя флажок isImmutable я бы хотел видеть, но не для коллекций, а для вообще всех поголовно объектов, и не для конкретных экземпляров, а для классов целиком.
igormich88
Я правильно понял что при подсчёте hashCode при каждом вызове просматриваются все элементы списка, в том числе и для ImmutableList?
А для equals попарно просматриваются элементы списков до первого несовпадения?
zzzzzzzzzzzz Автор
Ну да. Это штатное поведение списков в Java, а для ImmutableList сделано по аналогии.