gonzalo_graph/
resolve.rs

1//! Best-effort name resolution over an assembled view (ticket G).
2//!
3//! The base graph is a **heuristic** call graph: references match a target by
4//! name, so `callers_of("foo")` returns callers of *any* `foo`. This layer
5//! resolves each reference to the specific defining path it most likely means,
6//! disambiguating same-named symbols across files:
7//!
8//! 1. **Local** — a definition of the name in the reference's own file wins.
9//! 2. **Unique global** — otherwise, the sole definition across the view.
10//! 3. **Ambiguous** — multiple definitions and none local: left unresolved.
11//! 4. **Unresolved** — no definition in the view (honest dangling, ADR 0012).
12//!
13//! Resolution is file-scoped (not yet import-aware); it is a pure function of a
14//! [`GraphStore`]'s query methods, so it works over any backend and adds no
15//! trait surface. Import-following resolution is a further step.
16
17use crate::{GraphStore, Located, RefKind, Reference};
18use serde::{Deserialize, Serialize};
19use std::collections::BTreeSet;
20
21/// How a reference was resolved to a definition.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum Resolution {
24    /// A definition of the name exists in the reference's own file.
25    Local,
26    /// The name is defined exactly once across the view.
27    UniqueGlobal,
28    /// Several definitions and none in the reference's file — not resolved.
29    Ambiguous,
30    /// A method call (`x.foo()`) whose receiver type is unknown, so no
31    /// definition in the view can be claimed even if exactly one exists.
32    ///
33    /// Distinct from [`Unresolved`](Resolution::Unresolved): definitions of the
34    /// name may well be present, but attributing the call to one of them would
35    /// assert a receiver type the graph does not know (#223).
36    ReceiverUnknown,
37    /// No definition of the name in the view — a dangling reference.
38    Unresolved,
39}
40
41/// A reference resolved (best-effort) to the path of the symbol it refers to.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct ResolvedReference {
44    /// The reference and the path it was found in.
45    pub reference: Located<Reference>,
46    /// The defining path this reference resolves to, or `None` when ambiguous
47    /// or unresolved.
48    pub target: Option<String>,
49    /// Why it resolved (or didn't).
50    pub resolution: Resolution,
51}
52
53/// Resolve every reference to `name` to a defining path (see the module docs
54/// for the strategy).
55pub fn resolve_references_to(store: &dyn GraphStore, name: &str) -> Vec<ResolvedReference> {
56    let def_paths: BTreeSet<String> = store
57        .definitions(name)
58        .into_iter()
59        .map(|d| d.path)
60        .collect();
61
62    store
63        .references_to(name)
64        .into_iter()
65        .map(|located| {
66            let (target, resolution) = if def_paths.contains(&located.path) {
67                // A definition in the caller's own file wins for either shape:
68                // `self.foo()` next to `fn foo` is the one thing about a
69                // receiver we can reasonably assume.
70                (Some(located.path.clone()), Resolution::Local)
71            } else if def_paths.is_empty() {
72                // Nothing of this name anywhere: "not in the view" is the more
73                // informative answer than "receiver unknown", and it is true
74                // whatever the call shape.
75                (None, Resolution::Unresolved)
76            } else if located.item.kind == RefKind::Method {
77                // `x.foo()` belongs to whatever `x` is. Measured on gonzalo,
78                // 294 of the 388 cross-file method calls that used to resolve
79                // `UniqueGlobal` pointed at a *different crate* — `push`,
80                // `filter`, `send`, `next` and friends, i.e. std methods
81                // attributed to a same-named project function (#223).
82                (None, Resolution::ReceiverUnknown)
83            } else if def_paths.len() == 1 {
84                (def_paths.iter().next().cloned(), Resolution::UniqueGlobal)
85            } else {
86                (None, Resolution::Ambiguous)
87            };
88            ResolvedReference {
89                reference: located,
90                target,
91                resolution,
92            }
93        })
94        .collect()
95}
96
97/// Enclosing functions that call the `name` **defined at `defining_path`** — the
98/// precision refinement of [`GraphStore::callers_of`], which returns callers of
99/// any same-named symbol. Sorted and deduped.
100pub fn resolved_callers_of(store: &dyn GraphStore, defining_path: &str, name: &str) -> Vec<String> {
101    let mut callers: Vec<String> = resolve_references_to(store, name)
102        .into_iter()
103        .filter(|r| r.target.as_deref() == Some(defining_path))
104        .filter_map(|r| r.reference.item.from)
105        .collect();
106    callers.sort();
107    callers.dedup();
108    callers
109}
110
111/// One symbol reached by an impact closure, identified by the path that defines
112/// it rather than by name alone.
113#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
114pub struct ImpactNode {
115    pub name: String,
116    /// The file defining this symbol. Two same-named symbols in different files
117    /// are different nodes — that distinction is the whole point (#207).
118    pub path: String,
119}
120
121/// The result of a resolution-gated impact walk.
122#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
123pub struct ImpactReport {
124    /// Symbols transitively affected, sorted, excluding the seed.
125    pub reached: Vec<ImpactNode>,
126    /// Call edges dropped because the name has several definitions and none is
127    /// local. Reported rather than hidden: silently truncating a closure is its
128    /// own kind of lie, and a non-zero count here means the true impact set may
129    /// be larger than `reached`.
130    pub ambiguous_edges: usize,
131    /// Call edges dropped because they are method calls on a receiver of unknown
132    /// type ([`Resolution::ReceiverUnknown`]). Counted separately from
133    /// `ambiguous_edges` because the cause differs: not "too many candidates"
134    /// but "cannot claim any candidate" (#223).
135    pub receiver_unknown_edges: usize,
136    /// Whether the walk stopped at `max_depth` with unexplored frontier left.
137    ///
138    /// This means "the set may be incomplete", not "more definitely exists":
139    /// a node reached on the last permitted level was never asked for its own
140    /// callers, so completeness cannot be claimed either way.
141    pub truncated: bool,
142}
143
144/// The transitive closure of callers of `name`, following only edges that
145/// resolve to a specific definition.
146///
147/// [`GraphStore::impact`](crate::GraphStore::impact) walks the name-matched
148/// graph, so one hop into a name with several unrelated definitions absorbs
149/// every subgraph sharing that identifier — on gonzalo itself a single seed
150/// reached a quarter of the repository (#207). This walk keys nodes on
151/// `(name, defining path)` and consults [`resolve_references_to`] for every
152/// edge, so an [`Ambiguous`](Resolution::Ambiguous) reference is counted and
153/// dropped instead of merging two graphs.
154///
155/// A caller's own path needs no resolution: the enclosing function of a call is
156/// by definition in the file containing that call, so each reached node gets an
157/// exact path.
158///
159/// This gates [`Ambiguous`](Resolution::Ambiguous) edges only. A name defined
160/// exactly once still resolves [`UniqueGlobal`](Resolution::UniqueGlobal) even
161/// when the call really meant a std or dependency method of the same name, which
162/// remains a source of false edges (#223).
163///
164/// `max_depth` bounds the walk (`None` = unbounded); an ambiguous seed is walked
165/// from each of its definitions, since the caller asked about all of them.
166pub fn resolved_impact(
167    store: &dyn GraphStore,
168    name: &str,
169    max_depth: Option<usize>,
170) -> ImpactReport {
171    let seeds: Vec<ImpactNode> = store
172        .definitions(name)
173        .into_iter()
174        .map(|d| ImpactNode {
175            name: name.to_string(),
176            path: d.path,
177        })
178        .collect();
179
180    let mut visited: BTreeSet<ImpactNode> = seeds.iter().cloned().collect();
181    let mut frontier: Vec<ImpactNode> = seeds.clone();
182    let mut report = ImpactReport::default();
183    let mut depth = 0usize;
184
185    while !frontier.is_empty() {
186        if max_depth.is_some_and(|max| depth >= max) {
187            report.truncated = true;
188            break;
189        }
190        depth += 1;
191
192        let mut next: Vec<ImpactNode> = Vec::new();
193        for node in &frontier {
194            for resolved in resolve_references_to(store, &node.name) {
195                match resolved.resolution {
196                    // Unattributable: report it, do not traverse it.
197                    Resolution::Ambiguous => report.ambiguous_edges += 1,
198                    Resolution::ReceiverUnknown => report.receiver_unknown_edges += 1,
199                    // Resolves elsewhere, or nowhere — not an edge into `node`.
200                    _ if resolved.target.as_deref() != Some(node.path.as_str()) => {}
201                    _ => {
202                        let Some(from) = resolved.reference.item.from else {
203                            continue; // a top-level reference has no caller
204                        };
205                        let caller = ImpactNode {
206                            name: from,
207                            path: resolved.reference.path,
208                        };
209                        if visited.insert(caller.clone()) {
210                            next.push(caller);
211                        }
212                    }
213                }
214            }
215        }
216        frontier = next;
217    }
218
219    for seed in &seeds {
220        visited.remove(seed);
221    }
222    report.reached = visited.into_iter().collect();
223    report
224}
225
226#[cfg(test)]
227mod tests {
228    use super::*;
229    use crate::{InMemoryGraphStore, build_rust};
230
231    fn view() -> InMemoryGraphStore {
232        let mut s = InMemoryGraphStore::new();
233        // Two files each define `foo` and call it locally.
234        s.insert(
235            "a.rs",
236            build_rust("fn foo() {}\nfn ca() { foo(); }\nfn only() {}"),
237        );
238        s.insert("b.rs", build_rust("fn foo() {}\nfn cb() { foo(); }"));
239        // A cross-file call to `only` (defined once, in a.rs).
240        s.insert("c.rs", build_rust("fn cc() { only(); }"));
241        // A call to `foo` from a file that does not define it (ambiguous).
242        s.insert("d.rs", build_rust("fn cd() { foo(); }"));
243        s
244    }
245
246    #[test]
247    fn local_definition_wins() {
248        let s = view();
249        let resolved = resolve_references_to(&s, "foo");
250        // ca -> a.rs's foo, cb -> b.rs's foo (each local).
251        let ca = resolved
252            .iter()
253            .find(|r| r.reference.item.from.as_deref() == Some("ca"))
254            .unwrap();
255        assert_eq!(ca.resolution, Resolution::Local);
256        assert_eq!(ca.target.as_deref(), Some("a.rs"));
257        let cb = resolved
258            .iter()
259            .find(|r| r.reference.item.from.as_deref() == Some("cb"))
260            .unwrap();
261        assert_eq!(cb.target.as_deref(), Some("b.rs"));
262    }
263
264    #[test]
265    fn unique_global_resolves() {
266        let s = view();
267        let resolved = resolve_references_to(&s, "only");
268        assert_eq!(resolved.len(), 1);
269        assert_eq!(resolved[0].resolution, Resolution::UniqueGlobal);
270        assert_eq!(resolved[0].target.as_deref(), Some("a.rs"));
271    }
272
273    #[test]
274    fn multiple_defs_without_a_local_are_ambiguous() {
275        let s = view();
276        let cd = resolve_references_to(&s, "foo")
277            .into_iter()
278            .find(|r| r.reference.item.from.as_deref() == Some("cd"))
279            .unwrap();
280        assert_eq!(cd.resolution, Resolution::Ambiguous);
281        assert_eq!(cd.target, None);
282    }
283
284    #[test]
285    fn missing_definition_is_unresolved() {
286        let s = view();
287        let mut s = s;
288        s.insert("e.rs", build_rust("fn ce() { ghost(); }"));
289        let resolved = resolve_references_to(&s, "ghost");
290        assert_eq!(resolved.len(), 1);
291        assert_eq!(resolved[0].resolution, Resolution::Unresolved);
292        assert_eq!(resolved[0].target, None);
293    }
294
295    // ---- method calls do not claim a same-named free function (#223) ------
296
297    /// The exact shape found in the wild: a std method (`Iterator::chain`)
298    /// called in one crate, and a same-named test fixture that is the view's
299    /// only definition of `chain`.
300    fn std_method_collision() -> InMemoryGraphStore {
301        let mut s = InMemoryGraphStore::new();
302        s.insert(
303            "crates/core/src/merge.rs",
304            build_rust("fn merge() { let _ = ours.keys().chain(theirs.keys()); }"),
305        );
306        s.insert(
307            "crates/graph/src/store.rs",
308            build_rust("fn chain() -> u8 { 0 }"),
309        );
310        s
311    }
312
313    #[test]
314    fn a_method_call_does_not_resolve_to_a_same_named_free_function() {
315        let s = std_method_collision();
316        let r = resolve_references_to(&s, "chain");
317        let call = r
318            .iter()
319            .find(|r| r.reference.path.contains("merge.rs"))
320            .expect("the .chain() call is recorded");
321        assert_eq!(call.resolution, Resolution::ReceiverUnknown);
322        assert_eq!(call.target, None, "must not claim the test fixture");
323    }
324
325    #[test]
326    fn the_collision_no_longer_bridges_the_impact_closure() {
327        // Before: `chain` resolved UniqueGlobal, so seeding at the fixture
328        // dragged `merge` — in a crate that cannot depend on this one — in.
329        let report = resolved_impact(&std_method_collision(), "chain", None);
330        assert!(
331            !names_of(&report).contains(&"merge"),
332            "must not cross into the other crate: {report:?}"
333        );
334        assert_eq!(report.receiver_unknown_edges, 1, "and must say so");
335    }
336
337    #[test]
338    fn a_free_call_still_resolves_unique_global() {
339        // The fix must not disarm ordinary resolution.
340        let mut s = InMemoryGraphStore::new();
341        s.insert("a.rs", build_rust("fn only() {}"));
342        s.insert("b.rs", build_rust("fn cb() { only(); }"));
343        let r = resolve_references_to(&s, "only");
344        assert_eq!(r[0].resolution, Resolution::UniqueGlobal);
345        assert_eq!(r[0].target.as_deref(), Some("a.rs"));
346    }
347
348    #[test]
349    fn a_method_call_still_resolves_locally() {
350        // `self.helper()` beside `fn helper` is the one receiver assumption
351        // worth making, so same-file method calls keep resolving.
352        let mut s = InMemoryGraphStore::new();
353        s.insert(
354            "a.rs",
355            build_rust("fn helper() {}\nfn caller() { self.helper(); }"),
356        );
357        let r = resolve_references_to(&s, "helper");
358        let call = r.iter().find(|r| r.reference.item.from.is_some()).unwrap();
359        assert_eq!(call.resolution, Resolution::Local);
360        assert_eq!(call.target.as_deref(), Some("a.rs"));
361    }
362
363    #[test]
364    fn a_path_call_is_not_treated_as_a_method_call() {
365        // `a::b::foo()` is a path, not a receiver — it stays resolvable.
366        let mut s = InMemoryGraphStore::new();
367        s.insert("a.rs", build_rust("fn parse() {}"));
368        s.insert("b.rs", build_rust("fn cb() { util::parse(); }"));
369        let r = resolve_references_to(&s, "parse");
370        let call = r.iter().find(|r| r.reference.path == "b.rs").unwrap();
371        assert_eq!(call.resolution, Resolution::UniqueGlobal);
372    }
373
374    #[test]
375    fn receiver_unknown_is_distinct_from_unresolved() {
376        // A name with no definition at all is still Unresolved — the two mean
377        // different things and must stay distinguishable.
378        let mut s = InMemoryGraphStore::new();
379        s.insert("a.rs", build_rust("fn c() { x.ghost(); }"));
380        let r = resolve_references_to(&s, "ghost");
381        assert_eq!(r[0].resolution, Resolution::Unresolved);
382    }
383
384    // ---- resolution-gated impact closure (#207) ---------------------------
385
386    /// Two unrelated subgraphs joined only by a shared name. `helper` is
387    /// defined in both crates; nothing else is shared. A name-matched closure
388    /// merges them, a resolved one must not.
389    fn bridged() -> InMemoryGraphStore {
390        let mut s = InMemoryGraphStore::new();
391        s.insert(
392            "a.rs",
393            build_rust(
394                "fn leaf_a() {}\n\
395                 fn helper() { leaf_a(); }\n\
396                 fn top_a() { helper(); }",
397            ),
398        );
399        s.insert(
400            "b.rs",
401            build_rust(
402                "fn leaf_b() {}\n\
403                 fn helper() { leaf_b(); }\n\
404                 fn top_b() { helper(); }",
405            ),
406        );
407        s
408    }
409
410    fn names_of(report: &ImpactReport) -> Vec<&str> {
411        report.reached.iter().map(|n| n.name.as_str()).collect()
412    }
413
414    #[test]
415    fn name_matched_impact_merges_the_two_subgraphs() {
416        // The defect, pinned: the heuristic closure from `leaf_a` reaches
417        // b.rs's `top_b`, which cannot call it.
418        let s = bridged();
419        assert!(s.impact("leaf_a").contains(&"top_b".to_string()));
420    }
421
422    #[test]
423    fn resolved_impact_does_not_cross_an_ambiguous_name() {
424        let s = bridged();
425        let report = resolved_impact(&s, "leaf_a", None);
426        assert!(names_of(&report).contains(&"helper"), "{report:?}");
427        assert!(names_of(&report).contains(&"top_a"), "{report:?}");
428        assert!(
429            !names_of(&report).contains(&"top_b"),
430            "must not reach the other subgraph: {report:?}"
431        );
432        assert!(!names_of(&report).contains(&"leaf_b"), "{report:?}");
433    }
434
435    #[test]
436    fn resolved_impact_carries_a_defining_path_for_every_node() {
437        let report = resolved_impact(&bridged(), "leaf_a", None);
438        assert!(!report.reached.is_empty());
439        assert!(
440            report.reached.iter().all(|n| n.path == "a.rs"),
441            "{report:?}"
442        );
443    }
444
445    #[test]
446    fn resolved_impact_excludes_the_seed() {
447        let report = resolved_impact(&bridged(), "leaf_a", None);
448        assert!(!names_of(&report).contains(&"leaf_a"));
449    }
450
451    #[test]
452    fn resolved_impact_counts_ambiguous_edges_it_declined_to_follow() {
453        // `helper` is called from top_a and top_b, each local to its own file,
454        // so those resolve. Add a third file calling `helper` with no local
455        // definition: that edge is genuinely ambiguous and must be reported,
456        // not silently dropped.
457        let mut s = bridged();
458        s.insert("c.rs", build_rust("fn outsider() { helper(); }"));
459        let report = resolved_impact(&s, "leaf_a", None);
460        assert!(
461            report.ambiguous_edges > 0,
462            "an unattributable edge must be reported: {report:?}"
463        );
464        assert!(
465            !names_of(&report).contains(&"outsider"),
466            "and must not be traversed: {report:?}"
467        );
468    }
469
470    #[test]
471    fn resolved_impact_reports_no_ambiguity_when_every_name_is_unique() {
472        let mut s = InMemoryGraphStore::new();
473        s.insert("a.rs", build_rust("fn leaf() {}\nfn mid() { leaf(); }"));
474        let report = resolved_impact(&s, "leaf", None);
475        assert_eq!(report.ambiguous_edges, 0);
476        assert_eq!(names_of(&report), vec!["mid"]);
477        assert!(!report.truncated);
478    }
479
480    #[test]
481    fn resolved_impact_survives_cycles() {
482        let mut s = InMemoryGraphStore::new();
483        s.insert("cyc.rs", build_rust("fn a() { b(); }\nfn b() { a(); }"));
484        let report = resolved_impact(&s, "a", None);
485        assert_eq!(names_of(&report), vec!["b"], "terminates, seed excluded");
486    }
487
488    #[test]
489    fn resolved_impact_respects_max_depth() {
490        let mut s = InMemoryGraphStore::new();
491        s.insert(
492            "a.rs",
493            build_rust("fn l() {}\nfn m() { l(); }\nfn t() { m(); }"),
494        );
495        let one = resolved_impact(&s, "l", Some(1));
496        assert_eq!(names_of(&one), vec!["m"], "one hop only");
497        assert!(one.truncated, "a capped walk must say so");
498
499        // `truncated` means "stopped with frontier left", not "more existed":
500        // at depth 2 the walk has reached `t` but never asked who calls it, so
501        // it cannot claim the set is complete.
502        let two = resolved_impact(&s, "l", Some(2));
503        assert_eq!(names_of(&two), vec!["m", "t"]);
504        assert!(two.truncated, "t was reached but never explored");
505
506        // Only an uncapped walk (or one that exhausts the graph inside the cap)
507        // can honestly report completeness.
508        let deep = resolved_impact(&s, "l", Some(9));
509        assert_eq!(names_of(&deep), vec!["m", "t"]);
510        assert!(!deep.truncated);
511        assert!(!resolved_impact(&s, "l", None).truncated);
512    }
513
514    #[test]
515    fn resolved_impact_on_an_undefined_name_is_empty() {
516        let report = resolved_impact(&bridged(), "ghost", None);
517        assert!(report.reached.is_empty());
518        assert_eq!(report.ambiguous_edges, 0);
519    }
520
521    #[test]
522    fn resolved_impact_walks_every_definition_of_an_ambiguous_seed() {
523        // Seeding on an ambiguous name is legitimate: the caller asked about
524        // "helper", and both are real. Each is walked from its own path.
525        let report = resolved_impact(&bridged(), "helper", None);
526        let mut pairs: Vec<(&str, &str)> = report
527            .reached
528            .iter()
529            .map(|n| (n.name.as_str(), n.path.as_str()))
530            .collect();
531        pairs.sort();
532        assert_eq!(pairs, vec![("top_a", "a.rs"), ("top_b", "b.rs")]);
533    }
534
535    #[test]
536    fn resolved_callers_disambiguates_by_defining_path() {
537        let s = view();
538        // The heuristic callers_of("foo") returns ca, cb (and cd via the ref).
539        assert!(s.callers_of("foo").contains(&"ca".to_string()));
540        assert!(s.callers_of("foo").contains(&"cb".to_string()));
541        // Resolution narrows to callers of the *specific* foo.
542        assert_eq!(
543            resolved_callers_of(&s, "a.rs", "foo"),
544            vec!["ca".to_string()]
545        );
546        assert_eq!(
547            resolved_callers_of(&s, "b.rs", "foo"),
548            vec!["cb".to_string()]
549        );
550    }
551}
gonzalo_graph/resolve.rs

gonzalo_graph/
resolve.rs
