Прим. Wunder Fund: в этой статье из блога VSCode рассказана увлекательная алгоритмическая история о решении проблемы раскрашивания скобок. Господам удалось достичь значительного ускорения этого процесса. Нам самим очень нравится решать подобные задачи при работе над торговой системой, а если они вам тоже интересны, то пишите:)
Когда имеешь дело с глубоко вложенными скобками в Visual Studio Code — может быть непросто понять то, у каких скобок есть пары, а у каких — нет.
Для того чтобы упростить решение этой задачи, в 2016 году пользователь CoenraadS разработал восхитительное расширение для VS Code — Bracket Pair Colorizer, позволяющее раскрашивать парные скобки, и опубликовал его в VS Code Marketplace. Это расширение стало весьма популярным, теперь оно, с более чем 6 миллионами установок, входит в 10 самых скачиваемых расширений.
Для того чтобы решить проблемы, касающиеся производительности и точности работы расширения, в 2018 году CoenraadS выпустил расширение Bracket Pair Colorizer 2, которое тоже стало популярным и было установлено более 3 миллионов раз.
Bracket Pair Colorizer — это хороший пример возможностей расширяемости VS Code. Оно интенсивно использует для раскрашивания скобок Decoration API.
Мы рады тому, что в VS Code Marketplace имеются и многие другие подобные расширения, написанные пользователями редактора. Каждое из них весьма креативно подходит к решению задачи идентификации парных скобок. Среди них — следующие: Rainbow Brackets, Subtle Match Brackets, Bracket Highlighter, Blockman и Bracket Lens. Такое разнообразие расширений указывает на то, что у пользователей VS Code имеется реальное стремление к тому, чтобы редактор лучше поддерживал бы механизмы раскрашивания парных скобок.
Проблема производительности
К несчастью, то, что природа Decoration API неинкрементальна, и то, что мы не даём расширениям доступ к информации о токенах VS Code, приводит к тому, что расширение Bracket Pair Colorizer медленно обрабатывает большие файлы. При вставке одной скобки в начале файла checker.ts, содержащего более 42000 строк кода, входящего в состав TypeScript-проекта, на обновление цветов всех пар скобок уходит около 10 секунд. В течение этих 10 секунд хост-процесс расширения нагружает процессор на 100%, и все возможности редактора, обеспечиваемые расширениями, вроде автозавершения или диагностики, перестают функционировать. Хорошо, правда, то, что архитектура VS Code обеспечивает работоспособность и отзывчивость интерфейса, и то, что документ при этом можно сохранить на диск.
CoenraadS знал об этой проблеме с производительностью и приложил значительные усилия к повышению скорости и точности работы второй версии расширения. Он переиспользовал токены и движок парсинга скобок из VS Code. Но API VS Code и архитектура расширений не рассчитаны на высокопроизводительную раскраску пар скобок в ситуации, когда речь идёт о сотнях тысяч пар скобок. В результате даже у расширения Bracket Pair Colorizer 2, уходит некоторое время на то, чтобы цвета скобок отразили бы новые уровни вложенности кода после вставки { в начало вышеупомянутого файла.
Хотя нас вполне устроило бы простое улучшение производительности расширения (что, конечно, потребовало бы создания более продвинутых API, оптимизированных для сценариев, создающих большую нагрузку на систему), асинхронная коммуникация между подсистемой рендеринга и хост-процессом расширения ограничивает то, как быстро может быть выполнена раскраска скобок в том случае, если соответствующий механизм реализован в виде расширения. Это ограничение обойти нельзя. В частности, цвета для пар скобок не должны запрашиваться в асинхронном режиме когда они появляются в области просмотра документа, так как это может привести к мерцанию при прокрутке больших файлов. Обсуждение этого вопроса можно найти здесь.
Наше решение задачи
Мы пошли другим путём. А именно, в обновлении VS Code 1.60, мы внедрили возможности рассматриваемого расширения в ядро VS Code и снизили время обработки вышеупомянутого документа до менее чем миллисекунды. В данном конкретном случае это означает ускорение раскрашивания скобок более чем в 10000 раз.
Соответствующую возможность можно включить, добавив в редактор следующую настройку:
"editor.bracketPairColorization.enabled": true.Теперь перекрашивание скобок выполняется незаметно для пользователя — даже в файлах, содержащих сотни тысяч пар скобок. Обратите внимание на следующее анимированное изображение, где новый уровень вложенности отражается изменением цвета скобки в строке 42788 сразу же после вставки { в строку номер 2.
После того, как мы решили перевести обработку скобок на уровень ядра, мы, кроме того, пользуясь случаем, решили максимально ускорить эту операцию. Кто не любит алгоритмических задачек?
Мы, не ограниченные особенностями общедоступного API, могли использовать (2,3)-деревья, нерекурсивный обход деревьев, двоичную арифметику, инкрементальный парсинг и другие подходы. Целью всего этого было уменьшение временной сложности алгоритма обновления данных о скобках, которую он показывает в худшем случае (то есть — время, необходимое на обработку пользовательского ввода, когда документ уже был открыт). Мы хотели перейти от временной сложности алгоритма O(N+E) к временной сложности O(log 3 N+E), при условии, что N — это размер документа, а E — это размер редактируемой области, исходя из предположения о том, что уровень вложенности пар скобок ограничен O(log N).
Мы, кроме того, использовав в своих целях существующие токены из подсистемы рендеринга и её механизм инкрементного обновления токенов, достигли дополнительного серьёзного (но неизменного) ускорения.
Поддержка механизма раскрашивания скобок в Visual Studio Code for the Web
Помимо того, что новая реализация механизма раскрашивания скобок оказалась производительнее старых решений, она ещё и поддерживается в VS Code for the Web. Узнать подробнее об этом редакторе — о VS Code, работающем в браузере — можно здесь. Благодаря тому, что Bracket Pair Colorizer 2 использует в своих целях движок токенизации VS Code, невозможно было перевести это расширение в формат так называемого веб-расширения.
Но наша новая система раскрашивания скобок не только работает в VS Code for the Web. Она функционирует ещё и в Monaco Editor!
Сложная и интересная задача раскрашивания пар скобок
В раскрашивании пар скобок самое главное — это быстрое нахождение всех скобок и их (абсолютного) уровня вложенности в области просмотра документа. Область просмотра документа можно описать как небольшую часть документа, представленную некоторым количеством строк и столбцов.
К сожалению, уровень вложенности скобки зависит от всех предшествующих ей символов: замена любого символа на открывающую скобку, {, обычно увеличивает уровень вложенности всех следующих за ней скобок.
В результате при первоначальном раскрашивании скобок в самом конце документа, необходимо обработать абсолютно каждый символ во всём документе.
В расширении Bracket Pair Colorizer эта задача решается путём повторной обработки всего документа, выполняемой каждый раз, когда в документ добавляют новую скобку, или когда из него удаляют одну из существующих скобок (это весьма разумно при обработке маленьких документов). После этого нужно убрать старые цвета скобок и окрасить их в новые, используя Decoration API VS Code, который отправляет в подсистему рендеринга сведения о цветах символов.
Как уже было показано, этот подход, при обработке больших документов, включающих в себя сотни тысяч пар скобок, которые нужно раскрасить, оказывается медленным. Так как расширение не может менять сведения об оформлении скобок инкрементно и должно предоставить системе новые сведения за один раз, подобное расширение просто не может работать заметно лучше. Но, всё равно, подсистема рендеринга весьма разумно (с использованием так называемого дерева интервалов) организует полученные ей сведения об оформлении скобок. В результате рендеринг документа всегда выполняется быстро после того, как будут получены сведения об оформлении символов, возможно — сотен тысяч символов.
Наша цель заключается в том, чтобы избавиться от необходимости переобработки всего документа после каждого нажатия на клавишу клавиатуры. Вместо этого время, необходимое для обработки одного эпизода правки текста должно расти, по мере роста длины документа, лишь (поли) логарифмически.
Но при этом нам нужна и возможность выполнять запросы сведений обо всех скобках и об их уровнях вложенности в области просмотра документа за (поли) логарифмическое время, как это было бы при использовании Decoration API VS Code (этот API использует вышеупомянутое дерево интервалов).
Алгоритмическая сложность
Если вам это неинтересно — вы вполне можете пропустить этот раздел.
Ниже N — это длина документа. Если выразить нашу цель более формально, то окажется, что заключается она в том, чтобы выйти на временную сложность алгоритма, не превышающую O(log k N+R), используемого для запроса сведений обо всех скобках в заданном месте документа размера R и с достаточно маленьким k (наша цель — k=2). Сведения о скобках запрашиваются при рендеринге содержимого области просмотра документа, в результате запрос этих сведений должен быть по-настоящему быстрым.
Правда, мы допускаем, что временная сложность инициализации документа, открываемого впервые, может быть равна O(N). Это неизбежно, так как при первоначальном раскрашивании скобок нужно обработать все символы документа. Далее, нас устраивает временная сложность обновления цветов скобок, соответствующая O(log j N+E), где E — это количество модифицированных или добавленных в документ символов. Опять же, нам нужно достаточно маленькое значение j (наша цель — j=3). Мы, кроме того, исходим из предположения, что уровень вложенности пар скобок не слишком велик, что он ограничен O(log N), и что количество закрывающих скобок без соответствующих им открывающих пренебрежимо мало. Документ, не соответствующий этим предположениям — это документ нетипичный, и алгоритм, который нам нужен, не обязан быстро обрабатывать подобные документы.
Семантика языка усложняет раскрашивание пар скобок
Нашу задачу по-настоящему усложняет выявление настоящих скобок, являющихся скобками (а не, например, частями строк) в соответствии с правилами языка, используемого в документе. В частности, мы не хотели бы выявлять открывающие или закрывающие скобки в комментариях или в строках, как показано в следующем примере кода, написанного на C:
{ /* } */ char str[] = "}"; }Тут открывающую скобку закрывает лишь третье вхождение символа }.
Всё становится ещё сложнее в языках, где токены языка не имеют регулярной структуры. Например — это TypeScript с JSX:
Соответствует ли скобка [1] скобке [2] или скобке [3]? Это зависит от длины выражения шаблонного литерала, что может правильно определить лишь токенизатор с неограниченным состоянием (а это — нерегулярный токенизатор).
Наше спасение — в токенах
К счастью, при решении задачи подсветки синтаксических конструкций языка, приходится сталкиваться с теми же проблемами: нужно ли выводить скобку [2] в предыдущем примере как строку или как обычный текст программы?
Как оказалось, простое игнорирование скобок в комментариях и строках, идентифицированных системой подсветки синтаксиса, хорошо подходит при обработке большинства пар скобок. До сих пор мы обнаружили лишь одну проблемную пару скобок, появляющуюся в конструкции вида < ... >. Дело в том, что обе такие скобки обычно используются в операциях сравнения и как часть определения обобщённых типов, но и в том и в другом случаях тип их токена оказывается одним и тем же.
В VS Code уже имеется эффективный и синхронный механизм для управления информацией о токенах, используемый для подсветки синтаксиса. Мы можем использовать этот механизм в своих целях для идентификации открывающих и закрывающих скобок.
Это — ещё одна сложная проблема, плохо влияющая на производительность, которая встала перед автором расширения Bracket Pair Colorization. У расширения нет доступа к этим токеном, оно должно находить их самостоятельно, выполняя работу, которая, в сущности, уже сделана. Мы долго думали о том, как можно эффективно и надёжно предоставить информацию о токенах расширениям, но пришли к выводу, что не можем этого сделать, не допустив значительной утечки информации о деталях реализации ядра VS Code через API, предназначенный для расширений. Так как расширению, вне зависимости от того, как оно получает сведения о токенах, всё ещё нужно отправлять системе сведения о цвете каждой скобки в документе, только лишь появление нового API даже не позволит решить проблем с производительностью.
Попутно можно отметить, что при внесении в самое начало документа изменения, влияющего на все следующие за ним токены (вроде — добавление в документ конструкции /* для C-подобных язкыков), VS Code не проводит одномоментную повторную токенизацию всего докумета. Вместо этого документ обрабатывается по частям в течение некоторого времени. Это обеспечивает работоспособность интерфейса, отсутствие «тормозов», несмотря даже на то, что токенизация производится в подсистеме рендеринга в синхронном режиме.
Базовый алгоритм
Нашей основной идеей было использование рекурсивного нисходящего парсера для создания абстрактного синтаксического дерева (abstract syntax tree, AST), которое описывает структуру всех пар скобок. Когда обнаруживается скобка — проверяется информация о токене. Если скобка входит в состав комментария или обычной строки — она пропускается. Токенизатор позволяет парсеру получать сведения о подобных скобках или о текстовых токенах.
Самое интересное тут в том, чтобы хранить сведения лишь о длине каждого узла (и, кроме того, чтобы имелись текстовые узлы для хранения всего того, что не является скобкой, чтобы перекрывать «пространства» между скобками), а не абсолютные данные о позиции начала и конца пары скобок. Если имеются лишь сведения о длине, узел, представляющий скобку, находящийся в определённой позиции, всё ещё можно эффективно найти в AST.
На следующей схеме показан пример AST с аннотациями, касающимися длины фрагментов.
Сравните это с классическим AST-представлением подобных данных, где используются абсолютные координаты начала и конца фрагментов.
Оба AST описывают один и тот же документ, но при обходе первого AST абсолютные позиции элементов нужно вычислять на ходу (для этого нужны весьма скромные вычислительные ресурсы), а во втором AST эти сведения хранятся в готовом виде.
Правда, при вставке единственного символа в первое дерево нужно пересчитать лишь длину самого узла и его родительского узла. А все остальные сведения о длинах фрагментов не меняются.
Когда в AST, как во втором случае, хранятся абсолютные позиции символов, получается, что в такой же ситуации нужно инкрементировать позицию каждого узла, находящегося в документе ниже добавленного символа.
Кроме того, отказавшись от хранения абсолютных смещений, можно наладить совместное использование листовых узлов, имеющих одинаковую длину, что позволит сэкономить память.
Вот как AST с аннотациями, касающимися длины фрагментов, можно описать средствами TypeScript:
type Length = ...;
type AST = BracketAST | BracketPairAST | ListAST | TextAST;
/** Описывает одну скобку, как, например, {, } или begin */
class BracketAST {
constructor(public length: Length) {}
}
/** Описывает пару скобок, соответствующих друг другу, а так же узел, находящийся между ними. Например - {...} */
class BracketPairAST {
constructor(
public openingBracket: BracketAST;
public child: BracketPairAST | ListAST | TextAST;
public closingBracket: BracketAST;
) {}
length = openingBracket.length + child.length + closingBracket.length;
}
/** Описывает список пар скобок или текстовых узлов. Например - ()...() */
class ListAST {
constructor(
public items: Array<BracketPairAST | TextAST>
) {}
length = items.sum(item => item.length);
}
/** Описывает текст, в котором нет скобок. */
class TextAST {
constructor(public length: Length) {}
}Выполнение запросов к такому дереву для получения списка всех скобок и уровня их вложенности выглядит сравнительно просто: выполняется обход в глубину, на ходу вычисляется абсолютная позиция текущего узла (путём сложения длин предыдущих узлов), пропускаются дочерние элементы узлов, которые полностью находятся до или после области документа, сведения о которой запрошены.
Этот базовый алгоритм уже является рабочим, однако с ним связано несколько открытых вопросов:
-
Как убедиться в том, что запрос сведений обо всех скобках в нужном фрагменте документа отличается нужной нам логарифмической временной сложностью и соответствующим уровнем производительности?
-
Как, при вводе текста, избежать создания нового AST с нуля?
-
Как обрабатывать поступление сведений о группах токенов? Когда открывается большой документ, в нашем распоряжении изначально нет сведений о токенах. Они поступают постепенно, в виде отдельных блоков данных.
Проверка того, что временная сложность алгоритма является логарифмической
При запросе информации о скобках в заданном диапазоне документа, производительность может очень сильно пострадать в том случае, если речь идёт о по-настоящему длинных списках скобок. Мы не можем выполнить быстрый бинарный поиск на их дочерних элементах для того, чтобы опустить все ненужные непересекающиеся узлы, так как нам нужно сложить длины всех узлов для вычисления абсолютной позиции на ходу. В худшем случае нужно обойти все узлы.
В следующем примере нужно просмотреть 13 узлов (выделены синим) до тех пор, пока мы не найдём скобку в позиции 24.
Хотя можно вычислить и кешировать суммы длин, что позволит использовать бинарный поиск, тут появляется та же проблема, которая характерна для деревьев, хранящих абсолютные позиции узлов: нужно пересчитывать все данные о позициях каждый раз, когда размер хотя бы одного узла растёт или уменьшается, что означает серьёзную вычислительную нагрузку при обработке больших списков.
Вместо этого мы сделали так, чтобы списки, в виде дочерних элементов, могли бы иметь другие списки:
class ListAST {
constructor(public items: Array<ListAST | BracketPairAST | TextAST>) {}
length = items.sum(item => item.length);
}Как это улучшает ситуацию?
Если мы можем гарантировать то, что у каждого узла имеется лишь ограниченное число дочерних узлов, и то, что получившаяся структура напоминает сбалансированное дерево, высота которого логарифмически зависит от числа его узлов, оказывается, что этого достаточно для того, чтобы обеспечить логарифмическую временную сложность запроса информации о скобках.
Поддерживаем деревья списков в сбалансированном состоянии
Для того чтобы обеспечить сбалансированность списков, мы используем (2,3)-деревья: у каждого узла должно быть минимум 2 и максимум 3 дочерних элемента. Все дочерние элементы списка должны иметь одинаковую высоту в сбалансированном дереве списков. Обратите внимание на то, что пары скобок рассматриваются в сбалансированном дереве как листовые узлы высоты 0, но в AST у них могут быть дочерние элементы.
При конструировании AST с нуля при инициализации системы мы, в первую очередь, собираем все сведения о дочерних элементах, а затем преобразуем эти сведения в сбалансированное дерево. Это можно сделать за линейное время.
Возможный вариант (2,3)-дерева, соответствующего вышеприведённому примеру, выглядит так, как показано ниже. Обратите внимание на то, что теперь нам достаточно просмотреть лишь 8 узлов (выделены синим) для того чтобы обнаружить пару скобок в позиции 24, и на то, что при конструировании этого дерева можно пользоваться определённой свободой, так как у списка может быть 2 или 3 дочерних элемента.
Анализ временной сложности для наихудшего случая
Если вам это неинтересно — вы вполне можете пропустить этот раздел.
Сейчас мы исходим из предположения о том, что каждый список похож на (2,3)-дерево, и в результате может иметь до 3 дочерних элементов.
Для того чтобы максимизировать время выполнения запроса, мы поработаем с документом, в котором имеется O(log N) вложенных пар скобок.
{
{
... O(log N) вложенных пар скобок
{
{} [1]
}
...
}
}Тут пока нет списков, но нам надо обойти O(log N) узлов для того чтобы найти пару скобок в позиции [1]. К счастью, документы, отличающиеся ещё большим уровнем вложенности, встречаются очень редко, то есть — нам не нужно принимать их во внимание при анализе наихудшего случая.
Теперь, если говорить об анализе наихудшей временной сложности нашего алгоритма, мы заполним документ данными до тех пор, пока его размер не окажется равным N, вставляя в него дополнительные пары скобок, в количестве O(Nlog N ), в каждую вложенную пару скобок:
{}{}{}{}{}{}{}{}... O(N / log N)
{
{}{}{}{}{}{}{}{}... O(N / log N)
{
... O(log N) вложенных пар скобок
{
{}{}{}{}{}{}{}{}... O(N / log N)
{} [1]
}
...
}
}
Каждый список скобок на одном и том же уровне вложенности приводит к появлению дерева высоты Olog Nlog N =Olog N — log log N =O(log N ).
В результате — для того чтобы найти узел в позиции [1], нужно обойти O(log N) сбалансированных деревьев высоты O(log N). После того, как мы нашли узел и хотим собрать все скобки в диапазоне размера R, нам нужно прочитать сведения из, самое большее, O® смежных листовых узлов, соединённых, самое большее, O(N +R) внутренними узлами.
Получается, что наихудшая временная сложность операции запроса информации о скобках равна O(N +R).
Кроме того, это показывает, что максимальная высота AST равняется O(N).
Инкрементные обновления сведений о скобках
Но самый интересный вопрос, касающийся высокопроизводительной раскраски пар скобок, остаётся открытым: если имеется актуальное (сбалансированное) AST и выполнена правка текста, приводящая к замене некоего фрагмента документа, как эффективно обновить дерево для того, чтобы в нём отразились бы результаты этой правки текста?
Наша идея заключается в том, чтобы переиспользовать рекурсивный нисходящий парсер, применяемый при инициализации системы, и добавить в систему некий механизм кеширования. Это позволит повторно использовать информацию об узлах, на которые правка данных не подействовала, а значит — не обрабатывать их при обновлении фрагмента дерева.
Когда рекурсивный нисходящий парсер разбирает список пар скобок в позиции p, а правка затрагивает позицию e, он в первую очередь проверяет, есть ли в предыдущем AST узел с длиной, самое большее, e-p, находящийся там, где была позиция p до изменения текста. Если такой узел найти удаётся — то этот узел не надо подвергать повторному парсингу, а токенизатор, работающий на более глубоком уровне, может просто обработать фрагмент, соответствующий длине узла. После обработки узла парсинг продолжается. Обратите внимание на то, что этот узел может представлять собой и отдельную пару скобок, и целый список. Кроме того, если удаётся найти несколько подобных узлов, подходящих для повторного использования, нужно выбрать самый длинный из них.
Следующий пример демонстрирует то, какие узлы можно использовать повторно (выделены зелёным), когда в документ вставляют единственную открывающую скобку (минуя узлы, соответствующие отдельным скобкам).
После обработки операции вставки текста, выполняемой путём повторного парсинга узлов, содержащих изменённый текст и переиспользования всех неизменённых узлов, обновлённое AST выглядит так, как показано ниже. Обратите внимание на то, что 11 узлов, подходящих для повторного использования, могут быть переиспользованы путём обработки 3 узлов — B, H и G, а лишь четыре узла (выделенные оранжевым) нужно создать заново.
Этот пример демонстрирует тот факт, что применение сбалансированных списков не только позволяет быстро запрашивать информацию о скобках, но и помогает повторно использовать сразу множество узлов.
Алгоритмическая сложность
Если вам это неинтересно — вы вполне можете пропустить этот раздел.
Давайте представим себе, что в ходе редактирования текста заменяется фрагмент, размер которого не превышает E. При этом количество символов в новом тексте так же не превышает E. Мы, кроме того, пока игнорируем тут редкий случай, когда у закрывающих скобок нет парных открывающих скобок.
Нам нужно подвергнуть повторному парсингу лишь те узлы, которые пересекаются с зоной редактирования текста. В результате повторному парсингу надо подвергнуть, самое большее, O(N +E) узлов (тут применимы те же рассуждения, что и при разговоре о временной сложности выполнения запросов о скобках). А все остальные узлы могут быть переиспользованы.
Очевидно то, что если узел не пересекается с диапазоном редактирования текста, тогда с ним не пересекаются и дочерние элементы этого узла. В результате нам нужно ориентироваться на переиспользование узлов, которые не пересекаются с диапазоном редактирования, но при этом их родительские узлы могут пересекаться с этим диапазоном (при таком подходе автоматически будут переиспользованы все узлы, в случае, когда с диапазоном редактирования не пересекаются ни они сами, ни их родительские узлы). Далее, подобные родительские узлы не могут быть полностью перекрыты диапазоном редактирования, в противном случае с ним пересекутся все их дочерние узлы. Но на каждом уровне AST присутствует, самое большее, два узла, частично пересекающихся с диапазоном редактирования. Так как в AST может быть, самое большее, O(N) уровней (что ограничено высотой AST), а у каждого узла может быть, самое большее, 3 дочерних элемента, количество всех узлов, подходящих для повторного использования, будет, в лучшем случае, равняться O(2 ∙3∙N)=O(N) .
В результате, чтобы сконструировать обновлённое дерево, нам надо произвести повторный парсинг, самое большее, O(N+ E) узлов, а повторно использовать можно будет O(N) узлов.
Это, кроме того, определяет и временную сложность операции обновления дерева, но тут есть один нюанс.
Как перебалансировать AST?
К сожалению, дерево, показанное в последнем примере, больше не является сбалансированным.
При комбинировании списка узлов, подходящих для повторного использования, с узлом, только что полученным от парсера, нужно приложить некоторые усилия для того, чтобы наше дерево оставалось бы (2,3)-деревом. Мы знаем о том, что переиспользованные узлы и новый узел уже являются (2,3)-деревьями, но они могут иметь различную высоту. В результате мы не можем просто создавать родительские узлы, так как все дочерние элементы узла (2,3)-дерева должны иметь одну и ту же высоту.
Как эффективно объединить все эти узлы, имеющие разную высоту, в единое (2,3)-дерево?
Эту задачу несложно свести к задаче добавления маленького дерева в начало или конец большого дерева. Если два дерева имеют одинаковую высоту, достаточно создать список, содержащий оба дочерних элемента. В противном случае мы вставляем маленькое дерево высоты h1 в более крупное дерево размера h2 и вполне можем нарушить устройство узлов, что произойдёт в том случае, если у них, в итоге, будет более 3 дочерних элементов (это похоже на то, как происходит операция вставки данных в (2,3)-деревья).
Так как время выполнения такой операции соответствует O(h2- h1), мы берём 3 соседних узла (a, b и c), которые хотим вставить в дерево, и вставляем первым лишь один из них (это может привести к увеличению высоты дерева), что зависит от того, какая пара отличается наименьшей разницей высоты. Этот процесс повторяется до тех пор, пока все узлы не будут вставлены в дерево. Продолжая оптимизацию этого процесса, мы ищем последовательности узлов, которые имеют одну и ту же высоту, и создаём родительские списки для них за линейное время.
Для того чтобы сбалансировать списки и из предыдущего примера, мы выполняем операцию конкатенации над их дочерними элементами (списки, выделенные красным, нарушают правила построения (2,3)-деревьев, оранжевые узлы имеют высоту, отличающуюся от ожидаемой, а зелёные узлы пересоздаются в процессе перебалансировки дерева).
Так как в несбалансированном дереве список B имеет высоту 2, а пара скобок — высоту 0, нам нужно присоединить к B, после чего обработка списка может считаться завершённой. Оставшееся (2,3)-дерево — это B, в результате оно становится новым корнем и заменяет список. Мы продолжаем работу с, его дочерний элемент и H имеют высоту, равную 0, а высота G равняется 1.
Мы, в первую очередь, объединяем и H и создаём новый родительский узел Y высоты 1 (так как и H имеют одинаковую высоту). Затем мы конкатенируем Y и G и создаём новый родительский список X (по той же причине). Затем X становится новым дочерним элементом родительской пары скобок, заменяя несбалансированный список.
В нашем примере операция балансировки помогла успешно уменьшить высоту самого верхнего списка с 3 до 2. Но общая высота AST выросла с 4 до 5, что плохо влияет на время выполнения запроса в наихудшем случае. Причиной этого является пара скобок, которая действует в роли листового узла в сбалансированном дереве списков, но, на самом деле, содержит ещё один список высоты 2.
Учёт высоты внутреннего AST узла при балансировке родительского списка может улучшить показатели, характерные для наихудшего случая, но это выходит за пределы теории (2,3)-деревьев.
Алгоритмическая сложность
Если вам это неинтересно — вы вполне можете пропустить этот раздел.
Нам надо произвести объединение, самое большее, O(N) узлов с максимальной высотой списка O(log N) (те, что мы переиспользуем), с дополнительными узлами в количестве O(N+ E), с высотой списков 0 (те, которые получены после повторного парсинга данных).
Так как конкатенация двух узлов разной высоты имеет временную сложность O(log N), и все узлы, полученные после повторного парсинга данных в списке, являются смежными и отличаются высотой списка 0, временная сложность всей операции по обновлению дерева составляет, самое большее, O(N+ E), учитывая то, что поиск узла, подходящего для повторного использования, может быть выполнен достаточно быстро.
Как эффективно находить узлы, подходящие для повторного использования?
Для решения этой задачи используются два механизма: средство сопоставления новых позиций элементов с позициями элементов до правки (класс BeforeEditPositionMapper) и средство считывания данных узлов (класс NodeReader).
Класс BeforeEditPositionMapper осуществляет, если это возможно, сопоставление позиции в новом документе (после выполнения правки) со старым документом (до выполнения правки). Он, кроме того, сообщает нам о расстоянии между текущей позицией и следующей правкой (или 0, если мы находимся в том месте, где выполняется правка). Делается это за время O(1).
При обработке операции правки текста и при парсинге узла этот компонент даёт нам позицию узла, который мы, возможно, сможем переиспользовать, а так же сообщает о максимальной длине, которую может иметь этот узел. Очевидно то, что узел, который мы хотим переиспользовать, должен быть меньше расстояния до следующей правки.
Класс NodeReader способен быстро находить самый длинный узел, удовлетворяющий заданному предикату и находящийся на заданной позиции в AST. Для того чтобы найти узел, который можно использовать повторно, мы используем BeforeEditPositionMapper для того, чтобы узнать его старую позицию и его максимальную разрешённую длину, а затем используем NodeReader для того, чтобы найти этот узел. Если мы такой узел нашли — мы знаем о том, что он не изменялся, и что мы можем его переиспользовать, не обращая внимания на его длину.
Так как запросы к NodeReader выполняются с передачей ему монотонно возрастающих сведений об интересующей нас позиции, ему не нужно каждый раз начинать поиск узлов с самого начала. Он может продолжить поиск с того места, где был найден последний переиспользованный узел. Самое главное тут — это алгоритм обхода дерева, в котором не используется рекурсия, который способен заходить в узлы, но может их пропускать или возвращаться к родительским узлам. Когда удаётся обнаружить узел, подходящий для повторного использования, обход дерева прекращается и продолжается лишь после следующего запроса к NodeReader.
Сложность однократного выполнения запроса к NodeReader выглядит как O(N), но мы более чем уверены, что амортизированная сложность, характеризующая все запросы, выполненные в ходе одной операции обновления дерева, тоже соответствует O(N). В конце концов, к классу NodeReader обращаются за сведениями о позициях, на которые не повлияли правки текста, и выполнение этих операций всегда производится с как можно меньшими затратами времени, когда система идёт от одного узла, подходящего для повторного использования, к другому такому узлу. В результате мы думаем, что класс NodeReader достаточно эффективен и не оказывает негативного влияния на вычислительную сложность алгоритма обновления дерева.
Обновление токенов
Когда в начало документов, содержащих код на C-подобном языке, вставляют конструкцию /, и при этом в тексте, идущем после неё, нет /, весь документ превращается в один большой комментарий, что приводит к изменению всех токенов.
Так как токенизация текста производится в том же процессе, что и рендеринг, в синхронном режиме, повторную токенизацию нельзя произвести за один проход, не «подвесив» при этом интерфейс редактора.
Поэтому сведения о токенах обновляются фрагментарно, в течение некоторого времени, в результате цикл событий JavaScript не блокируется на слишком длительные промежутки времени. Хотя этот подход и не позволяет уменьшить общее время блокировки главного потока, он улучшает отзывчивость интерфейса во время процесса обновления сведений о токенах. Тот же механизм используется и при первоначальной токенизации документа.
К счастью, благодаря инкрементальному механизму обновления сведений о парах скобок в AST, мы можем сразу же применить новые сведения о токенах, рассматривая новые группы токенов как операции правки текста. Эти токены заменяют данные о тех участках текста, которые подверглись повторной токенизации. После того как система получит все обновлённые токены, AST, содержащее сведения о парах скобок, гарантированно будет в том же состоянии, в котором оно пребывало бы в том случае, если было бы создано с нуля — даже если пользователь редактировал документ во время повторной токенизации текста.
При таком подходе не только токенизация оказывается достаточно производительной в том случае, если все токены в документы изменяются. Производительной оказывается и операция раскрашивания пар скобок.
Но, если документ содержит множество непарных скобок в комментариях, цвет скобок в конце документа может мерцать, так как парсер скобок постепенно узнаёт о том, что на определённые скобки внимания обращать не нужно.
Для того чтобы избежать мерцания пар скобок при открытии документа и при прокрутке его до самого конца, мы поддерживаем два AST, содержащих информацию о скобках, используя их до тех пор, пока процесс токенизации текста не будем завершён. Первое AST создаётся без учёта информации о токенах, оно не получает сведения об обновлениях токенов. Второе дерево изначально является клоном первого, но оно получает обновления токенов и всё сильнее и сильнее отличается от первого дерева по мере продвижения процесса токенизации и по мере применения сведений об обновлениях токенов. Изначально первое AST используется для выполнения запросов о скобках, а после полной токенизации документа его место занимает второе дерево.
Так как операция глубокого клонирования дерева почти так же ресурсозатратна, как и повторный парсинг документа, мы реализовали схему копирования при записи, что позволило нам выйти на временную сложность операции клонирования, соответствующую O(1).
Кодирование длины
Область просмотра документа в редакторе описывается в терминах номеров строк и столбцов. Ожидается, что и сведения о цветовом оформлении символов тоже будут выражены в виде диапазонов значений, основанных на номерах строк и столбцов.
Для того чтобы избежать преобразований между смещением и позициями, основанными на номерах строк и столбцов (что может быть сделано за время O(log N), мы и в AST используем сведения о позициях символов, основанные на номерах строк и столбцов.
Обратите внимание на то, что этот подход очень сильно отличается от подхода, предусматривающего применение структур данных, напрямую индексируемых номерами строк (как, например, в случае использования массива строк, описывающего содержимое документа). В частности, этот подход позволяет выполнять единообразные операции бинарного поиска и в применении к строкам целиком, и в применении к содержимому строк.
Сложить два значения длины несложно, но для выполнения этой операции нужно понять то, в каких именно условиях она выполняется. А именно, хотя сведения о номерах строк просто складывают, количество столбцов первого показателя длины включается в состав итогового показателя только в том случае, если второй показатель длины соответствует нулю строк.
Удивительно то, что большая часть кода не нуждается в знании о том, как именно представлены длины элементов. Это серьёзно усложняет лишь код BeforeEditPositionMapper, так как этому классу приходится учитывать тот факт, что в одну строку может быть внесено несколько правок.
Если говорить о деталях реализации, то мы кодируем подобные сведения о длине в виде единственного числа для того, чтобы ослабить нагрузку на память. JavaScript поддерживает целые числа вплоть до 253+1, поэтому мы можем использовать до 26 бит для хранения сведений о количестве строк и столбцов. Но v8, к сожалению, хранит числа, большие, чем 231, в куче, в результате этот трюк с кодированием данных оказался не таким эффективным, как мы того ожидали.
Дальнейшие трудности: непарные скобки
До сих пор мы исходили из предположения о том, что у каждой открывающей скобки имеется соответствующая ей закрывающая скобка. Но нам хотелось бы поддерживать и открывающие скобки без закрывающих, и закрывающие без открывающих. Красота рекурсивного нисходящего парсера заключается в том, что он позволяет использовать наборы привязок для улучшения работы системы при возникновении ошибок парсинга.
Рассмотрим следующий пример:
( [1]
} [2]
) [3]Ясно, что } в позиции [2] не закрывает какую-либо пару скобок и представляется в виде закрывающей скобки для пока не открытой пары скобок. А вот скобки в позициях [1] и [3] формируют замечательную пару. Правда, если вставить в начале этого кода {, ситуация меняется:
{ [0]
( [1]
} [2]
) [3]Теперь должны совпасть скобки [0] и [2], скобка [1] должна быть представлена как открывающая скобка без закрывающей, а скобка [3] — как закрывающая без открывающей.
В частности, в следующем примере скобка [1] должна быть представлена в виде незакрытой скобки, область действия этой скобки оканчивается на скобке [2]:
{
( [1]
} [2]
{}В противном случае открытие круглой скобки будет способно повлиять на уровень вложенности следующих за ней пар скобок, никак с ней не связанных.
Для того чтобы поддерживать больше вариантов восстановления при возникновении ошибок, можно использовать наборы привязок для наблюдения за набором токенов, появление которых ожидается в некоей ситуации, с которым может продолжить работу сущность, пользующаяся услугами парсера.
В предыдущем примере, в позиции 1, набор привязок может выглядеть как { } }. В результате, при парсинге пары скобок в позиции [1], обнаруживается неожиданно появившаяся скобка в позиции [2]. Парсеру это не нравится, он возвращает то, что можно назвать «незакрытой парой скобок».
В первом примере набор привязок в позиции [2] выглядит как { ) }, но тут появляется неожиданный символ }. Так как он не является частью набора привязок — он считается «неоткрытой парой скобок»
Это нужно учитывать при переиспользовании узлов: пару ( } ) нельзя использовать повторно в том случае, если перед ней окажется {. Мы используем наборы бит для кодирования наборов привязок и находим для каждого узла набор содержащихся в нём непарных закрывающих скобок. Если узлы пересекаются — мы не можем повторно использовать такой узел. Но, к счастью, существует совсем немного типов скобок, поэтому это не слишком воздействует на производительность.
Что дальше?
Создание эффективной системы раскраски пар скобок было увлекательной задачей. С применением новых структур данных мы смогли лучше решить некоторые задачи, имеющие отношение к работе со скобками. Например — общую задачу сопоставления парных скобок или задачу цветового выделения области, соответствующей открывающей и закрывающей скобкам.
Даже несмотря на то, что JavaScript — это, возможно, не самый лучший язык для написания высокопроизводительного кода, различные задачи можно значительно ускорить, если снизить асимптотическую сложность алгоритмов, особенно — если речь идёт о работе с большими объёмами входных данных.
О, а приходите к нам работать? 😏
Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.
Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.
Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.
Присоединяйтесь к нашей команде.
Автор:
mr-pickles
