Хабрахабр

Текстовый редактор — это вам не высшая математика, тут думать надо

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

Алексей уже лет 10 пишет Intellij IDEA в JetBrains. В основе статьи — доклад Алексея Кудрявцева с Joker 2017. Под катом вы найдете видео и текстовую расшифровку доклада.

Чтобы понять, как устроен редактор, давайте его напишем.

Всё, наш простейший редактор готов.

Чтобы получить какой-нибудь символ по смещению, мы вызываем метод StringBuffer.charAt(i). Внутри редактора текст легче всего хранить в массиве символов, ну или, что то же самое (в смысле организации памяти), в Java-классе StringBuffer. А чтобы вставить в него символ, который мы напечатали на клавиатуре, вызовем метод StringBuffer.insert(), который вставит символ куда-то в середину.

Оно и просто и почти всегда быстро. Что самое интересное, несмотря на всю простоту и идиотичность этого редактора, — это самое хорошее представление, которое только можно выдумать.

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

Вот как это будет выглядеть в памяти:

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

Чтобы решить эту проблему вставки символа в середину, давным-давно придумали обходной манёвр под названием «Gap Buffer».

Gap Buffer

Gap — это зазор. Buffer — это, как вы догадываетесь, буфер. Структура данных «Gap Buffer» — это такой пустой буфер, который мы храним посередине нашего текста, на всякий случай. Если нам потребовалось что-то напечатать, мы используем этот текстовый маленький буфер для быстрого впечатывания.

Чтобы взять символ из редактора по какому-то смещению, нам нужно понять, находится ли он до или после этого буфера и немножечко подправить смещение. Структура данных у нас немножко поменялась — массив остался на месте, но появились два указателя: на начало буфера и на его конец. И, конечно, если мы вышли за пределы нашего буфера, его как-то пересоздать. А чтобы вставить символ, нам нужно сначала пододвинуть Gap Buffer к этому месту и заполнить его этими символами. Вот как это выглядит на картинке.

Потом мы используем этот буфер, впечатывая туда символы. Как видно, мы сначала долго двигаем на маленький gap-buffer (синенький прямоугольник) к месту редактирования (просто меняя местами символы с его левого и правого края по очереди).

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

Piece Table

Как раз в это время корпорация под названием Microsoft писала текстовый редактор Word. Они решили применить у себя другую идею для ускорения редактирования под названием «Piece Table», то есть «Таблица Кусочков». И они предложили текст редактора сохранять в этом же самом простейшем массиве символов, который меняться не будет, а все его изменения складывать в отдельную таблицу из этих самых отредактированных кусочков.

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

Для этого мы добавляем в таблицу кусочков два новых кусочка: один указывает на первый фрагмент («Облом»), а второй указывает на фрагмент после редактирования («овцы»). Здесь мы захотели удалить пробел по смещению 5. Потом добавляем новый текст («страдающие обломовщиной») в конец. Получается, что пробел из них исчезает, эти два кусочка склеиваются, и у нас получается новый текст уже без пробела: «Обломовцы». Используем дополнительный буфер и добавляем в таблицу кусочков (piece table) новый кусочек, который указывает на этот самый новый добавленный текст.

Плохо то, что становится сложнее добраться до символа, потому что перебирать все эти куски довольно тяжело. Как видите, никаких перемещений туда-сюда не происходит, весь текст остаётся на месте.

Подведем итоги.

Что хорошо в Piece Table:

  • Быстро вставлять;
  • Легко сделать undo;
  • Append-only.

Что плохо:

  • Ужасно сложно обращаться к документу;
  • Ужасно сложно реализовать.

Давайте посмотрим, кто у нас вообще обычно что использует.

Vi не заморачивается и использует просто список строчек. NetBeans, Eclipse и Emacs используют Gap Buffer — молодцы! Word использует Piece Table (недавно они выложили свои древние сорцы и там даже можно что-то понять).

