aptu_coder_core/
graph.rs

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

aptu_coder_core/
graph.rs
