Reps, Teitelbaum & Demers (1983) -- Incremental Context-Dependent Analysis for Language-Based Editors

Paper Summary

Reps, Teitelbaum, and Demers attack the problem of keeping a program’s context-dependent (non-context-free) properties consistent as the program is edited, one small change at a time, inside an interactive language-based editor (the Cornell Program Synthesizer / Synthesizer Generator) (Abstract, p449; S1, p449-450). Context-free grammars cannot express constraints that interrelate widely separated parts of a program (declarations vs. uses, scoping, types); attribute grammars (Knuth [19]) extend CFGs declaratively to do so (S1, p450; S2, p451). The editor represents a program as an attributed tree, and edits are derivation-tree operations — pruning, grafting, deriving (S1, p450; S3, p453-454). After each edit the editor must restore a consistent, fully attributed tree; the paper’s contribution is a family of incremental attribute-evaluation algorithms, culminating in one that is asymptotically optimal in time (Abstract, p449; S1, p450).

An attribute grammar attaches synthesized and inherited attributes to grammar symbols; each production carries semantic equations defining one attribute as a semantic function of others in that production (S2, p451). In normal form, every equation defines a synthesized attribute of the left side or an inherited attribute of a right-side symbol from inherited attributes of the left side and synthesized attributes of the right side (S2, p451). A derivation-tree node labelled X has attribute instances; a semantic tree assigns each instance a value or the token null (null = “unavailable”, outside every attribute’s domain) (S2, p452). Functional dependencies are captured by a dependency graph D(T): a vertex b' per attribute instance b, and an edge (b', c') iff b is an argument of c (“b' is used to determine c'”) (S2, p452). An instance is consistent iff its arguments are available and its value equals its semantic function applied to those arguments; a tree/graph is consistent iff all its instances are (S2, p452). The grammar is assumed well-formed and noncircular — D(T) acyclic for every derivation tree (noncircularity decidable [18], intrinsically exponential [14] but feasible in practice) (S2, p453). To keep partial programs fully attributed, each nonterminal X has a completing production X → ⊥ (“unexpanded”); every edit — insertion, deletion, derivation — is modelled as a subtree replacement of one X-rooted tree by another (S3, p453-454). Replacement = pruning U then grafting U'; grafting copies the old node’s synthesized attributes and the new root’s inherited attributes, so all initial inconsistencies are confined to the attributes of the single modification point r (normal form) (S3, p454; S4.1, p455).

The core quantity is AFFECTED: let T' be the inconsistent tree just after replacement and T'' the same tree after updating; AFFECTED is the set of attribute instances that have different values in T' and T'' (S4.3, p457). Crucially, AFFECTED is not known a priori — “it is not known which attributes are members of AFFECTED; AFFECTED is determined as a result of the updating process itself” (S1, p449-450; S4.3, p458). Because O(|AFFECTED|) is the minimum work any updater must do (you must at least write the new value of every attribute that changed), an evaluator is optimal-time iff it runs in O(|AFFECTED|) steps, counting each semantic-function evaluation as unit cost (S4.3, p457-458).

The paper builds up to the optimal algorithm through two naive ones (S4). Change propagation (Algorithm 1, p456) keeps every attribute available-but-possibly-inconsistent and a work-list S of attributes whose arguments changed; it reevaluates an attribute, and if the new value differs from the old, inserts the successors into S — “if reevaluating an attribute instance yields a value equal to its old value, changes need not be propagated further” (S4.1, p455). This unchanged-value cutoff is the heart of incrementality, but naive change propagation is sensitive to evaluation order: with attributes joined by more than one path, following dependencies blindly can be quadratic (FIFO) or exponential (LIFO) in the number of attributes reevaluated (S4.1, p456; Appendix, p474-475). Nullification/reevaluation (Algorithm 2, p457) instead NULLIFYs the modification point and propagates null, then EVALUATEs consistent values; each attribute is touched once, so it is linear in the attributes considered — but the set of attributes reachable from the modification point bears no fixed relation to |AFFECTED|, so it does extensive needless propagation when AFFECTED is small (S4.2-4.3, p456-458). Neither naive method is optimal.

