meta_ast/graph/
edge.rs

1//! Edge types for the dependency graph.
2//!
3//! Defines the semantic relationships between nodes in the code graph.
4//! Edges are directed and carry metadata about the relationship type
5//! and confidence level.
6//!
7//! ## Design: uni-directional edges
8//!
9//! All edges are directed. There is no bidirectional or monitor/link
10//! pattern - an edge from A to B means A depends on B, not that B will
11//! be notified of A's failure. Shared-fate semantics (failure propagation)
12//! are a separate, optional annotation that the deploy layer may add
13//! during cut-edge RPC conversion. This follows the principle from
14//! *A Unified Semantics for Future Erlang* §2.2/§6.2: bidirectional links
15//! are replaced by uni-directional links plus monitors, and supervision
16//! trees can be built from uni-directional links alone.
17
18/// Semantic kind of a directed edge in the code graph.
19#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, serde::Serialize)]
20#[non_exhaustive]
21pub enum EdgeKind {
22    /// Ownership edge: File owns/contains a symbol.
23    Ownership,
24
25    /// Import edge: File imports/depends on another file.
26    Import,
27
28    /// Reference edge: Symbol references/uses another symbol.
29    Reference,
30
31    /// Flow edge: DataNode def-use or dataflow relationship.
32    Flow,
33}
34
35/// Confidence ladder for scope-resolved edges.
36///
37/// Own file and direct same-language imports score 1.0. Transitive
38/// same-language imports decay to 0.8. Cross-language imports score 0.6.
39pub const CONFIDENCE_OWN_OR_DIRECT: f32 = 1.0;
40/// Transitive same-language import.
41pub const CONFIDENCE_TRANSITIVE: f32 = 0.8;
42/// Cross-language import.
43pub const CONFIDENCE_CROSS_LANGUAGE: f32 = 0.6;
44
45/// Confidence ladder for MetaCall client-call edges.
46///
47/// Unique load-confirmed calls score 1.0. Multiple load-confirmed calls
48/// score 0.8. Unique global matches score 0.6. Multiple global matches
49/// score 0.5. Computed names cap at 0.4.
50pub const CONFIDENCE_CLIENT_UNIQUE_LOAD: f32 = 1.0;
51/// Multiple load-confirmed candidates.
52pub const CONFIDENCE_CLIENT_MULTI_LOAD: f32 = 0.8;
53/// Unique global fallback match.
54pub const CONFIDENCE_CLIENT_UNIQUE_GLOBAL: f32 = 0.6;
55/// Multiple global fallback matches.
56pub const CONFIDENCE_CLIENT_MULTI_GLOBAL: f32 = 0.5;
57/// Computed function, tag, or script name.
58pub const CONFIDENCE_COMPUTED: f32 = 0.4;
59
60/// Dataflow def-use edge confidence.
61pub const CONFIDENCE_DEF_USE: f32 = 0.9;
62
63/// Coarse class of a confidence value. Exact ladder matching, no interpolation.
64#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
65pub enum ConfidenceTier {
66    /// Own file, or a direct same-language import, or a unique load-confirmed
67    /// call.
68    OwnOrDirect,
69    /// Definition-use edge.
70    DefUse,
71    /// Transitive same-language import, or multiple load-confirmed calls.
72    Transitive,
73    /// Cross-language import, or a unique global call match.
74    CrossLanguage,
75    /// Multiple global call candidates.
76    ClientMultiGlobal,
77    /// Computed call name.
78    Computed,
79    /// Not one of the ladder values.
80    Unknown,
81}
82
83/// Classify a confidence value by exact equality with the ladder constants.
84///
85/// A value the ladder does not define is [`ConfidenceTier::Unknown`], so a
86/// consumer decides how to present it instead of letting it fall between two
87/// tiers.
88pub fn confidence_tier(confidence: f32) -> ConfidenceTier {
89    if confidence == CONFIDENCE_OWN_OR_DIRECT || confidence == CONFIDENCE_CLIENT_UNIQUE_LOAD {
90        ConfidenceTier::OwnOrDirect
91    } else if confidence == CONFIDENCE_DEF_USE {
92        ConfidenceTier::DefUse
93    } else if confidence == CONFIDENCE_TRANSITIVE || confidence == CONFIDENCE_CLIENT_MULTI_LOAD {
94        ConfidenceTier::Transitive
95    } else if confidence == CONFIDENCE_CROSS_LANGUAGE
96        || confidence == CONFIDENCE_CLIENT_UNIQUE_GLOBAL
97    {
98        ConfidenceTier::CrossLanguage
99    } else if confidence == CONFIDENCE_CLIENT_MULTI_GLOBAL {
100        ConfidenceTier::ClientMultiGlobal
101    } else if confidence == CONFIDENCE_COMPUTED {
102        ConfidenceTier::Computed
103    } else {
104        ConfidenceTier::Unknown
105    }
106}
107
108impl EdgeKind {
109    /// Returns true if this edge kind participates in SCC computation.
110    pub fn participates_in_scc(self) -> bool {
111        matches!(self, EdgeKind::Import | EdgeKind::Reference)
112    }
113
114    /// Returns true if this edge represents a cross-file dependency.
115    pub fn is_cross_file(self) -> bool {
116        matches!(self, EdgeKind::Import)
117    }
118
119    /// Returns the human-readable name of this edge kind.
120    pub const fn as_str(self) -> &'static str {
121        match self {
122            EdgeKind::Ownership => "ownership",
123            EdgeKind::Import => "import",
124            EdgeKind::Reference => "reference",
125            EdgeKind::Flow => "flow",
126        }
127    }
128}
129
130impl std::fmt::Display for EdgeKind {
131    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
132        write!(f, "{}", self.as_str())
133    }
134}
135
136/// Data stored for each edge in the graph.
137#[derive(Debug, Clone, Copy, serde::Serialize)]
138pub struct EdgeData {
139    /// Semantic kind of the relationship.
140    pub kind: EdgeKind,
141
142    /// Confidence level for the edge resolution.
143    /// Used for cross-language and best-effort resolution.
144    pub confidence: f32,
145
146    /// Flow kind for dataflow edges (None for non-Flow edges).
147    pub flow_kind: Option<crate::model::FlowKind>,
148}
149
150impl EdgeData {
151    /// Creates a new edge with full confidence (1.0) and no flow kind.
152    pub fn new(kind: EdgeKind) -> Self {
153        Self {
154            kind,
155            confidence: 1.0,
156            flow_kind: None,
157        }
158    }
159
160    /// Creates a new edge with specified confidence and no flow kind.
161    pub fn with_confidence(kind: EdgeKind, confidence: f32) -> Self {
162        Self {
163            kind,
164            confidence: confidence.clamp(0.0, 1.0),
165            flow_kind: None,
166        }
167    }
168
169    /// Creates a Flow edge with a flow kind and confidence.
170    pub fn flow(flow_kind: crate::model::FlowKind, confidence: f32) -> Self {
171        Self {
172            kind: EdgeKind::Flow,
173            confidence: confidence.clamp(0.0, 1.0),
174            flow_kind: Some(flow_kind),
175        }
176    }
177
178    pub fn participates_in_scc(&self) -> bool {
179        self.kind.participates_in_scc()
180    }
181
182    /// Merges a repeated `(source, target, kind)` edge into this one.
183    ///
184    /// The stronger confidence wins and the first flow kind is kept. This is
185    /// the only copy of the rule; every writer calls it.
186    pub(crate) fn merge_repeated(
187        &mut self,
188        confidence: f32,
189        flow_kind: Option<crate::model::FlowKind>,
190    ) {
191        self.confidence = self.confidence.max(confidence.clamp(0.0, 1.0));
192        if self.flow_kind.is_none() {
193            self.flow_kind = flow_kind;
194        }
195    }
196}
197
198impl Default for EdgeData {
199    fn default() -> Self {
200        Self::new(EdgeKind::Reference)
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::*;
207
208    #[test]
209    fn edge_kind_scc_participation() {
210        assert!(!EdgeKind::Ownership.participates_in_scc());
211        assert!(EdgeKind::Import.participates_in_scc());
212        assert!(EdgeKind::Reference.participates_in_scc());
213    }
214
215    #[test]
216    fn edge_kind_as_str() {
217        assert_eq!(EdgeKind::Ownership.as_str(), "ownership");
218        assert_eq!(EdgeKind::Import.as_str(), "import");
219        assert_eq!(EdgeKind::Reference.as_str(), "reference");
220        assert_eq!(EdgeKind::Flow.as_str(), "flow");
221    }
222
223    #[test]
224    fn flow_edge_excluded_from_scc() {
225        assert!(!EdgeKind::Flow.participates_in_scc());
226    }
227
228    #[test]
229    fn flow_edge_not_cross_file() {
230        assert!(!EdgeKind::Flow.is_cross_file());
231    }
232
233    #[test]
234    fn edge_kind_display() {
235        assert_eq!(format!("{}", EdgeKind::Import), "import");
236    }
237
238    #[test]
239    fn edge_data_new_defaults_to_full_confidence() {
240        let edge = EdgeData::new(EdgeKind::Import);
241        assert_eq!(edge.kind, EdgeKind::Import);
242        assert_eq!(edge.confidence, 1.0);
243        assert!(edge.participates_in_scc());
244    }
245
246    #[test]
247    fn edge_data_with_confidence_clamps() {
248        let low = EdgeData::with_confidence(EdgeKind::Reference, -0.5);
249        assert_eq!(low.confidence, 0.0);
250
251        let high = EdgeData::with_confidence(EdgeKind::Reference, 1.5);
252        assert_eq!(high.confidence, 1.0);
253
254        let mid = EdgeData::with_confidence(EdgeKind::Reference, 0.75);
255        assert_eq!(mid.confidence, 0.75);
256    }
257
258    #[test]
259    fn edge_data_default() {
260        let edge: EdgeData = Default::default();
261        assert_eq!(edge.confidence, 1.0);
262        assert!(edge.participates_in_scc());
263    }
264
265    #[test]
266    fn every_ladder_value_has_exactly_one_tier() {
267        for (confidence, tier) in [
268            (CONFIDENCE_OWN_OR_DIRECT, ConfidenceTier::OwnOrDirect),
269            (CONFIDENCE_CLIENT_UNIQUE_LOAD, ConfidenceTier::OwnOrDirect),
270            (CONFIDENCE_DEF_USE, ConfidenceTier::DefUse),
271            (CONFIDENCE_TRANSITIVE, ConfidenceTier::Transitive),
272            (CONFIDENCE_CLIENT_MULTI_LOAD, ConfidenceTier::Transitive),
273            (CONFIDENCE_CROSS_LANGUAGE, ConfidenceTier::CrossLanguage),
274            (
275                CONFIDENCE_CLIENT_UNIQUE_GLOBAL,
276                ConfidenceTier::CrossLanguage,
277            ),
278            (
279                CONFIDENCE_CLIENT_MULTI_GLOBAL,
280                ConfidenceTier::ClientMultiGlobal,
281            ),
282            (CONFIDENCE_COMPUTED, ConfidenceTier::Computed),
283        ] {
284            assert_eq!(confidence_tier(confidence), tier, "at {confidence}");
285        }
286    }
287
288    #[test]
289    fn a_value_between_ladder_steps_is_unknown() {
290        for confidence in [0.7, 0.0, 1.5, -1.0] {
291            assert_eq!(
292                confidence_tier(confidence),
293                ConfidenceTier::Unknown,
294                "at {confidence}"
295            );
296        }
297    }
298}
meta_ast/graph/edge.rs

meta_ast/graph/
edge.rs
