Undo и Redo — анализ и реализации

Привет! В связи со своей реальной задачей проанализировать возможности Qt и .NET для реализации так называемых «Назад» (Undo) и «Вперёд» (Redo), цель которых отменить действие и отменить отмену соответственно, я решил все свои мысли, идеи и задумки развернуть в этой статье, даже если они будут частично или совсем неверными (поэтому по возможности и интересу пишите в комментарии свои замечания). Хоть и на просторах Интернета спокойно можно найти хорошие (и не очень) библиотеки и примеры реализаций, более общего представления на эти вещи я нашёл не так скоро, да и то, только в ответе на StackOverflow ^[1], а этого было мне не достаточно. Во всём найденном есть моменты, которые меня порадовали, есть и которые огорчили. Пожалуй, стоит отменить все печали и радости… чтобы к ним снова вернуться… «Назад… в будущее»!

Интересно? Добро пожаловать!

Исследование

Красная или синяя? Примерно к такому вопросу нужно будет прийти, после того, как решили реализовать в приложении Undo/Redo. Объясняю: есть два основных способа реализовать пошаговую отмену, для которых я присвоил следующие наименования: operation-oriented и value-oriented. Первый способ основан на создании операций (или транзакций), у которых есть два метода — сделать и вернуть всё как было. Второй способ не хранит никаких операций — он лишь записывает значения, которые изменились в определённый момент времени. И у первого и у второго способа есть свои плюсы и минусы.

UPD: Чтобы в дальнейшем было меньше вопросов, напомню, что Undo/Redo предназначено больше для хранения информации предыдущих вариантов документа (к примеру) во время редактирования. Записывать данные в БД или на диск будет долго, и это уже мало относится к цели Undo/Redo. Впрочем, если сильно надо — делайте, но лучше не стоит.

Метод 1: operation-oriented

Реализуется на основе паттерна «Команда» (Command).
Этот метод заключается в том, чтобы хранить операции в специальном стеке. У стека есть позиция (можно сказать, итератор), которая указывает на последнюю операцию. При добавлении операции в стек — она выполниться (redo), позиция инкрементируется. Для отмены операции стек вызывает команду undo из последней операции, а потом сдвигает позицию последней операции ниже (сдвигает, но не удаляет). Если понадобится вернуть действие — сдвиг выше, выполнение redo. Если после отмены добавляется новая операция, то есть два решения: либо заменять операции выше позиции новыми (и тогда вернуться к прежним будет невозможно), либо начинать новую «ветку» в стеке, но отсюда возникает вопрос — к какой ветке потом идти? Впрочем, ответ на этот вопрос уже искать нужно не мне, так как это зависит от требований к программе.

И так, для самого просто Undo/Redo нам нужно: базовый класс (интерфейс) с чисто виртуальными (абстрактными) функциями undo() и redo(), также класс, который будет хранить указатели на объекты, произведённые от базового класса и, конечно же, сами классы, в которых будут переопределены функции undo() и redo(). Также можно (в некоторых случаях даже очень нужно) будет сделать функции совмещения операций в одну, для того, чтобы, допустим, отменять не каждую букву по отдельности, а слова и предложения, когда буквы станут таковыми, и тому подобное. Поэтому также желательно для каждой операции присваивать определённый тип, при различии которых нельзя будет склеить операции.

И так, плюсы:

• При правильном построении операций шансы пострадать бизнес-логике низки, так как выполняются именно операции, в которых также может быть задействована магия БЛ, только для undo нужно выполнять действия в обратном порядке, а сами действия должны быть обратными (исключая моменты, когда один объект меняется, и другие зависят от первого, тогда в таком случае в конце и undo и redo нужен будет пересчёт).
• Менее требователен к памяти — записываются только операции, но не значения переменных. Если при операции вызывается механизм пересчёта чуть ли не всего и вся — в память эти изменения не попадают, а при отмене снова нужен будет пересчёт.
• Более гибкий способ Undo/Redo.

Минусы:

• При неправильном построении… у бизнес-логики нет и шанса на правильную работу с Undo/Redo.
• Если операции вызывают пересчёт зависимостей и тому подобное, то такой подход будет требователен к производительности.

Также можно прочитать вот эту статью на Wiki про паттерн команд (Command) ^[2], который и используется для реализации такого способа Undo/Redo, а также эту статью ^[3] на Хабрахабре.

Метод 2: value-oriented

Реализуется на основе паттерна «Хранитель» (Memento).
Принцип метода — знать о всех возможных переменных, которые могут измениться, и в начале возможных изменений поставить стэк «на запись», а в конце — сделать коммит изменений.

Тем не менее, записываться должны все изменения. Если записывается только изменения, произведённые пользователем, но не записывались изменения зависимостей — то тогда при отмене/возврате зависимости останутся без изменений. Конечно, можно хитрым способом каждый раз вызывать пересчёт зависимостей, но это уже больше похоже на первый способ и удобнее тогда будет он. О способах реализации будет рассказано ниже, а пока посмотрим на достоинства и недостатки.

Плюсы:

• Не нуждается в пересчётах — не требователен к производительности.
• Бизнес-логика не страдает — всё подсчитанное просто снова встаёт на свои места.
• Более простой способ Undo/Redo.

