sqry_db/queries/
condensation.rs

1//! Condensation DAG derived query.
2//!
3//! The condensation collapses each SCC into a single node, producing a DAG.
4//! This is used by `trace_path` for efficient path-finding through large
5//! call graphs.
6
7use std::collections::HashMap;
8use std::sync::Arc;
9
10use sqry_core::graph::unified::concurrent::GraphSnapshot;
11use sqry_core::graph::unified::edge::kind::EdgeKind;
12
13use crate::QueryDb;
14use crate::dependency::record_file_dep;
15use crate::queries::scc::SccQuery;
16use crate::query::DerivedQuery;
17
18// PN3 cold-start persistence: CachedCondensation is serialized via postcard at
19// cache-insert time. HashMap<u32, Vec<u32>> contains only primitive types.
20// EdgeKind already derives Serialize/Deserialize from sqry-core.
21
22/// Type alias for the key used by [`CondensationQuery`].
23/// Uses the same key type as [`SccQuery`] — the edge kind to condense over.
24/// `EdgeKind` already derives `Serialize`/`Deserialize` from sqry-core.
25pub type CondensationKey = EdgeKind;
26
27/// Type alias for the value produced by [`CondensationQuery`].
28/// `Arc` is serde-transparent when the workspace `serde` `rc` feature is enabled.
29pub type CondensationValue = std::sync::Arc<CachedCondensation>;
30
31/// Condensation of the call graph: DAG of SCC components.
32///
33/// Each SCC is collapsed to a single node. Edges between SCCs represent
34/// inter-component calls.
35// HashMap<u32, Vec<u32>>: primitive types, cleanly serde-able.
36#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
37pub struct CachedCondensation {
38    /// SCC component index → set of successor component indices.
39    pub dag_edges: HashMap<u32, Vec<u32>>,
40    /// Number of SCC components (= number of DAG nodes).
41    pub component_count: usize,
42    /// Edge kind this condensation was computed for.
43    pub edge_kind: EdgeKind,
44}
45
46/// Computes the condensation DAG from the SCC decomposition.
47///
48/// # Invalidation
49///
50/// `TRACKS_EDGE_REVISION = true`: invalidated when any edge changes.
51pub struct CondensationQuery;
52
53impl DerivedQuery for CondensationQuery {
54    type Key = EdgeKind;
55    type Value = Arc<CachedCondensation>;
56    const QUERY_TYPE_ID: u32 = crate::queries::type_ids::CONDENSATION;
57    const TRACKS_EDGE_REVISION: bool = true;
58
59    fn execute(key: &EdgeKind, db: &QueryDb, snapshot: &GraphSnapshot) -> Arc<CachedCondensation> {
60        // Record all files as deps
61        for (fid, _seg) in snapshot.file_segments().iter() {
62            record_file_dep(fid);
63        }
64
65        // Get the cached SCC data (or compute it)
66        let scc = db.get::<SccQuery>(key);
67
68        // Build the condensation DAG: for each edge in the original graph,
69        // if source and target are in different SCCs, add a DAG edge.
70        let mut dag_edges: HashMap<u32, Vec<u32>> = HashMap::new();
71
72        for (nid, entry) in snapshot.nodes().iter() {
73            // Gate 0d iter-2 fix: skip unified losers from
74            // condensation DAG. SccQuery already filters them, so
75            // `component_of` would return None for a loser, but the
76            // explicit guard is belt-and-braces. See
77            // `NodeEntry::is_unified_loser`.
78            if entry.is_unified_loser() {
79                continue;
80            }
81            let src_comp = match scc.component_of(nid) {
82                Some(c) => c,
83                None => continue,
84            };
85
86            for edge_ref in &snapshot.edges().edges_from(nid) {
87                if std::mem::discriminant(&edge_ref.kind) != std::mem::discriminant(key) {
88                    continue;
89                }
90                if let Some(tgt_comp) = scc.component_of(edge_ref.target)
91                    && src_comp != tgt_comp
92                {
93                    dag_edges.entry(src_comp).or_default().push(tgt_comp);
94                }
95            }
96        }
97
98        // Deduplicate DAG edges
99        for successors in dag_edges.values_mut() {
100            successors.sort_unstable();
101            successors.dedup();
102        }
103
104        Arc::new(CachedCondensation {
105            component_count: scc.component_count(),
106            dag_edges,
107            edge_kind: key.clone(),
108        })
109    }
110}
111
112// ============================================================================
113// PN3 serde roundtrip tests
114// ============================================================================
115
116#[cfg(test)]
117mod serde_roundtrip {
118    use super::*;
119    use postcard::{from_bytes, to_allocvec};
120
121    #[test]
122    fn cached_condensation_roundtrip() {
123        let mut dag_edges: HashMap<u32, Vec<u32>> = HashMap::new();
124        dag_edges.insert(0, vec![1, 2]);
125        dag_edges.insert(1, vec![3]);
126        let original = CachedCondensation {
127            dag_edges,
128            component_count: 4,
129            edge_kind: EdgeKind::Calls {
130                argument_count: 0,
131                is_async: false,
132            },
133        };
134        let bytes = to_allocvec(&original).expect("serialize failed");
135        let decoded: CachedCondensation = from_bytes(&bytes).expect("deserialize failed");
136        assert_eq!(decoded.component_count, original.component_count);
137        assert_eq!(decoded.edge_kind, original.edge_kind);
138        // dag_edges: verify contents match (HashMap order may differ).
139        assert_eq!(decoded.dag_edges.len(), original.dag_edges.len());
140        for (k, v) in &original.dag_edges {
141            assert_eq!(decoded.dag_edges.get(k), Some(v));
142        }
143    }
144
145    #[test]
146    fn condensation_key_roundtrip() {
147        // CondensationKey = EdgeKind
148        let original: CondensationKey = EdgeKind::Calls {
149            argument_count: 3,
150            is_async: true,
151        };
152        let bytes = to_allocvec(&original).expect("serialize failed");
153        let decoded: CondensationKey = from_bytes(&bytes).expect("deserialize failed");
154        assert_eq!(decoded, original);
155    }
156
157    #[test]
158    fn condensation_value_roundtrip() {
159        // CondensationValue = Arc<CachedCondensation>
160        let original: CondensationValue = Arc::new(CachedCondensation {
161            dag_edges: HashMap::new(),
162            component_count: 0,
163            edge_kind: EdgeKind::References,
164        });
165        let bytes = to_allocvec(&original).expect("serialize failed");
166        let decoded: CondensationValue = from_bytes(&bytes).expect("deserialize failed");
167        assert_eq!(decoded.component_count, original.component_count);
168        assert_eq!(decoded.edge_kind, original.edge_kind);
169    }
170}
sqry_db/queries/condensation.rs

sqry_db/queries/
condensation.rs
