A Zero-Copy, Incremental Approach to Abstract Syntax Tree Manipulation for Real-Time Code Refactoring
Lars Shakya Buch-Jepsen
A Zero-Copy, Incremental Approach to Abstract Syntax Tree Manipulation for Real-Time Code Refactoring
1. Introduction
Classical AST manipulation is expensive in ways that only surface under real-time constraints. Every edit to an immutable tree rebuilds a path to the root; every mutation of a mutable tree risks aliasing bugs that are nightmares to reproduce; and every analysis pass that touches a graph in memory pays garbage-collection pressure proportional to the churn. For interactive refactoring - where operations arrive per keystroke and analyses must re-run within the latency budget of an editor - these costs are the binding constraint, not the analysis algorithms themselves.
This article presents the representation at the core of the DevelApp stack: the CognitiveGraph, a zero-copy graph for code analysis that replaces the AST as the substrate for parsing, editing, analysis and refactoring. The representation is shipped as a production library (with 127 unit tests across core functionality, performance and edge cases, distributed via NuGet, tested on Windows, Linux and macOS), and it is the substrate that Minotaur’s parsing, unparser, and Labyrinth analysis engine - and Golem’s transformations - operate on.
2. Why Classical AST Mutation Is Expensive
Three structural problems, not implementation sloppiness:
- Aliasing and structural sharing hazards. A mutable tree shared across components (editor, analyzer, refactoring engine) invites one component to invalidate another’s assumptions. The purely functional tradition answers with persistent structures and structural sharing [1] - at the cost of rebuilding paths on every edit.
- Representation duplication. In conventional pipelines the parser’s tree, the analyzer’s graph, and the unparser’s model are three structures, translated back and forth - copying at every seam.
- GC pressure. Node-object forests allocate heavily under incremental edit workloads; an editor reparsing per keystroke spends more time in allocation than in analysis.
3. The Zero-Copy CognitiveGraph
3.1 Memory model
The CognitiveGraph stores the entire graph in a contiguous binary buffer: symbol and packed nodes with type-safe property records, offsets instead of object references, and source positions embedded per node. Readers access nodes through span-based, allocation-free views; there is no per-node heap object at all. The buffer format is a cross-platform binary layout, and the same format supports memory-mapped files, so very large graphs load without resident copies - the property Golem’s training harness relies on for TB-scale corpora.
3.2 SPPF and CPG in one structure
The graph unifies two classic representations: Shared Packed Parse Forest (SPPF) packing for syntactic ambiguity - ambiguous nodes carry all parse interpretations as packed alternatives rather than forcing an eager choice - and Code Property Graph (CPG)-style semantic edges for control flow, data flow, and type relationships. One structure therefore serves the parser (ambiguity preserved), the analyzer (semantic edges), and the refactoring engine (both) - eliminating the representation duplication of conventional pipelines.
3.3 Concurrency model
Reads are fully concurrent on the immutable buffer; writes follow a single-writer discipline. For interactive tooling this is the right asymmetry: many consumers (highlighting, analysis, rule matching) against one producer (the edit pipeline).
4. Editing and Refactoring as Graph Rewrites
Refactoring is the acid test of a code representation: the operations that matter (rename, extract, inline, move) are structural rewrites that must stay consistent across every reference. In the DevelApp stack, refactoring operations are graph-level transformations on the CognitiveGraph, with the classic discipline of behavior-preserving program transformations [2], [3] enforced by what the representation itself makes checkable: semantic edges (data flow, control flow) mean a rename’s blast radius is a traversable set rather than a text search; the grammar (via Minotaur’s parser and Unparser) means rewritten output is validated by round-trip; and the incremental edit pipeline is copy-on-write at the buffer level: layout-preserving edits clone the graph buffer once and patch the affected fixed-size records in place, with every offset in the buffer stable across the edit. A single-node rewrite on a 10K-node graph is measured at 1.9 ms and one buffer-sized allocation (Section 5) - proportional to the file, not to the change; absolute edit-cost proportionality (structural sharing between versions) remains the declared design target.
4.1 Spatial Indexes and Scope-Aware Symbol Tables (design surface)
The rewrite semantics above treat edits as graph operations, but two queries that refactoring engines issue constantly are not themselves rewrites, and both admit designs that consume the shipped graph without changing it. This subsection records those designs as proposed architecture for refactoring engines consuming the shipped graph; neither component is shipped or measured, and nothing in the measured sections should be read as evidence about them.
Spatial indexing over the interval index. The zero-copy buffer already maintains an interval index for node spans. The proposal is to overlay interval-query structures on that same index so location-based questions, which construct encloses offset 4,117?, what is visible under this hover rectangle? —* become index lookups and independent tree traversals rooted at candidate intervals. Because span queries never mutate, and because after a rewrite new node spans either adapt from their sources or re-register, the spatial layer’s update cost is carried entirely by the update flow already measured for the interval index.
Scope-aware symbol tables as an integrated view. The
second design defines an IScopeAwareSymbolTable: not a
separate data structure to be rebuilt as the tree mutates, but an
integrated view over semantic edges that already exist in the graph,
resolution and binding relationships. Because the view is edge-driven,
find-usages and the blast radius of a rename stop being
analytical guesses and become traversable edge sets: consuming a symbol
means following binding edges, renaming it means enumerating exactly the
nodes holding those edges and staging their updates as graph rewrites,
the same primitive already at work in the shipped model. Scope
boundaries ride along as auxiliary edges, so name lookup is a graph walk
rather than a synthetic table lookup refreshed after every edit.
5. Performance: What Is Measured, What Is Target
The library’s BenchmarkDotNet suite (CognitiveGraph issue #58) compares the CognitiveGraph against a naive object-node AST and a persistent immutable AST over the identical tree shape, with committed raw exports, environment records, and scripts in the repository under benchmarks/results/. We report each claim with its exact epistemic status:
- Measured (medians, Linux x64, .NET 8, short job; raw
BenchmarkDotNet exports committed):
- Graph creation: 1K nodes in 0.95 ms cold (about 1 µs per node; 11.2 ms for 10K, 83 ms for 100K) - the under-1-ms target for 1K nodes is met. Building the flat buffer is ~10x slower than building the equivalent object tree; the buffer write path (property records, string table, interval index, packed nodes) does more work per node than an object allocation.
- Access: node-header reads at 1.6 ns per node; span-based property reads at 18.6 ns per property, allocation-free as designed (1 byte per full-tree pass); keyed property lookup is 184 ns because key comparison materializes strings - the span path, not the key path, is the one the ~10 ns order-of-magnitude describes.
- Memory: O(n) confirmed - the buffer holds a flat 104 bytes per node, and live heap grows 0.1 / 1.0 / 10.3 / 103 MiB across 1K to 1M nodes, about 3.4x less live memory than the equivalent object-node AST.
- Memory-mapped load: a mapped graph loads with zero bytes allocated and zero growth of the managed heap, where a resident copy puts the whole file on the GC heap (measured +99.2 MiB for a 1M-node, 99 MiB file). The honest price: traversal of the mapped view is ~25% slower than the resident copy on a cold file.
- Incremental editing (issue #68): layout-preserving edits - a node rewrite without structural change, a node move, a property update that keeps its byte length - clone the buffer once and patch records in place, all offsets stable. A single-node rewrite on a 10K-node graph takes 1.94 ms and allocates 2.28 MB (one flat copy; the previous rebuild implementation measured 24 ms / 10.3 MB - 12.3x / 4.5x); a same-length property update takes 0.73 ms / 1.04 MB (33x); and a sustained 100-edit loop runs 190 ms allocating 216 MB (previously 969 ms / ~1 GB), with Gen0-Gen2 collections per 1000 loop operations down from 79,000 to 24,000. Edits that do change the layout (insert, delete, property add/remove, type or length change) fall back to the full rebuild. The persistent-tree baseline still performs a single path edit in 0.62 µs with 1.3 KB - O(depth) versus our one buffer copy - so per-edit cost is now free of per-node allocation and rebuild, but proportional to the buffer, not to the change.
- Tests: 127 tests, all green, in CI on Windows, Linux and macOS.
- Still design targets: true edit-cost proportionality - making an edit cost proportional to the change rather than the file - requires structural sharing between graph versions (offset indirection), which the copy-on-write fast path deliberately does not attempt; it is the tracked follow-up to issue #68. Likewise, the TB-scale mmap claim is extrapolation: zero-copy load is verified on measured hardware to 1M nodes (~100 MiB), not terabytes.
This labeling is not a disclaimer bolted on; it is the difference between an engineering claim (the architecture makes these costs structurally unlikely) and an empirical claim (measured on a benchmark suite). Where the committed suite has spoken, we make the second; where it has not, we make only the first.
6. Related Work
Persistent data structures and their structural-sharing economics are given by Okasaki [1]. Incremental parsing as an editor requirement was normalized by tree-sitter [4]; the CognitiveGraph shares its incrementality goal and differs in representation (flat binary buffer with SPPF/CPG semantics rather than concrete syntax trees). Behavior-preserving refactoring was formalized by Opdyke [2] and cataloged by Fowler [3]; the graph’s semantic edges make such preservation checkable structurally.
7. Conclusion
The zero-copy CognitiveGraph replaces the AST with a single flat, concurrently-readable, ambiguity-preserving, semantically-edged graph that every layer of the stack shares without copying - the “why CognitiveGraph exists” answer to the companion symbolic-execution article’s “what it enables”. Its architecture eliminates, structurally, the aliasing, duplication and GC costs of classical AST manipulation; its zero-copy claims are now backed by committed measurements - creation, access, memory, mapped load, and the copy-on-write incremental edit path - and where a claim is still a target rather than a measurement (structural sharing between versions, TB-scale load), this article says exactly that.