Некоторые IDE и текстовые редакторы парсят исходный файл целиком при каждом изменении, что тормозит, а некоторые делают это построчно с помощью регулярных выражений, что тоже тормозит и не даёт качественной подсветки кода, т.к. теряется контекст. Для решения этих проблем был создан 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 используют регулярные выражения, которые применяются построчно, для подсветки кода. Это приводит к тому, что, в отличие от редакторов опирающихся на синтаксические деревья, они не могут знать контекст и подсветка оставляет желать лучшего. Да и производительностью на больших объемах строк такой подход похвастаться не может.
Но проблемы у редакторов использующих регулярные выражения возникают не только когда строк кода много, но и когда она всего одна, зато очень длинная. В этом случае такие редакторы ограничивают максимальную длину строки для подсветки, иначе парсинг регулярками занимал бы слишком много времени. Если редактор оперирует синтаксическими деревьями, то ни количество строк, ни их длина ему не помеха.
Свёртка кода
Самый простой способ найти блоки кода для свёртывания - ориентироваться на величину отступов, т.к. обычно многострочный блок кода имеет единый размер отступов на каждой строке, что приводит к путанице, когда это не так. Зная синтаксическую структуру кода, текстовый редактор может сворачивать блоки кода независимо от величины отступов.
Расширение выделения
Также знание о синтаксической структуре кода даёт нам такой мощный инструмент как расширение выделения.
Обработка ошибок
Tree-sitter устойчив к синтаксическим ошибкам в коде и достаточно умён чтобы понять какая часть кода (синтаксического дерева) лишняя. Это позволяет текстовым редакторам подсвечивать только ошибочные участки кода, а не окрашивать всё красным.
Скорость
Самая главная фишка tree-sitter - инкрементальный парсинг, т.е. при изменении кода исходный файл не будет обработан целиком - обработана будет только изменённая часть, что делает возможным запускать такой парсинг на каждое нажатие клавиш в текстовом редакторе без задержек в отклике интерфейса.
Как это работает
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 готов к использованию в виде библиотеки для следующих языков программирования:
Haskell
JavaScript (Node.js)
JavaScript (Wasm)
Lua
OCaml
Python
Ruby
Rust
Swift
Kotlin
Java
Парсеры
Готовы к использованию парсеры следующих языков:
Bash
C
C#
C++
Common Lisp
CSS
CUDA
DOT
Elm
Emacs Lisp
Eno
ERB / EJS
Fennel
GLSL (OpenGL Shading Language)
Go
HCL
HTML
Java
JavaScript
JSON
Lua
Make
Markdown
OCaml
PHP
Python
Ruby
Rust
R
S-expressions
SPARQL
SystemRDL
Svelte
TOML
Turtle
TypeScript
Verilog
VHDL
Vue
YAML
WASM
WGSL WebGPU Shading Language
В разработке:
Agda
Elixir
Erlang
Dockerfile
Go mod
Hack
Haskell
Julia
Kotlin
Nix
Objective-C
Org
Perl
Protocol Buffers
Scala
Sourcepawn
Swift
SQL
Проекты
Список некоторых проектов использующих tree-sitter:
Atom - текстовый редактор от GitHub, с которого и началась история использования tree-sitter.
GitHub использует для различных фич: подсветка некоторых языков, навигация по коду и т.д.
Neovim (экспериментально с версии 0.5) с помощью nvim-treesitter.
Плагин для Emacs.
Diffsitter - difftool для AST.
Tree-grepper - как grep, но для AST. Позволяет искать в исходных файлах с учетом синтаксической структуры.
Runestone - текстовый редактор для iOS.
Zee - консольный текстовый редактор написаный на Rust.
Semantic - Haskell-библиотека и консольная утилита для парсинга, анализа и сравнения исходного кода.
Полезные ссылки
Официальный сайт проекта
Проект на GitHub
Выступления Max Brunsfeld на Strange Loop 2018, FOSDEM 2018 и GitHub Universe 2017
A Comprehensive Introduction to Tree-sitter
How to write a linter using tree-sitter in an hour
Static Analysis at GitHub by Timothy Clem and Patrick Thomson (PDF)
