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


    В этой статье мы продолжим рассказывать о том, как мы делали 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, на какие элементарные операции его разбить и как обойтись минимальным количеством сохраняемых в памяти данных. Это позволило нам создать несложную в реализации модель документа, которая достаточно эффективно использует память и не требует значительных вычислительных ресурсов как при обходе модели во время форматирования документа, так и при внесении в неё самых разнообразных изменений.

    Предыдущая статья на эту тему | Следующая статья на эту тему
    Developer Soft
    80,00
    Компания
    Поделиться публикацией

    Похожие публикации

    Комментарии 43

      +2
      «Почему собака виляет хвостом? Потому что она умнее. Если бы хвост был умнее, он бы вилял собакой»
        0
        Согласен. Что бы Undo/Redo не вилял программой изначально должно быть правильное проектирование. Это я еще понял лет 8 назад когда третий раз переписывал свою прорамму (хобби было, а не что то комерческое) и начал использовать ЮМЛ — вот тогда у меня собака и стала умнее.
          –3
          Что такое ЮМЛ?
            +1
            UML
              +2
                +1
                thx, думал русское какое то сокращение
          +2
          Первое что пришло бы в голову хранить не полные версии. Типа diff и хранить только патчи…
            +1
            боюсь на каждый чих вычислять диффку проца не напасешься…
              +1
              Это первое что в голову пришло, а не
              >> на каждое действие сохранять состояние документа целиком

              Если начать копать, то можно попытаться разбить весь текст на примитивы (позиция от и до которой произошло изменение) и уже к ним делать те же diff… Да и вообще в сторону системы контроля версий смотреть. NetBeans хранит историю на диске, вроде больших тормозов не наблюдал.
            +2
            а что происходит с перекрёстными участками. Если, например, выделен «orld» и для него применён курсив?
              +1
              Опять разбивать. Получится следующее:
              «Hello » — normal
              «W» — bold
              «or» — bold + italic
              «ld!» — normal
                +1
                «ld» — italic, конечно
                "!" — normal
              +2
              У GOF построение текстового редактора подробно описано в терминах паттернов, где решены все ваши проблемы. Авторы, вы их читали?
                0
                realtimecollisiondetection.net/blog/?p=81#comment-3276
                О вреде паттернов =)

                  0
                    0
                    Ну а может, всё-таки вначале почитать GoF, а не давать подобные ссылки? Лично вот я вижу, что авторы данного поста пытались что-то изобрести и изобрели почти что паттерн «Команда», только кривоватый. В результате было потрачено лишнее время, а ведь гораздо быстрее можно было бы решить задачу, всего лишь прочитав GoF. Автор же гневной статьи как раз пишет, что «Design patterns are spoonfeed material for brainless programmers incapable of independent thought». Кстати, статус самих паттернов описан и у GoF, и если внимательно читать, то всё становится понятным. Ну и никто, конечно же, не мешает криворукому программеру криво использовать паттерны, как, собтвенно, никто ему же не мешает криво использовать Java, C#, Python. Но ведь никто не ругает сами языки (точнее, ругают, но на то есть совсем другие причины) и учебники по ним.

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

                    И, прежде чем ругать паттерны, хочу заметить одну вещь. У любой проблемы есть достаточно много аспектов. Какие-то из них более-менее очевидны, какие-то нет. Непосредственный опыт позволяет с этими неочевидными проблемами столкнуться нос к носу. И кто-то уже сталкивался не раз. И уже предостерёг остальных от решения проблемы «не так», написав «как нужно». Ну, например, GoF. А хотите писать код, который преподнесёт в будущем немало сюрпризов и ругани — выкидывайте нафиг все книги и будьте «программистами, способными независимо мыслить». Я вас предупреждал.
                  +1
                  Жжоте, дядьки. Всё уже придумали до Вас
                    +4
                    Прежде, чем давать ссылки неплохо было бы самому понимать для чего предназначен тот или иной паттерн. Паттерн «команда» предназначен для инкапсуляции тех или иных действий с возможностью отката или повторения этих действий. Автор же показал декомпозицию части функциональности текстового редактора на элементарные операции, т.е именно тот элементарный функционал (семантику операции), который будет выполнять тот или иной экземпляр паттерны «комманда».
                      0
                      Ну, прямо скажем, автор про декомпозицию функциональности текстового редактора говорит уже после того, как изобрёл паттерн «Команда». Да и декомпозицию можно сделать по-разному. Кстати, про структуру текста неплохо написано у тех же GoF.
                        0
                        ну я посмотрю, как вы по GOF нормальный Rich сделаете
                          –1
                          А вы мне денежку на работу кинете?
                    +2
                    изменяемый объект — это ссылка. неизменяемый — значение. а то, что вы реализовали для форматирования — ленивое копирование.

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

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

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

                      при этом механизмы отката и подсветки полностью независимы и не накладывают друг на друга никаких ограничений.
                        +2
                        Очень сильно от задачи зависит. Вот у Вас допущение, изменился один параграф, только его и перекрашиваем. Многострочные комментарии сразу идут лесом. Если в Вашей задаче это неважно, значит Вам повезло.
                          0
                          не идут %-) параграфы являются блоками только в тексте, а в програмном коде другие блоки и различные коментарии в частности

                          вот, попробуй: mojura.110mb.com/i-component/?client/main/iface/field/field.html
                            0
                            неплохая штука.
                            хотя с комментами как раз не всё гладко. однострочный внутри многострочного делает плохо.
                              0
                              хех, какой-то косяк с приоритетами в регулярке ._."
                        +2
                        Если бы всё ограничивалось только текстом, то, возможно, и имело бы смысл городить огород и пытаться сделать более универсальную вещь. Но кроме текста в документе встречается много всякой всячины, например списки, картинки, таблицы, поля, букмарки и т.д. и т.п. И тут уже не затачиваясь на апи сделать ничего не получится.
                        В теории всё просто, читай GOF и будет тебе счастье, на практике же грабельки разложены более замысловато.
                          0
                          а в чём проблема со списками таблицами и прочей лабудой? идея представления документа в виде неизменяемого дерева со ссылками на блоки данных — универсальна.

                          дай ссылку на это чтиво чтоли
                        +2
                        Сборище закинутых самовлюбленных умников, получивших красные дипломы, просидев ночами за книгами и выучив их все наизусть, каждый из который старается опустить других и продемонстрировать объемы своего головного мозга, не нагруженного больше ничем кроме заученными книгами и всепоглащающами мыслями о самовозвышении и блядском унижении других.
                        фуф, извините, наболело )
                          0
                          а в чём проблема со списками таблицами и прочей лабудой? идея представления документа в виде неизменяемого дерева со ссылками на блоки данных — универсальна.

                          дай ссылку на это чтиво
                            +2
                            Дело в том, что те же таблицы лежат не в дереве, а в параллельной структуре, которая «опирается» на дерево (ссылается на его узлы). И сама таблица имеет структуру не совсем уж примитивную. А букмарки вообще представляют собой именованный диапазон документа. Причем начинаться или заканчиваться он запросто может прямо посреди run. Списки и стили тоже в своей иерархии лежат, из узлов дерева на них только косвенные ссылки есть.

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

                              этот стандарт и есть тот самый гоф? о0
                                0
                                Формально никакого. На практике, то что в этом документе написано один в один соответствует внутренней организации данных в ворде. Отступления от этой организации, конечно, возможны, правда ведут к гемморою, например в тех же импортах/экспортах. Мы когда файлы OpenOffice читали, задолбались конвертировать его модель.

                                Букмарки — навигация, пометка частей документа для дальнейшей обработки.

                                А GoF это сюда.
                                  +1
                                  а како смысле делать также как в ворде? не проще ли тогда просто сделать свой интерфейс к нему и всё?

                                  яснее не стало. если это типа якорей их хтмл, то никаких сложностей не вижу

                                  оно на русском есть?
                                    0
                                    не проще, он зараза денег стоит за каждое рабочее место.
                                      0
                                      оупенофис?
                                        0
                                        подумал про ворда.
                                      0
                              0
                              гомэн, это не тебе. а у тебя от чёго такой сильный баттхёрт? %-)
                                +1
                                Это официальное отношение сотрудника компании DevExpress к аудитории Хабра?

                                Кстати, зачем Вы убрали информацию о компании из профиля? Ещё неделю назад была (когда был предыдущий топик про Undo/Redo от одномённой компании). Уволились, что ли? ;)
                                  0
                                  Это моя личная оценка основываясь на первом десятке комметариев, может эмоции одержали вверх, не надо смешивать личное
                                0
                                К слову, Undo/Redo с блекджеком делается элементарно на immutable-объектах.

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                Самое читаемое