aptu_coder_core/
graph.rs

1// SPDX-FileCopyrightText: 2026 aptu-coder contributors
2// SPDX-License-Identifier: Apache-2.0
3//! Call graph construction and analysis.
4//!
5//! Builds caller and callee relationships from semantic analysis results.
6//! Implements type-aware function matching to disambiguate overloads and name collisions.
7
8use crate::types::{CallEdge, ImplTraitInfo, SemanticAnalysis, SymbolMatchMode};
9use std::collections::{HashMap, HashSet, VecDeque};
10use std::path::{Path, PathBuf};
11use std::sync::Arc;
12use thiserror::Error;
13use tracing::{debug, instrument};
14
15const MAX_CANDIDATES_IN_ERROR: usize = 20;
16
17fn format_candidates(candidates: &[String]) -> String {
18    if candidates.len() <= MAX_CANDIDATES_IN_ERROR {
19        candidates.join(", ")
20    } else {
21        format!(
22            "{}, (and {} more)",
23            candidates[..MAX_CANDIDATES_IN_ERROR].join(", "),
24            candidates.len() - MAX_CANDIDATES_IN_ERROR
25        )
26    }
27}
28
29#[derive(Debug, Error)]
30#[non_exhaustive]
31pub enum GraphError {
32    #[error("Symbol not found: '{symbol}'. {hint}")]
33    SymbolNotFound { symbol: String, hint: String },
34    #[error(
35        "Multiple candidates matched '{query}': {candidates_display}. Use match_mode=exact to target one of the candidates listed above, or refine the symbol name.",
36        candidates_display = format_candidates(.candidates)
37    )]
38    MultipleCandidates {
39        query: String,
40        candidates: Vec<String>,
41    },
42}
43
44/// Resolve a symbol name against the set of known symbols using the requested match mode.
45///
46/// Returns:
47/// - `Ok(name)` when exactly one symbol matches.
48/// - `Err(GraphError::SymbolNotFound)` when no symbol matches.
49/// - `Err(GraphError::MultipleCandidates)` when more than one symbol matches.
50pub fn resolve_symbol<'a>(
51    known_symbols: impl Iterator<Item = &'a String>,
52    query: &str,
53    mode: &SymbolMatchMode,
54) -> Result<String, GraphError> {
55    let mut matches: Vec<String> = if matches!(mode, SymbolMatchMode::Exact) {
56        known_symbols
57            .filter(|s| s.as_str() == query)
58            .cloned()
59            .collect()
60    } else {
61        let query_lower = query.to_lowercase();
62        known_symbols
63            .filter(|s| match mode {
64                SymbolMatchMode::Exact => unreachable!(),
65                SymbolMatchMode::Insensitive => s.to_lowercase() == query_lower,
66                SymbolMatchMode::Prefix => s.to_lowercase().starts_with(&query_lower),
67                SymbolMatchMode::Contains => s.to_lowercase().contains(&query_lower),
68            })
69            .cloned()
70            .collect()
71    };
72    matches.sort();
73
74    debug!(
75        query,
76        mode = ?mode,
77        candidate_count = matches.len(),
78        "resolve_symbol"
79    );
80
81    match matches.len() {
82        1 => {
83            // SAFETY: match arm for `1` guarantees exactly one element in matches; next() cannot return None.
84            #[allow(clippy::expect_used)]
85            Ok(matches.into_iter().next().expect("len==1"))
86        }
87        0 => {
88            let hint = match mode {
89                SymbolMatchMode::Exact => {
90                    "Try match_mode=insensitive for a case-insensitive search, or match_mode=prefix to list symbols starting with this name.".to_string()
91                }
92                _ => "No symbols matched; try a shorter query or match_mode=contains.".to_string(),
93            };
94            Err(GraphError::SymbolNotFound {
95                symbol: query.to_string(),
96                hint,
97            })
98        }
99        _ => Err(GraphError::MultipleCandidates {
100            query: query.to_string(),
101            candidates: matches,
102        }),
103    }
104}
105
106/// Resolve a symbol using the `lowercase_index` for O(1) case-insensitive lookup.
107/// For other modes, iterates the `lowercase_index` keys to avoid per-symbol allocations.
108impl CallGraph {
109    pub fn resolve_symbol_indexed(
110        &self,
111        query: &str,
112        mode: &SymbolMatchMode,
113    ) -> Result<String, GraphError> {
114        // Fast path for exact, case-sensitive lookups: O(1) contains_key checks with no
115        // intermediate allocations.
116        if matches!(mode, SymbolMatchMode::Exact) {
117            if self.definitions.contains_key(query)
118                || self.callers.contains_key(query)
119                || self.callees.contains_key(query)
120            {
121                return Ok(query.to_string());
122            }
123            return Err(GraphError::SymbolNotFound {
124                symbol: query.to_string(),
125                hint: "Try match_mode=insensitive for a case-insensitive search, or match_mode=prefix to list symbols starting with this name.".to_string(),
126            });
127        }
128
129        let query_lower = query.to_lowercase();
130        let mut matches: Vec<String> = {
131            match mode {
132                SymbolMatchMode::Insensitive => {
133                    // O(1) lookup using lowercase_index
134                    if let Some(originals) = self.lowercase_index.get(&query_lower) {
135                        if originals.len() > 1 {
136                            // Multiple originals map to the same lowercase key; report all.
137                            return Err(GraphError::MultipleCandidates {
138                                query: query.to_string(),
139                                candidates: originals.clone(),
140                            });
141                        }
142                        // Exactly one original maps to this lowercase key; return it.
143                        vec![originals[0].clone()]
144                    } else {
145                        vec![]
146                    }
147                }
148                SymbolMatchMode::Prefix => {
149                    // Use .iter() to avoid redundant hash lookup.
150                    self.lowercase_index
151                        .iter()
152                        .filter(|(k, _)| k.starts_with(&query_lower))
153                        .flat_map(|(_, v)| v.iter().cloned())
154                        .collect()
155                }
156                SymbolMatchMode::Contains => {
157                    // Use .iter() to avoid redundant hash lookup.
158                    self.lowercase_index
159                        .iter()
160                        .filter(|(k, _)| k.contains(&query_lower))
161                        .flat_map(|(_, v)| v.iter().cloned())
162                        .collect()
163                }
164                SymbolMatchMode::Exact => unreachable!("handled above"),
165            }
166        };
167        matches.sort();
168        matches.dedup();
169
170        debug!(
171            query,
172            mode = ?mode,
173            candidate_count = matches.len(),
174            "resolve_symbol_indexed"
175        );
176
177        match matches.len() {
178            1 => {
179                // SAFETY: match arm for `1` guarantees exactly one element in matches; next() cannot return None.
180                #[allow(clippy::expect_used)]
181                Ok(matches.into_iter().next().expect("len==1"))
182            }
183            0 => Err(GraphError::SymbolNotFound {
184                symbol: query.to_string(),
185                hint: "No symbols matched; try a shorter query or match_mode=contains.".to_string(),
186            }),
187            _ => Err(GraphError::MultipleCandidates {
188                query: query.to_string(),
189                candidates: matches,
190            }),
191        }
192    }
193}
194
195/// Strip scope prefixes from a callee name.
196/// Handles patterns: `self.method` -> `method`, `Type::method` -> `method`, `module::function` -> `function`.
197/// If no prefix is found, returns the original name.
198fn strip_scope_prefix(name: &str) -> &str {
199    if let Some(pos) = name.rfind("::") {
200        &name[pos + 2..]
201    } else if let Some(pos) = name.rfind('.') {
202        &name[pos + 1..]
203    } else {
204        name
205    }
206}
207
208#[derive(Debug, Clone)]
209pub struct InternalCallChain {
210    pub chain: Vec<(String, PathBuf, usize)>,
211}
212
213/// Call graph storing callers, callees, and function definitions.
214#[derive(Debug, Clone)]
215#[non_exhaustive]
216pub struct CallGraph {
217    /// Callers map: `function_name` -> vec of `CallEdge` (one per call site).
218    pub callers: HashMap<String, Vec<CallEdge>>,
219    /// Callees map: `function_name` -> vec of `CallEdge` (one per call site).
220    pub callees: HashMap<String, Vec<CallEdge>>,
221    /// Definitions map: `function_name` -> vec of (`file_path`, `line_number`).
222    pub definitions: HashMap<String, Vec<(PathBuf, usize)>>,
223    /// Index for O(1) case-insensitive symbol lookup: lowercased -> vec of originals.
224    lowercase_index: HashMap<String, Vec<String>>,
225}
226
227impl CallGraph {
228    #[must_use]
229    pub fn new() -> Self {
230        Self {
231            callers: HashMap::new(),
232            callees: HashMap::new(),
233            definitions: HashMap::new(),
234            lowercase_index: HashMap::new(),
235        }
236    }
237
238    /// Resolve a callee name using two strategies:
239    /// 1. Try the raw callee name first in definitions; return it if found.
240    /// 2. Strip any scope prefix (e.g. `Foo::bar` → `bar`) and look up the stripped name; return it if found.
241    ///
242    /// If neither strategy finds a definition, returns the original callee unchanged.
243    ///
244    /// Returns the resolved callee name (which may be the stripped version).
245    fn resolve_callee(
246        callee: &str,
247        _call_file: &Path,
248        _call_line: usize,
249        _arg_count: Option<usize>,
250        definitions: &HashMap<String, Vec<(PathBuf, usize)>>,
251    ) -> String {
252        // Try raw callee name first
253        if let Some(_defs) = definitions.get(callee) {
254            return callee.to_string();
255        }
256
257        // Try stripped name
258        let stripped = strip_scope_prefix(callee);
259        if stripped != callee
260            && let Some(_defs) = definitions.get(stripped)
261        {
262            return stripped.to_string();
263        }
264
265        // No definition found; return the original callee
266        callee.to_string()
267    }
268
269    /// Build a call graph from semantic analysis results and trait implementation info.
270    #[instrument(skip_all)]
271    #[allow(clippy::too_many_lines)]
272    // exhaustive graph construction pass; splitting into subfunctions harms readability
273    // public API; callers expect owned semantics
274    #[allow(clippy::needless_pass_by_value)]
275    pub fn build_from_results(
276        results: Vec<(PathBuf, SemanticAnalysis)>,
277        impl_traits: &[ImplTraitInfo],
278        impl_only: bool,
279    ) -> Result<Self, GraphError> {
280        let mut graph = CallGraph::new();
281
282        // Build definitions map first
283        for (path, analysis) in &results {
284            for func in &analysis.functions {
285                graph
286                    .definitions
287                    .entry(func.name.clone())
288                    .or_default()
289                    .push((path.clone(), func.line));
290            }
291            for class in &analysis.classes {
292                graph
293                    .definitions
294                    .entry(class.name.clone())
295                    .or_default()
296                    .push((path.clone(), class.line));
297            }
298        }
299
300        // Process calls with resolved callee names
301        for (path, analysis) in &results {
302            for call in &analysis.calls {
303                let resolved_callee = Self::resolve_callee(
304                    &call.callee,
305                    path,
306                    call.line,
307                    call.arg_count,
308                    &graph.definitions,
309                );
310
311                graph
312                    .callees
313                    .entry(call.caller.clone())
314                    .or_default()
315                    .push(CallEdge {
316                        path: path.clone(),
317                        line: call.line,
318                        neighbor_name: resolved_callee.clone(),
319                        is_impl_trait: false,
320                    });
321                graph
322                    .callers
323                    .entry(resolved_callee)
324                    .or_default()
325                    .push(CallEdge {
326                        path: path.clone(),
327                        line: call.line,
328                        neighbor_name: call.caller.clone(),
329                        is_impl_trait: false,
330                    });
331            }
332            for reference in &analysis.references {
333                graph
334                    .callers
335                    .entry(reference.symbol.clone())
336                    .or_default()
337                    .push(CallEdge {
338                        path: path.clone(),
339                        line: reference.line,
340                        neighbor_name: "<reference>".to_string(),
341                        is_impl_trait: false,
342                    });
343            }
344        }
345
346        // Add explicit caller edges for each impl Trait for Type block.
347        // These represent the implementing type as a caller of the trait, enabling
348        // impl_only filtering to surface trait implementors rather than call sites.
349        for it in impl_traits {
350            graph
351                .callers
352                .entry(it.trait_name.clone())
353                .or_default()
354                .push(CallEdge {
355                    path: it.path.clone(),
356                    line: it.line,
357                    neighbor_name: it.impl_type.clone(),
358                    is_impl_trait: true,
359                });
360        }
361
362        // If impl_only=true, retain only impl-trait caller edges across all nodes.
363        // Callees are never filtered. This ensures traversal and formatting are
364        // consistently restricted to impl-trait edges regardless of follow_depth.
365        if impl_only {
366            for edges in graph.callers.values_mut() {
367                edges.retain(|e| e.is_impl_trait);
368            }
369        }
370
371        // Build lowercase_index for O(1) case-insensitive lookup.
372        // Union of all keys from definitions, callers, and callees.
373        // Group all originals per lowercase key; sort so min() is stable.
374        for key in graph
375            .definitions
376            .keys()
377            .chain(graph.callers.keys())
378            .chain(graph.callees.keys())
379        {
380            graph
381                .lowercase_index
382                .entry(key.to_lowercase())
383                .or_default()
384                .push(key.clone());
385        }
386        for originals in graph.lowercase_index.values_mut() {
387            originals.sort();
388            originals.dedup();
389        }
390
391        let total_edges = graph.callees.values().map(Vec::len).sum::<usize>()
392            + graph.callers.values().map(Vec::len).sum::<usize>();
393        let file_count = results.len();
394
395        tracing::debug!(
396            definitions = graph.definitions.len(),
397            edges = total_edges,
398            files = file_count,
399            impl_only,
400            "graph built"
401        );
402
403        Ok(graph)
404    }
405
406    fn find_chains_bfs(
407        &self,
408        symbol: &str,
409        follow_depth: u32,
410        is_incoming: bool,
411    ) -> Result<Vec<InternalCallChain>, GraphError> {
412        let graph_map = if is_incoming {
413            &self.callers
414        } else {
415            &self.callees
416        };
417
418        if !self.definitions.contains_key(symbol) && !graph_map.contains_key(symbol) {
419            return Err(GraphError::SymbolNotFound {
420                symbol: symbol.to_string(),
421                hint: "Symbol resolved but not found in graph. The symbol may have no calls or definitions in the indexed files.".to_string(),
422            });
423        }
424
425        let mut chains = Vec::new();
426        let mut visited = HashSet::new();
427        let mut queue: VecDeque<(Arc<str>, u32)> = VecDeque::new();
428        queue.push_back((Arc::from(symbol), 0));
429        visited.insert(Arc::from(symbol));
430
431        while let Some((current, depth)) = queue.pop_front() {
432            if depth > follow_depth {
433                continue;
434            }
435
436            // Child span for graph traversal at this depth level
437            let _traverse_span = tracing::info_span!("graph.traverse", depth = depth).entered();
438
439            if let Some(neighbors) = graph_map.get(current.as_ref()) {
440                for edge in neighbors {
441                    let path = &edge.path;
442                    let line = edge.line;
443                    let neighbor = &edge.neighbor_name;
444                    // Pre-allocate capacity: chain holds at most follow_depth + 2 entries
445                    // (the BFS node, up to follow_depth intermediate hops, and the neighbor).
446                    // For incoming chains we accumulate in reverse BFS order (focus first, then
447                    // deeper callers) then call reverse() at the end so that:
448                    //   chain[0]    = immediate caller of focus (closest)
449                    //   chain.last() = focus symbol (the BFS start node at depth 0) or the
450                    //                  current BFS node for deeper depth levels.
451                    // For outgoing chains the order is already focus-first.
452                    let mut chain = {
453                        let mut v = Vec::with_capacity(follow_depth as usize + 2);
454                        v.push((current.to_string(), path.clone(), line));
455                        v
456                    };
457                    let mut chain_node = neighbor.clone();
458                    let mut chain_depth = depth;
459
460                    while chain_depth < follow_depth {
461                        if let Some(next_neighbors) = graph_map.get(&chain_node)
462                            && let Some(next_edge) = next_neighbors.first()
463                        {
464                            // Advance to the next (deeper) caller before pushing, so that
465                            // for incoming chains the element pushed is the deeper ancestor
466                            // (not chain_node itself, which was already recorded or is the
467                            // immediate neighbor pushed after this loop).
468                            chain_node = next_edge.neighbor_name.clone();
469                            chain.push((
470                                chain_node.clone(),
471                                next_edge.path.clone(),
472                                next_edge.line,
473                            ));
474                            chain_depth += 1;
475                        } else {
476                            break;
477                        }
478                    }
479
480                    if is_incoming {
481                        // Add the immediate neighbor (closest to focus) at the end,
482                        // then reverse so chain[0] = immediate neighbor.
483                        chain.push((neighbor.clone(), path.clone(), line));
484                        chain.reverse();
485                    } else {
486                        chain.push((neighbor.clone(), path.clone(), line));
487                    }
488
489                    debug_assert!(
490                        chain.len() <= follow_depth as usize + 2,
491                        "find_chains_bfs: chain length {} exceeds bound {}",
492                        chain.len(),
493                        follow_depth + 2
494                    );
495
496                    chains.push(InternalCallChain { chain });
497
498                    if !visited.contains(neighbor.as_str()) && depth < follow_depth {
499                        visited.insert(Arc::from(neighbor.as_str()));
500                        queue.push_back((Arc::from(neighbor.as_str()), depth + 1));
501                    }
502                }
503            }
504        }
505
506        Ok(chains)
507    }
508
509    #[instrument(skip(self))]
510    pub fn find_incoming_chains(
511        &self,
512        symbol: &str,
513        follow_depth: u32,
514    ) -> Result<Vec<InternalCallChain>, GraphError> {
515        self.find_chains_bfs(symbol, follow_depth, true)
516    }
517
518    #[instrument(skip(self))]
519    pub fn find_outgoing_chains(
520        &self,
521        symbol: &str,
522        follow_depth: u32,
523    ) -> Result<Vec<InternalCallChain>, GraphError> {
524        self.find_chains_bfs(symbol, follow_depth, false)
525    }
526}
527
528impl Default for CallGraph {
529    fn default() -> Self {
530        Self::new()
531    }
532}
533
534#[cfg(test)]
535mod tests {
536    use super::*;
537    use crate::types::{CallInfo, FunctionInfo};
538
539    fn make_analysis(
540        funcs: Vec<(&str, usize)>,
541        calls: Vec<(&str, &str, usize)>,
542    ) -> SemanticAnalysis {
543        SemanticAnalysis {
544            functions: funcs
545                .into_iter()
546                .map(|(n, l)| FunctionInfo {
547                    name: n.to_string(),
548                    line: l,
549                    end_line: l + 5,
550                    parameters: vec![],
551                    return_type: None,
552                })
553                .collect(),
554            classes: vec![],
555            imports: vec![],
556            references: vec![],
557            call_frequency: Default::default(),
558            calls: calls
559                .into_iter()
560                .map(|(c, e, l)| CallInfo {
561                    caller: c.to_string(),
562                    callee: e.to_string(),
563                    line: l,
564                    column: 0,
565                    arg_count: None,
566                })
567                .collect(),
568            impl_traits: vec![],
569            def_use_sites: vec![],
570        }
571    }
572
573    fn make_typed_analysis(
574        funcs: Vec<(&str, usize, Vec<String>, Option<&str>)>,
575        calls: Vec<(&str, &str, usize, Option<usize>)>,
576    ) -> SemanticAnalysis {
577        SemanticAnalysis {
578            functions: funcs
579                .into_iter()
580                .map(|(n, l, params, ret_type)| FunctionInfo {
581                    name: n.to_string(),
582                    line: l,
583                    end_line: l + 5,
584                    parameters: params,
585                    return_type: ret_type.map(|s| s.to_string()),
586                })
587                .collect(),
588            classes: vec![],
589            imports: vec![],
590            references: vec![],
591            call_frequency: Default::default(),
592            calls: calls
593                .into_iter()
594                .map(|(c, e, l, arg_count)| CallInfo {
595                    caller: c.to_string(),
596                    callee: e.to_string(),
597                    line: l,
598                    column: 0,
599                    arg_count,
600                })
601                .collect(),
602            impl_traits: vec![],
603            def_use_sites: vec![],
604        }
605    }
606
607    #[test]
608    fn test_graph_construction() {
609        let analysis = make_analysis(
610            vec![("main", 1), ("foo", 10), ("bar", 20)],
611            vec![("main", "foo", 2), ("foo", "bar", 15)],
612        );
613        let graph =
614            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
615                .expect("Failed to build graph");
616        assert!(graph.definitions.contains_key("main"));
617        assert!(graph.definitions.contains_key("foo"));
618        assert_eq!(graph.callees["main"][0].neighbor_name, "foo");
619        assert_eq!(graph.callers["foo"][0].neighbor_name, "main");
620    }
621
622    #[test]
623    fn test_find_incoming_chains_depth_zero() {
624        let analysis = make_analysis(vec![("main", 1), ("foo", 10)], vec![("main", "foo", 2)]);
625        let graph =
626            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
627                .expect("Failed to build graph");
628        assert!(
629            !graph
630                .find_incoming_chains("foo", 0)
631                .expect("Failed to find chains")
632                .is_empty()
633        );
634    }
635
636    #[test]
637    fn test_find_outgoing_chains_depth_zero() {
638        let analysis = make_analysis(vec![("main", 1), ("foo", 10)], vec![("main", "foo", 2)]);
639        let graph =
640            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
641                .expect("Failed to build graph");
642        assert!(
643            !graph
644                .find_outgoing_chains("main", 0)
645                .expect("Failed to find chains")
646                .is_empty()
647        );
648    }
649
650    #[test]
651    fn test_symbol_not_found() {
652        assert!(
653            CallGraph::new()
654                .find_incoming_chains("nonexistent", 0)
655                .is_err()
656        );
657    }
658
659    #[test]
660    fn test_same_file_preference() {
661        // Two files each define "helper". File a.rs has a call from "main" to "helper".
662        // Assert that the graph's callees for "main" point to "helper" and the callers
663        // for "helper" include an entry from a.rs (not b.rs).
664        let analysis_a = make_analysis(
665            vec![("main", 1), ("helper", 10)],
666            vec![("main", "helper", 5)],
667        );
668        let analysis_b = make_analysis(vec![("helper", 20)], vec![]);
669
670        let graph = CallGraph::build_from_results(
671            vec![
672                (PathBuf::from("a.rs"), analysis_a),
673                (PathBuf::from("b.rs"), analysis_b),
674            ],
675            &[],
676            false,
677        )
678        .expect("Failed to build graph");
679
680        // Check that main calls helper
681        assert!(graph.callees.contains_key("main"));
682        let main_callees = &graph.callees["main"];
683        assert_eq!(main_callees.len(), 1);
684        assert_eq!(main_callees[0].neighbor_name, "helper");
685
686        // Check that the call is from a.rs (same file as main)
687        assert_eq!(main_callees[0].path, PathBuf::from("a.rs"));
688
689        // Check that helper has a caller from a.rs
690        assert!(graph.callers.contains_key("helper"));
691        let helper_callers = &graph.callers["helper"];
692        assert!(
693            helper_callers
694                .iter()
695                .any(|e| e.path == PathBuf::from("a.rs"))
696        );
697    }
698
699    #[test]
700    fn test_line_proximity() {
701        // One file with "process" defined at line 10 and line 50, and a call at line 12.
702        // Assert resolution picks the definition at line 10 (closest).
703        let analysis = make_analysis(
704            vec![("process", 10), ("process", 50)],
705            vec![("main", "process", 12)],
706        );
707
708        let graph =
709            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
710                .expect("Failed to build graph");
711
712        // Check that main calls process
713        assert!(graph.callees.contains_key("main"));
714        let main_callees = &graph.callees["main"];
715        assert_eq!(main_callees.len(), 1);
716        assert_eq!(main_callees[0].neighbor_name, "process");
717
718        // Check that process has a caller from main at line 12
719        assert!(graph.callers.contains_key("process"));
720        let process_callers = &graph.callers["process"];
721        assert!(
722            process_callers
723                .iter()
724                .any(|e| e.line == 12 && e.neighbor_name == "main")
725        );
726    }
727
728    #[test]
729    fn test_scope_prefix_stripping() {
730        // One file defines "method" at line 10. Calls use "self.method", "Type::method".
731        // Assert these resolve to "method" in the graph.
732        let analysis = make_analysis(
733            vec![("method", 10)],
734            vec![
735                ("caller1", "self.method", 5),
736                ("caller2", "Type::method", 15),
737                ("caller3", "module::method", 25),
738            ],
739        );
740
741        let graph =
742            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
743                .expect("Failed to build graph");
744
745        // Check that all three callers have "method" as their callee
746        assert_eq!(graph.callees["caller1"][0].neighbor_name, "method");
747        assert_eq!(graph.callees["caller2"][0].neighbor_name, "method");
748        assert_eq!(graph.callees["caller3"][0].neighbor_name, "method");
749
750        // Check that method has three callers
751        assert!(graph.callers.contains_key("method"));
752        let method_callers = &graph.callers["method"];
753        assert_eq!(method_callers.len(), 3);
754        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller1"));
755        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller2"));
756        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller3"));
757    }
758
759    #[test]
760    fn test_no_same_file_fallback() {
761        // File a.rs calls "helper" but "helper" is only defined in b.rs.
762        // Assert the call still resolves (graph has the edge).
763        let analysis_a = make_analysis(vec![("main", 1)], vec![("main", "helper", 5)]);
764        let analysis_b = make_analysis(vec![("helper", 10)], vec![]);
765
766        let graph = CallGraph::build_from_results(
767            vec![
768                (PathBuf::from("a.rs"), analysis_a),
769                (PathBuf::from("b.rs"), analysis_b),
770            ],
771            &[],
772            false,
773        )
774        .expect("Failed to build graph");
775
776        // Check that main calls helper
777        assert!(graph.callees.contains_key("main"));
778        let main_callees = &graph.callees["main"];
779        assert_eq!(main_callees.len(), 1);
780        assert_eq!(main_callees[0].neighbor_name, "helper");
781
782        // Check that helper has a caller from a.rs
783        assert!(graph.callers.contains_key("helper"));
784        let helper_callers = &graph.callers["helper"];
785        assert!(
786            helper_callers
787                .iter()
788                .any(|e| e.path == PathBuf::from("a.rs") && e.neighbor_name == "main")
789        );
790    }
791
792    #[test]
793    fn test_type_disambiguation_by_params() {
794        // Two functions named 'process' in the same file with different parameter counts.
795        // process(x: i32) at line 10, process(x: i32, y: String) at line 12.
796        // Call from main at line 11 is equidistant from both (1 line away).
797        // Type matching should prefer the 2-param version since arg_count=2.
798        let analysis = make_typed_analysis(
799            vec![
800                ("process", 10, vec!["(x: i32)".to_string()], Some("i32")),
801                (
802                    "process",
803                    12,
804                    vec!["(x: i32, y: String)".to_string()],
805                    Some("String"),
806                ),
807                ("main", 1, vec![], None),
808            ],
809            vec![("main", "process", 11, Some(2))],
810        );
811
812        let graph =
813            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
814                .expect("Failed to build graph");
815
816        // Check that main calls process
817        assert!(graph.callees.contains_key("main"));
818        let main_callees = &graph.callees["main"];
819        assert_eq!(main_callees.len(), 1);
820        assert_eq!(main_callees[0].neighbor_name, "process");
821
822        // Check that process has a caller from main at line 11
823        assert!(graph.callers.contains_key("process"));
824        let process_callers = &graph.callers["process"];
825        assert!(
826            process_callers
827                .iter()
828                .any(|e| e.line == 11 && e.neighbor_name == "main")
829        );
830    }
831
832    #[test]
833    fn test_type_disambiguation_fallback() {
834        // Two functions named 'process' with no type info (empty parameters, None return_type).
835        // Call from main at line 12 should resolve using line proximity (no regression).
836        // arg_count=None means type matching won't fire, fallback to line proximity.
837        let analysis = make_analysis(
838            vec![("process", 10), ("process", 50), ("main", 1)],
839            vec![("main", "process", 12)],
840        );
841
842        let graph =
843            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
844                .expect("Failed to build graph");
845
846        // Check that main calls process
847        assert!(graph.callees.contains_key("main"));
848        let main_callees = &graph.callees["main"];
849        assert_eq!(main_callees.len(), 1);
850        assert_eq!(main_callees[0].neighbor_name, "process");
851
852        // Check that process has a caller from main
853        assert!(graph.callers.contains_key("process"));
854        let process_callers = &graph.callers["process"];
855        assert!(
856            process_callers
857                .iter()
858                .any(|e| e.line == 12 && e.neighbor_name == "main")
859        );
860    }
861
862    #[test]
863    fn test_impl_only_filters_to_impl_sites() {
864        // Arrange: WriterImpl implements Write; plain_fn calls write directly.
865        use crate::types::ImplTraitInfo;
866        let analysis = make_analysis(
867            vec![("write", 1), ("plain_fn", 20)],
868            vec![("plain_fn", "write", 22)],
869        );
870        let impl_traits = vec![ImplTraitInfo {
871            trait_name: "Write".to_string(),
872            impl_type: "WriterImpl".to_string(),
873            path: PathBuf::from("test.rs"),
874            line: 10,
875        }];
876
877        // Act: build with impl_only=true
878        let graph = CallGraph::build_from_results(
879            vec![(PathBuf::from("test.rs"), analysis)],
880            &impl_traits,
881            true,
882        )
883        .expect("Failed to build graph");
884
885        // Assert: trait "Write" has WriterImpl as an explicit impl-trait caller edge.
886        let callers = graph
887            .callers
888            .get("Write")
889            .expect("Write must have impl caller");
890        assert_eq!(callers.len(), 1, "only impl-trait caller retained");
891        assert_eq!(callers[0].neighbor_name, "WriterImpl");
892        assert!(
893            callers[0].is_impl_trait,
894            "edge must be tagged is_impl_trait"
895        );
896
897        // Assert: regular call-site callers of "write" are filtered out by impl_only.
898        let write_callers = graph.callers.get("write").map(|v| v.len()).unwrap_or(0);
899        assert_eq!(
900            write_callers, 0,
901            "regular callers filtered when impl_only=true"
902        );
903    }
904
905    #[test]
906    fn test_impl_only_false_is_backward_compatible() {
907        // Arrange: same setup, impl_only=false -- all callers returned.
908        use crate::types::ImplTraitInfo;
909        let analysis = make_analysis(
910            vec![("write", 1), ("WriterImpl", 10), ("plain_fn", 20)],
911            vec![("WriterImpl", "write", 12), ("plain_fn", "write", 22)],
912        );
913        let impl_traits = vec![ImplTraitInfo {
914            trait_name: "Write".to_string(),
915            impl_type: "WriterImpl".to_string(),
916            path: PathBuf::from("test.rs"),
917            line: 10,
918        }];
919
920        // Act: build with impl_only=false
921        let graph = CallGraph::build_from_results(
922            vec![(PathBuf::from("test.rs"), analysis)],
923            &impl_traits,
924            false,
925        )
926        .expect("Failed to build graph");
927
928        // Assert: both call-site callers preserved
929        let callers = graph.callers.get("write").expect("write must have callers");
930        assert_eq!(
931            callers.len(),
932            2,
933            "both call-site callers should be present when impl_only=false"
934        );
935
936        // Assert: impl-trait edge is always present regardless of impl_only
937        let write_impl_callers = graph
938            .callers
939            .get("Write")
940            .expect("Write must have impl caller");
941        assert_eq!(write_impl_callers.len(), 1);
942        assert!(write_impl_callers[0].is_impl_trait);
943    }
944
945    #[test]
946    fn test_impl_only_callees_unaffected() {
947        // Arrange: WriterImpl calls write; impl_only=true should not remove callees.
948        use crate::types::ImplTraitInfo;
949        let analysis = make_analysis(
950            vec![("write", 1), ("WriterImpl", 10)],
951            vec![("WriterImpl", "write", 12)],
952        );
953        let impl_traits = vec![ImplTraitInfo {
954            trait_name: "Write".to_string(),
955            impl_type: "WriterImpl".to_string(),
956            path: PathBuf::from("test.rs"),
957            line: 10,
958        }];
959
960        let graph = CallGraph::build_from_results(
961            vec![(PathBuf::from("test.rs"), analysis)],
962            &impl_traits,
963            true,
964        )
965        .expect("Failed to build graph");
966
967        // Assert: callees of WriterImpl are NOT filtered
968        let callees = graph
969            .callees
970            .get("WriterImpl")
971            .expect("WriterImpl must have callees");
972        assert_eq!(
973            callees.len(),
974            1,
975            "callees must not be filtered by impl_only"
976        );
977        assert_eq!(callees[0].neighbor_name, "write");
978    }
979
980    // ---- resolve_symbol tests ----
981
982    fn known(names: &[&str]) -> Vec<String> {
983        names.iter().map(|s| s.to_string()).collect()
984    }
985
986    #[test]
987    fn test_resolve_symbol_exact_match() {
988        let syms = known(&["parse_config", "ParseConfig", "PARSE_CONFIG"]);
989        let result = resolve_symbol(syms.iter(), "parse_config", &SymbolMatchMode::Exact);
990        assert_eq!(result.unwrap(), "parse_config");
991    }
992
993    #[test]
994    fn test_resolve_symbol_exact_no_match() {
995        let syms = known(&["ParseConfig"]);
996        let err = resolve_symbol(syms.iter(), "parse_config", &SymbolMatchMode::Exact).unwrap_err();
997        std::assert_matches!(err, GraphError::SymbolNotFound { .. });
998    }
999
1000    #[test]
1001    fn test_resolve_symbol_insensitive_match() {
1002        let syms = known(&["ParseConfig", "other"]);
1003        let result = resolve_symbol(syms.iter(), "parseconfig", &SymbolMatchMode::Insensitive);
1004        assert_eq!(result.unwrap(), "ParseConfig");
1005    }
1006
1007    #[test]
1008    fn test_resolve_symbol_insensitive_no_match() {
1009        let syms = known(&["unrelated"]);
1010        let err =
1011            resolve_symbol(syms.iter(), "parseconfig", &SymbolMatchMode::Insensitive).unwrap_err();
1012        std::assert_matches!(err, GraphError::SymbolNotFound { .. });
1013    }
1014
1015    #[test]
1016    fn test_resolve_symbol_prefix_single() {
1017        let syms = known(&["parse_config", "parse_args", "build"]);
1018        let result = resolve_symbol(syms.iter(), "build", &SymbolMatchMode::Prefix);
1019        assert_eq!(result.unwrap(), "build");
1020    }
1021
1022    #[test]
1023    fn test_resolve_symbol_prefix_multiple_candidates() {
1024        let syms = known(&["parse_config", "parse_args", "build"]);
1025        let err = resolve_symbol(syms.iter(), "parse", &SymbolMatchMode::Prefix).unwrap_err();
1026        std::assert_matches!(&err, GraphError::MultipleCandidates { .. });
1027        if let GraphError::MultipleCandidates { candidates, .. } = err {
1028            assert_eq!(candidates.len(), 2);
1029        }
1030    }
1031
1032    #[test]
1033    fn test_resolve_symbol_contains_single() {
1034        let syms = known(&["parse_config", "build_artifact"]);
1035        let result = resolve_symbol(syms.iter(), "config", &SymbolMatchMode::Contains);
1036        assert_eq!(result.unwrap(), "parse_config");
1037    }
1038
1039    #[test]
1040    fn test_resolve_symbol_contains_no_match() {
1041        let syms = known(&["parse_config", "build_artifact"]);
1042        let err = resolve_symbol(syms.iter(), "deploy", &SymbolMatchMode::Contains).unwrap_err();
1043        std::assert_matches!(err, GraphError::SymbolNotFound { .. });
1044    }
1045
1046    #[test]
1047    fn test_incoming_chain_order_two_hops() {
1048        // Graph: A calls B calls C.  Focus = C, follow_depth = 2.
1049        //
1050        // Expected chains after reverse():
1051        //   depth-0 chain: [B, A, C]  -- immediate caller first, then outermost, then focus
1052        //   depth-1 chain: [A, B]     -- A calls B
1053        //
1054        // This test pins the ordering so that a missing reverse() or an off-by-one in the
1055        // inner-loop push would be caught: chain[1] must be "A" (outermost), not "B" again.
1056        let analysis = make_analysis(
1057            vec![("A", 1), ("B", 10), ("C", 20)],
1058            vec![("A", "B", 2), ("B", "C", 15)],
1059        );
1060        let graph =
1061            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1062                .expect("Failed to build graph");
1063
1064        let chains = graph
1065            .find_incoming_chains("C", 2)
1066            .expect("Failed to find incoming chains");
1067
1068        assert!(
1069            !chains.is_empty(),
1070            "Expected at least one incoming chain for C"
1071        );
1072
1073        // The 2-hop chain has 3 elements: [immediate_caller, outermost_caller, focus].
1074        let chain = chains
1075            .iter()
1076            .find(|c| c.chain.len() == 3)
1077            .expect("Expected a 3-element chain");
1078
1079        assert_eq!(
1080            chain.chain[0].0, "B",
1081            "chain[0] should be immediate caller B, got {}",
1082            chain.chain[0].0
1083        );
1084        assert_eq!(
1085            chain.chain[1].0, "A",
1086            "chain[1] should be outermost caller A, got {}",
1087            chain.chain[1].0
1088        );
1089        assert_eq!(
1090            chain.chain[2].0, "C",
1091            "chain[2] should be focus node C, got {}",
1092            chain.chain[2].0
1093        );
1094    }
1095
1096    // ---- resolve_symbol_indexed tests ----
1097
1098    #[test]
1099    fn test_insensitive_resolve_via_index() {
1100        // Arrange: build a CallGraph with known symbols
1101        let analysis = make_analysis(
1102            vec![("ParseConfig", 1), ("parse_args", 5)],
1103            vec![("ParseConfig", "parse_args", 10)],
1104        );
1105        let graph =
1106            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1107                .expect("Failed to build graph");
1108
1109        // Act: resolve using insensitive mode via the indexed method
1110        let result = graph
1111            .resolve_symbol_indexed("parseconfig", &SymbolMatchMode::Insensitive)
1112            .expect("Should resolve ParseConfig");
1113
1114        // Assert: O(1) lookup via lowercase_index returns the original symbol
1115        assert_eq!(result, "ParseConfig");
1116    }
1117
1118    #[test]
1119    fn test_prefix_resolve_via_index() {
1120        // Arrange: build a CallGraph with multiple symbols matching a prefix
1121        let analysis = make_analysis(
1122            vec![("parse_config", 1), ("parse_args", 5), ("build", 10)],
1123            vec![],
1124        );
1125        let graph =
1126            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1127                .expect("Failed to build graph");
1128
1129        // Act: resolve using prefix mode via the indexed method
1130        let err = graph
1131            .resolve_symbol_indexed("parse", &SymbolMatchMode::Prefix)
1132            .unwrap_err();
1133
1134        // Assert: multiple candidates found
1135        std::assert_matches!(&err, GraphError::MultipleCandidates { .. });
1136        if let GraphError::MultipleCandidates { candidates, .. } = err {
1137            assert_eq!(candidates.len(), 2);
1138        }
1139    }
1140
1141    #[test]
1142    fn test_insensitive_case_collision_returns_multiple_candidates() {
1143        // Arrange: two symbols that differ only by case map to the same lowercase key
1144        let analysis = make_analysis(vec![("Foo", 1), ("foo", 5)], vec![("Foo", "foo", 10)]);
1145        let graph =
1146            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1147                .expect("Failed to build graph");
1148
1149        // Act: insensitive lookup for "foo" hits both Foo and foo
1150        let err = graph
1151            .resolve_symbol_indexed("foo", &SymbolMatchMode::Insensitive)
1152            .unwrap_err();
1153
1154        // Assert: MultipleCandidates returned for case collision
1155        std::assert_matches!(&err, GraphError::MultipleCandidates { .. });
1156        if let GraphError::MultipleCandidates { candidates, .. } = err {
1157            assert_eq!(candidates.len(), 2);
1158        }
1159    }
1160
1161    #[test]
1162    fn test_contains_resolve_via_index() {
1163        // Arrange: symbols where two match the query substring; one does not
1164        let analysis = make_analysis(
1165            vec![("parse_config", 1), ("build_config", 5), ("run", 10)],
1166            vec![],
1167        );
1168        let graph =
1169            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1170                .expect("Failed to build graph");
1171
1172        // Act: resolve using contains mode; "config" matches parse_config and build_config
1173        let err = graph
1174            .resolve_symbol_indexed("config", &SymbolMatchMode::Contains)
1175            .unwrap_err();
1176
1177        // Assert: both matching symbols returned as MultipleCandidates
1178        std::assert_matches!(&err, GraphError::MultipleCandidates { .. });
1179        if let GraphError::MultipleCandidates { candidates, .. } = err {
1180            let mut sorted = candidates.clone();
1181            sorted.sort();
1182            assert_eq!(sorted, vec!["build_config", "parse_config"]);
1183        }
1184    }
1185}
aptu_coder_core/graph.rs

aptu_coder_core/
graph.rs
