David Trowbridge
Writing

Tree Sitter in Review Board: Applying Highlighting

Part three of a series on integrating Tree Sitter into Review Board: how we actually apply syntax highlighting to code.

Sep 9, 202619 min
treesitterreviewboardsyntax-highlightingdiffs

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

Handling file content

Review Board primarily operates on files in a line-by-line basis. We split the original and modified versions into lists of lines, and then run our diff algorithm to find out which lines were added, which were removed, which were changed, etc.

Tree Sitter works a little differently. When Tree Sitter parses a file, it operates on a stream of bytes. Running queries against the parsed tree gives us a set of matching nodes. Each node in the tree has a start and end position, which contain a row (0-indexed line number) and column (0-indexed position within that line). Because Tree Sitter is operating entirely on a stream of bytes, that column number represents the number of bytes offset within the line, not the number of characters.

The distinction between characters and bytes is the bane of software developers everywhere.

To represent text, computers have to map each character to a number. The old ASCII encoding (prominently featured in The Martian) encoded every letter of the English alphabet, upper- and lower-case, a few symbols, as well as a bunch of non-printable “control characters” like NEW LINE and BELL within 7 bits of space. If all you have to use is 26 letters that’s fine, but we live in a global society, and even if you’re just in an English-speaking country, a lot of names include accents or other diacritics (my own son’s name has broken several different systems throughout his school with an “á” character).

Modern software, when it gets it right, knows that any string is not just a series of bytes, but a series of bytes with an associated encoding. ASCII is one such encoding, but there are a bunch out there. These days, except in rare circumstances, software deals with Unicode. The core idea of the Unicode standard is the definitions of code points. Each code point is a number (roughly between 1 and 221) which represents a character or piece of a character.

That means that there’s a unique number given for a simple English “a”, a Hebrew “א”, a Hangul “ㅑ”, and even historical characters like Egyptian hieroglyphs. Code points have also been assigned to represent emoji, so Oxford 2015 Word of the Year “Face with Tears of Joy” (😂) is represented internally on a computer as the number 128514, more commonly written U+1F602.

There are many ways of turning that string of code points (numbers) into a stream of bytes. Code points are numbers up to 221, which fits into 3 bytes. If we just write out the code point directly using 4 byte chunks (since counting by 3s is awkward on a computer), it’s an encoding called UTF-32. Unfortunately that means if you have a document that only uses the 26 English letters with no special characters, the UTF-32 encoding takes 4 times the amount of storage space and internet bandwidth than the equivalent ASCII encoding.

These days most people use an encoding called UTF-8. In UTF-8, the first 128 characters are the same as ASCII, giving it built-in compatibility. If the first bit of that first byte is a 1 instead of a 0, that means that the character is actually a multi-byte character. Anything that doesn’t fit into ASCII gets stretched out into at least 2 bytes, and some characters can use 3 or 4. UTF-8 was invented by legendary programmers Ken Thompson (inventor of the UNIX operating system) and Rob Pike (who built the first windowing system for Unix, and more recently the Go programming language). UTF-8 is super clever in a bunch of ways, but because an individual character is not a fixed width, it’s also annoying to work with.

When Review Board needs to apply syntax highlighting, we have both representations:

How content and lines differ The two parameters written as annotated Python declarations: lines is a list of separate strings with the newlines removed, content is a single flat byte string whose newlines are part of the data, with spans marking which run of content becomes which entry. lines : list[str] = [ 's = "café" # done' , 'print(s)' , ] content : bytes = b' s = "caf \xc3\xa9 " # done \n print(s) \n ' lines[0] lines[1] one entry per line of the file no newline characters all entries indexed from column 0 29 bytes in one flat sequence newlines are part of the data always ends with a newline character

Because we want to be good citizens, we need to be able to handle more than just ASCII. In this example, the é character takes up a single position in the str representation, but two positions in the bytes.

Byte columns and character columns on one line A single line of Python with each character in its own cell, and two index rows beneath it: character offsets, and byte offsets. The two rows agree until the two-byte é, after which every byte offset sits one ahead of its character offset. CHAR BYTE s 0 0 · 1 1 = 2 2 · 3 3 " 4 4 c 5 5 a 6 6 f 7 7 é 8 8 " 9 10 · 10 11 · 11 12 # 12 13 · 13 14 d 14 15 o 15 16 n 16 17 e 17 18 é is two bytes, so every BYTE column from here on sits one ahead of its CHAR column.

The big lesson here is this: throughout the entire process, we can’t just assume that an index is an index. Any time we have a number that’s referring to a position somewhere in the text, we need to know: is this index a character offset or a byte offset?

The processing pipeline

Applying syntax highlighting is effectively a data processing pipeline. We want to start with our file content, and end with HTML that we can send to the client. This means we need to not only add info for what color or style we want to apply to any given slice of the text, but we also need to escape some characters (e.g. a < less-than operator in a C file shouldn’t be misinterpreted by the browser as opening an HTML tag, so we need to replace it with &lt;).

