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. 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 with the workbook’s locked engine, 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 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 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.

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