1. TLDR tldrTwo technologies have endowed every editor with IDE superpowers this past decade: tree-sitter, a generic incremental parser that gives your editor a live syntax tree of your code, and the Language Server Protocol (LSP), a generic client-server protocol that gives your editor code intelligence features like linting, type-checking, auto-completion, and code navigation. Each one replaces an M×N fan-out of per-language, per-editor hacks with a single, language- and editor-agnostic protocol. Emacs has merged support for both into its core, and shipped them in Emacs 29.1 (three years ago this month!). This post explains what each one does, visualizes a real-life tree-sitter parse tree, and recounts how both technologies made their way upstream into the glorious Emacs core.An interactive visualization of the syntax tree tree-sitter builds from a small Python module — hover any node for details, click to zoom into a subtree. Two more of these live further down the post.2. About emacs carnival programmingThis is my entry for July's Emacs Carnival, hosted by Andy over at Plain DrOps. The theme is Programming, i.e. Emacs as a programming environment. I've done these before (May was about deep Emacs patterns, June about Emacs teaching you Emacs), and this month I want to push back on my least favorite meme: that Emacs is arcane; rusty and dusty; old news; the "Editor for Middle Aged Computer Scientists".Emacs has been under active development by a growing number of contributors, and is surprisingly modern. As two language-agnostic protocols for IDE features arose (tree-sitter for syntax and LSP for semantics), Emacs developers quickly merged support for both into core. More interestingly, they made them usable in the editor by integrating them into the Emacs machinery that predates them by decades.The first suggested topic in the carnival is "Language Specific Setups" and, given the utility of tree-sitter and LSP, I couldn't help but misinterpret this suggestion intentionally and create a post on my "Language Generic Setup".3. The Combinatorial Woes of M×N leverage architectureTraditionally, in most IDEs "support for language X" meant one implementation per editor, per language.Syntax highlighting was a mixed bag of regular expressions that approximated the language's grammar.Navigation ("jump to the function I'm in") was basically regex guesswork. Completion and go-to-definition, if they were even available, came from language-specific plugins of wildly varying quality.With M editors and N languages, the world had to write (and maintain, and debug) M×N of these plugins. The modern fix is the classic programmer's reflex of establishing a generic layer, or protocol, in the middle, and paying a much more affordable M+N tax instead (the framing the LSP community itself uses).This reflex is older than any editor in the diagram below, by the way. It's the UNCOL argument from 1958, which suggested putting one universal intermediate language between M source languages and N machines, and M×N compilers become M+N. UNCOL itself never shipped, but its argument became the standard justification for compiler intermediate representations, and the argument is just as valid for editor tooling.graph TB subgraph before["Before: every editor reimplements every language (M × N)"] direction LR A1[Emacs] --- B1[Python] A1 --- B2[Rust] A1 --- B3[TypeScript] A2[Vim] --- B1 A2 --- B2 A2 --- B3 A3[VS Code] --- B1 A3 --- B2 A3 --- B3 end subgraph after["After: one generic layer in the middle (M + N)"] direction LR C1[Emacs] --> MID(("tree-sitter+ LSP")) C2[Vim] --> MID C3[VS Code] --> MID MID --> D1[Python grammar & server] MID --> D2[Rust grammar & server] MID --> D3[TypeScript grammar & server] end before ~~~ afterTree-sitter provides the answer to "what is this text, structurally?" — it can tell the editor that characters 4 through 7 are a function name. LSP provides the answer to "what does this text mean, in this project?" — it knows that the function is defined in another file, is called from twelve places, and is missing an argument, etc…. These two layers solve "syntax and semantics" in a graceful, reusable way.4. Tree-sitter: a Fresh Parse Tree on Every Keystroke treesitter parsingTree-sitter, started by Max Brunsfeld while working on Atom at GitHub, is a parser generator plus an incremental parsing library. Rather than implementing a boat-load of regular expressions, you provide tree-sitter with a language's grammar, tree-sitter compiles it into a small C library, and any tool can then parse that language. Each grammar is its own small repository. The canonical ones live under the tree-sitter GitHub org (e.g. tree-sitter-python, the grammar behind every tree in this post), and the community maintains a list of hundreds more.Compilers typically wouldn't work well for providing live feedback in the text-editing use case, but there are two properties that make tree-sitter performant and robust enough to be editor-grade:It's incremental. When you type a character, tree-sitter doesn't re-parse the file, but rather patches the existing tree in microseconds. The result is that you have an up-to-date parse tree, immediately, on every keystroke.It's error-tolerant. Code being edited is malformed almost all of the time, because you are mid-keystroke more often than not. Tree-sitter handles this gracefully and keeps the rest of the tree intact instead of failing at the first syntax error.These aren't new ideas so much as ideas finally made practical. The figure below comes from the 1998 Berkeley dissertation that inspired tree-sitter's development, and it shows the incremental trick. As an edit arrives, the parser restores a consistent tree by creating just two new nodes (black) and adjusting a handful of others (gray). Every other node in the tree is reused as-is. This is a phenomenal paper, by the way, I highly recommend you read it.Figure 1: From Tim Wagner's 1998 Berkeley dissertation, Practical Algorithms for Incremental Software Development Environments (his Figure 4.3), the work tree-sitter's incremental parsing builds on. Dashed lines are the paths walked to reach the edit site.4.1. Looking at Concrete TreesYou'll most often hear these trees called Abstract Syntax Trees (ASTs). Tree-sitter's own docs use the term, but strictly speaking, tree-sitter produces a concrete syntax tree (CST). While an AST discards everything that stops mattering once the structure is known (keywords, parentheses, punctuation), a CST keeps every last token of the source. Editors need the concrete version, because you can't highlight a def you've thrown away. You'll see this in the charts below, where the keyword and punctuation tokens appear in the tree, in gray.Here I show a few examples, in order of increasing complexity, of the syntax trees that tree-sitter actually produces from Python code.There are many ways to visualize these trees. Mine are drawn with plotly as an icicle chart. Each tile is a node in the tree. A tile's width is proportional to the amount of source code the node covers, and its children sit beneath it. Color encodes the node's role in the code. These charts are interactive and fun to play with (which is why I created three examples!). You can hover over any tile to see the node type and the exact source bytes it covers, and you can click a tile to zoom into its subtree (the breadcrumb bar that appears on top zooms you back out).4.1.1. Fibona-treeHere's everyone's favorite, flogged-to-death fibanacci function:def fib(n): if n