Tree Sitter in Review Board: Shipping 167 Languages

Part 1: Introduction
Part 2: Shipping 167 Languages
Part 3: Applying Highlighting
Part 4: Translating Lua Patterns

Just add the dependency?

In Part 1, I discussed what Tree Sitter is, and why we’re going to start using it in Review Board.

So what pieces do we actually need in order for this to work? The major barrier to pulling in Tree Sitter for any project is that it runs as native code, and each individual grammar is shipped as a separate project. Fortunately for us, there are two Python packages that make it relatively easy to pull in. The py-tree-sitter package gives us the bindings for the framework, and tree-sitter-language-pack is a binary package that ships precompiled grammars for most of the popular languages as well as a large number of less common ones.

So a quick update to add the dependencies, a little bit of code to wire it up, and we’re done, right? Unfortunately, not so fast.

In order to understand how the Tree Sitter API works, it’s worth digging into the primitives:

Language

A Tree Sitter grammar for a given programming language. These are expensive to load, but can be cached and shared across threads.

Parser

A lightweight object that contains the state for a given parsing operation. These use the Language to do the actual parsing of content.

Tree

The result returned by a Parser. This is the abstract syntax tree for the parsed content. The nodes in the tree each have a byte range within the content, and a name. The actual value for the name is opaque; each language implementation chooses its own names.

Queries

A way to match parts of the parsed tree. These are defined using S-expressions that get loaded in from a text file and pre-compiled so they can run fast. For syntax highlighting, the queries we care about are usually distributed in two separate files: a highlights.scm file provides the queries to actually highlight the code, and an injections.scm provides queries that tell us where one language gets injected into another (for example, JavaScript inside of <script> tags in an HTML file).

These basic API primitives are all provided by py-tree-sitter, and the code behind each Language comes from the grammars in tree-sitter-language-pack. What’s missing are those files with the S-expressions for the queries.

Here’s what that looks like. This is an excerpt from the highlights queries from tree-sitter-c, the grammar for the C programming language.

(identifier) @variable

