Верёвка

«Война и мир» — 2 904 144 знака. Если хранить роман одной строкой и вставить слово в середину, придётся сдвинуть полтора миллиона знаков, которые стоят после него. Одна такая правка незаметна. Но «заменить все» по 827 местам двигает хвост 827 раз — миллиард знаков. Редакторы так не делают. Ниже первая часть романа в верёвке: текст лежит кусками по 256 знаков в листьях дерева, и правка трогает один кусок и путь к нему.

Оранжевые точки — узлы, через которые прошла правка; их несколько десятков из девятисот с лишним, и ни один кусок, кроме разрезанного, не переписан. Счётчики ниже складывают, сколько знаков переписал бы каждый способ хранения. Строка сдвигает хвост. Буфер с зазором держит пустое место у курсора, и правка рядом с курсором почти бесплатна, а далёкая требует перенести зазор. Верёвка платит за путь в дереве и за разрезанный кусок, где бы ни была правка.

Идея

Верёвка — это текст, разложенный на куски по листьям сбалансированного дерева. Каждый узел знает суммарную длину своего поддерева, поэтому знак с номером p находится спуском: если левое поддерево длиннее p — налево, иначе вычитаем его длину и направо. Вставка и удаление — это разрез дерева в нужной позиции и склейка частей; разрез внутри куска делит кусок на два. Если узел знает ещё и число переводов строки в поддереве, тем же спуском находится строка любой позиции и начало строки с любым номером.

Разрез и склейка

Дерево удобнее всего взять декартово по неявному ключу: ключ узла — его место в тексте, его не хранят, а вычисляют по длинам поддеревьев. У дерева две операции, через которые выражается всё остальное.

• split(t, k) — разрезать текст на первые k знаков и остальное. Спуск идёт по длинам; если позиция k попадает внутрь куска, кусок делится на два новых узла, и это единственный текст, который копируется.
• merge(a, b) — склеить два текста. Склейка идёт по приоритетам, как в любом декартовом дереве, и текст не копирует вовсе.

Вставить строку s в позицию p: split по p, merge левой части, дерева из кусков s и правой части. Удалить k знаков с позиции p: split по p, у правой части split по k, merge крайних. Вырезать и вставить абзац в другое место — два разреза и две склейки, и сам абзац не копируется: переезжает поддерево.

У декартова дерева со случайными приоритетами ожидаемая глубина — O(log n), так что правка стоит O(log n + C) в среднем. Размер куска — компромисс: маленькие куски дёшево резать, но узлов больше и обход медленнее; большие — наоборот. В листинге куски до 512 знаков, в сцене — до 256; редакторы берут от сотен знаков до нескольких килобайт.

Номер строки

Редактору нужна не только позиция, но и «строка 4812, столбец 17»: номер строки показывают внизу экрана, к строке переходят, по строкам рисуют экран. Если в узле хранить число переводов строки в поддереве, номер строки знака p — это число переводов строки до него плюс один, и считается он тем же спуском: каждый раз, уходя направо, прибавляем переводы строки левого поддерева и куска. Обратный вопрос — где начинается строка с номером k — решается спуском по счётчикам переводов строки вместо длин. Листинг сверяет тысячу таких ответов с подсчётом в лоб.

Именно ради строк VS Code в 2018 году переписал хранение текста. Раньше файл лежал массивом строк, и 35-мегабайтный файл из 13,7 миллиона строк занимал около 600 мегабайт — по 40–60 байт на объект строки. Новый буфер — таблица кусков на красно-чёрном дереве, где узел помнит, где в его куске переводы строки, — занимает почти столько же, сколько сам файл.

Тонкости

