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