A Stable Lossless Syntax Tree for Real-Time Collaborative Programming

Software development has outgrown the lone programmer coding in a garage myth. It is a tool-rich, inherently collaborative process [12, 5, 47]. Yet, certain tasks demand high interaction and routinely leave developers navigating their teammates through code like “scroll to line 276…now type L-O-G”. These scenarios are common and break the programming flow, moments where simply taking over the keyboard would be more efficient. Real-time collaborative programming (RCP) environments emerged to enable these highly synchronous interactions inside Integrated Development Environments (IDEs) [45]. While many needs of collaborative programming are well served by asynchronous tools like Git, they do not suffice when immediate, shared context is required [26]. Such cases include pair and mob programming [42], code walkthroughs and interviews, teaching and peer learning [43], live troubleshooting, and concurrent edits to a single, tightly coupled artifact [45]. RCP tools belong to the field of Computer-Supported Cooperative Work (CSCW). In CSCW terms, synchronous groupware is constituted as “the class of applications in which two or more people collaborate in what they perceive to be real time” [7]. In practice, latencies vary but the community commonly uses real-time to denote such synchronous or near-synchronous systems. We follow this convention and use real-time collaborative programming to refer to these environments, treating real-time and synchronous interchangeably.

Popular RCP tools (e.g. JetBrains Code With Me [21], VS Code Live Share [28] and Replit [35]) synchronize and propagate changes at the text level via variants of Operational Transformation (OT) [41] or Conflict-free Replicated Data Types (CRDT) [25, 49, 50, 46]. However, mainstream OT and CRDT approaches target general-purpose text editing and are oblivious to programming language structure and semantic validity, so they routinely propagate syntactically invalid intermediate states that disrupt builds, analysis, and execution [30, 22, 40, 17, 33]. The result is chattiness (every keystroke broadcast) and visible lag on real networks [52, 45, 17], as well as weak synchronization semantics when multiple developers work on related code [14, 46, 33]. Host–participant architectures further constrain tooling and resilience [13]. Prior work [17] quantified these propagation inefficiencies and demonstrated that using a structure-aware model gating updates on syntactic validity can substantially reduce message volume and build-breaking states. Furthermore, it has been shown, that using a structure-aware model as a base for code synchronization enables better semantic-aware convergence that mirrors developer intent [30, 33].

A core requirement in RCP is convergence to the same user-intended program state [25, 41, 46, 49, 33]. For code, this entails two practical constraints: (i) edits must preserve byte-level round trips, including trivia such as whitespace, line breaks, and comments; and (ii) propagation should be gated to parser-accepted states to avoid broadcasting transient syntax errors. In addition, HCI findings constrain interaction latency: local feedback should remain immediate (roughly $0.1$–$0.2$ s) [29], while remote convergence need not be instantaneous but should typically complete within $\approx 1$–$10$ s to feel seamless [32].

Modern IDE and compiler infrastructures already maintain incremental parse trees, providing keystroke-speed for single-user code analysis and completion. However, they were not designed as replication substrates: they are typically lossy with respect to source bytes and stable node identities across revisions are not available. Prior structure-aware RCP efforts [30, 33] assume simple languages where the Abstract Syntax Tree (AST) mirrors the source text, limiting applicability to mainstream languages and leaving code-to-structure-to-code round-tripping unsolved.

Moving to structure is necessary but not sufficient. We found that three building blocks are missing in today’s tooling and research:

1. 1.

   Lossless, identity-stable syntax substrate with principled ID reuse. There is no substrate that simultaneously (i) guarantees byte-identical round trips, (ii) exposes persistent node identities across (re)parses, and (iii) specifies when existing IDs may be reused after edits (a reconciliation policy).

2. 2.

   Canonical, replayable edit algebra: Available AST differencing [20, 18, 51, 34, 19, 15, 10, 11] focuses on offline analysis and human-readable change, not a minimal, deterministic operation set suitable for replication semantics and Lossless Syntax Trees.