Минусы:

• Более требователен к памяти, так как сохраняются все зависимые объекты (в противном случае либо страдает производительность, либо бизнес-логика).
• Не способен на вызов определённых операций, так как идёт только «восстановление памяти».

Также можно прочитать вот эту статью на Wiki про паттерн Хранителя (Memento) ^[4].

Плохой метод 3: full snapshot

Если что и говорить о требовательности к памяти, то этот метод будет есть очень много. Представьте ситуацию, когда при наборе лишь одного символа сохранялся весь документ. И так каждый раз. Представили? А теперь забудьте об этом методе и более не вспоминайте, ибо это уже не Undo/Redo, а бэкапы.

UPD: И нет, здесь я не имел в виду паттерн Memento, который также может сохранять кроме частичного ещё полный снимок изменений/значений. Имеется в виду, что не желательно сохранять снимок всего документа, когда изменилось лишь пару значений. Если всё-таки этого не избежать, то это скорее vl-or, а в некоторых ситуациях, когда очень редко и по сложной схеме изменяется весь документ, вы можете отказаться от записи таких изменений (сказать пользователю, что откат изменений после этой операции будет недоступен).

Способы реализации

C++: Qt

Operation-oriented

Здесь разработчики на славу постарались. С помощью Qt можно легко и просто реализовать Undo/Redo. Записывайте рецепт. Нам понадобиться: QUndoStack ^[5], QUndoCommand ^[6], а также QUndoView ^[7] и QUndoGroup ^[8] по вкусу. Сначала от QUndoCommand наследуем собственные классы, в которых должны быть переопределены undo() и redo(), также желательно переопределить id() для определения типа операции, чтобы потом в переопределённой mergeWith(const QUndoCommand *command) можно было проверить обе операции на совместимость. После этого создаём объект класса QUndoStack, и помещаем в него все новые операции. Для удобства, можно взять QAction *undo ^[9] и QAction *redo ^[10] из функций стека, которые потом можно добавить в меню, или прикрепить к кнопке. А если нужно использовать несколько стеков, тогда в этом поможет QUndoGroup, если нужно отобразить список операций: QUndoView.

Также, в QUndoStack можно отмечать clear state (чистое состояние), которые, например, может означать сохранён ли документ на диск и т.д. Вполне удобная реализация op-or undo/redo.

Я реализовал самый простой пример на Qt.

Хочу посмотреть!

Вот схема классов, к которой я пришёл (скорее всего, я сильно ошибаюсь на счёт направления стрелок...):

Здесь также упоминается некий «сервер», это на случай, если он тоже будет присутствовать и взаимодействовать с вашим приложением-клиентом. А вот и исходники ^[11] (считайте, что всё писал «на коленке»).

Value-oriented

Упс… Qt такого варианта не предоставил. Даже поиск по ключевым словам «Qt memento» не дал ничего. Ну и ладно, там и такого вполне достаточно, а если не достаточно, можно воспользоваться Native'ными методами.

C++: Native

Так как в Qt не посчитали нужным добавить value-oriented Undo/Redo, поэтому нужно будет искать либо готовые реализации (где можно встретить магическое для меня слово «Memento»), либо реализовывать придётся самим. В основном всё реализуется на основе шаблонов. Всё это можно без проблем найти. Я, например, нашёл вот этот проект ^[12] на GitHub. Тут реализованы сразу две идеи, можете взять и посмотреть, потестировать.

C#: .NET

Для меня C# и .NET пока что тёмные леса далёкой Сибири, но тем не менее, он мне очень и очень нужен. Поэтому стоит рассказать хотя бы о том, что мне удалось нагуглить.

Operation-oriented

Самыми хорошими примерами для меня были:

• Хорошая статья ^[13] на Хабрахабре.
• Интересный пост ^[14] про паттерн команд на .NET.
• И просто хороший пример ^[15] Undo/Redo с использованием Generics.

Вскоре нашлась и такая вот старая статья ^[16].

Быть может, что-то сможете найти и вы, а возможно на основе этого взять и написать свой велосипед гениальный код. Дерзайте.

Value-oriented

Вообще, для такого рода задач в .NET есть интерфейс IEditableObject ^[17], но придётся много чего реализовывать с нуля, хотя пример реализации есть прямо на MSDN. Тем не менее, мне очень понравилась библиотека DejaVu ^[18], ради которой даже написана целая статья ^[19] на Хабрахабре. Читайте, влюбляйтесь, пишите.

Есть ещё два примера, но они мне совсем не понравились:

• Пример 1 ^[20].
• Пример 2 ^[21].

Заключение

И так, что нужно знать, чтобы выбрать между двумя методами реализации только одну? Во-первых, реализацию вашего проекта, написан ли (будет?) он на основе команд, или просто изменение множества значений (если ни то, ни другое — думаю, лучше переписывать проект). Во-вторых, требования к памяти и производительности, ибо возможно именно из-за них придётся отказаться от одного варианта в пользу другого. В-третьих, нужно точно знать, что должно сохранятся и как, а что не должно вообще. Вот, в принципе и всё.

Удачи в будущем!

Автор: faserg1

Источник ^[22]