memstead_base/validator/
graph.rs

1//! Graph construction + community detection for the validator.
2//!
3//! Builds a `Store` from validated entities using the same stub +
4//! edge rules as the runtime loader (`entity::store_builder`), then
5//! runs Louvain with a fixed seed. Defence-in-depth cross-mem guard
6//! rejects any relationship whose target lives in another mem
7//! (structurally impossible inside a single archive because
8//! `parse_markdown` tags every relationship with the archive's single
9//! mem, but the guard stays to catch engine refactors).
10
11use std::sync::Arc;
12
13use memstead_schema::{TypeDefinition, type_by_name};
14
15use super::ValidationError;
16use crate::entity::ParseResult;
17use crate::entity::store_builder::push_entities_into_store;
18use crate::graph::{LouvainOutput, community::detect_communities};
19use crate::store::Store;
20
21/// Fixed seed for Louvain — published once so both the validator and
22/// any downstream reproducibility checker can assert on the same
23/// value. Value `1` is arbitrary but pinned.
24pub const VALIDATOR_LOUVAIN_SEED: u32 = 1;
25
26/// Default resolution parameter for Louvain at ingress. Matches the
27/// `community.resolution` default used by every shipped schema so
28/// validator-built stores land at the same modularity the runtime
29/// would produce for the same bytes.
30pub const VALIDATOR_RESOLUTION: f64 = 1.0;
31
32/// One relationship whose target lives in a different mem than the
33/// one being validated/exported — i.e. an edge that cannot travel
34/// inside a single-mem archive. `install` refuses on these
35/// (`ARCHIVE_VALIDATION_FAILED`); `export` warns on them
36/// (`DANGLING_CROSS_MEM_EDGE_IN_EXPORT`) so the operator sees the
37/// install-time failure before sharing — one predicate, two postures.
38#[derive(Debug, Clone, PartialEq, Eq, serde::Serialize)]
39pub struct DanglingCrossMemEdge {
40    /// Archive-relative path of the entity carrying the edge.
41    pub entity_path: String,
42    /// Fully-qualified target id (e.g. `other-mem--thing`).
43    pub target_id: String,
44    /// The target's mem (the mem that won't travel in this archive).
45    pub target_mem: String,
46}
47
48/// Result of running graph checks — Store + communities, ready for
49/// downstream stats + canonical re-pack.
50#[derive(Debug)]
51pub struct GraphCheckResult {
52    pub store: Store,
53    pub communities: LouvainOutput,
54    /// Relationships whose target lives outside the validated mem.
55    /// Empty for a self-contained archive. In `cross_mem_as_error`
56    /// mode `build_and_check` returns `Err` on the first such edge and
57    /// this never carries entries; in lenient mode every offending edge
58    /// is collected here for the caller to surface as a warning.
59    pub dangling_cross_mem_edges: Vec<DanglingCrossMemEdge>,
60}
61
62/// Build a `Store` from parse results and run community detection.
63/// Rejects any parse-result relationship whose target lives in a
64/// different mem (defense-in-depth: `parse_markdown` already tags
65/// every relationship with the entity's own mem via
66/// `wiki_link_to_id`, so this should never fire on a well-formed
67/// archive — but any refactor that weakens that invariant will be
68/// caught here instead of silently diverging from runtime semantics).
69pub fn build_and_check(
70    parse_results: Vec<ParseResult>,
71    fallback_schema: &TypeDefinition,
72    mem_name: &str,
73    cross_mem_as_error: bool,
74) -> Result<GraphCheckResult, ValidationError> {
75    // One predicate (`rel.target.mem() != mem_name`), two postures.
76    // `install` / archive-load pass `cross_mem_as_error: true` and
77    // refuse on the first
78    // offending edge — a cross-mem edge can't resolve inside a
79    // single-mem archive. `export` passes `false` and collects every
80    // offending edge so it can warn (`DANGLING_CROSS_MEM_EDGE_IN_EXPORT`)
81    // without blocking the snapshot. Same condition either way, so the
82    // two surfaces can't drift.
83    if cross_mem_as_error
84        && let Some(pr) = parse_results.iter().find(|pr| {
85            pr.entity
86                .relationships
87                .iter()
88                .any(|r| r.target.mem() != mem_name)
89        })
90    {
91        let rel = pr
92            .entity
93            .relationships
94            .iter()
95            .find(|r| r.target.mem() != mem_name)
96            .expect("find guaranteed a match");
97        return Err(ValidationError::CrossMemRelationship {
98            path: pr.entity.file_path.clone(),
99            target: rel.target.as_ref().to_string(),
100        });
101    }
102    let dangling_cross_mem_edges = dangling_cross_mem_edges_in(&parse_results, mem_name);
103
104    let mut store = Store::new();
105    // Validator operates on isolated input; no roster, no drift detection —
106    // nested-prefix warnings would be noise in a schema-check run.
107    push_entities_into_store(&mut store, parse_results, fallback_schema, None);
108
109    let communities = detect_communities(
110        &store,
111        VALIDATOR_RESOLUTION,
112        VALIDATOR_LOUVAIN_SEED,
113        |rel_type| {
114            // Weight by the fallback schema's edge_weight lookup —
115            // every entity in this archive passed strict validation
116            // against a schema resolvable by type_by_name, so the
117            // weights that land in Louvain match what the runtime
118            // would use for the same bytes.
119            fallback_schema.edge_weight(rel_type) as f64
120        },
121    );
122
123    Ok(GraphCheckResult {
124        store,
125        communities,
126        dangling_cross_mem_edges,
127    })
128}
129
130/// The shared cross-mem predicate: every relationship in
131/// `parse_results` whose target lives in a mem other than
132/// `mem_name`. `build_and_check` (install/load) refuses on the first;
133/// the export side warns on all of them — both go through this one
134/// function so the surfaces can't drift.
135pub fn dangling_cross_mem_edges_in(
136    parse_results: &[ParseResult],
137    mem_name: &str,
138) -> Vec<DanglingCrossMemEdge> {
139    let mut edges = Vec::new();
140    for pr in parse_results {
141        for rel in &pr.entity.relationships {
142            if rel.target.mem() != mem_name {
143                edges.push(DanglingCrossMemEdge {
144                    entity_path: pr.entity.file_path.clone(),
145                    target_id: rel.target.as_ref().to_string(),
146                    target_mem: rel.target.mem().to_string(),
147                });
148            }
149        }
150    }
151    edges
152}
153
154/// Resolve the fallback type for Store construction given a config.
155/// Picks the first entry of `config.types` and falls back to the
156/// engine-wide fallback if unresolvable — the config checker has
157/// already confirmed every listed type resolves post-validation.
158pub fn resolve_fallback_type(config_types: Option<&[String]>) -> Arc<TypeDefinition> {
159    if let Some(name) = config_types.and_then(|v| v.first())
160        && let Some(s) = type_by_name(name)
161    {
162        return s;
163    }
164    crate::engine_fallback_type()
165}
166
167/// Walk the store and count entities and all out-edges. Used for
168/// `MemStats` post-validation.
169pub fn tally(store: &Store) -> (usize, usize) {
170    let entity_count = store.len();
171    let edge_count: usize = store.all_ids().map(|id| store.outgoing(id).len()).sum();
172    (entity_count, edge_count)
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178    use crate::entity::id::file_path_to_id;
179    use crate::entity::parser::parse_markdown;
180    use memstead_schema::type_by_name;
181
182    const MINIMAL_SPEC: &str = "\
183---
184type: spec
185created_date: 2026-01-15
186last_modified: 2026-01-15
187level: M0
188---
189# Alpha
190
191## Identity
192
193A
194
195## Purpose
196
197B
198
199## Specifies
200
201C
202
203## Constraints
204
205D
206
207## Rationale
208
209E
210
211## Relationships
212
213- **USES**: [[beta]]
214";
215
216    fn spec_type() -> Arc<TypeDefinition> {
217        type_by_name("spec").unwrap()
218    }
219
220    fn parse(path: &str, mem: &str, content: &str) -> ParseResult {
221        parse_markdown(content, path, &spec_type(), mem).unwrap()
222    }
223
224    #[test]
225    fn accepts_single_entity_archive() {
226        let result = build_and_check(
227            vec![parse("alpha.md", "v", MINIMAL_SPEC)],
228            &spec_type(),
229            "v",
230            true,
231        )
232        .unwrap();
233        assert!(result.store.contains(&file_path_to_id("alpha.md", "v")));
234    }
235
236    #[test]
237    fn materializes_stub_for_unresolved_wiki_link() {
238        let result = build_and_check(
239            vec![parse("alpha.md", "v", MINIMAL_SPEC)],
240            &spec_type(),
241            "v",
242            true,
243        )
244        .unwrap();
245        let stub_id = file_path_to_id("beta", "v");
246        let stub = result.store.get(&stub_id).expect("stub materialized");
247        assert!(stub.stub);
248    }
249
250    #[test]
251    fn empty_archive_yields_zero_communities() {
252        let result = build_and_check(vec![], &spec_type(), "v", true).unwrap();
253        assert_eq!(result.communities.count, 0);
254    }
255
256    #[test]
257    fn rejects_cross_mem_relationship() {
258        // Craft a parse result with a handcrafted cross-mem
259        // relationship. `parse_markdown` won't produce this (it always
260        // tags rels with the entity's mem), so build it by hand.
261        let cross_mem_pr = || {
262            let mut pr = parse("alpha.md", "v", MINIMAL_SPEC);
263            pr.entity.relationships.push(crate::entity::Relationship {
264                rel_type: "DEPENDS_ON".to_string(),
265                target: crate::entity::EntityId("other-mem--thing".to_string()),
266                description: None,
267            });
268            pr
269        };
270        let err = build_and_check(vec![cross_mem_pr()], &spec_type(), "v", true).unwrap_err();
271        assert!(matches!(err, ValidationError::CrossMemRelationship { .. }));
272
273        // Lenient mode: the same cross-mem edge is collected as data
274        // (no error), so the export side can warn without blocking.
275        let result = build_and_check(vec![cross_mem_pr()], &spec_type(), "v", false).unwrap();
276        assert_eq!(result.dangling_cross_mem_edges.len(), 1);
277        let edge = &result.dangling_cross_mem_edges[0];
278        assert_eq!(edge.target_id, "other-mem--thing");
279        assert_eq!(edge.target_mem, "other-mem");
280    }
281
282    #[test]
283    fn resolve_fallback_type_picks_first_entry() {
284        let s = resolve_fallback_type(Some(&["concept".to_string(), "spec".to_string()]));
285        assert_eq!(s.name.as_str(), "concept");
286    }
287
288    #[test]
289    fn resolve_fallback_type_falls_back_on_unknown() {
290        let s = resolve_fallback_type(Some(&["bogus".to_string()]));
291        // Engine-wide fallback is `spec`.
292        assert_eq!(s.name.as_str(), "spec");
293    }
294
295    #[test]
296    fn resolve_fallback_type_falls_back_on_empty() {
297        let s = resolve_fallback_type(None);
298        assert_eq!(s.name.as_str(), "spec");
299    }
300}
memstead_base/validator/graph.rs

memstead_base/validator/
graph.rs
