code_analyze_core/
graph.rs

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

code_analyze_core/
graph.rs
