memstead_base/graph/
chain.rs

1//! A chain scope: the subgraph reachable from one root along a named
2//! rel-type set in one direction — the reduced set the export formats
3//! and the topology projection render when a caller asks for a chain
4//! instead of a whole mem.
5//!
6//! One resolver, one walker. The scope is resolved here once, through
7//! [`reachable_via`](crate::graph::query::reachable_via) — the same
8//! primitive `memstead_search`'s `expand_via` uses, so direction means
9//! the same thing on both surfaces: applied at EVERY hop, a pure
10//! transitive closure. The renderers then filter their existing
11//! per-entity passes by the resolved set; nothing is rendered twice and
12//! no second walker exists.
13
14use std::collections::HashSet;
15
16use serde::Serialize;
17
18use crate::entity::EntityId;
19use crate::graph::query::{ReachedVia, TraversalDirection, reachable_via};
20use crate::runtime_validator::validate_rel_type;
21
22/// What a caller asks for: a root entity, the rel-types to follow, the
23/// direction to follow them in, and how many hops.
24#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
25pub struct ChainScope {
26    /// The entity the walk starts from; it is always part of the set.
27    pub root: EntityId,
28    /// Rel-types followed at every hop. Validated against the mem's
29    /// schema vocabulary before the walk.
30    pub via: Vec<String>,
31    /// Direction applied at every hop.
32    pub direction: TraversalDirection,
33    /// Maximum hops; `usize::MAX` for an unbounded walk.
34    pub depth: usize,
35}
36
37/// A resolved chain: the root plus everything reached, in any mem. The
38/// renderers filter to their mem; cross-mem members stay in the set so
39/// an edge into one renders as a reached (marked) target, not as an
40/// unresolved link.
41#[derive(Debug, Clone, PartialEq, Eq)]
42pub struct ChainSet {
43    pub scope: ChainScope,
44    /// Root plus reached ids.
45    pub ids: HashSet<EntityId>,
46    /// Every reached entity with the edge it was first reached by.
47    pub reached: Vec<ReachedVia>,
48}
49
50impl ChainSet {
51    pub fn contains(&self, id: &EntityId) -> bool {
52        self.ids.contains(id)
53    }
54
55    /// One line naming the scope, for the headers of scoped renderings.
56    pub fn describe(&self) -> String {
57        let depth = if self.scope.depth == usize::MAX {
58            "unbounded".to_string()
59        } else {
60            self.scope.depth.to_string()
61        };
62        format!(
63            "root {} via {} direction {} depth {}",
64            self.scope.root,
65            self.scope.via.join(","),
66            self.scope.direction.as_wire(),
67            depth
68        )
69    }
70}
71
72impl TraversalDirection {
73    /// Stable wire form.
74    pub fn as_wire(self) -> &'static str {
75        match self {
76            TraversalDirection::Out => "out",
77            TraversalDirection::In => "in",
78            TraversalDirection::Both => "both",
79        }
80    }
81
82    /// Inverse of [`Self::as_wire`]; `None` for an unknown string.
83    pub fn from_wire(s: &str) -> Option<Self> {
84        match s {
85            "out" => Some(TraversalDirection::Out),
86            "in" => Some(TraversalDirection::In),
87            "both" => Some(TraversalDirection::Both),
88            _ => None,
89        }
90    }
91
92    /// Every wire string.
93    pub const WIRE_VALUES: &'static [&'static str] = &["out", "in", "both"];
94}
95
96impl crate::Engine {
97    /// Resolve `scope` against `mem`: the mem must be mounted, the root
98    /// must be a real (non-stub) entity of that mem, `via` must be
99    /// non-empty and every rel-type known to the mem's schema
100    /// (`INVALID_REL_TYPE` naming the vocabulary otherwise), and the walk
101    /// follows `reachable_via` with the scope's direction at every hop.
102    pub fn chain_set(&self, mem: &str, scope: &ChainScope) -> Result<ChainSet, crate::EngineError> {
103        if self.mount(mem).is_none() {
104            return Err(self.unknown_mem_error(mem));
105        }
106        let root = self
107            .store()
108            .get(&scope.root)
109            .filter(|e| !e.stub)
110            .ok_or_else(|| crate::EngineError::NotFound {
111                id: scope.root.to_string(),
112            })?;
113        if root.mem != mem {
114            return Err(crate::EngineError::InvalidInput(format!(
115                "root {} lives in mem '{}', not in the exported mem '{mem}'",
116                scope.root, root.mem
117            )));
118        }
119        if scope.via.is_empty() {
120            return Err(crate::EngineError::InvalidInput(
121                "a chain needs at least one rel-type in `via`".to_string(),
122            ));
123        }
124        if let Some(schema) = self.schema_for(mem) {
125            for rel in &scope.via {
126                validate_rel_type(rel, &schema).map_err(crate::EngineError::Validation)?;
127            }
128        }
129        let reached = reachable_via(
130            self.store(),
131            &scope.root,
132            &scope.via,
133            scope.depth,
134            scope.direction,
135        );
136        let mut ids: HashSet<EntityId> = reached.iter().map(|r| r.id.clone()).collect();
137        ids.insert(scope.root.clone());
138        Ok(ChainSet {
139            scope: scope.clone(),
140            ids,
141            reached,
142        })
143    }
144}
145
146#[cfg(test)]
147mod tests {
148    use crate::graph::query::TraversalDirection;
149    use crate::storage::MemWriter;
150
151    use super::ChainScope;
152
153    /// root --A--> a1 --B--> a2 ; root --C--> c1 ; back --A--> root
154    /// (reachable only against `out`); a1 also cites x in another mem.
155    fn engine() -> (crate::Engine, tempfile::TempDir) {
156        let tmp = tempfile::TempDir::new().unwrap();
157        let seed = |dir: &std::path::Path, files: &[(&str, &str)]| {
158            std::fs::create_dir_all(dir).unwrap();
159            let writer = crate::storage::FilesystemMemWriter::new(dir.to_path_buf());
160            for (name, body) in files {
161                writer
162                    .write_entity(std::path::Path::new(name), body.as_bytes())
163                    .unwrap();
164            }
165            writer
166                .commit("seed", &crate::vcs::CommitContext::internal())
167                .unwrap();
168        };
169        let spec = |title: &str, rels: &str| {
170            format!(
171                "---\ntype: spec\ncreated_date: 2026-01-01\nlast_modified: 2026-01-01\nlevel: M0\n---\n# {title}\n\n## Identity\n\n{title}. See [[a2]] and [[c1]].\n{rels}"
172            )
173        };
174        let m = tmp.path().join("m");
175        let other = tmp.path().join("other");
176        seed(
177            &m,
178            &[
179                (
180                    "root.md",
181                    &spec(
182                        "Root",
183                        "\n## Relationships\n\n- **USES**: [[a1]]\n- **PART_OF**: [[c1]]\n",
184                    ),
185                ),
186                (
187                    "a1.md",
188                    &spec(
189                        "A1",
190                        "\n## Relationships\n\n- **DEPENDS_ON**: [[a2]]\n- **USES**: [[other--x]]\n",
191                    ),
192                ),
193                ("a2.md", &spec("A2", "")),
194                ("c1.md", &spec("C1", "")),
195                (
196                    "back.md",
197                    &spec("Back", "\n## Relationships\n\n- **USES**: [[root]]\n"),
198                ),
199            ],
200        );
201        seed(&other, &[("x.md", &spec("X", ""))]);
202        let mount = |mem: &str, path: std::path::PathBuf| {
203            (
204                crate::Mount {
205                    mem: mem.to_string(),
206                    schema: Some(memstead_schema::SchemaRef::new(
207                        "default",
208                        semver::Version::new(1, 0, 0),
209                    )),
210                    storage: crate::MountStorage::Folder { path: path.clone() },
211                    capability: crate::MountCapability::Write,
212                    lifecycle: crate::MountLifecycle::Eager,
213                    cross_linkable: true,
214                    migration_target: None,
215                },
216                Box::new(crate::storage::FilesystemMemWriter::new(path))
217                    as Box<dyn crate::MemBackend>,
218            )
219        };
220        let engine =
221            crate::Engine::from_mounts(vec![mount("m", m), mount("other", other)]).unwrap();
222        (engine, tmp)
223    }
224
225    fn scope(via: &[&str], direction: TraversalDirection, depth: usize) -> ChainScope {
226        ChainScope {
227            root: crate::EntityId::canonical("m--root"),
228            via: via.iter().map(|s| s.to_string()).collect(),
229            direction,
230            depth,
231        }
232    }
233
234    fn ids(engine: &crate::Engine, s: &ChainScope) -> Vec<String> {
235        let mut v: Vec<String> = engine
236            .chain_set("m", s)
237            .unwrap()
238            .ids
239            .iter()
240            .map(|i| i.to_string())
241            .collect();
242        v.sort();
243        v
244    }
245
246    /// The set is root plus exactly what the rel-types reach in the
247    /// direction, at every hop; the other rel-type and the
248    /// against-direction referrer stay out; depth 1 drops the second hop;
249    /// `in` walks the other way; cross-mem reached nodes stay in the set.
250    #[test]
251    fn chain_set_follows_via_and_direction_at_every_hop() {
252        let (engine, _tmp) = engine();
253        assert_eq!(
254            ids(
255                &engine,
256                &scope(&["USES", "DEPENDS_ON"], TraversalDirection::Out, usize::MAX)
257            ),
258            vec!["m--a1", "m--a2", "m--root", "other--x"]
259        );
260        assert_eq!(
261            ids(
262                &engine,
263                &scope(&["USES", "DEPENDS_ON"], TraversalDirection::Out, 1)
264            ),
265            vec!["m--a1", "m--root"]
266        );
267        assert_eq!(
268            ids(
269                &engine,
270                &scope(&["USES"], TraversalDirection::In, usize::MAX)
271            ),
272            vec!["m--back", "m--root"]
273        );
274        assert_eq!(
275            ids(
276                &engine,
277                &scope(&["PART_OF"], TraversalDirection::Out, usize::MAX)
278            ),
279            vec!["m--c1", "m--root"]
280        );
281        let set = engine
282            .chain_set(
283                "m",
284                &scope(&["USES", "DEPENDS_ON"], TraversalDirection::Out, usize::MAX),
285            )
286            .unwrap();
287        assert_eq!(set.reached.len(), 3);
288        assert!(
289            set.describe()
290                .contains("root m--root via USES,DEPENDS_ON direction out depth unbounded")
291        );
292    }
293
294    /// Refusals: an unknown rel-type names the vocabulary, a missing root
295    /// is ENTITY_NOT_FOUND, an empty via and a root outside the mem are
296    /// INVALID_INPUT, an unknown mem is UNKNOWN_MEM.
297    #[test]
298    fn chain_set_refuses_typed() {
299        let (engine, _tmp) = engine();
300        let err = engine
301            .chain_set("m", &scope(&["NOPE"], TraversalDirection::Out, 3))
302            .unwrap_err();
303        assert_eq!(err.code(), "INVALID_REL_TYPE", "{err}");
304        assert!(
305            err.details().to_string().contains("USES"),
306            "the recovery payload names the vocabulary: {}",
307            err.details()
308        );
309        let missing = ChainScope {
310            root: crate::EntityId::canonical("m--missing"),
311            ..scope(&["USES"], TraversalDirection::Out, 3)
312        };
313        assert_eq!(
314            engine.chain_set("m", &missing).unwrap_err().code(),
315            "ENTITY_NOT_FOUND"
316        );
317        assert_eq!(
318            engine
319                .chain_set("m", &scope(&[], TraversalDirection::Out, 3))
320                .unwrap_err()
321                .code(),
322            "INVALID_INPUT"
323        );
324        assert_eq!(
325            engine
326                .chain_set("other", &scope(&["USES"], TraversalDirection::Out, 3))
327                .unwrap_err()
328                .code(),
329            "INVALID_INPUT",
330            "root in another mem"
331        );
332        assert_eq!(
333            engine
334                .chain_set("ghost", &scope(&["USES"], TraversalDirection::Out, 3))
335                .unwrap_err()
336                .code(),
337            "UNKNOWN_MEM"
338        );
339    }
340
341    /// The scoped renderers carry exactly the chain's in-mem entities,
342    /// mark links to excluded entities unresolved, and the unscoped call
343    /// stays byte-identical to the pre-scope output.
344    #[test]
345    fn scoped_renderers_reduce_and_unscoped_stays_identical() {
346        let (engine, _tmp) = engine();
347        let chain = engine
348            .chain_set(
349                "m",
350                &scope(&["USES", "DEPENDS_ON"], TraversalDirection::Out, usize::MAX),
351            )
352            .unwrap();
353
354        // HTML
355        let full = engine.render_html_export("m", "2026-09-02").unwrap();
356        let same = engine
357            .render_html_export_scoped("m", "2026-09-02", None)
358            .unwrap();
359        assert_eq!(full, same, "None is byte-identical to the unscoped export");
360        let reduced = engine
361            .render_html_export_scoped("m", "2026-09-02", Some(&chain))
362            .unwrap();
363        for id in ["m--root", "m--a1", "m--a2"] {
364            assert!(reduced.contains(&format!("id=\"{id}\"")), "{id} rendered");
365        }
366        for id in ["m--c1", "m--back"] {
367            assert!(!reduced.contains(&format!("id=\"{id}\"")), "{id} excluded");
368        }
369        assert!(reduced.contains("Chain:"), "header names the chain");
370        assert!(
371            reduced.contains("unresolved"),
372            "links to excluded entities are marked"
373        );
374        assert!(reduced.contains("3 entities"));
375
376        // llms-txt
377        let ctx = crate::engine::export_llms_txt::LlmsTxtContext {
378            authority: None,
379            href_prefix: String::new(),
380            wider_project: Vec::new(),
381        };
382        let full = engine.render_llms_txt("m", &ctx).unwrap();
383        assert_eq!(
384            full,
385            engine.render_llms_txt_scoped("m", &ctx, None).unwrap()
386        );
387        let reduced = engine
388            .render_llms_txt_scoped("m", &ctx, Some(&chain))
389            .unwrap();
390        assert!(
391            reduced
392                .contains("Chain: root m--root via USES,DEPENDS_ON direction out depth unbounded")
393        );
394        assert!(reduced.contains("Entities: 3"));
395        assert!(reduced.contains("# A2"));
396        assert!(!reduced.contains("# C1"));
397        assert!(!reduced.contains("# Back"));
398        // The link to the included a2 resolves; the link to the excluded
399        // c1 is left unresolved (the linkifier's plain-text form), never
400        // a link to a page this document does not contain.
401        assert!(reduced.contains("[A2](entity/m--a2)"), "{reduced}");
402        assert!(reduced.contains(" and c1."), "{reduced}");
403        assert!(!reduced.contains("entity/m--c1"), "{reduced}");
404
405        // Topology
406        let full = engine.mem_topology("m").unwrap();
407        assert_eq!(full, engine.mem_topology_scoped("m", None).unwrap());
408        let reduced = engine.mem_topology_scoped("m", Some(&chain)).unwrap();
409        let node_ids: Vec<&str> = reduced.nodes.iter().map(|n| n.id.as_str()).collect();
410        assert_eq!(node_ids, vec!["m--a1", "m--a2", "m--root"]);
411        let edges: Vec<(String, String, bool)> = reduced
412            .edges
413            .iter()
414            .map(|e| (e.source.clone(), e.target.clone(), e.target_in_mem))
415            .collect();
416        assert_eq!(
417            edges,
418            vec![
419                ("m--a1".to_string(), "m--a2".to_string(), true),
420                ("m--a1".to_string(), "other--x".to_string(), false),
421                ("m--root".to_string(), "m--a1".to_string(), true),
422            ],
423            "edges with both ends in the chain, cross-mem target marked"
424        );
425    }
426}
memstead_base/graph/chain.rs

memstead_base/graph/
chain.rs
