core_api/repograph/
path.rs

1//! The walk between two nodes that no single rule explains.
2//!
3//! When nothing links two files directly, the useful answer is not "no" but
4//! "through here": the shortest chain of imports, calls, co-changes and
5//! mentions that reaches one from the other. Breadth-first, so the first path
6//! found is a shortest one, and bounded by hops so a question about two
7//! unrelated corners of a repository costs no more than a question about two
8//! neighbours.
9
10use crate::db::GraphDb;
11use crate::repograph::facts::neighbors;
12use crate::Direction;
13use core_storage::fs::Fs;
14use std::collections::{BTreeMap, BTreeSet, VecDeque};
15
16/// The edge types a path may be walked over, in the order the digests name
17/// them. Every one of them says one part of a repository depends on, changes
18/// with, or talks about another.
19pub const PATH_EDGES: [&str; 4] = ["IMPORTS", "CALLS", "CO_CHANGED", "MENTIONS"];
20
21/// Longest chain a `why` fallback will look for.
22pub const MAX_HOPS: usize = 6;
23
24/// The shortest chain of `edge_types` edges from `a` to `b`, as
25/// `(edge type, node reached)` hops — so a two-hop answer is
26/// `[(IMPORTS, x), (CO_CHANGED, b)]` and `a` is the caller's own starting
27/// point.
28///
29/// Edges are followed in both directions: `a` importing `x` and `x` importing
30/// `a` both say the two are connected, and a reader asking how two files relate
31/// does not care which way the arrow points. Empty when `a` and `b` are the
32/// same node, when either is unknown, or when no chain of at most `max_hops`
33/// reaches one from the other.
34///
35/// Deterministic: neighbours are visited in `(key, edge type)` order, so of
36/// several shortest paths the same one always comes back.
37#[must_use]
38pub fn shortest_path<F: Fs>(
39    db: &GraphDb<F>,
40    a: &str,
41    b: &str,
42    edge_types: &[&str],
43    max_hops: usize,
44) -> Vec<(String, String)> {
45    if a == b || max_hops == 0 || !db.has_node(a) || !db.has_node(b) {
46        return Vec::new();
47    }
48    // How each node was first reached: the edge walked and the node it came
49    // from. Filled in discovery order, which the sort below pins.
50    let mut came_from: BTreeMap<String, (String, String)> = BTreeMap::new();
51    let mut seen: BTreeSet<String> = [a.to_string()].into_iter().collect();
52    let mut queue: VecDeque<(String, usize)> = [(a.to_string(), 0)].into_iter().collect();
53
54    while let Some((node, depth)) = queue.pop_front() {
55        if depth == max_hops {
56            continue;
57        }
58        for (next, etype) in step(db, &node, edge_types) {
59            if !seen.insert(next.clone()) {
60                continue;
61            }
62            came_from.insert(next.clone(), (etype, node.clone()));
63            if next == b {
64                return unwind(&came_from, a, b);
65            }
66            queue.push_back((next, depth + 1));
67        }
68    }
69    Vec::new()
70}
71
72/// Every node one edge away from `node`, as `(neighbour, edge type)` sorted by
73/// neighbour and then edge type. A neighbour reachable over two edge types
74/// appears once, under the type that sorts first — the path prints one edge per
75/// hop, and this is which one it names.
76fn step<F: Fs>(db: &GraphDb<F>, node: &str, edge_types: &[&str]) -> Vec<(String, String)> {
77    let mut out: Vec<(String, String)> = Vec::new();
78    for etype in edge_types {
79        for dir in [Direction::Out, Direction::In] {
80            for nbr in neighbors(db, node, etype, dir) {
81                out.push((nbr, (*etype).to_string()));
82            }
83        }
84    }
85    out.sort();
86    out.dedup_by(|x, y| x.0 == y.0);
87    out
88}
89
90/// Walk the `came_from` chain back from `b` and hand it out forwards.
91fn unwind(
92    came_from: &BTreeMap<String, (String, String)>,
93    a: &str,
94    b: &str,
95) -> Vec<(String, String)> {
96    let mut hops: Vec<(String, String)> = Vec::new();
97    let mut node = b.to_string();
98    while node != a {
99        let Some((etype, prev)) = came_from.get(&node) else {
100            return Vec::new(); // unreachable: every seen node but `a` has one
101        };
102        hops.push((etype.clone(), node.clone()));
103        node = prev.clone();
104    }
105    hops.reverse();
106    hops
107}
core_api/repograph/path.rs

core_api/repograph/
path.rs