До недавнего времени они не заморачивались и использовали JavaScript-список строчек. С Atom интереснее. Но вот эти кусочки у них хранятся не в списке, а в дереве, причём в так называемом splay tree — это дерево, которое саморегулируется при вставке в него, чтобы недавние вставки были быстрее. А потом решили всё переписать на C++ и наворотили довольно сложную структуру, которая вроде как похожа на Piece Table. Очень сложную штуку они наворотили.

Нет, вы тоже не правы, не piece table.
Да, совершенно верно, свой собственный велосипед. Что использует Intellij IDEA?
Нет, не gap-buffer.

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

Конкуррентность / Версионность

Для того, чтобы поддержать параллельность, операции с текстом обычно оборачивают в «synchronized», или в Read-/Write-локи. К сожалению, это всё не очень хорошо масштабируется. Другой подход — Immutable Text, то есть неизменяемое хранилище текста.

Вот как выглядит редактор с неизменяемым документом в качестве поддерживающей структуры данных.

Как устроена сама структура данных?

При обращении по какому-то смещению он пытается в этом дереве дойти до самого нижнего листа, и у него уже спросить символ, к которому мы обращались. Вместо массива символов у нас будет новый объект типа ImmutableText, хранящий текст в виде дерева, где в листах хранятся маленькие подстрочки. А при вставке текста он создает новое дерево и сохраняет его в старом месте.

Он реализован как дерево с двумя листами из подстрочек «Бес» и «калорийный». К примеру, у нас есть документ с текстом «Бескалорийный». И именно, создается новый корень, к которому привязываются уже три листа: «Бес», «довольно» и «калорийный». Когда мы хотим вставить в середину строчку «довольно», то создается новая версия нашего документа. А для листа, в который мы вставили строчку «довольно», отводится новая вершина. Причём два из этих новых листов могут ссылаться на первую версию нашего документа. Всё выглядит хорошо. Тут и первая версия, и вторая версии доступны одновременно и они все иммутабельные, неизменяемые.

Кто же использует какие хитрые структуры?

Xi-Editor — это новый блестящий редактор от Google — использует Persistent Rope. Вот, например, в GNOME какой-то их стандартный виджет использует структуру под названием Rope. За этими всеми названиями, на самом деле, скрывается более-менее одна и та же структура данных с древовидным представлением текста. А Intellij IDEA использует этот самый Immutable Tree. За исключением того, что GtkTextBuffer использует Mutable Rope, то есть дерево с изменяемыми вершинами, а Intellij IDEA и Xi-Editor — Immutable.

Эта фича позволяет печатать сразу в несколько мест, используя несколько кареток. Следующая вещь, которую нужно учитывать при разработке хранилища символов в современных IDE, называется «мультикаретки».

Если мы посмотрим, как наши структуры данных, которые мы рассмотрели, реагируют на мультикаретки, мы увидим кое-что интересное. Мы можем что-то печатать и одновременно в нескольких местах документа у нас вставляется то, что мы туда напечатали.

Это записывается в виде O(N). Если мы вставляем символ в наш самый первый примитивный редактор, для этого потребуется, естественно, линейное количество времени, чтобы сдвинуть туда-сюда кучу символов. Для редактора на основе Gap Buffer’а, в свою очередь, требуется уже константное время, для этого он и был придуман.

Для Piece Table тоже требуется константа.
Но все немножко меняется, если мы попробуем померять время вставки символа в редактор с мульти-каретками, то есть, вставки одновременно в несколько мест. Для immutable-дерева время зависит логарифмически от размера, потому что надо сначала пройти от вершины дерева до его листа — это логарифм, а потом для всех вершин на пути создать новые вершины для нового дерева — это опять логарифм. Всё так и происходит, за исключением Gap Buffer’а. С первого взгляда, время вроде как должно пропорционально увеличиться в C раз — число мест, куда вставляется символ. Почему так происходит? В его случае время, вместо C раз, неожиданно увеличивается какое-то непонятное C*L раз, где L — среднее расстояние между каретками.

Представим, что нам надо вставить строчку «, на» в два места в нашем документе.

