Semantic Tokens: Relative Encoding and Delta Updates

Grammar-based highlighting assigns colours by lexical shape: a pattern matches an identifier, and the colour comes from the pattern that matched. That is fast and language-agnostic, and it cannot distinguish a local variable from a type that happens to be spelled the same way, nor tell a deprecated function from its replacement. A language server knows both facts from its analysis, so the protocol carries a second, semantic layer of token spans. The interesting part of that layer is not the token types, which are painted by the client’s theme, but the encoding: a flat array of 32-bit integers in which each token is expressed relative to the one before it, so that a small edit changes a small part of the array.

From a token stream to a flat integer array

The result of a token request is a single array of unsigned integers, five per token, consumed in order: the line delta from the previous token, the character delta within that line, the token’s length, an index into the server’s token type list, and a bitmask of modifiers. A client walks the array from the start, accumulating the line and character deltas to recover absolute positions, and paints each span with the theme entry that corresponds to the type index.

The choice of integers rather than objects is a size decision, and the sizes are easy to state. Twenty bytes of binary per token become a JSON array of numbers, where each number can occupy up to ten characters plus a separator, so a file with tens of thousands of tokens is a payload in the hundreds of kilobytes. The protocol describes the array form as the memory-friendly one, and suggests that implementations that need to ship it over a transport with different framing could pack the integers directly rather than as decimal text.

Two normative details constrain the encoding. A token type index must stay below 65536, so a legend is bounded, and a token’s length and its character deltas are expressed in the position encoding negotiated at initialization — the same units that every other range in the session uses, with the same consequences when they disagree, as described in Byte Offsets, UTF-16 Code Units, and Editor Positions. A server that assumes bytes in a UTF-16 session produces tokens that start correctly and end early, drifting progressively further from the text in proportion to the non-ASCII content before them.

def encode(tokens):                       # tokens: (line, col, len, type, mods)
    out, prev_line, prev_col = [], 0, 0
    for line, col, length, ttype, mods in tokens:
        dline = line - prev_line
        dcol = col - prev_col if dline == 0 else col   # absolute after a line break
        out += [dline, dcol, length, ttype, mods]
        prev_line, prev_col = line, col
    return out

The second line of that snippet is the rule people get wrong: the character delta is relative to the previous token’s start only when both are on the same line. When the line changes, the delta is the token’s absolute start character, because there is no meaningful relationship between a column in one line and a column in another.

Why tokens are encoded relative to their predecessor

Absolute positions would be simpler to consume. The relative form exists because of what edits do to the array rather than what they do to any single token. Most tokens in a file sit at the same offset relative to their neighbours before and after an edit: inserting a character inside a line shifts the absolute columns of every token on that line, and shifts the absolute lines of every token after it, but leaves the deltas between adjacent tokens unchanged except around the insertion point. In the array representation, that edit touches a handful of positions rather than every position after it.

The property is the same one that makes incremental synchronization worthwhile at the character level, and it is what makes a diff of the number array small enough to be worth computing. The saves are not uniform — inserting a line shifts every subsequent token’s absolute line, which the delta form absorbs entirely; inserting a character at the start of a line shifts the deltas of the tokens on that line, which turn into a contiguous run of changed integers — but in both cases the changed region is local.

Delta edits behave like text edits on the array

A full token request returns the array together with an optional result identifier. The delta request sends that identifier back and receives either a fresh full array with a new identifier — used when the changes are extensive enough that a diff is not worth sending — or a list of edits to apply to the array the client already holds.

Each edit names a start offset in the array, a count of integers to delete, and the integers to insert. The semantics are deliberately the same as text edits on a document, with one addition that is easy to miss: all edits in one delta are expressed against the same previous state of the array, not against the state produced by the preceding edit. They are also not required to be sorted, so an implementation applies them from the back of the array forward, or sorts them first, exactly as the specification suggests.

def apply_delta(data: list[int], edits: list[dict]) -> list[int]:
    # All edits index into the same prior state: apply back to front.
    for e in sorted(edits, key=lambda e: e["start"], reverse=True):
        start, count = e["start"], e["deleteCount"]
        data[start:start + count] = e.get("data", [])
    return data