The fix (S4.3, p458): a temporarily-wrong value propagates spurious changes “arbitrarily far beyond the boundaries of AFFECTED.” So an attribute must not be reevaluated until all its arguments hold their correct final values — equivalently, AFFECTED must be enumerated in topological order w.r.t. D(T). Nonincremental evaluators get this from Knuth’s topological sort [20] over D(T) in O(|D(T)|) [17, 22]; the incremental problem is to generate AFFECTED in topological order in O(|AFFECTED|) (S4.3, p458).

Optimal-time change propagation (S5; Algorithm 3, p462; refined as Algorithms 4-5) is a generalization of Knuth’s topological sort in which the vertex set of the scheduling graph is generated dynamically while it is enumerated (S5, p458-459). It keeps a work-list of attributes ready for reevaluation (in-degree zero) and a model graph M of dependencies among not-yet-reevaluated attributes; an attribute joins the work-list when its in-degree in M drops to zero (S5, p458-459; S5.2, p461). The decisive trick is characteristic graphs: for a node s, the subordinate graph s.C = D(T_s)/V_s projects the dependencies of the subtree rooted at s onto s’s own attributes, and the superior graph s.C̄ = (D(T) − D(T_s))/V_s projects the rest-of-tree dependencies onto s’s attributes (S5.1, p459; projection A/V' defined p459). These transitive-dependency edges let PROPAGATE skip, in unit time, arbitrarily large sections of D(T) whose values do not change and ensure an attribute is never updated before all its ancestors are consistent — so no attribute is ever assigned a temporarily-wrong value (S5.2, p463). M starts as r.C ∪ r.C̄ (just the modification point’s attributes); it is expanded one production instance at a time (procedures EXPAND, ExpandedSubordinate, ExpandedSuperior, Figure 3, p462) only when a changed attribute is an argument of an attribute outside M — i.e. only when a new member of AFFECTED is discovered (S5.2, p461-462). Therefore M never exceeds O(|AFFECTED|), each vertex costs one semantic-function application plus constant bookkeeping, and both the total number of evaluations and the total bookkeeping cost are O(|AFFECTED|) — PROPAGATE is asymptotically optimal (S5.2, p462-463).

Three refinements complete the surface. (1) A bare M-enumeration still evaluates some attributes that join M but whose arguments never changed (an attribute at r up to 3 times, others up to twice — not a violation of the bound, but wasteful since evaluations may be costly); the set NeedToBeEvaluated removes them: an attribute is reevaluated only if a predecessor actually changed value (S5.3, p464-465; Algorithm 4, p465). (2) Characteristic graphs are maintained lazily relative to the cursor. Maintaining every node’s graphs is too expensive (a replacement at r can alter graphs arbitrarily far away); instead the tree is kept “prepared for propagation at the cursor r”: r carries both r.C and r.C̄, each node on the path r→root carries its superior graph, every off-path node carries its subordinate graph (S5.4, p465-466; Figure 6). Cursor motion (AscendToParent/DescendToChild) re-establishes this invariant at unit cost per step, so moving the cursor over a path of length m costs O(m) (S5.4, p466). (3) The single-edit restriction is dropped: for an arbitrary restructuring, let R be the smallest connected region containing all initially-inconsistent attributes; initialize M to D(R) ∪ root(R).C̄ ∪ {subordinate graphs of R's frontier} and NeedToBeEvaluated to all of R’s attributes — this also drops the normal-form assumption (S5.5, p467).

Section 6 adds practical machinery. Identity-function (copy-rule) optimization (S6.1, p468-469): a large fraction of semantic functions are identities [40]; once a copy-rule chain’s head changes, the rest must change, so the equality tests along the chain can be skipped (valid only when the chain’s old values were consistent — the only possible inconsistencies are inside R) (S6.1, p468-469). Demand attributes (S6.2, p469-470): attributes whose values are not observable right after an edit need not be kept consistent — they are evaluated only when a demand arises (user query, screen display, or a neighbouring regular attribute needing the value); a demand attribute that loses an argument’s value is set to null and lazily recomputed via DEMANDVALUE (Algorithm 5, p470). This is exactly demand-driven / pull-based evaluation, dual to the topological push: “start from the vertices with no successors, reverse the edges, and do depth-first endorder” (S6.2, p469-470). The authors note the characteristic graphs themselves are graph-valued demand attributes linked to the cursor (S6.2, p469). Efficient large attributes (S6.3, p471-472): symbol-table-valued attributes are shared through indirection so identical values share storage and copy-rules copy pointers; sharable 2-3 trees let nearly-identical values share all but O(log n) structure, giving O(log n) MEMBER/INSERT vs. O(n) for linked lists [34] (S6.3, p471-472). Section 7 contrasts the declarative AG approach with the imperative semantic-action approach (Gandalf, AVID): action routines can record nonlocal dependencies and thus skip large tree regions an AG evaluator must visit node-by-node, but require hand-written, order-independent semantic retractions to undo effects on deletion — the AG approach needs no explicit undo because consistency is re-established automatically from the equations (S7, p472-474).

Key Concepts

Attributed tree / semantic tree (S2, p452). A derivation tree plus an assignment of a value or null to each attribute instance. null (“unavailable”) is outside every attribute’s domain; fully attributed = every instance non-null; an instance is ready for evaluation when all its arguments are available.
Dependency graph D(T) (S2, p452). Vertex b' per attribute instance b; edge (b', c') iff b is an argument of c (“b' determines c'”). The single structure over which all propagation runs. Noncircular AG ⇒ D(T) acyclic for every tree (S2, p453).
Consistency (S2, p452). Instance b is consistent iff (1) its arguments are available and (2) value(b) equals its semantic function applied to those arguments. The editor’s job after each edit: restore a consistent, fully attributed tree (S3, p455).
Subtree replacement confines inconsistency to one node (S3, p454; S4.1, p455). Grafting copies the old node’s synthesized + new root’s inherited attributes; under normal form all initial inconsistencies sit at the single modification point r. This is what lets PROPAGATE start from r alone.
AFFECTED = {attributes whose value differs before vs. after updating} (S4.3, p457). The exact set that must be rewritten. Determined only by the updating process itself, never known a priori (S1, p449-450; S4.3, p458). |AFFECTED| is the information-theoretic lower bound on update work.
Optimal-time = O(|AFFECTED|) (S4.3, p457-458). An incremental evaluator is optimal iff its cost (semantic-function evals as unit steps, plus bookkeeping) is proportional to |AFFECTED|, not to |D(T)| or to the reverse-reachable set from r.
Unchanged-value cutoff (S4.1, p455). “If reevaluating an attribute instance yields a value equal to its old value, changes need not be propagated further.” The cutoff that bounds propagation to AFFECTED — a recomputed-but-unchanged attribute does not enqueue its successors.
Order sensitivity of naive propagation (S4.1, p456; Appendix, p474-475). Following dependencies blindly when two attributes are joined by multiple paths gives quadratic (FIFO) or exponential (LIFO) behaviour. The cure is to never reevaluate an attribute until all its arguments are final ⇒ topological enumeration of AFFECTED (S4.3, p458).
Characteristic graphs s.C / s.C̄ (S5.1, p459). s.C = D(T_s)/V_s (subordinate: subtree-below transitive deps projected onto s’s attributes); s.C̄ = (D(T) − D(T_s))/V_s (superior: rest-of-tree transitive deps). They encode transitive dependencies that travel entirely outside the modeled region, so propagation can skip unchanged regions in unit time and never assigns a temporarily-wrong value (S5.2, p463).
The model M + dynamic topological sort (S5, p458-459; S5.2, p461). PROPAGATE = Knuth’s topological sort whose vertex set is generated while being enumerated. M holds dependencies among not-yet-reevaluated attributes; it starts at r.C ∪ r.C̄ and grows one production instance per newly-discovered AFFECTED member (EXPAND, Fig 3, p462), so |M| = O(|AFFECTED|) always. Result: O(|AFFECTED|) total (S5.2, p462-463).
NeedToBeEvaluated (S5.3, p464-465). Avoids reevaluating attributes that enter M but whose arguments never changed (≤3× at r, ≤2× elsewhere otherwise). An attribute is reevaluated only when a predecessor actually changed — prunes wasted evaluations without affecting the asymptotic bound.
“Prepared for propagation at r” invariant (S5.4, p465-466). Only r needs both characteristic graphs; path-to-root nodes carry superior graphs, off-path nodes carry subordinate graphs. Re-established at unit cost per cursor step (AscendToParent/DescendToChild), so cursor motion of length m costs O(m). Avoids maintaining every node’s graphs (which an edit could invalidate arbitrarily far away).
Generalization to a region R (S5.5, p467). For multi-node restructurings, seed M with D(R) ∪ root(R).C̄ ∪ {frontier subordinate graphs} and NeedToBeEvaluated with all of R. Drops both the single-edit and the normal-form restrictions.
Demand attributes = pull-based laziness (S6.2, p469-470). Attributes unobservable right after an edit are recomputed only on demand (query / display / a regular attribute needing the value); a demanded attribute that lost an argument is nulled and lazily recomputed (DEMANDVALUE, Alg 5, p470). The reverse-edge depth-first endorder evaluator — the demand-driven dual of topological push.
Copy-rule (identity-function) optimization (S6.1, p468-469). Skip equality tests down an identity chain once its head changes (most semantic functions are identities [40]); valid except inside the modified region R, where copy-rule attributes must be tested individually.
Sharable structures for large attributes (S6.3, p471-472). Indirection + structure sharing so identical/near-identical attribute values share storage; sharable 2-3 trees give O(log n) set ops with O(log n) extra nodes per update vs. O(n) for linked lists.
Declarative AG vs. imperative semantic actions (S7, p472-474). AG re-establishes consistency automatically with no explicit undo/retraction; semantic-action editors gain nonlocal-dependency shortcuts (skip large regions) but must hand-code order-independent retractions and cannot be made optimal by these methods in the presence of nonlocal deps (S7, p474).

Implementation Mapping

Current Usage in Gen Ecosystem

gen-rebuild (Foundational — the theorem that grounds `dirtySet` minimality and the topological eval-order seam)

gen-rebuild is the rebuilder of Mokhov 2018 — the component that, given a changed input over a dependency graph, decides the minimal set to recompute and reuses the rest. RTD-1983 is the foundational optimality result for exactly that decision in the static-tree, single-edit setting: it defines the minimal recompute set (AFFECTED), proves O(|AFFECTED|) is the lower bound, and exhibits an algorithm meeting it. Where Mokhov gives the taxonomy of rebuilders and Acar 2002 gives the change-propagation algorithm with a soundness proof, RTD gives the minimality theorem — the statement that the recompute set can be exactly the attributes whose values change, enumerated in topological order, at cost proportional to that set. The correspondence is direct:

D(T) = gen-rebuild’s dependency record. RTD’s attribute instance b = a (key, value) entry in gen-rebuild’s flat relocatable store; RTD’s edge (b', c') (“b' determines c'”) = a recorded dependency (source-key → consumer-key) tagged with the consumer’s semantic function / re-eval closure (S2, p452). This is the graph dirtySet/override/propagate walk.
AFFECTED = gen-rebuild’s dirtySet (minimal form). RTD’s AFFECTED = “the attribute instances that have different values” before vs. after updating (S4.3, p457) is precisely the minimal dirtySet: not the whole reverse-dependency cone, but the cone minus every node whose recomputed value is unchanged. RTD is the proof that this set is both the lower bound (O(|AFFECTED|) is the minimum possible work, S4.3, p457-458) and achievable (Algorithm 3-4 hit it, S5.2, p462-463). gen-rebuild’s “dirtySet = cone minus cutoffs” is RTD’s AFFECTED verbatim.
earlyCutoff = the unchanged-value cutoff (S4.1, p455). RTD’s rule “if reevaluating an attribute yields a value equal to its old value, changes need not be propagated further” is earlyCutoff in its original form: a recomputed-but-unchanged node does not enqueue its successors, so propagation is bounded to AFFECTED. (RTD’s NeedToBeEvaluated, S5.3, additionally suppresses evaluating nodes whose arguments never changed — a pre-cutoff complementary to the post-cutoff value compare.)
Seam S6 (eval order) = topological enumeration of AFFECTED (S4.3, p458; S5, p458-459). RTD is the reason the rebuild must respect evaluation order: reevaluating an attribute before its arguments are final propagates spurious changes “arbitrarily far beyond the boundaries of AFFECTED” (S4.3, p458), which is exactly the FIFO-quadratic / LIFO-exponential blowup of the Appendix (p474-475). The cure — “an attribute should not be reevaluated until all of its arguments are known to have their correct final values” ⇒ enumerate AFFECTED in topological order (S4.3, p458) — is the formal content of S6. PROPAGATE realizes it as a dynamic topological sort whose vertex set is generated as it is enumerated (S5, p458-459).
override / propagate = PROPAGATE over the model M. gen-rebuild’s override (recompute a changed key’s affected region) and its propagate/restabilize driver are RTD’s PROPAGATE (Algorithm 3-4, p462,465): seed M with the changed point’s characteristic graphs, drain the in-degree-zero work-list, and expand M by one production only when a new AFFECTED member is found (S5.2, p461-462). The guarantee |M| = O(|AFFECTED|) is the proof that override need never touch the unaffected store.
Characteristic graphs s.C / s.C̄ = transitive-dependency cutoff edges (S5.1, p459; S5.2, p463). These are what let PROPAGATE “skip, in unit time, arbitrarily large sections of D(T) in which values do not change” (S5.2, p463). For gen-rebuild they are the formal ground for summarized / transitive dependency edges that let dirtySet jump over unchanged subgraphs rather than walking them node-by-node — the difference between an O(|AFFECTED|) and an O(|reverse-cone|) dirty set.
restabilize = drive PROPAGATE to quiescence (S5.2, p462). restabilize runs incremental recomputation until the tree is consistent again; RTD’s PROPAGATE terminates exactly when the work-list S empties — “M consists of all attributes of all production instances in which an attribute has changed value” (S5.2, p462). Quiescence = re-stabilized.
support / why / affected provenance = D(T) reachability. RTD’s affected query = forward reachability from the changed point through D(T), pruned by the value cutoff (= AFFECTED); support/why = the argument (in-edge) instances a value depends on (S2, p452). D(T) is the provenance graph these read.

gen-scope (Seam provider — the demand-driven evaluator + the topological scheduler S6 assumes)

RTD presents both evaluation disciplines gen-scope embodies. The push discipline is the topological PROPAGATE (S5); the pull discipline is demand attributes (S6.2, p469-470) — “start from the vertices with no successors, reverse the edges, do depth-first endorder,” which is exactly Nix lazy thunk forcing / gen-scope’s self.get. RTD’s observation that the characteristic graphs are themselves graph-valued demand attributes linked to the cursor (S6.2, p469) prefigures gen-scope co-locating derived dependency metadata with the node. The S6 eval-order seam is RTD’s topological-enumeration requirement; gen-scope’s lazy evaluator supplies the demand-ordered variant, and the open question (shared with Acar/Hammer) is whether Nix’s native thunk order suffices or whether an explicit order-rank must be recorded.

gen-graph (Seam provider — `D(T)` and the projection/characteristic-graph operations)

RTD’s D(T) is a typed DAG; gen-graph provides the reachability affected/support/why read. RTD adds one structural operation beyond plain reachability: the projection A/V' = (V', E') where E' records a path in A between two V' vertices avoiding other V' vertices (S5.1, p459) — the operation that builds characteristic graphs. A faithful gen-graph would expose this transitive-projection (a quotient/contraction of the dependency graph onto a vertex subset) as a first-class query, since it is what makes the optimal bound reachable.

Relevance to gen-rebuild Op Surface

RTD concept	gen-rebuild realization
`AFFECTED` set (S4.3, p457)	`dirtySet` in its minimal form: reverse-cone minus unchanged-value nodes
`O(	AFFECTED
Unchanged-value cutoff (S4.1, p455)	`earlyCutoff` (post-recompute value compare; stop enqueueing successors)
`NeedToBeEvaluated` (S5.3, p465)	a pre-cutoff dual: skip recomputing nodes whose arguments never changed
Topological enumeration of `AFFECTED` (S4.3, p458)	seam S6 — recompute in dependency order so no node is ever assigned a non-final value
Dynamic topological sort / model `M` (S5, p459)	`override`/`propagate` engine; `M` grows one production per new `AFFECTED` member
Characteristic graphs `s.C`/`s.C̄` (S5.1, p459)	transitive cutoff edges that let `dirtySet` skip unchanged subgraphs in unit time
`PROPAGATE` to quiescence (S5.2, p462)	`restabilize` (drain frontier to fixed point)
Region `R` generalization (S5.5, p467)	`batch` / multi-key `applyDelta`: seed propagation from all initially-inconsistent keys
Copy-rule optimization (S6.1, p468)	identity-edge fast path: skip equality tests down a copy chain
Demand attributes (S6.2, p469)	the pull-based / lazy half (gen-scope `self.get`); dual to push `override`

The central lesson for gen-rebuild is that minimality is a theorem about a set, not a heuristic: the dirtySet is AFFECTED, the set of keys whose value actually changes, and it is achievable in O(|AFFECTED|) iff (a) recomputation proceeds in topological order (S6) so no key is recomputed before its inputs are final, and (b) the unchanged-value cutoff (earlyCutoff) prunes the cone down to the truly-changed set. RTD proves these two ingredients are jointly necessary and sufficient for optimality in the static-tree single-edit case.

Appendix: Follow-up Work

Unexploited Ideas

Transitive-dependency summary edges (characteristic graphs) for sub-cone dirtySet (S5.1-5.2, p459-463). gen-rebuild’s dirtySet as a plain reverse-dependency cone is O(|cone|), not O(|AFFECTED|). RTD’s characteristic graphs — transitive-dependency edges projected onto a region boundary — are precisely what let propagation skip unchanged subgraphs in unit time and never assign a non-final value. Implementing a summarized-edge layer (precomputed transitive deps across an unchanged subgraph, invalidated lazily relative to the change point as in the “prepared for propagation” invariant, S5.4) is the concrete route from a cone-sized dirty set to a minimal AFFECTED-sized one. This is RTD’s direct, un-exploited contribution beyond what Mokhov/Acar provide.
NeedToBeEvaluated as an explicit pre-cutoff op (S5.3, p465). earlyCutoff is a post-recompute value compare. RTD’s NeedToBeEvaluated is the complementary pre-recompute guard: a node enters the model but is not recomputed at all unless a predecessor actually changed value, eliminating the ≤2-3× redundant evaluations of bare topological enumeration. A needsEval predicate distinct from earlyCutoff would let gen-rebuild avoid expensive semantic-function calls, not just avoid propagating their results.
Explicit topological-order scheduling for override (S4.3, p458; S5, p459). RTD proves blind propagation order is quadratic/exponential and that topological order is mandatory for optimality. gen-rebuild’s S6 seam currently leans on Nix’s implicit thunk order; making the recompute order an explicit, RTD-justified dynamic topological sort (vertex set generated as enumerated) would give a provable O(|AFFECTED|) schedule rather than an order inherited accidentally from the evaluator.
The projection/contraction operation as a gen-graph primitive (S5.1, p459). A/V' — transitive paths between a vertex subset, contracting away the interior — is the operation that builds characteristic graphs and underlies the optimal bound. It is absent from the current graph surface, which has reachability but not transitive contraction onto a boundary.
Region-seeded propagation for batch deltas (S5.5, p467). RTD generalizes single-edit propagation to an arbitrary connected region R by seeding M with D(R) plus the frontier’s characteristic graphs. This is the exact recipe gen-rebuild’s batch/multi-key applyDelta should follow: compute the smallest connected region containing all changed keys, seed propagation there, and let one PROPAGATE drain it — rather than running per-key overrides that redundantly re-traverse shared downstream regions.

Potential New Libraries or Features

affected as a first-class, cutoff-pruned set op. RTD names AFFECTED as the object of interest and stresses it is discovered by the update, never precomputed (S4.3, p458). gen-rebuild could expose affected :: Store -> KeySet -> KeySet whose contract is “the keys whose value changes,” computed by running the cutoff-pruned propagation — distinguishing it sharply from the (cheap, over-approximate) reverse-cone. The two-tier distinction (approximate reachable cone vs. exact AFFECTED) is RTD’s, and making both explicit clarifies which queries are cheap-but-loose vs. exact-but-eager.
prepareAt / cursor-locality op (S5.4, p465-466). RTD maintains characteristic graphs only along the cursor path, re-established at unit cost per move. For gen-rebuild over a large fleet/config graph, a prepareAt key that materializes transitive cutoff edges only around an expected change locus — and tears them down on “cursor” move — would bound the bookkeeping (not just the recompute) to the working set, the dimension Mokhov’s taxonomy ignores.
Copy-rule / identity-edge fast path (S6.1, p468-469). RTD notes most semantic functions are identities [40] and that equality tests down an identity chain are skippable once the head changes (except inside the modified region). gen-rebuild could tag identity dependencies so earlyCutoff skips the equality test along a copy chain entirely — a cheap, high-frequency optimization with a precise correctness side-condition (test individually only within the modified region R).

Research Directions

Does O(|AFFECTED|) optimality survive a dynamic dependency graph? RTD’s theorem is for a static AG over a fixed tree with a single subtree replacement whose inconsistency is confined to one node (S3, p454; S4.1, p455). gen-rebuild’s graph is dynamic: dependencies are demand-discovered (Adapton), keys are allocated/relocated, and a change can alter the graph shape, not just attribute values. RTD’s confinement-to-r and its characteristic graphs both assume the dependency structure is known and stable around the edit. The open question: what is the minimal-recompute analogue of AFFECTED when an edit changes which edges exist, and is it still computable in time proportional to the changed set?
Topological order vs. cyclic / fixpoint attributes. RTD assumes a noncircular AG — D(T) acyclic for every tree (S2, p453) — which is what makes topological enumeration well-defined and guarantees an in-degree-zero start vertex exists (S5.1, p459). gen-rebuild must contend with cyclic/fixpoint computations (gen-derive fixpoints, gen-scope circular, converge loops). Topological order is undefined on a cycle; the O(|AFFECTED|) bound and the “never assign a non-final value” invariant both break. RTD offers no guidance here — the optimal-incremental theory for circular attribute grammars is a separate, harder problem, and gen-rebuild’s fixpoint ops are outside RTD’s transfer envelope.
Batch deltas vs. single-edit minimality. RTD’s optimal algorithm is per-edit (REPLACE updates after each subtree replacement, S3, p455); its region generalization (S5.5) handles a single arbitrary restructuring, not a sequence of independent deltas demanded together. For genuine batch incrementality — many input changes coalesced into one rebuild — the minimal recompute set is the union of per-change AFFECTEDs minus keys that change-then-change-back, which RTD does not characterize. (RTD explicitly defers updating “only after the whole sequence of structural modifications has been completed,” S5.5, p467, but does not give the optimal batch algorithm.)
Retraction without explicit undo (S7, p472-474). RTD’s headline advantage over the semantic-action approach is that deletion needs no hand-coded retraction — consistency is re-established automatically because attribute flow is purely along tree edges (S7, p473-474). But this is bought with the limitation that values “flow only along edges of the derivation tree,” so an AG evaluator must visit unchanged-but-on-path nodes that a nonlocal-dependency structure could skip (S7, p474). gen-rebuild’s flat relocatable store is closer to the semantic-action data structures (nonlocal edges) than to RTD’s tree — so it inherits the need to handle retraction explicitly (a deleted key’s reverse-cone must be invalidated) that RTD’s tree discipline avoided. RTD is the warning that nonlocal dependency shortcuts and automatic retraction are in tension: gen-rebuild has the former and must therefore engineer the latter (Acar’s obsolete-edge splice-out is the corresponding mechanism).
Demand-driven laziness vs. eager optimality (S6.2, p469-470). RTD’s optimal PROPAGATE is an eager push that keeps the whole tree consistent; its demand attributes are a separate, opt-in lazy mechanism for unobservable values. RTD does not prove O(|AFFECTED|) for the demand/lazy discipline — it gives demand attributes as a pragmatic deferral, not an optimality result. gen-rebuild’s native setting is lazy/pull (Nix, Adapton). Whether the AFFECTED-minimality theorem holds when recomputation is demand-ordered rather than topologically-pushed — i.e. whether “recompute only the demanded path” still achieves O(|AFFECTED ∩ demanded|) without the characteristic-graph cutoff edges that the push algorithm relies on — is unresolved by RTD and is the precise seam where its optimality assumptions stop transferring to gen-rebuild.

Palettes adapted from Catppuccin (Macchiato) (MIT), Tokyo Night (Apache-2.0), gruvbox (MIT), Catppuccin (Latte) (MIT), Rosé Pine (Dawn) (MIT).