Вот что происходит в редакторе в это время.

  • Создаем в редакторе gap-buffer (синенький прямоугольничек на рисунке);
  • Заводим две каретки (черные жирные вертикальные черты);
  • Пробуем печатать;
  • Вставляем запятую в наш Gap Buffer;
  • Должны теперь вставить её в место второй каретки;
  • Для этого нам нужно пододвинуть наш Gap Buffer до положения следующей каретки;
  • Впечатываем запятую во второе место;
  • Теперь нужно вставить следующий символ в положение первой каретки;
  • И мы должны пододвинуть наш Gap Buffer обратно;
  • Вставляем букву «н»;
  • И двигаем наш многострадальный буфер в место второй каретки;
  • Вставляем туда нашу «н»;
  • Двигаем буфер обратно, чтобы вставить следующий символ.

Чувствуете, к чему все идет?

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

Слишком много строчек? LineSet!

Какие еще есть проблемы в обычном текстовом редакторе? Самая сложная проблема — это скроллинг, то есть перерисовка редактора во время передвигания каретки на следующую строчку.

Для этого нам нужно быстро понять, какой строчке какое смещение соответствует. Когда редактор скроллится, мы должны понять, с какой строчки, с какого символа нам нужно начинать отрисовывать текст в нашем маленьком окошке.

И наоборот, по смещению в тексте понять, в какой строчке оно находится. Для этого есть очевидный интерфейс, когда мы по номеру строчки должны понять её смещение в тексте. Как это можно быстро сделать?

Например, так:

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

Другой способ ещё проще.

И тогда, чтобы по номеру строки найти смещение начала и конца, нужно будет обратиться по индексу. Записать в таблицу смещение начала строчек и конца строчек.

Что интересно, в реальном мире используется и тот, и другой способ.

А IDEA использует табличную структуру, для которой чтение — это быстрая константа, — это обращение по индексу в таблице, но зато перестроение — довольно медленное, потому что нужно всю таблицу перестроить при изменении длины какой-то строчки. Например, Eclipse использует такую деревянную структуру, которая, как видно, работает за логарифмическое время и на чтение, и на обновление.

Всё ещё слишком много строчек? Foldings!

Что ещё есть плохого, на что натыкаются в текстовых редакторах? Например, фолдинги. Это кусочки текста, которые можно «схлопнуть» и показать вместо них что-то другое.

Вот эти вот многоточия на зелёном фоне на картинке скрывают позади себя много символов, но, если нам их смотреть неинтересно (как в случае, например, длиннейших скучных Java-doc’ов или импорт-листов), мы их скрываем, схлопываем в это самое многоточие.

Как это организовано, расскажу чуть позже. И тут опять нужно понять, когда заканчивается и когда начинается регион, который нам нужно показать, и как это всё быстро обновлять?

Слишком длинные строчки? Soft wrap!

На картинке видно, что разработчик открыл JavaScript-файл после минимизации и сразу об этом пожалел. Также современные редакторы не могут жить без Soft wrap. Поэтому soft wrap ее принудительно разрывает на несколько строчек и впихивает в экран.
Как это организовано — позже. Вот эта огроменнейшая JavaScript-строка, когда мы её пытаемся показать в редакторе, ни в какой экран не влезет.

Слишком мало красоты

Например, подсветить некоторые слова. И, наконец, хочется ещё в текстовых редакторах навести красоту. На картинке выше ключевые слова подсвечены синим жирным, какие-то static методы италиком, какие-то аннотации — тоже другим цветом.

Так как же все-таки хранить и обрабатывать фолдинги, софт-врапы и хайлайтинги?
Оказывается, что всё это, в принципе, — одна и та же задача.

Слишком мало красоты? Range highlighters!

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

Естественно, в виде дерева. Как это обычно реализуется?

Проблема: слишком много красоты? Interval tree!

Мы складываем интервалы этих хайлайтингов в дерево поиска, так называемое интервальное дерево. Вот, например, у нас тут есть несколько жёлтых подсветок, которые мы хотим сохранить в тексте. Это то же самое дерево поиска, но немного хитрее, потому что нам надо хранить интервалы вместо числа.

