rusty_xml_valid/
lib.rs

1//! DTD validation, C14N, RelaxNG, XML Schema, Schematron.
2
3#![forbid(unsafe_code)]
4
5mod c14n;
6mod rng;
7mod xsd;
8mod schematron;
9
10use rusty_xml_tree::{AttrDefault, ElementDecl, NodeId, NodeKind, XmlDoc, XmlDtd};
11
12pub use c14n::*;
13pub use rng::*;
14pub use xsd::*;
15pub use schematron::*;
16
17/// `xmlValidateDocument` against the document's attached DTD.
18#[doc(alias = "xmlValidateDocument")]
19pub fn xml_validate_document(doc: &XmlDoc) -> Result<(), String> {
20    let dtd = doc.dtd.as_ref().ok_or("no DTD")?;
21    xml_validate_dtd(doc, dtd)
22}
23
24/// `xmlValidateDtd`.
25#[doc(alias = "xmlValidateDtd")]
26pub fn xml_validate_dtd(doc: &XmlDoc, dtd: &XmlDtd) -> Result<(), String> {
27    let root = doc
28        .xml_doc_get_root_element()
29        .ok_or("document has no root")?;
30    if let Some(n) = &dtd.name {
31        if doc.name(root) != n.as_str() {
32            return Err(format!("root element {} does not match DOCTYPE {n}", doc.name(root)));
33        }
34    }
35    // Constraints on the DECLARATIONS themselves, before any instance of them
36    // is looked at. None of these was checked, so a declaration could promise
37    // something no document could satisfy.
38    // "Unique Element Type Declaration": no element type may be declared more
39    // than once. A HashMap cannot say so on its own, so the parser records it.
40    if let Some(dup) = dtd.duplicate_elements.first() {
41        return Err(format!("Redefinition of element {dup}"));
42    }
43    // "No Duplicate Types": a mixed content model may not name the same
44    // element twice.
45    for (elem, decl) in &dtd.elements {
46        if let ElementDecl::Mixed(names) = decl {
47            let mut seen = std::collections::HashSet::new();
48            for n in names {
49                if !seen.insert(n) {
50                    return Err(format!(
51                        "Definition of {elem} has duplicate references of {n}"
52                    ));
53                }
54            }
55        }
56    }
57    for ((elem, aname), ad) in &dtd.attributes {
58        // "No Duplicate Tokens": an enumeration may not repeat a value.
59        let mut seen = std::collections::HashSet::new();
60        for e in &ad.enumerated {
61            if !seen.insert(e) {
62                return Err(format!(
63                    "attribute {aname} of {elem}: enumeration value token {e} duplicated"
64                ));
65            }
66        }
67        // "ID Attribute Default": an ID attribute must be #IMPLIED or
68        // #REQUIRED -- it cannot carry a default value, since two elements
69        // taking the default would share an ID.
70        if ad.att_type == "ID"
71            && matches!(ad.default, AttrDefault::Value | AttrDefault::Fixed)
72        {
73            return Err(format!(
74                "ID attribute {aname} of {elem} is not valid, must be #IMPLIED or #REQUIRED"
75            ));
76        }
77        // "No Notation on Empty Element": an element declared EMPTY cannot
78        // carry a NOTATION attribute, since it can never have content for the
79        // notation to describe.
80        if ad.att_type == "NOTATION" && matches!(dtd.elements.get(elem), Some(ElementDecl::Empty)) {
81            return Err(format!(
82                "NOTATION attribute type declared for EMPTY element {elem}"
83            ));
84        }
85        // "Attribute Default Value Syntactically Correct": the default has to
86        // satisfy the type it is declared with.
87        let Some(def) = ad.default_value.as_deref() else {
88            continue;
89        };
90        let ok = match ad.att_type.as_str() {
91            "ID" | "IDREF" | "ENTITY" => is_name(def),
92            "IDREFS" | "ENTITIES" => {
93                def.split_ascii_whitespace().next().is_some()
94                    && def.split_ascii_whitespace().all(is_name)
95            }
96            "NMTOKEN" => is_nmtoken(def),
97            "NMTOKENS" => {
98                def.split_ascii_whitespace().next().is_some()
99                    && def.split_ascii_whitespace().all(is_nmtoken)
100            }
101            _ => true,
102        };
103        if !ok {
104            return Err(format!("invalid default value for attribute {aname} of {elem}"));
105        }
106        if !ad.enumerated.is_empty() && !ad.enumerated.iter().any(|e| e == def) {
107            return Err(format!("invalid default value for attribute {aname} of {elem}"));
108        }
109    }
110
111    // Walk iteratively: validation used to recurse per element, which is the
112    // same stack cliff the parser, the writer and C14N all had.
113    let mut ids: std::collections::HashMap<String, ()> = Default::default();
114    let mut idrefs: Vec<String> = Vec::new();
115    let mut stack = vec![root];
116    while let Some(id) = stack.pop() {
117        validate_element(doc, id, dtd, &mut ids, &mut idrefs)?;
118        let mut c = doc.last_child(id);
119        while let Some(x) = c {
120            if doc.kind(x) == NodeKind::Element {
121                stack.push(x);
122            }
123            c = doc.prev_sibling(x);
124        }
125    }
126    // IDREF VC: every referenced ID must be declared somewhere in the
127    // document. This was never checked at all.
128    for r in &idrefs {
129        if !ids.contains_key(r) {
130            return Err(format!("IDREF attribute references unknown ID \"{r}\""));
131        }
132    }
133    Ok(())
134}
135
136/// A Name, as the ID / IDREF validity constraints require.
137fn is_name(v: &str) -> bool {
138    let mut cs = v.chars();
139    match cs.next() {
140        Some(c) if rusty_xml_parser::chvalid::xml_is_name_start_char(c as u32, false) => {}
141        _ => return false,
142    }
143    cs.all(|c| rusty_xml_parser::chvalid::xml_is_name_char(c as u32, false))
144}
145
146/// An Nmtoken: like a Name but with no restriction on the first character.
147fn is_nmtoken(v: &str) -> bool {
148    !v.is_empty()
149        && v.chars()
150            .all(|c| rusty_xml_parser::chvalid::xml_is_name_char(c as u32, false))
151}
152
153fn validate_element(
154    doc: &XmlDoc,
155    id: NodeId,
156    dtd: &XmlDtd,
157    ids: &mut std::collections::HashMap<String, ()>,
158    idrefs: &mut Vec<String>,
159) -> Result<(), String> {
160    if doc.kind(id) != NodeKind::Element {
161        return Ok(());
162    }
163    let name = doc.name(id).to_string();
164    // "Element Valid": an element with no declaration is invalid, and nothing
165    // said so. A DTD that declares nothing at all is not a validating DTD, so
166    // only complain when there are declarations to be missing from.
167    if !dtd.elements.is_empty() && !dtd.elements.contains_key(&name) {
168        return Err(format!("No declaration for element {name}"));
169    }
170    if let Some(decl) = dtd.elements.get(&name) {
171        match decl {
172            ElementDecl::Empty => {
173                if doc.first_child(id).is_some() {
174                    return Err(format!("element {name} must be EMPTY"));
175                }
176            }
177            ElementDecl::Any => {}
178            ElementDecl::Mixed(_) => {
179                let mut c = doc.first_child(id);
180                while let Some(x) = c {
181                    match doc.kind(x) {
182                        NodeKind::Element => {
183                            if let ElementDecl::Mixed(allowed) = decl {
184                                if !allowed.is_empty() && !allowed.iter().any(|n| n == doc.name(x)) {
185                                    return Err(format!("element {} not allowed in mixed {name}", doc.name(x)));
186                                }
187                            }
188                        }
189                        NodeKind::Text | NodeKind::CData | NodeKind::Comment | NodeKind::Pi => {}
190                        _ => {}
191                    }
192                    c = doc.next_sibling(x);
193                }
194            }
195            ElementDecl::Children(spec) => {
196                let kids: Vec<String> = {
197                    let mut v = Vec::new();
198                    let mut c = doc.first_child(id);
199                    while let Some(x) = c {
200                        if doc.kind(x) == NodeKind::Element {
201                            v.push(doc.name(x).to_string());
202                        } else if doc.kind(x) == NodeKind::Text && !doc.xml_is_blank_node(x) {
203                            return Err(format!("character data not allowed in {name}"));
204                        } else if doc.kind(x) == NodeKind::CData {
205                            // A CDATA section is character data whatever is in
206                            // it. Whitespace inside one is never the ignorable
207                            // kind, so an empty `<![CDATA[]]>` still breaks an
208                            // element-only content model -- and we were only
209                            // looking at Text nodes.
210                            return Err(format!("character data not allowed in {name}"));
211                        }
212                        c = doc.next_sibling(x);
213                    }
214                    v
215                };
216                if !match_children_spec(spec, &kids) {
217                    return Err(format!("content of {name} does not match {spec}"));
218                }
219            }
220        }
221    }
222    for ((elem, aname), ad) in &dtd.attributes {
223        if elem != &name {
224            continue;
225        }
226        // An ATTLIST declares a QName, so `xml:lang` is looked up as
227        // `xml:lang`. xml_get_prop is xmlGetProp -- it matches unprefixed
228        // attributes only -- so every prefixed declared attribute looked
229        // absent, and a #REQUIRED one was reported missing on a document that
230        // plainly had it.
231        let have = {
232            let mut found = None;
233            let mut a = doc.first_attr(id);
234            while let Some(x) = a {
235                if doc.qname(x) == *aname {
236                    found = Some(doc.content(x).to_string());
237                    break;
238                }
239                a = doc.next_sibling(x);
240            }
241            found
242        };
243        match ad.default {
244            AttrDefault::Required if have.is_none() => {
245                return Err(format!("attribute {aname} of {name} is required"));
246            }
247            AttrDefault::Fixed => {
248                if let (Some(v), Some(fix)) = (&have, &ad.default_value) {
249                    if v != fix {
250                        return Err(format!("attribute {aname} must be {fix}"));
251                    }
252                }
253            }
254            _ => {}
255        }
256        if let Some(v) = &have {
257            if !ad.enumerated.is_empty() && !ad.enumerated.iter().any(|e| e == v) {
258                return Err(format!("attribute {aname} value not in enumeration"));
259            }
260            // The tokenized types carry validity constraints on their VALUES,
261            // and not one of them was enforced -- the ID branch said
262            // "uniqueness checked loosely", which meant not at all.
263            match ad.att_type.as_str() {
264                "ID" | "IDREF" => {
265                    if !is_name(v) {
266                        return Err(format!(
267                            "Syntax of value for attribute {aname} of {name} is not valid"
268                        ));
269                    }
270                    if ad.att_type == "ID" {
271                        if ids.insert(v.clone(), ()).is_some() {
272                            return Err(format!("ID {v} already defined"));
273                        }
274                    } else {
275                        idrefs.push(v.clone());
276                    }
277                }
278                "IDREFS" => {
279                    let mut any = false;
280                    for part in v.split_ascii_whitespace() {
281                        any = true;
282                        if !is_name(part) {
283                            return Err(format!(
284                                "Syntax of value for attribute {aname} of {name} is not valid"
285                            ));
286                        }
287                        idrefs.push(part.to_string());
288                    }
289                    if !any {
290                        return Err(format!(
291                            "Syntax of value for attribute {aname} of {name} is not valid"
292                        ));
293                    }
294                }
295                "NMTOKEN" => {
296                    if !is_nmtoken(v) {
297                        return Err(format!(
298                            "Syntax of value for attribute {aname} of {name} is not valid"
299                        ));
300                    }
301                }
302                "NMTOKENS" => {
303                    if v.split_ascii_whitespace().next().is_none()
304                        || !v.split_ascii_whitespace().all(is_nmtoken)
305                    {
306                        return Err(format!(
307                            "Syntax of value for attribute {aname} of {name} is not valid"
308                        ));
309                    }
310                }
311                "ENTITY" | "ENTITIES" => {
312                    for part in v.split_ascii_whitespace() {
313                        if !is_name(part) {
314                            return Err(format!(
315                                "Syntax of value for attribute {aname} of {name} is not valid"
316                            ));
317                        }
318                        if !dtd.unparsed_entities.contains(part) {
319                            return Err(format!(
320                                "ENTITY attribute {aname} references an unknown entity \"{part}\""
321                            ));
322                        }
323                    }
324                }
325                _ => {}
326            }
327        }
328    }
329    // "Attribute Value Type": every attribute an element carries must be
330    // declared for that element type. Nothing checked, so `xml:space` on an
331    // element whose ATTLIST never mentions it was fine by us.
332    if !dtd.elements.is_empty() {
333        let mut a = doc.first_attr(id);
334        while let Some(x) = a {
335            let q = doc.qname(x);
336            if !dtd.attributes.contains_key(&(name.clone(), q.clone())) {
337                return Err(format!("No declaration for attribute {q} of element {name}"));
338            }
339            a = doc.next_sibling(x);
340        }
341    }
342    // "One ID per Element Type": an element type may carry at most one ID
343    // attribute, however the declarations are spread across ATTLISTs.
344    let id_attrs = dtd
345        .attributes
346        .iter()
347        .filter(|((e, _), ad)| e == &name && ad.att_type == "ID")
348        .count();
349    if id_attrs > 1 {
350        return Err(format!("Element {name} has {id_attrs} ID attributes"));
351    }
352    Ok(())
353}
354
355fn match_children_spec(spec: &str, kids: &[String]) -> bool {
356    let toks = tokenize_content(spec);
357    match_seq(&toks, kids, 0).contains(&kids.len())
358}
359
360#[derive(Clone, Debug)]
361enum Tok {
362    Name(String),
363    Seq(Vec<Tok>),
364    Choice(Vec<Tok>),
365    Star,
366    Plus,
367    Q,
368}
369
370fn tokenize_content(spec: &str) -> Vec<Tok> {
371    // Very small content-model parser: names, ',', '|', '*+?', parentheses.
372    let p = spec.trim();
373    fn parse_choice<'a>(p: &mut &'a str) -> Vec<Tok> {
374        let mut alts = vec![Tok::Seq(parse_seq(p))];
375        loop {
376            skip(p);
377            if p.starts_with('|') {
378                *p = &p[1..];
379                alts.push(Tok::Seq(parse_seq(p)));
380            } else {
381                break;
382            }
383        }
384        alts
385    }
386    fn parse_seq<'a>(p: &mut &'a str) -> Vec<Tok> {
387        let mut v = Vec::new();
388        loop {
389            skip(p);
390            if p.is_empty() || p.starts_with('|') || p.starts_with(')') {
391                break;
392            }
393            if p.starts_with(',') {
394                *p = &p[1..];
395                continue;
396            }
397            // A particle that consumes nothing is the end of what we can
398            // read, not a reason to try again.
399            //
400            // `<!ELEMENT doc (a & b)?>` used SGML's "and" connector: `&` is
401            // not a name character, so take_name returned "" and the position
402            // never moved. This loop pushed an empty Name forever -- 32 bytes
403            // of DTD grew a Vec until the process died asking for 32 GB. Any
404            // document with a DTD could do it to anything that validates.
405            let before = p.len();
406            let particle = parse_particle(p);
407            if p.len() == before {
408                break;
409            }
410            v.push(particle);
411        }
412        v
413    }
414    fn parse_particle<'a>(p: &mut &'a str) -> Tok {
415        skip(p);
416        let mut inner = if p.starts_with('(') {
417            *p = &p[1..];
418            let c = parse_choice(p);
419            skip(p);
420            if p.starts_with(')') {
421                *p = &p[1..];
422            }
423            if c.len() == 1 {
424                Tok::Seq(match c.into_iter().next().unwrap() {
425                    Tok::Seq(s) => s,
426                    other => vec![other],
427                })
428            } else {
429                Tok::Choice(c)
430            }
431        } else {
432            let name = take_name(p);
433            Tok::Name(name)
434        };
435        skip(p);
436        inner = match p.chars().next() {
437            Some('*') => {
438                *p = &p[1..];
439                Tok::Seq(vec![inner, Tok::Star])
440            }
441            Some('+') => {
442                *p = &p[1..];
443                Tok::Seq(vec![inner, Tok::Plus])
444            }
445            Some('?') => {
446                *p = &p[1..];
447                Tok::Seq(vec![inner, Tok::Q])
448            }
449            _ => inner,
450        };
451        inner
452    }
453    fn take_name<'a>(p: &mut &'a str) -> String {
454        let bytes = p.as_bytes();
455        let mut i = 0;
456        while i < bytes.len() {
457            let c = bytes[i] as char;
458            if c.is_ascii_alphanumeric() || "-._:".contains(c) {
459                i += 1;
460            } else {
461                break;
462            }
463        }
464        let s = p[..i].to_string();
465        *p = &p[i..];
466        s
467    }
468    fn skip(p: &mut &str) {
469        *p = p.trim_start();
470    }
471    let mut tmp = p;
472    parse_choice(&mut tmp)
473}
474
475fn match_seq(toks: &[Tok], kids: &[String], i: usize) -> Vec<usize> {
476    if toks.is_empty() {
477        return vec![i];
478    }
479    match &toks[0] {
480        Tok::Star => {
481            let rest = &toks[1..];
482            // Star applies to previous — encoded as Seq(inner, Star). Handle Seq instead.
483            match_seq(rest, kids, i)
484        }
485        Tok::Plus | Tok::Q => match_seq(&toks[1..], kids, i),
486        Tok::Name(n) => {
487            if i < kids.len() && &kids[i] == n {
488                match_seq(&toks[1..], kids, i + 1)
489            } else {
490                vec![]
491            }
492        }
493        Tok::Seq(inner) => {
494            let (body, quant) = split_quant(inner);
495            apply_quant(body, quant, &toks[1..], kids, i)
496        }
497        Tok::Choice(alts) => {
498            let mut out = Vec::new();
499            for a in alts {
500                let one = match_seq(&[a.clone()], kids, i);
501                for pos in one {
502                    out.extend(match_seq(&toks[1..], kids, pos));
503                }
504            }
505            out.sort();
506            out.dedup();
507            out
508        }
509    }
510}
511
512enum Quant {
513    One,
514    Q,
515    Star,
516    Plus,
517}
518
519fn split_quant(inner: &[Tok]) -> (&[Tok], Quant) {
520    if inner.len() >= 2 {
521        match inner.last() {
522            Some(Tok::Star) => return (&inner[..inner.len() - 1], Quant::Star),
523            Some(Tok::Plus) => return (&inner[..inner.len() - 1], Quant::Plus),
524            Some(Tok::Q) => return (&inner[..inner.len() - 1], Quant::Q),
525            _ => {}
526        }
527    }
528    (inner, Quant::One)
529}
530
531fn apply_quant(body: &[Tok], q: Quant, rest: &[Tok], kids: &[String], i: usize) -> Vec<usize> {
532    match q {
533        Quant::One => {
534            let mut out = Vec::new();
535            for p in match_seq(body, kids, i) {
536                out.extend(match_seq(rest, kids, p));
537            }
538            out
539        }
540        Quant::Q => {
541            let mut out = match_seq(rest, kids, i);
542            for p in match_seq(body, kids, i) {
543                out.extend(match_seq(rest, kids, p));
544            }
545            out.sort();
546            out.dedup();
547            out
548        }
549        Quant::Star => {
550            let mut out = match_seq(rest, kids, i);
551            let mut frontier = vec![i];
552            while let Some(p) = frontier.pop() {
553                for n in match_seq(body, kids, p) {
554                    if n > p {
555                        out.extend(match_seq(rest, kids, n));
556                        frontier.push(n);
557                    }
558                }
559            }
560            out.sort();
561            out.dedup();
562            out
563        }
564        Quant::Plus => {
565            let mut out = Vec::new();
566            for p in match_seq(body, kids, i) {
567                out.extend(apply_quant(body, Quant::Star, rest, kids, p));
568            }
569            out.sort();
570            out.dedup();
571            out
572        }
573    }
574}
rusty_xml_valid/lib.rs

rusty_xml_valid/
lib.rs
