Completion Filtering, Ranking, and Lazy Item Resolution

Completion is the feature that most shapes a language server’s architecture, because it is asked at the highest rate and under the tightest deadline. The editor requests a list when the user types a character that the server nominated as a trigger, and then the user keeps typing, which changes the query string that the list was computed for. A round trip per keystroke is not affordable at typical typing speed, so the protocol is arranged so that the client can answer most subsequent keystrokes locally, and the server’s job is to predict what will be needed and to make the list cheap enough to filter in the client’s typing thread.

Why the client filters what the server returned

The request asks for items at a position, with a context describing what triggered it, whether the request was retriggered, and any already-selected item. The reply is either a plain array or a list object that also states whether the list is incomplete. A plain array is by definition complete; a list marked incomplete tells the client that the set is a subset and that filtering it locally would hide items the server could have produced, which forces the client to re-query on the next keystroke.

That flag is the pivot of the whole design. With a complete list, the client applies its own matching to the items it holds as the user types more characters, so the visible set narrows without a single message. This is why the protocol documentation directs clients to filter locally for speed, and why servers that set the incomplete flag pay for correctness in latency: every keystroke becomes a request, each potentially cancelled by the next. The flag exists for the cases where the returned set genuinely depends on the query prefix — when the server ranks by something other than the typed text, or when the candidate set is too large to enumerate.

The client’s local filtering also means the item set must be self-describing. A filter that only sees the label cannot reproduce the server’s intent, which is why items carry strings dedicated to matching and sorting rather than reusing the text that gets inserted.

Scoring a fuzzy match

Matching in editors is almost never equality. Typing gfu is expected to find get_file_uri, so the filter is a subsequence test with a score, not a prefix comparison. The cheapest correct form is a two-pointer scan that walks the candidate string looking for the query characters in order; that answers reachability in linear time but gives every match the same score unless it also accumulates a heuristic.

The scoring heuristics that make results feel ordered are consistent across implementations. A match that is a prefix of the candidate outranks a match buried in the middle; consecutive matched characters score higher than the same characters spread apart, which pushes gfu toward gfu and away from gather_from_url when both are candidates; a character matched immediately after a word boundary (an underscore, a capital in a camelCase identifier, a path separator) scores higher than one matched mid-word, which is what makes acronym queries work. Gap penalties subtract for skipped characters, and the final score is compared across candidates.

BOUNDARY = {"_", "-", "/", "."}

def score(query: str, cand: str) -> int:
    """Subsequence score: consecutive and boundary matches win."""
    qi, total, run = 0, 0, 0
    q = query.casefold()
    for i, ch in enumerate(cand.casefold()):
        if qi < len(q) and ch == q[qi]:
            total += 2 + run                    # consecutive bonus grows
            prev = cand[i - 1] if i else "/"
            if prev in BOUNDARY or (prev.islower() and cand[i].isupper()):
                total += 3                      # word-boundary bonus
            run += 1
            qi += 1
        else:
            run = 0
            total -= 1                          # gap penalty
    return total if qi == len(q) else -1        # -1 means no subsequence match

Two properties of this scoring are worth stating explicitly. It is not edit distance: a subsequence match ignores insertions in the candidate entirely, which is the right behaviour for identifiers and the wrong behaviour for prose, and the classical edit-distance formulation counts substitutions and transpositions that this metric deliberately does not consider. And case-insensitive matching must use Unicode case folding rather than a naive lowercasing, because the two disagree for a small set of characters, and the disagreement changes what matches in languages whose identifiers are not ASCII.

The three strings that decide which item appears

An item carries a label for display, and two optional strings whose purpose is entirely mechanical. The filter text is what the client matches the typed prefix against, and the text to insert is what ends up in the document. Where the filter text is absent the label is used, so a label that includes parameter lists or type annotations makes those characters matchable, and a query that hits them selects an item that appears unrelated to what was typed. The sort text is what the client orders by, as a string comparison; where it is absent the label is used.