Хотя и очень широко известная в computer science. А так как есть как здоровые, так и маленькие интервалы, то как их сортировать, друг с другом сравнивать и складывать в дерево — довольно нетривиальная задача. Так вот, берём и складываем все наши интервалы в дерево, и потом каждое изменение текста где-нибудь посередине приводит к логарифмическому изменению этого дерева. Посмотрите потом как-нибудь на досуге, как оно устроено. Для этого мы находим все доминантные вершины для этого символа и указываем, что все их подвершины надо отодвинуть на один символ вправо. Например, вставка символа должна привести в обновлению всех интервалов справа от этого символа.

Ещё хочется красоты? Ligatures!

Это разные красоты вроде того, как знак «!=» рисуется в виде большого глифа «не равно» и так далее. Ещё есть такая страшная штуковина — лигатуры, которую тоже бы хотелось поддержать. И, по нашему опыту, он, видимо, работает наипростейшим образом. К счастью, тут мы рассчитываем на свинговый механизм поддержки этих лигатур. Потом, при отрисовке строчки, Swing просто перебирает все эти пары, находит нужные и рисует их соответствующим образом. Внутри шрифта хранится список всех этих пар символов, которые, соединяясь вместе, образуют какую-то хитрую лигатуру. Если у вас в шрифте очень много лигатур, то, видимо, отображение его будет пропорционально тормозить.

Тормозит тайпинг

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

Если залезть внутрь Intellij IDEA и посмотреть, что происходит при нажатии какой-то кнопки, то там происходит, оказывается, следующий ужас:

  • При нажатии кнопки мы должны посмотреть, не находимся ли мы в completion popup’е, чтобы закрыть меню для completion’а, если мы, например, впечатываем какой-нибудь «Enter».
  • Нужно посмотреть, находится ли файл под какой-то хитрой системой контроля версий, вроде Perforce, которая должна сделать какие-то действия для начала редактирования.
  • Проверить, есть ли какой-то специальный регион в документе, в котором нельзя печатать, вроде каких-нибудь автогенерированных текстов.
  • Если документ заблокирован операцией, которая не закончилась, нужно завершить форматирование, и только потом продолжить.
  • Найти injected-документ, если он имеется в этом месте, потому что язык в нём будет другой, нужно совсем по-другому всё впечатывать.
  • Вызвать у всех плагинов auto popup handler, чтобы они могли впечатать, например, закрывающую и открывающую кавычку в нужном месте.
  • Для параметров info обновить окошечко, чтобы оно показывало нужные параметры, если мы туда переместились. У этих плагинов вызвать selection remove, чтобы они удалили selection нужным образом, зависящим от языка. И убрать этот selection физически, удалив его из документа.
  • Выбрать у всех плагинов typed handler, чтобы они обработали нужный символ для того, чтобы напечатать скобку поверх другой скобки.
  • Закрывающую структурную скобку обработать.
  • Запустить undo, подсчитать virtual space’ы и запустить write action.
  • Наконец, вставить символ в наш документ.

Ура!

Удалить символ, если наш буфер переполнился. Черт, нет, это не всё. Отскроллить editor view. Например, в консоли вызвать listener для того, чтобы все знали, что что-то поменялось. Вызвать какие-то ещё дурацкие listener’ы.

И что теперь происходит в редакторе, когда он узнал, что документ-то у нас поменялся и вызвался DocumentListener?

В Editor.documentChanged() происходит вот что:

  • Обновить error stripe;
  • Пересчитать gutter size, перерисовать;
  • Пересчитать editor component size, послать эвенты при изменении;
  • Подсчитать измененные строки и их координаты;
  • пересчитать soft wrap, если изменение его затронуло;
  • Вызвать repaint().

Этот repaint() — это просто указание для Swing, что данный регион на экране должен быть перерисован. Настоящая перерисовка произойдет, когда событие Repaint будет обработано очередью сообщений Swing.

То есть где-то через полчаса подойдет очередь обработки нашего события, вызовется метод repaint у соответствующей компоненты, который будет делать следующее:

Вызывается куча разных paint-методов, которые рисуют всё, что только возможно на свете в этом случае.

Ну что, может, соптимизируем это всё?

Поэтому мы в Intellij IDEA решили обмануть пользователя. Это всё, мягко говоря, довольно сложно.