3. 3.

   End-to-end pipeline: An incremental pipeline that localizes edits, preserves IDs, gates propagation to parser-accepted states, and prints byte-identically has not been demonstrated for Real-time Collaborative Programming.

Guided by the presented research gaps, we ask:

RQ1.

Which invariants characterize well-formed program states in a stable lossless model, and how should tokens and trivia be organized to ensure precise round-trip printing and stable node identities across edits? (defined in Section 3.1–3.2, evaluated in Section 6.)

RQ2.

What minimal set of primitive operations is sufficient to capture edits while preserving closure and deterministic, canonical edit scripts? (algebra formalization in Section 4, experimental evaluation in Section 6.)

RQ3.

Can a structure-aware approach meet established HCI response-time budgets, and how do program/tree-structure properties (e.g. node count, maximum sibling fanout, depth) influence those latencies across languages and edit scenarios? (evaluated in Section 6.)

Building on prior evidence of propagation inefficiency and non-parsable states in text-based RCP [17, 45, 52], and to answer the presented research questions, this paper makes the following contributions:

1. 1.

   A Lossless Syntax Tree (LST) and Stable Syntax Tree (SST) substrate with reconciliation. We combine a Lossless Syntax Tree that guarantees byte-identical round trips with a Stable Syntax Tree overlay that assigns persistent, parent-scoped identifiers. We specify and validate reconciliation rules that deterministically reuse IDs of nodes, yielding durable, unambiguous identities across revisions. (RQ1, RQ3)

2. 2.

   A deterministic structural edit algebra. We define and formalize a small, prescriptive operation set and a deterministic extraction (diffing) procedure that yield canonical, replayable edit scripts over stable identities and preserve lossless printing. (RQ2, RQ3)

3. 3.

   Proof-of-concept and evaluation. We implement the approach in a web-based code editor and extensively evaluate two languages (Java, JavaScript), multiple file sizes, and five edit scenarios, reporting determinism, identity stability, byte-identical replay, and end-to-end latency. (RQ1–RQ3)

We do not address semantic concurrency control (e.g. intent inference, conflict resolution or merge policies). Instead, we contribute the structure-aware substrate such techniques require: a lossless, stable program representation and a deterministic change model that cleanly exposes program locality and identity. This substrate is designed to support a wide range of replication and resolution layers built on top [3, 8, 33].

Section 2 discusses related work and positions our approach within the context of RCP, synchronization techniques (OT/CRDT), incremental language tooling and parse trees, as well as approaches and algorithms to extract tree operations that drive the core contribution of this paper. Section 3 provides an overview of the structure-aware approach to RCP and defines the proposed LST and SST models, their invariants and our reconciliation heuristics. Section 4 presents a formal edit algebra and a deterministic operation extraction algorithm, and provides proofs of closure and replay correctness. Section 5 describes the proof-of-concept and discusses challenges and how we solved them. Section 6 presents our extensive evaluation and discusses results. Section 7 presents threats to validity. Section 8 concludes and outlines future directions.

Commercial systems (e.g. Code With Me [21], VS Code Live Share [28], Replit [35]) and research prototypes (CoVSCode [13], CoIDEA [48], CoEclipse [14], CRTC [23]) differ architecturally leveraging host–participant versus fully replicated workspaces. Yet, they share a text-first synchronization layer [30, 13, 48, 14, 23].

Operational Transformation and Conflict-free Replicated Data Types are well established for collaborative general text editors [41, 25, 49, 46]. Their operations are defined over sequences or text. Synchronization identities are positional rather than semantic. For code, replication benefits from operations anchored to structural entities with persistent names. The useful takeaways for RCP are thus: (1) edits must be replayable, and (2) those edits should target nodes with stable identities rather than transient character offsets [30].

