rusty_xml_valid/
rng.rs

1//! RelaxNG (simplified) matching libxml2 `relaxng.h` for the tutorial corpus.
2
3use rusty_xml_parser::{default_parse_options, xml_read_memory};
4use rusty_xml_tree::{NodeId, NodeKind, XmlDoc};
5use std::collections::HashMap;
6
7const RNG_NS: &str = "http://relaxng.org/ns/structure/1.0";
8
9#[derive(Clone, Debug)]
10enum Pat {
11    Empty,
12    Text,
13    NotAllowed,
14    Element { name: String, inner: Box<Pat> },
15    Attribute { name: String, inner: Box<Pat> },
16    Group(Vec<Pat>),
17    Choice(Vec<Pat>),
18    Interleave(Vec<Pat>),
19    Optional(Box<Pat>),
20    ZeroOrMore(Box<Pat>),
21    OneOrMore(Box<Pat>),
22    Value(String),
23    Data(String),
24    Ref(String),
25    List(Box<Pat>),
26}
27
28struct Schema {
29    start: Pat,
30    defs: HashMap<String, Pat>,
31}
32
33/// `xmlRelaxNGParse` + `xmlRelaxNGValidateDoc`.
34#[doc(alias = "xmlRelaxNGValidateDoc")]
35pub fn xml_relaxng_validate_doc(rng_xml: &[u8], doc: &XmlDoc) -> Result<(), String> {
36    let rng_doc = xml_read_memory(rng_xml, None, None, default_parse_options())
37        .map_err(|e| e.to_string())?;
38    let schema = compile(&rng_doc)?;
39    let root = doc.xml_doc_get_root_element().ok_or("no root")?;
40    match_element(&schema, &schema.start, doc, root)?;
41    Ok(())
42}
43
44fn compile(doc: &XmlDoc) -> Result<Schema, String> {
45    let root = doc.xml_doc_get_root_element().ok_or("empty rng")?;
46    let mut defs = HashMap::new();
47    harvest_defs(doc, root, &mut defs);
48    let start = if is_rng(doc, root, "grammar") {
49        match find_child_named(doc, root, "start") {
50            // `<start/>` with no pattern inside used to `.unwrap()` an Err and
51            // panic. It is a malformed schema, which is an error to report, not
52            // a reason to kill the caller's thread.
53            Some(s) => compile_pat(doc, first_pat_child(doc, s).ok_or("empty start")?),
54            None => compile_pat(doc, root),
55        }
56    } else {
57        compile_pat(doc, root)
58    };
59    let schema = Schema { start, defs };
60    check_no_ref_cycle(&schema)?;
61    Ok(schema)
62}
63
64/// Reject a schema whose definitions reference each other in a cycle without
65/// consuming an element.
66///
67/// `<define name="a"><ref name="a"/></define>` made the matcher recurse until
68/// the stack ran out, which ABORTS THE PROCESS -- a stack overflow cannot be
69/// caught. Mutual cycles (a -> b -> a) and cycles through choice/group did the
70/// same. Such a grammar can never match anything, so refusing it at compile
71/// time loses nothing and is decidable here, unlike a depth limit in the
72/// matcher which would only move the cliff.
73fn check_no_ref_cycle(schema: &Schema) -> Result<(), String> {
74    fn walk(
75        schema: &Schema,
76        pat: &Pat,
77        stack: &mut Vec<String>,
78    ) -> Result<(), String> {
79        match pat {
80            // An Element consumes input, so a reference under it cannot loop
81            // forever; that is where recursive grammars are legitimate.
82            Pat::Element { .. } => Ok(()),
83            Pat::Ref(n) => {
84                if stack.iter().any(|s| s == n) {
85                    return Err(format!("cyclic ref {n} in schema"));
86                }
87                let Some(next) = schema.defs.get(n) else {
88                    return Ok(()); // undefined refs are reported while matching
89                };
90                stack.push(n.clone());
91                let r = walk(schema, next, stack);
92                stack.pop();
93                r
94            }
95            Pat::Attribute { inner, .. }
96            | Pat::Optional(inner)
97            | Pat::ZeroOrMore(inner)
98            | Pat::OneOrMore(inner)
99            | Pat::List(inner) => walk(schema, inner, stack),
100            Pat::Group(v) | Pat::Choice(v) | Pat::Interleave(v) => {
101                for p in v {
102                    walk(schema, p, stack)?;
103                }
104                Ok(())
105            }
106            _ => Ok(()),
107        }
108    }
109    let mut stack = Vec::new();
110    walk(schema, &schema.start, &mut stack)?;
111    for (name, pat) in &schema.defs {
112        stack.clear();
113        stack.push(name.clone());
114        walk(schema, pat, &mut stack)?;
115    }
116    Ok(())
117}
118
119fn harvest_defs(doc: &XmlDoc, id: NodeId, defs: &mut HashMap<String, Pat>) {
120    if is_rng(doc, id, "define") {
121        if let Some(name) = doc.xml_get_prop(id, "name") {
122            if let Some(ch) = first_pat_child(doc, id) {
123                defs.insert(name, compile_pat(doc, ch));
124            }
125        }
126    }
127    let mut c = doc.first_child(id);
128    while let Some(x) = c {
129        harvest_defs(doc, x, defs);
130        c = doc.next_sibling(x);
131    }
132}
133
134fn is_rng(doc: &XmlDoc, id: NodeId, name: &str) -> bool {
135    doc.kind(id) == NodeKind::Element
136        && doc.name(id) == name
137        && (doc.ns_uri(id) == Some(RNG_NS) || doc.ns_uri(id).is_none())
138}
139
140fn first_pat_child(doc: &XmlDoc, id: NodeId) -> Option<NodeId> {
141    let mut c = doc.first_child(id);
142    while let Some(x) = c {
143        if doc.kind(x) == NodeKind::Element {
144            return Some(x);
145        }
146        c = doc.next_sibling(x);
147    }
148    None
149}
150
151fn find_child_named(doc: &XmlDoc, id: NodeId, name: &str) -> Option<NodeId> {
152    let mut c = doc.first_child(id);
153    while let Some(x) = c {
154        if is_rng(doc, x, name) {
155            return Some(x);
156        }
157        c = doc.next_sibling(x);
158    }
159    None
160}
161
162fn compile_pat(doc: &XmlDoc, id: NodeId) -> Pat {
163    let name = doc.name(id);
164    match name {
165        "element" => {
166            let n = doc.xml_get_prop(id, "name").unwrap_or_default();
167            Pat::Element {
168                name: n,
169                inner: Box::new(compile_group_children(doc, id)),
170            }
171        }
172        "attribute" => {
173            let n = doc.xml_get_prop(id, "name").unwrap_or_default();
174            Pat::Attribute {
175                name: n,
176                inner: Box::new(compile_group_children(doc, id)),
177            }
178        }
179        "empty" => Pat::Empty,
180        "text" => Pat::Text,
181        "notAllowed" => Pat::NotAllowed,
182        "optional" => Pat::Optional(Box::new(compile_group_children(doc, id))),
183        "zeroOrMore" => Pat::ZeroOrMore(Box::new(compile_group_children(doc, id))),
184        "oneOrMore" => Pat::OneOrMore(Box::new(compile_group_children(doc, id))),
185        "choice" => Pat::Choice(compile_child_pats(doc, id)),
186        "group" => Pat::Group(compile_child_pats(doc, id)),
187        "interleave" => Pat::Interleave(compile_child_pats(doc, id)),
188        "value" => Pat::Value(doc.xml_node_get_content(id).trim().to_string()),
189        "data" => Pat::Data(doc.xml_get_prop(id, "type").unwrap_or_else(|| "string".into())),
190        "ref" => Pat::Ref(doc.xml_get_prop(id, "name").unwrap_or_default()),
191        "list" => Pat::List(Box::new(compile_group_children(doc, id))),
192        "mixed" => Pat::Interleave(vec![Pat::Text, compile_group_children(doc, id)]),
193        "grammar" => find_child_named(doc, id, "start")
194            .and_then(|s| first_pat_child(doc, s))
195            .map(|c| compile_pat(doc, c))
196            .unwrap_or(Pat::NotAllowed),
197        _ => compile_group_children(doc, id),
198    }
199}
200
201fn compile_child_pats(doc: &XmlDoc, id: NodeId) -> Vec<Pat> {
202    let mut v = Vec::new();
203    let mut c = doc.first_child(id);
204    while let Some(x) = c {
205        if doc.kind(x) == NodeKind::Element {
206            v.push(compile_pat(doc, x));
207        }
208        c = doc.next_sibling(x);
209    }
210    v
211}
212
213fn compile_group_children(doc: &XmlDoc, id: NodeId) -> Pat {
214    let v = compile_child_pats(doc, id);
215    match v.len() {
216        0 => Pat::Empty,
217        1 => v.into_iter().next().unwrap(),
218        _ => Pat::Group(v),
219    }
220}
221
222fn match_element(schema: &Schema, pat: &Pat, doc: &XmlDoc, id: NodeId) -> Result<(), String> {
223    let pat = deref_pat(schema, pat)?;
224    match pat {
225        Pat::Element { name, inner } => {
226            if doc.name(id) != name {
227                return Err(format!("expected element {name}, got {}", doc.name(id)));
228            }
229            match_content(schema, &inner, doc, id)
230        }
231        Pat::Choice(alts) => {
232            for a in &alts {
233                if match_element(schema, a, doc, id).is_ok() {
234                    return Ok(());
235                }
236            }
237            Err("choice failed".into())
238        }
239        Pat::Ref(n) => {
240            let p = schema.defs.get(&n).ok_or_else(|| format!("undefined ref {n}"))?;
241            match_element(schema, p, doc, id)
242        }
243        other => match_content(schema, &other, doc, id),
244    }
245}
246
247fn deref_pat<'a>(schema: &'a Schema, pat: &'a Pat) -> Result<Pat, String> {
248    match pat {
249        Pat::Ref(n) => schema
250            .defs
251            .get(n)
252            .cloned()
253            .ok_or_else(|| format!("undefined ref {n}")),
254        p => Ok(p.clone()),
255    }
256}
257
258fn match_content(schema: &Schema, pat: &Pat, doc: &XmlDoc, id: NodeId) -> Result<(), String> {
259    let mut attrs: Vec<(String, String)> = Vec::new();
260    let mut a = doc.first_attr(id);
261    while let Some(x) = a {
262        if !doc.name(x).starts_with("xmlns") {
263            attrs.push((doc.name(x).to_string(), doc.content(x).to_string()));
264        }
265        a = doc.next_sibling(x);
266    }
267    let mut kids: Vec<NodeId> = Vec::new();
268    let mut c = doc.first_child(id);
269    while let Some(x) = c {
270        match doc.kind(x) {
271            NodeKind::Element => kids.push(x),
272            NodeKind::Text | NodeKind::CData => {
273                if !doc.xml_is_blank_node(x) {
274                    kids.push(x);
275                }
276            }
277            _ => {}
278        }
279        c = doc.next_sibling(x);
280    }
281    consume(schema, pat, doc, &mut kids, &mut attrs)?;
282    if !attrs.is_empty() {
283        return Err(format!("undeclared attributes {:?}", attrs));
284    }
285    if kids.iter().any(|&k| doc.kind(k) == NodeKind::Element) {
286        return Err("extra element content".into());
287    }
288    Ok(())
289}
290
291fn consume(
292    schema: &Schema,
293    pat: &Pat,
294    doc: &XmlDoc,
295    kids: &mut Vec<NodeId>,
296    attrs: &mut Vec<(String, String)>,
297) -> Result<(), String> {
298    let pat = deref_pat(schema, pat)?;
299    match pat {
300        Pat::Empty => Ok(()),
301        Pat::Text => {
302            kids.retain(|&k| doc.kind(k) == NodeKind::Element);
303            Ok(())
304        }
305        Pat::NotAllowed => Err("notAllowed".into()),
306        Pat::Attribute { name, inner } => {
307            if let Some(i) = attrs.iter().position(|(n, _)| n == &name) {
308                let val = attrs.remove(i).1;
309                match *inner {
310                    Pat::Text | Pat::Empty | Pat::Data(_) => Ok(()),
311                    Pat::Value(v) if v == val => Ok(()),
312                    Pat::Value(v) => Err(format!("attr {name} expected {v}")),
313                    _ => Ok(()),
314                }
315            } else {
316                Err(format!("missing attribute {name}"))
317            }
318        }
319        Pat::Element { name, inner } => {
320            if let Some(i) = kids.iter().position(|&k| {
321                doc.kind(k) == NodeKind::Element && doc.name(k) == name
322            }) {
323                let n = kids.remove(i);
324                match_content(schema, &inner, doc, n)
325            } else {
326                Err(format!("missing element {name}"))
327            }
328        }
329        Pat::Group(ps) => {
330            for p in &ps {
331                consume(schema, p, doc, kids, attrs)?;
332            }
333            Ok(())
334        }
335        Pat::Choice(ps) => {
336            for p in &ps {
337                let mut k2 = kids.clone();
338                let mut a2 = attrs.clone();
339                if consume(schema, p, doc, &mut k2, &mut a2).is_ok() {
340                    *kids = k2;
341                    *attrs = a2;
342                    return Ok(());
343                }
344            }
345            Err("choice failed".into())
346        }
347        Pat::Interleave(ps) => {
348            for p in &ps {
349                consume(schema, p, doc, kids, attrs)?;
350            }
351            Ok(())
352        }
353        Pat::Optional(p) => {
354            let mut k2 = kids.clone();
355            let mut a2 = attrs.clone();
356            if consume(schema, &p, doc, &mut k2, &mut a2).is_ok() {
357                *kids = k2;
358                *attrs = a2;
359            }
360            Ok(())
361        }
362        Pat::ZeroOrMore(p) => {
363            loop {
364                let mut k2 = kids.clone();
365                let mut a2 = attrs.clone();
366                if consume(schema, &p, doc, &mut k2, &mut a2).is_ok()
367                    && (k2.len() < kids.len() || a2.len() < attrs.len())
368                {
369                    *kids = k2;
370                    *attrs = a2;
371                } else {
372                    break;
373                }
374            }
375            Ok(())
376        }
377        Pat::OneOrMore(p) => {
378            consume(schema, &p, doc, kids, attrs)?;
379            consume(schema, &Pat::ZeroOrMore(p), doc, kids, attrs)
380        }
381        Pat::Value(v) => {
382            let text: String = kids
383                .iter()
384                .filter(|k| doc.kind(**k) != NodeKind::Element)
385                .map(|k| doc.content(*k))
386                .collect();
387            kids.retain(|&k| doc.kind(k) == NodeKind::Element);
388            if text.trim() == v {
389                Ok(())
390            } else {
391                Err(format!("value {v} != {}", text.trim()))
392            }
393        }
394        Pat::Data(_) | Pat::List(_) => {
395            kids.retain(|&k| doc.kind(k) == NodeKind::Element);
396            Ok(())
397        }
398        Pat::Ref(n) => {
399            let p = schema.defs.get(&n).ok_or_else(|| format!("undefined {n}"))?;
400            consume(schema, p, doc, kids, attrs)
401        }
402    }
403}
rusty_xml_valid/rng.rs

rusty_xml_valid/
rng.rs
