Undo и Redo — анализ и реализации
Интересно? Добро пожаловать!
Исследование
Красная или синяя? Примерно к такому вопросу нужно будет прийти, после того, как решили реализовать в приложении Undo/Redo. Объясняю: есть два основных способа реализовать пошаговую отмену, для которых я присвоил следующие наименования: operation-oriented и value-oriented. Первый способ основан на создании операций (или транзакций), у которых есть два метода — сделать и вернуть всё как было. Второй способ не хранит никаких операций — он лишь записывает значения, которые изменились в определённый момент времени. И у первого и у второго способа есть свои плюсы и минусы.
Метод 1: operation-oriented
Этот метод заключается в том, чтобы хранить операции в специальном стеке. У стека есть позиция (можно сказать, итератор), которая указывает на последнюю операцию. При добавлении операции в стек — она выполниться (redo), позиция инкрементируется. Для отмены операции стек вызывает команду undo из последней операции, а потом сдвигает позицию последней операции ниже (сдвигает, но не удаляет). Если понадобится вернуть действие — сдвиг выше, выполнение redo. Если после отмены добавляется новая операция, то есть два решения: либо заменять операции выше позиции новыми (и тогда вернуться к прежним будет невозможно), либо начинать новую «ветку» в стеке, но отсюда возникает вопрос — к какой ветке потом идти? Впрочем, ответ на этот вопрос уже искать нужно не мне, так как это зависит от требований к программе.
И так, для самого просто Undo/Redo нам нужно: базовый класс (интерфейс) с чисто виртуальными (абстрактными) функциями undo () и redo (), также класс, который будет хранить указатели на объекты, произведённые от базового класса и, конечно же, сами классы, в которых будут переопределены функции undo () и redo (). Также можно (в некоторых случаях даже очень нужно) будет сделать функции совмещения операций в одну, для того, чтобы, допустим, отменять не каждую букву по отдельности, а слова и предложения, когда буквы станут таковыми, и тому подобное. Поэтому также желательно для каждой операции присваивать определённый тип, при различии которых нельзя будет склеить операции.
И так, плюсы:
- При правильном построении операций шансы пострадать бизнес-логике низки, так как выполняются именно операции, в которых также может быть задействована магия БЛ, только для undo нужно выполнять действия в обратном порядке, а сами действия должны быть обратными (исключая моменты, когда один объект меняется, и другие зависят от первого, тогда в таком случае в конце и undo и redo нужен будет пересчёт).
- Менее требователен к памяти — записываются только операции, но не значения переменных. Если при операции вызывается механизм пересчёта чуть ли не всего и вся — в память эти изменения не попадают, а при отмене снова нужен будет пересчёт.
- Более гибкий способ Undo/Redo.
Минусы:
- При неправильном построении… у бизнес-логики нет и шанса на правильную работу с Undo/Redo.
- Если операции вызывают пересчёт зависимостей и тому подобное, то такой подход будет требователен к производительности.
Также можно прочитать вот эту статью на Wiki про паттерн команд, который и используется для реализации такого способа Undo/Redo, а также эту статью на Хабрахабре.
Метод 2: value-oriented
Принцип метода — знать о всех возможных переменных, которые могут измениться, и в начале возможных изменений поставить стэк «на запись», а в конце — сделать коммит изменений.
Тем не менее, записываться должны все изменения. Если записывается только изменения, произведённые пользователем, но не записывались изменения зависимостей — то тогда при отмене/возврате зависимости останутся без изменений. Конечно, можно хитрым способом каждый раз вызывать пересчёт зависимостей, но это уже больше похоже на первый способ и удобнее тогда будет он. О способах реализации будет рассказано ниже, а пока посмотрим на достоинства и недостатки.
Плюсы:
- Не нуждается в пересчётах — не требователен к производительности.
- Бизнес-логика не страдает — всё подсчитанное просто снова встаёт на свои места.
- Более простой способ Undo/Redo.
Минусы:
- Более требователен к памяти, так как сохраняются все зависимые объекты (в противном случае либо страдает производительность, либо бизнес-логика).
- Не способен на вызов определённых операций, так как идёт только «восстановление памяти».
Также можно прочитать вот эту статью на Wiki про паттерн Хранителя.
Плохой метод 3: full snapshot
Если что и говорить о требовательности к памяти, то этот метод будет есть очень много. Представьте ситуацию, когда при наборе лишь одного символа сохранялся весь документ. И так каждый раз. Представили? А теперь забудьте об этом методе и более не вспоминайте, ибо это уже не Undo/Redo, а бэкапы.
UPD: И нет, здесь я не имел в виду паттерн Memento, который также может сохранять кроме частичного ещё полный снимок изменений/значений. Имеется в виду, что не желательно сохранять снимок всего документа, когда изменилось лишь пару значений. Если всё-таки этого не избежать, то это скорее vl-or, а в некоторых ситуациях, когда очень редко и по сложной схеме изменяется весь документ, вы можете отказаться от записи таких изменений (сказать пользователю, что откат изменений после этой операции будет недоступен).
Способы реализации
C++: Qt
Operation-oriented
Здесь разработчики на славу постарались. С помощью Qt можно легко и просто реализовать Undo/Redo. Записывайте рецепт. Нам понадобиться: QUndoStack, QUndoCommand, а также QUndoView и QUndoGroup по вкусу. Сначала от QUndoCommand наследуем собственные классы, в которых должны быть переопределены undo () и redo (), также желательно переопределить id () для определения типа операции, чтобы потом в переопределённой mergeWith (const QUndoCommand *command) можно было проверить обе операции на совместимость. После этого создаём объект класса QUndoStack, и помещаем в него все новые операции. Для удобства, можно взять QAction *undo и QAction *redo из функций стека, которые потом можно добавить в меню, или прикрепить к кнопке. А если нужно использовать несколько стеков, тогда в этом поможет QUndoGroup, если нужно отобразить список операций: QUndoView.
Также, в QUndoStack можно отмечать clear state (чистое состояние), которые, например, может означать сохранён ли документ на диск и т.д. Вполне удобная реализация op-or undo/redo.
Я реализовал самый простой пример на Qt.
Здесь также упоминается некий «сервер», это на случай, если он тоже будет присутствовать и взаимодействовать с вашим приложением-клиентом. А вот и исходники (считайте, что всё писал «на коленке»).
Value-oriented
Упс… Qt такого варианта не предоставил. Даже поиск по ключевым словам «Qt memento» не дал ничего. Ну и ладно, там и такого вполне достаточно, а если не достаточно, можно воспользоваться Native’ными методами.
C++: Native
Так как в Qt не посчитали нужным добавить value-oriented Undo/Redo, поэтому нужно будет искать либо готовые реализации (где можно встретить магическое для меня слово «Memento»), либо реализовывать придётся самим. В основном всё реализуется на основе шаблонов. Всё это можно без проблем найти. Я, например, нашёл вот этот проект на GitHub. Тут реализованы сразу две идеи, можете взять и посмотреть, потестировать.
C#: .NET
Для меня C# и .NET пока что тёмные леса далёкой Сибири, но тем не менее, он мне очень и очень нужен. Поэтому стоит рассказать хотя бы о том, что мне удалось нагуглить.
Operation-oriented
Самыми хорошими примерами для меня были:
- Хорошая статья на Хабрахабре.
- Интересный пост про паттерн команд на .NET.
- И просто хороший пример Undo/Redo с использованием Generics.
Вскоре нашлась и такая вот старая статья.
Быть может, что-то сможете найти и вы, а возможно на основе этого взять и написать свой велосипед гениальный код. Дерзайте.
Value-oriented
Вообще, для такого рода задач в .NET есть интерфейс IEditableObject, но придётся много чего реализовывать с нуля, хотя пример реализации есть прямо на MSDN. Тем не менее, мне очень понравилась библиотека DejaVu, ради которой даже написана целая статья на Хабрахабре. Читайте, влюбляйтесь, пишите.
Есть ещё два примера, но они мне совсем не понравились:
- Пример 1.
- Пример 2.
Заключение
И так, что нужно знать, чтобы выбрать между двумя методами реализации только одну? Во-первых, реализацию вашего проекта, написан ли (будет?) он на основе команд, или просто изменение множества значений (если ни то, ни другое — думаю, лучше переписывать проект). Во-вторых, требования к памяти и производительности, ибо возможно именно из-за них придётся отказаться от одного варианта в пользу другого. В-третьих, нужно точно знать, что должно сохранятся и как, а что не должно вообще. Вот, в принципе и всё.
Удачи в будущем!
Комментарии (10)
27 июля 2016 в 12:03
+1↑
↓
Это все, конечно, здорово на этапе проектирования нового приложения. Тогда можно выбрать operation-oriented или value-oriented метод, и в соответствии с этим реализовывать логику приложения. Но когда вашему приложению уже 5 лет, у вас куча всевозможных действий над данными, и вдруг менеджер проекта решает, что пора бы вам прикрутить Undo/Redo, то тот самый плохой 3-й способ может быть единственным решением, без переписывания всего приложения.27 июля 2016 в 12:22
0↑
↓
Это означает, что 5 лет назад этап проектирования был пропущен.
27 июля 2016 в 12:29 (комментарий был изменён)
0↑
↓
Написать про value-oriented то, что он не требует пересчётов — это лукавство. Всё-таки сохраняется контрольная точка и набор изменений только в сторону redo либо в сторону undo, иначе это несколько автоматизированный Operation-oriented, в котором сложные изменения представляется в виде набора простых команд (в Qt это называется macro).
faserg1
27 июля 2016 в 12:36
0↑
↓
В Value-oriented может и не быть пересчётов вовсе, если сохранять все значения, даже зависимые. Но я одного не понимаю, при чём тут автоматизированный op-or?27 июля 2016 в 12:45 (комментарий был изменён)
0↑
↓
> В Value-oriented может и не быть пересчётов вовсе, если сохранять все значения, даже зависимые
Но это третий метод же! «когда при наборе лишь одного символа сохранялся весь документ». А если сохранять все зависимые части, то есть от позиции редактирования до конца документа, то восстановление потребует-таки некоторых пересчётов, как минимум, перерисовки.
Я понимаю, что пример несколько оторванный от реальности, но…-
faserg1
27 июля 2016 в 12:49
0↑
↓
Не настолько зависимые. Одно дело — перерисовка документа. Другое дело — пересчёт всей таблицы (да хоть Excel) после изменения ячейки. Грубо говоря, при смене одной ячейки идёт пересчёт зависимых от неё, и только они сохраняются.
Перерисовка к Undo/Redo вообще никакого отношения иметь не должна.27 июля 2016 в 12:58
0↑
↓
С этой точки зрения согласен.
Вообще, по моему ничтожному мнению, Operation-oriented метод представляет большую гибкость, нежели Value-oriented, так как в рамках операции можно сохранить состояние объекта вместе со всеми зависимостями. И даже более того, можно добавить чек-поинты и пересчёт от них, если чуть-чуть выбраться из коробки. Как это сделать в Value-oriented, я с ходу сказать не имею.-
faserg1
27 июля 2016 в 13:01
0↑
↓
То, что op-or — более гибок, верно. Vl-or более простой вариант, ибо для op-or нужно прописывать реализацию для каждой команды.
RPG18
27 июля 2016 в 12:30
0↑
↓
А теперь забудьте об этом методе и более не вспоминайте, ибо это уже не Undo/Redo, а бэкапы.
Назначение хранитель (memento) создавать снимки (snapshot) состояния. Снимок может быть полный или частичный, зависит от требований и сложности предметной области.
-
faserg1
27 июля 2016 в 12:34
0↑
↓
Здесь я имел в виду, что сохранять всё и вся без такой необходимости — плохой вариант.
