Pull to refresh

Undo/Redo — Хвост виляет собакой

Developer Soft corporate blog

В этой статье мы продолжим рассказывать о том, как мы делали Undo/Redo в текстовом редакторе XtraRichEdit.

Началось всё с того, что нашей команде отдали исходники концепта текстового редактора с пожеланием довести этот концепт до ума. Несмотря на то, что времени на разработку концепта было потрачено всего-то месяц, умел он немало: можно было вводить и удалять текст, двигать курсор по горизонтали и вертикали.

Нам же оставалось добавить возможность форматирования участков текста (шрифт, его размер и т.п.) и все остальные «мелочи» типа параграфов со всеми их свойствами, стилей и т.п. А ещё концепт не умел делать Undo/Redo.

За те две недели, что пришлось вникать в исходники концепта, стало окончательно ясно, что единственный способ прикрутить к нему Undo/Redo, не переписывая его с нуля – это на каждое действие сохранять состояние документа целиком (фактически делать копию документа):

public class DocumentHistoryItem : HistoryItem {
    readonly DocumentState previousState;
    readonly DocumentState nextState;

    public DocumentHistoryItem(DocumentState previousState, DocumentState nextState) {
        this.previousState = previousState;
        this.nextState = nextState;
    }

    public override void Undo(Document document) {
        document.ApplyState(previousState);
    }
    public override void Redo(Document document) {
        document.ApplyState(nextState);
    }
}

Это, разумеется, было неприемлемо, т.к. при таком подходе использовалось бы слишком много памяти. Представьте себе документ размером хотя бы в 1 мегабайт. Задача для второклассника: сколько клавиш надо нажать до того, как кончится память, если каждое нажатие клавиши приводит к изменению документа и записи в undo buffer?

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

Например, было нетрудно сохранить данные по изменению имени шрифта. Для этого необходимо было сохранить старое и новое имя шрифта, чтобы иметь возможность как отмены, так и повтора действия. Аналогично, для размера шрифта — надо было хранить старый и новый размеры. Однако, если за одно действие (например в диалоге Font) изменялось и имя шрифта, и его размер, то было необходимо сохранять уже 2 элемента в undo buffer. А ведь кроме собственно имени шрифта и его размеров было необходимо хранить информацию, к какому участку текста эти значения должны быть применены.

В конце концов, сделав несколько неудачных попыток встроить Undo/Redo в существующий код, мы пришли к выводу: для того, чтобы не было проблем с Undo/Redo, необходимо специальным образом перепроектировать структуры данных и алгоритмы.

Было решено, что каждое действие пользователя над документом должно преобразовываться в последовательность элементарных операций над документом. Каждая такая операция должна быть настолько элементарна, чтобы для неё можно было очень легко реализовать обратную операцию. Такая операция также хранит минимально необходимое количество данных, необходимых для её прямого и обратного выполнения. Элементарные операции упаковываются в единый составной элемент и помещаются в буфер undo:

public class CompositeHistoryItem : HistoryItem {
    readonly List<HistoryItem> items = new List<HistoryItem>();

    public void AddItem(HistoryItem item) {
        items.Add(item);
    }
    protected override void UndoCore() {
        for (int i = items.Count - 1; i >= 0; i--)
            items[i].Undo();
    }
    protected override void RedoCore() {
        int count = items.Count;
        for (int i = 0; i < count; i++)
            items[i].Redo();
    }
}

Отметим, что откат элементов составной операции проводится в обратном порядке, а накат — в прямом.

Для того, чтобы разбить действия на элементарные операции, нам пришлось специальным образом организовать структуры данных. Текст внутри параграфов мы разбили на интервалы (runs) таким образом, чтобы форматирование текста внутри каждого интервала было одним и тем же.



При изменении форматирования произвольного выделенного текста, сначала осуществлялось разбиение текста на интервалы в соответствие с выделением, а потом изменялось форматирование тех интервалов, что находились внутри выделения. Таким образом было выделено 3 элементарные операции «разделить интервал», «объединить 2 соседних интервала» и «изменить форматирование интервала».

Последняя элементарная операция заслуживает отдельного рассмотрения. Чтобы минимизировать объём данных, хранимых в буфере undo, объект, содержащий свойства текста в интервале был разделен на два подобъекта: изменяемый (CharacterFormattingBase) и неизменяемый (CharacterFormattingInfo). Неизменяемые объекты сохранялись в списке-кэше (CharacterFormattingInfoCache), причем элементы списка были уникальны и из списка никогда не удалялись. Изменяемые объекты хранили лишь индекс неизменяемого объекта в списке.



Это позволило изменение любого свойства (или сразу нескольких свойств, это уже дело техники) изменяемого объекта свести к поиску в кэше индекса подходящего неизменяемого объекта и сохранению его в изменяемом объекте. Если же подходящий объект найти не удавалось, то он создавался и добавлялся в кэш.

Используя такой подход, мы добились сохранения в буфере undo всего лишь 2 индексов, старого и нового, для изменения любого количества свойств интервала (разумеется, в пределах одной транзакции).

На первый взгляд, создаётся впечатление, что постоянно растущий кэш нерационально использует память. Но в действительности это не так. Дело в том, что различных комбинаций свойств текста в реальных документах не так уж и много. Более того, бОльшая часть текста, как правило, имеет одно и то же форматирование. И вместо того, чтобы в каждом интервале дублировать все значения свойств отвечающих за форматирование, мы дублируем лишь индекс единственного объекта в кэше.

И, наконец, рассмотрим пример действия и его разбиение на элементарные операции.

Изначально имеется сплошной и единственный участок текста:



Выделим жирным шрифтом часть текста «Wor».

Это действие можно разбить на 3 элементарных операции:

Разбиваем участок текста на 2 смежных участка.



Разбиваем правый участок текста еще на 2 участка.



Для участка с индексом 1 применяем жирное начертание шрифта.



Каждая из операций предельно проста, легко обратима и хранит минимум данных. Так, для операции разрезания участка текста, достаточно сохранить индекс разрезаемого участка и индекс буквы на участке, перед которой произойдет разрез. Операция применения стиля шрифта сохраняет номер участка текста (run index), а также старый и новый индексы объектов CharacterFormattingInfo в кэше.

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

При разработке XtraRichEdit мы изначально стали использовать подход «от Undo/Redo». При проектировании каждого действия мы прежде всего продумывали то, как уложить это действие в концепцию Undo/Redo, на какие элементарные операции его разбить и как обойтись минимальным количеством сохраняемых в памяти данных. Это позволило нам создать несложную в реализации модель документа, которая достаточно эффективно использует память и не требует значительных вычислительных ресурсов как при обходе модели во время форматирования документа, так и при внесении в неё самых разнообразных изменений.

Предыдущая статья на эту тему | Следующая статья на эту тему
Tags:
Hubs:
Total votes 44: ↑34 and ↓10 +24
Views 13K
Comments Comments 43

Information

Founded
1998
Location
Россия
Website
www.developersoft.ru
Employees
201–500 employees
Registered