The six steps of the highlight pipeline A single rail running from content through six numbered steps -- find captures, flatten and order, split by line, sort per line, convert to events, apply and encode -- and ending in the returned HTML. content HTML 1 find captures 2 flatten + order 3 split by line 4 sort per line 5 convert to events 6 apply + encode

Each step does some processing and then hands the next a list of tuples. Note that two of these carry columns, and they do not mean the same thing:

python
#: (capture name, start row, start column, end row, end column).
#: Columns are BYTE offsets, exactly as Tree Sitter reports them.
HighlightCapture = tuple[str, int, int, int, int]

#: (capture name, start column, end column), within a single line.
#: Columns are CHARACTER offsets.
HighlightNode = tuple[str, int, int]

#: (HTML tag, character offset to insert it at).
HighlightEvent = tuple[str, int]

#: Indexes into the tuples above, for the sorts in steps 4 and 5.
START_COL, END_COL = 1, 2
EVENT_POSITION = 1

Step 1: Find the highlight captures

When we run Tree Sitter queries (discussed in Part 2) against a parsed Tree, we get a set of captures.

python
highlights_scm = get_queries(language_name, 'highlights.scm')

ts_language = tree_sitter_language_pack.get_language(language_name)
query = tree_sitter.Query(ts_language, highlights_scm)
cursor = tree_sitter.QueryCursor(query)
captures: dict[str, list[tree_sitter.Node]] = cursor.captures(
    tree.root_node, predicate_handler)

The returned data from Tree Sitter is a mapping where the keys are the capture names, and the values are a list of nodes from the tree that matched.

{
    'keyword': [Node, Node, ...],
    'operator': [Node, ...],
    ...
}

Step 2: Convert the captures dict into an ordered sequence of captures

The captures we get from Tree Sitter are organized by their capture name. If we were looking for a specific thing that would be great, but this is kind of an awkward shape for the general task of applying highlighting. So the first step is to flatten it into a list.

Because we’re pulling in highlights queries from external sources, there are a bunch of highlight captures that we don’t care about. As we process the captures dict, we skip anything from the ignore list. This ignore list starts with an initial set of capture names, but can grow as we process the data and discover capture names from the upstream queries that don’t result in a highlight.

We don’t just have a whitelist because highlight capture names have an hierarchy. Some upstream queries will return specific names like @variable.member or @variable.parameter where our highlighter is just looking for @variable. As we find these, we’ll first check for a direct match in our known highlight classes, and if that doesn’t exist, we’ll split on the ”.” character and look for the more generic term. If nothing is found, we’ll then extend the ignored capture names set for the next time a file of that type is processed.

When we process this, we do it sorted with the shortest capture names first. More on this later.

python
names = set(captures.keys()) - HIGHLIGHT_IGNORE

captures_list: list[HighlightCapture] = []

for name in sorted(names, key=lambda name: (len(name), name)):
    nodes = captures[name]

    for node in nodes:
        captures_list.append((
            name,
            node.start_point.row,
            node.start_point.column,
            node.end_point.row,
            node.end_point.column,
        ))

We’ve now converted our captures dict into a flat list of tuples storing the capture name and the start/end positions of the affected node.

Step 3: Split captures by line

Because we’re going to apply highlighting line by line, we now need to to organize the captures by line. There are a few things we need to watch out for:

  • When Tree Sitter encounters a file that has syntax errors, it will try its best to recover and deliver a parse tree anyway. Sometimes this is done by adding error-recovery nodes which exist in a virtual space after the actual last line of the file.
  • The bytes-encoded version of the file has a newline character at the end, which is sometimes consumed by a capture range.
  • Some captures can span multiple lines (for example, a Python docstring will have a single @string capture).

We’ll scan through now to split our single list out into a list per-line,

python
nodes_by_line: list[list[HighlightNode]] = [[] for _ in lines]

for name, start_row, start_col, end_row, end_col in captures_list:
    if start_row >= len(lines):
        # Error-recovery nodes can start past the last line.
        continue

    if end_row >= len(lines):
        # A node that consumed the file's trailing newline ends at the start
        # of a row past the last line. Clamp it to the end of that line.
        end_row = len(lines) - 1
        end_col = len(lines[end_row].encode())

    # Deliberately new names: these are character offsets, not byte offsets.
    start = _byte_to_char_pos(lines[start_row], start_col)
    end = _byte_to_char_pos(lines[end_row], end_col)

    if start_row == end_row:
        nodes_by_line[start_row].append((name, start, end))
    else:
        # A capture can span lines -- a docstring is one string node -- so
        # split it into one node per line.
        nodes_by_line[start_row].append(
            (name, start, len(lines[start_row])))

        for row in range(start_row + 1, end_row):
            nodes_by_line[row].append((name, 0, len(lines[row])))

        nodes_by_line[end_row].append((name, 0, end))

Step 4: Sort the captures within each line

We now need to make sure the captures are sorted so that we can apply them in order. We sort first by the start column, and second with the longest ranges first (so if we have two captures that begin on the same column, the “outer” one will be listed first).

Because of the sort we applied in step 1, if two highlight ranges exactly overlap, the shorter capture name will come first (this works because Python’s sorted is stable).

