ripbi_core/graph/
reachability.rs

1//! Reachability: the two-pass traversal that separates live objects from dead.
2//!
3//! Two plain passes encode the relationship policy without any special-cased
4//! machinery (the policy itself is documented in [`super`]):
5//!
6//! 1. **Strong pass** — from the roots (report bindings and roles), over every
7//!    edge *except* relationship endpoints and the inactive-relationship
8//!    edges. Containment fires: a used column keeps its table alive, a used
9//!    table keeps its partitions and active relationships alive.
10//! 2. **Weak pass** — extends the strong set over every edge *except*
11//!    containment and the inactive-relationship edges. A live table pulls in
12//!    its relationships and both their key columns, but a key column that is
13//!    only alive this way can no longer keep its own table alive — so a table
14//!    referenced by nothing but a relationship is still reported unused. An
15//!    inactive relationship joins only through a live `USERELATIONSHIP`
16//!    reference (an ordinary Dax edge); its table references never confer
17//!    liveness, so an unactivated one is a finding.
18//!
19//! A consumer annotation therefore never lies: for any unused object, every
20//! referencing object is either itself unused, live only through a
21//! relationship endpoint (its `also_unused` flag is `false`), or the table of
22//! an inactive relationship the relationship cannot keep alive.
23
24use std::collections::HashSet;
25
26use super::{DependencyGraph, ObjectId, Provenance};
27
28/// The liveness verdict for one graph: the set of live objects.
29pub(super) struct Reachability {
30    live: HashSet<ObjectId>,
31}
32
33impl Reachability {
34    /// Runs both passes over the finished graph.
35    pub(super) fn compute(graph: &DependencyGraph) -> Self {
36        // Pass 1 reaches everything except relationship-endpoint targets; pass 2
37        // extends that set without letting containment fire again, so weakly
38        // alive key columns never drag their tables along — and inactive
39        // relationships never confer liveness at all.
40        let strong = graph.reach(graph.seed_indices(), Provenance::is_strong_pass_edge);
41        let live = graph.reach(strong.iter().copied(), Provenance::is_weak_pass_edge);
42        Self {
43            live: live
44                .into_iter()
45                .map(|idx| graph.object_at(idx).clone())
46                .collect(),
47        }
48    }
49
50    /// True when the object is live at all.
51    pub(super) fn is_live(&self, id: &ObjectId) -> bool {
52        self.live.contains(id)
53    }
54}
55
56/// One object reachability never reached — a `scan` finding.
57#[derive(Debug, Clone, PartialEq, Eq)]
58pub struct UnusedObject {
59    /// The unused object.
60    pub id: ObjectId,
61    /// Every graph edge pointing at it. Empty means nothing references the
62    /// object at all: the root cause of its dead chain, deletable outright.
63    pub used_by: Vec<UsedBy>,
64    /// The M expressions that name this object — its Power Query supply
65    /// chain, carried beside the graph because it is deliberately not edges.
66    /// Unloading the object cannot break these; removing it from the script
67    /// entirely means editing each of them. Non-empty only ever for columns.
68    pub named_by_m: Vec<ObjectId>,
69}
70
71/// One referencing object behind an [`UnusedObject`].
72#[derive(Debug, Clone, PartialEq, Eq)]
73pub struct UsedBy {
74    /// The referencing object.
75    pub id: ObjectId,
76    /// What kind of use the edge records.
77    pub provenance: Provenance,
78    /// True when the referencing object is itself unused — the "also unused"
79    /// of the `← only used by X (also unused)` annotation. False means the
80    /// referencing object is live but its use could not keep this one alive:
81    /// a key column kept alive only as an active relationship endpoint,
82    /// holding its table's only reference, or the live table of an inactive
83    /// relationship nothing activates.
84    pub also_unused: bool,
85}
ripbi_core/graph/reachability.rs

ripbi_core/graph/
reachability.rs
