memstead_schema/
content_expr.rs

1//! Content expressions — the compiled half of the section-format
2//! vocabulary (agent-toolbox plan 08).
3//!
4//! A section can declare its markdown shape as a flat expression over
5//! the mdast block-node vocabulary, verbatim: `paragraph`, `list`,
6//! `table`, `code`, `blockquote`, `heading`, `thematicBreak`, `html`.
7//! Operators: sequence (space), alternation of names
8//! (`(paragraph | list)`), repetition `+` `*` `?` on names and on
9//! parenthesized groups. The grammar is deliberately **regular** — no
10//! nesting, no recursion — the ProseMirror precedent: a deterministic
11//! content model is what lets a refusal say "expected X at position N"
12//! instead of "the structure didn't match".
13//!
14//! This module owns parsing, validation, and matching. It knows
15//! nothing about markdown itself — the consumer (the engine's
16//! section-format evaluator) reduces a section body to a sequence of
17//! [`ObservedBlock`]s with a real CommonMark parser and hands it to
18//! [`ContentExpr::match_blocks`].
19
20use serde::Serialize;
21
22/// The mdast block-node names the vocabulary admits, verbatim
23/// (including `thematicBreak`'s camelCase — mdast names are used
24/// unchanged because they are the vocabulary agents already know from
25/// the remark/MDX ecosystem).
26pub const BLOCK_NAMES: &[&str] = &[
27    "paragraph",
28    "list",
29    "table",
30    "code",
31    "blockquote",
32    "heading",
33    "thematicBreak",
34    "html",
35];
36
37/// One observed top-level block of a section body, as reduced by the
38/// consumer's markdown parser. Carries exactly the attributes the
39/// expression vocabulary can constrain.
40#[derive(Debug, Clone, PartialEq, Eq)]
41pub enum ObservedBlock {
42    Paragraph,
43    /// `ordered: false` is a bullet list.
44    List {
45        ordered: bool,
46    },
47    Table,
48    /// `lang` is the fenced-code info string's first word, empty for
49    /// none (and for indented code blocks).
50    Code {
51        lang: String,
52    },
53    Blockquote,
54    /// ATX or setext heading depth (1–6).
55    Heading {
56        depth: u8,
57    },
58    ThematicBreak,
59    Html,
60}
61
62impl ObservedBlock {
63    /// The mdast name of this block — the `found` vocabulary in
64    /// mismatch payloads.
65    pub fn name(&self) -> &'static str {
66        match self {
67            Self::Paragraph => "paragraph",
68            Self::List { .. } => "list",
69            Self::Table => "table",
70            Self::Code { .. } => "code",
71            Self::Blockquote => "blockquote",
72            Self::Heading { .. } => "heading",
73            Self::ThematicBreak => "thematicBreak",
74            Self::Html => "html",
75        }
76    }
77
78    /// Rendered with its attribute where one exists — the display
79    /// form used in `found` sequences (`list(bullet)`, `heading(3)`).
80    pub fn display(&self) -> String {
81        match self {
82            Self::List { ordered: false } => "list(bullet)".to_string(),
83            Self::List { ordered: true } => "list(ordered)".to_string(),
84            Self::Heading { depth } => format!("heading({depth})"),
85            Self::Code { lang } if !lang.is_empty() => format!("code(lang={lang})"),
86            other => other.name().to_string(),
87        }
88    }
89}
90
91/// One terminal of a compiled expression: a block name plus its
92/// optional attribute constraint.
93#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
94pub struct Terminal {
95    pub name: String,
96    /// `bullet` / `ordered` for `list`, `3`..`6` for `heading`,
97    /// `lang=<tag>` for `code`. `None` admits any attribute.
98    pub attr: Option<String>,
99}
100
101impl Terminal {
102    /// Display form (`list(bullet)`, `heading(3)`, `paragraph`) —
103    /// used for `expected_next` payloads.
104    pub fn display(&self) -> String {
105        match &self.attr {
106            Some(a) => format!("{}({})", self.name, a),
107            None => self.name.clone(),
108        }
109    }
110
111    /// Whether this terminal admits the observed block.
112    pub fn admits(&self, block: &ObservedBlock) -> bool {
113        if self.name != block.name() {
114            return false;
115        }
116        let Some(attr) = &self.attr else {
117            return true;
118        };
119        match block {
120            ObservedBlock::List { ordered } => {
121                (attr == "bullet" && !ordered) || (attr == "ordered" && *ordered)
122            }
123            ObservedBlock::Heading { depth } => attr.parse::<u8>() == Ok(*depth),
124            ObservedBlock::Code { lang } => attr
125                .strip_prefix("lang=")
126                .is_some_and(|expected| expected == lang),
127            // The remaining kinds admit no attributes; the parser
128            // refuses attributes on them, so this arm is unreachable
129            // for a parsed expression.
130            _ => false,
131        }
132    }
133}
134
135/// Typed parse/validation failure for a content expression. `offender`
136/// carries the offending token so loader errors can name it.
137#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
138pub enum ContentExprError {
139    #[error(
140        "unknown block name '{0}' — the vocabulary is paragraph, list, table, code, blockquote, heading, thematicBreak, html"
141    )]
142    UnknownBlockName(String),
143    #[error("invalid attribute '{attr}' on '{name}'")]
144    InvalidAttribute { name: String, attr: String },
145    #[error(
146        "heading depth {0} is outside 3–6 — h1/h2 are the entity's own levels (title, section delimiters)"
147    )]
148    HeadingDepthReserved(u8),
149    #[error(
150        "nested groups are not allowed — the expression grammar is regular (no nesting, no recursion)"
151    )]
152    NestedGroup,
153    #[error(
154        "a group must be either an alternation of names or a sequence — mixing '|' and sequence inside one group is not allowed"
155    )]
156    MixedGroupOperators,
157    #[error("unbalanced parentheses")]
158    UnbalancedParens,
159    #[error("repetition operator '{0}' has nothing to apply to")]
160    DanglingRepetition(char),
161    #[error("empty expression")]
162    Empty,
163    #[error("empty group")]
164    EmptyGroup,
165    #[error("unexpected token '{0}'")]
166    UnexpectedToken(String),
167}
168
169/// How often a term repeats.
170#[derive(Debug, Clone, Copy, PartialEq, Eq)]
171enum Repeat {
172    One,
173    OneOrMore,
174    ZeroOrMore,
175    ZeroOrOne,
176}
177
178/// One term of the (flat) expression: a single terminal, an
179/// alternation of terminals, or a sequence group — each with a
180/// repetition.
181#[derive(Debug, Clone, PartialEq, Eq)]
182enum Term {
183    Atom(Terminal, Repeat),
184    /// `(a | b | c)` — names only.
185    Alternation(Vec<Terminal>, Repeat),
186    /// `(a b c)` — a repeated sequence group.
187    Sequence(Vec<Terminal>, Repeat),
188}
189
190/// A parsed, validated content expression. Matching runs an NFA
191/// simulation over the observed block sequence so a failure can
192/// report the exact position and the terminals that would have been
193/// legal there.
194#[derive(Debug, Clone, PartialEq, Eq)]
195pub struct ContentExpr {
196    source: String,
197    terms: Vec<Term>,
198    nfa: Nfa,
199}
200
201/// Match failure: the observed sequence does not satisfy the
202/// expression. `failed_at` is the index into the observed sequence
203/// (== its length when the body ended too early); `expected_next`
204/// lists the display forms of the terminals legal at that position;
205/// `found` is the display form of the offending block (`None` at
206/// end-of-body).
207#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
208pub struct MatchFailure {
209    pub failed_at: usize,
210    pub expected_next: Vec<String>,
211    pub found: Option<String>,
212}
213
214impl ContentExpr {
215    /// Parse and validate an expression string. The compiled
216    /// expression is cached on the schema at load time — parse once,
217    /// match per write.
218    pub fn parse(source: &str) -> Result<Self, ContentExprError> {
219        let terms = parse_terms(source)?;
220        if terms.is_empty() {
221            return Err(ContentExprError::Empty);
222        }
223        let nfa = Nfa::compile(&terms);
224        Ok(Self {
225            source: source.to_string(),
226            terms,
227            nfa,
228        })
229    }
230
231    /// The verbatim declaration text.
232    pub fn source(&self) -> &str {
233        &self.source
234    }
235
236    /// The distinct block names the expression mentions — the loader
237    /// uses this for `item_pattern` legality ("exactly one of `list`
238    /// / `paragraph`", counted by name, repeated occurrences of the
239    /// same kind are fine).
240    pub fn mentioned_names(&self) -> Vec<&str> {
241        let mut names: Vec<&str> = self
242            .all_terminals()
243            .map(|t| t.name.as_str())
244            .collect::<std::collections::BTreeSet<_>>()
245            .into_iter()
246            .collect();
247        names.sort_unstable();
248        names
249    }
250
251    fn all_terminals(&self) -> impl Iterator<Item = &Terminal> {
252        self.terms.iter().flat_map(|t| match t {
253            Term::Atom(a, _) => std::slice::from_ref(a).iter(),
254            Term::Alternation(v, _) | Term::Sequence(v, _) => v.iter(),
255        })
256    }
257
258    /// Match the observed block sequence against the expression.
259    pub fn match_blocks(&self, blocks: &[ObservedBlock]) -> Result<(), MatchFailure> {
260        self.nfa.run(blocks)
261    }
262}
263
264// ---------------------------------------------------------------------------
265// Parser
266// ---------------------------------------------------------------------------
267
268#[derive(Debug, Clone, PartialEq, Eq)]
269enum Token {
270    Name(Terminal),
271    Open,
272    Close,
273    Pipe,
274    Rep(char),
275}
276
277fn tokenize(source: &str) -> Result<Vec<Token>, ContentExprError> {
278    let mut out = Vec::new();
279    let chars: Vec<char> = source.chars().collect();
280    let mut i = 0;
281    while i < chars.len() {
282        let c = chars[i];
283        match c {
284            ' ' | '\t' | '\n' => i += 1,
285            '(' => {
286                // Disambiguate group-open from attribute-open: an
287                // attribute paren directly follows a name and is
288                // consumed by the name lexer below, so a bare '(' here
289                // is always a group.
290                out.push(Token::Open);
291                i += 1;
292            }
293            ')' => {
294                out.push(Token::Close);
295                i += 1;
296            }
297            '|' => {
298                out.push(Token::Pipe);
299                i += 1;
300            }
301            '+' | '*' | '?' => {
302                out.push(Token::Rep(c));
303                i += 1;
304            }
305            c if c.is_ascii_alphabetic() => {
306                let start = i;
307                while i < chars.len() && (chars[i].is_ascii_alphanumeric()) {
308                    i += 1;
309                }
310                let name: String = chars[start..i].iter().collect();
311                let mut attr = None;
312                if i < chars.len() && chars[i] == '(' {
313                    // Attribute parens bind tighter than group parens
314                    // — only when the content is attribute-shaped
315                    // (no spaces / pipes before the close).
316                    let close = chars[i + 1..]
317                        .iter()
318                        .position(|&c| c == ')')
319                        .map(|p| i + 1 + p);
320                    if let Some(close_idx) = close {
321                        let inner: String = chars[i + 1..close_idx].iter().collect();
322                        if !inner.contains(' ') && !inner.contains('|') && !inner.is_empty() {
323                            attr = Some(inner);
324                            i = close_idx + 1;
325                        }
326                    }
327                }
328                out.push(Token::Name(validate_terminal(name, attr)?));
329            }
330            other => return Err(ContentExprError::UnexpectedToken(other.to_string())),
331        }
332    }
333    Ok(out)
334}
335
336fn validate_terminal(name: String, attr: Option<String>) -> Result<Terminal, ContentExprError> {
337    if !BLOCK_NAMES.contains(&name.as_str()) {
338        return Err(ContentExprError::UnknownBlockName(name));
339    }
340    if let Some(a) = &attr {
341        let valid = match name.as_str() {
342            "list" => a == "bullet" || a == "ordered",
343            "heading" => match a.parse::<u8>() {
344                Ok(d @ 3..=6) => {
345                    let _ = d;
346                    true
347                }
348                Ok(d @ (1 | 2)) => return Err(ContentExprError::HeadingDepthReserved(d)),
349                _ => false,
350            },
351            "code" => a.starts_with("lang=") && a.len() > "lang=".len(),
352            _ => false,
353        };
354        if !valid {
355            return Err(ContentExprError::InvalidAttribute {
356                name,
357                attr: a.clone(),
358            });
359        }
360    }
361    Ok(Terminal { name, attr })
362}
363
364fn parse_terms(source: &str) -> Result<Vec<Term>, ContentExprError> {
365    let tokens = tokenize(source)?;
366    let mut terms = Vec::new();
367    let mut i = 0;
368    while i < tokens.len() {
369        match &tokens[i] {
370            Token::Name(t) => {
371                let rep = take_rep(&tokens, i + 1);
372                let consumed = 1 + usize::from(rep != Repeat::One);
373                terms.push(Term::Atom(t.clone(), rep));
374                i += consumed;
375            }
376            Token::Open => {
377                // Collect group members up to the matching close —
378                // flat only, a nested Open refuses.
379                let mut members: Vec<Terminal> = Vec::new();
380                let mut saw_pipe = false;
381                let mut saw_adjacent_names = false;
382                let mut j = i + 1;
383                let mut prev_was_name = false;
384                loop {
385                    match tokens.get(j) {
386                        None => return Err(ContentExprError::UnbalancedParens),
387                        Some(Token::Close) => break,
388                        Some(Token::Open) => return Err(ContentExprError::NestedGroup),
389                        Some(Token::Pipe) => {
390                            saw_pipe = true;
391                            prev_was_name = false;
392                            j += 1;
393                        }
394                        Some(Token::Name(t)) => {
395                            if prev_was_name {
396                                saw_adjacent_names = true;
397                            }
398                            members.push(t.clone());
399                            prev_was_name = true;
400                            j += 1;
401                        }
402                        Some(Token::Rep(c)) => {
403                            // Repetition inside a group would nest.
404                            return Err(ContentExprError::DanglingRepetition(*c));
405                        }
406                    }
407                }
408                if members.is_empty() {
409                    return Err(ContentExprError::EmptyGroup);
410                }
411                if saw_pipe && saw_adjacent_names {
412                    return Err(ContentExprError::MixedGroupOperators);
413                }
414                let rep = take_rep(&tokens, j + 1);
415                let consumed = j + 1 - i + usize::from(rep != Repeat::One);
416                if saw_pipe {
417                    terms.push(Term::Alternation(members, rep));
418                } else {
419                    terms.push(Term::Sequence(members, rep));
420                }
421                i += consumed;
422            }
423            Token::Close => return Err(ContentExprError::UnbalancedParens),
424            Token::Pipe => {
425                return Err(ContentExprError::UnexpectedToken("|".to_string()));
426            }
427            Token::Rep(c) => return Err(ContentExprError::DanglingRepetition(*c)),
428        }
429    }
430    Ok(terms)
431}
432
433fn take_rep(tokens: &[Token], at: usize) -> Repeat {
434    match tokens.get(at) {
435        Some(Token::Rep('+')) => Repeat::OneOrMore,
436        Some(Token::Rep('*')) => Repeat::ZeroOrMore,
437        Some(Token::Rep('?')) => Repeat::ZeroOrOne,
438        _ => Repeat::One,
439    }
440}
441
442// ---------------------------------------------------------------------------
443// NFA
444// ---------------------------------------------------------------------------
445
446/// Thompson-style NFA over [`Terminal`] transitions. Small by
447/// construction (the grammar is regular and flat), simulated with a
448/// state-set walk so failures report position + legal-next terminals.
449#[derive(Debug, Clone, PartialEq, Eq)]
450struct Nfa {
451    /// `transitions[state]` = list of `(terminal, next_state)`.
452    transitions: Vec<Vec<(Terminal, usize)>>,
453    /// `epsilons[state]` = ε-reachable next states.
454    epsilons: Vec<Vec<usize>>,
455    accept: usize,
456}
457
458impl Nfa {
459    fn compile(terms: &[Term]) -> Self {
460        let mut nfa = Nfa {
461            transitions: vec![Vec::new()],
462            epsilons: vec![Vec::new()],
463            accept: 0,
464        };
465        let mut current = 0;
466        for term in terms {
467            current = nfa.append_term(current, term);
468        }
469        nfa.accept = current;
470        nfa
471    }
472
473    fn new_state(&mut self) -> usize {
474        self.transitions.push(Vec::new());
475        self.epsilons.push(Vec::new());
476        self.transitions.len() - 1
477    }
478
479    /// Append one term after `from`; returns the term's exit state.
480    fn append_term(&mut self, from: usize, term: &Term) -> usize {
481        type UnitBuilder = Box<dyn Fn(&mut Nfa, usize) -> usize>;
482        let (unit_entry_build, rep): (UnitBuilder, Repeat) = match term {
483            Term::Atom(t, rep) => {
484                let t = t.clone();
485                (
486                    Box::new(move |nfa: &mut Nfa, from: usize| {
487                        let next = nfa.new_state();
488                        nfa.transitions[from].push((t.clone(), next));
489                        next
490                    }),
491                    *rep,
492                )
493            }
494            Term::Alternation(alts, rep) => {
495                let alts = alts.clone();
496                (
497                    Box::new(move |nfa: &mut Nfa, from: usize| {
498                        let next = nfa.new_state();
499                        for t in &alts {
500                            nfa.transitions[from].push((t.clone(), next));
501                        }
502                        next
503                    }),
504                    *rep,
505                )
506            }
507            Term::Sequence(seq, rep) => {
508                let seq = seq.clone();
509                (
510                    Box::new(move |nfa: &mut Nfa, from: usize| {
511                        let mut cur = from;
512                        for t in &seq {
513                            let next = nfa.new_state();
514                            nfa.transitions[cur].push((t.clone(), next));
515                            cur = next;
516                        }
517                        cur
518                    }),
519                    *rep,
520                )
521            }
522        };
523
524        match rep {
525            Repeat::One => unit_entry_build(self, from),
526            Repeat::ZeroOrOne => {
527                let exit = unit_entry_build(self, from);
528                self.epsilons[from].push(exit);
529                exit
530            }
531            Repeat::OneOrMore => {
532                let exit = unit_entry_build(self, from);
533                // Loop back: from the exit, the unit can run again.
534                let exit2 = unit_entry_build(self, exit);
535                self.epsilons[exit2].push(exit);
536                self.epsilons[exit].push(exit2);
537                // Collapse: use `exit` as the canonical exit; the
538                // second copy shares it via the ε-cycle above.
539                exit
540            }
541            Repeat::ZeroOrMore => {
542                let exit = unit_entry_build(self, from);
543                self.epsilons[exit].push(from);
544                self.epsilons[from].push(exit);
545                exit
546            }
547        }
548    }
549
550    fn closure(&self, states: &mut std::collections::BTreeSet<usize>) {
551        let mut stack: Vec<usize> = states.iter().copied().collect();
552        while let Some(s) = stack.pop() {
553            for &e in &self.epsilons[s] {
554                if states.insert(e) {
555                    stack.push(e);
556                }
557            }
558        }
559    }
560
561    fn run(&self, blocks: &[ObservedBlock]) -> Result<(), MatchFailure> {
562        let mut current: std::collections::BTreeSet<usize> = std::iter::once(0).collect();
563        self.closure(&mut current);
564        for (i, block) in blocks.iter().enumerate() {
565            let mut next: std::collections::BTreeSet<usize> = Default::default();
566            for &s in &current {
567                for (terminal, to) in &self.transitions[s] {
568                    if terminal.admits(block) {
569                        next.insert(*to);
570                    }
571                }
572            }
573            if next.is_empty() {
574                return Err(MatchFailure {
575                    failed_at: i,
576                    expected_next: self.expected_from(&current),
577                    found: Some(block.display()),
578                });
579            }
580            self.closure(&mut next);
581            current = next;
582        }
583        if current.contains(&self.accept) {
584            Ok(())
585        } else {
586            Err(MatchFailure {
587                failed_at: blocks.len(),
588                expected_next: self.expected_from(&current),
589                found: None,
590            })
591        }
592    }
593
594    /// The display forms of every terminal legal from the state set —
595    /// deduplicated, deterministic order.
596    fn expected_from(&self, states: &std::collections::BTreeSet<usize>) -> Vec<String> {
597        let mut out: std::collections::BTreeSet<String> = Default::default();
598        for &s in states {
599            for (terminal, _) in &self.transitions[s] {
600                out.insert(terminal.display());
601            }
602        }
603        out.into_iter().collect()
604    }
605}
606
607#[cfg(test)]
608mod tests {
609    use super::*;
610
611    fn bullet() -> ObservedBlock {
612        ObservedBlock::List { ordered: false }
613    }
614    fn h(depth: u8) -> ObservedBlock {
615        ObservedBlock::Heading { depth }
616    }
617    fn para() -> ObservedBlock {
618        ObservedBlock::Paragraph
619    }
620
621    #[test]
622    fn single_name_matches_exactly_one_block() {
623        let e = ContentExpr::parse("list(bullet)").unwrap();
624        assert!(e.match_blocks(&[bullet()]).is_ok());
625        assert!(e.match_blocks(&[]).is_err());
626        assert!(e.match_blocks(&[bullet(), bullet()]).is_err());
627        assert!(
628            e.match_blocks(&[ObservedBlock::List { ordered: true }])
629                .is_err()
630        );
631    }
632
633    #[test]
634    fn plan_example_repeated_group() {
635        // The plan's own example: "(heading(3) list(bullet))+"
636        let e = ContentExpr::parse("(heading(3) list(bullet))+").unwrap();
637        assert!(e.match_blocks(&[h(3), bullet()]).is_ok());
638        assert!(e.match_blocks(&[h(3), bullet(), h(3), bullet()]).is_ok());
639        assert!(e.match_blocks(&[h(3)]).is_err(), "group half-done");
640        assert!(e.match_blocks(&[]).is_err(), "+ needs at least one");
641        assert!(e.match_blocks(&[bullet(), h(3)]).is_err(), "order matters");
642        assert!(e.match_blocks(&[h(4), bullet()]).is_err(), "depth pinned");
643    }
644
645    #[test]
646    fn alternation_and_optional() {
647        let e = ContentExpr::parse("(paragraph | list) table?").unwrap();
648        assert!(e.match_blocks(&[para()]).is_ok());
649        assert!(e.match_blocks(&[bullet()]).is_ok());
650        assert!(e.match_blocks(&[para(), ObservedBlock::Table]).is_ok());
651        assert!(e.match_blocks(&[ObservedBlock::Table]).is_err());
652    }
653
654    #[test]
655    fn star_admits_empty() {
656        let e = ContentExpr::parse("paragraph*").unwrap();
657        assert!(e.match_blocks(&[]).is_ok());
658        assert!(e.match_blocks(&[para(), para(), para()]).is_ok());
659        assert!(e.match_blocks(&[bullet()]).is_err());
660    }
661
662    #[test]
663    fn sequence_of_names() {
664        let e = ContentExpr::parse("paragraph list(bullet) paragraph?").unwrap();
665        assert!(e.match_blocks(&[para(), bullet()]).is_ok());
666        assert!(e.match_blocks(&[para(), bullet(), para()]).is_ok());
667        assert!(e.match_blocks(&[bullet(), para()]).is_err());
668    }
669
670    #[test]
671    fn failure_reports_position_and_expected_next() {
672        let e = ContentExpr::parse("heading(3) list(bullet)+").unwrap();
673        let err = e.match_blocks(&[h(3), para()]).unwrap_err();
674        assert_eq!(err.failed_at, 1);
675        assert_eq!(err.expected_next, vec!["list(bullet)".to_string()]);
676        assert_eq!(err.found.as_deref(), Some("paragraph"));
677
678        let err = e.match_blocks(&[h(3)]).unwrap_err();
679        assert_eq!(err.failed_at, 1);
680        assert_eq!(err.found, None, "body ended too early");
681        assert_eq!(err.expected_next, vec!["list(bullet)".to_string()]);
682    }
683
684    #[test]
685    fn code_lang_attribute() {
686        let e = ContentExpr::parse("code(lang=rust)").unwrap();
687        assert!(
688            e.match_blocks(&[ObservedBlock::Code {
689                lang: "rust".into()
690            }])
691            .is_ok()
692        );
693        assert!(
694            e.match_blocks(&[ObservedBlock::Code {
695                lang: "python".into()
696            }])
697            .is_err()
698        );
699        let bare = ContentExpr::parse("code").unwrap();
700        assert!(
701            bare.match_blocks(&[ObservedBlock::Code { lang: "".into() }])
702                .is_ok()
703        );
704    }
705
706    #[test]
707    fn validation_refusals() {
708        assert!(matches!(
709            ContentExpr::parse("bulletList"),
710            Err(ContentExprError::UnknownBlockName(n)) if n == "bulletList"
711        ));
712        assert!(matches!(
713            ContentExpr::parse("heading(2)"),
714            Err(ContentExprError::HeadingDepthReserved(2))
715        ));
716        assert!(matches!(
717            ContentExpr::parse("heading(1) list"),
718            Err(ContentExprError::HeadingDepthReserved(1))
719        ));
720        assert!(matches!(
721            ContentExpr::parse("list(numbered)"),
722            Err(ContentExprError::InvalidAttribute { .. })
723        ));
724        assert!(matches!(
725            ContentExpr::parse("paragraph(x)"),
726            Err(ContentExprError::InvalidAttribute { .. })
727        ));
728        assert!(matches!(
729            ContentExpr::parse("((list))"),
730            Err(ContentExprError::NestedGroup)
731        ));
732        assert!(matches!(
733            ContentExpr::parse("(paragraph | list table)"),
734            Err(ContentExprError::MixedGroupOperators)
735        ));
736        assert!(matches!(
737            ContentExpr::parse("(list"),
738            Err(ContentExprError::UnbalancedParens)
739        ));
740        assert!(matches!(
741            ContentExpr::parse("+list"),
742            Err(ContentExprError::DanglingRepetition('+'))
743        ));
744        assert!(matches!(
745            ContentExpr::parse(""),
746            Err(ContentExprError::Empty)
747        ));
748        assert!(matches!(
749            ContentExpr::parse("()"),
750            Err(ContentExprError::EmptyGroup)
751        ));
752    }
753
754    #[test]
755    fn mentioned_names_deduplicate() {
756        let e = ContentExpr::parse("(heading(3) list(bullet))+ list(bullet)?").unwrap();
757        assert_eq!(e.mentioned_names(), vec!["heading", "list"]);
758    }
759}
760
761/// Seeded adversarial smoke over the content-expression parser and
762/// matcher, the third trust-boundary target: published archives embed a
763/// schema tree, so foreign expression strings reach this parser.
764///
765/// Same discipline as the memstead-base harnesses (hand-rolled
766/// xorshift64, deterministic, bounded, failures reproduce from the seed
767/// and case index). Lives inside this module because the properties pin
768/// private structure: NFA size stays linear in the expression's
769/// terminal count (no adversarial state blowup), which needs `nfa` and
770/// `terms` access.
771///
772/// Per case:
773/// - parsing never panics; it returns `Ok` or a typed
774///   [`ContentExprError`];
775/// - parse-source-parse is stable: an accepted expression's verbatim
776///   `source()` re-parses to a structurally identical expression;
777/// - the compiled NFA is linearly bounded: `transitions.len()` never
778///   exceeds `1 + 2 x` the total terminal occurrences (OneOrMore builds
779///   its unit twice, everything else once);
780/// - matching arbitrary observed-block sequences never panics, is
781///   deterministic, and every failure payload is coherent: `found`
782///   present exactly when the failure is not end-of-body, `failed_at`
783///   in bounds, and `found` equal to the offending block's display.
784#[cfg(test)]
785mod adversarial {
786    use super::*;
787    use std::panic::{AssertUnwindSafe, catch_unwind};
788
789    // Measured 2026-08-22 (debug build, M-series): 3 x 3000 cases with
790    // four match sequences each, well under a second.
791    const CASES_PER_SEED: usize = 3000;
792
793    struct Xorshift(u64);
794    impl Xorshift {
795        fn next(&mut self) -> u64 {
796            let mut x = self.0;
797            x ^= x << 13;
798            x ^= x >> 7;
799            x ^= x << 17;
800            self.0 = x;
801            x
802        }
803        fn pick(&mut self, n: usize) -> usize {
804            (self.next() % n as u64) as usize
805        }
806    }
807
808    /// Decision-point fragments: every block name (and lookalikes with
809    /// wrong case or unknown spelling), every attribute shape (valid,
810    /// reserved, out-of-range, malformed), every operator, and junk.
811    const FRAGMENTS: &[&str] = &[
812        "paragraph",
813        "list",
814        "table",
815        "code",
816        "blockquote",
817        "heading",
818        "thematicBreak",
819        "html",
820        "bulletList",
821        "Paragraph",
822        "thematicbreak",
823        "p",
824        "(bullet)",
825        "(ordered)",
826        "(numbered)",
827        "(3)",
828        "(6)",
829        "(2)",
830        "(1)",
831        "(7)",
832        "(0)",
833        "(255)",
834        "(lang=rust)",
835        "(lang=)",
836        "(lang=a b)",
837        "()",
838        "(x y)",
839        "(a|b)",
840        "+",
841        "*",
842        "?",
843        "|",
844        "(",
845        ")",
846        " ",
847        "\t",
848        "\n",
849        "++",
850        "??",
851        "((",
852        "))",
853        "!",
854        "é",
855        "0",
856        "list(bullet)",
857        "heading(3)",
858    ];
859
860    /// Valid seed expressions the generator splices and truncates.
861    const SEED_EXPRS: &[&str] = &[
862        "list(bullet)",
863        "(heading(3) list(bullet))+",
864        "(paragraph | list) table?",
865        "paragraph*",
866        "paragraph list(bullet) paragraph?",
867        "code(lang=rust)",
868        "heading(3) list(bullet)+ (paragraph | blockquote)* thematicBreak? html",
869    ];
870
871    fn char_boundary(s: &str, mut i: usize) -> usize {
872        while i < s.len() && !s.is_char_boundary(i) {
873            i += 1;
874        }
875        i
876    }
877
878    fn gen_expr(rng: &mut Xorshift) -> String {
879        match rng.pick(3) {
880            0 => {
881                let n = 1 + rng.pick(12);
882                let mut out = String::new();
883                for _ in 0..n {
884                    out.push_str(FRAGMENTS[rng.pick(FRAGMENTS.len())]);
885                    if rng.pick(3) == 0 {
886                        out.push(' ');
887                    }
888                }
889                out
890            }
891            1 => {
892                let seed = SEED_EXPRS[rng.pick(SEED_EXPRS.len())];
893                let at = char_boundary(seed, rng.pick(seed.len() + 1));
894                let frag = FRAGMENTS[rng.pick(FRAGMENTS.len())];
895                format!("{}{}{}", &seed[..at], frag, &seed[at..])
896            }
897            _ => {
898                let seed = SEED_EXPRS[rng.pick(SEED_EXPRS.len())];
899                seed[..char_boundary(seed, rng.pick(seed.len() + 1))].to_string()
900            }
901        }
902    }
903
904    fn gen_block(rng: &mut Xorshift) -> ObservedBlock {
905        match rng.pick(8) {
906            0 => ObservedBlock::Paragraph,
907            1 => ObservedBlock::List {
908                ordered: rng.pick(2) == 0,
909            },
910            2 => ObservedBlock::Table,
911            3 => ObservedBlock::Code {
912                lang: ["", "rust", "python", "lang=", "é🦀"][rng.pick(5)].to_string(),
913            },
914            4 => ObservedBlock::Blockquote,
915            5 => ObservedBlock::Heading {
916                depth: (rng.pick(9)) as u8,
917            },
918            6 => ObservedBlock::ThematicBreak,
919            _ => ObservedBlock::Html,
920        }
921    }
922
923    fn exercise(rng: &mut Xorshift, source: &str) {
924        let Ok(expr) = ContentExpr::parse(source) else {
925            return; // a typed refusal is a correct outcome
926        };
927
928        // parse-source-parse stability: the verbatim source re-parses
929        // to a structurally identical expression.
930        let again = ContentExpr::parse(expr.source())
931            .expect("an accepted expression's source must re-parse");
932        assert_eq!(again, expr, "parse-source-parse is not stable");
933
934        // Linear NFA bound: OneOrMore builds its unit twice, everything
935        // else once, so states never exceed 1 + 2x terminal occurrences.
936        let total_members: usize = expr
937            .terms
938            .iter()
939            .map(|t| match t {
940                Term::Atom(..) => 1,
941                Term::Alternation(v, _) | Term::Sequence(v, _) => v.len(),
942            })
943            .sum();
944        assert!(
945            expr.nfa.transitions.len() <= 1 + 2 * total_members,
946            "NFA state blowup: {} states for {} terminal occurrences (source {source:?})",
947            expr.nfa.transitions.len(),
948            total_members
949        );
950
951        // Matching: no panic, deterministic, coherent failure payloads.
952        for _ in 0..4 {
953            let blocks: Vec<ObservedBlock> = (0..rng.pick(12)).map(|_| gen_block(rng)).collect();
954            let first = expr.match_blocks(&blocks);
955            let second = expr.match_blocks(&blocks);
956            assert_eq!(first, second, "matching is not deterministic");
957            if let Err(f) = first {
958                assert!(
959                    f.failed_at <= blocks.len(),
960                    "failed_at out of bounds: {} > {}",
961                    f.failed_at,
962                    blocks.len()
963                );
964                match &f.found {
965                    Some(found) => {
966                        assert!(f.failed_at < blocks.len(), "found set at end-of-body");
967                        assert_eq!(
968                            *found,
969                            blocks[f.failed_at].display(),
970                            "found does not name the offending block"
971                        );
972                    }
973                    None => assert_eq!(
974                        f.failed_at,
975                        blocks.len(),
976                        "end-of-body failure not at the end"
977                    ),
978                }
979            }
980        }
981    }
982
983    /// Full replay of the committed shared corpus
984    /// (`fuzz/corpus/content_expr`, seeds for the coverage-guided long
985    /// tier) as ordinary tests; `seed-*` members must parse, keeping
986    /// the corpus alive. Skips loudly when the corpus is absent (a
987    /// packaged crate has no fuzz tree).
988    #[test]
989    fn committed_content_expr_corpus_replays() {
990        let dir =
991            std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("../../fuzz/corpus/content_expr");
992        if !dir.is_dir() {
993            eprintln!("SKIP: shared fuzz corpus not present at {}", dir.display());
994            return;
995        }
996        let mut rng = Xorshift(0x5eed_e0c0);
997        let mut replayed = 0;
998        for entry in std::fs::read_dir(&dir).unwrap() {
999            let path = entry.unwrap().path();
1000            let Ok(source) = std::fs::read_to_string(&path) else {
1001                continue; // non-UTF-8 corpus members are for the byte-level fuzzer
1002            };
1003            let name = path.file_name().unwrap().to_string_lossy().into_owned();
1004            if name.starts_with("seed-") {
1005                assert!(
1006                    ContentExpr::parse(&source).is_ok(),
1007                    "materialized seed expression {name} must parse: {source:?}"
1008                );
1009            }
1010            if let Err(payload) = catch_unwind(AssertUnwindSafe(|| exercise(&mut rng, &source))) {
1011                let msg = payload
1012                    .downcast_ref::<String>()
1013                    .map(|s| s.as_str())
1014                    .or_else(|| payload.downcast_ref::<&str>().copied())
1015                    .unwrap_or("<non-string panic payload>");
1016                panic!("corpus file {name}: {msg}\nexpression: {source:?}");
1017            }
1018            replayed += 1;
1019        }
1020        assert!(replayed > 0, "corpus dir exists but replayed nothing");
1021    }
1022
1023    #[test]
1024    fn content_expr_survives_adversarial_inputs() {
1025        // The seed corpus is alive: every seed parses.
1026        for seed_expr in SEED_EXPRS {
1027            assert!(
1028                ContentExpr::parse(seed_expr).is_ok(),
1029                "seed expression must parse: {seed_expr:?}"
1030            );
1031        }
1032        for seed in [0x5eed_e001_u64, 0x5eed_e002, 0x5eed_e003] {
1033            let mut rng = Xorshift(seed);
1034            for case in 0..CASES_PER_SEED {
1035                let source = gen_expr(&mut rng);
1036                if let Err(payload) = catch_unwind(AssertUnwindSafe(|| exercise(&mut rng, &source)))
1037                {
1038                    let msg = payload
1039                        .downcast_ref::<String>()
1040                        .map(|s| s.as_str())
1041                        .or_else(|| payload.downcast_ref::<&str>().copied())
1042                        .unwrap_or("<non-string panic payload>");
1043                    panic!("seed {seed:#x} case {case}: {msg}\nexpression: {source:?}");
1044                }
1045            }
1046        }
1047    }
1048}
memstead_schema/content_expr.rs

memstead_schema/
content_expr.rs
