← Back
Home › Systems › CI/CD and developer tooling

language-server

Provides editor features such as completion, go to definition, rename and diagnostics for a programming language over one protocol, serving any editor.

rust-analyzer

Open the language-server pagelanguage-server Code symbol indexingcompilers: Extract definitions and references per file, give each symbol a stable string id, and store symbol to occurrences, re-indexing only files whose content hash changed.›Incremental parsingcompilers: Reparse only the region an edit damaged and splice the new subtrees into the old tree, sharing everything else; O(edit) instead of O(file).›Name resolutioncompilers: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.›Text position encodingcompilers: Store byte offsets, convert to (line, column) on demand with a line-start table and binary search, and count columns in the unit the peer negotiated.›Type inference hindley milnercompilers: Algorithm W and J: unification-based inference with let-polymorphism and generalizationString interningdata-structures: Store each distinct string once and refer to it by idRopegraphics: A balanced tree of small string chunks with cached byte and newline counts, so seek, insert, delete and snapshot cost O(log n) instead of O(n).›File system watchinghardware-os: Treat OS change notices as hints, debounce them, and rescan and diff a snapshot whenever notices overflow or may be lost.›Json rpcnetworking: JSON-RPC 2.0 requests, notifications and batchingLength-prefix framingnetworking: Split a byte stream (TCP, TLS, pipes) into messages by writing each message's length before it; O(1) boundary detection with no escaping.›Fuzzy finder scoringsearch-sort: Subsequence matching with gap/position scoring (fzf-style)Arena allocatorsystems: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.›Incremental computationsystems: Dependency graph of derived values recomputed only when inputs change (reactive cells, spreadsheets)Language server protocolcompilers: One JSON-RPC conversation over a pipe lets any editor drive any language's analysis server; the cost is keeping a live, edited document in sync and answering before it changes.›Protobuf wire formatnetworking: Protocol Buffers wire format: tags, varints, length-delimited fields and schema evolutionInverted indexstorage: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›Lossless syntax treescompilers: Concrete syntax trees with trivia, green/red node split (Roslyn, rowan) for tools that rewrite codeParser error recoverycompilers: Recover from syntax errors via synchronization tokens and error nodes to keep a full treeRecursive-descent parsingcompilers: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.›Unificationcompilers: First-order unification with union-find and occurs check; basis of type inference and logic programmingUnion-findgraphs: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.›Hash consingdata-structures: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximalSwiss tabledata-structures: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.›Topological sortgraphs: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.›Bit packing and PFORcompression: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.›Delta encodingcompression: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›Varint (LEB128)compression: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.›BM25 rankingsearch-sort: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.›Sorted-list intersectionsearch-sort: Intersect sorted id lists by merging, galloping from the short list into the long one, and skipping whole compressed blocks, shortest list first.›Edit distancesearch-sort: Levenshtein/Damerau distance by DP, bit-parallel Myers variantBFS and DFSgraphs: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›SIMD programminghardware-os: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›Top-k selectionsearch-sort: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.›Unicode text tokenization forsearchsearch-sort: Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.›Sparse matrices (CSR)numerics: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.›d-ary heapdata-structures: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.›Text normalizationmachine-learning: Rewrite messy text into one canonical form for matchers and models, or into spoken words for speech output (and back), keeping a map to the original offsets.›

How it is built

Architecture overview

A language server turns a programming language into editor features (completion, go to definition, rename, diagnostics) behind one protocol, so one server serves every editor. The hard part is not the protocol; it is answering questions about code that is broken half the time (the user is mid-keystroke), while the answer to the previous question is already stale. The design that survives this has four layers. A transport layer frames JSON messages and keeps a model of the open documents. A syntax layer parses every file into a tree that never fails and keeps all text. A semantic layer answers questions (what does this name refer to, what is the type here) lazily and caches the answers in a dependency graph, so an edit invalidates only what it touches. An index layer holds cross-file facts (all symbols, all references) for workspace-wide questions. A scheduler on top decides which work runs now and which is cancelled by the next edit. The rust-analyzer architecture document is the running example; clangd is the contrasting one.

