Skip to main content

code_system_graph_core/
query.rs

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