((identifier) @constant
 (#match? @constant "^[A-Z][A-Z\\d_]*$"))

"break" @keyword
"case" @keyword
"const" @keyword

"--" @operator
"-" @operator
"-=" @operator

(string_literal) @string
(system_lib_string) @string

(call_expression
 function: (identifier) @function)

The raw tree has the parsed nodes with very simple names like “identifier”, “string_literal”, etc. The queries search through this tree, find nodes like a leaf that contains the text “const”, and return a series of matches annotated with the result names (telling us that said “const” node should be highlighted as a @keyword).

Queries can also make use of predicates and directives.

A predicate is basically a function implemented in the query engine that can perform some check and return a boolean result. In the above example, #match? is a predicate which does a regular expression match on the captured value. Predicate names in the query language always end with ?.

A directive is similar, but instead of affecting whether a query matches or not, it allows the engine to store metadata on the match or manipulate the match in some way. An example of this would be the detection of the language name on a fenced code block in Markdown (where it would extract the language name and set it as metadata for the injection engine to use). Directive names always end with !.

There are two big problems:

1. tree-sitter-language-pack doesn’t actually ship any query files. Each Tree Sitter grammar lives in its own repo, and many of those contain a queries directory with the .scm file(s) we’re looking for. To collect highlights for all the languages we can parse, we need to scan through a ton of different repos.
2. Queries are very tightly coupled to grammar implementations. If any of the individual queries in a file include a node name that does not exist in the compiled grammar, attempting to load the queries will fail. This means that we need to make sure that whatever queries we find correspond to the same version of the grammar that was compiled and shipped in the version of tree-sitter-language-pack that we use. For some grammars under heavy development, the node names can change at almost every commit.

Vendoring the queries

Here’s the task: find highlights.scm queries for each supported language, but ensure that they also are a match for the exact version of the grammar that exists in our pinned version of tree-sitter-language-pack.

For each language, we:

• Find the relevant repository, usually but not always on GitHub.
• Clone the repository to the local disk.
• Load the Language from tree-sitter-language-pack.
• Attempt to load queries/highlights.scm and queries/injections.scm. If those files contains node names which cannot be compiled with the given Language, move up to the parent commit and try again.
• Once a version of the queries is found which is confirmed to work against the shipped version of the grammar, copy them into our repo and write a lockfile with info about the repository and commit that we got it from.

Now we have the bindings, we have the grammars, and we have queries. Time to highlight!

It was at this point that I discovered that the highlights.scm files shipped by many Tree Sitter grammars are extremely underwhelming. For example, those highlights from tree-sitter-c? They define keywords and operators, but those lists are missing a number of things from the language spec. A << bit-shift operator will be highlighted as plain text because it’s missing from the queries!

I had naively assumed that the great syntax highlighting I get inside Neovim would magically translate to great syntax highlighting in Review Board.

Enter nvim-treesitter

When I set up my Neovim configuration, I happily configured nvim-treesitter without really understanding what it was. I went to take a closer look and discovered that the bulk of the package is made up of Tree Sitter query files. Because these are used daily by people who really care about their editor, incomplete or broken definitions get fixed pretty fast. nvim-treesitter’s queries for the C language are four times the size of the ones in tree-sitter-c. This not only includes a complete list of all keywords and operators, but also definitions for symbols like __declspec or __clang__ which are not part of the language spec but exist in real code in the real world.

I redirected our query vendoring script to look at the nvim-treesitter repo instead, and got to extracting queries. With a couple of exceptions I was able to find query files that match the tree-sitter-language-pack grammar versions.

At this point, highlighting was starting to improve, but I hit an unpleasant discovery: the queries in nvim-treesitter are full of predicates and directives which I didn’t have.

The Tree Sitter library defines a few built-in predicates and directives:

• #eq?, #any-eq?, #not-eq?, #any-not-eq?
• #match?, #any-match?, #not-match?
• #any-of?, #not-any-of?
• #is?, #is-not?
• #set!
• #select-adjacent!
• #strip!

Reading through my new query files, I found a bunch of others. These are implemented in either Neovim itself, or inside the nvim-treesitter plugin:

• #contains?, #any-contains?
• #has-ancestor?, #not-has-ancestor?
• #has-parent?, #not-has-parent?
• #lua-match?, #not-lua-match?
• #gsub!
• #make-range!
• #offset!

The Neovim queries also make use of an inheritance feature to reduce duplication. The C++ queries start out with the C queries and then build on top:

; inherits: c

((identifier) @variable.member
  (#lua-match? @variable.member "^m_.*$"))
...

So now we have a next step: we need to implement these predicates in our own engine. py-tree-sitter allows us to specify a predicate handler when running queries. This is a callable that takes in the predicate name, a set of arguments, the pattern index (which query is being run), and the current captures from the queries (a mapping from the capture name to a list of matching nodes).

def predicate_handler(
    predicate: str,
    args: Sequence[tuple[str, Literal['capture', 'string']]],
    pattern_index: int,
    captures: Mapping[str, Sequence[tree_sitter.Node]],
) -> bool:
    ...

Implementing most of these new predicates and directives is pretty simple. The contains? ones just are a check to see if the captured text includes the predicate argument(s). The parent? and ancestor? checks need to scan up the tree from the captured nodes to see if the node names match. make-range! stores some info that we don’t care about in Review Board, so it’s a no-op. offset! stores a delta to the captured range, which is used for some languages to handle injections.

Here’s a slightly simplified example of what one of those predicate implementations looks like:

def _has_parent(
    args: PredicateArgs,
    captures: PredicateCaptures,
    pattern_index: int,
    query: tree_sitter.Query,
) -> bool:
    capture_id = args[0][0]
    parent_types = {arg[0] for arg in args[1:]}

    for node in captures.get(capture_id):
        if (parent := node.parent) and parent.type in parent_types:
            return True

    return False

lua-match? and gsub! are the tricky ones. These two are pretty heavily used throughout the queries, so we need to figure out a way to handle them. lua-match? is like match?, checking to see if the pattern matches. gsub! does a substitution, replacing the matched section with other text before storing as metadata. Unfortunately, because Neovim’s entire Tree Sitter infrastructure is implemented in Lua, both of these use Lua patterns instead of regular expressions.

My Lua experience is pretty thin, limited to only what I’ve needed for interacting with software that uses it, such as creating my editor config. I hadn’t worked at all with Lua patterns before, so I was a little surprised to find a language that doesn’t use some variant of Perl-compatible regular expressions. It makes sense: a full PCRE implementation is huge, and Lua is meant to be a small language that can be embedded in all sorts of places. In order to implement these, I pulled in the luapatt library (more on that in a future post).

All the pieces are in place now. We have:

• The Tree Sitter library
• A bunch of Tree Sitter grammars
• highlights.scm files with the queries for highlights, and where appropriate, injections.scm files for marking injections
• Implementations of all the necessary predicates and directives

Next up: using the queries to actually apply syntax highlighting.