Tree-sitter: обзор инкрементального парсера
Некоторые IDE и текстовые редакторы парсят исходный файл целиком при каждом изменении, что может тормозить на больших файлах, а некоторые делают это построчно с помощью регулярных выражений, что тоже тормозит и не даёт качественной подсветки кода, т.к. теряется контекст. Для решения этих проблем в недрах GitHub был создан tree-sitter — инкрементальный парсер, который используют всё больше и больше проектов. Давайте разбираться зачем и почему.
Введение с официального сайта гласит:
Tree-sitter это инструмент для создания парсеров и библиотека инкрементального парсинга. Он может построить синтаксическое дерево для исходного файла и эффективно обновлять синтаксическое дерево при изменении исходного файла. Tree-sitter нацелен быть:
Достаточно общим, чтобы парсить любой язык программирования.
Достаточно быстрым, чтобы парсить на каждое нажатие клавиши в текстовом редакторе.
Достаточно надёжным, чтобы выдавать пригодные результаты даже при наличии синтаксических ошибок.
Не иметь зависимостей, чтобы библиотека (написанная на чистом C) могла быть встроена в любое приложение.
Далее на примерах разберём как это влияет на работу IDE и текстовых редакторов (слайды взяты с выступления «Tree-sitter — a new parsing system for programming tools» by Max Brunsfeld).
Подсветка кода
Такие редакторы текста как TextMate, Sublime Text или Visual Studio Code используют регулярные выражения, которые применяются построчно, для подсветки кода. Это приводит к тому, что, в отличие от редакторов опирающихся на синтаксические деревья, они не могут знать контекст и подсветка оставляет желать лучшего. Да и производительностью на больших объемах строк такой подход похвастаться не может.
Сравнение подсветки кода Sublime Text 3, VS Code, Atom без tree-sitter и Atom с tree-sitter. Atom с tree-sitter подсвечивает больше, т.к. понимает структуру и контекст.
Но проблемы у редакторов использующих регулярные выражения возникают не только когда строк кода много, но и когда она всего одна, зато очень длинная. В этом случае такие редакторы ограничивают максимальную длину строки для подсветки, иначе парсинг регулярками занимал бы слишком много времени. Если редактор оперирует синтаксическими деревьями, то ни количество строк, ни их длина ему не помеха.
Сравнение подсветки длинных строк в текстовом редакторе основанном на регулярных выражениях (вверху) и текстовом редакторе с tree-sitter (внизу).
Свёртка кода
Самый простой способ найти блоки кода для свёртывания — ориентироваться на величину отступов, т.к. обычно многострочный блок кода имеет единый размер отступов на каждой строке, что приводит к путанице, когда это не так. Зная синтаксическую структуру кода, текстовый редактор может сворачивать блоки кода независимо от величины отступов.
Тело метода можно свернуть, даже если в коде нет никаких отступов.
Расширение выделения
Также знание о синтаксической структуре кода даёт нам такой мощный инструмент как расширение выделения.
Обработка ошибок
Tree-sitter устойчив к синтаксическим ошибкам в коде и достаточно умён чтобы понять какая часть кода (синтаксического дерева) лишняя. Это позволяет текстовым редакторам подсвечивать только ошибочные участки кода, а не окрашивать всё красным.
Синтаксическое дерево с обнаруженной ошибочной веткой, что позволяет подсветить это место в коде.
Скорость
Самая главная фишка tree-sitter — инкрементальный парсинг, т.е. при изменении кода исходный файл не будет обработан целиком — обработана будет только изменённая часть, что делает возможным запускать такой парсинг на каждое нажатие клавиш в текстовом редакторе без задержек в отклике интерфейса.
Парсинг 20 тысяч строк кода на JavaScript занимает 54 милисекунды. На каком железе — не указано.
Как это работает
Tree-sitter использует GLR-парсер — обобщённый LR-парсер. GLR-алгоритм парсинга похож на LR, но приспособлен для работы с неоднозначностями.
Если кратко, то LR парсер имеет стэк и таблицу правил. Он читает токены слева-направо и сверяясь с таблицей правил преобразует стэк. Проблема возникает, если синтаксис языка допускает неоднозначности. Например, выражения ниже начинаются одинаково (x = (y)) и понять что мы в данный момент парсим можно только дойдя до ; или =>.
x = (y); // выражение в скобках
x = (y) => z; // лямбдаТут на помощь и приходит GLR-парсер. При наличии неоднозначностей он параллельно перебирает все возможные варианты не используя backtracking. Т.е. стэк распараллеливается на несколько возможных вариантов, но в итоге остаётся только один, а все неправильные предположения отбрасываются.
Подробнее и с картинками можно посмотреть в выступлении Tree-sitter — a new parsing system for programming tools или в статье A Comprehensive Introduction to Tree-sitter.
Песочница
Tree-sitter можно попробовать в песочнице прямо в браузере. Выбираем свой любимый язык программирования и пишем код. Снизу в реальном времени будет результат парсинга.
Пример работы песочницы.
В песочнице tree-sitter показывает только именованные узлы (Named Nodes, подсвечены синим), в то время как анонимные узлы (Anonymous Nodes), такие как скобки или точка с запятой, скрыты, но присутствуют в дереве. Также некоторые узлы могут иметь поля (Fields, подсвечены серым), которые позволяют проще ориентироваться в структуре дерева.
Ещё одной фишкой tree-sitter «из коробки» является возможность поиска в дереве по шаблону. Для этого активируем чекбокс Query в песочнице. Синтаксис запросов основан на S-выражениях и позволяет задавать весьма сложные шаблоны для поиска. Подробнее про поиск и синтаксис запросов можно почитать в документации.
Запросы для поиска первого и последнего параметров функции.
Использование
В основном, как не сложно догадаться, tree-sitter используют текстовые редакторы, но есть и другие проекты: поиск по коду, diff и т.д. Для tree-sitter существуют библиотеки для популярных языков программирования, а также готовые парсеры различных языков, если вы вдруг решите использовать его в своём проекте или придумаете какой-то новый. Например, линтер за час написать.
Биндинги
Tree-sitter готов к использованию в виде библиотеки для следующих языков программирования:
Парсеры
Готовы к использованию парсеры следующих языков:
В разработке:
Проекты
Список некоторых проектов использующих tree-sitter:
Atom — текстовый редактор от GitHub, с которого и началась история использования tree-sitter.
GitHub использует для различных фич: подсветка некоторых языков, навигация по коду и т.д.
Anycode — расширение для VSCode от Microsoft для поддержки фичей Language Server в ситуациях, когда Language Server нет.
Neovim (экспериментально с версии 0.5) с помощью nvim-treesitter.
Плагин для Emacs.
Ещё один плагин для Emacs для стуктурного редактирования кода.
Diffsitter — difftool для AST.
Tree-grepper — как grep, но для AST. Позволяет искать в исходных файлах с учетом синтаксической структуры.
Runestone — текстовый редактор для iOS.
Zee — консольный текстовый редактор написаный на Rust.
Zed — ещё не вышедший текстовый редактор от создателя tree-sitter ориентированный на совместную разработку написанный на Rust.
Semantic — Haskell-библиотека и консольная утилита для парсинга, анализа и сравнения исходного кода.
