lean_ctx/core/property_graph/
queries.rs

1//! Graph traversal queries: dependents, dependencies, impact analysis,
2//! dependency chains (BFS-based shortest path).
3//!
4//! All traversal queries support multi-edge traversal: imports, calls,
5//! exports, type_ref, tested_by, and more. Edge kinds are weighted
6//! for impact scoring.
7
8use std::collections::{HashMap, HashSet, VecDeque};
9
10use rusqlite::{Connection, params};
11
12#[derive(Debug, Clone)]
13pub struct GraphQuery;
14
15#[derive(Debug, Clone)]
16pub struct ImpactResult {
17    pub root_file: String,
18    pub affected_files: Vec<String>,
19    pub max_depth_reached: usize,
20    pub edges_traversed: usize,
21}
22
23#[derive(Debug, Clone)]
24pub struct DependencyChain {
25    pub path: Vec<String>,
26    pub depth: usize,
27}
28
29/// Edge kinds considered structural (code connectivity).
30const STRUCTURAL_EDGE_KINDS: &str =
31    "'imports','calls','exports','type_ref','tested_by','module','cochange','sibling'";
32
33/// Weight multiplier per edge kind for impact scoring.
34pub fn edge_weight(kind: &str) -> f64 {
35    match kind {
36        "imports" => 1.0,
37        "calls" => 0.8,
38        "exports" => 0.7,
39        "module" => 0.6,
40        "type_ref" => 0.5,
41        "tested_by" => 0.4,
42        "cochange" => 0.35,
43        "defines" => 0.3,
44        "sibling" => 0.25,
45        "changed_in" => 0.2,
46        _ => 0.1,
47    }
48}
49
50/// Files that depend on `file_path` via structural edges (imports, calls, type_ref, etc.).
51pub(super) fn dependents(conn: &Connection, file_path: &str) -> anyhow::Result<Vec<String>> {
52    let sql = format!(
53        "SELECT DISTINCT n_src.file_path
54         FROM edges e
55         JOIN nodes n_src ON e.source_id = n_src.id
56         JOIN nodes n_tgt ON e.target_id = n_tgt.id
57         WHERE n_tgt.file_path = ?1
58           AND n_src.file_path != ?1
59           AND e.kind IN ({STRUCTURAL_EDGE_KINDS})"
60    );
61    let mut stmt = conn.prepare(&sql)?;
62
63    let mut results: Vec<String> = stmt
64        .query_map(params![file_path], |row| row.get(0))?
65        .filter_map(std::result::Result::ok)
66        .collect();
67
68    results.sort();
69    results.dedup();
70    Ok(results)
71}
72
73/// Files that `file_path` depends on via structural edges.
74pub(super) fn dependencies(conn: &Connection, file_path: &str) -> anyhow::Result<Vec<String>> {
75    let sql = format!(
76        "SELECT DISTINCT n_tgt.file_path
77         FROM edges e
78         JOIN nodes n_src ON e.source_id = n_src.id
79         JOIN nodes n_tgt ON e.target_id = n_tgt.id
80         WHERE n_src.file_path = ?1
81           AND n_tgt.file_path != ?1
82           AND e.kind IN ({STRUCTURAL_EDGE_KINDS})"
83    );
84    let mut stmt = conn.prepare(&sql)?;
85
86    let mut results: Vec<String> = stmt
87        .query_map(params![file_path], |row| row.get(0))?
88        .filter_map(std::result::Result::ok)
89        .collect();
90
91    results.sort();
92    results.dedup();
93    Ok(results)
94}
95
96/// Weighted BFS from `file_path` following reverse structural edges up to `max_depth`.
97/// Edge weights attenuate propagation: calls edges carry less impact than imports.
98/// Nodes only propagate when cumulative weight exceeds the threshold (0.1).
99pub(super) fn impact_analysis(
100    conn: &Connection,
101    file_path: &str,
102    max_depth: usize,
103) -> anyhow::Result<ImpactResult> {
104    // Graph node keys use canonical `/` separators (see the builder walk);
105    // accept native Windows input too.
106    let file_path = file_path.replace('\\', "/");
107    let file_path = file_path.as_str();
108    let reverse_graph = build_weighted_reverse_graph(conn)?;
109    const PROPAGATION_THRESHOLD: f64 = 0.1;
110
111    let mut visited: HashSet<String> = HashSet::new();
112    let mut queue: VecDeque<(String, usize, f64)> = VecDeque::new();
113    let mut max_depth_reached = 0;
114    let mut edges_traversed = 0;
115
116    visited.insert(file_path.to_string());
117    queue.push_back((file_path.to_string(), 0, 1.0));
118
119    while let Some((current, depth, weight)) = queue.pop_front() {
120        if depth >= max_depth {
121            continue;
122        }
123
124        if let Some(dependents) = reverse_graph.get(&current) {
125            for (dep, ew) in dependents {
126                edges_traversed += 1;
127                let propagated = weight * ew;
128                if propagated < PROPAGATION_THRESHOLD {
129                    continue;
130                }
131                if visited.insert(dep.clone()) {
132                    let new_depth = depth + 1;
133                    if new_depth > max_depth_reached {
134                        max_depth_reached = new_depth;
135                    }
136                    queue.push_back((dep.clone(), new_depth, propagated));
137                }
138            }
139        }
140    }
141
142    visited.remove(file_path);
143
144    Ok(ImpactResult {
145        root_file: file_path.to_string(),
146        affected_files: visited.into_iter().collect(),
147        max_depth_reached,
148        edges_traversed,
149    })
150}
151
152/// BFS shortest path from `from` to `to` following structural edges.
153pub(super) fn dependency_chain(
154    conn: &Connection,
155    from: &str,
156    to: &str,
157) -> anyhow::Result<Option<DependencyChain>> {
158    // Same canonicalization as `impact_analysis`.
159    let from = from.replace('\\', "/");
160    let to = to.replace('\\', "/");
161    let from = from.as_str();
162    let to = to.as_str();
163    let forward_graph = build_forward_graph(conn)?;
164
165    let mut visited: HashSet<String> = HashSet::new();
166    let mut parent: HashMap<String, String> = HashMap::new();
167    let mut queue: VecDeque<String> = VecDeque::new();
168
169    visited.insert(from.to_string());
170    queue.push_back(from.to_string());
171
172    while let Some(current) = queue.pop_front() {
173        if current == to {
174            let mut path = vec![to.to_string()];
175            let mut cursor = to.to_string();
176            while let Some(prev) = parent.get(&cursor) {
177                path.push(prev.clone());
178                cursor = prev.clone();
179            }
180            path.reverse();
181            let depth = path.len() - 1;
182            return Ok(Some(DependencyChain { path, depth }));
183        }
184
185        if let Some(deps) = forward_graph.get(&current) {
186            for dep in deps {
187                if visited.insert(dep.clone()) {
188                    parent.insert(dep.clone(), current.clone());
189                    queue.push_back(dep.clone());
190                }
191            }
192        }
193    }
194
195    Ok(None)
196}
197
198/// Related files for a given path: direct neighbors via any structural edge,
199/// sorted by edge weight (strongest relationship first). Returns (path, weight) pairs.
200pub fn related_files(
201    conn: &Connection,
202    file_path: &str,
203    limit: usize,
204) -> anyhow::Result<Vec<(String, f64)>> {
205    let sql = format!(
206        "SELECT n_other.file_path, e.kind
207         FROM edges e
208         JOIN nodes n_self ON (e.source_id = n_self.id OR e.target_id = n_self.id)
209         JOIN nodes n_other ON (
210             (e.source_id = n_other.id AND e.target_id = n_self.id)
211             OR (e.target_id = n_other.id AND e.source_id = n_self.id)
212         )
213         WHERE n_self.file_path = ?1
214           AND n_other.file_path != ?1
215           AND e.kind IN ({STRUCTURAL_EDGE_KINDS})"
216    );
217    let mut stmt = conn.prepare(&sql)?;
218
219    let mut scores: HashMap<String, f64> = HashMap::new();
220    let rows = stmt.query_map(params![file_path], |row| {
221        Ok((row.get::<_, String>(0)?, row.get::<_, String>(1)?))
222    })?;
223
224    for row in rows {
225        let (path, kind) = row?;
226        *scores.entry(path).or_default() += edge_weight(&kind);
227    }
228
229    let mut results: Vec<(String, f64)> = scores.into_iter().collect();
230    results.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
231    results.truncate(limit);
232    Ok(results)
233}
234
235/// Graph connectivity stats for a file: incoming/outgoing edge counts by kind.
236pub fn file_connectivity(
237    conn: &Connection,
238    file_path: &str,
239) -> anyhow::Result<HashMap<String, (usize, usize)>> {
240    let mut result: HashMap<String, (usize, usize)> = HashMap::new();
241
242    let mut stmt_out = conn.prepare(
243        "SELECT e.kind, COUNT(*)
244         FROM edges e JOIN nodes n ON e.source_id = n.id
245         WHERE n.file_path = ?1
246         GROUP BY e.kind",
247    )?;
248    let rows = stmt_out.query_map(params![file_path], |row| {
249        Ok((row.get::<_, String>(0)?, row.get::<_, i64>(1)?))
250    })?;
251    for row in rows {
252        let (kind, count) = row?;
253        result.entry(kind).or_insert((0, 0)).0 = count as usize;
254    }
255
256    let mut stmt_in = conn.prepare(
257        "SELECT e.kind, COUNT(*)
258         FROM edges e JOIN nodes n ON e.target_id = n.id
259         WHERE n.file_path = ?1
260         GROUP BY e.kind",
261    )?;
262    let rows = stmt_in.query_map(params![file_path], |row| {
263        Ok((row.get::<_, String>(0)?, row.get::<_, i64>(1)?))
264    })?;
265    for row in rows {
266        let (kind, count) = row?;
267        result.entry(kind).or_insert((0, 0)).1 = count as usize;
268    }
269
270    Ok(result)
271}
272
273fn build_weighted_reverse_graph(
274    conn: &Connection,
275) -> anyhow::Result<HashMap<String, Vec<(String, f64)>>> {
276    let sql = format!(
277        "SELECT n_tgt.file_path, n_src.file_path, e.kind
278         FROM edges e
279         JOIN nodes n_src ON e.source_id = n_src.id
280         JOIN nodes n_tgt ON e.target_id = n_tgt.id
281         WHERE e.kind IN ({STRUCTURAL_EDGE_KINDS})
282           AND n_src.file_path != n_tgt.file_path"
283    );
284    let mut stmt = conn.prepare(&sql)?;
285
286    let mut graph: HashMap<String, HashMap<String, f64>> = HashMap::new();
287    let rows = stmt.query_map([], |row| {
288        Ok((
289            row.get::<_, String>(0)?,
290            row.get::<_, String>(1)?,
291            row.get::<_, String>(2)?,
292        ))
293    })?;
294
295    for row in rows {
296        let (target, source, kind) = row?;
297        let w = edge_weight(&kind);
298        let entry = graph
299            .entry(target)
300            .or_default()
301            .entry(source)
302            .or_insert(0.0);
303        if w > *entry {
304            *entry = w;
305        }
306    }
307
308    Ok(graph
309        .into_iter()
310        .map(|(k, v)| (k, v.into_iter().collect()))
311        .collect())
312}
313
314fn build_forward_graph(conn: &Connection) -> anyhow::Result<HashMap<String, Vec<String>>> {
315    let sql = format!(
316        "SELECT DISTINCT n_src.file_path, n_tgt.file_path
317         FROM edges e
318         JOIN nodes n_src ON e.source_id = n_src.id
319         JOIN nodes n_tgt ON e.target_id = n_tgt.id
320         WHERE e.kind IN ({STRUCTURAL_EDGE_KINDS})
321           AND n_src.file_path != n_tgt.file_path"
322    );
323    let mut stmt = conn.prepare(&sql)?;
324
325    let mut graph: HashMap<String, Vec<String>> = HashMap::new();
326    let rows = stmt.query_map([], |row| {
327        Ok((row.get::<_, String>(0)?, row.get::<_, String>(1)?))
328    })?;
329
330    for row in rows {
331        let (source, target) = row?;
332        graph.entry(source).or_default().push(target);
333    }
334
335    for deps in graph.values_mut() {
336        deps.sort();
337        deps.dedup();
338    }
339    Ok(graph)
340}
lean_ctx/core/property_graph/queries.rs

lean_ctx/core/property_graph/
queries.rs