Modern IDEs demand a fast code analysis, essentially instantly to preserve a developer’s sense of flow. Tight HCI interaction budgets [29] push editors toward incremental parsing: only the region affected by an edit is reparsed and reanalyzed rather than re-parsing the whole program. Mainstream compilers such as Roslyn (C#) [31], Rowan (Rust) [36] and Swift [44] embody this with persistent, immutable program trees [24]. Roslyn’s Red–Green design, for instance, keeps a compact, immutable lossless green tree and a lightweight red façade. Edits rebuild only the affected path and may hash-cons identical subtrees for efficiency [24]. For compilers, hash-consing identical greens is harmless and efficient. However, when extracting changes in code during tree diffing and replication, it is problematic: two subtrees with the same shape and tokens may collapse to the same instance, so there is no way to distinguish per-occurrence identity. Other incremental parsing approaches, such as Tree-sitter [27], emphasize fast reparsing and broad grammar coverage. Tree-sitter constructs concrete syntax trees of node typees and source ranges, not a self-contained document tree. Lexemes are obtained by slicing the original buffer, and trivia is generally treated as non-structural. As a result, Tree-sitter does not promise a standalone, byte-for-byte round-trip or provide a built-in code-generation (it is a one-way text$\to$tree parser). Presented tools were designed for static analysis, not replication: lossless models generally do not publish durable node identities across (re)parses, edit-local updates often do not preserve all source bytes.

Classic tree differencing algorithms such as GumTree [11, 10], Zhang–Shasha [51], APTED [34], and ChangeDistiller [19, 15] compute compact, human-readable edit scripts from two snapshots by recovering node correspondences over the whole tree. These scripts are descriptive: node identities are ephemeral and formatting bytes are typically ignored. Replication instead needs prescriptive scripts over persistent ids that preserve trivia so replay prints the exact target bytes.

A related idea appears in React’s virtual DOM reconciliation (Fiber), which uses persistent keys to derive small, deterministic updates to a concrete target [6, 1]. Although our target is source code rather than a browser DOM, the design lesson transfers: maintain a printable concrete tree plus a stable-id overlay, reconcile per parent, and emit deterministic scripts over those ids.

CoAST [30] provides important foundational evidence for the promise of structural approaches to RCP. By defining an AST-based CRDT, it shows that operating over program structure can improve convergence and better preserve user intent than text-based schemes. At the same time, the evaluation assumes a simple Lisp-like subset in which the program is effectively identical to its AST, so concrete syntactic details such as comments and whitespace fall outside the model. The approach uses the GumTree [11, 10] algorithm to derive tree operations between versions, which is reasonable in that restricted AST-only setting, but becomes less practical for larger programs and large file structures, where GumTree does not scale well. Overall, CoAST highlights both the opportunity of structural RCP and the limits of a purely AST-based formulation, motivating a concrete, lossless syntax representation.

Human–computer interaction research suggest that local feedback must remain immediate ($\approx 0.1$–$0.2$ s [29]) so the editor never “freezes”, while remote interactions should ordinarily complete within about $1$–$10$ s to feel seamless [32]. Empirical reports for RCP indicate that character-wise propagation amplifies lag [52, 45] and exposes collaborators to broken builds; batching at parser-accepted boundaries attenuates both effects [17]. Consequently, the synchronization substrate should be incremental, with commit gating and round-trip guarantees.

We treat collaborative editing as replication of program structure, not character streams. The approach maintains a byte-preserving syntax representation and an identity layer that keeps syntactic entities addressable across revisions. From successive accepted program states we then derive a deterministic, replayable change log (edit script). This log is the contract exported to collaboration: it supports efficient replication and provides the stable addressing required by higher-level concurrency control and conflict-resolution layers, which are orthogonal to this paper.

We use round-trip fidelity to mean byte-identical printing of source, including program trivia, like linebreaks, comments and other symbols not covered by ASTs but necessary in source code files. A syntax gate (shown in Figure 2) commits changes only for parser-accepted states. Stable identities are node identifiers that are deterministically reused across revisions and remain unchanged for syntactic entities that are unaffected by an edit. An edit script is the deterministic operation sequence extracted between two program states (details in Section 4).

An overview of the core pipeline is presented in Figure 1. Given a local text delta $\mathrm{\Delta }t$, we incrementally reparse and apply the syntax gate. From the accepted parse we (i) materialize the LST, (ii) reconcile SST identities against the previous revision, and (iii) deterministically extract an edit script over SST identifiers. In a distributed setting, this script is the exported replication contract: replicas apply it to their local SST/LST state and reprint byte-identically, without re-parsing. Section 4 formalizes the edit algebra, deterministic extraction, and replay semantics, and proves closure and replay correctness. Conceptually this follows state machine replication [37, 38], with edit scripts as the command log and the SST as the replicated state.
We propose the following design goals:

• $\mathrm{■}$

  Round-trip fidelity. Printing after replay reproduces the target source byte-for-byte.

• $\mathrm{■}$

  Identity persistence. Unchanged entities retain their SST IDs across revisions; IDs are parent-scoped to keep reuse precise (presented in section 3.2).

• $\mathrm{■}$

  Determinism. Given the same prior state, applying the extracted script to any replica in state $S^{-}$ yields the same new state $S^{+}$ (presented and formalized in section 4).

• $\mathrm{■}$

  Locality. Unaffected regions remain untouched and small edits yield small edit scripts (evaluated in section 6.2).

• $\mathrm{■}$

  Language-agnosticism. A lightweight per-language specification (presented in section 3.2.1) configures keying and reconciliation without changing the core.

We mount the Monaco Editor in a thin component and normalize End-of-Lines(EOLs) to LF (to keep Tree-sitter byte math consistent), and forward editor change batches to the worker. The UI stays responsive: it only updates view state from worker acks. An OpsGraph widget visualizes operation batches over time.

We ship Tree-sitter via its wasm (WebAssembly) package and load per-language grammars (Java, JavaScript) in the worker. On each editor change event, we convert line/column ranges to byte offsets, call tree.edit(…), and then reparse incrementally. For robustness, the pipeline is gated when the parse contains ERROR/MISSING nodes: the worker updates the parse tree, but defers LST/SST/diff until the code is syntactically valid.

A compact per-language specification (§ 3.2.1) configures identifiers, container kinds, delimiters, separators, trivia, and optional semantic keys. The specification drives keying and delimiter-aware matching in reconciliation. This keeps the core algorithm (presented in section 3.2.1) language-agnostic while enabling precise reuse.

The worker converts the Tree-sitter tree to an LST that preserves bytes. We then build an SST with stable ids by parent-scoped reuse, guided by the spec-derived key function.

Given the previous and next SST plus the set $R$ of reused ids, we produce an edit script based on the formalism presented in Section 4. We do not broadcast operations to real clients. Instead, the app simulates a replica: we clone the previous SST once and apply only operations to that replica. Both the source-of-truth LST and the replica LST are printed back to source code. The UI shows a convergence check ($\mathrm{✓}/\times$) and the last operations applied.

The worker exposes four messages: init, set-language, edit, and build. Replies include: buildable (syntax gate), lastOps (recent structural edits), ranges (changed byte windows), and the printed strings (truthPrinted/replicaPrinted). Language metadata is returned on init/set-language to keep the UI dumb and fast.

All CPU-intensive steps run off the main thread. The syntax gate prevents expensive work during transient syntax errors, improving perceived latency during fast typing.

The prototype is single-user in the browser: we simulate replication locally and do not implement network transport or real multi-site causality. Nevertheless, this is sufficient for our contribution because all reported invariants and timings concern the local parse$\to$reconcile$\to$diff$\to$replay pipeline. Network transport and multi-site causality only affect delivery latency and ordering, not the structure or determinism of the generated edit scripts.

We will lower tree-build latency via incremental SST rebuilds keyed to dirty spans, targeting p95 1 s on large, wide files. Additionally, we will broaden language coverage to layout-sensitive (e.g. Python) languages, and stress-test large modules to evaluate how far the language-spec dials generalize. We will make the edit script the OT/CRDT convergence layer over SST identifiers, and evaluate bandwidth and replay idempotence under reordering, benchmarking against text-based approaches. Finally, we plan developer studies to assess perceived responsiveness and situational awareness versus text-based RCP, and to explore which commit gates (e.g. parser-accepted boundaries, debounce windows, or semantic checkpoints) best align with developer intent and typical workflows in RCP.