[Из песочницы] Реализация функциональности многоуровневого undo/redo на примере прототипа электронной таблицы
Введение
Кнопки «Undo» и «Redo», позволяющие отменить и вернуть обратно любые пользовательские действия, а также посмотреть в списке перечень всех выполненных действий, являются стандартом де-факто для таких приложений, как текстовые процессоры и среды разработки, редакторы графики и САПР, системы редактирования и монтажа звука и видео. Они настолько привычны для пользователя, что последний воспринимает их наличие как данность, всего лишь одну функциональную возможность наряду с десятками других. Но с точки зрения разработчика требование к наличию undo является одним из факторов, влияющих на всю архитектуру проекта, определяемую на самых ранних стадиях проекта разработки.
В открытых источниках существует довольно мало информации о том, как практически реализовывать функциональность undo/redo. Классическая книга Э. Гаммы и др. «Приёмы объектно-ориентированного программирования. Паттерны проектирования» коротко упоминает о пригодности для этой цели паттерна «команда», в интернете на эту тему много общей информации, но нам не удалось найти достаточно полного, проработанного примера реализации. В нашей статье мы попытаемся восполнить этот пробел и, основываясь на опыте автора, продемонстрировать подробный пример архитектуры приложения, поддерживающей undo/redo, который может быть взят за основу других проектов.
Примеры кода в статье даны на языке Java, однако в них нет ничего Java-специфичного и все изложенные здесь идеи подходят для любого объектно-ориентированного языка (сам автор впервые реализовал их на Delphi).
Следует отметить, что для различных нужд и типов приложений существуют различные «модели undo»: линейные — с отменой операций строго в обратной последовательности, и нелинейные — с отменой произвольных операций из истории произведённых действий. Мы будем вести речь о реализации линейного Undo в системе с синхронизированными модификациями модели данных, т. е. такой, в которой не допускается одновременная модификация внутреннего состояния модели данных в разных потоках выполнения. Классификация возможных моделей undo приводится, например, в статье в Википедии.
Мы, естественно, предполагаем, что в приложении реализовано отделение модели данных (Model) от представления (View), и функциональность undo реализуется на уровне модели данных, в виде методов undo () и redo () одного из её классов.
Иллюстрирующий пример
В качестве иллюстрирующего примера в статье рассматривается модель данных приложения, прототипирующего электронную таблицу (в стиле MS Excel/ LibreOffice Calc). Имеется лист (для простоты — только один), состоящий из ячеек, значения и размеры которых можно изменять, строки и столбцы — менять местами, и все эти действия, соответственно, являются отменяемыми. Исходные коды и соответствующие модульные тесты доступны по адресу http://inponomarev.ru/programming/undoredo.zip и могут быть скомпилированы и выполнены при помощи Maven.
Основными сущностями в нашем примере являются:
- рабочий лист — класс Worksheet,
- строки и столбцы — классы Row и Column (наследники класса AxisElement),
- ячейки — класс Cell.
Получающаяся в результате несложная модель данных представлена на диаграмме классов на рисунке ниже:
Не вдаваясь в подробности реализации электронных таблиц, отметим вкратце основные принципы устройства исходного кода. Хотя для пользователя лист электронной таблицы представляется как двумерный массив данных, границы которого уходят далеко за пределы экрана, использование двумерного массива для модели данных не оправдано ни с точки зрения расхода оперативной памяти, ни с точки зрения быстродействия типовых операций. К примеру, если в ранних версиях MS Excel допускалось существование 65536 столбцов и строк, то выделение памяти под 655362, т. е. 4 млрд. ячеек, было бы просто технически невозможно в 32-битной системе.
Решением является использование словарей на базе деревьев и хэш-таблиц для хранения одних лишь только изменённых значений, подставляя вместо отсутствующего в словаре значения некоторое значение по умолчанию.
Для хранения экземпляров Row и Column, используются словари TreeMap
Корневой класс модели и отменяемые методы
Класс Worksheet в нашем примере является центральным: 1) работа со всеми другими объектами бизнес-логики начинается с получения экземпляра именно этого класса, 2) экземпляры других классов могут работать только в контексте объекта Worksheet, 3)через метод save (…) и статический метод load (…) он сохраняет в поток и восстанавливает из потока состояние всей системы. Этот класс мы назовём корневым классом модели. Как правило, при разработке приложений в архитектуре Model-View-Controller не возникает затруднений с определением того, что является корневым классом модели. Именно он и снабжается методами, специфичными для функциональности Undo/Redo.
Также не должно вызвать затруднений определение методов, изменяющих состояние модели. Это те методы, результат вызова которых необходимо отменять по undo. В нашем примере — следующие:
- setCellValue (int row, int col, String value) — устанавливает значение ячейки (для простоты примера мы считаем, что ячейки могут принимать только строковые значения!),
- insertValues (int top, int left, String[][] value) — вставляет в ячейки значения двумерного массива (например, полученного из буфера обмена),
- setRowHeight (int row, int height), setColWidth (int col, int width) — задают высоту строк и ширину столбцов,
- insertColumnLeft (int colNum), insertRowAbove (int rowNum) — вставляют столбцы и строки,
- deleteColumn (int colNum), deleteRow (int rowNum) — удаляют столбцы и строки,
- moveColumn (int from, int to), moveRow (int from, int to) — перемещают столбцы и строки вместе с содержимым с заменой содержимого конечного столбца / строки.
В реальном приложении, конечно, их может быть гораздо больше. Каждому из них требуется сопоставить соответствующий класс команды (о чём пойдёт речь дальше), а методы необходимо переписать особым образом.
Undo- и Redo-стеки
В линейной модели Undo отмена операций производится таким образом, чтобы сохранять последовательность производимых над документом действий. Например, если в документ сначала был добавлен столбец, а затем изменена его ширина, то отмена этих операций возможна только в обратном порядке, а возврат — в прямом. Поэтому для хранения операций, подлежащих отмене и восстановлению, естественно использовать два стека на связных списках (linked lists), являющихся частью корневого класса модели. При вызове метода, изменяющего состояние модели, стек Redo сбрасывается, а стек Undo пополняется очередным значением. Выполнение команды Undo должно приводить к извлечению значения из стека Undo и переносу его в стек Redo. Выполнение команды Redo, если таковое случится, должно вновь возвращать значение в стек Undo (см. рис.).
Cодержимым этих стеков являются объекты-наследники класса Command, о котором речь пойдёт далее. Вот перечень публичных методов корневого класса бизнес-логики, дающих доступ к функциональности Undo/Redo:
Паттерн «команда»
Методы, изменяющие состояние модели, могут иметь разные параметры и вообще быть определены в разных классах модели. Полностью инкапсулировать информацию о параметрах и целевом объекте метода, «причесать всех под одну гребёнку», позволяет паттерн проектирования «команда». Нетривиальность этого паттерна заключается в том, что обычно классами в объектно-ориентированном коде описываются некоторые сущности. Здесь же класс описывает не сущность, а действие, производимое меняющим состояние модели методом, «отняв» эту прерогативу у самого метода.
Класс каждой из команд наследуется от базового абстрактного класса Command. Сам по себе Command имеет всего три абстрактных метода: execute, undo и getDescription, не имеющих (что важно!) никаких параметров. Это позволяет выполнять и отменять команды методами undo () и redo () корневого класса, «ничего не знающими» о тех операциях, которые выполняются или отменяются. Метод getDescription () должен возвращать текстовое описание действия: именно это описание будет доступно пользователю в списке отменяемых действий.
Наследники класса Command, помимо реализации его абстрактных методов, могут содержать сколько угодно дополнительных полей, содержащих информацию о параметрах запуска команды и информацию, необходимую для отмены уже выполненной команды и показа текстового описания выполненной команды. При этом метод execute () должен содержать код, который обычно содержится в методе, меняющем состояние модели, только вместо параметров метода этот код должен использовать поля класса команды. Отметим, что команда оперирует внутренним состоянием объекта модели так же, как раньше это делал его собственный метод. Поэтому команда должна иметь доступ к скрытым (private) полям объекта модели. В языке Java этого удобно добиться, если сделать класс-наследник Command вложенным в соответствующий класс модели. В нашем приложении, например, команда SetSize вложена в класс модели AxisElement, остальные команды вложены в Worksheet.
Метод undo (), в свою очередь, должен уметь отменять последствия вызова метода еxecute (). Вся необходимая для этого информация должна храниться в полях класса команды. Дело упрощается, если понимать, что на момент вызова метода undo () состояние объектов бизнес-логики будет всегда тождественно тому, каким оно было сразу же после выполнения соответствующего метода execute (). Если с тех пор пользователь выполнял другие операции, то, прежде чем он доберётся до undo () текущей команды, он должен будет выполнить undo () для всех команд, которые вызывались после неё. На практике понимание этого принципа сильно облегчает написание метода undo () и сокращает количество сохраняемой в команде информации.
Рассмотрим реализацию команды, устанавливающей значение ячейки:
final class SetCellValue extends Command {
private final int row;
private final int col;
private String val;
public SetCellValue(int row, int col, String newValue) {
this.row = row;
this.col = col;
this.val = newValue;
}
@Override
public String getDescription() {
return ("Ввод данных");
}
private void changeVal() {
String oldValue = getCellValue(row, col);
Row r = rows.get(row);
Column c = columns.get(col);
//.... получение объекта cell по row и col...
cell.setValue(val);
//....
val = oldValue;
}
@Override
public void execute() {
changeVal();
}
@Override
public void undo() {
changeVal();
}
}
Как видим, в классе имеются переменные для сохранения адреса ячейки и её значения. Причём в целях экономии памяти можно обойтись лишь одной переменной для сохранения значения: нового, если метод execute () ещё не выполнен, или старого, если метод execute () уже выполнен. Т. е. здесь как раз используется тот факт, что методы execute () и undo () выполняются поочерёдно. Метод getDescription () может использовать переменные класса для того, чтобы описание команды было более подробным.
Шаблон отменяемого метода
Как команды используются в отменяемых методах? Если обычно такие методы с учётом своих параметров просто выполняют какие-то действия над моделью, то в системе с undo все они строго должны производить следующие три операции:
- создать экземпляр соответствующей команды (класса-наследника Command),
- инициализировать поля команды параметрами метода и, возможно, дополнительной информацией,
- выполнить метод execute (Command cmd) корневого объекта, передав в качестве параметра только что созданную и инициализированную команду.
В нашем примере выглядит реализация метода setCellValue выглядит так:
public void setCellValue(int row, int col, String value) {
Command cmd = new SetCellValue(row, col, value);
execute(cmd);
}
Примерно так же выглядят все другие отменяемые методы.
Метод execute (Command cmd) корневого класса выполняет действие команды, сброс стека redo и укладывание команды в стек undo:
undoStack.push(cmd);
redoStack.clear();
cmd.execute();
С этого момента команда становится частью цепочки отменяемых/повторяемых действий. Как было сказано выше, вызов метода undo () в корневом классе вызывает метод undo () команды, находящейся на вершине стека Undo, и переносит её в стек Redo. Вызов метода redo () корневого класса, в свою очередь, выполняет метод execute () команды, находящейся на вершине Redo-стека, и переносит её в стек Undo.Повторное использование классов команд
Итак, для задач, которые в обычном случае требуют написания одного метода, в системах с undo требуется создавать целый класс, что приводит к справедливым опасениям относительно объёма кода и трудоёмкости его поддержки: в реальных проектах количество отменяемых методов исчисляется десятками.
На самом деле, классов-команд может быть существенно меньше за счёт их универсализации и использования одного класса-команды для нескольких отменяемых методов. К примеру, основной код класса SetCellValue, по сути, может быть использован для любых методов, в которых требуется поменять одно значение какой-либо переменной. Сделать класс команды более универсальным можно как путём добавления дополнительных полей, так и за счёт параметризации класса.
Для примера рассмотрим универсальную команду удаления, которая используется для удаления как строк, так и столбцов таблицы:
final class Delete extends Command {
private final int num;
private final T deleted;
private final TreeMap map;
Delete(TreeMap map, int num) {
this.num = num;
this.map = map;
deleted = map.get(num);
}
@Override
public String getDescription() {
return String.format("Удаление %s %d", map == columns ? "столбца" : "строки", num);
}
@Override
public void execute() {
internalDelete(map, num);
}
@Override
public void undo() {
internalInsert(map, num);
map.put(num, deleted);
}
}
private static void
internalDelete(TreeMap map, int num) {
//...
//удаление из словаря записи с ключом num
//и сдвиг всех записей с ключом > num на минус одну позицию
//...
}
private static void
internalInsert(TreeMap map, int num) {
//...
//сдвиг всех записей с ключом >= num на плюс одну позицию
//...
}
}
Её использование в методах deleteColumn и deleteRow выглядит следующим образом:
public void deleteColumn(int colNum) {
Command cmd = new Delete(columns, colNum);
execute(cmd);
}
public void deleteRow(int rowNum) {
Command cmd = new Delete(rows, rowNum);
execute(cmd);
}
Макрокоманды
Иногда может оказаться, что вызов метода, меняющего состояние — слишком мелкая единица для хранения в стеке Undo. Рассмотрим процедуру insertValues (int top, int left, String[][] value) вставки значений из двумерного списка (например, из буфера обмена) в документ. Эта процедура в цикле одну за другой обновляет ячейки документа значениями ячеек из буфера. Таким образом, если мы вставляем кусок таблицы размером 4×4, то, с точки зрения механизма Undo, мы производим 16 изменений ячеек документа. Это означает, что если пользователь захочет отменить результат вставки, то 16 раз придётся нажать на кнопку Undo, при этом в таблице одна за другой 16 ячеек будут восстанавливать свои прежние значения.
Разумеется, это неправильно: результаты операций, подобных данной, должны отменяться и восстанавливаться как единое целое, и в списке отменяемых операций отображаться одной строкой. Для того, чтобы это стало возможно, применяются макрокоманды.
Идея реализации макрокоманды проста: это всего лишь специальный наследник класса Command, содержащий внутри себя цепочку других команд, как показано на рис.:
Метод execute () класса MacroCommand пробегает по собственному списку команд и выполняет их методы execute (). При вызове метода undo () той же макрокоманды, он пробегает по тому же списку команд уже в обратном порядке и вызывает их методы undo ().
Макро-методы, подобные методу вставки из буфера обмена, в приложениях, построенных в архитектуре Model/View/Controller, как правило, не являются частью модели, а реализуются на уровне контроллера. Зачастую они представляют собой лишь автоматизацию некоторой рутинной работы, необходимость в которой в зависимости от вида пользовательского интерфейса может существовать, а может и отсутствовать. Кроме того, часто возникает необходимость в группировке нескольких пользовательских действий в одно: например, текстовые редакторы группируют в одно макро-действие ввод пользователем слов и предложений, вместо того, чтобы засорять undo-стек записями о вводе каждой отдельной буквы.
Поэтому поддержка макрокоманд может и должна быть реализована на абстрактном уровне, независимым от приложения образом. Это делается с помощью добавления в корневой класс модели публичных методов beginMacro (String description) и endMacro (). Методы вызываются перед началом и после завершения макро-действий. Вызывая beginMacro (…) со строковым параметром, значение которого затем окажется доступным пользователю в списке отменяемых операций, мы порождаем объект типа MacroCommand и на время подменяем Undo-стек внутренним стеком макрокоманды. Таким образом, после вызова beginMacro всякая последующая передача команды в метод execute (…) корневого класса приводит к её записи не непосредственно в Undo-стек, а во внутренний стек текущей макрокоманды (которая уже, в свою очередь, записана в Undo-стек). Вызов endMacro () возвращает всё на свои места. Допускается также многоуровневое вложение макрокоманд друг в друга.
Отслеживание наличия несохранённых изменений
Наличие функциональности undo предоставляет надёжный способ отслеживания несохранённых изменений в документе. Это необходимо для реализации корректного поведения кнопки «Сохранить» в приложении:
- кнопка «Сохранить» должна быть активна тогда и только тогда, когда несохранённые изменения присутствуют (в противном случае сохраняться незачем: документ не изменялся),
- при закрытии документа имеет смысл спрашивать пользователя о том, хочет ли он сохранить изменения, только в случае, если несохранённые изменения присутствуют.
В нашем примере наличие несохранённых изменений возвращается методом isModified (). Реализуется он следующим образом: при каждом вызове метода save (…) текущая вершина стека Undo сохраняется в переменную lastSavedPoint. При вызове метода isModified текущая вершина стека Undo сравнивается со значением lastSavedPoint: если они равны, то несохранённые изменения отсутствуют. При деактивированном механизме undo метод isModified () всегда возвращает true.
Заключение
Мы рассмотрели основные принципы реализации линейного многоуровневого Undo/Redo на примере, который, на наш взгляд, достаточно универсален, чтобы служить шаблоном для других проектов.
Неудивительно, что функциональность undo и redo предъявляет достаточно серьёзные требования к архитектуре приложения и профессионализму разработчиков. Но такие вещи, как строгое следование архитектуре Model/View/Controller и хорошо продуманная модель (написание каждого из методов, меняющих состояние модели, в системе с undo «обходится дороже»), несмотря на некоторую трудоёмкость, окупаются высоким качеством и надёжностью создаваемой программы, что в конечном итоге обернётся удовлетворённостью её пользователей.
* * *
Полные исходные коды и соответствующие модульные тесты примера, рассмотренного в статье, доступны по адресу http://inponomarev.ru/programming/undoredo.zip и могут быть скомпилированы и выполнены при помощи Maven.
