1use anyhow::Result;
2use serde::{Deserialize, Serialize};
3use std::collections::BTreeMap;
4use std::collections::{HashMap, HashSet, VecDeque};
5use tree_sitter::{Parser, Query, QueryCursor, StreamingIterator};
6use tsift_core::{GraphEdge, GraphNode, GraphProjection, GraphProvenance};
7
8pub mod lang;
9pub use lang::{Lang, Symbol};
10
11pub mod complexity;
12pub use complexity::{ComplexityMetrics, LanguageExtractor, LanguageRegistry};
13
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct CallSite {
16 pub callee: String,
17 pub line: usize,
18}
19
20#[derive(Debug, Clone, PartialEq, Eq)]
21pub struct CallEdge {
22 pub caller: String,
23 pub callee: String,
24 pub caller_line: usize,
25 pub call_site_line: usize,
26}
27
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub struct RouteSite {
30 pub framework: String,
31 pub method: Option<String>,
32 pub path: String,
33 pub handler: String,
34 pub line: usize,
35 pub handler_line: Option<usize>,
36}
37
38#[derive(Debug, Clone)]
39struct PendingRoute {
40 framework: String,
41 method: Option<String>,
42 path: String,
43 line: usize,
44}
45
46pub fn extract_call_sites(lang: Lang, source: &[u8]) -> Result<Vec<CallSite>> {
47 let query_str = match lang.call_query() {
48 Some(q) => q,
49 None => return Ok(Vec::new()),
50 };
51 let mut parser = Parser::new();
52 let ts_lang = lang.tree_sitter_language();
53 parser.set_language(&ts_lang)?;
54 let tree = parser
55 .parse(source, None)
56 .ok_or_else(|| anyhow::anyhow!("parse failed"))?;
57 let query = Query::new(&ts_lang, query_str)?;
58 let mut cursor = QueryCursor::new();
59 let mut sites = Vec::new();
60 let capture_names: Vec<String> = query
61 .capture_names()
62 .iter()
63 .map(|s| s.to_string())
64 .collect();
65
66 let mut matches = cursor.matches(&query, tree.root_node(), source);
67 while let Some(m) = matches.next() {
68 for capture in m.captures {
69 let name = &capture_names[capture.index as usize];
70 if name == "call.name" {
71 let callee = capture
72 .node
73 .utf8_text(source)
74 .unwrap_or("<invalid utf8>")
75 .to_string();
76 sites.push(CallSite {
77 callee,
78 line: capture.node.start_position().row,
79 });
80 }
81 }
82 }
83 Ok(sites)
84}
85
86pub fn extract_route_sites(lang: Lang, source: &[u8]) -> Result<Vec<RouteSite>> {
87 let text = std::str::from_utf8(source)?;
88 Ok(match lang {
89 #[cfg(feature = "lang-rust")]
90 Lang::Rust => extract_rust_routes(text),
91 #[cfg(feature = "lang-python")]
92 Lang::Python => extract_python_routes(text),
93 #[cfg(feature = "lang-typescript")]
94 Lang::TypeScript | Lang::Tsx => extract_typescript_routes(text),
95 #[cfg(feature = "lang-javascript")]
96 Lang::JavaScript | Lang::Jsx => extract_typescript_routes(text),
97 _ => Vec::new(),
98 })
99}
100
101fn extract_string_literal(input: &str) -> Option<(String, usize)> {
102 let mut chars = input.char_indices();
103 while let Some((start, ch)) = chars.next() {
104 if ch != '"' && ch != '\'' {
105 continue;
106 }
107 let quote = ch;
108 let mut escaped = false;
109 let mut value = String::new();
110 for (offset, current) in chars.by_ref() {
111 if escaped {
112 value.push(current);
113 escaped = false;
114 continue;
115 }
116 if current == '\\' {
117 escaped = true;
118 continue;
119 }
120 if current == quote {
121 return Some((value, offset + current.len_utf8()));
122 }
123 value.push(current);
124 }
125 return Some((input[start + quote.len_utf8()..].to_string(), input.len()));
126 }
127 None
128}
129
130fn first_identifier(input: &str) -> Option<String> {
131 let mut start = None;
132 for (idx, ch) in input.char_indices() {
133 if start.is_none() {
134 if ch == '_' || ch.is_ascii_alphabetic() {
135 start = Some(idx);
136 }
137 continue;
138 }
139 if !(ch == '_' || ch.is_ascii_alphanumeric()) {
140 let value = input[start.unwrap()..idx].to_string();
141 return (!is_handler_keyword(&value)).then_some(value);
142 }
143 }
144 start
145 .map(|idx| input[idx..].to_string())
146 .filter(|value| !is_handler_keyword(value))
147}
148
149fn is_handler_keyword(value: &str) -> bool {
150 matches!(
151 value,
152 "async" | "await" | "function" | "move" | "None" | "Some" | "lambda"
153 )
154}
155
156fn route_methods() -> &'static [&'static str] {
157 &[
158 "get", "post", "put", "patch", "delete", "head", "options", "any", "route",
159 ]
160}
161
162fn parse_wrapped_handler(input: &str) -> (Option<String>, Option<String>) {
163 for method in route_methods() {
164 let needle = format!("{method}(");
165 if let Some(pos) = input.find(&needle) {
166 let inside = &input[pos + needle.len()..];
167 return (
168 Some((*method).to_string()),
169 first_identifier(inside).or_else(|| Some("<inline>".to_string())),
170 );
171 }
172 }
173 (None, first_identifier(input))
174}
175
176fn parse_rust_fn_name(line: &str) -> Option<String> {
177 let pos = line.find("fn ")?;
178 first_identifier(&line[pos + 3..])
179}
180
181fn parse_route_attribute(line: &str, framework: &str) -> Option<PendingRoute> {
182 let trimmed = line.trim_start();
183 let rest = trimmed.strip_prefix("#[")?;
184 for method in route_methods() {
185 let Some(method_rest) = rest.strip_prefix(method) else {
186 continue;
187 };
188 if !method_rest.trim_start().starts_with('(') {
189 continue;
190 }
191 let (path, _) = extract_string_literal(method_rest)?;
192 return Some(PendingRoute {
193 framework: framework.to_string(),
194 method: Some((*method).to_string()),
195 path,
196 line: 0,
197 });
198 }
199 None
200}
201
202fn extract_rust_routes(text: &str) -> Vec<RouteSite> {
203 let mut routes = Vec::new();
204 let mut pending = Vec::<PendingRoute>::new();
205
206 for (line_idx, line) in text.lines().enumerate() {
207 if let Some(mut attr) = parse_route_attribute(line, "actix") {
208 attr.line = line_idx;
209 if let Some(handler) = parse_rust_fn_name(line) {
210 routes.push(RouteSite {
211 framework: attr.framework,
212 method: attr.method,
213 path: attr.path,
214 handler,
215 line: attr.line,
216 handler_line: Some(line_idx),
217 });
218 } else {
219 pending.push(attr);
220 }
221 } else if !pending.is_empty()
222 && let Some(handler) = parse_rust_fn_name(line)
223 {
224 for attr in pending.drain(..) {
225 routes.push(RouteSite {
226 framework: attr.framework,
227 method: attr.method,
228 path: attr.path,
229 handler: handler.clone(),
230 line: attr.line,
231 handler_line: Some(line_idx),
232 });
233 }
234 }
235
236 if let Some(route_pos) = line.find(".route(") {
237 let route_args = &line[route_pos + ".route(".len()..];
238 if let Some((path, end_offset)) = extract_string_literal(route_args) {
239 let args_after_path = &route_args[end_offset..];
240 let (method, handler) = parse_wrapped_handler(args_after_path);
241 if let Some(handler) = handler {
242 routes.push(RouteSite {
243 framework: "axum".to_string(),
244 method: method.or_else(|| Some("route".to_string())),
245 path,
246 handler,
247 line: line_idx,
248 handler_line: None,
249 });
250 }
251 }
252 }
253 }
254
255 routes
256}
257
258fn parse_python_def_name(line: &str) -> Option<String> {
259 let trimmed = line.trim_start();
260 let rest = trimmed
261 .strip_prefix("async def ")
262 .or_else(|| trimmed.strip_prefix("def "))?;
263 first_identifier(rest)
264}
265
266fn parse_python_route_decorator(line: &str) -> Option<PendingRoute> {
267 let trimmed = line.trim_start();
268 let rest = trimmed.strip_prefix('@')?;
269 let dot = rest.find('.')?;
270 let after_dot = &rest[dot + 1..];
271 for method in route_methods() {
272 let Some(method_rest) = after_dot.strip_prefix(method) else {
273 continue;
274 };
275 if !method_rest.trim_start().starts_with('(') {
276 continue;
277 }
278 let (path, _) = extract_string_literal(method_rest)?;
279 let framework = if *method == "route" {
280 "flask"
281 } else {
282 "fastapi"
283 };
284 return Some(PendingRoute {
285 framework: framework.to_string(),
286 method: Some((*method).to_string()),
287 path,
288 line: 0,
289 });
290 }
291 None
292}
293
294fn extract_python_routes(text: &str) -> Vec<RouteSite> {
295 let mut routes = Vec::new();
296 let mut pending = Vec::<PendingRoute>::new();
297
298 for (line_idx, line) in text.lines().enumerate() {
299 if let Some(mut route) = parse_python_route_decorator(line) {
300 route.line = line_idx;
301 pending.push(route);
302 continue;
303 }
304
305 if !pending.is_empty()
306 && let Some(handler) = parse_python_def_name(line)
307 {
308 for route in pending.drain(..) {
309 routes.push(RouteSite {
310 framework: route.framework,
311 method: route.method,
312 path: route.path,
313 handler: handler.clone(),
314 line: route.line,
315 handler_line: Some(line_idx),
316 });
317 }
318 }
319 }
320
321 routes
322}
323
324fn parse_ts_method_name(line: &str) -> Option<String> {
325 let trimmed = line.trim_start();
326 first_identifier(trimmed)
327}
328
329fn parse_ts_route_decorator(line: &str) -> Option<PendingRoute> {
330 let trimmed = line.trim_start();
331 let rest = trimmed.strip_prefix('@')?;
332 for method in route_methods() {
333 let mut chars = method.chars();
334 let title = match chars.next() {
335 Some(first) => format!("{}{}", first.to_ascii_uppercase(), chars.as_str()),
336 None => continue,
337 };
338 let Some(method_rest) = rest.strip_prefix(&title) else {
339 continue;
340 };
341 if !method_rest.trim_start().starts_with('(') {
342 continue;
343 }
344 let (path, _) = extract_string_literal(method_rest)?;
345 return Some(PendingRoute {
346 framework: "nestjs".to_string(),
347 method: Some((*method).to_string()),
348 path,
349 line: 0,
350 });
351 }
352 None
353}
354
355fn parse_ts_router_call(line: &str, line_idx: usize) -> Option<RouteSite> {
356 for method in route_methods() {
357 if *method == "route" {
358 continue;
359 }
360 let needle = format!(".{method}(");
361 let Some(pos) = line.find(&needle) else {
362 continue;
363 };
364 let args = &line[pos + needle.len()..];
365 let (path, end_offset) = extract_string_literal(args)?;
366 let handler = args[end_offset..]
367 .split_once(',')
368 .and_then(|(_, rest)| first_identifier(rest))
369 .unwrap_or_else(|| "<inline>".to_string());
370 return Some(RouteSite {
371 framework: "express".to_string(),
372 method: Some((*method).to_string()),
373 path,
374 handler,
375 line: line_idx,
376 handler_line: None,
377 });
378 }
379 None
380}
381
382fn extract_typescript_routes(text: &str) -> Vec<RouteSite> {
383 let mut routes = Vec::new();
384 let mut pending = Vec::<PendingRoute>::new();
385
386 for (line_idx, line) in text.lines().enumerate() {
387 if let Some(mut route) = parse_ts_route_decorator(line) {
388 route.line = line_idx;
389 pending.push(route);
390 continue;
391 }
392
393 if !pending.is_empty()
394 && let Some(handler) = parse_ts_method_name(line)
395 {
396 for route in pending.drain(..) {
397 routes.push(RouteSite {
398 framework: route.framework,
399 method: route.method,
400 path: route.path,
401 handler: handler.clone(),
402 line: route.line,
403 handler_line: Some(line_idx),
404 });
405 }
406 }
407
408 if let Some(route) = parse_ts_router_call(line, line_idx) {
409 routes.push(route);
410 }
411 }
412
413 routes
414}
415
416pub fn resolve_edges(symbols: &[Symbol], call_sites: &[CallSite]) -> Vec<CallEdge> {
417 let mut edges = Vec::new();
418 for site in call_sites {
419 let caller = symbols
420 .iter()
421 .filter(|s| s.kind == "function" || s.kind == "class" || s.kind == "mod")
422 .filter(|s| site.line >= s.line && site.line <= s.end_line)
423 .min_by_key(|s| s.end_line - s.line);
424 if let Some(caller) = caller {
425 edges.push(CallEdge {
426 caller: caller.name.clone(),
427 callee: site.callee.clone(),
428 caller_line: caller.line,
429 call_site_line: site.line,
430 });
431 }
432 }
433 edges
434}
435
436pub fn code_symbol_node_id(name: &str) -> String {
437 format!("code.symbol:{name}")
438}
439
440pub fn code_route_node_id(framework: &str, method: Option<&str>, path: &str) -> String {
441 format!(
442 "code.route:{}:{}:{}",
443 framework,
444 method.unwrap_or("any"),
445 path
446 )
447}
448
449pub fn project_call_edges(
450 edges: &[CallEdge],
451 provenance: Option<GraphProvenance>,
452) -> GraphProjection {
453 let mut nodes = BTreeMap::<String, GraphNode>::new();
454 let mut projected_edges = Vec::with_capacity(edges.len());
455
456 for edge in edges {
457 let caller_id = code_symbol_node_id(&edge.caller);
458 let callee_id = code_symbol_node_id(&edge.callee);
459 for (id, label) in [(&caller_id, &edge.caller), (&callee_id, &edge.callee)] {
460 nodes.entry(id.clone()).or_insert_with(|| {
461 let mut node = GraphNode::new(id.clone(), "code_symbol", label.clone());
462 if let Some(provenance) = provenance.clone() {
463 node = node.with_provenance(provenance);
464 }
465 node
466 });
467 }
468
469 let mut projected = GraphEdge::new(caller_id, callee_id, "calls")
470 .with_property("caller_line", edge.caller_line.to_string())
471 .with_property("call_site_line", edge.call_site_line.to_string());
472 if let Some(provenance) = provenance.clone() {
473 projected = projected.with_provenance(provenance);
474 }
475 projected_edges.push(projected);
476 }
477
478 GraphProjection {
479 nodes: nodes.into_values().collect(),
480 edges: projected_edges,
481 }
482}
483
484pub fn project_routes(
485 routes: &[RouteSite],
486 provenance: Option<GraphProvenance>,
487) -> GraphProjection {
488 let mut nodes = BTreeMap::<String, GraphNode>::new();
489 let mut projected_edges = Vec::with_capacity(routes.len());
490
491 for route in routes {
492 let route_id = code_route_node_id(&route.framework, route.method.as_deref(), &route.path);
493 let handler_id = code_symbol_node_id(&route.handler);
494 let mut route_node = GraphNode::new(
495 route_id.clone(),
496 "route",
497 format!(
498 "{} {}",
499 route.method.as_deref().unwrap_or("any").to_uppercase(),
500 route.path
501 ),
502 )
503 .with_property("framework", route.framework.clone())
504 .with_property("path", route.path.clone())
505 .with_property("handler", route.handler.clone())
506 .with_property("line", route.line.to_string());
507 if let Some(method) = &route.method {
508 route_node = route_node.with_property("method", method.clone());
509 }
510 if let Some(provenance) = provenance.clone() {
511 route_node = route_node.with_provenance(provenance);
512 }
513 nodes.entry(route_id.clone()).or_insert(route_node);
514
515 nodes.entry(handler_id.clone()).or_insert_with(|| {
516 let mut node = GraphNode::new(handler_id.clone(), "code_symbol", route.handler.clone());
517 if let Some(provenance) = provenance.clone() {
518 node = node.with_provenance(provenance);
519 }
520 node
521 });
522
523 let mut edge = GraphEdge::new(route_id, handler_id, "handled_by")
524 .with_property("route_path", route.path.clone())
525 .with_property("framework", route.framework.clone());
526 if let Some(method) = &route.method {
527 edge = edge.with_property("method", method.clone());
528 }
529 if let Some(provenance) = provenance.clone() {
530 edge = edge.with_provenance(provenance);
531 }
532 projected_edges.push(edge);
533 }
534
535 GraphProjection {
536 nodes: nodes.into_values().collect(),
537 edges: projected_edges,
538 }
539}
540
541#[derive(Debug, Clone, Serialize, Deserialize)]
542pub struct CommunityMemberRef {
543 pub file: String,
544 pub line: i64,
545 pub role: String,
546 pub peer: String,
547}
548
549#[derive(Debug, Clone, Serialize, Deserialize)]
550pub struct CommunityMember {
551 pub name: String,
552 #[serde(skip_serializing_if = "Option::is_none", default)]
553 pub file: Option<String>,
554 #[serde(skip_serializing_if = "Option::is_none", default)]
555 pub line: Option<i64>,
556 #[serde(skip_serializing_if = "Vec::is_empty", default)]
557 pub refs: Vec<CommunityMemberRef>,
558 #[serde(skip_serializing_if = "Option::is_none", default)]
559 pub tagpath_handle: Option<String>,
560}
561
562impl CommunityMember {
563 pub fn new(name: impl Into<String>) -> Self {
564 Self {
565 name: name.into(),
566 file: None,
567 line: None,
568 refs: Vec::new(),
569 tagpath_handle: None,
570 }
571 }
572}
573
574#[derive(Debug, Clone, Serialize, Deserialize)]
575pub struct Community {
576 pub id: usize,
577 pub members: Vec<CommunityMember>,
578 pub modularity_contribution: f64,
579}
580
581#[derive(Debug, Clone, Serialize, Deserialize)]
582pub struct CommunityResult {
583 pub communities: Vec<Community>,
584 pub modularity: f64,
585 pub iterations: usize,
586 pub node_count: usize,
587 pub edge_count: usize,
588}
589
590pub fn detect_communities(edges: &[(String, String)]) -> CommunityResult {
591 if edges.is_empty() {
592 return CommunityResult {
593 communities: Vec::new(),
594 modularity: 0.0,
595 iterations: 0,
596 node_count: 0,
597 edge_count: 0,
598 };
599 }
600
601 let mut node_vec: Vec<String> = Vec::new();
602 let mut node_idx: HashMap<String, usize> = HashMap::new();
603 for (a, b) in edges {
604 for name in [a, b] {
605 if !node_idx.contains_key(name) {
606 node_idx.insert(name.clone(), node_vec.len());
607 node_vec.push(name.clone());
608 }
609 }
610 }
611 let n = node_vec.len();
612
613 let mut adj: Vec<HashSet<usize>> = vec![HashSet::new(); n];
614 for (a, b) in edges {
615 let ai = node_idx[a];
616 let bi = node_idx[b];
617 if ai != bi {
618 adj[ai].insert(bi);
619 adj[bi].insert(ai);
620 }
621 }
622
623 let degree: Vec<f64> = adj.iter().map(|nb| nb.len() as f64).collect();
624 let m = degree.iter().sum::<f64>() / 2.0;
625
626 if m == 0.0 {
627 let communities = node_vec
628 .iter()
629 .enumerate()
630 .map(|(i, name)| Community {
631 id: i,
632 members: vec![CommunityMember::new(name.clone())],
633 modularity_contribution: 0.0,
634 })
635 .collect();
636 return CommunityResult {
637 communities,
638 modularity: 0.0,
639 iterations: 0,
640 node_count: n,
641 edge_count: 0,
642 };
643 }
644
645 let mut community: Vec<usize> = (0..n).collect();
646 let mut comm_degree: Vec<f64> = degree.clone();
647
648 let mut iterations = 0;
649 loop {
650 let mut improved = false;
651 iterations += 1;
652
653 for i in 0..n {
654 let cur_c = community[i];
655 let ki = degree[i];
656
657 let ki_in_cur = adj[i].iter().filter(|&&nb| community[nb] == cur_c).count() as f64;
658 let cur_gain = ki_in_cur / m - ki * (comm_degree[cur_c] - ki) / (2.0 * m * m);
659
660 let mut best_delta = 0.0f64;
661 let mut best_c = cur_c;
662
663 let mut seen_comms: HashSet<usize> = HashSet::new();
664 for &nb in &adj[i] {
665 let c = community[nb];
666 if c == cur_c || !seen_comms.insert(c) {
667 continue;
668 }
669 let ki_in_c = adj[i].iter().filter(|&&nb2| community[nb2] == c).count() as f64;
670 let target_gain = ki_in_c / m - ki * comm_degree[c] / (2.0 * m * m);
671 let delta = target_gain - cur_gain;
672 if delta > best_delta {
673 best_delta = delta;
674 best_c = c;
675 }
676 }
677
678 if best_c != cur_c {
679 comm_degree[cur_c] -= ki;
680 comm_degree[best_c] += ki;
681 community[i] = best_c;
682 improved = true;
683 }
684 }
685
686 if !improved || iterations >= 100 {
687 break;
688 }
689 }
690
691 let mut comm_members: HashMap<usize, Vec<String>> = HashMap::new();
692 let mut comm_internal: HashMap<usize, f64> = HashMap::new();
693
694 for (i, &c) in community.iter().enumerate() {
695 comm_members.entry(c).or_default().push(node_vec[i].clone());
696 }
697 for i in 0..n {
698 for &nb in &adj[i] {
699 if nb > i && community[nb] == community[i] {
700 *comm_internal.entry(community[i]).or_insert(0.0) += 1.0;
701 }
702 }
703 }
704
705 let mut total_modularity = 0.0;
706 let mut communities: Vec<Community> = comm_members
707 .into_iter()
708 .map(|(id, mut members)| {
709 members.sort();
710 let lc = comm_internal.get(&id).copied().unwrap_or(0.0);
711 let dc = comm_degree[id];
712 let mod_contrib = lc / m - (dc / (2.0 * m)).powi(2);
713 total_modularity += mod_contrib;
714 Community {
715 id,
716 members: members.into_iter().map(CommunityMember::new).collect(),
717 modularity_contribution: mod_contrib,
718 }
719 })
720 .collect();
721
722 communities.sort_by(|a, b| b.members.len().cmp(&a.members.len()).then(a.id.cmp(&b.id)));
723
724 CommunityResult {
725 communities,
726 modularity: total_modularity,
727 iterations,
728 node_count: n,
729 edge_count: m as usize,
730 }
731}
732
733#[derive(Debug, Clone, Serialize)]
734pub struct PathNode {
735 pub name: String,
736 #[serde(skip_serializing_if = "Option::is_none", default)]
737 pub tagpath_handle: Option<String>,
738}
739
740impl PathNode {
741 pub fn new(name: impl Into<String>) -> Self {
742 Self {
743 name: name.into(),
744 tagpath_handle: None,
745 }
746 }
747}
748
749#[derive(Debug, Clone, Serialize)]
750pub struct PathResult {
751 pub from: String,
752 pub to: String,
753 pub path: Vec<PathNode>,
754 pub hops: usize,
755}
756
757pub fn shortest_path(edges: &[(String, String)], from: &str, to: &str) -> Option<PathResult> {
758 if from == to {
759 return Some(PathResult {
760 from: from.to_string(),
761 to: to.to_string(),
762 path: vec![PathNode::new(from)],
763 hops: 0,
764 });
765 }
766
767 let mut adj: HashMap<&str, HashSet<&str>> = HashMap::new();
768 for (a, b) in edges {
769 if a == b {
770 continue;
771 }
772 adj.entry(a.as_str()).or_default().insert(b.as_str());
773 adj.entry(b.as_str()).or_default().insert(a.as_str());
774 }
775
776 if !adj.contains_key(from) || !adj.contains_key(to) {
777 return None;
778 }
779
780 let mut visited: HashSet<&str> = HashSet::new();
781 let mut queue: VecDeque<&str> = VecDeque::new();
782 let mut parent: HashMap<&str, &str> = HashMap::new();
783
784 visited.insert(from);
785 queue.push_back(from);
786
787 while let Some(current) = queue.pop_front() {
788 if let Some(neighbors) = adj.get(current) {
789 for &neighbor in neighbors {
790 if visited.insert(neighbor) {
791 parent.insert(neighbor, current);
792 if neighbor == to {
793 let mut path = vec![PathNode::new(to)];
794 let mut curr = to;
795 while let Some(&p) = parent.get(curr) {
796 path.push(PathNode::new(p));
797 curr = p;
798 }
799 path.reverse();
800 let hops = path.len() - 1;
801 return Some(PathResult {
802 from: from.to_string(),
803 to: to.to_string(),
804 path,
805 hops,
806 });
807 }
808 queue.push_back(neighbor);
809 }
810 }
811 }
812 }
813
814 None
815}
816
817#[cfg(test)]
818mod tests {
819 use super::*;
820
821 #[cfg(feature = "lang-rust")]
822 #[test]
823 fn rust_direct_call() {
824 let source = b"fn helper() {}\nfn main() { helper(); }";
825 let sites = extract_call_sites(Lang::Rust, source).unwrap();
826 assert!(
827 sites.iter().any(|s| s.callee == "helper"),
828 "got: {:?}",
829 sites
830 );
831 }
832
833 #[cfg(feature = "lang-rust")]
834 #[test]
835 fn rust_method_call() {
836 let source = b"fn main() { vec.push(1); }";
837 let sites = extract_call_sites(Lang::Rust, source).unwrap();
838 assert!(sites.iter().any(|s| s.callee == "push"), "got: {:?}", sites);
839 }
840
841 #[cfg(feature = "lang-rust")]
842 #[test]
843 fn rust_scoped_call() {
844 let source = b"fn main() { Vec::new(); }";
845 let sites = extract_call_sites(Lang::Rust, source).unwrap();
846 assert!(sites.iter().any(|s| s.callee == "new"), "got: {:?}", sites);
847 }
848
849 #[cfg(feature = "lang-rust")]
850 #[test]
851 fn rust_macro_call() {
852 let source = b"fn main() { println!(\"hi\"); }";
853 let sites = extract_call_sites(Lang::Rust, source).unwrap();
854 assert!(
855 sites.iter().any(|s| s.callee == "println"),
856 "got: {:?}",
857 sites
858 );
859 }
860
861 #[cfg(feature = "lang-rust")]
862 #[test]
863 fn rust_axum_route_extracted() {
864 let source = br#"fn router() {
865 Router::new().route("/users", get(list_users));
866}
867fn list_users() {}
868"#;
869 let routes = extract_route_sites(Lang::Rust, source).unwrap();
870 assert!(routes.iter().any(|route| {
871 route.framework == "axum"
872 && route.method.as_deref() == Some("get")
873 && route.path == "/users"
874 && route.handler == "list_users"
875 }));
876 }
877
878 #[cfg(feature = "lang-rust")]
879 #[test]
880 fn rust_actix_route_attribute_extracted() {
881 let source = br#"#[post("/submit")]
882async fn submit_form() {}
883"#;
884 let routes = extract_route_sites(Lang::Rust, source).unwrap();
885 assert_eq!(routes.len(), 1);
886 assert_eq!(routes[0].framework, "actix");
887 assert_eq!(routes[0].method.as_deref(), Some("post"));
888 assert_eq!(routes[0].handler, "submit_form");
889 }
890
891 #[cfg(feature = "lang-python")]
892 #[test]
893 fn python_direct_call() {
894 let source = b"def helper(): pass\ndef main(): helper()";
895 let sites = extract_call_sites(Lang::Python, source).unwrap();
896 assert!(
897 sites.iter().any(|s| s.callee == "helper"),
898 "got: {:?}",
899 sites
900 );
901 }
902
903 #[cfg(feature = "lang-python")]
904 #[test]
905 fn python_method_call() {
906 let source = b"def main(): obj.method()";
907 let sites = extract_call_sites(Lang::Python, source).unwrap();
908 assert!(
909 sites.iter().any(|s| s.callee == "method"),
910 "got: {:?}",
911 sites
912 );
913 }
914
915 #[cfg(feature = "lang-python")]
916 #[test]
917 fn python_fastapi_route_extracted() {
918 let source = br#"@router.get("/items/{item_id}")
919def read_item(item_id: str):
920 return item_id
921"#;
922 let routes = extract_route_sites(Lang::Python, source).unwrap();
923 assert_eq!(routes.len(), 1);
924 assert_eq!(routes[0].framework, "fastapi");
925 assert_eq!(routes[0].method.as_deref(), Some("get"));
926 assert_eq!(routes[0].path, "/items/{item_id}");
927 assert_eq!(routes[0].handler, "read_item");
928 }
929
930 #[cfg(feature = "lang-typescript")]
931 #[test]
932 fn typescript_direct_call() {
933 let source = b"function helper() {}\nfunction main() { helper(); }";
934 let sites = extract_call_sites(Lang::TypeScript, source).unwrap();
935 assert!(
936 sites.iter().any(|s| s.callee == "helper"),
937 "got: {:?}",
938 sites
939 );
940 }
941
942 #[cfg(feature = "lang-typescript")]
943 #[test]
944 fn typescript_method_call() {
945 let source = b"function main() { arr.push(1); }";
946 let sites = extract_call_sites(Lang::TypeScript, source).unwrap();
947 assert!(sites.iter().any(|s| s.callee == "push"), "got: {:?}", sites);
948 }
949
950 #[cfg(feature = "lang-typescript")]
951 #[test]
952 fn typescript_express_route_extracted() {
953 let source = br#"router.post("/users", createUser);
954function createUser() {}
955"#;
956 let routes = extract_route_sites(Lang::TypeScript, source).unwrap();
957 assert_eq!(routes.len(), 1);
958 assert_eq!(routes[0].framework, "express");
959 assert_eq!(routes[0].method.as_deref(), Some("post"));
960 assert_eq!(routes[0].path, "/users");
961 assert_eq!(routes[0].handler, "createUser");
962 }
963
964 #[cfg(feature = "lang-javascript")]
965 #[test]
966 fn javascript_call() {
967 let source = b"function main() { helper(); obj.method(); }";
968 let sites = extract_call_sites(Lang::JavaScript, source).unwrap();
969 assert!(
970 sites.iter().any(|s| s.callee == "helper"),
971 "got: {:?}",
972 sites
973 );
974 assert!(
975 sites.iter().any(|s| s.callee == "method"),
976 "got: {:?}",
977 sites
978 );
979 }
980
981 #[cfg(feature = "lang-rust")]
982 #[test]
983 fn resolve_edges_basic() {
984 let symbols = vec![
985 Symbol {
986 name: "main".into(),
987 kind: "function".into(),
988 line: 1,
989 end_line: 3,
990 },
991 Symbol {
992 name: "helper".into(),
993 kind: "function".into(),
994 line: 5,
995 end_line: 7,
996 },
997 ];
998 let sites = vec![
999 CallSite {
1000 callee: "helper".into(),
1001 line: 2,
1002 },
1003 CallSite {
1004 callee: "println".into(),
1005 line: 6,
1006 },
1007 ];
1008 let edges = resolve_edges(&symbols, &sites);
1009 assert_eq!(edges.len(), 2);
1010 assert_eq!(edges[0].caller, "main");
1011 assert_eq!(edges[0].callee, "helper");
1012 assert_eq!(edges[1].caller, "helper");
1013 assert_eq!(edges[1].callee, "println");
1014 }
1015
1016 #[cfg(feature = "lang-rust")]
1017 #[test]
1018 fn resolve_edges_nested_picks_innermost() {
1019 let symbols = vec![
1020 Symbol {
1021 name: "outer".into(),
1022 kind: "function".into(),
1023 line: 0,
1024 end_line: 10,
1025 },
1026 Symbol {
1027 name: "inner".into(),
1028 kind: "function".into(),
1029 line: 2,
1030 end_line: 5,
1031 },
1032 ];
1033 let sites = vec![CallSite {
1034 callee: "foo".into(),
1035 line: 3,
1036 }];
1037 let edges = resolve_edges(&symbols, &sites);
1038 assert_eq!(edges.len(), 1);
1039 assert_eq!(edges[0].caller, "inner");
1040 }
1041
1042 #[cfg(feature = "lang-rust")]
1043 #[test]
1044 fn resolve_edges_top_level_call_excluded() {
1045 let symbols = vec![Symbol {
1046 name: "main".into(),
1047 kind: "function".into(),
1048 line: 5,
1049 end_line: 10,
1050 }];
1051 let sites = vec![CallSite {
1052 callee: "foo".into(),
1053 line: 2,
1054 }];
1055 let edges = resolve_edges(&symbols, &sites);
1056 assert!(edges.is_empty());
1057 }
1058
1059 #[test]
1060 fn project_call_edges_to_provider_neutral_substrate() {
1061 let edges = vec![CallEdge {
1062 caller: "main".into(),
1063 callee: "helper".into(),
1064 caller_line: 10,
1065 call_site_line: 12,
1066 }];
1067 let projection = project_call_edges(
1068 &edges,
1069 Some(GraphProvenance::new("tsift.index", "src/main.rs")),
1070 );
1071
1072 assert_eq!(projection.nodes.len(), 2);
1073 assert_eq!(projection.edges.len(), 1);
1074 assert!(
1075 projection
1076 .nodes
1077 .iter()
1078 .any(|node| node.id == code_symbol_node_id("main") && node.kind == "code_symbol")
1079 );
1080 }
1081
1082 #[test]
1083 fn project_routes_to_provider_neutral_substrate() {
1084 let routes = vec![RouteSite {
1085 framework: "fastapi".into(),
1086 method: Some("get".into()),
1087 path: "/items".into(),
1088 handler: "list_items".into(),
1089 line: 3,
1090 handler_line: Some(4),
1091 }];
1092 let projection = project_routes(
1093 &routes,
1094 Some(GraphProvenance::new("tsift.index", "src/api.py")),
1095 );
1096
1097 assert!(
1098 projection
1099 .nodes
1100 .iter()
1101 .any(|node| node.kind == "route" && node.label == "GET /items")
1102 );
1103 assert!(projection.edges.iter().any(|edge| edge.kind == "handled_by"
1104 && edge.properties.get("route_path") == Some(&"/items".to_string())));
1105 }
1106
1107 #[test]
1108 fn no_call_query_returns_empty() {
1109 #[cfg(feature = "lang-markdown")]
1110 {
1111 let sites = extract_call_sites(Lang::Markdown, b"# Hello").unwrap();
1112 assert!(sites.is_empty());
1113 }
1114 }
1115
1116 #[cfg(feature = "lang-rust")]
1117 #[test]
1118 fn full_roundtrip_rust() {
1119 let source = b"fn helper() { println!(\"hi\"); }\nfn main() { helper(); Vec::new(); }";
1120 let symbols = Lang::Rust.extract_symbols(source).unwrap();
1121 let sites = extract_call_sites(Lang::Rust, source).unwrap();
1122 let edges = resolve_edges(&symbols, &sites);
1123 let main_calls: Vec<&str> = edges
1124 .iter()
1125 .filter(|e| e.caller == "main")
1126 .map(|e| e.callee.as_str())
1127 .collect();
1128 assert!(
1129 main_calls.contains(&"helper"),
1130 "main should call helper, got: {:?}",
1131 main_calls
1132 );
1133 assert!(
1134 main_calls.contains(&"new"),
1135 "main should call new, got: {:?}",
1136 main_calls
1137 );
1138 }
1139
1140 fn s(a: &str, b: &str) -> (String, String) {
1141 (a.to_string(), b.to_string())
1142 }
1143
1144 #[test]
1145 fn communities_empty_graph() {
1146 let result = detect_communities(&[]);
1147 assert_eq!(result.node_count, 0);
1148 assert_eq!(result.edge_count, 0);
1149 assert!(result.communities.is_empty());
1150 assert_eq!(result.iterations, 0);
1151 }
1152
1153 #[test]
1154 fn communities_single_edge() {
1155 let edges = vec![s("a", "b")];
1156 let result = detect_communities(&edges);
1157 assert_eq!(result.node_count, 2);
1158 assert_eq!(result.edge_count, 1);
1159 assert_eq!(result.communities.len(), 1);
1160 assert_eq!(result.communities[0].members.len(), 2);
1161 }
1162
1163 #[test]
1164 fn communities_self_loop_ignored() {
1165 let edges = vec![s("a", "a"), s("a", "b")];
1166 let result = detect_communities(&edges);
1167 assert_eq!(result.node_count, 2);
1168 assert_eq!(result.edge_count, 1);
1169 }
1170
1171 #[test]
1172 fn communities_duplicate_edges_deduplicated() {
1173 let edges = vec![
1174 s("main", "helper"),
1175 s("main", "helper"),
1176 s("main", "helper"),
1177 ];
1178 let result = detect_communities(&edges);
1179 assert_eq!(result.node_count, 2);
1180 assert_eq!(result.edge_count, 1);
1181 }
1182
1183 #[test]
1184 fn communities_two_cliques_split() {
1185 let edges = vec![
1186 s("a", "b"),
1187 s("a", "c"),
1188 s("b", "c"),
1189 s("d", "e"),
1190 s("d", "f"),
1191 s("e", "f"),
1192 s("a", "d"),
1193 ];
1194 let result = detect_communities(&edges);
1195 assert_eq!(result.node_count, 6);
1196 assert_eq!(
1197 result.communities.len(),
1198 2,
1199 "expected 2 communities, got: {:?}",
1200 result
1201 .communities
1202 .iter()
1203 .map(|c| &c.members)
1204 .collect::<Vec<_>>()
1205 );
1206 assert_eq!(result.communities[0].members.len(), 3);
1207 assert_eq!(result.communities[1].members.len(), 3);
1208 assert!(result.modularity > 0.0);
1209 }
1210
1211 #[test]
1212 fn communities_disconnected_components() {
1213 let edges = vec![s("a", "b"), s("c", "d")];
1214 let result = detect_communities(&edges);
1215 assert_eq!(result.node_count, 4);
1216 assert_eq!(result.edge_count, 2);
1217 assert!(result.modularity >= 0.0);
1218 }
1219
1220 #[test]
1221 fn communities_modularity_non_negative_for_clustered() {
1222 let edges = vec![
1223 s("a", "b"),
1224 s("a", "c"),
1225 s("b", "c"),
1226 s("d", "e"),
1227 s("d", "f"),
1228 s("e", "f"),
1229 ];
1230 let result = detect_communities(&edges);
1231 assert!(result.modularity >= 0.0, "Q={}", result.modularity);
1232 }
1233
1234 fn path_names(result: &PathResult) -> Vec<&str> {
1235 result.path.iter().map(|n| n.name.as_str()).collect()
1236 }
1237
1238 #[test]
1239 fn path_direct_neighbors() {
1240 let edges = vec![s("a", "b")];
1241 let result = shortest_path(&edges, "a", "b").unwrap();
1242 assert_eq!(path_names(&result), vec!["a", "b"]);
1243 assert_eq!(result.hops, 1);
1244 assert!(result.path.iter().all(|n| n.tagpath_handle.is_none()));
1245 }
1246
1247 #[test]
1248 fn path_two_hops() {
1249 let edges = vec![s("a", "b"), s("b", "c")];
1250 let result = shortest_path(&edges, "a", "c").unwrap();
1251 assert_eq!(result.hops, 2);
1252 assert_eq!(result.path.first().unwrap().name, "a");
1253 assert_eq!(result.path.last().unwrap().name, "c");
1254 }
1255
1256 #[test]
1257 fn path_same_node() {
1258 let edges = vec![s("a", "b")];
1259 let result = shortest_path(&edges, "a", "a").unwrap();
1260 assert_eq!(path_names(&result), vec!["a"]);
1261 assert_eq!(result.hops, 0);
1262 }
1263
1264 #[test]
1265 fn path_no_connection() {
1266 let edges = vec![s("a", "b"), s("c", "d")];
1267 assert!(shortest_path(&edges, "a", "c").is_none());
1268 }
1269
1270 #[test]
1271 fn path_unknown_node() {
1272 let edges = vec![s("a", "b")];
1273 assert!(shortest_path(&edges, "a", "z").is_none());
1274 }
1275
1276 #[test]
1277 fn path_prefers_shorter() {
1278 let edges = vec![s("a", "b"), s("b", "c"), s("a", "c")];
1279 let result = shortest_path(&edges, "a", "c").unwrap();
1280 assert_eq!(result.hops, 1);
1281 }
1282
1283 #[test]
1284 fn path_self_loop_ignored() {
1285 let edges = vec![s("a", "a"), s("a", "b")];
1286 let result = shortest_path(&edges, "a", "b").unwrap();
1287 assert_eq!(result.hops, 1);
1288 }
1289}