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. Containment fires: a used column
8//!    keeps its table alive, a used table keeps its partitions and
9//!    relationships alive.
10//! 2. **Weak pass** — extends the strong set over every edge *except*
11//!    containment. A live table pulls in its relationships and both their key
12//!    columns, but a key column that is only alive this way can no longer keep
13//!    its own table alive — so a table referenced by nothing but a
14//!    relationship is still reported unused.
15//!
16//! A consumer annotation therefore never lies: for any unused object, every
17//! referencing object is either itself unused, or live only through a
18//! relationship endpoint (its `also_unused` flag is `false`).
19
20use std::collections::HashSet;
21
22use super::{DependencyGraph, ObjectId, Provenance};
23
24/// The liveness verdict for one graph: the set of live objects.
25pub(super) struct Reachability {
26    live: HashSet<ObjectId>,
27}
28
29impl Reachability {
30    /// Runs both passes over the finished graph.
31    pub(super) fn compute(graph: &DependencyGraph) -> Self {
32        // Pass 1 reaches everything except relationship-endpoint targets; pass 2
33        // extends that set without letting containment fire again, so weakly
34        // alive key columns never drag their tables along.
35        let strong = graph.reach(graph.seed_indices(), Provenance::is_strong_pass_edge);
36        let live = graph.reach(strong.iter().copied(), Provenance::is_weak_pass_edge);
37        Self {
38            live: live
39                .into_iter()
40                .map(|idx| graph.object_at(idx).clone())
41                .collect(),
42        }
43    }
44
45    /// True when the object is live at all.
46    pub(super) fn is_live(&self, id: &ObjectId) -> bool {
47        self.live.contains(id)
48    }
49}
50
51/// One object reachability never reached — a `scan` finding.
52#[derive(Debug, Clone, PartialEq, Eq)]
53pub struct UnusedObject {
54    /// The unused object.
55    pub id: ObjectId,
56    /// Every graph edge pointing at it. Empty means nothing references the
57    /// object at all: the root cause of its dead chain, deletable outright.
58    pub used_by: Vec<UsedBy>,
59}
60
61/// One referencing object behind an [`UnusedObject`].
62#[derive(Debug, Clone, PartialEq, Eq)]
63pub struct UsedBy {
64    /// The referencing object.
65    pub id: ObjectId,
66    /// What kind of use the edge records.
67    pub provenance: Provenance,
68    /// True when the referencing object is itself unused — the "also unused"
69    /// of the `← only used by X (also unused)` annotation. False means the
70    /// referencing object is live but its use could not keep this one alive:
71    /// a key column kept alive only as a relationship endpoint, holding its
72    /// table's only reference.
73    pub also_unused: bool,
74}
ripbi_core/graph/reachability.rs

ripbi_core/graph/
reachability.rs