The sort text is the server’s ranking channel, and because it is compared as a string rather than parsed, servers encode priority by prefixing with digits or letters, which is why completion lists often arrive with sort texts like 01_ or 0001. The consequence is that a server which wants a category to appear first must assign every item in every category a sort text, not merely the items it wants promoted: an item with no sort text sorts by its label, and label ordering interleaves with whatever scheme the server applied.

The inserted text comes in two flavours, distinguished by a format field. Plain text is inserted literally. Snippets may contain tab stops and placeholders, which the client must interpret, expand, and select in sequence — but only if the client advertised support for snippet syntax during the handshake, since a client without that capability would insert the placeholder syntax characters into the file. Snippet support is a client capability rather than a server one, and a server that ignores it produces function calls with literal ${1:arg} text in them on those clients.

A third mechanism for the same problem is the text edit form, in which the item states the range it replaces rather than relying on the client’s notion of the current word. The protocol describes both modes and notes that they differ in who computes the replaced range: with an insert text, the client decides using a default word pattern, which fails for identifiers containing characters the default pattern does not treat as word characters, and for expressions where the completion replaces more than one token. The text edit form avoids the guess at the cost of computing a range that must remain valid until the item is committed, which is the same staleness problem that affects every range in the protocol, including the change ranges exchanged in Incremental Document Synchronization Between Client and Server.

Resolving an item after selection

Building full documentation, type signatures, and resolved default values for several hundred candidates is wasted work, because exactly one candidate is chosen and only the chosen one’s details are displayed. The resolve mechanism splits the item in two: the response carries a lightweight item plus an opaque data payload, and when the client selects an item it sends the item back, data included, in a request whose reply is the enriched item.

Which properties may be filled in during resolve is not left to convention. The client advertises, through a capability, the set of properties it supports resolving, and every other property (the specification names sort text, filter text, insert text, and the text edit as the usual core set) must be present in the original response and must not change in the resolved one. The split exists so that the client can render, filter, and commit an item using only what it already has, and so that a resolve call that is cancelled or fails leaves the item usable. A server that returns an item without a filter text and then supplies one during resolve breaks filtering for that item in clients that filter locally, because the payload arrives after the list has been narrowed.

The data payload also ties completion to the rest of the session state. It is the server’s own encoding of the context that produced the item, and it is opaque to the client, which means it must survive the client’s storage and the round trip unchanged — including while the document changes underneath it. The practical consequence is that a resolve request has to be treated as possibly referring to an older document state; the item’s result may be right for the analysis that produced it and wrong for the current text, and no field in the resolve request carries the document version.

Triggering, re-querying, and cancellation

The server declares which characters cause the client to request completion; a period in a qualified name or a colon in a mapping language are typical. The client also requests completion explicitly, and may do so again while a request is in flight, which produces a storm of overlapping requests during fast typing. Since responses can arrive out of order, a client that applies whichever reply lands last will display items for an older prefix.

The mechanism that prevents this is the same cancellation path described in Cancellation, Progress, and Partial Results in the Language Server Protocol: the client cancels the outstanding request, and the server either honours the cancellation or answers with a cancellation error, which the client discards silently rather than reporting. Servers are also permitted to answer with a content-modified error when the document changed while the request was being computed, which is the honest alternative to returning a list that no longer applies.

Latency is the constraint that shapes the rest. A list of a thousand items with modest metadata runs to tens of kilobytes of JSON, and a server that computes all of them on the client’s typing thread adds exactly the delay the local filtering exists to avoid. Servers therefore bound the candidate count, defer the expensive parts to resolve, and use the shared-defaults mechanism in newer protocol revisions to avoid repeating identical fields — a range, a commit-character list, or an insert-text format that every item in the list shares.

When the list is wrong

The failure modes concentrate in a few places. A filter text that does not contain the typed characters makes an item unreachable while it is still visible in a longer list, which reads as an editor that ignores typing. An incomplete flag set to true everywhere removes local filtering and makes completion unusable in a slow connection. Snippet syntax sent to a client that did not advertise support inserts placeholder text into source files. And resolve responses that change core properties turn an item the user selected into a different insertion than the one that was shown — the clearest case of a rule in this protocol that exists to keep the client’s view and the server’s belief the same thing.