Parts:

  editor ──stdio──► [framing + JSON-RPC] ──► [scheduler / main loop] ──► worker pool
                       ▲                         │ state-changing events        │ read-only requests
   didOpen/didChange ──┘                         ▼                              ▼
                                       ┌─────────────────┐   snapshot   ┌──────────────────┐
  watcher / editor ──file events─────► │ document store  │────────────► │ semantic engine  │
                                       │  (VFS + ropes)  │              │ (memoised graph) │
                                       └───────┬─────────┘              └───────┬──────────┘
                                               │ text → tree                   │ symbols, refs
                                               ▼                               ▼
                                       [syntax: lossless tree]         [index: symbol → locations]

How the parts fit together

Protocol and transport

Language server protocol is JSON-RPC 2.0 (json-rpc, no page yet: requests with ids, notifications without, errors with codes) over a byte stream, each message preceded by headers with a Content-Length (source: LSP 3.17 specification). That is length-prefix framing: the receiver reads the header, then exactly that many bytes, with no escaping and no scan for a delimiter. The choice follows from what travels: JSON bodies contain every byte value including newlines, so a delimiter scheme would need escaping.

Two details of the protocol shape the rest of the server. First, positions are (line, character) pairs, and the unit of "character" is negotiated. UTF-16 code units is the default, and since 3.17 a client can offer UTF-8 or UTF-32 instead via positionEncoding (source: LSP 3.17). A server whose own text is UTF-8 stores byte offsets and converts at the edge: text position encoding describes that method (a line-start table plus binary search, counting columns in the peer's unit). Doing it at the boundary, once, keeps every internal data structure in a single unit. rust-analyzer states the same rule for its layers: only the top crate knows about LSP and JSON, and the ide API is built of plain data types such as offsets and ranges (source: rust-analyzer architecture doc).

Second, requests can be cancelled. A client sends $/cancelRequest; the server must still answer a cancelled request, with an error such as ServerCancelled or ContentModified (codes -32802 and -32801 in 3.17), because every request id has to be answered (source: LSP 3.17). ContentModified is how a server says "the document changed under this answer, ask again". Long operations report through $/progress with a token, and results can stream as partial results.

Document and file store

The server has two sources of truth that disagree: the file on disk and the editor buffer. The protocol makes the editor authoritative for open documents (didOpen, didChange, didClose) and leaves the rest to the disk. A virtual file system sits between them: rust-analyzer's vfs crate hands out an opaque FileId for each path and stores the current contents, so higher layers never see paths and never read the disk (source: rust-analyzer architecture doc). The buffer representation matters when files are large and edits are frequent. A rope, a balanced tree of small chunks with cached lengths, gives O(log n) insert and delete and cheap snapshots, which is why editors favour it; a language server that receives incremental changes (range plus new text) applies them to its copy. Many servers simply store each file as one string and replace it, which is fine for source files of ordinary size; I did not verify which representation rust-analyzer's VFS uses and do not claim one.

For closed files, change detection uses file system watching, treating notifications as hints that may be lost. The protocol allows the client to do the watching: the server registers glob patterns, and the client sends workspace/didChangeWatchedFiles (source: LSP 3.17). rust-analyzer's own vfs-notify crate is described in its source as untested and "quite probably buggy", and by default the server relies on the editor's watching instead (source: rust-analyzer architecture doc). Both choices follow the same rule: do not trust one event channel and rescan when in doubt.

Syntax

Each file gets its own tree, built by a hand-written recursive-descent parser. rust-analyzer's parser emits a flat stream of events that a separate step turns into a tree, and it is designed never to fail: on an unexpected token it records an error and keeps going, so an unfinished foo. still gives a usable tree around the cursor (source: rust-analyzer architecture doc). The tree is lossless (lossless-syntax-trees, no page yet): whitespace and comments are kept as tokens, so the tree can print back exactly the source text and every node has a text range. A rust-analyzer detail worth noting is that the syntax tree crate is value-typed and per-file: it knows nothing about the rest of the project, which makes it trivial to cache and share between threads (same document).

Rebuilding the tree on every keystroke is usually fast enough for ordinary files, but incremental parsing reparses only the damaged region and reuses the other subtrees, O(edit) instead of O(file). tree-sitter takes this approach as a core feature, with the cost of a more complex parser generator and error recovery model than a hand-written parser. Interned identifiers (string-interning, no page yet) turn name comparisons into integer comparisons; rust-analyzer's intern crate does this with shared pointers. An arena allocator suits syntax and semantic tables with a shared lifetime, where one reset frees a whole generation.

Semantic engine

The semantic model answers "what is this name", "what is the type of this expression", "which impl applies". It is computed from the trees and the project structure, which rust-analyzer represents as a CrateGraph: crates with their dependencies, configuration and root files, the one input the server gets from the build system rather than from source (source: rust-analyzer architecture doc). Everything below that graph is derived.

Name resolution binds each use to a declaration, handling scopes, shadowing and imports. Type inference (type-inference-hindley-milner, no page yet; Rust's inference is a related unification-based design, not Algorithm W itself) follows. Both are queries: a function from keys to values that may call other queries. The engine behind this is incremental-computation (no page yet) and the rust-analyzer implementation is the salsa library. Its documented algorithm is red-green: each query result is stamped with the revision at which it last changed; when an input changes, a dependent query is re-examined, its inputs are checked, and if none actually changed its old result is kept ("backdating"), so the recomputation stops where results stop changing (source: salsa docs). Durability levels let inputs that rarely change (library crates) skip checks entirely.

A design trick matters more than any algorithm here: make the stable parts of the semantic model independent of the unstable ones. In rust-analyzer the ItemTree (signatures of items) does not include function bodies, so typing inside a function body does not invalidate item-level queries such as "which names are in scope in this module" (source: rust-analyzer architecture doc). Typing in a body re-runs inference for that body only.

Laziness and incrementality are different strategies, and the choice sets the whole design. The rust-analyzer blog compares three architectures: a map-reduce style that indexes stubs per file and combines (fast for languages where declarations can be found without semantic analysis); a snapshot of headers or a preamble rebuilt when it changes (the clangd and C++ approach, forced by the preprocessor and by headers being parsed in the context of the including file); and query-based on-demand computation (rust-analyzer, where Rust's macros and name resolution make declarations depend on far more than syntax) (source: Three Architectures for a Responsive IDE). The qualitative lesson: the more global the dependency from edit to result, the more you need a fine-grained dependency graph.

Macros are the awkward case. Procedural macros run arbitrary code, so rust-analyzer runs them in a separate process (proc-macro-srv) to isolate crashes (source: rust-analyzer architecture doc).

Some questions cannot be answered by walking from the cursor: workspace symbol search, find all references, rename. They need an index. Code symbol indexing extracts symbols and references per file, gives each symbol a stable id, and re-indexes only files whose content changed. clangd documents the layered version: a dynamic index of opened files and their headers (always fresh), a background index built by parsing all project files with a thread pool and cached on disk as per-file .idx files, an optional static index built offline, and a remote index for codebases where the full index takes hours and gigabytes of memory; a MergedIndex layers them so features see one interface (source: clangd, The clangd index). The per-file storage is what makes edits cheap: replace one file's entry and the rest stay valid.

Fuzzy lookup (fuzzy-finder-scoring, no page yet) ranks names for workspace symbol search and completion. For rust-analyzer, the symbol index keeps one finite-state-transducer per file from the fst crate and unions them for a query, so a file update rebuilds one small structure (source: rust-analyzer symbol_index.rs; I read the code, the architecture doc does not describe it). The scoring that decides whether HshMp matches HashMap is a separate step on top of the candidate set.

Scheduler

The scheduler is where responsiveness is won or lost. rust-analyzer's main_loop handles requests that change state or must block typing (such as formatting and on-type edits) on the main thread, and sends other requests to a thread pool, each working on a consistent snapshot of the database (source: rust-analyzer architecture doc). The server is stateless in the protocol sense: a request is answered from the current state with no hidden session state.

Cancellation is the second half. When a new edit arrives, the database revision increments. A running read request that touches the database notices the revision mismatch and aborts by raising a special Cancelled unwinding panic which is caught at the ide crate boundary, and the server replies ContentModified (source: rust-analyzer architecture doc, with the error code from LSP 3.17). Cancellation by exception means analysis code needs no explicit checks, but code that catches all panics must rethrow this one.

Start-up work, such as priming caches for all crates, runs as background tasks that report $/progress.

Data and control flow

Keystroke to completion list.

  1. The editor sends textDocument/didChange with the changed range; the server updates the buffer in the file store.
  2. The main loop applies the change to the database inputs and bumps the revision. Any running request on the old revision is cancelled and answered with ContentModified.
  3. The editor sends textDocument/completion for the cursor position. The server converts the (line, character) pair into an internal offset in the negotiated encoding.
  4. A worker takes a snapshot, reparses the file (or its damaged region) into a lossless tree, finds the node at the offset, and queries name resolution and types for the receiver and scope. Only queries whose inputs changed re-run.
  5. Candidates are ranked and returned; expensive detail (documentation, edits) is deferred to completionItem/resolve so the first list is quick (source: LSP 3.17).

Cold start.

  1. The server initialises, negotiates capabilities and position encoding, and receives the workspace folders.
  2. The build system supplies the project structure (crate graph); the file store loads files and starts watching.
  3. A background pass parses and indexes the workspace, reporting $/progress; on-disk caches (as in clangd's .idx files) shorten later starts.
  4. Requests arriving meanwhile are answered from what exists, with partial or empty results rather than waiting.

Scaling

In the order the limits appear:

  1. Per-keystroke latency: parse and recompute only what changed; split item signatures from bodies so bodies do not invalidate the module-level model.
  2. Whole-workspace start-up: index in the background with a thread pool, cache per-file results on disk, and answer from partial data while it runs.
  3. Memory: the dependency graph and the index are the big items. Interning and arenas reduce the footprint; a remote index moves it off the laptop (clangd's reported answer for Chromium-sized code).
  4. Project size in files: watcher limits (inotify descriptors, event overflow) make a naive watcher fail, and the protocol's client-side watching offloads that work.
  5. Language complexity: macro expansion and templates make the dependency from edit to answer global; that is what pushes designs from the map-reduce style towards query-based computation.

Failure modes

FailureSymptomCauseFix
Stale answers after an editgo to definition lands on the old linerequest answered from an older revisionrevision check; answer ContentModified and let the client retry
Wrong columnshighlights and edits shifted on lines with emoji or CJKserver and client disagree on the position unitnegotiate positionEncoding; convert only at the boundary
Cancelled request never answerededitor spinner never endsprotocol requires a response even to a cancelled requestalways send an error response
Typing lagscompletion arrives after the next keylong request on the main thread, or no cancellationmain thread only for state changes; workers snapshot; cancel on revision bump
Whole-file invalidationevery keystroke re-resolves the modulefunction bodies part of the item-level inputsseparate signatures from bodies; backdate unchanged results
Lost file eventsnew file never seen; renamed file shown twicewatcher overflow or unsupported file systemtreat events as hints; rescan; let the client watch
Parser gives upfeatures vanish in half-typed codeparser throws on the first errorerror-tolerant parser that always returns a tree
Macro or build script crash takes server downserver exits when opening one projectuntrusted code executed in-processout-of-process macro server; restart on crash
Index never finishesworkspace symbol search empty on big repossingle-threaded indexing or memory pressurethread pool with disk cache; static or remote index
Garbled stream"invalid header" and a dead sessiona log line written to stdout instead of stderrreserve stdout for protocol; log to stderr

Real implementations

namewhat it isrepolicencenotes
rust-analyzerRust language server, query-based with salsarust-lang/rust-analyzerMIT or Apache-2.0architecture doc is the best written description
salsaincremental computation framework used by rust-analyzersalsa-rs/salsaMIT or Apache-2.0red-green algorithm, durability
rowanlossless syntax tree library used by rust-analyzerrust-analyzer/rowanMIT or Apache-2.0README: library for lossless syntax trees
clangdC++ language server in the LLVM projectllvm/llvm-projectApache-2.0 with LLVM exceptionpreamble and layered index design
goplsGo language servergolang/toolsBSD-stylelives in the Go tools repository
Eclipse JDT LSJava language servereclipse-jdtls/eclipse.jdt.lsEPL-2.0built on the Eclipse Java compiler infrastructure
tree-sitterincremental parsing library used by many editors (not a language server by itself)tree-sitter/tree-sitterMITsyntax layer only

The alternative: no server, a library linked into each editor. This avoids the protocol and the second process but needs one implementation per editor, which is exactly the matrix the protocol exists to remove. A middle path is a syntax-only server on tree-sitter: much cheaper and resilient, with no semantic answers. A compiler-driven server can reuse the real compiler for semantics but must work against code that does not compile.

Sources

Similar systems

Share the most building blocks with this one.

incremental-compiler 30 %code-editor 20 %type-checker 17 %formatter-linter 17 %