tiptap_rusty_parser/
content.rs

1//! ProseMirror **content expressions** — cardinality + ordering for schema
2//! validation (e.g. `paragraph+`, `heading{1,3}`, `(text | image)*`, `block+`).
3//!
4//! A [`NodeSpec`](crate::NodeSpec)'s `content` is a [`ContentRule`]: either a
5//! set of allowed child types (the array form, order/count-insensitive) or a
6//! [`ContentExpr`] parsed from a content-expression string. Expressions compile
7//! to an NFA and are matched against a node's child-type sequence; a name in an
8//! expression matches a child whose `type` equals it **or** whose
9//! [`NodeSpec::group`](crate::NodeSpec) contains it. A child whose type is
10//! missing or not in the schema matches any name: it is already reported as
11//! its own violation, so it never also invalidates its parent's content.
12//!
13//! Supported grammar (the full ProseMirror content-expression language):
14//! ```text
15//! Choice  := Seq ('|' Seq)*
16//! Seq     := Postfix*                  // whitespace-separated; empty allowed
17//! Postfix := Atom ('*' | '+' | '?' | '{' n (',' m?)? '}')?
18//! Atom    := '(' Choice ')' | Name     // Name = [A-Za-z0-9_-]+
19//! ```
20
21use crate::node::Node;
22use crate::schema::Schema;
23use serde::de::{self, Deserializer, Visitor};
24use serde::{Deserialize, Serialize, Serializer};
25use std::collections::HashSet;
26use std::fmt;
27
28/// Largest explicit repeat bound allowed in `{n}`/`{n,m}` (guards NFA blowup).
29const MAX_REPEAT: u32 = 1000;
30/// Hard ceiling on compiled NFA states (guards pathological expressions).
31const MAX_NFA_STATES: usize = 100_000;
32
33/// Error parsing (or compiling) a content expression.
34#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
35#[error("invalid content expression at byte {pos}: {msg}")]
36pub struct ParseExprError {
37    /// Byte offset into the source string where the problem was detected.
38    pub pos: usize,
39    /// Human-readable reason.
40    pub msg: String,
41}
42
43// ---- AST ----------------------------------------------------------------
44
45#[derive(Debug, Clone, PartialEq, Eq)]
46enum Expr {
47    Empty,
48    Name(String),
49    Seq(Vec<Expr>),
50    Choice(Vec<Expr>),
51    Star(Box<Expr>),
52    Plus(Box<Expr>),
53    Opt(Box<Expr>),
54    Range {
55        min: u32,
56        max: Option<u32>,
57        inner: Box<Expr>,
58    },
59}
60
61fn is_name_char(c: char) -> bool {
62    c.is_alphanumeric() || c == '_' || c == '-'
63}
64
65struct Parser<'a> {
66    input: &'a str,
67    pos: usize,
68}
69
70impl<'a> Parser<'a> {
71    fn new(input: &'a str) -> Self {
72        Self { input, pos: 0 }
73    }
74    fn peek(&self) -> Option<char> {
75        self.input[self.pos..].chars().next()
76    }
77    fn bump(&mut self) -> Option<char> {
78        let c = self.peek()?;
79        self.pos += c.len_utf8();
80        Some(c)
81    }
82    fn skip_ws(&mut self) {
83        while let Some(c) = self.peek() {
84            if c.is_whitespace() {
85                self.pos += c.len_utf8();
86            } else {
87                break;
88            }
89        }
90    }
91    fn err(&self, msg: impl Into<String>) -> ParseExprError {
92        ParseExprError {
93            pos: self.pos,
94            msg: msg.into(),
95        }
96    }
97
98    fn parse_choice(&mut self) -> Result<Expr, ParseExprError> {
99        let mut opts = vec![self.parse_seq()?];
100        loop {
101            self.skip_ws();
102            if self.peek() == Some('|') {
103                self.bump();
104                opts.push(self.parse_seq()?);
105            } else {
106                break;
107            }
108        }
109        Ok(if opts.len() == 1 {
110            opts.pop().unwrap()
111        } else {
112            Expr::Choice(opts)
113        })
114    }
115
116    fn parse_seq(&mut self) -> Result<Expr, ParseExprError> {
117        let mut items = Vec::new();
118        loop {
119            self.skip_ws();
120            match self.peek() {
121                Some(c) if c == '(' || is_name_char(c) => items.push(self.parse_postfix()?),
122                _ => break,
123            }
124        }
125        Ok(match items.len() {
126            0 => Expr::Empty,
127            1 => items.pop().unwrap(),
128            _ => Expr::Seq(items),
129        })
130    }
131
132    fn parse_postfix(&mut self) -> Result<Expr, ParseExprError> {
133        let atom = self.parse_atom()?;
134        self.skip_ws();
135        match self.peek() {
136            Some('*') => {
137                self.bump();
138                Ok(Expr::Star(Box::new(atom)))
139            }
140            Some('+') => {
141                self.bump();
142                Ok(Expr::Plus(Box::new(atom)))
143            }
144            Some('?') => {
145                self.bump();
146                Ok(Expr::Opt(Box::new(atom)))
147            }
148            Some('{') => {
149                self.bump();
150                let (min, max) = self.parse_range()?;
151                Ok(Expr::Range {
152                    min,
153                    max,
154                    inner: Box::new(atom),
155                })
156            }
157            _ => Ok(atom),
158        }
159    }
160
161    fn parse_atom(&mut self) -> Result<Expr, ParseExprError> {
162        self.skip_ws();
163        match self.peek() {
164            Some('(') => {
165                self.bump();
166                let e = self.parse_choice()?;
167                self.skip_ws();
168                if self.peek() != Some(')') {
169                    return Err(self.err("expected ')'"));
170                }
171                self.bump();
172                Ok(e)
173            }
174            Some(c) if is_name_char(c) => {
175                let start = self.pos;
176                while self.peek().is_some_and(is_name_char) {
177                    self.bump();
178                }
179                Ok(Expr::Name(self.input[start..self.pos].to_string()))
180            }
181            _ => Err(self.err("expected a name or '('")),
182        }
183    }
184
185    /// Parse a `{n}` / `{n,}` / `{n,m}` body (the opening `{` already consumed).
186    fn parse_range(&mut self) -> Result<(u32, Option<u32>), ParseExprError> {
187        self.skip_ws();
188        let min = self.parse_num()?;
189        self.skip_ws();
190        let max = match self.peek() {
191            Some(',') => {
192                self.bump();
193                self.skip_ws();
194                match self.peek() {
195                    Some('}') => None,
196                    Some(c) if c.is_ascii_digit() => Some(self.parse_num()?),
197                    _ => return Err(self.err("expected a number or '}' in range")),
198                }
199            }
200            Some('}') => Some(min),
201            _ => return Err(self.err("expected ',' or '}' in range")),
202        };
203        self.skip_ws();
204        if self.peek() != Some('}') {
205            return Err(self.err("expected '}'"));
206        }
207        self.bump();
208        if min > MAX_REPEAT || max.is_some_and(|m| m > MAX_REPEAT) {
209            return Err(self.err(format!("repeat count exceeds cap of {MAX_REPEAT}")));
210        }
211        if max.is_some_and(|m| m < min) {
212            return Err(self.err("range maximum is less than minimum"));
213        }
214        Ok((min, max))
215    }
216
217    fn parse_num(&mut self) -> Result<u32, ParseExprError> {
218        let start = self.pos;
219        while self.peek().is_some_and(|c| c.is_ascii_digit()) {
220            self.bump();
221        }
222        if self.pos == start {
223            return Err(self.err("expected a number"));
224        }
225        self.input[start..self.pos]
226            .parse()
227            .map_err(|_| self.err("number too large"))
228    }
229}
230
231fn parse(input: &str) -> Result<Expr, ParseExprError> {
232    let mut p = Parser::new(input);
233    let e = p.parse_choice()?;
234    p.skip_ws();
235    if p.pos != input.len() {
236        return Err(p.err("unexpected trailing input"));
237    }
238    Ok(e)
239}
240
241// ---- NFA ----------------------------------------------------------------
242
243#[derive(Debug, Clone)]
244struct State {
245    eps: Vec<usize>,
246    edges: Vec<(String, usize)>,
247}
248
249#[derive(Debug, Clone)]
250struct Nfa {
251    states: Vec<State>,
252    start: usize,
253    accept: usize,
254}
255
256struct Builder {
257    states: Vec<State>,
258}
259
260impl Builder {
261    fn new_state(&mut self) -> Result<usize, ParseExprError> {
262        if self.states.len() >= MAX_NFA_STATES {
263            return Err(ParseExprError {
264                pos: 0,
265                msg: format!("content expression too large (> {MAX_NFA_STATES} states)"),
266            });
267        }
268        self.states.push(State {
269            eps: Vec::new(),
270            edges: Vec::new(),
271        });
272        Ok(self.states.len() - 1)
273    }
274    fn eps(&mut self, from: usize, to: usize) {
275        self.states[from].eps.push(to);
276    }
277
278    /// Build a Thompson fragment for `e`, returning its `(start, out)` states.
279    fn build(&mut self, e: &Expr) -> Result<(usize, usize), ParseExprError> {
280        match e {
281            Expr::Empty => {
282                let (s, o) = (self.new_state()?, self.new_state()?);
283                self.eps(s, o);
284                Ok((s, o))
285            }
286            Expr::Name(n) => {
287                let (s, o) = (self.new_state()?, self.new_state()?);
288                self.states[s].edges.push((n.clone(), o));
289                Ok((s, o))
290            }
291            Expr::Seq(items) => {
292                let s = self.new_state()?;
293                let mut cur = s;
294                for it in items {
295                    let (fs, fo) = self.build(it)?;
296                    self.eps(cur, fs);
297                    cur = fo;
298                }
299                Ok((s, cur))
300            }
301            Expr::Choice(opts) => {
302                let (s, o) = (self.new_state()?, self.new_state()?);
303                for opt in opts {
304                    let (fs, fo) = self.build(opt)?;
305                    self.eps(s, fs);
306                    self.eps(fo, o);
307                }
308                Ok((s, o))
309            }
310            Expr::Star(inner) => {
311                let (s, o) = (self.new_state()?, self.new_state()?);
312                let (fs, fo) = self.build(inner)?;
313                self.eps(s, fs);
314                self.eps(s, o);
315                self.eps(fo, fs);
316                self.eps(fo, o);
317                Ok((s, o))
318            }
319            Expr::Plus(inner) => {
320                let (s, o) = (self.new_state()?, self.new_state()?);
321                let (fs, fo) = self.build(inner)?;
322                self.eps(s, fs);
323                self.eps(fo, fs);
324                self.eps(fo, o);
325                Ok((s, o))
326            }
327            Expr::Opt(inner) => {
328                let (s, o) = (self.new_state()?, self.new_state()?);
329                let (fs, fo) = self.build(inner)?;
330                self.eps(s, fs);
331                self.eps(s, o);
332                self.eps(fo, o);
333                Ok((s, o))
334            }
335            Expr::Range { min, max, inner } => {
336                let s = self.new_state()?;
337                let mut cur = s;
338                for _ in 0..*min {
339                    let (fs, fo) = self.build(inner)?;
340                    self.eps(cur, fs);
341                    cur = fo;
342                }
343                match max {
344                    None => {
345                        // open `{n,}` => append `inner*` (loop-back, no expansion)
346                        let (fs, fo) = self.build(inner)?;
347                        let (ss, so) = (self.new_state()?, self.new_state()?);
348                        self.eps(ss, fs);
349                        self.eps(ss, so);
350                        self.eps(fo, fs);
351                        self.eps(fo, so);
352                        self.eps(cur, ss);
353                        cur = so;
354                    }
355                    Some(m) => {
356                        // `(m - min)` optional copies
357                        for _ in *min..*m {
358                            let (fs, fo) = self.build(inner)?;
359                            let (os, oo) = (self.new_state()?, self.new_state()?);
360                            self.eps(os, fs);
361                            self.eps(os, oo);
362                            self.eps(fo, oo);
363                            self.eps(cur, os);
364                            cur = oo;
365                        }
366                    }
367                }
368                Ok((s, cur))
369            }
370        }
371    }
372}
373
374fn compile(ast: &Expr) -> Result<Nfa, ParseExprError> {
375    let mut b = Builder { states: Vec::new() };
376    let (start, accept) = b.build(ast)?;
377    Ok(Nfa {
378        states: b.states,
379        start,
380        accept,
381    })
382}
383
384/// A label matches a child if it equals the child's type or one of its groups.
385fn label_matches(label: &str, child_type: &str, schema: &Schema) -> bool {
386    label == child_type
387        || schema
388            .nodes
389            .get(child_type)
390            .and_then(|spec| spec.group.as_deref())
391            .is_some_and(|g| g.split_whitespace().any(|grp| grp == label))
392}
393
394impl Nfa {
395    fn eps_closure(&self, set: &mut [bool], stack: &mut Vec<usize>) {
396        while let Some(s) = stack.pop() {
397            for &t in &self.states[s].eps {
398                if !set[t] {
399                    set[t] = true;
400                    stack.push(t);
401                }
402            }
403        }
404    }
405
406    /// `Ok` if `children` match; `Err(Some(i))` if child `i` is the first one
407    /// no live state can consume; `Err(None)` if every child was consumed but
408    /// the expression wants more.
409    fn check(&self, children: &[Node], schema: &Schema) -> Result<(), Option<usize>> {
410        let n = self.states.len();
411        let mut current = vec![false; n];
412        let mut next = vec![false; n];
413        let mut stack = vec![self.start];
414        current[self.start] = true;
415        self.eps_closure(&mut current, &mut stack);
416
417        for (i, child) in children.iter().enumerate() {
418            // Untyped / unknown children are wildcards: they are reported as
419            // their own violation, not as their parent's.
420            let ct = child
421                .node_type
422                .as_deref()
423                .filter(|t| schema.nodes.contains_key(*t));
424            next.fill(false);
425            for (s, &active) in current.iter().enumerate() {
426                if active {
427                    for (label, dst) in &self.states[s].edges {
428                        if !next[*dst] && ct.is_none_or(|ct| label_matches(label, ct, schema)) {
429                            next[*dst] = true;
430                            stack.push(*dst);
431                        }
432                    }
433                }
434            }
435            self.eps_closure(&mut next, &mut stack);
436            if !next.iter().any(|&b| b) {
437                return Err(Some(i)); // dead — no state survives this child
438            }
439            std::mem::swap(&mut current, &mut next);
440        }
441        if current[self.accept] {
442            Ok(())
443        } else {
444            Err(None)
445        }
446    }
447}
448
449// ---- public types -------------------------------------------------------
450
451/// A compiled ProseMirror content expression (e.g. `paragraph+`).
452///
453/// Parse with [`ContentExpr::parse`]; (de)serializes as its source string.
454#[derive(Debug, Clone)]
455pub struct ContentExpr {
456    raw: String,
457    ast: Expr,
458    nfa: Nfa,
459}
460
461impl ContentExpr {
462    /// Parse and compile a content-expression string.
463    ///
464    /// ```
465    /// use tiptap_rusty_parser::ContentExpr;
466    /// assert!(ContentExpr::parse("paragraph+").is_ok());
467    /// assert!(ContentExpr::parse("(a |").is_err());
468    /// ```
469    pub fn parse(s: &str) -> Result<Self, ParseExprError> {
470        let ast = parse(s)?;
471        let nfa = compile(&ast)?;
472        Ok(Self {
473            raw: s.to_string(),
474            ast,
475            nfa,
476        })
477    }
478
479    /// The original expression source.
480    pub fn as_str(&self) -> &str {
481        &self.raw
482    }
483
484    /// Whether `children`'s type sequence satisfies this expression.
485    /// `Err(Some(i))`: child `i` is the first that cannot be matched;
486    /// `Err(None)`: every child matched but more are required.
487    pub(crate) fn check(&self, children: &[Node], schema: &Schema) -> Result<(), Option<usize>> {
488        self.nfa.check(children, schema)
489    }
490}
491
492impl PartialEq for ContentExpr {
493    fn eq(&self, other: &Self) -> bool {
494        self.ast == other.ast // compare structure, not the compiled NFA
495    }
496}
497
498impl Serialize for ContentExpr {
499    fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
500        s.serialize_str(&self.raw)
501    }
502}
503
504impl<'de> Deserialize<'de> for ContentExpr {
505    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
506        let s = String::deserialize(d)?;
507        ContentExpr::parse(&s).map_err(de::Error::custom)
508    }
509}
510
511/// A node's allowed content: a set of child types (array form) or an ordered
512/// content [expression](ContentExpr) (string form).
513#[derive(Debug, Clone, PartialEq)]
514pub enum ContentRule {
515    /// Allowed child types, any count/order. Emits `DisallowedChild`.
516    Types(HashSet<String>),
517    /// A content expression (cardinality + ordering). Emits `InvalidContent`.
518    Expr(ContentExpr),
519}
520
521impl Serialize for ContentRule {
522    fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
523        match self {
524            ContentRule::Types(set) => set.serialize(s), // JSON array
525            ContentRule::Expr(e) => e.serialize(s),      // JSON string
526        }
527    }
528}
529
530impl<'de> Deserialize<'de> for ContentRule {
531    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
532        struct RuleVisitor;
533        impl<'de> Visitor<'de> for RuleVisitor {
534            type Value = ContentRule;
535            fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
536                f.write_str("an array of child type names or a content-expression string")
537            }
538            fn visit_str<E: de::Error>(self, v: &str) -> Result<ContentRule, E> {
539                ContentExpr::parse(v)
540                    .map(ContentRule::Expr)
541                    .map_err(E::custom)
542            }
543            fn visit_string<E: de::Error>(self, v: String) -> Result<ContentRule, E> {
544                self.visit_str(&v)
545            }
546            fn visit_seq<A: de::SeqAccess<'de>>(self, mut seq: A) -> Result<ContentRule, A::Error> {
547                let mut set = HashSet::new();
548                while let Some(s) = seq.next_element::<String>()? {
549                    set.insert(s);
550                }
551                Ok(ContentRule::Types(set))
552            }
553        }
554        d.deserialize_any(RuleVisitor)
555    }
556}
557
558#[cfg(test)]
559mod tests {
560    use super::*;
561
562    fn name(s: &str) -> Expr {
563        Expr::Name(s.to_string())
564    }
565
566    #[test]
567    fn precedence_and_shape() {
568        // `|` binds loosest; sequence by whitespace; postfix binds to its atom.
569        assert_eq!(
570            parse("a b | c").unwrap(),
571            Expr::Choice(vec![Expr::Seq(vec![name("a"), name("b")]), name("c")])
572        );
573        assert_eq!(
574            parse("a b+").unwrap(),
575            Expr::Seq(vec![name("a"), Expr::Plus(Box::new(name("b")))])
576        );
577        assert_eq!(
578            parse("(a b)+").unwrap(),
579            Expr::Plus(Box::new(Expr::Seq(vec![name("a"), name("b")])))
580        );
581        assert_eq!(parse("").unwrap(), Expr::Empty);
582        assert_eq!(
583            parse("h{2,3}").unwrap(),
584            Expr::Range {
585                min: 2,
586                max: Some(3),
587                inner: Box::new(name("h")),
588            }
589        );
590        assert_eq!(
591            parse("h{2,}").unwrap(),
592            Expr::Range {
593                min: 2,
594                max: None,
595                inner: Box::new(name("h")),
596            }
597        );
598    }
599
600    #[test]
601    fn range_cap_and_errors() {
602        assert!(parse("a{2000}").is_err());
603        assert!(parse("a{3,1}").is_err());
604        assert!(parse("a**").is_err());
605        // serialized form round-trips through ContentExpr
606        let e = ContentExpr::parse("(a | b) c*").unwrap();
607        assert_eq!(e.as_str(), "(a | b) c*");
608    }
609}
tiptap_rusty_parser/content.rs

tiptap_rusty_parser/
content.rs
