1use std::cmp::Ordering;
4use std::collections::{BTreeMap, BTreeSet, VecDeque};
5use std::time::{Duration, Instant};
6
7use code_system_graph_model::{
8 CommunityId, Edge, EdgeId, EdgeKind, EpistemicStatus, Evidence, Node, NodeId, NodeKind, RepoFreshnessState, RepoId, TraceSegment
9};
10use schemars::JsonSchema;
11use serde::{Deserialize, Serialize};
12use thiserror::Error;
13
14const MAX_SEARCH_RESULTS: usize = 100;
15const MAX_SEARCH_OFFSET: usize = 1_000_000;
16const MAX_TRAVERSAL_DEPTH: usize = 128;
17const MAX_TRAVERSAL_NODES: usize = 100_000;
18const MAX_TRAVERSAL_EDGES: usize = 1_000_000;
19const MAX_TRAVERSAL_TIMEOUT_MS: u64 = 60_000;
20const MAX_K_PATHS: usize = 16;
21const MIN_CONFIDENCE_FOR_WEIGHT: f64 = 0.01;
22
23#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
25pub struct SearchFilters {
26 #[serde(default)]
28 pub node_kinds: Vec<NodeKind>,
29 #[serde(default)]
31 pub repo_ids: Vec<RepoId>,
32 #[serde(default)]
34 pub workspace_nodes: Vec<NodeId>,
35 #[serde(default)]
37 pub service_ids: Vec<NodeId>,
38 #[serde(default)]
40 pub community_ids: Vec<CommunityId>,
41}
42
43#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
45pub struct SearchRequest {
46 pub query: String,
48 #[serde(default)]
50 pub filters: SearchFilters,
51 #[serde(default)]
53 pub fts_scores: BTreeMap<NodeId, f64>,
54 #[serde(default)]
56 pub centrality_scores: BTreeMap<NodeId, f64>,
57 #[serde(default)]
59 pub service_memberships: BTreeMap<NodeId, Vec<NodeId>>,
60 #[serde(default)]
62 pub community_memberships: BTreeMap<NodeId, Vec<CommunityId>>,
63 #[serde(default)]
65 pub evidence: BTreeMap<NodeId, Vec<Evidence>>,
66 #[serde(default)]
68 pub freshness: BTreeMap<RepoId, RepoFreshnessState>,
69 pub offset: usize,
71 pub limit: usize,
73}
74
75#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
77pub struct SearchExplanation {
78 pub matched_fields: Vec<String>,
80 pub exact_score: f64,
82 pub prefix_score: f64,
84 pub suffix_score: f64,
86 pub fts_score: f64,
88 pub type_score: f64,
90 pub scope_score: f64,
92 pub centrality_score: f64,
94 pub community_score: f64,
96 pub evidence_score: f64,
98 pub freshness_penalty: f64,
100}
101
102#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
104pub struct SearchHit {
105 pub node: Node,
107 pub score: f64,
109 pub explanation: SearchExplanation,
111}
112
113#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
115pub struct SearchCoverage {
116 pub input_nodes: usize,
118 pub eligible_nodes: usize,
120 pub matched_nodes: usize,
122 pub fts_scored_nodes: usize,
124 pub freshness_unknown_repositories: Vec<RepoId>,
126 pub gaps: Vec<String>,
128}
129
130#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
132pub struct AgentNextAction {
133 pub tool: String,
135 pub arguments: BTreeMap<String, String>,
137 pub rationale: String,
139}
140
141#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
143pub struct SearchReport {
144 pub hits: Vec<SearchHit>,
146 pub total_matches: usize,
148 pub offset: usize,
150 pub limit: usize,
152 pub truncated: bool,
154 pub coverage: SearchCoverage,
156 #[serde(default)]
158 pub next_actions: Vec<AgentNextAction>,
159}
160
161#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
163#[serde(rename_all = "snake_case")]
164pub enum TraversalAlgorithm {
165 Bfs,
167 Dijkstra,
169 KShortest,
171}
172
173#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
175#[serde(rename_all = "snake_case")]
176pub enum TraversalDirection {
177 Outgoing,
179 Incoming,
181 Both,
183}
184
185#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
187pub struct TraversalFilters {
188 #[serde(default)]
190 pub edge_kinds: Vec<EdgeKind>,
191 pub min_confidence: f64,
193 pub include_tests: bool,
195 pub include_generated_artifacts: bool,
197 pub environment_namespace: Option<String>,
199}
200
201impl Default for TraversalFilters {
202 fn default() -> Self {
203 Self {
204 edge_kinds: Vec::new(),
205 min_confidence: 0.0,
206 include_tests: true,
207 include_generated_artifacts: true,
208 environment_namespace: None,
209 }
210 }
211}
212
213#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize, JsonSchema)]
215pub struct EdgeKindCost {
216 pub kind: EdgeKind,
218 pub cost: f64,
220}
221
222#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
224pub struct TraversalOptions {
225 pub algorithm: TraversalAlgorithm,
227 pub direction: TraversalDirection,
229 pub max_depth: usize,
231 pub max_cross_repo_hops: usize,
233 pub node_limit: usize,
235 pub edge_limit: usize,
237 pub timeout_ms: u64,
239 pub k: usize,
241 #[serde(default)]
243 pub edge_kind_costs: Vec<EdgeKindCost>,
244}
245
246impl Default for TraversalOptions {
247 fn default() -> Self {
248 Self {
249 algorithm: TraversalAlgorithm::Bfs,
250 direction: TraversalDirection::Outgoing,
251 max_depth: 8,
252 max_cross_repo_hops: 4,
253 node_limit: 10_000,
254 edge_limit: 50_000,
255 timeout_ms: 1_000,
256 k: 1,
257 edge_kind_costs: Vec::new(),
258 }
259 }
260}
261
262#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
264pub struct TraversalRequest {
265 pub start: NodeId,
267 pub target: NodeId,
269 #[serde(default)]
271 pub filters: TraversalFilters,
272 #[serde(default)]
274 pub options: TraversalOptions,
275}
276
277#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
279#[serde(rename_all = "snake_case")]
280pub enum PathSegmentScope {
281 Local,
283 CrossRepository,
285}
286
287#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
289pub struct PathSegment {
290 pub trace: TraceSegment,
292 pub scope: PathSegmentScope,
294 pub reversed: bool,
296 pub weight: f64,
298}
299
300#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
302pub struct TraversalPath {
303 pub segments: Vec<PathSegment>,
305 pub total_weight: f64,
307 pub cross_repo_hops: usize,
309}
310
311#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize, JsonSchema)]
313pub struct TraversalLimits {
314 pub max_depth: usize,
316 pub max_cross_repo_hops: usize,
318 pub node_limit: usize,
320 pub edge_limit: usize,
322 pub timeout_ms: u64,
324 pub max_paths: usize,
326}
327
328#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, JsonSchema)]
330pub struct TraversalReport {
331 pub paths: Vec<TraversalPath>,
333 pub frontier: Vec<Node>,
335 pub candidate_unresolved_edges: Vec<Edge>,
337 pub coverage_gaps: Vec<String>,
339 pub truncated: bool,
341 pub visited_nodes: usize,
343 pub examined_edges: usize,
345 pub limits: TraversalLimits,
347}
348
349#[derive(Debug, Error, PartialEq)]
351pub enum QueryError {
352 #[error("search query must contain at least one letter or digit")]
354 EmptyQuery,
355 #[error(
357 "search limit must be in 1..={MAX_SEARCH_RESULTS} and offset must not exceed {MAX_SEARCH_OFFSET}"
358 )]
359 InvalidPagination,
360 #[error("invalid {signal} score for node `{node}`")]
362 InvalidScore {
363 signal: &'static str,
365 node: String,
367 },
368 #[error("duplicate node identifier `{0}`")]
370 DuplicateNode(String),
371 #[error("duplicate edge identifier `{0}`")]
373 DuplicateEdge(String),
374 #[error("edge `{edge}` references missing node `{node}`")]
376 DanglingEdge {
377 edge: String,
379 node: String,
381 },
382 #[error("traversal anchor `{0}` is not present")]
384 UnknownAnchor(String),
385 #[error("traversal limits are outside supported bounds")]
387 InvalidTraversalLimits,
388 #[error("minimum confidence must be finite and in the inclusive range 0..=1")]
390 InvalidMinimumConfidence,
391 #[error("edge `{0}` confidence must be finite and in the inclusive range 0..=1")]
393 InvalidEdgeConfidence(String),
394 #[error("edge-kind cost for `{0:?}` must be finite and positive")]
396 InvalidEdgeCost(EdgeKind),
397 #[error("path references missing node `{0}`")]
399 InconsistentPath(String),
400}
401
402#[must_use = "search results and validation errors must be handled"]
412pub fn search(nodes: &[Node], request: &SearchRequest) -> Result<SearchReport, QueryError> {
413 let normalized_query = normalize(&request.query);
414 validate_search(nodes, request, &normalized_query)?;
415 let distinct = distinct_nodes(nodes)?;
416 let mut unknown_freshness = BTreeSet::new();
417 let mut hits = Vec::new();
418 let mut eligible_nodes = 0;
419
420 for node in distinct.values().copied() {
421 if !matches_search_filters(node, request) {
422 continue;
423 }
424 eligible_nodes += 1;
425 if let Some(hit) = score_node(node, request, &normalized_query, &mut unknown_freshness) {
426 hits.push(hit);
427 }
428 }
429 sort_search_hits(&mut hits);
430 let total_matches = hits.len();
431 let page_end = request
432 .offset
433 .saturating_add(request.limit)
434 .min(total_matches);
435 let page = hits
436 .into_iter()
437 .skip(request.offset.min(total_matches))
438 .take(page_end.saturating_sub(request.offset))
439 .collect();
440 let coverage = search_coverage(
441 distinct.len(),
442 eligible_nodes,
443 total_matches,
444 request,
445 unknown_freshness,
446 );
447 Ok(SearchReport {
448 hits: page,
449 total_matches,
450 offset: request.offset,
451 limit: request.limit,
452 truncated: page_end < total_matches,
453 coverage,
454 next_actions: Vec::new(),
455 })
456}
457
458fn validate_search(
459 nodes: &[Node],
460 request: &SearchRequest,
461 normalized_query: &str,
462) -> Result<(), QueryError> {
463 if normalized_query.is_empty() {
464 return Err(QueryError::EmptyQuery);
465 }
466 if request.limit == 0
467 || request.limit > MAX_SEARCH_RESULTS
468 || request.offset > MAX_SEARCH_OFFSET
469 {
470 return Err(QueryError::InvalidPagination);
471 }
472 let _ = distinct_nodes(nodes)?;
473 validate_score_map(&request.fts_scores, "full-text")?;
474 validate_score_map(&request.centrality_scores, "centrality")?;
475 for (node_id, evidence) in &request.evidence {
476 if evidence
477 .iter()
478 .any(|item| !item.confidence.is_finite() || !(0.0..=1.0).contains(&item.confidence))
479 {
480 return Err(QueryError::InvalidScore {
481 signal: "evidence confidence",
482 node: node_id.as_str().to_owned(),
483 });
484 }
485 }
486 Ok(())
487}
488
489fn validate_score_map(
490 scores: &BTreeMap<NodeId, f64>,
491 signal: &'static str,
492) -> Result<(), QueryError> {
493 for (node_id, score) in scores {
494 if !score.is_finite() || *score < 0.0 {
495 return Err(QueryError::InvalidScore {
496 signal,
497 node: node_id.as_str().to_owned(),
498 });
499 }
500 }
501 Ok(())
502}
503
504fn distinct_nodes(nodes: &[Node]) -> Result<BTreeMap<NodeId, &Node>, QueryError> {
505 let mut distinct = BTreeMap::new();
506 for node in nodes {
507 if distinct.insert(node.id.clone(), node).is_some() {
508 return Err(QueryError::DuplicateNode(node.id.as_str().to_owned()));
509 }
510 }
511 Ok(distinct)
512}
513
514fn matches_search_filters(node: &Node, request: &SearchRequest) -> bool {
515 let filters = &request.filters;
516 if !filters.node_kinds.is_empty() && !filters.node_kinds.contains(&node.kind) {
517 return false;
518 }
519 if !filters.repo_ids.is_empty()
520 && node
521 .repo_id
522 .as_ref()
523 .is_none_or(|repo_id| !filters.repo_ids.contains(repo_id))
524 {
525 return false;
526 }
527 if !filters.workspace_nodes.is_empty() && !filters.workspace_nodes.contains(&node.id) {
528 return false;
529 }
530 if !membership_matches(
531 request.service_memberships.get(&node.id),
532 &filters.service_ids,
533 ) {
534 return false;
535 }
536 membership_matches(
537 request.community_memberships.get(&node.id),
538 &filters.community_ids,
539 )
540}
541
542fn membership_matches<T: PartialEq>(memberships: Option<&Vec<T>>, required: &[T]) -> bool {
543 required.is_empty()
544 || memberships.is_some_and(|values| {
545 required
546 .iter()
547 .any(|required_value| values.contains(required_value))
548 })
549}
550
551fn score_node(
552 node: &Node,
553 request: &SearchRequest,
554 query: &str,
555 unknown_freshness: &mut BTreeSet<RepoId>,
556) -> Option<SearchHit> {
557 let stable_key = normalize(&node.stable_key);
558 let label = normalize(&node.label);
559 let kind = node_kind_name(node.kind);
560 let mut explanation = lexical_explanation(query, &stable_key, &label, kind);
561 let supplied_fts = request.fts_scores.get(&node.id).copied().unwrap_or(0.0);
562 if explanation.matched_fields.is_empty() && supplied_fts <= 0.0 {
563 return None;
564 }
565 explanation.fts_score = supplied_fts.min(1.0) * 2.0;
566 explanation.type_score = type_signal(query, kind);
567 explanation.scope_score = scope_signal(node, request);
568 explanation.centrality_score = request
569 .centrality_scores
570 .get(&node.id)
571 .copied()
572 .unwrap_or(0.0)
573 .min(1.0)
574 * 0.5;
575 explanation.community_score = community_signal(node, request);
576 explanation.evidence_score = evidence_signal(node, request);
577 explanation.freshness_penalty = freshness_penalty(node, request, unknown_freshness);
578 let score = explanation_score(&explanation).max(0.0);
579 Some(SearchHit {
580 node: node.clone(),
581 score,
582 explanation,
583 })
584}
585
586fn lexical_explanation(
587 query: &str,
588 stable_key: &str,
589 label: &str,
590 kind: &str,
591) -> SearchExplanation {
592 let mut matched_fields = Vec::new();
593 let exact = stable_key == query || label == query;
594 if stable_key == query {
595 matched_fields.push("stable_key_exact".to_owned());
596 }
597 if label == query {
598 matched_fields.push("label_exact".to_owned());
599 }
600 let prefix = !exact && (stable_key.starts_with(query) || label.starts_with(query));
601 if prefix {
602 matched_fields.push("normalized_prefix".to_owned());
603 }
604 let suffix = !exact && (stable_key.ends_with(query) || label.ends_with(query));
605 if suffix {
606 matched_fields.push("normalized_suffix".to_owned());
607 }
608 if kind == query {
609 matched_fields.push("node_kind".to_owned());
610 }
611 SearchExplanation {
612 matched_fields,
613 exact_score: if exact { 4.0 } else { 0.0 },
614 prefix_score: if prefix { 1.5 } else { 0.0 },
615 suffix_score: if suffix { 1.0 } else { 0.0 },
616 fts_score: 0.0,
617 type_score: 0.0,
618 scope_score: 0.0,
619 centrality_score: 0.0,
620 community_score: 0.0,
621 evidence_score: 0.0,
622 freshness_penalty: 0.0,
623 }
624}
625
626fn type_signal(query: &str, kind: &str) -> f64 {
627 if kind == query {
628 0.5
629 } else if kind.starts_with(query) || kind.ends_with(query) {
630 0.25
631 } else {
632 0.0
633 }
634}
635
636fn scope_signal(node: &Node, request: &SearchRequest) -> f64 {
637 let mut score: f64 = 0.0;
638 if !request.filters.repo_ids.is_empty() {
639 score += 0.15;
640 }
641 if !request.filters.workspace_nodes.is_empty() {
642 score += 0.1;
643 }
644 if !request.filters.service_ids.is_empty()
645 && membership_matches(
646 request.service_memberships.get(&node.id),
647 &request.filters.service_ids,
648 )
649 {
650 score += 0.15;
651 }
652 score.min(0.4)
653}
654
655fn community_signal(node: &Node, request: &SearchRequest) -> f64 {
656 let Some(memberships) = request.community_memberships.get(&node.id) else {
657 return 0.0;
658 };
659 if request.filters.community_ids.is_empty() {
660 if memberships.is_empty() { 0.0 } else { 0.1 }
661 } else if membership_matches(Some(memberships), &request.filters.community_ids) {
662 0.4
663 } else {
664 0.0
665 }
666}
667
668fn evidence_signal(node: &Node, request: &SearchRequest) -> f64 {
669 let Some(items) = request.evidence.get(&node.id) else {
670 return 0.0;
671 };
672 if items.is_empty() {
673 return 0.0;
674 }
675 let (confidence_sum, denominator) = items.iter().fold((0.0, 0.0), |(sum, count), item| {
676 (sum + f64::from(item.confidence), count + 1.0)
677 });
678 (confidence_sum / denominator).min(1.0) * 0.75
679}
680
681fn freshness_penalty(node: &Node, request: &SearchRequest, unknown: &mut BTreeSet<RepoId>) -> f64 {
682 let Some(repo_id) = node.repo_id.as_ref() else {
683 return 0.0;
684 };
685 let Some(state) = request.freshness.get(repo_id) else {
686 unknown.insert(repo_id.clone());
687 return 0.2;
688 };
689 match state {
690 RepoFreshnessState::Fresh => 0.0,
691 RepoFreshnessState::WorkingTreeChanged => 0.05,
692 RepoFreshnessState::CommitsBehind => 0.1,
693 RepoFreshnessState::ConfigChanged
694 | RepoFreshnessState::ExtractorChanged
695 | RepoFreshnessState::CodegraphPending => 0.15,
696 RepoFreshnessState::Partial | RepoFreshnessState::Unknown => 0.2,
697 RepoFreshnessState::Corrupt => 0.4,
698 RepoFreshnessState::Unavailable => 0.5,
699 }
700}
701
702fn explanation_score(explanation: &SearchExplanation) -> f64 {
703 explanation.exact_score
704 + explanation.prefix_score
705 + explanation.suffix_score
706 + explanation.fts_score
707 + explanation.type_score
708 + explanation.scope_score
709 + explanation.centrality_score
710 + explanation.community_score
711 + explanation.evidence_score
712 - explanation.freshness_penalty
713}
714
715fn sort_search_hits(hits: &mut [SearchHit]) {
716 hits.sort_by(|left, right| {
717 right
718 .score
719 .total_cmp(&left.score)
720 .then_with(|| left.node.stable_key.cmp(&right.node.stable_key))
721 .then_with(|| left.node.id.cmp(&right.node.id))
722 });
723}
724
725fn search_coverage(
726 input_nodes: usize,
727 eligible_nodes: usize,
728 matched_nodes: usize,
729 request: &SearchRequest,
730 unknown: BTreeSet<RepoId>,
731) -> SearchCoverage {
732 let mut gaps = Vec::new();
733 if request.fts_scores.is_empty() {
734 gaps.push("Full-text scores were not provided.".to_owned());
735 }
736 if request.centrality_scores.is_empty() {
737 gaps.push("Centrality scores were not provided.".to_owned());
738 }
739 if request.evidence.is_empty() {
740 gaps.push("Node evidence was not provided.".to_owned());
741 }
742 if request.community_memberships.is_empty() {
743 gaps.push("Community memberships were not provided.".to_owned());
744 }
745 if !unknown.is_empty() {
746 gaps.push("Freshness was unavailable for one or more repositories.".to_owned());
747 }
748 SearchCoverage {
749 input_nodes,
750 eligible_nodes,
751 matched_nodes,
752 fts_scored_nodes: request.fts_scores.len(),
753 freshness_unknown_repositories: unknown.into_iter().collect(),
754 gaps,
755 }
756}
757
758fn normalize(value: &str) -> String {
759 let mut result = String::with_capacity(value.len());
760 let mut separator_pending = false;
761 for character in value.chars().flat_map(char::to_lowercase) {
762 if character.is_alphanumeric() {
763 if separator_pending && !result.is_empty() {
764 result.push(' ');
765 }
766 result.push(character);
767 separator_pending = false;
768 } else {
769 separator_pending = true;
770 }
771 }
772 result
773}
774
775fn node_kind_name(kind: NodeKind) -> &'static str {
776 match kind {
777 NodeKind::Repository => "repository",
778 NodeKind::Service => "service",
779 NodeKind::Package => "package",
780 NodeKind::Artifact => "artifact",
781 NodeKind::SymbolRef => "symbol ref",
782 NodeKind::TestCase => "test case",
783 NodeKind::HttpOperation => "http operation",
784 NodeKind::GraphqlOperation => "graphql operation",
785 NodeKind::RpcMethod => "rpc method",
786 NodeKind::EventChannel => "event channel",
787 NodeKind::EventSchema => "event schema",
788 NodeKind::Database => "database",
789 NodeKind::DatabaseTable => "database table",
790 NodeKind::DatabaseColumn => "database column",
791 NodeKind::ConfigKey => "config key",
792 NodeKind::Deployment => "deployment",
793 NodeKind::Document => "document",
794 NodeKind::Adr => "adr",
795 NodeKind::Owner => "owner",
796 NodeKind::ChangeSet => "change set",
797 NodeKind::PullRequest => "pull request",
798 NodeKind::Community => "community",
799 }
800}
801
802#[must_use = "traversal results and validation errors must be handled"]
812pub fn traverse(
813 nodes: &[Node],
814 edges: &[Edge],
815 request: &TraversalRequest,
816) -> Result<TraversalReport, QueryError> {
817 validate_traversal_request(request)?;
818 let graph = TraversalGraph::new(nodes, edges)?;
819 graph.require_anchor(&request.start)?;
820 graph.require_anchor(&request.target)?;
821 let mut runtime = TraversalRuntime::new(request);
822 let paths = if request.start == request.target {
823 vec![TraversalPath {
824 segments: Vec::new(),
825 total_weight: 0.0,
826 cross_repo_hops: 0,
827 }]
828 } else {
829 match request.options.algorithm {
830 TraversalAlgorithm::Bfs => bfs(&graph, request, &mut runtime)?,
831 TraversalAlgorithm::Dijkstra => weighted_paths(&graph, request, &mut runtime, 1)?,
832 TraversalAlgorithm::KShortest => {
833 weighted_paths(&graph, request, &mut runtime, request.options.k)?
834 }
835 }
836 };
837 build_traversal_report(&graph, request, runtime, paths)
838}
839
840fn validate_traversal_request(request: &TraversalRequest) -> Result<(), QueryError> {
841 let options = &request.options;
842 if options.max_depth == 0
843 || options.max_depth > MAX_TRAVERSAL_DEPTH
844 || options.node_limit == 0
845 || options.node_limit > MAX_TRAVERSAL_NODES
846 || options.edge_limit == 0
847 || options.edge_limit > MAX_TRAVERSAL_EDGES
848 || options.timeout_ms > MAX_TRAVERSAL_TIMEOUT_MS
849 || options.k == 0
850 || options.k > MAX_K_PATHS
851 {
852 return Err(QueryError::InvalidTraversalLimits);
853 }
854 let confidence = request.filters.min_confidence;
855 if !confidence.is_finite() || !(0.0..=1.0).contains(&confidence) {
856 return Err(QueryError::InvalidMinimumConfidence);
857 }
858 let mut cost_kinds = Vec::new();
859 for item in &options.edge_kind_costs {
860 if !item.cost.is_finite() || item.cost <= 0.0 || cost_kinds.contains(&item.kind) {
861 return Err(QueryError::InvalidEdgeCost(item.kind));
862 }
863 cost_kinds.push(item.kind);
864 }
865 Ok(())
866}
867
868struct TraversalGraph<'a> {
869 nodes: BTreeMap<NodeId, &'a Node>,
870 outgoing: BTreeMap<NodeId, Vec<&'a Edge>>,
871 incoming: BTreeMap<NodeId, Vec<&'a Edge>>,
872}
873
874impl<'a> TraversalGraph<'a> {
875 fn new(nodes: &'a [Node], edges: &'a [Edge]) -> Result<Self, QueryError> {
876 let nodes = distinct_nodes(nodes)?;
877 let mut edge_ids = BTreeSet::new();
878 let mut outgoing: BTreeMap<NodeId, Vec<&Edge>> = BTreeMap::new();
879 let mut incoming: BTreeMap<NodeId, Vec<&Edge>> = BTreeMap::new();
880 for edge in edges {
881 if !edge_ids.insert(edge.id.clone()) {
882 return Err(QueryError::DuplicateEdge(edge.id.as_str().to_owned()));
883 }
884 validate_graph_edge(edge, &nodes)?;
885 outgoing.entry(edge.source.clone()).or_default().push(edge);
886 incoming.entry(edge.target.clone()).or_default().push(edge);
887 }
888 for adjacent in outgoing.values_mut().chain(incoming.values_mut()) {
889 adjacent.sort_by(|left, right| left.id.cmp(&right.id));
890 }
891 Ok(Self {
892 nodes,
893 outgoing,
894 incoming,
895 })
896 }
897
898 fn require_anchor(&self, node_id: &NodeId) -> Result<(), QueryError> {
899 if self.nodes.contains_key(node_id) {
900 Ok(())
901 } else {
902 Err(QueryError::UnknownAnchor(node_id.as_str().to_owned()))
903 }
904 }
905
906 fn adjacent(&self, node_id: &NodeId, direction: TraversalDirection) -> Vec<Adjacent<'a>> {
907 let mut result = Vec::new();
908 if matches!(
909 direction,
910 TraversalDirection::Outgoing | TraversalDirection::Both
911 ) {
912 result.extend(
913 self.outgoing
914 .get(node_id)
915 .into_iter()
916 .flatten()
917 .map(|edge| Adjacent {
918 edge,
919 next: &edge.target,
920 reversed: false,
921 }),
922 );
923 }
924 if matches!(
925 direction,
926 TraversalDirection::Incoming | TraversalDirection::Both
927 ) {
928 result.extend(
929 self.incoming
930 .get(node_id)
931 .into_iter()
932 .flatten()
933 .map(|edge| Adjacent {
934 edge,
935 next: &edge.source,
936 reversed: true,
937 }),
938 );
939 }
940 result.sort_by(adjacent_order);
941 result.dedup_by(|left, right| {
942 left.edge.id == right.edge.id
943 && left.next == right.next
944 && left.reversed == right.reversed
945 });
946 result
947 }
948}
949
950fn validate_graph_edge(edge: &Edge, nodes: &BTreeMap<NodeId, &Node>) -> Result<(), QueryError> {
951 for endpoint in [&edge.source, &edge.target] {
952 if !nodes.contains_key(endpoint) {
953 return Err(QueryError::DanglingEdge {
954 edge: edge.id.as_str().to_owned(),
955 node: endpoint.as_str().to_owned(),
956 });
957 }
958 }
959 let confidence = f64::from(edge.confidence);
960 if !confidence.is_finite() || !(0.0..=1.0).contains(&confidence) {
961 return Err(QueryError::InvalidEdgeConfidence(
962 edge.id.as_str().to_owned(),
963 ));
964 }
965 Ok(())
966}
967
968#[derive(Clone, Copy)]
969struct Adjacent<'a> {
970 edge: &'a Edge,
971 next: &'a NodeId,
972 reversed: bool,
973}
974
975fn adjacent_order(left: &Adjacent<'_>, right: &Adjacent<'_>) -> Ordering {
976 left.edge
977 .id
978 .cmp(&right.edge.id)
979 .then_with(|| left.next.cmp(right.next))
980 .then_with(|| left.reversed.cmp(&right.reversed))
981}
982
983#[derive(Clone)]
984struct PathState<'a> {
985 nodes: Vec<NodeId>,
986 steps: Vec<Adjacent<'a>>,
987 total_weight: f64,
988 cross_repo_hops: usize,
989}
990
991impl<'a> PathState<'a> {
992 fn start(node_id: &NodeId) -> Self {
993 Self {
994 nodes: vec![node_id.clone()],
995 steps: Vec::new(),
996 total_weight: 0.0,
997 cross_repo_hops: 0,
998 }
999 }
1000
1001 fn current(&self) -> Option<&NodeId> {
1002 self.nodes.last()
1003 }
1004
1005 fn contains(&self, node_id: &NodeId) -> bool {
1006 self.nodes.contains(node_id)
1007 }
1008
1009 fn extended(&self, adjacent: Adjacent<'a>, weight: f64, cross_repo: bool) -> Self {
1010 let mut result = self.clone();
1011 result.nodes.push(adjacent.next.clone());
1012 result.steps.push(adjacent);
1013 result.total_weight += weight;
1014 result.cross_repo_hops += usize::from(cross_repo);
1015 result
1016 }
1017}
1018
1019struct TraversalRuntime {
1020 started: Instant,
1021 timeout: Duration,
1022 observed_nodes: BTreeSet<NodeId>,
1023 examined_edges: usize,
1024 candidate_edges: BTreeMap<EdgeId, Edge>,
1025 frontier_depth: usize,
1026 frontier: BTreeSet<NodeId>,
1027 coverage_gaps: BTreeSet<String>,
1028 truncated: bool,
1029}
1030
1031impl TraversalRuntime {
1032 fn new(request: &TraversalRequest) -> Self {
1033 Self {
1034 started: Instant::now(),
1035 timeout: Duration::from_millis(request.options.timeout_ms),
1036 observed_nodes: BTreeSet::from([request.start.clone()]),
1037 examined_edges: 0,
1038 candidate_edges: BTreeMap::new(),
1039 frontier_depth: 0,
1040 frontier: BTreeSet::from([request.start.clone()]),
1041 coverage_gaps: BTreeSet::new(),
1042 truncated: false,
1043 }
1044 }
1045
1046 fn timed_out(&mut self) -> bool {
1047 if self.started.elapsed() >= self.timeout {
1048 self.truncated = true;
1049 self.coverage_gaps
1050 .insert("Traversal stopped at the timeout bound.".to_owned());
1051 true
1052 } else {
1053 false
1054 }
1055 }
1056
1057 fn examine_edge(&mut self, edge_limit: usize) -> bool {
1058 if self.examined_edges >= edge_limit {
1059 self.truncated = true;
1060 self.coverage_gaps
1061 .insert("Traversal stopped at the edge limit.".to_owned());
1062 false
1063 } else {
1064 self.examined_edges += 1;
1065 true
1066 }
1067 }
1068
1069 fn observe_node(&mut self, node_id: &NodeId, node_limit: usize) -> bool {
1070 if self.observed_nodes.contains(node_id) {
1071 return true;
1072 }
1073 if self.observed_nodes.len() >= node_limit {
1074 self.truncated = true;
1075 self.coverage_gaps
1076 .insert("Traversal stopped at the node limit.".to_owned());
1077 false
1078 } else {
1079 self.observed_nodes.insert(node_id.clone());
1080 true
1081 }
1082 }
1083
1084 fn record_frontier(&mut self, node_id: &NodeId, depth: usize) {
1085 match depth.cmp(&self.frontier_depth) {
1086 Ordering::Greater => {
1087 self.frontier_depth = depth;
1088 self.frontier.clear();
1089 self.frontier.insert(node_id.clone());
1090 }
1091 Ordering::Equal => {
1092 self.frontier.insert(node_id.clone());
1093 }
1094 Ordering::Less => {}
1095 }
1096 }
1097
1098 fn record_candidate(&mut self, edge: &Edge) {
1099 self.candidate_edges
1100 .entry(edge.id.clone())
1101 .or_insert_with(|| edge.clone());
1102 }
1103
1104 fn record_depth_bound(&mut self) {
1105 self.truncated = true;
1106 self.coverage_gaps
1107 .insert("Traversal stopped at the depth limit.".to_owned());
1108 }
1109
1110 fn record_cross_repo_bound(&mut self) {
1111 self.truncated = true;
1112 self.coverage_gaps
1113 .insert("A path branch exceeded the cross-repository hop limit.".to_owned());
1114 }
1115}
1116
1117fn bfs(
1118 graph: &TraversalGraph<'_>,
1119 request: &TraversalRequest,
1120 runtime: &mut TraversalRuntime,
1121) -> Result<Vec<TraversalPath>, QueryError> {
1122 let mut queue = VecDeque::from([PathState::start(&request.start)]);
1123 while let Some(state) = queue.pop_front() {
1124 if runtime.timed_out() {
1125 break;
1126 }
1127 let Some(current) = state.current() else {
1128 continue;
1129 };
1130 runtime.record_frontier(current, state.steps.len());
1131 if current == &request.target {
1132 return Ok(vec![materialize_path(graph, &state, request)?]);
1133 }
1134 if state.steps.len() >= request.options.max_depth {
1135 runtime.record_depth_bound();
1136 continue;
1137 }
1138 expand_bfs_state(graph, request, runtime, &state, &mut queue)?;
1139 if runtime.truncated && queue.is_empty() {
1140 break;
1141 }
1142 }
1143 Ok(Vec::new())
1144}
1145
1146fn expand_bfs_state<'a>(
1147 graph: &TraversalGraph<'a>,
1148 request: &TraversalRequest,
1149 runtime: &mut TraversalRuntime,
1150 state: &PathState<'a>,
1151 queue: &mut VecDeque<PathState<'a>>,
1152) -> Result<(), QueryError> {
1153 let Some(current) = state.current() else {
1154 return Ok(());
1155 };
1156 for adjacent in graph.adjacent(current, request.options.direction) {
1157 if runtime.timed_out() || !runtime.examine_edge(request.options.edge_limit) {
1158 break;
1159 }
1160 if !edge_passes_filters(adjacent.edge, &request.filters) {
1161 continue;
1162 }
1163 if adjacent.edge.status != EpistemicStatus::Confirmed {
1164 runtime.record_candidate(adjacent.edge);
1165 continue;
1166 }
1167 if state.contains(adjacent.next)
1168 || !node_passes_filters(graph, adjacent.next, &request.filters, runtime)
1169 {
1170 continue;
1171 }
1172 let cross_repo = segment_is_cross_repo(graph, current, adjacent.next)?;
1173 if state.cross_repo_hops + usize::from(cross_repo) > request.options.max_cross_repo_hops {
1174 runtime.record_cross_repo_bound();
1175 continue;
1176 }
1177 if !runtime.observe_node(adjacent.next, request.options.node_limit) {
1178 continue;
1179 }
1180 let weight = edge_weight(adjacent.edge, &request.options)?;
1181 queue.push_back(state.extended(adjacent, weight, cross_repo));
1182 }
1183 Ok(())
1184}
1185
1186fn weighted_paths(
1187 graph: &TraversalGraph<'_>,
1188 request: &TraversalRequest,
1189 runtime: &mut TraversalRuntime,
1190 wanted: usize,
1191) -> Result<Vec<TraversalPath>, QueryError> {
1192 let mut candidates = vec![PathState::start(&request.start)];
1193 let mut paths = Vec::new();
1194 while !candidates.is_empty() && paths.len() < wanted {
1195 if runtime.timed_out() {
1196 break;
1197 }
1198 let selected = select_best_state(&candidates);
1199 let state = candidates.remove(selected);
1200 let Some(current) = state.current() else {
1201 continue;
1202 };
1203 runtime.record_frontier(current, state.steps.len());
1204 if current == &request.target {
1205 paths.push(materialize_path(graph, &state, request)?);
1206 continue;
1207 }
1208 if state.steps.len() >= request.options.max_depth {
1209 runtime.record_depth_bound();
1210 continue;
1211 }
1212 expand_weighted_state(graph, request, runtime, &state, &mut candidates)?;
1213 }
1214 paths.sort_by(path_order);
1215 Ok(paths)
1216}
1217
1218fn select_best_state(candidates: &[PathState<'_>]) -> usize {
1219 let mut best = 0;
1220 for index in 1..candidates.len() {
1221 if path_state_order(&candidates[index], &candidates[best]) == Ordering::Less {
1222 best = index;
1223 }
1224 }
1225 best
1226}
1227
1228fn path_state_order(left: &PathState<'_>, right: &PathState<'_>) -> Ordering {
1229 left.total_weight
1230 .total_cmp(&right.total_weight)
1231 .then_with(|| left.nodes.cmp(&right.nodes))
1232 .then_with(|| {
1233 left.steps
1234 .iter()
1235 .map(|step| &step.edge.id)
1236 .cmp(right.steps.iter().map(|step| &step.edge.id))
1237 })
1238 .then_with(|| {
1239 left.steps
1240 .iter()
1241 .map(|step| step.reversed)
1242 .cmp(right.steps.iter().map(|step| step.reversed))
1243 })
1244}
1245
1246fn expand_weighted_state<'a>(
1247 graph: &TraversalGraph<'a>,
1248 request: &TraversalRequest,
1249 runtime: &mut TraversalRuntime,
1250 state: &PathState<'a>,
1251 candidates: &mut Vec<PathState<'a>>,
1252) -> Result<(), QueryError> {
1253 let Some(current) = state.current() else {
1254 return Ok(());
1255 };
1256 for adjacent in graph.adjacent(current, request.options.direction) {
1257 if runtime.timed_out() || !runtime.examine_edge(request.options.edge_limit) {
1258 break;
1259 }
1260 if !edge_passes_filters(adjacent.edge, &request.filters) {
1261 continue;
1262 }
1263 if adjacent.edge.status != EpistemicStatus::Confirmed {
1264 runtime.record_candidate(adjacent.edge);
1265 continue;
1266 }
1267 if state.contains(adjacent.next)
1268 || !node_passes_filters(graph, adjacent.next, &request.filters, runtime)
1269 {
1270 continue;
1271 }
1272 let cross_repo = segment_is_cross_repo(graph, current, adjacent.next)?;
1273 if state.cross_repo_hops + usize::from(cross_repo) > request.options.max_cross_repo_hops {
1274 runtime.record_cross_repo_bound();
1275 continue;
1276 }
1277 if !runtime.observe_node(adjacent.next, request.options.node_limit) {
1278 continue;
1279 }
1280 let weight = edge_weight(adjacent.edge, &request.options)?;
1281 candidates.push(state.extended(adjacent, weight, cross_repo));
1282 }
1283 Ok(())
1284}
1285
1286fn edge_passes_filters(edge: &Edge, filters: &TraversalFilters) -> bool {
1287 (filters.edge_kinds.is_empty() || filters.edge_kinds.contains(&edge.kind))
1288 && f64::from(edge.confidence) >= filters.min_confidence
1289}
1290
1291fn node_passes_filters(
1292 graph: &TraversalGraph<'_>,
1293 node_id: &NodeId,
1294 filters: &TraversalFilters,
1295 runtime: &mut TraversalRuntime,
1296) -> bool {
1297 let Some(node) = graph.nodes.get(node_id).copied() else {
1298 return false;
1299 };
1300 if !filters.include_tests && node.kind == NodeKind::TestCase {
1301 return false;
1302 }
1303 if !filters.include_generated_artifacts
1304 && node.kind == NodeKind::Artifact
1305 && is_generated_artifact(node)
1306 {
1307 return false;
1308 }
1309 let Some(namespace) = filters.environment_namespace.as_deref() else {
1310 return true;
1311 };
1312 if node.kind != NodeKind::Deployment {
1313 return true;
1314 }
1315 if let Some(candidate) = deployment_namespace(&node.stable_key) {
1316 candidate == namespace
1317 } else {
1318 runtime.coverage_gaps.insert(format!(
1319 "Deployment `{}` has no representable environment namespace.",
1320 node.id.as_str()
1321 ));
1322 false
1323 }
1324}
1325
1326fn deployment_namespace(stable_key: &str) -> Option<&str> {
1327 let mut parts = stable_key.splitn(4, ':');
1328 if parts.next()? != "deployment" {
1329 return None;
1330 }
1331 let _technology = parts.next()?;
1332 let namespace = parts.next()?;
1333 let _name = parts.next()?;
1334 if namespace.is_empty() {
1335 None
1336 } else {
1337 Some(namespace)
1338 }
1339}
1340
1341fn is_generated_artifact(node: &Node) -> bool {
1342 let key = node.stable_key.to_ascii_lowercase().replace('\\', "/");
1343 [
1344 "/generated/",
1345 "/target/",
1346 "/dist/",
1347 "/build/",
1348 "/vendor/",
1349 ".generated.",
1350 "_generated.",
1351 "/gen/",
1352 ]
1353 .iter()
1354 .any(|marker| key.contains(marker))
1355}
1356
1357fn segment_is_cross_repo(
1358 graph: &TraversalGraph<'_>,
1359 source: &NodeId,
1360 target: &NodeId,
1361) -> Result<bool, QueryError> {
1362 let source_node = graph
1363 .nodes
1364 .get(source)
1365 .copied()
1366 .ok_or_else(|| QueryError::InconsistentPath(source.as_str().to_owned()))?;
1367 let target_node = graph
1368 .nodes
1369 .get(target)
1370 .copied()
1371 .ok_or_else(|| QueryError::InconsistentPath(target.as_str().to_owned()))?;
1372 Ok(source_node.repo_id != target_node.repo_id)
1373}
1374
1375fn edge_weight(edge: &Edge, options: &TraversalOptions) -> Result<f64, QueryError> {
1376 let base = options
1377 .edge_kind_costs
1378 .iter()
1379 .find(|item| item.kind == edge.kind)
1380 .map_or(1.0, |item| item.cost);
1381 let confidence = f64::from(edge.confidence).max(MIN_CONFIDENCE_FOR_WEIGHT);
1382 let weight = base / confidence;
1383 if weight.is_finite() && weight > 0.0 {
1384 Ok(weight)
1385 } else {
1386 Err(QueryError::InvalidEdgeCost(edge.kind))
1387 }
1388}
1389
1390fn materialize_path(
1391 graph: &TraversalGraph<'_>,
1392 state: &PathState<'_>,
1393 request: &TraversalRequest,
1394) -> Result<TraversalPath, QueryError> {
1395 let mut segments = Vec::with_capacity(state.steps.len());
1396 for (index, step) in state.steps.iter().enumerate() {
1397 let source_id = state
1398 .nodes
1399 .get(index)
1400 .ok_or_else(|| QueryError::InconsistentPath(request.start.as_str().to_owned()))?;
1401 let target_id = state
1402 .nodes
1403 .get(index + 1)
1404 .ok_or_else(|| QueryError::InconsistentPath(request.target.as_str().to_owned()))?;
1405 let source = graph
1406 .nodes
1407 .get(source_id)
1408 .copied()
1409 .ok_or_else(|| QueryError::InconsistentPath(source_id.as_str().to_owned()))?;
1410 let target = graph
1411 .nodes
1412 .get(target_id)
1413 .copied()
1414 .ok_or_else(|| QueryError::InconsistentPath(target_id.as_str().to_owned()))?;
1415 let cross_repo = source.repo_id != target.repo_id;
1416 segments.push(PathSegment {
1417 trace: TraceSegment {
1418 source: source.clone(),
1419 edge: step.edge.clone(),
1420 target: target.clone(),
1421 },
1422 scope: if cross_repo {
1423 PathSegmentScope::CrossRepository
1424 } else {
1425 PathSegmentScope::Local
1426 },
1427 reversed: step.reversed,
1428 weight: edge_weight(step.edge, &request.options)?,
1429 });
1430 }
1431 Ok(TraversalPath {
1432 segments,
1433 total_weight: state.total_weight,
1434 cross_repo_hops: state.cross_repo_hops,
1435 })
1436}
1437
1438fn path_order(left: &TraversalPath, right: &TraversalPath) -> Ordering {
1439 left.total_weight
1440 .total_cmp(&right.total_weight)
1441 .then_with(|| left.segments.len().cmp(&right.segments.len()))
1442 .then_with(|| {
1443 left.segments
1444 .iter()
1445 .map(|segment| &segment.trace.edge.id)
1446 .cmp(right.segments.iter().map(|segment| &segment.trace.edge.id))
1447 })
1448 .then_with(|| {
1449 left.segments
1450 .iter()
1451 .map(|segment| &segment.trace.target.id)
1452 .cmp(
1453 right
1454 .segments
1455 .iter()
1456 .map(|segment| &segment.trace.target.id),
1457 )
1458 })
1459}
1460
1461fn build_traversal_report(
1462 graph: &TraversalGraph<'_>,
1463 request: &TraversalRequest,
1464 mut runtime: TraversalRuntime,
1465 paths: Vec<TraversalPath>,
1466) -> Result<TraversalReport, QueryError> {
1467 if paths.is_empty() {
1468 runtime.coverage_gaps.insert(
1469 "No confirmed path was observed within available coverage and bounds.".to_owned(),
1470 );
1471 }
1472 if !runtime.candidate_edges.is_empty() {
1473 runtime
1474 .coverage_gaps
1475 .insert("Unresolved candidate edges were excluded from confirmed paths.".to_owned());
1476 }
1477 let frontier = runtime
1478 .frontier
1479 .iter()
1480 .map(|node_id| {
1481 graph
1482 .nodes
1483 .get(node_id)
1484 .copied()
1485 .cloned()
1486 .ok_or_else(|| QueryError::InconsistentPath(node_id.as_str().to_owned()))
1487 })
1488 .collect::<Result<Vec<_>, _>>()?;
1489 Ok(TraversalReport {
1490 paths,
1491 frontier,
1492 candidate_unresolved_edges: runtime.candidate_edges.into_values().collect(),
1493 coverage_gaps: runtime.coverage_gaps.into_iter().collect(),
1494 truncated: runtime.truncated,
1495 visited_nodes: runtime.observed_nodes.len(),
1496 examined_edges: runtime.examined_edges,
1497 limits: TraversalLimits {
1498 max_depth: request.options.max_depth,
1499 max_cross_repo_hops: request.options.max_cross_repo_hops,
1500 node_limit: request.options.node_limit,
1501 edge_limit: request.options.edge_limit,
1502 timeout_ms: request.options.timeout_ms,
1503 max_paths: if request.options.algorithm == TraversalAlgorithm::KShortest {
1504 request.options.k
1505 } else {
1506 1
1507 },
1508 },
1509 })
1510}
1511
1512#[cfg(test)]
1513mod tests {
1514 use code_system_graph_model::{EdgeId, EvidenceId, Provenance};
1515
1516 use super::*;
1517
1518 fn node(id: &str, kind: NodeKind, repo: Option<&str>) -> Node {
1519 Node {
1520 id: NodeId::new(id),
1521 kind,
1522 repo_id: repo.map(RepoId::new),
1523 stable_key: id.to_owned(),
1524 label: id.trim_start_matches("node:").to_owned(),
1525 }
1526 }
1527
1528 fn edge(
1529 id: &str,
1530 source: &str,
1531 target: &str,
1532 confidence: f32,
1533 status: EpistemicStatus,
1534 ) -> Edge {
1535 Edge {
1536 id: EdgeId::new(id),
1537 source: NodeId::new(source),
1538 target: NodeId::new(target),
1539 kind: EdgeKind::CallsRemote,
1540 confidence,
1541 status,
1542 evidence: Vec::new(),
1543 }
1544 }
1545
1546 fn evidence(confidence: f32) -> Evidence {
1547 Evidence {
1548 id: EvidenceId::new("evidence:1"),
1549 repo_id: Some(RepoId::new("repo:a")),
1550 file_path: Some("src/lib.rs".to_owned()),
1551 start_line: Some(1),
1552 end_line: Some(1),
1553 extractor: "test".to_owned(),
1554 extractor_version: "1.0.0".to_owned(),
1555 provenance: Provenance::Extracted,
1556 confidence,
1557 observed_at_commit: None,
1558 content_hash: None,
1559 note: None,
1560 }
1561 }
1562
1563 fn search_request(query: &str, offset: usize, limit: usize) -> SearchRequest {
1564 SearchRequest {
1565 query: query.to_owned(),
1566 filters: SearchFilters::default(),
1567 fts_scores: BTreeMap::new(),
1568 centrality_scores: BTreeMap::new(),
1569 service_memberships: BTreeMap::new(),
1570 community_memberships: BTreeMap::new(),
1571 evidence: BTreeMap::new(),
1572 freshness: BTreeMap::new(),
1573 offset,
1574 limit,
1575 }
1576 }
1577
1578 fn traversal_request(
1579 start: &str,
1580 target: &str,
1581 algorithm: TraversalAlgorithm,
1582 ) -> TraversalRequest {
1583 TraversalRequest {
1584 start: NodeId::new(start),
1585 target: NodeId::new(target),
1586 filters: TraversalFilters::default(),
1587 options: TraversalOptions {
1588 algorithm,
1589 ..TraversalOptions::default()
1590 },
1591 }
1592 }
1593
1594 fn report_or_panic(result: Result<TraversalReport, QueryError>) -> TraversalReport {
1595 match result {
1596 Ok(report) => report,
1597 Err(error) => panic!("unexpected traversal error: {error}"),
1598 }
1599 }
1600
1601 fn search_or_panic(result: Result<SearchReport, QueryError>) -> SearchReport {
1602 match result {
1603 Ok(report) => report,
1604 Err(error) => panic!("unexpected search error: {error}"),
1605 }
1606 }
1607
1608 #[test]
1609 fn search_is_deterministic_and_paginates_without_duplicates() {
1610 let nodes = vec![
1611 node("node:alpha-b", NodeKind::Service, Some("repo:a")),
1612 node("node:alpha-a", NodeKind::Service, Some("repo:a")),
1613 node("node:alpha-c", NodeKind::Service, Some("repo:a")),
1614 ];
1615 let first = search_or_panic(search(&nodes, &search_request("alpha", 0, 2)));
1616 let second = search_or_panic(search(&nodes, &search_request("alpha", 2, 2)));
1617 let ids = first
1618 .hits
1619 .iter()
1620 .chain(&second.hits)
1621 .map(|hit| hit.node.id.as_str())
1622 .collect::<BTreeSet<_>>();
1623
1624 assert_eq!(ids.len(), 3);
1625 }
1626
1627 #[test]
1628 fn search_explains_signals_and_freshness_penalty() {
1629 let nodes = vec![
1630 node("node:billing", NodeKind::Service, Some("repo:a")),
1631 node("node:billing-old", NodeKind::Service, Some("repo:b")),
1632 ];
1633 let mut request = search_request("billing", 0, 10);
1634 request.fts_scores.insert(NodeId::new("node:billing"), 0.8);
1635 request
1636 .centrality_scores
1637 .insert(NodeId::new("node:billing"), 0.5);
1638 request
1639 .evidence
1640 .insert(NodeId::new("node:billing"), vec![evidence(0.9)]);
1641 request
1642 .freshness
1643 .insert(RepoId::new("repo:a"), RepoFreshnessState::Fresh);
1644 request
1645 .freshness
1646 .insert(RepoId::new("repo:b"), RepoFreshnessState::Unavailable);
1647 let report = search_or_panic(search(&nodes, &request));
1648
1649 assert!(
1650 report.hits[0].explanation.fts_score > 0.0
1651 && report.hits[0].explanation.centrality_score > 0.0
1652 && report.hits[0].explanation.evidence_score > 0.0
1653 && report.hits[1].explanation.freshness_penalty > 0.0
1654 );
1655 }
1656
1657 #[test]
1658 fn bfs_honors_direction_and_returns_frontier() {
1659 let nodes = vec![
1660 node("node:a", NodeKind::Service, Some("repo:a")),
1661 node("node:b", NodeKind::Service, Some("repo:a")),
1662 node("node:c", NodeKind::Service, Some("repo:a")),
1663 ];
1664 let edges = vec![
1665 edge(
1666 "edge:1",
1667 "node:a",
1668 "node:b",
1669 1.0,
1670 EpistemicStatus::Confirmed,
1671 ),
1672 edge(
1673 "edge:2",
1674 "node:b",
1675 "node:c",
1676 1.0,
1677 EpistemicStatus::Confirmed,
1678 ),
1679 ];
1680 let mut request = traversal_request("node:c", "node:a", TraversalAlgorithm::Bfs);
1681 request.options.direction = TraversalDirection::Incoming;
1682 request.options.max_depth = 1;
1683 let report = report_or_panic(traverse(&nodes, &edges, &request));
1684
1685 assert!(
1686 report.paths.is_empty()
1687 && report.truncated
1688 && report
1689 .frontier
1690 .iter()
1691 .any(|item| item.id == NodeId::new("node:b"))
1692 );
1693 }
1694
1695 #[test]
1696 fn bfs_excludes_tests_and_filters_edge_kinds() {
1697 let nodes = vec![
1698 node("node:a", NodeKind::Service, None),
1699 node("node:test", NodeKind::TestCase, None),
1700 node("node:b", NodeKind::Service, None),
1701 ];
1702 let mut validating = edge(
1703 "edge:1",
1704 "node:a",
1705 "node:test",
1706 1.0,
1707 EpistemicStatus::Confirmed,
1708 );
1709 validating.kind = EdgeKind::Validates;
1710 let edges = vec![
1711 validating,
1712 edge(
1713 "edge:2",
1714 "node:test",
1715 "node:b",
1716 1.0,
1717 EpistemicStatus::Confirmed,
1718 ),
1719 ];
1720 let mut request = traversal_request("node:a", "node:b", TraversalAlgorithm::Bfs);
1721 request.filters.include_tests = false;
1722 request.filters.edge_kinds = vec![EdgeKind::Validates, EdgeKind::CallsRemote];
1723 let report = report_or_panic(traverse(&nodes, &edges, &request));
1724
1725 assert_eq!(report.paths, Vec::new());
1726 }
1727
1728 #[test]
1729 fn dijkstra_uses_confidence_weighted_shortest_path() {
1730 let nodes = vec![
1731 node("node:a", NodeKind::Service, None),
1732 node("node:b", NodeKind::Service, None),
1733 node("node:c", NodeKind::Service, None),
1734 ];
1735 let edges = vec![
1736 edge(
1737 "edge:1",
1738 "node:a",
1739 "node:c",
1740 0.2,
1741 EpistemicStatus::Confirmed,
1742 ),
1743 edge(
1744 "edge:2",
1745 "node:a",
1746 "node:b",
1747 1.0,
1748 EpistemicStatus::Confirmed,
1749 ),
1750 edge(
1751 "edge:3",
1752 "node:b",
1753 "node:c",
1754 1.0,
1755 EpistemicStatus::Confirmed,
1756 ),
1757 ];
1758 let request = traversal_request("node:a", "node:c", TraversalAlgorithm::Dijkstra);
1759 let report = report_or_panic(traverse(&nodes, &edges, &request));
1760 let edge_ids = report.paths[0]
1761 .segments
1762 .iter()
1763 .map(|segment| segment.trace.edge.id.as_str())
1764 .collect::<Vec<_>>();
1765
1766 assert_eq!(edge_ids, vec!["edge:2", "edge:3"]);
1767 }
1768
1769 #[test]
1770 fn k_shortest_is_loopless_and_deterministic() {
1771 let nodes = vec![
1772 node("node:a", NodeKind::Service, None),
1773 node("node:b", NodeKind::Service, None),
1774 node("node:c", NodeKind::Service, None),
1775 node("node:d", NodeKind::Service, None),
1776 ];
1777 let edges = vec![
1778 edge(
1779 "edge:1",
1780 "node:a",
1781 "node:b",
1782 1.0,
1783 EpistemicStatus::Confirmed,
1784 ),
1785 edge(
1786 "edge:2",
1787 "node:b",
1788 "node:d",
1789 1.0,
1790 EpistemicStatus::Confirmed,
1791 ),
1792 edge(
1793 "edge:3",
1794 "node:a",
1795 "node:c",
1796 1.0,
1797 EpistemicStatus::Confirmed,
1798 ),
1799 edge(
1800 "edge:4",
1801 "node:c",
1802 "node:d",
1803 1.0,
1804 EpistemicStatus::Confirmed,
1805 ),
1806 edge(
1807 "edge:5",
1808 "node:b",
1809 "node:a",
1810 1.0,
1811 EpistemicStatus::Confirmed,
1812 ),
1813 ];
1814 let mut request = traversal_request("node:a", "node:d", TraversalAlgorithm::KShortest);
1815 request.options.k = 2;
1816 let first = report_or_panic(traverse(&nodes, &edges, &request));
1817 let second = report_or_panic(traverse(&nodes, &edges, &request));
1818
1819 assert_eq!(first.paths, second.paths);
1820 }
1821
1822 #[test]
1823 fn unresolved_candidates_are_never_promoted_to_paths() {
1824 let nodes = vec![
1825 node("node:a", NodeKind::Service, None),
1826 node("node:b", NodeKind::Service, None),
1827 ];
1828 let edges = vec![edge(
1829 "edge:candidate",
1830 "node:a",
1831 "node:b",
1832 1.0,
1833 EpistemicStatus::Incomplete,
1834 )];
1835 let request = traversal_request("node:a", "node:b", TraversalAlgorithm::Bfs);
1836 let report = report_or_panic(traverse(&nodes, &edges, &request));
1837
1838 assert!(report.paths.is_empty() && report.candidate_unresolved_edges.len() == 1);
1839 }
1840
1841 #[test]
1842 fn traversal_reports_node_limit_and_timeout() {
1843 let nodes = vec![
1844 node("node:a", NodeKind::Service, None),
1845 node("node:b", NodeKind::Service, None),
1846 node("node:c", NodeKind::Service, None),
1847 ];
1848 let edges = vec![
1849 edge(
1850 "edge:1",
1851 "node:a",
1852 "node:b",
1853 1.0,
1854 EpistemicStatus::Confirmed,
1855 ),
1856 edge(
1857 "edge:2",
1858 "node:b",
1859 "node:c",
1860 1.0,
1861 EpistemicStatus::Confirmed,
1862 ),
1863 ];
1864 let mut limited = traversal_request("node:a", "node:c", TraversalAlgorithm::Bfs);
1865 limited.options.node_limit = 1;
1866 let limited_report = report_or_panic(traverse(&nodes, &edges, &limited));
1867 let mut timed = traversal_request("node:a", "node:c", TraversalAlgorithm::Bfs);
1868 timed.options.timeout_ms = 0;
1869 let timed_report = report_or_panic(traverse(&nodes, &edges, &timed));
1870
1871 assert!(limited_report.truncated && timed_report.truncated);
1872 }
1873}