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            if let Some(neighbors) = graph_map.get(&current) {
428                for edge in neighbors {
429                    let path = &edge.path;
430                    let line = edge.line;
431                    let neighbor = &edge.neighbor_name;
432                    // Pre-allocate capacity: chain holds at most follow_depth + 2 entries
433                    // (the BFS node, up to follow_depth intermediate hops, and the neighbor).
434                    // For incoming chains we accumulate in reverse BFS order (focus first, then
435                    // deeper callers) then call reverse() at the end so that:
436                    //   chain[0]    = immediate caller of focus (closest)
437                    //   chain.last() = focus symbol (the BFS start node at depth 0) or the
438                    //                  current BFS node for deeper depth levels.
439                    // For outgoing chains the order is already focus-first.
440                    let mut chain = {
441                        let mut v = Vec::with_capacity(follow_depth as usize + 2);
442                        v.push((current.clone(), path.clone(), line));
443                        v
444                    };
445                    let mut chain_node = neighbor.clone();
446                    let mut chain_depth = depth;
447
448                    while chain_depth < follow_depth {
449                        if let Some(next_neighbors) = graph_map.get(&chain_node) {
450                            if let Some(next_edge) = next_neighbors.first() {
451                                // Advance to the next (deeper) caller before pushing, so that
452                                // for incoming chains the element pushed is the deeper ancestor
453                                // (not chain_node itself, which was already recorded or is the
454                                // immediate neighbor pushed after this loop).
455                                chain_node = next_edge.neighbor_name.clone();
456                                chain.push((
457                                    chain_node.clone(),
458                                    next_edge.path.clone(),
459                                    next_edge.line,
460                                ));
461                                chain_depth += 1;
462                            } else {
463                                break;
464                            }
465                        } else {
466                            break;
467                        }
468                    }
469
470                    if is_incoming {
471                        // Add the immediate neighbor (closest to focus) at the end,
472                        // then reverse so chain[0] = immediate neighbor.
473                        chain.push((neighbor.clone(), path.clone(), line));
474                        chain.reverse();
475                    } else {
476                        chain.push((neighbor.clone(), path.clone(), line));
477                    }
478
479                    debug_assert!(
480                        chain.len() <= follow_depth as usize + 2,
481                        "find_chains_bfs: chain length {} exceeds bound {}",
482                        chain.len(),
483                        follow_depth + 2
484                    );
485
486                    chains.push(InternalCallChain { chain });
487
488                    if !visited.contains(neighbor) && depth < follow_depth {
489                        visited.insert(neighbor.clone());
490                        queue.push_back((neighbor.clone(), depth + 1));
491                    }
492                }
493            }
494        }
495
496        Ok(chains)
497    }
498
499    #[instrument(skip(self))]
500    pub(crate) fn find_incoming_chains(
501        &self,
502        symbol: &str,
503        follow_depth: u32,
504    ) -> Result<Vec<InternalCallChain>, GraphError> {
505        self.find_chains_bfs(symbol, follow_depth, true)
506    }
507
508    #[instrument(skip(self))]
509    pub(crate) fn find_outgoing_chains(
510        &self,
511        symbol: &str,
512        follow_depth: u32,
513    ) -> Result<Vec<InternalCallChain>, GraphError> {
514        self.find_chains_bfs(symbol, follow_depth, false)
515    }
516}
517
518impl Default for CallGraph {
519    fn default() -> Self {
520        Self::new()
521    }
522}
523
524#[cfg(test)]
525mod tests {
526    use super::*;
527    use crate::types::{CallInfo, FunctionInfo};
528
529    fn make_analysis(
530        funcs: Vec<(&str, usize)>,
531        calls: Vec<(&str, &str, usize)>,
532    ) -> SemanticAnalysis {
533        SemanticAnalysis {
534            functions: funcs
535                .into_iter()
536                .map(|(n, l)| FunctionInfo {
537                    name: n.to_string(),
538                    line: l,
539                    end_line: l + 5,
540                    parameters: vec![],
541                    return_type: None,
542                })
543                .collect(),
544            classes: vec![],
545            imports: vec![],
546            references: vec![],
547            call_frequency: Default::default(),
548            calls: calls
549                .into_iter()
550                .map(|(c, e, l)| CallInfo {
551                    caller: c.to_string(),
552                    callee: e.to_string(),
553                    line: l,
554                    column: 0,
555                    arg_count: None,
556                })
557                .collect(),
558            impl_traits: vec![],
559            def_use_sites: vec![],
560        }
561    }
562
563    fn make_typed_analysis(
564        funcs: Vec<(&str, usize, Vec<String>, Option<&str>)>,
565        calls: Vec<(&str, &str, usize, Option<usize>)>,
566    ) -> SemanticAnalysis {
567        SemanticAnalysis {
568            functions: funcs
569                .into_iter()
570                .map(|(n, l, params, ret_type)| FunctionInfo {
571                    name: n.to_string(),
572                    line: l,
573                    end_line: l + 5,
574                    parameters: params,
575                    return_type: ret_type.map(|s| s.to_string()),
576                })
577                .collect(),
578            classes: vec![],
579            imports: vec![],
580            references: vec![],
581            call_frequency: Default::default(),
582            calls: calls
583                .into_iter()
584                .map(|(c, e, l, arg_count)| CallInfo {
585                    caller: c.to_string(),
586                    callee: e.to_string(),
587                    line: l,
588                    column: 0,
589                    arg_count,
590                })
591                .collect(),
592            impl_traits: vec![],
593            def_use_sites: vec![],
594        }
595    }
596
597    #[test]
598    fn test_graph_construction() {
599        let analysis = make_analysis(
600            vec![("main", 1), ("foo", 10), ("bar", 20)],
601            vec![("main", "foo", 2), ("foo", "bar", 15)],
602        );
603        let graph =
604            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
605                .expect("Failed to build graph");
606        assert!(graph.definitions.contains_key("main"));
607        assert!(graph.definitions.contains_key("foo"));
608        assert_eq!(graph.callees["main"][0].neighbor_name, "foo");
609        assert_eq!(graph.callers["foo"][0].neighbor_name, "main");
610    }
611
612    #[test]
613    fn test_find_incoming_chains_depth_zero() {
614        let analysis = make_analysis(vec![("main", 1), ("foo", 10)], vec![("main", "foo", 2)]);
615        let graph =
616            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
617                .expect("Failed to build graph");
618        assert!(
619            !graph
620                .find_incoming_chains("foo", 0)
621                .expect("Failed to find chains")
622                .is_empty()
623        );
624    }
625
626    #[test]
627    fn test_find_outgoing_chains_depth_zero() {
628        let analysis = make_analysis(vec![("main", 1), ("foo", 10)], vec![("main", "foo", 2)]);
629        let graph =
630            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
631                .expect("Failed to build graph");
632        assert!(
633            !graph
634                .find_outgoing_chains("main", 0)
635                .expect("Failed to find chains")
636                .is_empty()
637        );
638    }
639
640    #[test]
641    fn test_symbol_not_found() {
642        assert!(
643            CallGraph::new()
644                .find_incoming_chains("nonexistent", 0)
645                .is_err()
646        );
647    }
648
649    #[test]
650    fn test_same_file_preference() {
651        // Two files each define "helper". File a.rs has a call from "main" to "helper".
652        // Assert that the graph's callees for "main" point to "helper" and the callers
653        // for "helper" include an entry from a.rs (not b.rs).
654        let analysis_a = make_analysis(
655            vec![("main", 1), ("helper", 10)],
656            vec![("main", "helper", 5)],
657        );
658        let analysis_b = make_analysis(vec![("helper", 20)], vec![]);
659
660        let graph = CallGraph::build_from_results(
661            vec![
662                (PathBuf::from("a.rs"), analysis_a),
663                (PathBuf::from("b.rs"), analysis_b),
664            ],
665            &[],
666            false,
667        )
668        .expect("Failed to build graph");
669
670        // Check that main calls helper
671        assert!(graph.callees.contains_key("main"));
672        let main_callees = &graph.callees["main"];
673        assert_eq!(main_callees.len(), 1);
674        assert_eq!(main_callees[0].neighbor_name, "helper");
675
676        // Check that the call is from a.rs (same file as main)
677        assert_eq!(main_callees[0].path, PathBuf::from("a.rs"));
678
679        // Check that helper has a caller from a.rs
680        assert!(graph.callers.contains_key("helper"));
681        let helper_callers = &graph.callers["helper"];
682        assert!(
683            helper_callers
684                .iter()
685                .any(|e| e.path == PathBuf::from("a.rs"))
686        );
687    }
688
689    #[test]
690    fn test_line_proximity() {
691        // One file with "process" defined at line 10 and line 50, and a call at line 12.
692        // Assert resolution picks the definition at line 10 (closest).
693        let analysis = make_analysis(
694            vec![("process", 10), ("process", 50)],
695            vec![("main", "process", 12)],
696        );
697
698        let graph =
699            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
700                .expect("Failed to build graph");
701
702        // Check that main calls process
703        assert!(graph.callees.contains_key("main"));
704        let main_callees = &graph.callees["main"];
705        assert_eq!(main_callees.len(), 1);
706        assert_eq!(main_callees[0].neighbor_name, "process");
707
708        // Check that process has a caller from main at line 12
709        assert!(graph.callers.contains_key("process"));
710        let process_callers = &graph.callers["process"];
711        assert!(
712            process_callers
713                .iter()
714                .any(|e| e.line == 12 && e.neighbor_name == "main")
715        );
716    }
717
718    #[test]
719    fn test_scope_prefix_stripping() {
720        // One file defines "method" at line 10. Calls use "self.method", "Type::method".
721        // Assert these resolve to "method" in the graph.
722        let analysis = make_analysis(
723            vec![("method", 10)],
724            vec![
725                ("caller1", "self.method", 5),
726                ("caller2", "Type::method", 15),
727                ("caller3", "module::method", 25),
728            ],
729        );
730
731        let graph =
732            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
733                .expect("Failed to build graph");
734
735        // Check that all three callers have "method" as their callee
736        assert_eq!(graph.callees["caller1"][0].neighbor_name, "method");
737        assert_eq!(graph.callees["caller2"][0].neighbor_name, "method");
738        assert_eq!(graph.callees["caller3"][0].neighbor_name, "method");
739
740        // Check that method has three callers
741        assert!(graph.callers.contains_key("method"));
742        let method_callers = &graph.callers["method"];
743        assert_eq!(method_callers.len(), 3);
744        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller1"));
745        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller2"));
746        assert!(method_callers.iter().any(|e| e.neighbor_name == "caller3"));
747    }
748
749    #[test]
750    fn test_no_same_file_fallback() {
751        // File a.rs calls "helper" but "helper" is only defined in b.rs.
752        // Assert the call still resolves (graph has the edge).
753        let analysis_a = make_analysis(vec![("main", 1)], vec![("main", "helper", 5)]);
754        let analysis_b = make_analysis(vec![("helper", 10)], vec![]);
755
756        let graph = CallGraph::build_from_results(
757            vec![
758                (PathBuf::from("a.rs"), analysis_a),
759                (PathBuf::from("b.rs"), analysis_b),
760            ],
761            &[],
762            false,
763        )
764        .expect("Failed to build graph");
765
766        // Check that main calls helper
767        assert!(graph.callees.contains_key("main"));
768        let main_callees = &graph.callees["main"];
769        assert_eq!(main_callees.len(), 1);
770        assert_eq!(main_callees[0].neighbor_name, "helper");
771
772        // Check that helper has a caller from a.rs
773        assert!(graph.callers.contains_key("helper"));
774        let helper_callers = &graph.callers["helper"];
775        assert!(
776            helper_callers
777                .iter()
778                .any(|e| e.path == PathBuf::from("a.rs") && e.neighbor_name == "main")
779        );
780    }
781
782    #[test]
783    fn test_type_disambiguation_by_params() {
784        // Two functions named 'process' in the same file with different parameter counts.
785        // process(x: i32) at line 10, process(x: i32, y: String) at line 12.
786        // Call from main at line 11 is equidistant from both (1 line away).
787        // Type matching should prefer the 2-param version since arg_count=2.
788        let analysis = make_typed_analysis(
789            vec![
790                ("process", 10, vec!["(x: i32)".to_string()], Some("i32")),
791                (
792                    "process",
793                    12,
794                    vec!["(x: i32, y: String)".to_string()],
795                    Some("String"),
796                ),
797                ("main", 1, vec![], None),
798            ],
799            vec![("main", "process", 11, Some(2))],
800        );
801
802        let graph =
803            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
804                .expect("Failed to build graph");
805
806        // Check that main calls process
807        assert!(graph.callees.contains_key("main"));
808        let main_callees = &graph.callees["main"];
809        assert_eq!(main_callees.len(), 1);
810        assert_eq!(main_callees[0].neighbor_name, "process");
811
812        // Check that process has a caller from main at line 11
813        assert!(graph.callers.contains_key("process"));
814        let process_callers = &graph.callers["process"];
815        assert!(
816            process_callers
817                .iter()
818                .any(|e| e.line == 11 && e.neighbor_name == "main")
819        );
820    }
821
822    #[test]
823    fn test_type_disambiguation_fallback() {
824        // Two functions named 'process' with no type info (empty parameters, None return_type).
825        // Call from main at line 12 should resolve using line proximity (no regression).
826        // arg_count=None means type matching won't fire, fallback to line proximity.
827        let analysis = make_analysis(
828            vec![("process", 10), ("process", 50), ("main", 1)],
829            vec![("main", "process", 12)],
830        );
831
832        let graph =
833            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
834                .expect("Failed to build graph");
835
836        // Check that main calls process
837        assert!(graph.callees.contains_key("main"));
838        let main_callees = &graph.callees["main"];
839        assert_eq!(main_callees.len(), 1);
840        assert_eq!(main_callees[0].neighbor_name, "process");
841
842        // Check that process has a caller from main
843        assert!(graph.callers.contains_key("process"));
844        let process_callers = &graph.callers["process"];
845        assert!(
846            process_callers
847                .iter()
848                .any(|e| e.line == 12 && e.neighbor_name == "main")
849        );
850    }
851
852    #[test]
853    fn test_impl_only_filters_to_impl_sites() {
854        // Arrange: WriterImpl implements Write; plain_fn calls write directly.
855        use crate::types::ImplTraitInfo;
856        let analysis = make_analysis(
857            vec![("write", 1), ("plain_fn", 20)],
858            vec![("plain_fn", "write", 22)],
859        );
860        let impl_traits = vec![ImplTraitInfo {
861            trait_name: "Write".to_string(),
862            impl_type: "WriterImpl".to_string(),
863            path: PathBuf::from("test.rs"),
864            line: 10,
865        }];
866
867        // Act: build with impl_only=true
868        let graph = CallGraph::build_from_results(
869            vec![(PathBuf::from("test.rs"), analysis)],
870            &impl_traits,
871            true,
872        )
873        .expect("Failed to build graph");
874
875        // Assert: trait "Write" has WriterImpl as an explicit impl-trait caller edge.
876        let callers = graph
877            .callers
878            .get("Write")
879            .expect("Write must have impl caller");
880        assert_eq!(callers.len(), 1, "only impl-trait caller retained");
881        assert_eq!(callers[0].neighbor_name, "WriterImpl");
882        assert!(
883            callers[0].is_impl_trait,
884            "edge must be tagged is_impl_trait"
885        );
886
887        // Assert: regular call-site callers of "write" are filtered out by impl_only.
888        let write_callers = graph.callers.get("write").map(|v| v.len()).unwrap_or(0);
889        assert_eq!(
890            write_callers, 0,
891            "regular callers filtered when impl_only=true"
892        );
893    }
894
895    #[test]
896    fn test_impl_only_false_is_backward_compatible() {
897        // Arrange: same setup, impl_only=false -- all callers returned.
898        use crate::types::ImplTraitInfo;
899        let analysis = make_analysis(
900            vec![("write", 1), ("WriterImpl", 10), ("plain_fn", 20)],
901            vec![("WriterImpl", "write", 12), ("plain_fn", "write", 22)],
902        );
903        let impl_traits = vec![ImplTraitInfo {
904            trait_name: "Write".to_string(),
905            impl_type: "WriterImpl".to_string(),
906            path: PathBuf::from("test.rs"),
907            line: 10,
908        }];
909
910        // Act: build with impl_only=false
911        let graph = CallGraph::build_from_results(
912            vec![(PathBuf::from("test.rs"), analysis)],
913            &impl_traits,
914            false,
915        )
916        .expect("Failed to build graph");
917
918        // Assert: both call-site callers preserved
919        let callers = graph.callers.get("write").expect("write must have callers");
920        assert_eq!(
921            callers.len(),
922            2,
923            "both call-site callers should be present when impl_only=false"
924        );
925
926        // Assert: impl-trait edge is always present regardless of impl_only
927        let write_impl_callers = graph
928            .callers
929            .get("Write")
930            .expect("Write must have impl caller");
931        assert_eq!(write_impl_callers.len(), 1);
932        assert!(write_impl_callers[0].is_impl_trait);
933    }
934
935    #[test]
936    fn test_impl_only_callees_unaffected() {
937        // Arrange: WriterImpl calls write; impl_only=true should not remove callees.
938        use crate::types::ImplTraitInfo;
939        let analysis = make_analysis(
940            vec![("write", 1), ("WriterImpl", 10)],
941            vec![("WriterImpl", "write", 12)],
942        );
943        let impl_traits = vec![ImplTraitInfo {
944            trait_name: "Write".to_string(),
945            impl_type: "WriterImpl".to_string(),
946            path: PathBuf::from("test.rs"),
947            line: 10,
948        }];
949
950        let graph = CallGraph::build_from_results(
951            vec![(PathBuf::from("test.rs"), analysis)],
952            &impl_traits,
953            true,
954        )
955        .expect("Failed to build graph");
956
957        // Assert: callees of WriterImpl are NOT filtered
958        let callees = graph
959            .callees
960            .get("WriterImpl")
961            .expect("WriterImpl must have callees");
962        assert_eq!(
963            callees.len(),
964            1,
965            "callees must not be filtered by impl_only"
966        );
967        assert_eq!(callees[0].neighbor_name, "write");
968    }
969
970    // ---- resolve_symbol tests ----
971
972    fn known(names: &[&str]) -> Vec<String> {
973        names.iter().map(|s| s.to_string()).collect()
974    }
975
976    #[test]
977    fn test_resolve_symbol_exact_match() {
978        let syms = known(&["parse_config", "ParseConfig", "PARSE_CONFIG"]);
979        let result = resolve_symbol(syms.iter(), "parse_config", &SymbolMatchMode::Exact);
980        assert_eq!(result.unwrap(), "parse_config");
981    }
982
983    #[test]
984    fn test_resolve_symbol_exact_no_match() {
985        let syms = known(&["ParseConfig"]);
986        let err = resolve_symbol(syms.iter(), "parse_config", &SymbolMatchMode::Exact).unwrap_err();
987        assert!(matches!(err, GraphError::SymbolNotFound { .. }));
988    }
989
990    #[test]
991    fn test_resolve_symbol_insensitive_match() {
992        let syms = known(&["ParseConfig", "other"]);
993        let result = resolve_symbol(syms.iter(), "parseconfig", &SymbolMatchMode::Insensitive);
994        assert_eq!(result.unwrap(), "ParseConfig");
995    }
996
997    #[test]
998    fn test_resolve_symbol_insensitive_no_match() {
999        let syms = known(&["unrelated"]);
1000        let err =
1001            resolve_symbol(syms.iter(), "parseconfig", &SymbolMatchMode::Insensitive).unwrap_err();
1002        assert!(matches!(err, GraphError::SymbolNotFound { .. }));
1003    }
1004
1005    #[test]
1006    fn test_resolve_symbol_prefix_single() {
1007        let syms = known(&["parse_config", "parse_args", "build"]);
1008        let result = resolve_symbol(syms.iter(), "build", &SymbolMatchMode::Prefix);
1009        assert_eq!(result.unwrap(), "build");
1010    }
1011
1012    #[test]
1013    fn test_resolve_symbol_prefix_multiple_candidates() {
1014        let syms = known(&["parse_config", "parse_args", "build"]);
1015        let err = resolve_symbol(syms.iter(), "parse", &SymbolMatchMode::Prefix).unwrap_err();
1016        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1017        if let GraphError::MultipleCandidates { candidates, .. } = err {
1018            assert_eq!(candidates.len(), 2);
1019        }
1020    }
1021
1022    #[test]
1023    fn test_resolve_symbol_contains_single() {
1024        let syms = known(&["parse_config", "build_artifact"]);
1025        let result = resolve_symbol(syms.iter(), "config", &SymbolMatchMode::Contains);
1026        assert_eq!(result.unwrap(), "parse_config");
1027    }
1028
1029    #[test]
1030    fn test_resolve_symbol_contains_no_match() {
1031        let syms = known(&["parse_config", "build_artifact"]);
1032        let err = resolve_symbol(syms.iter(), "deploy", &SymbolMatchMode::Contains).unwrap_err();
1033        assert!(matches!(err, GraphError::SymbolNotFound { .. }));
1034    }
1035
1036    #[test]
1037    fn test_incoming_chain_order_two_hops() {
1038        // Graph: A calls B calls C.  Focus = C, follow_depth = 2.
1039        //
1040        // Expected chains after reverse():
1041        //   depth-0 chain: [B, A, C]  -- immediate caller first, then outermost, then focus
1042        //   depth-1 chain: [A, B]     -- A calls B
1043        //
1044        // This test pins the ordering so that a missing reverse() or an off-by-one in the
1045        // inner-loop push would be caught: chain[1] must be "A" (outermost), not "B" again.
1046        let analysis = make_analysis(
1047            vec![("A", 1), ("B", 10), ("C", 20)],
1048            vec![("A", "B", 2), ("B", "C", 15)],
1049        );
1050        let graph =
1051            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1052                .expect("Failed to build graph");
1053
1054        let chains = graph
1055            .find_incoming_chains("C", 2)
1056            .expect("Failed to find incoming chains");
1057
1058        assert!(
1059            !chains.is_empty(),
1060            "Expected at least one incoming chain for C"
1061        );
1062
1063        // The 2-hop chain has 3 elements: [immediate_caller, outermost_caller, focus].
1064        let chain = chains
1065            .iter()
1066            .find(|c| c.chain.len() == 3)
1067            .expect("Expected a 3-element chain");
1068
1069        assert_eq!(
1070            chain.chain[0].0, "B",
1071            "chain[0] should be immediate caller B, got {}",
1072            chain.chain[0].0
1073        );
1074        assert_eq!(
1075            chain.chain[1].0, "A",
1076            "chain[1] should be outermost caller A, got {}",
1077            chain.chain[1].0
1078        );
1079        assert_eq!(
1080            chain.chain[2].0, "C",
1081            "chain[2] should be focus node C, got {}",
1082            chain.chain[2].0
1083        );
1084    }
1085
1086    // ---- resolve_symbol_indexed tests ----
1087
1088    #[test]
1089    fn test_insensitive_resolve_via_index() {
1090        // Arrange: build a CallGraph with known symbols
1091        let analysis = make_analysis(
1092            vec![("ParseConfig", 1), ("parse_args", 5)],
1093            vec![("ParseConfig", "parse_args", 10)],
1094        );
1095        let graph =
1096            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1097                .expect("Failed to build graph");
1098
1099        // Act: resolve using insensitive mode via the indexed method
1100        let result = graph
1101            .resolve_symbol_indexed("parseconfig", &SymbolMatchMode::Insensitive)
1102            .expect("Should resolve ParseConfig");
1103
1104        // Assert: O(1) lookup via lowercase_index returns the original symbol
1105        assert_eq!(result, "ParseConfig");
1106    }
1107
1108    #[test]
1109    fn test_prefix_resolve_via_index() {
1110        // Arrange: build a CallGraph with multiple symbols matching a prefix
1111        let analysis = make_analysis(
1112            vec![("parse_config", 1), ("parse_args", 5), ("build", 10)],
1113            vec![],
1114        );
1115        let graph =
1116            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1117                .expect("Failed to build graph");
1118
1119        // Act: resolve using prefix mode via the indexed method
1120        let err = graph
1121            .resolve_symbol_indexed("parse", &SymbolMatchMode::Prefix)
1122            .unwrap_err();
1123
1124        // Assert: multiple candidates found
1125        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1126        if let GraphError::MultipleCandidates { candidates, .. } = err {
1127            assert_eq!(candidates.len(), 2);
1128        }
1129    }
1130
1131    #[test]
1132    fn test_insensitive_case_collision_returns_multiple_candidates() {
1133        // Arrange: two symbols that differ only by case map to the same lowercase key
1134        let analysis = make_analysis(vec![("Foo", 1), ("foo", 5)], vec![("Foo", "foo", 10)]);
1135        let graph =
1136            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1137                .expect("Failed to build graph");
1138
1139        // Act: insensitive lookup for "foo" hits both Foo and foo
1140        let err = graph
1141            .resolve_symbol_indexed("foo", &SymbolMatchMode::Insensitive)
1142            .unwrap_err();
1143
1144        // Assert: MultipleCandidates returned for case collision
1145        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1146        if let GraphError::MultipleCandidates { candidates, .. } = err {
1147            assert_eq!(candidates.len(), 2);
1148        }
1149    }
1150
1151    #[test]
1152    fn test_contains_resolve_via_index() {
1153        // Arrange: symbols where two match the query substring; one does not
1154        let analysis = make_analysis(
1155            vec![("parse_config", 1), ("build_config", 5), ("run", 10)],
1156            vec![],
1157        );
1158        let graph =
1159            CallGraph::build_from_results(vec![(PathBuf::from("test.rs"), analysis)], &[], false)
1160                .expect("Failed to build graph");
1161
1162        // Act: resolve using contains mode; "config" matches parse_config and build_config
1163        let err = graph
1164            .resolve_symbol_indexed("config", &SymbolMatchMode::Contains)
1165            .unwrap_err();
1166
1167        // Assert: both matching symbols returned as MultipleCandidates
1168        assert!(matches!(&err, GraphError::MultipleCandidates { .. }));
1169        if let GraphError::MultipleCandidates { candidates, .. } = err {
1170            let mut sorted = candidates.clone();
1171            sorted.sort();
1172            assert_eq!(sorted, vec!["build_config", "parse_config"]);
1173        }
1174    }
1175}
aptu_coder_core/graph.rs

aptu_coder_core/
graph.rs
