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

lean_ctx/core/property_graph/
queries.rs