python
for i, line_nodes in enumerate(nodes_by_line):
    nodes_by_line[i] = sorted(
        line_nodes,
        key=lambda node: (node[START_COL], node[START_COL] - node[END_COL]))

Step 5: Convert highlight nodes to events

We now split each highlight into two “events”, which correspond to the HTML tags we want to inject. Each of these has an HTML tag (either <span class="..."> or </span>) and a position.

Highlight queries might add duplicate names for the same range (e.g @string.documentation and @string). Review Board doesn’t explicitly highlight @string.documentation, so this gets turned into @string. As we create the events (and discover this capture name mapping), we filter to make sure that we’re not creating HTML that looks like <span class="ts-string"><span class="ts-string">...</span></span>.

python
events_by_line: list[list[HighlightEvent]] = []

for nodes in nodes_by_line:
    events: list[HighlightEvent] = []
    added_spans: set[tuple[str, int, int]] = set()

    for node_name, start, end in nodes:
        if span_tag := _find_matching_highlight_tag(node_name):
            span_key = (span_tag, start, end)

            if span_key not in added_spans:
                events.append((span_tag, start))
                events.append(('</span>', end))
                added_spans.add(span_key)

    events_by_line.append(
        sorted(events, key=lambda event: event[EVENT_POSITION]))

Each event in events_by_line is now sorted by its position within the line. When two events have the same position, the prior sort order that was determined by the sorts in steps 1 and 3 still prevails.

Step 6: Apply events to each line and encode

Now the final step: take each line of the file and insert the HTML tags at their desired locations. While we do this, we also encode any HTML-sensitive characters.

python
html_escape_chars = {
    ord('&'): '&amp;',
    ord('<'): '&lt;',
    ord('>'): '&gt;',
    ord("'"): '&#39;',
    ord('"'): '&quot;',
}
highlighted_lines = [''] * len(lines)

for i, (line, events) in enumerate(zip(lines, events_by_line)):
    if not events:
        # Simple case of a line with no events
        highlighted_lines[i] = line.translate(html_escape_chars)
        continue

    parts: list[str] = []
    last_pos = 0

    for tag, pos in events:
        # Add any escaped text between the previous event and this one
        if pos > last_pos:
            parts.append(line[last_pos:pos].translate(html_escape_chars))
            last_pos = pos

        parts.append(tag)

    # Add any remaining text
    parts.append(line[last_pos:].translate(html_escape_chars))

    highlighted_lines[i] = ''.join(parts)

Handling injections

Injections are one of the coolest features of Tree Sitter. They let us highlight languages-within-languages (for example, JavaScript code inside of <script> tags in an HTML file).

We handle injections by doing a parallel scan. We do the highlights queries for the entire file, and then we do a separate injections query. For each injection we find, we can ask Tree Sitter to give us a parse tree for just that section of the file with a different language. Even better: the positions in the parse tree that it gives us are the node positions in the entire file rather than just the injected content.

So for each injected language, we construct a new parser, set included_ranges, and run a parse. We then run highlights on that smaller parse tree, giving us another set of captures. We can then just chain all of the separate captures together to pass into the highlighting pipeline. Once we have captures, the pipeline doesn’t care what language they’re coming from.

How an injected language is highlighted A fork-and-merge diagram: one HTML parse feeds both a highlights query and an injections query; the injections query yields a byte range that is re-parsed as JavaScript with included_ranges, and both capture streams merge into a single list. MAIN PASS INJECTION SCAN PARSE tree get_parser("html").parse(content) QUERY highlights.scm html · 4 tag captures QUERY injections.scm html MATCH injection.content bytes[18,27) · lang = javascript RE-PARSE parser.included_ranges javascript parser, same buffer QUERY highlights.scm javascript · 4 captures ('keyword', 1, 8, 1, 11) MERGE itertools.chain 8 captures, one coordinate space LEGEND query pass captured range re-parse with included_ranges

What’s with all the sorting?

In several of the steps of the pipeline, we’re carefully managing the sort order of the highlighting. Some of this is obvious: we need to process things in the order that the appear in the file, top to bottom, left to right. The less obvious one is the sort by the length of the capture name that happened all the way back in step 2.

Tree Sitter queries don’t assign a unique name per symbol. Each query runs in parallel, so we may get the same range marked for highlighting with multiple different names.

Here’s a very simple concrete example:

python
print(None)

The print token matches three separate highlight queries:

  • @variable
  • @function.call
  • @function.builtin

In every case I investigated from the queries, longer names indicate more specificity (especially when we get matches like @string and @string.documentation). We want to make sure that if we have CSS that highlights function.builtin differently from function.call, the more-specific name wins. That sort order we established at the very beginning of the pipeline ensures that in the resulting HTML, when we have multiple highlight classes that apply to the same range, the inner-most element is the most specific.

Why capture sort order controls span nesting Three nested boxes labelled with the span tags they emit: ts-variable outermost, then ts-function-call, then ts-function-builtin innermost around the token print. <span class="ts-variable"> <span class="ts-function-call"> <span class="ts-function-builtin"> print