Module dep_graph 

Dependency graph for incremental layout invalidation (bd-3p4y1.1).

Design

The dependency graph tracks which layout computations depend on which inputs. When an input changes (constraint, content, style, children), only the affected subtree is marked dirty and re-evaluated.

Data Structure: Per-Node Adjacency Lists

Each node stores fixed-size metadata (36 bytes) inline. Edges are stored in per-node Vec<NodeId> lists for both forward (deps) and reverse (dependents) directions, ensuring correct adjacency even when edges are added in arbitrary order.

Complexity

Operation	Time	Space
Create node	O(1) amort.	+36 bytes
Mark dirty	O(1)	—
Propagate dirty	O(k)	O(k) queue
Add dependency edge	O(V+E) cycle	+4 bytes/edge
Cycle detection	O(V + E)	O(V) coloring
Query dirty set	O(n) scan	—

Where k = dirty nodes + their transitive dependents, n = total nodes.

Memory: 40 bytes per node (struct only)

DepNode {
    generation: u32,       //  4 bytes — dirty-check generation
    dirty_gen: u32,        //  4 bytes — generation when last dirtied
    constraint_hash: u64,  //  8 bytes — detect constraint changes
    content_hash: u64,     //  8 bytes — detect content changes
    style_hash: u64,       //  8 bytes — detect style changes
    parent: u32,           //  4 bytes — parent NodeId (u32::MAX = none)
}                          // = 40 bytes (36 raw + 4 alignment padding)

Dirty Propagation

When a node is marked dirty, BFS traverses reverse edges (dependents) and marks each reachable node dirty. The dirty set is the transitive closure of the initially dirty nodes under the “depends-on” relation.

Cycle Detection

Layout cycles are bugs. The graph detects cycles on edge insertion using DFS reachability: before adding A → B, check that B cannot already reach A via existing edges. This is O(V + E) worst case but typically fast due to shallow widget trees.

Deterministic Traversal

Dirty nodes are visited in DFS pre-order (matching full layout traversal), ensuring bit-identical output regardless of whether the computation is incremental or full.

Structs

CycleError

Error returned when adding an edge would create a cycle.

DepGraph

Dependency graph for incremental layout invalidation.

NodeId

Lightweight handle into the dependency graph.

Enums

InputKind

Identifies which input domain changed on a node.