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