Applying edits in the order received, or recomputing offsets after each one, corrupts the array in a way that survives every subsequent delta, since the next delta assumes the previous state was correct. The recovery is the same as for a corrupted document mirror: request a full set and reset the identifier chain.

The identifier chain also defines what a client must retain. A client that stores only painted spans and discards the integer array cannot apply a delta, because the deltas index the array rather than the document. Implementations therefore keep the array per document, or a compact equivalent such as a decoded token list plus the mapping needed to re-encode it, and treat the result identifier as the ticket that proves which state they hold.

Legends, modifiers, and capability limits

The numbers are meaningless without the legend, which the server declares in its capabilities before any request: an ordered list of token type names and an ordered list of modifier names. Type indices index the first list; modifiers are bit flags, so a modifier value of 3 means bits 0 and 1 are set and corresponds to the first two entries of the modifier list. Since the modifier field is a 32-bit value, the number of usable modifiers is bounded by its width, and a server that declares more can never reference them.

The legend is fixed for the session, so renaming a type or reordering the list mid-session invalidates every index the client has cached. Client support is also not uniform and is declared up front: whether overlapping tokens are understood, whether a token may span several lines, and whether the client uses the tokens to augment an existing grammar-based colouring or to replace it. The last of these changes what the server should send. A client that replaces grammar colouring needs a token for essentially every span, including punctuation and operators, because anything omitted is left uncoloured; a client that augments only needs the semantically interesting spans and keeps the grammar’s colouring underneath.

Overlap deserves its own note because the failure is silent. Where a client does not support overlap, a server that sends a token nested inside another — an identifier inside a documentation comment, say — produces a client that applies them in array order and leaves the result dependent on ordering rather than intent. Multiline tokens behave similarly: a client without support treats a token as ending at the end of its line, so a server that emits a length crossing a newline gets a highlight that stops early rather than an error.

Layering over grammar-based highlighting

The two layers answer different questions and are ordered rather than merged. Grammar-based rules, driven by regular-expression patterns with a stack of begin/end states, produce a nearly complete colouring at negligible cost, and they survive broken syntax because they are lexical. Semantic tokens refine that colouring for the spans the analysis understands, and they invert priority: where a semantic token exists, it wins.

This is why semantic token traffic is often restricted to the visible range rather than the whole document. A full request for a large file after every keystroke costs a diff over an array of tens of thousands of integers plus the encoding work to produce it, while the visible region is a few hundred lines. Range requests exist for exactly this, and a server that supports them can answer in proportion to what is on screen. The trade is that scrolling triggers requests, so a client either requests ahead of the viewport or accepts a frame of grammar-only colouring at the edge.

The layering also explains why the token layer is the least dangerous place for a server to be wrong. A misplaced token colours the wrong word until the next report; unlike a text edit, it cannot modify the document.

Corruption modes and how to recover

Four failure modes account for nearly all broken highlighting in practice. A legend mismatch — a type index beyond the end of the declared list, typically after the server adds a type in a version the client cached — leaves a span unmapped, and the defensible client behaviour is to skip that token rather than to guess an index. A delta applied against an out-of-sync array desynchronises every later delta, because the identifiers are only compared for equality, not validated against content. A character unit mismatch, in either the deltas or the lengths, drifts the tokens away from the text as non-ASCII characters accumulate earlier in a line. And a stale delta computed from a document version the client has already replaced produces spans for code that moved.

The last case has a protocol-level guard worth knowing about: the identifier returned with a result is the server’s proof of which state it sent, so a client that keeps only the latest identifier and always sends it back will, in the worst case, be told to compute a full set rather than receive an unusable delta. Servers that accept an identifier they did not issue, and compute a delta against a guessed state, convert a detectable mismatch into silent corruption. Where the client and the server disagree irrecoverably, the reset is the same as elsewhere in the session: discard the cached array, ask for a full set, and rebuild from the text that the synchronization channel, described in Incremental Document Synchronization Between Client and Server, has kept in step.