aptu_coder_core/
graph.rs

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

aptu_coder_core/
graph.rs
