04 - nodes can be immutable

Status: Accepted

Date: 2026-02-25

Authors:

  • jinmin.hu@capgemini.com
  • huub.joosten@capgemini.com
  • luna.li@capgemini.com
  • paul.nelissen@esi.nl
  • pierre.vandelaar@tno.nl

Table of contents

Context

The goal of this ADR is to define a controlled way to update AST nodes, so that the resulting AST is still correct.

The project models trees made of nodes. Currently, node data (properties and children) operations read the tree and transformations create new trees instead of mutating in-place. Ensuring immutability helps reasoning about transformations, enables safer concurrency, and opens opportunities for caching and memoization.

Decision

Nodes can be implemented as immutable objects. Once a node is created, its properties and children cannot be modified. Any change to a tree (for example, updating a property or replacing a child) will be done through a rewriter produce a new node valid rather than mutating the existing node in-place.

Implementation notes and recommendations for contributors:

  • Provide rewriter to create modified copies of nodes (for example, a replace, remove insert pattern that returns a new node with the requested changes).
  • When storing modifications, make sure the result is still correct and raise exception in case of unsolvable conflict.

Rationale

  • Predictability: Callers can rely on a node's properties remaining the same after construction, simplifying reasoning about passes and refactorings.
  • Concurrency: Immutable data structures are safe to share across threads without synchronization.
  • Caching & memoization: Since nodes don't change, caching derived information (like computed hashes, string representations, or analysis results) is reliable.
  • Correctness: Avoids accidental side effects caused by in-place modifications during complex refactorings.
    # no problem
    rewrite.replace(new_content, ast.child[1:3])    
    # can be a problem because the line number changed, but it is solvable
    rewrite.replace(new_content, ast.child[4:6])    

    # raise exception, because it is partly changed and not guaranteed the result is still syntactical correct
    rewrite.replace(new_content, ast.child[2:4])

Consequences

Positive:

  • Easier reasoning about code that manipulates trees.
  • Safer concurrent processing and simplified caching.
  • Fewer bugs due to unintended mutation.

Negative / trade-offs:

  • Potential performance overhead due to allocation when creating modified copies. Mitigations include structural sharing (reusing unchanged children) and keeping node representations compact.
  • Some algorithms that expect in-place updates will need to be adapted or re-implemented in an immutable style.
  • Developers must learn and follow patterns for producing modified copies (builders, copy_with helpers).

Alternatives considered

  1. Mutable nodes with defensive copies
  2. Keep nodes mutable but perform defensive copying when necessary.

  3. Rejected because it is easy to forget copies and still produce subtle bugs.

  4. Hybrid approach: mostly immutable, but allow controlled mutation through explicit APIs

  5. Provides flexibility but complicates invariants and testing; increases cognitive load.

  6. Fully persistent immutable data structures (e.g., ropes, HAMT, custom persistent vectors)

  7. Strong sharing and performance but larger implementation cost and complexity; deferred for future optimization if needed.
  • See ADR 01 (children and properties) and ADR 02 (direct access) for related design choices about tree shape and access patterns.

Revision history:

  • 2026-02-25: Draft; adds ADR template and implementation guidance.