plushie/tree

Tree operations: normalization, diffing, and search.

After view(model) produces a Node tree, normalize applies scoped IDs and resolves a11y references. After each update cycle, diff compares old and new normalized trees to produce PatchOp lists for the wire protocol.

Values

diff

</>

pub fn diff(
  old: node.Node,
  new: node.Node,
) -> List(patch.PatchOp)

Compare two normalized trees and return a list of patch operations that transform old into new.

Paths are lists of integer child indices from the root. For example, [0, 2] means “root’s first child, then that node’s third child”.

The algorithm uses O(n) set comparison for reorder detection rather than O(n^2) LCS. When children are reordered, the entire node is replaced rather than computing minimal moves – a deliberate simplicity-over-optimality tradeoff matching the reference implementation.

exists

</>

pub fn exists(tree: node.Node, id: String) -> Bool

Check whether a node with the given ID exists anywhere in the tree.

find

</>

pub fn find(
  tree: node.Node,
  id: String,
) -> option.Option(node.Node)

Find a node by its ID (depth-first). Returns the first match.

Matches against the full ID first. If no match is found and the target does not contain “/”, falls back to matching the local segment (the part after the last “/”) of each node’s ID.

find_all

</>

pub fn find_all(
  tree: node.Node,
  predicate: fn(node.Node) -> Bool,
) -> List(node.Node)

Collect all nodes matching a predicate (depth-first order).

ids

</>

pub fn ids(tree: node.Node) -> List(String)

Return all node IDs in depth-first order.

normalize

</>

pub fn normalize(node: node.Node) -> node.Node

Normalize a node tree by applying scoped IDs and resolving a11y references. Call this on the output of view(model) before diffing.

Scoping rules:

Named (non-empty-ID) non-window nodes create scope boundaries. Their children’s IDs become parent_id/child_id.
Window nodes reset scope – children start with no scope prefix.
Empty-ID nodes don’t create scope boundaries.