Tree Sitter in Review Board: Translating Lua Patterns

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

In Tree Sitter, many of the queries that are written use pattern matching. Here’s an example:

(normal_command
 (identifier) @keyword.repeat
 (#match? @keyword.repeat "\\c^(continue|break)$"))

This query looks at nodes which the parser identified as normal_command and applies the @keyword.repeat highlight.

As discussed in Part 2, we’re getting most of our queries from nvim-treesitter. While several of these use Tree Sitter’s built-in #match? predicate (that uses regular expressions), the bulk of them actually use a Neovim-specific predicate called #lua-match? (which uses Lua patterns).

Here’s an example from the Python queries:

((attribute
  attribute: (identifier) @variable.member)
  (#lua-match? @variable.member "^[%l_].*$"))

What is a Lua Pattern?

The Lua language has no regular expression support. A full PCRE-compatible regex engine is huge, and Lua is designed to be embedded in a huge range of applications and devices.

Instead, Lua has patterns. This is a deliberately smaller language that looks similar to regex. There are three major differences:

• Lua patterns define a variety of character classes. Each of these represents some kind of set of characters (for example, %a is the equivalent of regex [A-Za-z]).
• The - character is used as a non-greedy quantifier.
• There are a handful of constructs with no regex analogue, such as %b, which matches balanced strings (such as %b() to match balanced parentheses).
• % is used as an escape character, and the rules about what needs to be escaped are different.

The first implementation

In order to implement the #lua-match? predicate, my first implementation pulled in the luapatt library as an additional dependency. Unfortunately, applying syntax highlighting with this ended up being pretty slow.

py-tree-sitter is implemented in C, and for the most part, execution stays there. All of the built-in predicates and directives are part of that C implementation. When it encounters a custom predicate (implemented as a Python callable), it uses PyObject_CallFunction() to transfer execution over into the Python code. Each time that boundary is crossed it adds overhead. Once we’re in Python-land, the pure-Python implementation of luapatt is also not super fast.

The highlighting queries use pattern matching a lot. While there’s some optimization that can be done on how the queries themselves are written (using the structure of the parse tree to reduce the number of pattern matches that get run), every bit of overhead on this path adds up fast. Ideally, we’d want to stay inside C the entire time instead of needing to cross that C/Python boundary.

Translating at vendor time

As I discussed in Part 2 of this series, we vendor these external queries into our own source tree. We’re already doing some processing during this vendor step in order to flatten inheritance so that each language ends up in its own self-contained file. If we can translate the Lua pattern into an equivalent Python regex, we can replace #lua-match? with #match? in the queries themselves. The implementation of #match? in py-tree-sitter calls to re.search, which is itself implemented in C. Because of the details of how CPython is implemented, we never end up crossing that C/Python boundary.

The converter loop

To convert a pattern to a regex, we look through it one character at a time. In the body of the loop, we look at the current character and make a decision about what we’re looking at:

1. A % escape. This can indicate either a built-in character class or an escaped special character.
2. A [...] character class. When we encounter the opening [, we’ll scan through to find the closing one, and then convert everything inside.
3. A - lazy quantifier.
4. Anchors and other quantifiers (^, $, *, +, or ?). These are thankfully the same between patterns and regexes.
5. Characters that require escaping in regex but not in patterns ({, }, |, [, ], and \\).
6. Anything else.

Starting with a translation table

When we see that % character, we’ll peek ahead one character and then start with a translation table. This allows us to swap in regex equivalents for Lua’s built-in character classes, as well as convert the escaped %% literal to a bare % character (since Python doesn’t need that to be escaped).

LUA_TO_PYTHON_CLASSES: Mapping[str, str] = {
    '%%': '%',
    '%A': '[^A-Za-z]',
    '%a': '[A-Za-z]',
    '%c': r'[\x00-\x1F\x7F]',
    '%C': r'[^\x00-\x1F\x7F]',
    '%d': r'\d',
    '%D': r'\D',
    '%L': '[^a-z]',
    '%l': '[a-z]',
    '%p': r'[!"#$%&\'()*+,\-./:;<=>?@[\\\]^_`{|}~]',
    '%P': r'[^!"#$%&\'()*+,\-./:;<=>?@[\\\]^_`{|}~]',
    '%s': r'\s',
    '%S': r'\S',
    '%U': '[^A-Z]',
    '%u': '[A-Z]',
    '%w': r'\w',
    '%W': r'\W',
    '%X': '[^A-Fa-f0-9]',
    '%x': '[A-Fa-f0-9]',
    '%Z': r'[^\x00]',
    '%z': r'\x00',
}

Escaping and un-escaping

If the % was an escape character, we check to see if it was escaping something that Python also needs escaped, and convert it to a \ if so. We can’t just assume that anything that was escaped in Lua should be escaped in Python, because a surprising number of the queries used %-escapes for characters that did not need it. If we blindly converted %n to \n, we’d be changing the meaning of the string in a fundamental way!

Bracketed character classes

In addition to the built-ins, Lua has [...] character classes, just like regex. We pull the contents from within the brackets and convert them using the same translation table and escaping rules. There are a couple caveats:

• We need to be careful when finding the closing bracket. Lua has a rule that a class always holds at least one item. This means that []] is a class containing ], and [^]] is a class containing anything except ]. An escaped %] also does not close the class.
• Some of the things in our translation table use bracketed character classes for the regex. Python regexes don’t let you nest brackets. A Lua pattern like [%a_] can’t be naively translated to [[A-Za-z]_]. When we’re inside a class, we strip outer brackets from the translated version so we can merge it together into [A-Za-z_].
• Some of Lua’s classes indicate opposites, like %A, which matches anything that’s not a letter. There’s no way to merge these with other characters, so if we encounter this, we error out.

The non-greedy quantifier

Python’s * qualifier is greedy, continuing to match the previous group until it hits something that doesn’t. Lua’s - is similar, except it matches as little as possible. It also only becomes a qualifier if the thing that preceeded it is something that’s able to repeat. So in a-$, the - is a quantifier which causes this to match “zero or more ‘a’ characters up until the end of the string.” In contrast, in (-, the ( is denoting the start of a capture group rather than a repeatable item, and so the - here refers specifically to a dash literal.

When we see a -, we make a choice: if the preceeding character was referring to a repeatable item. If it is, we convert to *?. If not, we treat it as a literal.

Dots and newlines.

Lua’s . matches any character, including a newline. In Python regexes, . skips newlines unless the string is matched with re.DOTALL. Fortunately, Python allows us to notate this in the pattern itself: if we encounter a ., we prepend (?s) to the pattern, so a.-b gets translated to (?s)a.*?b.

Handling double-escaping.

The converted regex gets written back into the query file as a quoted string. Query files use backslashes for escapes, so every backslash in the regex has to be doubled before we write it out.

What we can’t support

Lua has two pattern features that have no regex equivalent:

• %b matches balanced pairs. So %b() can handle parenthesized expressions with nesting.
• %f[set] is a “frontier” pattern. It matches the spot where one kind of character changes to another.

Python’s re implementation can’t do either of these. We’ll error out when encountering one, skipping these. In practice, the query files we’re dealing with don’t use either of these except in a couple very obscure languages. I’ll admit I was pretty worried about the balanced parentheses one, since we’re dealing with code, but thankfully that’s handled in the tree-sitter parse phase rather than in the query phase.

Coming up next: how we actually rewrite Tree Sitter query files with the translated patterns.