И всё! Перед всякими этими ужасами, которые что-то пересчитывают и что-то записывают, мы вызываем маленький метод, который рисует эту несчастную букву прямо на том месте, куда пользователь её впечатывает. Под капотом всё ещё только начинается, но буковка-то уже перед ним горит. Пользователь счастлив, потому что он думает, что уже всё поменялось, а на самом-то деле — нет! Эта фича у нас называется «Zero latency typing». И поэтому все довольны.

Сейчас есть такая модная штука — так называемые коллаборативные редакторы.

Это когда один пользователь сидит в Индии, другой — в Японии, они пытаются в один и тот же Google Docs что-то напечатать и хотят какого-то предсказуемого результата. Что это такое?

Что особенного:

  • Тысячи пользователей;
  • Большая задержка.

Особенность тут такая, что огромное число пользователей это может делать одновременно, и сигнал очень долго может идти из Индии в Японию.

И придумали разные вещи, как убедиться, что всё работает как нужно. И из-за этого обычно в коллаборативных редакторах используют новомодные вещи вроде иммутабельности. Первый критерий — это сохранение интенции, «intention preservation». Это несколько критериев. И второй критерий — конвергенция. Это значит, что если кто-то впечатал символ, то рано или поздно символ из Индии приплывёт в Японию, и японец увидит именно то, что задумал индиец. Это значит, что символы из Индии и Японии рано или поздно преобразуются во что-то одно и то же и для Японии, и для Индии.

Operation transformation

Он работает так. Первый алгоритм, который был придуман для поддержки этой штуковины, называется «operation transformation». Фреймворк Operation transformation посылает эти операции во все другие места. Сидят индиец и японец, что-то печатают: один удаляет с конца букву, другой пририсовывает букву в начало. Например, когда у вас одновременно буква удалилась и появилась. Он должен понять, как нужно смержить операции, приходящие к нему, чтобы получилось хоть что-нибудь здравомыслящее. К сожалению, как видно из моего путаного объяснения, это дело довольно сложное. Он должен и там, и там отработать более-менее консистентно и прийти к одной и той же строчке.

Этот злополучный пример назвали «TP2 puzzle». Когда стали появляться первые реализации этого фреймворка, изумленные разработчики обнаружили, что есть универсальный пример, который все ломает.

После того, как это всё Operation transformation пытается слить в одно и то же, то должна, по идее, получиться вот эта строчка («ДАНА»). Один пользователь пририсовывает в начало строчки какие-то символы, другой всё это удаляет, а третий пририсовывает в конец. Потому что непонятно, куда вставлять нужно. Однако некоторые имплементации делали вот такую («НАДА»). На картинке выше видно, на каком уровне находится вся эта наука про Operation transformation, если из-за такого примитивного примера у них всё ломалось.

Они используют Operation transformation несмотря на перечисленные проблемы. Но несмотря на это некоторые люди всё равно это делают, вроде Google Docs, Google Wave и какого-то распределённого редактора Etherpad.

Conflict-free replicated data type

Люди тут пораскинули мозгами и решили: «Давайте сделаем проще, чем OT!» Число всяких хитрых сочетаний операций, которые нужно обрабатывать и сливать вместе, растет квадратично. Поэтому, вместо того, чтобы обрабатывать все сочетания, мы будем просто отправлять своё состояние вместе с операцией всем другим хостам таким образом, чтобы можно было с гарантией 100% это всё слить в один и тот же текст. Это называется «CRDT» (Conflict-free replicated data type).

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

Есть ли в природе такие функции и как их можно применить?

Например, для случая так называемых G-counter’ов, то есть счетчиков, которые только растут. Да. Потому что если у нас есть операция «+1» из Японии, другая «+1» из Индии, понятно, как из них сделать новое состояние — просто прибавить «2». Можно написать для этого счетчика функцию, которая действительно будет монотонной и так далее. Для этого достаточно взять один G-counter, который растёт всё время вверх, и все операции инкремента применять к нему. Но оказывается, что таким же образом можно делать ещё и произвольный счетчик, который можно инкрементировать и декрементировать. Чтобы получить актуальное состояние, нужно просто вычесть их содержимое, и у нас получится та самая монотонность. А все декременты применять к другому G-counterу, который будет расти вниз. Но самое главное — на произвольные строки. Это всё возможно распространить на произвольные множества. Оказывается, это довольно легко. Да, редактирование произвольных строк тоже можно сделать CRDT.

