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 FunctionTypeInfo = (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<FunctionTypeInfo>>,
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<FunctionTypeInfo>>,
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        }
583    }
584
585    fn make_typed_analysis(
586        funcs: Vec<(&str, usize, Vec<String>, Option<&str>)>,
587        calls: Vec<(&str, &str, usize, Option<usize>)>,
588    ) -> SemanticAnalysis {
589        SemanticAnalysis {
590            functions: funcs
591                .into_iter()
592                .map(|(n, l, params, ret_type)| FunctionInfo {
593                    name: n.to_string(),
594                    line: l,
595                    end_line: l + 5,
596                    parameters: params,
597                    return_type: ret_type.map(|s| s.to_string()),
598                })
599                .collect(),
600            classes: vec![],
601            imports: vec![],
602            references: vec![],
603            call_frequency: Default::default(),
604            calls: calls
605                .into_iter()
606                .map(|(c, e, l, arg_count)| CallInfo {
607                    caller: c.to_string(),
608                    callee: e.to_string(),
609                    line: l,
610                    column: 0,
611                    arg_count,
612                })
613                .collect(),
614            impl_traits: vec![],
615        }
616    }
617
618    #[test]
619    fn test_graph_construction() {
620        let analysis = make_analysis(
621            vec![("main", 1), ("foo", 10), ("bar", 20)],
622            vec![("main", "foo", 2), ("foo", "bar", 15)],
623        );
624        let graph =
625            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
626                .expect("Failed to build graph");
627        assert!(graph.definitions.contains_key("main"));
628        assert!(graph.definitions.contains_key("foo"));
629        assert_eq!(graph.callees["main"][0].neighbor_name, "foo");
630        assert_eq!(graph.callers["foo"][0].neighbor_name, "main");
631    }
632
633    #[test]
634    fn test_find_incoming_chains_depth_zero() {
635        let analysis = make_analysis(vec![("main", 1), ("foo", 10)], vec![("main", "foo", 2)]);
636        let graph =
637            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
638                .expect("Failed to build graph");
639        assert!(
640            !graph
641                .find_incoming_chains("foo", 0)
642                .expect("Failed to find chains")
643                .is_empty()
644        );
645    }
646
647    #[test]
648    fn test_find_outgoing_chains_depth_zero() {
649        let analysis = make_analysis(vec![("main", 1), ("foo", 10)], vec![("main", "foo", 2)]);
650        let graph =
651            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
652                .expect("Failed to build graph");
653        assert!(
654            !graph
655                .find_outgoing_chains("main", 0)
656                .expect("Failed to find chains")
657                .is_empty()
658        );
659    }
660
661    #[test]
662    fn test_symbol_not_found() {
663        assert!(
664            CallGraph::new()
665                .find_incoming_chains("nonexistent", 0)
666                .is_err()
667        );
668    }
669
670    #[test]
671    fn test_same_file_preference() {
672        // Two files each define "helper". File a.rs has a call from "main" to "helper".
673        // Assert that the graph's callees for "main" point to "helper" and the callers
674        // for "helper" include an entry from a.rs (not b.rs).
675        let analysis_a = make_analysis(
676            vec![("main", 1), ("helper", 10)],
677            vec![("main", "helper", 5)],
678        );
679        let analysis_b = make_analysis(vec![("helper", 20)], vec![]);
680
681        let graph = CallGraph::build_from_results(
682            vec![
683                (PathBuf::from("a.rs"), analysis_a),
684                (PathBuf::from("b.rs"), analysis_b),
685            ],
686            &[],
687            false,
688        )
689        .expect("Failed to build graph");
690
691        // Check that main calls helper
692        assert!(graph.callees.contains_key("main"));
693        let main_callees = &graph.callees["main"];
694        assert_eq!(main_callees.len(), 1);
695        assert_eq!(main_callees[0].neighbor_name, "helper");
696
697        // Check that the call is from a.rs (same file as main)
698        assert_eq!(main_callees[0].path, PathBuf::from("a.rs"));
699
700        // Check that helper has a caller from a.rs
701        assert!(graph.callers.contains_key("helper"));
702        let helper_callers = &graph.callers["helper"];
703        assert!(
704            helper_callers
705                .iter()
706                .any(|e| e.path == PathBuf::from("a.rs"))
707        );
708    }
709
710    #[test]
711    fn test_line_proximity() {
712        // One file with "process" defined at line 10 and line 50, and a call at line 12.
713        // Assert resolution picks the definition at line 10 (closest).
714        let analysis = make_analysis(
715            vec![("process", 10), ("process", 50)],
716            vec![("main", "process", 12)],
717        );
718
719        let graph =
720            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
721                .expect("Failed to build graph");
722
723        // Check that main calls process
724        assert!(graph.callees.contains_key("main"));
725        let main_callees = &graph.callees["main"];
726        assert_eq!(main_callees.len(), 1);
727        assert_eq!(main_callees[0].neighbor_name, "process");
728
729        // Check that process has a caller from main at line 12
730        assert!(graph.callers.contains_key("process"));
731        let process_callers = &graph.callers["process"];
732        assert!(
733            process_callers
734                .iter()
735                .any(|e| e.line == 12 && e.neighbor_name == "main")
736        );
737    }
738
739    #[test]
740    fn test_scope_prefix_stripping() {
741        // One file defines "method" at line 10. Calls use "self.method", "Type::method".
742        // Assert these resolve to "method" in the graph.
743        let analysis = make_analysis(
744            vec![("method", 10)],
745            vec![
746                ("caller1", "self.method", 5),
747                ("caller2", "Type::method", 15),
748                ("caller3", "module::method", 25),
749            ],
750        );
751
752        let graph =
753            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
754                .expect("Failed to build graph");
755
756        // Check that all three callers have "method" as their callee
757        assert_eq!(graph.callees["caller1"][0].neighbor_name, "method");
758        assert_eq!(graph.callees["caller2"][0].neighbor_name, "method");
759        assert_eq!(graph.callees["caller3"][0].neighbor_name, "method");
760
761        // Check that method has three callers
762        assert!(graph.callers.contains_key("method"));
763        let method_callers = &graph.callers["method"];
764        assert_eq!(method_callers.len(), 3);
765        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller1"));
766        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller2"));
767        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller3"));
768    }
769
770    #[test]
771    fn test_no_same_file_fallback() {
772        // File a.rs calls "helper" but "helper" is only defined in b.rs.
773        // Assert the call still resolves (graph has the edge).
774        let analysis_a = make_analysis(vec![("main", 1)], vec![("main", "helper", 5)]);
775        let analysis_b = make_analysis(vec![("helper", 10)], vec![]);
776
777        let graph = CallGraph::build_from_results(
778            vec![
779                (PathBuf::from("a.rs"), analysis_a),
780                (PathBuf::from("b.rs"), analysis_b),
781            ],
782            &[],
783            false,
784        )
785        .expect("Failed to build graph");
786
787        // Check that main calls helper
788        assert!(graph.callees.contains_key("main"));
789        let main_callees = &graph.callees["main"];
790        assert_eq!(main_callees.len(), 1);
791        assert_eq!(main_callees[0].neighbor_name, "helper");
792
793        // Check that helper has a caller from a.rs
794        assert!(graph.callers.contains_key("helper"));
795        let helper_callers = &graph.callers["helper"];
796        assert!(
797            helper_callers
798                .iter()
799                .any(|e| e.path == PathBuf::from("a.rs") && e.neighbor_name == "main")
800        );
801    }
802
803    #[test]
804    fn test_type_disambiguation_by_params() {
805        // Two functions named 'process' in the same file with different parameter counts.
806        // process(x: i32) at line 10, process(x: i32, y: String) at line 12.
807        // Call from main at line 11 is equidistant from both (1 line away).
808        // Type matching should prefer the 2-param version since arg_count=2.
809        let analysis = make_typed_analysis(
810            vec![
811                ("process", 10, vec!["(x: i32)".to_string()], Some("i32")),
812                (
813                    "process",
814                    12,
815                    vec!["(x: i32, y: String)".to_string()],
816                    Some("String"),
817                ),
818                ("main", 1, vec![], None),
819            ],
820            vec![("main", "process", 11, Some(2))],
821        );
822
823        let graph =
824            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
825                .expect("Failed to build graph");
826
827        // Check that main calls process
828        assert!(graph.callees.contains_key("main"));
829        let main_callees = &graph.callees["main"];
830        assert_eq!(main_callees.len(), 1);
831        assert_eq!(main_callees[0].neighbor_name, "process");
832
833        // Check that process has a caller from main at line 11
834        assert!(graph.callers.contains_key("process"));
835        let process_callers = &graph.callers["process"];
836        assert!(
837            process_callers
838                .iter()
839                .any(|e| e.line == 11 && e.neighbor_name == "main")
840        );
841    }
842
843    #[test]
844    fn test_type_disambiguation_fallback() {
845        // Two functions named 'process' with no type info (empty parameters, None return_type).
846        // Call from main at line 12 should resolve using line proximity (no regression).
847        // arg_count=None means type matching won't fire, fallback to line proximity.
848        let analysis = make_analysis(
849            vec![("process", 10), ("process", 50), ("main", 1)],
850            vec![("main", "process", 12)],
851        );
852
853        let graph =
854            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
855                .expect("Failed to build graph");
856
857        // Check that main calls process
858        assert!(graph.callees.contains_key("main"));
859        let main_callees = &graph.callees["main"];
860        assert_eq!(main_callees.len(), 1);
861        assert_eq!(main_callees[0].neighbor_name, "process");
862
863        // Check that process has a caller from main
864        assert!(graph.callers.contains_key("process"));
865        let process_callers = &graph.callers["process"];
866        assert!(
867            process_callers
868                .iter()
869                .any(|e| e.line == 12 && e.neighbor_name == "main")
870        );
871    }
872
873    #[test]
874    fn test_impl_only_filters_to_impl_sites() {
875        // Arrange: WriterImpl implements Write; plain_fn calls write directly.
876        use crate::types::ImplTraitInfo;
877        let analysis = make_analysis(
878            vec![("write", 1), ("plain_fn", 20)],
879            vec![("plain_fn", "write", 22)],
880        );
881        let impl_traits = vec![ImplTraitInfo {
882            trait_name: "Write".to_string(),
883            impl_type: "WriterImpl".to_string(),
884            path: PathBuf::from("test.rs"),
885            line: 10,
886        }];
887
888        // Act: build with impl_only=true
889        let graph = CallGraph::build_from_results(
890            vec![(PathBuf::from("test.rs"), analysis)],
891            &impl_traits,
892            true,
893        )
894        .expect("Failed to build graph");
895
896        // Assert: trait "Write" has WriterImpl as an explicit impl-trait caller edge.
897        let callers = graph
898            .callers
899            .get("Write")
900            .expect("Write must have impl caller");
901        assert_eq!(callers.len(), 1, "only impl-trait caller retained");
902        assert_eq!(callers[0].neighbor_name, "WriterImpl");
903        assert!(
904            callers[0].is_impl_trait,
905            "edge must be tagged is_impl_trait"
906        );
907
908        // Assert: regular call-site callers of "write" are filtered out by impl_only.
909        let write_callers = graph.callers.get("write").map(|v| v.len()).unwrap_or(0);
910        assert_eq!(
911            write_callers, 0,
912            "regular callers filtered when impl_only=true"
913        );
914    }
915
916    #[test]
917    fn test_impl_only_false_is_backward_compatible() {
918        // Arrange: same setup, impl_only=false -- all callers returned.
919        use crate::types::ImplTraitInfo;
920        let analysis = make_analysis(
921            vec![("write", 1), ("WriterImpl", 10), ("plain_fn", 20)],
922            vec![("WriterImpl", "write", 12), ("plain_fn", "write", 22)],
923        );
924        let impl_traits = vec![ImplTraitInfo {
925            trait_name: "Write".to_string(),
926            impl_type: "WriterImpl".to_string(),
927            path: PathBuf::from("test.rs"),
928            line: 10,
929        }];
930
931        // Act: build with impl_only=false
932        let graph = CallGraph::build_from_results(
933            vec![(PathBuf::from("test.rs"), analysis)],
934            &impl_traits,
935            false,
936        )
937        .expect("Failed to build graph");
938
939        // Assert: both call-site callers preserved
940        let callers = graph.callers.get("write").expect("write must have callers");
941        assert_eq!(
942            callers.len(),
943            2,
944            "both call-site callers should be present when impl_only=false"
945        );
946
947        // Assert: impl-trait edge is always present regardless of impl_only
948        let write_impl_callers = graph
949            .callers
950            .get("Write")
951            .expect("Write must have impl caller");
952        assert_eq!(write_impl_callers.len(), 1);
953        assert!(write_impl_callers[0].is_impl_trait);
954    }
955
956    #[test]
957    fn test_impl_only_callees_unaffected() {
958        // Arrange: WriterImpl calls write; impl_only=true should not remove callees.
959        use crate::types::ImplTraitInfo;
960        let analysis = make_analysis(
961            vec![("write", 1), ("WriterImpl", 10)],
962            vec![("WriterImpl", "write", 12)],
963        );
964        let impl_traits = vec![ImplTraitInfo {
965            trait_name: "Write".to_string(),
966            impl_type: "WriterImpl".to_string(),
967            path: PathBuf::from("test.rs"),
968            line: 10,
969        }];
970
971        let graph = CallGraph::build_from_results(
972            vec![(PathBuf::from("test.rs"), analysis)],
973            &impl_traits,
974            true,
975        )
976        .expect("Failed to build graph");
977
978        // Assert: callees of WriterImpl are NOT filtered
979        let callees = graph
980            .callees
981            .get("WriterImpl")
982            .expect("WriterImpl must have callees");
983        assert_eq!(
984            callees.len(),
985            1,
986            "callees must not be filtered by impl_only"
987        );
988        assert_eq!(callees[0].neighbor_name, "write");
989    }
990
991    // ---- resolve_symbol tests ----
992
993    fn known(names: &[&str]) -> Vec<String> {
994        names.iter().map(|s| s.to_string()).collect()
995    }
996
997    #[test]
998    fn test_resolve_symbol_exact_match() {
999        let syms = known(&["parse_config", "ParseConfig", "PARSE_CONFIG"]);
1000        let result = resolve_symbol(syms.iter(), "parse_config", &SymbolMatchMode::Exact);
1001        assert_eq!(result.unwrap(), "parse_config");
1002    }
1003
1004    #[test]
1005    fn test_resolve_symbol_exact_no_match() {
1006        let syms = known(&["ParseConfig"]);
1007        let err = resolve_symbol(syms.iter(), "parse_config", &SymbolMatchMode::Exact).unwrap_err();
1008        assert!(matches!(err, GraphError::SymbolNotFound { .. }));
1009    }
1010
1011    #[test]
1012    fn test_resolve_symbol_insensitive_match() {
1013        let syms = known(&["ParseConfig", "other"]);
1014        let result = resolve_symbol(syms.iter(), "parseconfig", &SymbolMatchMode::Insensitive);
1015        assert_eq!(result.unwrap(), "ParseConfig");
1016    }
1017
1018    #[test]
1019    fn test_resolve_symbol_insensitive_no_match() {
1020        let syms = known(&["unrelated"]);
1021        let err =
1022            resolve_symbol(syms.iter(), "parseconfig", &SymbolMatchMode::Insensitive).unwrap_err();
1023        assert!(matches!(err, GraphError::SymbolNotFound { .. }));
1024    }
1025
1026    #[test]
1027    fn test_resolve_symbol_prefix_single() {
1028        let syms = known(&["parse_config", "parse_args", "build"]);
1029        let result = resolve_symbol(syms.iter(), "build", &SymbolMatchMode::Prefix);
1030        assert_eq!(result.unwrap(), "build");
1031    }
1032
1033    #[test]
1034    fn test_resolve_symbol_prefix_multiple_candidates() {
1035        let syms = known(&["parse_config", "parse_args", "build"]);
1036        let err = resolve_symbol(syms.iter(), "parse", &SymbolMatchMode::Prefix).unwrap_err();
1037        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1038        if let GraphError::MultipleCandidates { candidates, .. } = err {
1039            assert_eq!(candidates.len(), 2);
1040        }
1041    }
1042
1043    #[test]
1044    fn test_resolve_symbol_contains_single() {
1045        let syms = known(&["parse_config", "build_artifact"]);
1046        let result = resolve_symbol(syms.iter(), "config", &SymbolMatchMode::Contains);
1047        assert_eq!(result.unwrap(), "parse_config");
1048    }
1049
1050    #[test]
1051    fn test_resolve_symbol_contains_no_match() {
1052        let syms = known(&["parse_config", "build_artifact"]);
1053        let err = resolve_symbol(syms.iter(), "deploy", &SymbolMatchMode::Contains).unwrap_err();
1054        assert!(matches!(err, GraphError::SymbolNotFound { .. }));
1055    }
1056
1057    #[test]
1058    fn test_incoming_chain_order_two_hops() {
1059        // Graph: A calls B calls C.  Focus = C, follow_depth = 2.
1060        //
1061        // Expected chains after reverse():
1062        //   depth-0 chain: [B, A, C]  -- immediate caller first, then outermost, then focus
1063        //   depth-1 chain: [A, B]     -- A calls B
1064        //
1065        // This test pins the ordering so that a missing reverse() or an off-by-one in the
1066        // inner-loop push would be caught: chain[1] must be "A" (outermost), not "B" again.
1067        let analysis = make_analysis(
1068            vec![("A", 1), ("B", 10), ("C", 20)],
1069            vec![("A", "B", 2), ("B", "C", 15)],
1070        );
1071        let graph =
1072            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1073                .expect("Failed to build graph");
1074
1075        let chains = graph
1076            .find_incoming_chains("C", 2)
1077            .expect("Failed to find incoming chains");
1078
1079        assert!(
1080            !chains.is_empty(),
1081            "Expected at least one incoming chain for C"
1082        );
1083
1084        // The 2-hop chain has 3 elements: [immediate_caller, outermost_caller, focus].
1085        let chain = chains
1086            .iter()
1087            .find(|c| c.chain.len() == 3)
1088            .expect("Expected a 3-element chain");
1089
1090        assert_eq!(
1091            chain.chain[0].0, "B",
1092            "chain[0] should be immediate caller B, got {}",
1093            chain.chain[0].0
1094        );
1095        assert_eq!(
1096            chain.chain[1].0, "A",
1097            "chain[1] should be outermost caller A, got {}",
1098            chain.chain[1].0
1099        );
1100        assert_eq!(
1101            chain.chain[2].0, "C",
1102            "chain[2] should be focus node C, got {}",
1103            chain.chain[2].0
1104        );
1105    }
1106
1107    // ---- resolve_symbol_indexed tests ----
1108
1109    #[test]
1110    fn test_insensitive_resolve_via_index() {
1111        // Arrange: build a CallGraph with known symbols
1112        let analysis = make_analysis(
1113            vec![("ParseConfig", 1), ("parse_args", 5)],
1114            vec![("ParseConfig", "parse_args", 10)],
1115        );
1116        let graph =
1117            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1118                .expect("Failed to build graph");
1119
1120        // Act: resolve using insensitive mode via the indexed method
1121        let result = graph
1122            .resolve_symbol_indexed("parseconfig", &SymbolMatchMode::Insensitive)
1123            .expect("Should resolve ParseConfig");
1124
1125        // Assert: O(1) lookup via lowercase_index returns the original symbol
1126        assert_eq!(result, "ParseConfig");
1127    }
1128
1129    #[test]
1130    fn test_prefix_resolve_via_index() {
1131        // Arrange: build a CallGraph with multiple symbols matching a prefix
1132        let analysis = make_analysis(
1133            vec![("parse_config", 1), ("parse_args", 5), ("build", 10)],
1134            vec![],
1135        );
1136        let graph =
1137            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1138                .expect("Failed to build graph");
1139
1140        // Act: resolve using prefix mode via the indexed method
1141        let err = graph
1142            .resolve_symbol_indexed("parse", &SymbolMatchMode::Prefix)
1143            .unwrap_err();
1144
1145        // Assert: multiple candidates found
1146        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1147        if let GraphError::MultipleCandidates { candidates, .. } = err {
1148            assert_eq!(candidates.len(), 2);
1149        }
1150    }
1151
1152    #[test]
1153    fn test_insensitive_case_collision_returns_multiple_candidates() {
1154        // Arrange: two symbols that differ only by case map to the same lowercase key
1155        let analysis = make_analysis(vec![("Foo", 1), ("foo", 5)], vec![("Foo", "foo", 10)]);
1156        let graph =
1157            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1158                .expect("Failed to build graph");
1159
1160        // Act: insensitive lookup for "foo" hits both Foo and foo
1161        let err = graph
1162            .resolve_symbol_indexed("foo", &SymbolMatchMode::Insensitive)
1163            .unwrap_err();
1164
1165        // Assert: MultipleCandidates returned for case collision
1166        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1167        if let GraphError::MultipleCandidates { candidates, .. } = err {
1168            assert_eq!(candidates.len(), 2);
1169        }
1170    }
1171
1172    #[test]
1173    fn test_contains_resolve_via_index() {
1174        // Arrange: symbols where two match the query substring; one does not
1175        let analysis = make_analysis(
1176            vec![("parse_config", 1), ("build_config", 5), ("run", 10)],
1177            vec![],
1178        );
1179        let graph =
1180            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1181                .expect("Failed to build graph");
1182
1183        // Act: resolve using contains mode; "config" matches parse_config and build_config
1184        let err = graph
1185            .resolve_symbol_indexed("config", &SymbolMatchMode::Contains)
1186            .unwrap_err();
1187
1188        // Assert: both matching symbols returned as MultipleCandidates
1189        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1190        if let GraphError::MultipleCandidates { candidates, .. } = err {
1191            let mut sorted = candidates.clone();
1192            sorted.sort();
1193            assert_eq!(sorted, vec!["build_config", "parse_config"]);
1194        }
1195    }
1196}
code_analyze_core/graph.rs

code_analyze_core/
graph.rs
