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. Three primitives are provided: [`explain`] (a node
6//! and its provenance-labelled neighbourhood), [`list_kind`] (all nodes of a
7//! kind), and [`path`] (a shortest path between two nodes). All return
8//! mixed-provenance results — the "one query surface" from ADR-0001 — with every
9//! edge carrying its `provenance`.
10
11use std::collections::{BTreeMap, VecDeque};
12
13use serde::Serialize;
14
15use crate::store::{Store, StoreError};
16use crate::{Edge, NodeKind};
17
18/// The versioned schema tag emitted on every query result. Bump the version on
19/// any breaking change to the shape.
20pub const SCHEMA: &str = "roteiro.query/v1";
21
22/// A compact node summary (used in listings and as the subject of an
23/// [`Explanation`]).
24#[derive(Debug, Clone, PartialEq, Serialize)]
25pub struct NodeSummary {
26    /// Natural key.
27    pub key: String,
28    /// Kind token (e.g. `fn`, `adr`).
29    pub kind: String,
30    /// Human-facing name.
31    pub name: String,
32    /// Repository-relative path, if any.
33    pub path: Option<String>,
34    /// Language token, if any.
35    pub lang: Option<String>,
36}
37
38impl NodeSummary {
39    fn from_node(node: &crate::Node) -> Self {
40        Self {
41            key: node.key.clone(),
42            kind: node.kind.as_str().to_owned(),
43            name: node.name.clone(),
44            path: node.path.clone(),
45            lang: node.lang.clone(),
46        }
47    }
48}
49
50/// One end of an edge as seen from a subject node: the relationship, how it was
51/// produced, and the node on the other end.
52#[derive(Debug, Clone, PartialEq, Serialize)]
53pub struct EdgeRef {
54    /// Edge kind token (e.g. `calls`, `references`).
55    pub kind: String,
56    /// How the edge was produced (`derived` | `authored` | `inferred`).
57    pub provenance: &'static str,
58    /// Confidence score, present only for inferred edges.
59    pub confidence: Option<f64>,
60    /// The natural key of the node at the other end.
61    pub node: String,
62}
63
64/// A node together with its provenance-labelled neighbourhood.
65#[derive(Debug, Clone, PartialEq, Serialize)]
66pub struct Explanation {
67    /// Stable schema tag ([`SCHEMA`]).
68    pub schema: &'static str,
69    /// The subject node.
70    pub node: NodeSummary,
71    /// Structured metadata attached to the node.
72    pub meta: serde_json::Value,
73    /// Edges where the subject is the source.
74    pub outgoing: Vec<EdgeRef>,
75    /// Edges where the subject is the destination.
76    pub incoming: Vec<EdgeRef>,
77}
78
79/// A listing of all nodes of one kind.
80#[derive(Debug, Clone, PartialEq, Serialize)]
81pub struct Listing {
82    /// Stable schema tag ([`SCHEMA`]).
83    pub schema: &'static str,
84    /// The kind that was listed.
85    pub kind: String,
86    /// Matching nodes, ordered by key.
87    pub nodes: Vec<NodeSummary>,
88}
89
90/// One step along a [`Path`]: the edge traversed and the node it leads to.
91#[derive(Debug, Clone, PartialEq, Serialize)]
92pub struct PathHop {
93    /// Edge kind token (e.g. `calls`, `contains`).
94    pub kind: String,
95    /// How the edge was produced.
96    pub provenance: &'static str,
97    /// Confidence score, present only for inferred edges.
98    pub confidence: Option<f64>,
99    /// The direction the edge was traversed relative to the previous node
100    /// (`outgoing` = along the edge, `incoming` = against it).
101    pub direction: &'static str,
102    /// The natural key of the node this hop arrives at.
103    pub node: String,
104}
105
106/// A shortest path between two nodes. Edges are followed in either direction
107/// (the graph is treated as undirected for reachability), and each hop records
108/// the actual direction and provenance of the edge used.
109#[derive(Debug, Clone, PartialEq, Serialize)]
110pub struct Path {
111    /// Stable schema tag ([`SCHEMA`]).
112    pub schema: &'static str,
113    /// Natural key of the start node.
114    pub from: String,
115    /// Natural key of the goal node.
116    pub to: String,
117    /// Whether a path (including the trivial empty one) was found.
118    pub found: bool,
119    /// Number of hops (edges) in the path; `0` when `from == to`.
120    pub length: usize,
121    /// The hops from `from` to `to`, in order.
122    pub hops: Vec<PathHop>,
123}
124
125fn out_ref(edge: &Edge) -> EdgeRef {
126    EdgeRef {
127        kind: edge.kind.as_str().to_owned(),
128        provenance: edge.provenance.as_str(),
129        confidence: edge.confidence,
130        node: edge.dst.clone(),
131    }
132}
133
134fn in_ref(edge: &Edge) -> EdgeRef {
135    EdgeRef {
136        kind: edge.kind.as_str().to_owned(),
137        provenance: edge.provenance.as_str(),
138        confidence: edge.confidence,
139        node: edge.src.clone(),
140    }
141}
142
143fn sort_refs(refs: &mut [EdgeRef]) {
144    // Include provenance so edges differing only in provenance have a total,
145    // stable order; with the edge-uniqueness constraint this key is unique.
146    refs.sort_by(|a, b| (&a.kind, &a.node, a.provenance).cmp(&(&b.kind, &b.node, b.provenance)));
147}
148
149/// Explain a node: its record plus every incoming and outgoing edge, each
150/// labelled with provenance. Returns `None` if no node has that key.
151///
152/// # Errors
153/// Returns [`StoreError`] on query failure.
154pub fn explain(store: &Store, key: &str) -> Result<Option<Explanation>, StoreError> {
155    let Some(node) = store.get_node(key)? else {
156        return Ok(None);
157    };
158    let mut outgoing: Vec<EdgeRef> = store.edges_from(key)?.iter().map(out_ref).collect();
159    let mut incoming: Vec<EdgeRef> = store.edges_to(key)?.iter().map(in_ref).collect();
160    sort_refs(&mut outgoing);
161    sort_refs(&mut incoming);
162    Ok(Some(Explanation {
163        schema: SCHEMA,
164        node: NodeSummary::from_node(&node),
165        meta: node.meta,
166        outgoing,
167        incoming,
168    }))
169}
170
171/// List every node of the given `kind`, ordered by key.
172///
173/// # Errors
174/// Returns [`StoreError`] on query failure.
175pub fn list_kind(store: &Store, kind: &NodeKind) -> Result<Listing, StoreError> {
176    let nodes = store
177        .nodes_by_kind(kind)?
178        .iter()
179        .map(NodeSummary::from_node)
180        .collect();
181    Ok(Listing {
182        schema: SCHEMA,
183        kind: kind.as_str().to_owned(),
184        nodes,
185    })
186}
187
188/// A candidate step out of a node during traversal: the edge used and the node
189/// on the other end. Ordered so BFS expansion is deterministic.
190struct Step {
191    node: String,
192    hop: PathHop,
193}
194
195/// All one-hop steps out of `key`, following edges in either direction, sorted
196/// for deterministic traversal.
197fn steps_from(store: &Store, key: &str) -> Result<Vec<Step>, StoreError> {
198    let mut steps = Vec::new();
199    for edge in store.edges_from(key)? {
200        steps.push(Step {
201            node: edge.dst.clone(),
202            hop: hop(&edge, "outgoing", edge.dst.clone()),
203        });
204    }
205    for edge in store.edges_to(key)? {
206        steps.push(Step {
207            node: edge.src.clone(),
208            hop: hop(&edge, "incoming", edge.src.clone()),
209        });
210    }
211    steps.sort_by(|a, b| {
212        (&a.node, &a.hop.kind, a.hop.provenance, a.hop.direction).cmp(&(
213            &b.node,
214            &b.hop.kind,
215            b.hop.provenance,
216            b.hop.direction,
217        ))
218    });
219    Ok(steps)
220}
221
222fn hop(edge: &Edge, direction: &'static str, node: String) -> PathHop {
223    PathHop {
224        kind: edge.kind.as_str().to_owned(),
225        provenance: edge.provenance.as_str(),
226        confidence: edge.confidence,
227        direction,
228        node,
229    }
230}
231
232/// Find a shortest path from `from` to `to`, following edges in either
233/// direction. Returns a [`Path`] with `found = false` (and no hops) if either
234/// endpoint is absent or `to` is unreachable; `from == to` yields the trivial
235/// zero-length path.
236///
237/// The search is breadth-first with deterministic neighbour ordering, so the
238/// returned path is stable for a given graph.
239///
240/// # Errors
241/// Returns [`StoreError`] on query failure.
242pub fn path(store: &Store, from: &str, to: &str) -> Result<Path, StoreError> {
243    let not_found = |found: bool, hops: Vec<PathHop>| Path {
244        schema: SCHEMA,
245        from: from.to_owned(),
246        to: to.to_owned(),
247        found,
248        length: hops.len(),
249        hops,
250    };
251
252    // Both endpoints must exist in the graph.
253    if store.get_node(from)?.is_none() || store.get_node(to)?.is_none() {
254        return Ok(not_found(false, Vec::new()));
255    }
256    if from == to {
257        return Ok(not_found(true, Vec::new()));
258    }
259
260    // BFS, recording for each visited node the (predecessor, hop) that reached
261    // it so the path can be reconstructed.
262    let mut came_from: BTreeMap<String, (String, PathHop)> = BTreeMap::new();
263    let mut queue: VecDeque<String> = VecDeque::new();
264    queue.push_back(from.to_owned());
265    came_from.insert(from.to_owned(), (String::new(), placeholder_hop()));
266
267    while let Some(current) = queue.pop_front() {
268        if current == to {
269            break;
270        }
271        for step in steps_from(store, &current)? {
272            if came_from.contains_key(&step.node) {
273                continue;
274            }
275            came_from.insert(step.node.clone(), (current.clone(), step.hop));
276            queue.push_back(step.node);
277        }
278    }
279
280    // Walk predecessors back from `to` to `from`, then reverse. Every node in
281    // `came_from` other than `from` has a real predecessor, so this terminates
282    // at `from`. If the chain is ever broken (an invariant violation), treat it
283    // as no path rather than silently returning a partial one.
284    let mut hops = Vec::new();
285    let mut cursor = to.to_owned();
286    while cursor != from {
287        let Some((prev, hop)) = came_from.get(&cursor) else {
288            return Ok(not_found(false, Vec::new()));
289        };
290        hops.push(hop.clone());
291        cursor = prev.clone();
292    }
293    hops.reverse();
294    Ok(not_found(true, hops))
295}
296
297/// A sentinel hop for the BFS start node (never emitted in a result).
298fn placeholder_hop() -> PathHop {
299    PathHop {
300        kind: String::new(),
301        provenance: "derived",
302        confidence: None,
303        direction: "outgoing",
304        node: String::new(),
305    }
306}
307
308#[cfg(test)]
309mod tests {
310    use super::{SCHEMA, explain, list_kind, path};
311    use crate::{Edge, EdgeKind, FactSet, Node, NodeKind, Store};
312
313    fn seeded() -> Store {
314        let mut store = Store::open_in_memory().expect("store");
315        let facts = FactSet::new()
316            .with_node(Node::new("sym:rust:a.rs#main", NodeKind::Fn, "main"))
317            .with_node(Node::new("sym:rust:a.rs#helper", NodeKind::Fn, "helper"))
318            .with_node(Node::new("adr:0001", NodeKind::Adr, "Build Roteiro"))
319            .with_edge(Edge::derived(
320                "sym:rust:a.rs#main",
321                "sym:rust:a.rs#helper",
322                EdgeKind::Calls,
323            ))
324            .with_edge(Edge::authored(
325                "adr:0001",
326                "sym:rust:a.rs#main",
327                EdgeKind::References,
328            ));
329        store.apply_factset(&facts).expect("apply");
330        store
331    }
332
333    #[test]
334    fn explain_reports_labelled_neighbourhood() {
335        let store = seeded();
336        let ex = explain(&store, "sym:rust:a.rs#main")
337            .expect("query")
338            .expect("present");
339        assert_eq!(ex.schema, SCHEMA);
340        assert_eq!(ex.node.kind, "fn");
341
342        // Outgoing: derived call to helper.
343        assert_eq!(ex.outgoing.len(), 1);
344        assert_eq!(ex.outgoing[0].kind, "calls");
345        assert_eq!(ex.outgoing[0].provenance, "derived");
346        assert_eq!(ex.outgoing[0].node, "sym:rust:a.rs#helper");
347
348        // Incoming: authored reference from the ADR.
349        assert_eq!(ex.incoming.len(), 1);
350        assert_eq!(ex.incoming[0].provenance, "authored");
351        assert_eq!(ex.incoming[0].node, "adr:0001");
352    }
353
354    #[test]
355    fn explain_missing_node_is_none() {
356        let store = seeded();
357        assert!(explain(&store, "sym:rust:a.rs#ghost").expect("q").is_none());
358    }
359
360    #[test]
361    fn edges_differing_only_in_provenance_are_ordered() {
362        // Two edges A->B with the same kind but different provenance must sort
363        // into a stable, deterministic order (authored before derived).
364        let mut store = Store::open_in_memory().expect("store");
365        let facts = FactSet::new()
366            .with_node(Node::new("a", NodeKind::Fn, "a"))
367            .with_node(Node::new("b", NodeKind::Fn, "b"))
368            .with_edge(Edge::derived("a", "b", EdgeKind::References))
369            .with_edge(Edge::authored("a", "b", EdgeKind::References));
370        store.apply_factset(&facts).expect("apply");
371
372        let ex = explain(&store, "a").expect("q").expect("present");
373        let provs: Vec<_> = ex.outgoing.iter().map(|e| e.provenance).collect();
374        assert_eq!(provs, ["authored", "derived"]);
375    }
376
377    #[test]
378    fn list_kind_is_ordered() {
379        let store = seeded();
380        let listing = list_kind(&store, &NodeKind::Fn).expect("list");
381        let keys: Vec<_> = listing.nodes.iter().map(|n| n.key.as_str()).collect();
382        assert_eq!(keys, ["sym:rust:a.rs#helper", "sym:rust:a.rs#main"]);
383    }
384
385    #[test]
386    fn json_schema_is_stable() {
387        let store = seeded();
388        let ex = explain(&store, "adr:0001").expect("q").expect("present");
389        let json = serde_json::to_value(&ex).expect("json");
390        assert_eq!(json["schema"], SCHEMA);
391        assert_eq!(json["node"]["key"], "adr:0001");
392        assert_eq!(json["node"]["kind"], "adr");
393        // Outgoing authored reference is present with its provenance label.
394        assert_eq!(json["outgoing"][0]["kind"], "references");
395        assert_eq!(json["outgoing"][0]["provenance"], "authored");
396        assert_eq!(json["outgoing"][0]["node"], "sym:rust:a.rs#main");
397        assert!(json["outgoing"][0]["confidence"].is_null());
398    }
399
400    #[test]
401    fn path_crosses_provenance_and_direction() {
402        // adr:0001 --authored/references--> main --derived/calls--> helper.
403        // A path from the ADR to helper must traverse both, each hop labelled.
404        let store = seeded();
405        let p = path(&store, "adr:0001", "sym:rust:a.rs#helper").expect("path");
406        assert!(p.found);
407        assert_eq!(p.length, 2);
408        assert_eq!(p.schema, SCHEMA);
409
410        assert_eq!(p.hops[0].kind, "references");
411        assert_eq!(p.hops[0].provenance, "authored");
412        assert_eq!(p.hops[0].direction, "outgoing");
413        assert_eq!(p.hops[0].node, "sym:rust:a.rs#main");
414
415        assert_eq!(p.hops[1].kind, "calls");
416        assert_eq!(p.hops[1].provenance, "derived");
417        assert_eq!(p.hops[1].node, "sym:rust:a.rs#helper");
418    }
419
420    #[test]
421    fn path_follows_edges_against_direction() {
422        // From helper back to the ADR: both edges are traversed against their
423        // stored direction, so each hop is `incoming`.
424        let store = seeded();
425        let p = path(&store, "sym:rust:a.rs#helper", "adr:0001").expect("path");
426        assert!(p.found);
427        assert_eq!(p.length, 2);
428        assert!(p.hops.iter().all(|h| h.direction == "incoming"));
429        assert_eq!(p.hops.last().unwrap().node, "adr:0001");
430    }
431
432    #[test]
433    fn path_same_node_is_trivial() {
434        let store = seeded();
435        let p = path(&store, "adr:0001", "adr:0001").expect("path");
436        assert!(p.found);
437        assert_eq!(p.length, 0);
438        assert!(p.hops.is_empty());
439    }
440
441    #[test]
442    fn path_missing_endpoint_or_unreachable_is_not_found() {
443        let mut store = Store::open_in_memory().expect("store");
444        // Two disconnected components: a-b and an isolated island.
445        let facts = FactSet::new()
446            .with_node(Node::new("a", NodeKind::Fn, "a"))
447            .with_node(Node::new("b", NodeKind::Fn, "b"))
448            .with_node(Node::new("island", NodeKind::Fn, "island"))
449            .with_edge(Edge::derived("a", "b", EdgeKind::Calls));
450        store.apply_factset(&facts).expect("apply");
451
452        // Absent endpoint.
453        let missing = path(&store, "a", "ghost").expect("path");
454        assert!(!missing.found);
455        assert!(missing.hops.is_empty());
456
457        // Present but unreachable.
458        let unreachable = path(&store, "a", "island").expect("path");
459        assert!(!unreachable.found);
460        assert!(unreachable.hops.is_empty());
461    }
462
463    #[test]
464    fn path_is_shortest() {
465        // a-b-c-d chain plus a direct a-d edge: the path must take the shortcut.
466        let mut store = Store::open_in_memory().expect("store");
467        let facts = FactSet::new()
468            .with_node(Node::new("a", NodeKind::Fn, "a"))
469            .with_node(Node::new("b", NodeKind::Fn, "b"))
470            .with_node(Node::new("c", NodeKind::Fn, "c"))
471            .with_node(Node::new("d", NodeKind::Fn, "d"))
472            .with_edge(Edge::derived("a", "b", EdgeKind::Calls))
473            .with_edge(Edge::derived("b", "c", EdgeKind::Calls))
474            .with_edge(Edge::derived("c", "d", EdgeKind::Calls))
475            .with_edge(Edge::derived("a", "d", EdgeKind::Calls));
476        store.apply_factset(&facts).expect("apply");
477
478        let p = path(&store, "a", "d").expect("path");
479        assert!(p.found);
480        assert_eq!(p.length, 1, "the direct a->d edge is the shortest path");
481        assert_eq!(p.hops[0].node, "d");
482    }
483}
rto_graph/query.rs

rto_graph/
query.rs