Conflict-free replicated inserts

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

И тогда понятно, что никаких разночтений быть не может, куда бы мы ни вставляли, мы точно будем знать место, даже после всяких других операций. Теперь вместо того, чтобы отправлять всем людям информацию, что мы вставляем по какому-то смещению какой-то символ, мы, вместо этого, будем говорить, между какими именно символами мы будем это вставлять. Вот, например, вместо того, чтобы посылать операцию о том, что мы по смещению 2 мы хотим вставить «РЖУ», мы будем посылать информацию, что между этой «У» и этой «Й» мы вставляем «РЖУ».

Conflict-free replicated deletes

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

Conflict-free replicated edits

И, на самом деле, CRDT даже где-то реализовано, например, в Xi-Editor от Google, который будет вставлен в их новомодную секретную операционную систему Fuchsia. Честно говоря, других примеров я не знаю, но это точно работает.
Ещё хотел бы рассказать о штуке, которая используется в этом новом иммутабельном мире под названием «Zipper». После того, как мы свои структуры сделали неизменяемыми, появились некоторые нюансы работы с ними. Вот, к примеру, у нас есть наше иммутабельное дерево с текстом. Нам хочется его поменять, (под «поменять» здесь, как вы понимаете, я имею в виду «создать новую версию»). Причем, нам хочется его менять в каком-то определённом месте и довольно активно. В редакторах это довольно часто встречается, когда в месте курсора мы постоянно что-то печатаем, вставляем и удаляем. Для этого функциональщики придумали структуру под названием Zipper.

Вот как это делается. Она имеет понятие так называемого курсора или текущего места для редактирования, сохраняя при этом полную иммутабельность.

Вызываем операцию на этом Zipper’е для перемещения по строке в место редактирования. Создаём Zipper для нашего документа, который содержит строку для редактирования («Ну надо же»). Для этого мы создаем новую вершину (красненькую), соответствующую текущей вершине, прикрепляем к ней ссылки на дочерние вершины из нашего дерева. В нашем случае — спуститься на вершину вправо вниз. При этом, добавляем ссылку на вершину вверх, чтобы не забыть, откуда пришли (красные стрелки). Теперь, чтобы переместить курсор Zipperа, мы спускаемся вправо-вниз и создаем также создаем новую вершину вместо той, на которой стояли. Теперь возвращаемся назад, идя по красным стрелкам вверх и заменяя их по пути на правильные ссылки на дочерние вершины. Дойдя таким образом до места редактирования, мы создаем новый лист взамен поредактированного текста (красный прямоугольник). Когда дойдем до вершины, у нас получится новое дерево с отредактированным листом.

Обратите внимание, как курсор помогает нам редактировать текущий кусочек дерева.

Во-первых, как ни странно, в теме текстовых редакторов, несмотря на её затхлость, существуют всякие интересные вещи. Какие выводы я хотел до вас донести? И в-третьих, иногда они настолько новые, что не работают с первого раза. Более того, в этой же теме появляются иногда новые, иногда неожиданные открытия. Спасибо. Зато интересно и можно согреться.

→ Репозиторий
→ Почта

Zipper data structure
Как устроен CRDT in Xi Editor
И вообще о древовидных структурах данных для текста
Что наворотили в Атоме

После доклада прошло много времени, и Микрософт успел вспомнить о своих корнях и переписать Visual Studio Code editor на Piece Table.
И вообще, многих людей почему-то потянуло на эксперименты.

Тогда ждём вас на Joker 2018. Хотите ещё больше мощных докладов, в том числе и о Java 11? До конференции осталось 17 дней. В этом году выступят: Джош Лонг, Джон МакКлин, Маркус Хирт, Роберт Шольте и другие не менее крутые спикеры. Билеты на сайте.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть