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 используют регулярные выражения, которые применяются построчно, для подсветки кода. Это приводит к тому, что, в отличие от редакторов опирающихся на синтаксические деревья, они не могут знать контекст и подсветка оставляет желать лучшего. Да и производительностью на больших объемах строк такой подход похвастаться не может.

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

Свёртка кода

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

Расширение выделения

Также знание о синтаксической структуре кода даёт нам такой мощный инструмент как расширение выделения.

Обработка ошибок

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 существуют библиотеки для популярных языков программирования, а также готовые парсеры различных языков, если вы вдруг решите использовать его в своём проекте или придумаете какой-то новый. Например, линтер за час написать.

Создание парсера

Грамматика задаётся в специальном файле grammar.js. Как не трудно догадаться, описывается она с помощью JavaScript. Процесс этот не самый простой и подробнее о нём можно почитать в документации. Можно посмотреть на примеры грамматик для Java и JavaScript.

Биндинги

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 использует для различных фич: подсветка некоторых языков, навигация по коду и т.д.

• 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-библиотека и консольная утилита для парсинга, анализа и сравнения исходного кода.

Полезные ссылки

• Официальный сайт проекта

• Проект на GitHub

• Выступления Max Brunsfeld на Strange Loop 2018, FOSDEM 2018 и GitHub Universe 2017

• A Comprehensive Introduction to Tree-sitter

• Introductory to Treesitter

• How to write a linter using tree-sitter in an hour

• Static Analysis at GitHub by Timothy Clem and Patrick Thomson (PDF)

• EmacsConf 2021: Tree-edit: Structural editing for Java, Python, C, and beyond! - Ethan Leba