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