Struct DependencyGraph 

pub struct DependencyGraph { /* private fields */ }

The dependency graph of a Workbook: precedents and reverse-edge indexes derived from every formula cell via extract_refs.

Built with DependencyGraph::build; queried with precedents_of, direct_dependents_of, topological_order, and cycle_cells. A traversal that walks precedents transitively also wants formula_precedent_cells (what to walk next) and name_target_of (what a name currently points at). It is a pure derived view — it borrows nothing from the workbook after build returns and holds no values.

Rebuild rules (issue #534, “Rebuild rules on set/clear/rename”): the graph is a function of the workbook’s formulas, sheet names, and named-range targets, so any edit that changes those — set/clear of a formula cell, a sheet rename, a named-range retarget — invalidates it. The P3.4 mutation API rebuilds (or incrementally updates) the graph after such edits; the graph-rebuild equivalence tests assert that a from-scratch build after an arbitrary edit sequence equals the maintained graph.

Implementations

impl DependencyGraph

pub fn build(workbook: &Workbook) -> Self

Builds the dependency graph from workbook.

Walks every populated cell on every sheet; for each formula cell, parses the formula (flavor-independent, no engine needed — issue #900), extracts its refs (extract_refs), resolves each to a concrete node, and records both the forward precedent list and the reverse edges. Named-range targets are resolved up front so name indirection edges are available.

Resolution is total: an unresolvable reference becomes a Precedent::Unresolved rather than an error, so a workbook with a dangling Sheet9!A1 or an unknown name still builds (the recalc engine turns those into Sheets errors, fixture-verified in P3.3). Building therefore never fails.

pub fn precedents_of(&self, cell: &CellRef) -> Option<&[Precedent]>

The resolved precedents of cell in formula order, or None if cell is not a formula cell (a literal or an empty cell has no precedents).

pub fn is_formula(&self, cell: &CellRef) -> bool

Whether cell is a formula cell tracked by the graph.

pub fn formula_cells(&self) -> impl Iterator<Item = &CellRef>

Every formula cell in the graph, in canonical (sheet, address) order.

pub fn direct_dependents_of(&self, cell: &CellRef) -> BTreeSet<CellRef>

The formula cells that read cell directly — through a single-cell reference, through a range that contains cell, or through a named range whose target contains cell.

This is the dirty-propagation primitive the incremental recalc engine (P3.3) walks transitively: when cell changes, every cell returned here is dirty, and the walk repeats from each of them. It deliberately composes all three edge kinds so callers never reason about range-node compression or name indirection themselves.

Returned in canonical (sheet, address) order; the set is deduplicated even when a formula reaches cell by more than one path.

pub fn name_dependents_of(&self, name: &str) -> BTreeSet<CellRef>

The formula cells that depend on the named range name (any case), i.e. would be dirtied by retargeting it (P3.4).

Retargeting a name changes what its dependents read without changing their formulas, so the recalc engine dirties exactly this set (the name → target indirection promised by issue #534).

pub fn name_target_of(&self, name: &str) -> Option<NameTarget>

The current target of the named range name (any case): the cell or range its dependents actually read, or None when the name is not defined in this workbook or its reference does not resolve.

The forward half of the name → target indirection whose reverse half is name_dependents_of. A caller walking a formula’s precedents needs it to report what a Precedent::Name actually points at; NameTarget is the two-variant type for exactly that answer, so the signature itself rules out a name or an unresolved reference coming back — no doc caveat required.

pub fn topological_order(&self) -> Result<Vec<CellRef>, BTreeSet<CellRef>>

A topological order of the formula cells: every cell appears after all the formula cells it (transitively) reads, so evaluating in this order visits each cell only once with its precedents already current.

Returns Ok(order) when the formula-cell subgraph is acyclic, or Err(cycle_cells) listing every formula cell that lies on a cycle (the set cycle_cells returns). Only edges between formula cells participate: a formula that reads a literal cell has nothing to wait for. This is the ordering primitive P3.3 evaluates in; the Sheets circular-dependency error semantics for the cells on a cycle are applied by the recalc engine (fixture-verified there), not here.

pub fn evaluation_order(&self) -> (Vec<CellRef>, BTreeSet<CellRef>)

The evaluation order and the cycle set together, from one pass over the formula-cell edges.

A recalculation needs both: the order to evaluate in, and the cells to mark with the circular-dependency error. Asking for them separately (cycle_cells then topological_order) derives the same formula-cell adjacency from the precedent lists twice and throws it away twice. This builds it once. Nothing is cached and nothing has to be invalidated; it is the same work, done once instead of twice.

The order is topological_order’s when the graph is acyclic (and the cycle set is then empty), and acyclic_order_excluding’s over the acyclic remainder when it is not.

pub fn acyclic_order_excluding(&self, cycle: &BTreeSet<CellRef>) -> Vec<CellRef>

A topological order over the formula cells not on a cycle, for the cyclic-graph case (P3.3): cells that do not transitively read the cycle still evaluate in dependency order; cells on or downstream of the cycle are omitted (the recalc engine gives them the circular error). When the graph is acyclic this equals topological_order.

cycle must be the cycle set returned by cycle_cells (passed in so the caller computes it once). The order is deterministic (canonical tie-breaking), matching topological_order’s discipline.

pub fn cycle_cells(&self) -> BTreeSet<CellRef>

Every formula cell that lies on a dependency cycle (a strongly connected component of size > 1, or a self-referential cell).

This is the set P3.3 marks with the Sheets circular-dependency error. Empty iff the formula-cell subgraph is acyclic. Computed independently of topological_order so it can be queried directly.

pub fn formula_precedent_cells(&self, prec: &Precedent) -> Vec<CellRef>

Maps a precedent to the formula cells it covers (its intersection with the graph’s formula-cell set), following name indirection. Literal and empty cells are not yielded — only edges between formula cells matter for ordering and cycles.

This is the “what do I walk next” primitive of a precedent traversal: a Precedent::Cell yields that cell iff it carries a formula, a Precedent::Range yields the formula cells inside it (range-node compression is expanded only here, never in the stored edges), a Precedent::Name yields the formula cells its current target covers, and a Precedent::Unresolved yields nothing. Returned in canonical (sheet, address) order.

Cost is O(1) for a cell precedent and, for a range or range-targeted name, O(formula cells on the rows the range spans) — the rows are indexed and only occupied rows are keyed, so neither the empty rows a tall reference spans nor the formula cells elsewhere in the workbook are visited (issue #908). Still an upper bound rather than a contract: callers should not rely on it staying this expensive or this cheap.

Trait Implementations

impl Clone for DependencyGraph

fn clone(&self) -> DependencyGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DependencyGraph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for DependencyGraph

fn eq(&self, other: &DependencyGraph) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for DependencyGraph