rto_graph/
query.rs

1//! The agent- and human-facing query surface over the graph.
2//!
3//! Everything here is a read-only view built from the store's typed queries,
4//! serialised under a **stable, versioned** JSON schema ([`SCHEMA`]) so agents
5//! can depend on the shape. The primitives are [`explain`] (a node and its
6//! provenance-labelled neighbourhood), [`list_kind`] (all nodes of a kind),
7//! [`path`] (a shortest path between two nodes), [`debt`] (the intent-debt marker
8//! inventory), and [`search`] (relevance-ranked node search). All return
9//! mixed-provenance results — the "one query surface" from ADR-0001 — with every
10//! edge carrying its `provenance`.
11
12use std::collections::{BTreeMap, VecDeque};
13
14use serde::Serialize;
15
16use crate::store::{Store, StoreError};
17use crate::{Edge, NodeKind, Provenance};
18
19/// The versioned schema tag emitted on every query result. Bump the version on
20/// any breaking change to the shape.
21pub const SCHEMA: &str = "roteiro.query/v1";
22
23/// A compact node summary (used in listings and as the subject of an
24/// [`Explanation`]).
25#[derive(Debug, Clone, PartialEq, Serialize)]
26pub struct NodeSummary {
27    /// Natural key.
28    pub key: String,
29    /// Kind token (e.g. `fn`, `adr`).
30    pub kind: String,
31    /// Human-facing name.
32    pub name: String,
33    /// Repository-relative path, if any.
34    pub path: Option<String>,
35    /// Language token, if any.
36    pub lang: Option<String>,
37}
38
39impl NodeSummary {
40    fn from_node(node: &crate::Node) -> Self {
41        Self {
42            key: node.key.clone(),
43            kind: node.kind.as_str().to_owned(),
44            name: node.name.clone(),
45            path: node.path.clone(),
46            lang: node.lang.clone(),
47        }
48    }
49}
50
51/// One end of an edge as seen from a subject node: the relationship, how it was
52/// produced, and the node on the other end.
53#[derive(Debug, Clone, PartialEq, Serialize)]
54pub struct EdgeRef {
55    /// Edge kind token (e.g. `calls`, `references`).
56    pub kind: String,
57    /// How the edge was produced (`derived` | `authored` | `inferred`).
58    pub provenance: &'static str,
59    /// Confidence score, present only for inferred edges.
60    pub confidence: Option<f64>,
61    /// The natural key of the node at the other end.
62    pub node: String,
63}
64
65/// A node together with its provenance-labelled neighbourhood.
66#[derive(Debug, Clone, PartialEq, Serialize)]
67pub struct Explanation {
68    /// Stable schema tag ([`SCHEMA`]).
69    pub schema: &'static str,
70    /// The subject node.
71    pub node: NodeSummary,
72    /// Structured metadata attached to the node.
73    pub meta: serde_json::Value,
74    /// Edges where the subject is the source.
75    pub outgoing: Vec<EdgeRef>,
76    /// Edges where the subject is the destination.
77    pub incoming: Vec<EdgeRef>,
78}
79
80/// A listing of all nodes of one kind.
81#[derive(Debug, Clone, PartialEq, Serialize)]
82pub struct Listing {
83    /// Stable schema tag ([`SCHEMA`]).
84    pub schema: &'static str,
85    /// The kind that was listed.
86    pub kind: String,
87    /// Matching nodes, ordered by key.
88    pub nodes: Vec<NodeSummary>,
89}
90
91/// One intent-debt finding in a [`DebtReport`].
92#[derive(Debug, Clone, PartialEq, Serialize)]
93pub struct DebtItem {
94    /// Natural key of the marker node (`marker:<path>#<line>`).
95    pub key: String,
96    /// Category token (`todo` | `fixme` | `hack` | `stub` | `deferred`).
97    pub category: String,
98    /// The marker text (the trimmed source line).
99    pub text: String,
100    /// Repository-relative path of the source file, if any.
101    pub path: Option<String>,
102    /// 1-based line number, if recorded.
103    pub line: Option<u32>,
104}
105
106/// The intent-debt inventory: every `marker` node, grouped and listed. A
107/// deterministic, provenance-`derived` view of what is incomplete or postponed.
108#[derive(Debug, Clone, PartialEq, Serialize)]
109pub struct DebtReport {
110    /// Stable schema tag ([`SCHEMA`]).
111    pub schema: &'static str,
112    /// Total markers in the report (after any category filter).
113    pub total: usize,
114    /// Count per category, ordered by category token.
115    pub by_category: BTreeMap<String, usize>,
116    /// The markers, ordered by `(path, line, key)`.
117    pub items: Vec<DebtItem>,
118}
119
120/// Inventory intent-debt markers in the graph, optionally restricted to the
121/// given `categories` (empty means all) and excluding markers whose file path
122/// matches any `ignore` glob (config `[debt] ignore` — empty means keep all).
123/// Ordered by `(path, line)` so output is stable and reads top-to-bottom per
124/// file; `total` and `by_category` reflect the retained markers only.
125///
126/// # Errors
127/// Returns [`StoreError`] on query failure.
128pub fn debt(
129    store: &Store,
130    categories: &[String],
131    ignore: &[String],
132) -> Result<DebtReport, StoreError> {
133    let filter: std::collections::BTreeSet<&str> = categories.iter().map(String::as_str).collect();
134    let mut items = Vec::new();
135    let mut by_category: BTreeMap<String, usize> = BTreeMap::new();
136    for node in store.nodes_by_kind(&NodeKind::Marker)? {
137        let category = node
138            .meta
139            .get("category")
140            .and_then(serde_json::Value::as_str)
141            .unwrap_or("other")
142            .to_owned();
143        if !filter.is_empty() && !filter.contains(category.as_str()) {
144            continue;
145        }
146        // Drop markers under an ignored path (e.g. `vendor/**`) before counting.
147        if let Some(path) = node.path.as_deref()
148            && ignore.iter().any(|glob| glob_match(glob, path))
149        {
150            continue;
151        }
152        let text = node
153            .meta
154            .get("text")
155            .and_then(serde_json::Value::as_str)
156            .unwrap_or(node.name.as_str())
157            .to_owned();
158        let line = node
159            .meta
160            .get("line")
161            .and_then(serde_json::Value::as_u64)
162            .and_then(|l| u32::try_from(l).ok());
163        *by_category.entry(category.clone()).or_default() += 1;
164        items.push(DebtItem {
165            key: node.key.clone(),
166            category,
167            text,
168            path: node.path.clone(),
169            line,
170        });
171    }
172    items.sort_by(|a, b| (&a.path, a.line, &a.key).cmp(&(&b.path, b.line, &b.key)));
173    Ok(DebtReport {
174        schema: SCHEMA,
175        total: items.len(),
176        by_category,
177        items,
178    })
179}
180
181/// Match a slash-separated `path` against a glob `pattern`, anchored end-to-end.
182/// `?` matches one non-`/` character, `*` matches any run within a single path
183/// segment, and `**` matches zero or more whole segments. Used for config
184/// `[debt] ignore` patterns (e.g. `vendor/**`, `**/generated/*`).
185#[must_use]
186fn glob_match(pattern: &str, path: &str) -> bool {
187    let pat: Vec<&str> = pattern.split('/').collect();
188    let seg: Vec<&str> = path.split('/').collect();
189    match_segments(&pat, &seg)
190}
191
192/// Anchored match of glob segments `pat` against path segments `seg`, with `**`
193/// consuming zero or more segments.
194fn match_segments(pat: &[&str], seg: &[&str]) -> bool {
195    match pat.first() {
196        None => seg.is_empty(),
197        Some(&"**") => (0..=seg.len()).any(|i| match_segments(&pat[1..], &seg[i..])),
198        Some(token) => {
199            !seg.is_empty() && match_token(token, seg[0]) && match_segments(&pat[1..], &seg[1..])
200        }
201    }
202}
203
204/// Match a single path segment `s` against a `pattern` token containing `*`
205/// (any run, no `/`) and `?` (one char, no `/`).
206fn match_token(pattern: &str, s: &str) -> bool {
207    let pat: Vec<char> = pattern.chars().collect();
208    let chars: Vec<char> = s.chars().collect();
209    match_token_chars(&pat, &chars)
210}
211
212/// Recursive char-slice matcher backing [`match_token`].
213fn match_token_chars(pat: &[char], chars: &[char]) -> bool {
214    match pat.first() {
215        None => chars.is_empty(),
216        Some('*') => (0..=chars.len()).any(|i| match_token_chars(&pat[1..], &chars[i..])),
217        Some('?') => !chars.is_empty() && match_token_chars(&pat[1..], &chars[1..]),
218        Some(&ch) => {
219            !chars.is_empty() && chars[0] == ch && match_token_chars(&pat[1..], &chars[1..])
220        }
221    }
222}
223
224/// One step along a [`Path`]: the edge traversed and the node it leads to.
225#[derive(Debug, Clone, PartialEq, Serialize)]
226pub struct PathHop {
227    /// Edge kind token (e.g. `calls`, `contains`).
228    pub kind: String,
229    /// How the edge was produced.
230    pub provenance: &'static str,
231    /// Confidence score, present only for inferred edges.
232    pub confidence: Option<f64>,
233    /// The direction the edge was traversed relative to the previous node
234    /// (`outgoing` = along the edge, `incoming` = against it).
235    pub direction: &'static str,
236    /// The natural key of the node this hop arrives at.
237    pub node: String,
238}
239
240/// A shortest path between two nodes. Edges are followed in either direction
241/// (the graph is treated as undirected for reachability), and each hop records
242/// the actual direction and provenance of the edge used.
243#[derive(Debug, Clone, PartialEq, Serialize)]
244pub struct Path {
245    /// Stable schema tag ([`SCHEMA`]).
246    pub schema: &'static str,
247    /// Natural key of the start node.
248    pub from: String,
249    /// Natural key of the goal node.
250    pub to: String,
251    /// Whether a path (including the trivial empty one) was found.
252    pub found: bool,
253    /// Number of hops (edges) in the path; `0` when `from == to`.
254    pub length: usize,
255    /// The hops from `from` to `to`, in order.
256    pub hops: Vec<PathHop>,
257}
258
259fn out_ref(edge: &Edge) -> EdgeRef {
260    EdgeRef {
261        kind: edge.kind.as_str().to_owned(),
262        provenance: edge.provenance.as_str(),
263        confidence: edge.confidence,
264        node: edge.dst.clone(),
265    }
266}
267
268fn in_ref(edge: &Edge) -> EdgeRef {
269    EdgeRef {
270        kind: edge.kind.as_str().to_owned(),
271        provenance: edge.provenance.as_str(),
272        confidence: edge.confidence,
273        node: edge.src.clone(),
274    }
275}
276
277fn sort_refs(refs: &mut [EdgeRef]) {
278    // Include provenance so edges differing only in provenance have a total,
279    // stable order; with the edge-uniqueness constraint this key is unique.
280    refs.sort_by(|a, b| (&a.kind, &a.node, a.provenance).cmp(&(&b.kind, &b.node, b.provenance)));
281}
282
283/// Explain a node: its record plus every incoming and outgoing edge, each
284/// labelled with provenance. Returns `None` if no node has that key.
285///
286/// # Errors
287/// Returns [`StoreError`] on query failure.
288pub fn explain(store: &Store, key: &str) -> Result<Option<Explanation>, StoreError> {
289    let Some(node) = store.get_node(key)? else {
290        return Ok(None);
291    };
292    let mut outgoing: Vec<EdgeRef> = store.edges_from(key)?.iter().map(out_ref).collect();
293    let mut incoming: Vec<EdgeRef> = store.edges_to(key)?.iter().map(in_ref).collect();
294    sort_refs(&mut outgoing);
295    sort_refs(&mut incoming);
296    Ok(Some(Explanation {
297        schema: SCHEMA,
298        node: NodeSummary::from_node(&node),
299        meta: node.meta,
300        outgoing,
301        incoming,
302    }))
303}
304
305/// List every node of the given `kind`, ordered by key.
306///
307/// # Errors
308/// Returns [`StoreError`] on query failure.
309pub fn list_kind(store: &Store, kind: &NodeKind) -> Result<Listing, StoreError> {
310    let nodes = store
311        .nodes_by_kind(kind)?
312        .iter()
313        .map(NodeSummary::from_node)
314        .collect();
315    Ok(Listing {
316        schema: SCHEMA,
317        kind: kind.as_str().to_owned(),
318        nodes,
319    })
320}
321
322/// A relevance-ranked search hit: a node summary plus its score.
323#[derive(Debug, Clone, PartialEq, Serialize)]
324pub struct SearchHit {
325    /// Relevance score (higher is better); see [`search`] for how it is derived.
326    pub score: u32,
327    /// The matching node.
328    #[serde(flatten)]
329    pub node: NodeSummary,
330}
331
332/// Deterministically search nodes for `query`, ranked by relevance, returning at
333/// most `limit` hits. Case-insensitive; every whitespace/`::`-separated token must
334/// appear somewhere in the node's **name, key, path, or captured `meta.content`**
335/// (so a question's words find the *description*, e.g. a README/ADR, not only a
336/// same-named symbol). Scoring favours an exact name match, then a name/content
337/// substring, then per-token hits; it then **boosts curated intent** (`authored`
338/// ADRs/blueprints) and READMEs/overviews and **penalises test scaffolding**, so
339/// "what/why" questions land on the real answer rather than a same-named test
340/// helper. Ties break by key so results are stable.
341///
342/// # Errors
343/// Returns [`StoreError`] on query failure.
344pub fn search(store: &Store, query: &str, limit: usize) -> Result<Vec<SearchHit>, StoreError> {
345    if limit == 0 {
346        return Ok(Vec::new());
347    }
348    let q = query.trim().to_lowercase();
349    // Tokens are separated by whitespace or the `::` path separator; a lone `:`
350    // (as in a `sym:rust:…` key) does not split a token.
351    let tokens: Vec<&str> = q.split("::").flat_map(str::split_whitespace).collect();
352    if tokens.is_empty() {
353        return Ok(Vec::new());
354    }
355
356    let mut hits: Vec<SearchHit> = Vec::new();
357    for node in store.all_nodes()? {
358        let name = node.name.to_lowercase();
359        let key = node.key.to_lowercase();
360        let path = node.path.as_deref().unwrap_or("").to_lowercase();
361        // The captured knowledge base (doc comments, prose, ADR/README/blueprint
362        // text) is searchable too, so a question's words find the *description*,
363        // not just a same-named symbol. Only lowercase when a node actually has
364        // content — most nodes (code symbols) don't, so skip the allocation.
365        let content = node
366            .meta
367            .get("content")
368            .and_then(|v| v.as_str())
369            .map(str::to_lowercase);
370        let content = content.as_deref().unwrap_or("");
371        // Require every token to appear somewhere (including content), so a
372        // multi-word query narrows.
373        if !tokens
374            .iter()
375            .all(|t| name.contains(t) || key.contains(t) || path.contains(t) || content.contains(t))
376        {
377            continue;
378        }
379        let mut relevance: i32 = 0;
380        if name == q {
381            relevance += 100;
382        } else if name.contains(&q) {
383            relevance += 60;
384        } else if content.contains(&q) {
385            relevance += 25;
386        }
387        for t in &tokens {
388            if name.contains(t) {
389                relevance += 12;
390            } else if key.contains(t) {
391                relevance += 6;
392            } else if content.contains(t) {
393                relevance += 8;
394            } else if path.contains(t) {
395                relevance += 3;
396            }
397        }
398        // Curated intent (ADRs/blueprints — `authored`) is the best answer to a
399        // "what/why" question; a README/overview is the natural landing page; and
400        // test scaffolding should not outrank the real thing when it shares a name.
401        if node.provenance == Provenance::Authored {
402            relevance += 40;
403        }
404        if is_overview_path(&path) {
405            relevance += 30;
406        }
407        if is_test_path(&path) {
408            relevance -= 60;
409        }
410        hits.push(SearchHit {
411            score: u32::try_from(relevance.max(0)).unwrap_or(0),
412            node: NodeSummary::from_node(&node),
413        });
414    }
415    // Highest score first; ties by key for a stable, deterministic order.
416    hits.sort_by(|a, b| {
417        b.score
418            .cmp(&a.score)
419            .then_with(|| a.node.key.cmp(&b.node.key))
420    });
421    hits.truncate(limit);
422    Ok(hits)
423}
424
425/// Whether `path` (already lowercased) is a README/overview doc — the natural
426/// landing for "what is this project" questions, so it is ranked up. Matches a
427/// `readme*` or `overview*` basename (blueprints, the other overview docs, are
428/// already boosted via their `authored` provenance).
429fn is_overview_path(path: &str) -> bool {
430    path.rsplit('/')
431        .next()
432        .is_some_and(|base| base.starts_with("readme") || base.starts_with("overview"))
433}
434
435/// Whether `path` (already lowercased) is test scaffolding, which should not
436/// outrank real content that happens to share a name.
437fn is_test_path(path: &str) -> bool {
438    path.contains("/tests/") || path.contains("/test/")
439}
440
441/// A candidate step out of a node during traversal: the edge used and the node
442/// on the other end. Ordered so BFS expansion is deterministic.
443struct Step {
444    node: String,
445    hop: PathHop,
446}
447
448/// All one-hop steps out of `key`, following edges in either direction, sorted
449/// for deterministic traversal.
450fn steps_from(store: &Store, key: &str) -> Result<Vec<Step>, StoreError> {
451    let mut steps = Vec::new();
452    for edge in store.edges_from(key)? {
453        steps.push(Step {
454            node: edge.dst.clone(),
455            hop: hop(&edge, "outgoing", edge.dst.clone()),
456        });
457    }
458    for edge in store.edges_to(key)? {
459        steps.push(Step {
460            node: edge.src.clone(),
461            hop: hop(&edge, "incoming", edge.src.clone()),
462        });
463    }
464    steps.sort_by(|a, b| {
465        (&a.node, &a.hop.kind, a.hop.provenance, a.hop.direction).cmp(&(
466            &b.node,
467            &b.hop.kind,
468            b.hop.provenance,
469            b.hop.direction,
470        ))
471    });
472    Ok(steps)
473}
474
475fn hop(edge: &Edge, direction: &'static str, node: String) -> PathHop {
476    PathHop {
477        kind: edge.kind.as_str().to_owned(),
478        provenance: edge.provenance.as_str(),
479        confidence: edge.confidence,
480        direction,
481        node,
482    }
483}
484
485/// Find a shortest path from `from` to `to`, following edges in either
486/// direction. Returns a [`Path`] with `found = false` (and no hops) if either
487/// endpoint is absent or `to` is unreachable; `from == to` yields the trivial
488/// zero-length path.
489///
490/// The search is breadth-first with deterministic neighbour ordering, so the
491/// returned path is stable for a given graph.
492///
493/// # Errors
494/// Returns [`StoreError`] on query failure.
495pub fn path(store: &Store, from: &str, to: &str) -> Result<Path, StoreError> {
496    let not_found = |found: bool, hops: Vec<PathHop>| Path {
497        schema: SCHEMA,
498        from: from.to_owned(),
499        to: to.to_owned(),
500        found,
501        length: hops.len(),
502        hops,
503    };
504
505    // Both endpoints must exist in the graph.
506    if store.get_node(from)?.is_none() || store.get_node(to)?.is_none() {
507        return Ok(not_found(false, Vec::new()));
508    }
509    if from == to {
510        return Ok(not_found(true, Vec::new()));
511    }
512
513    // BFS, recording for each visited node the (predecessor, hop) that reached
514    // it so the path can be reconstructed.
515    let mut came_from: BTreeMap<String, (String, PathHop)> = BTreeMap::new();
516    let mut queue: VecDeque<String> = VecDeque::new();
517    queue.push_back(from.to_owned());
518    came_from.insert(from.to_owned(), (String::new(), placeholder_hop()));
519
520    while let Some(current) = queue.pop_front() {
521        if current == to {
522            break;
523        }
524        for step in steps_from(store, &current)? {
525            if came_from.contains_key(&step.node) {
526                continue;
527            }
528            came_from.insert(step.node.clone(), (current.clone(), step.hop));
529            queue.push_back(step.node);
530        }
531    }
532
533    // Walk predecessors back from `to` to `from`, then reverse. Every node in
534    // `came_from` other than `from` has a real predecessor, so this terminates
535    // at `from`. If the chain is ever broken (an invariant violation), treat it
536    // as no path rather than silently returning a partial one.
537    let mut hops = Vec::new();
538    let mut cursor = to.to_owned();
539    while cursor != from {
540        let Some((prev, hop)) = came_from.get(&cursor) else {
541            return Ok(not_found(false, Vec::new()));
542        };
543        hops.push(hop.clone());
544        cursor = prev.clone();
545    }
546    hops.reverse();
547    Ok(not_found(true, hops))
548}
549
550/// A sentinel hop for the BFS start node (never emitted in a result).
551fn placeholder_hop() -> PathHop {
552    PathHop {
553        kind: String::new(),
554        provenance: "derived",
555        confidence: None,
556        direction: "outgoing",
557        node: String::new(),
558    }
559}
560
561#[cfg(test)]
562mod tests {
563    use super::{SCHEMA, explain, glob_match, list_kind, path, search};
564    use crate::{Edge, EdgeKind, FactSet, Node, NodeKind, Store};
565
566    fn seeded() -> Store {
567        let mut store = Store::open_in_memory().expect("store");
568        let facts = FactSet::new()
569            .with_node(Node::new("sym:rust:a.rs#main", NodeKind::Fn, "main"))
570            .with_node(Node::new("sym:rust:a.rs#helper", NodeKind::Fn, "helper"))
571            .with_node(Node::new("adr:0001", NodeKind::Adr, "Build Roteiro"))
572            .with_edge(Edge::derived(
573                "sym:rust:a.rs#main",
574                "sym:rust:a.rs#helper",
575                EdgeKind::Calls,
576            ))
577            .with_edge(Edge::authored(
578                "adr:0001",
579                "sym:rust:a.rs#main",
580                EdgeKind::References,
581            ));
582        store.apply_factset(&facts).expect("apply");
583        store
584    }
585
586    #[test]
587    fn search_ranks_by_relevance_and_is_bounded() {
588        let store = seeded();
589        // An exact name match outranks a substring match.
590        let hits = search(&store, "helper", 10).expect("search");
591        assert_eq!(hits[0].node.key, "sym:rust:a.rs#helper");
592        assert!(hits[0].score >= 100, "exact name match scores high");
593
594        // Every token must appear: "main roteiro" matches nothing (no node has both).
595        assert!(
596            search(&store, "main roteiro", 10)
597                .expect("search")
598                .is_empty()
599        );
600
601        // A lone `:` does not split a token: `sym:rust` is one token matching the
602        // code-symbol keys but not `adr:0001`.
603        let by_prefix = search(&store, "sym:rust", 10).expect("search");
604        assert!(!by_prefix.is_empty());
605        assert!(
606            by_prefix
607                .iter()
608                .all(|h| h.node.key.starts_with("sym:rust:"))
609        );
610
611        // A blank query yields nothing; the limit is respected.
612        assert!(search(&store, "   ", 10).expect("search").is_empty());
613        assert!(search(&store, "a.rs", 1).expect("search").len() <= 1);
614    }
615
616    #[test]
617    fn search_prefers_curated_content_over_same_named_test_symbols() {
618        use crate::Provenance;
619        let mut store = Store::open_in_memory().expect("store");
620        // A same-named test helper (exact name, but test scaffolding)…
621        let mut test_fn = Node::new(
622            "sym:rust:crates/x/tests/cli.rs#roteiro",
623            NodeKind::Fn,
624            "roteiro",
625        );
626        test_fn.path = Some("crates/x/tests/cli.rs".into());
627        // …the authored ADR that actually answers "what is roteiro"…
628        let mut adr = Node::new("adr:0001", NodeKind::Adr, "Build Roteiro")
629            .with_provenance(Provenance::Authored);
630        adr.path = Some("docs/adr/0001.md".into());
631        adr.meta = serde_json::json!({ "content": "Roteiro is a provenance-tagged codebase knowledge graph." });
632        // …and a README whose *content* (not its name) describes the project.
633        let mut readme = Node::new("file:README.md", NodeKind::File, "README.md");
634        readme.path = Some("README.md".into());
635        readme.meta =
636            serde_json::json!({ "content": "Roteiro turns a repo into one knowledge graph." });
637        store
638            .apply_factset(
639                &FactSet::new()
640                    .with_node(test_fn)
641                    .with_node(adr)
642                    .with_node(readme),
643            )
644            .expect("apply");
645
646        let hits = search(&store, "roteiro", 10).expect("search");
647        let keys: Vec<&str> = hits.iter().map(|h| h.node.key.as_str()).collect();
648        let idx = |k: &str| keys.iter().position(|x| *x == k).expect("present");
649        // The authored ADR and the README (found *by content*) both outrank the
650        // same-named test helper.
651        assert!(
652            idx("adr:0001") < idx("sym:rust:crates/x/tests/cli.rs#roteiro"),
653            "authored ADR outranks the test symbol: {keys:?}"
654        );
655        assert!(
656            idx("file:README.md") < idx("sym:rust:crates/x/tests/cli.rs#roteiro"),
657            "README (matched via content) outranks the test symbol: {keys:?}"
658        );
659
660        // A content-only term finds the node even though no name/key/path has it.
661        let by_content = search(&store, "provenance-tagged", 10).expect("search");
662        assert_eq!(
663            by_content.first().map(|h| h.node.key.as_str()),
664            Some("adr:0001"),
665            "content search matches the ADR by its captured text"
666        );
667    }
668
669    #[test]
670    fn explain_reports_labelled_neighbourhood() {
671        let store = seeded();
672        let ex = explain(&store, "sym:rust:a.rs#main")
673            .expect("query")
674            .expect("present");
675        assert_eq!(ex.schema, SCHEMA);
676        assert_eq!(ex.node.kind, "fn");
677
678        // Outgoing: derived call to helper.
679        assert_eq!(ex.outgoing.len(), 1);
680        assert_eq!(ex.outgoing[0].kind, "calls");
681        assert_eq!(ex.outgoing[0].provenance, "derived");
682        assert_eq!(ex.outgoing[0].node, "sym:rust:a.rs#helper");
683
684        // Incoming: authored reference from the ADR.
685        assert_eq!(ex.incoming.len(), 1);
686        assert_eq!(ex.incoming[0].provenance, "authored");
687        assert_eq!(ex.incoming[0].node, "adr:0001");
688    }
689
690    #[test]
691    fn explain_missing_node_is_none() {
692        let store = seeded();
693        assert!(explain(&store, "sym:rust:a.rs#ghost").expect("q").is_none());
694    }
695
696    #[test]
697    fn edges_differing_only_in_provenance_are_ordered() {
698        // Two edges A->B with the same kind but different provenance must sort
699        // into a stable, deterministic order (authored before derived).
700        let mut store = Store::open_in_memory().expect("store");
701        let facts = FactSet::new()
702            .with_node(Node::new("a", NodeKind::Fn, "a"))
703            .with_node(Node::new("b", NodeKind::Fn, "b"))
704            .with_edge(Edge::derived("a", "b", EdgeKind::References))
705            .with_edge(Edge::authored("a", "b", EdgeKind::References));
706        store.apply_factset(&facts).expect("apply");
707
708        let ex = explain(&store, "a").expect("q").expect("present");
709        let provs: Vec<_> = ex.outgoing.iter().map(|e| e.provenance).collect();
710        assert_eq!(provs, ["authored", "derived"]);
711    }
712
713    #[test]
714    fn list_kind_is_ordered() {
715        let store = seeded();
716        let listing = list_kind(&store, &NodeKind::Fn).expect("list");
717        let keys: Vec<_> = listing.nodes.iter().map(|n| n.key.as_str()).collect();
718        assert_eq!(keys, ["sym:rust:a.rs#helper", "sym:rust:a.rs#main"]);
719    }
720
721    #[test]
722    fn json_schema_is_stable() {
723        let store = seeded();
724        let ex = explain(&store, "adr:0001").expect("q").expect("present");
725        let json = serde_json::to_value(&ex).expect("json");
726        assert_eq!(json["schema"], SCHEMA);
727        assert_eq!(json["node"]["key"], "adr:0001");
728        assert_eq!(json["node"]["kind"], "adr");
729        // Outgoing authored reference is present with its provenance label.
730        assert_eq!(json["outgoing"][0]["kind"], "references");
731        assert_eq!(json["outgoing"][0]["provenance"], "authored");
732        assert_eq!(json["outgoing"][0]["node"], "sym:rust:a.rs#main");
733        assert!(json["outgoing"][0]["confidence"].is_null());
734    }
735
736    #[test]
737    fn path_crosses_provenance_and_direction() {
738        // adr:0001 --authored/references--> main --derived/calls--> helper.
739        // A path from the ADR to helper must traverse both, each hop labelled.
740        let store = seeded();
741        let p = path(&store, "adr:0001", "sym:rust:a.rs#helper").expect("path");
742        assert!(p.found);
743        assert_eq!(p.length, 2);
744        assert_eq!(p.schema, SCHEMA);
745
746        assert_eq!(p.hops[0].kind, "references");
747        assert_eq!(p.hops[0].provenance, "authored");
748        assert_eq!(p.hops[0].direction, "outgoing");
749        assert_eq!(p.hops[0].node, "sym:rust:a.rs#main");
750
751        assert_eq!(p.hops[1].kind, "calls");
752        assert_eq!(p.hops[1].provenance, "derived");
753        assert_eq!(p.hops[1].node, "sym:rust:a.rs#helper");
754    }
755
756    #[test]
757    fn path_follows_edges_against_direction() {
758        // From helper back to the ADR: both edges are traversed against their
759        // stored direction, so each hop is `incoming`.
760        let store = seeded();
761        let p = path(&store, "sym:rust:a.rs#helper", "adr:0001").expect("path");
762        assert!(p.found);
763        assert_eq!(p.length, 2);
764        assert!(p.hops.iter().all(|h| h.direction == "incoming"));
765        assert_eq!(p.hops.last().unwrap().node, "adr:0001");
766    }
767
768    #[test]
769    fn path_same_node_is_trivial() {
770        let store = seeded();
771        let p = path(&store, "adr:0001", "adr:0001").expect("path");
772        assert!(p.found);
773        assert_eq!(p.length, 0);
774        assert!(p.hops.is_empty());
775    }
776
777    #[test]
778    fn path_missing_endpoint_or_unreachable_is_not_found() {
779        let mut store = Store::open_in_memory().expect("store");
780        // Two disconnected components: a-b and an isolated island.
781        let facts = FactSet::new()
782            .with_node(Node::new("a", NodeKind::Fn, "a"))
783            .with_node(Node::new("b", NodeKind::Fn, "b"))
784            .with_node(Node::new("island", NodeKind::Fn, "island"))
785            .with_edge(Edge::derived("a", "b", EdgeKind::Calls));
786        store.apply_factset(&facts).expect("apply");
787
788        // Absent endpoint.
789        let missing = path(&store, "a", "ghost").expect("path");
790        assert!(!missing.found);
791        assert!(missing.hops.is_empty());
792
793        // Present but unreachable.
794        let unreachable = path(&store, "a", "island").expect("path");
795        assert!(!unreachable.found);
796        assert!(unreachable.hops.is_empty());
797    }
798
799    #[test]
800    fn path_is_shortest() {
801        // a-b-c-d chain plus a direct a-d edge: the path must take the shortcut.
802        let mut store = Store::open_in_memory().expect("store");
803        let facts = FactSet::new()
804            .with_node(Node::new("a", NodeKind::Fn, "a"))
805            .with_node(Node::new("b", NodeKind::Fn, "b"))
806            .with_node(Node::new("c", NodeKind::Fn, "c"))
807            .with_node(Node::new("d", NodeKind::Fn, "d"))
808            .with_edge(Edge::derived("a", "b", EdgeKind::Calls))
809            .with_edge(Edge::derived("b", "c", EdgeKind::Calls))
810            .with_edge(Edge::derived("c", "d", EdgeKind::Calls))
811            .with_edge(Edge::derived("a", "d", EdgeKind::Calls));
812        store.apply_factset(&facts).expect("apply");
813
814        let p = path(&store, "a", "d").expect("path");
815        assert!(p.found);
816        assert_eq!(p.length, 1, "the direct a->d edge is the shortest path");
817        assert_eq!(p.hops[0].node, "d");
818    }
819
820    #[test]
821    fn glob_matches_segments_and_wildcards() {
822        // `**` spans segments (including zero) and anchors both ends.
823        assert!(glob_match("vendor/**", "vendor/lib/a.rs"));
824        assert!(glob_match("vendor/**", "vendor")); // zero trailing segments
825        assert!(glob_match("**/generated/*", "src/gen/generated/x.rs"));
826        assert!(glob_match("**/*.rs", "a/b/c.rs"));
827        // `*` and `?` stay within one segment.
828        assert!(glob_match("src/*.rs", "src/main.rs"));
829        assert!(!glob_match("src/*.rs", "src/sub/main.rs"));
830        assert!(glob_match("a?c.rs", "abc.rs"));
831        assert!(!glob_match("a?c.rs", "ac.rs"));
832        // Anchored: a bare name does not match a nested path.
833        assert!(!glob_match("generated", "src/generated"));
834        assert!(!glob_match("vendor/**", "third_party/vendor/a.rs"));
835    }
836}
rto_graph/query.rs

rto_graph/
query.rs