• Набор по одной букве. Если каждую нажатую клавишу вставлять отдельным куском, дерево обрастёт кусками по одному знаку, и через страницу текста узлов будет больше, чем букв. Поэтому вставку рядом с концом недавнего куска дописывают в сам кусок, пока он не дорос до предела, а соседние короткие куски время от времени склеивают. Таблица кусков решает это иначе: всё набранное дописывается в конец одного большого буфера, и кусок, который на него указывает, просто удлиняется.
• Что считать позицией. Знак, байт UTF-8 и единица UTF-16 — три разные позиции одного места: буква «ж» — один знак, два байта и одна единица, а иероглиф или значок вне основной плоскости Юникода — четыре байта и две единицы. Редактор говорит с разными частями мира на разных языках, поэтому узлы хранят длины во всех нужных единицах, а кусок никогда не режут посреди знака.
• Склейка без копирования. Склеить два текста верёвкой — это склеить два дерева, O(log n), а не O(n), как у строк. Отсюда идея Бёма и соавторов делать верёвками вообще все длинные строки программы: конкатенации в цикле, которые у обычных строк дают квадратичное время, становятся почти бесплатными.

Код

Листинг кладёт в верёвку всю «Войну и мир» и делает две серии правок. Первая — переименовать героиню: каждое «Наташа» заменить на «Наталья», от начала романа к концу, как сделала бы команда «заменить всё». Вторая — двести вставок фразы в случайные места. Для каждой серии он считает переписанные знаки: у строки — сдвинутый хвост, у буфера с зазором — путь зазора от правки к правке, у верёвки — разрезанные куски. Вписанный текст засчитан всем. Результат сверяется с обычными строковыми операциями.

War and Peace: 2904144 characters, 11931 lines, pieces of up to 512
edit                                string moves  gap buffer  rope copies
rename, 827 places                    1096739396     2805233       588314
200 inserts in random places           291340865   178413225       103246
1000 line lookups: right; 7718 pieces in a tree 32 levels deep

Переименование по порядку — лучший случай для буфера с зазором: зазор один раз проходит весь роман, 2,8 миллиона знаков. Верёвке — 0,6 миллиона, строке — миллиард. Случайные вставки буфер не любит: зазор мечется по тексту, 178 миллионов знаков на двести правок. Верёвке всё равно, где правка: 103 тысячи, примерно по куску на вставку.

Сколько это стоит

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

Где работает

• Zed. Текст лежит в B+-дереве, где каждый узел хранит сводку поддерева: длину, переводы строки, длины в разных кодировках. Сами авторы говорят, что это не верёвка в классическом смысле, но устроено по той же идее: позиция переводится в строку и столбец за O(log n), а копии дерева неизменяемы и дешёвы.
• VS Code. С 2018 года — таблица кусков на красно-чёрном дереве: исходный файл и всё добавленное лежат в больших неизменяемых буферах, а дерево хранит ссылки на куски этих буферов и переводы строки в них.
• GNU Emacs. Буфер с зазором: текст в одном массиве, пустое место — в точке правки. Для набора текста лучше не придумать.
• Word. Таблица кусков идёт от редактора Bravo 1974 года, где её применил Чарльз Симони, и оттуда — в Word. Чарльз Кроули в 1998 году сравнил шесть способов хранить текст и назвал таблицу кусков лучшим в общем случае, а буфер с зазором — почти таким же хорошим.

История

Ханс Бём, Расс Аткинсон и Майкл Пласс в 1995 году опубликовали статью «Верёвки: альтернатива строкам». Они предложили хранить в виде деревьев не только тексты редактора, а вообще все строки программы, кроме совсем коротких: склейка тогда стоит O(1) или O(log n), подстрока не копируется, а неизменяемость даётся даром. По их словам, верёвки использовались в среде Cedar почти с самого её начала, но в литературе почти не обсуждались. Слово прижилось: верёвка — то, что сплетено из многих нитей-строк.

Задачи

В задаче — редактор с полной историей: правка любой прошлой версии создаёт новую, и нужно отвечать о любой версии. Копия на каждую версию не помещается в память; помогает персистентная верёвка.