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