Skip to main content

openbim_dt/
parser.rs

1//! Bounded XML parsing with explicit namespace resolution.
2
3use std::{collections::HashMap, error::Error, fmt, sync::Arc};
4
5use quick_xml::{escape::unescape, events::BytesStart, events::Event, Reader, XmlVersion};
6use roxmltree::{Document as StrictDocument, Error as StrictError, ParsingOptions};
7
8use crate::document::{Attribute, Document, Element, Node, NodeList, Span, XmlDeclaration};
9
10const XML_NAMESPACE: &str = "http://www.w3.org/XML/1998/namespace";
11const XMLNS_NAMESPACE: &str = "http://www.w3.org/2000/xmlns/";
12
13type NamespaceScope = HashMap<String, Arc<str>>;
14type NamespaceUndo = Vec<(String, Option<Arc<str>>)>;
15
16/// Resource limits applied before or during XML parsing.
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub struct ParseOptions {
19    pub max_bytes: usize,
20    pub max_depth: usize,
21    pub max_nodes: usize,
22    pub max_attributes_per_element: usize,
23}
24
25impl Default for ParseOptions {
26    fn default() -> Self {
27        Self {
28            max_bytes: 16 * 1024 * 1024,
29            max_depth: 128,
30            max_nodes: 1_000_000,
31            max_attributes_per_element: 1_024,
32        }
33    }
34}
35
36/// Stable category for a parse failure.
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub enum ParseErrorKind {
39    InputTooLarge,
40    DepthLimit,
41    NodeLimit,
42    AttributeLimit,
43    DoctypeForbidden,
44    UnknownEntity,
45    UndeclaredPrefix,
46    MalformedQName,
47    MissingRoot,
48    MultipleRoots,
49    MalformedXml,
50    InvalidEncoding,
51}
52
53/// XML parse failure with a stable category and byte position.
54#[derive(Debug, Clone, PartialEq, Eq)]
55pub struct ParseError {
56    kind: ParseErrorKind,
57    position: u64,
58    message: String,
59}
60
61impl ParseError {
62    fn new(kind: ParseErrorKind, position: u64, message: impl Into<String>) -> Self {
63        Self {
64            kind,
65            position,
66            message: message.into(),
67        }
68    }
69
70    #[must_use]
71    pub const fn kind(&self) -> ParseErrorKind {
72        self.kind
73    }
74
75    #[must_use]
76    pub const fn position(&self) -> u64 {
77        self.position
78    }
79}
80
81impl fmt::Display for ParseError {
82    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
83        write!(
84            formatter,
85            "XML parse error {:?} at byte {}: {}",
86            self.kind, self.position, self.message
87        )
88    }
89}
90
91impl Error for ParseError {}
92
93pub(crate) fn parse_document(xml: &str, options: ParseOptions) -> Result<Document, ParseError> {
94    if xml.len() > options.max_bytes {
95        return Err(ParseError::new(
96            ParseErrorKind::InputTooLarge,
97            0,
98            format!("{} bytes exceeds limit {}", xml.len(), options.max_bytes),
99        ));
100    }
101
102    strict_well_formedness_check(xml, options)?;
103
104    let mut reader = Reader::from_str(xml);
105    reader.config_mut().trim_text(false);
106    reader.config_mut().check_end_names = true;
107    reader.config_mut().expand_empty_elements = false;
108
109    let mut declaration = None;
110    let mut declaration_span = None;
111    let mut prolog = NodeList::new();
112    let mut epilog = NodeList::new();
113    let mut root = None;
114    let mut elements = Vec::<Element>::new();
115    let mut scope = base_scope();
116    let mut scope_undos = Vec::<NamespaceUndo>::new();
117    let mut node_count = 0usize;
118    let mut xml_version = XmlVersion::Implicit1_0;
119
120    loop {
121        let position = reader.buffer_position();
122        let event = reader.read_event().map_err(|error| {
123            ParseError::new(ParseErrorKind::MalformedXml, position, error.to_string())
124        })?;
125        match event {
126            Event::Decl(value) => {
127                if declaration.is_some() || root.is_some() || !elements.is_empty() {
128                    return Err(ParseError::new(
129                        ParseErrorKind::MalformedXml,
130                        position,
131                        "XML declaration is not first",
132                    ));
133                }
134                let parsed = parse_declaration(&reader, &value, position)?;
135                xml_version = match parsed.version.as_str() {
136                    "1.0" => XmlVersion::Explicit1_0,
137                    "1.1" => {
138                        return Err(ParseError::new(
139                            ParseErrorKind::MalformedXml,
140                            position,
141                            "XML 1.1 is not supported; convert the document to XML 1.0 first",
142                        ));
143                    }
144                    other => {
145                        return Err(ParseError::new(
146                            ParseErrorKind::MalformedXml,
147                            position,
148                            format!("unsupported XML version `{other}`"),
149                        ));
150                    }
151                };
152                declaration = Some(parsed);
153                declaration_span = Some(Span::new(position, reader.buffer_position()));
154            }
155            Event::Start(value) => {
156                increment_nodes(&mut node_count, options, position)?;
157                if elements.len() + 1 > options.max_depth {
158                    return Err(ParseError::new(
159                        ParseErrorKind::DepthLimit,
160                        position,
161                        format!("depth exceeds limit {}", options.max_depth),
162                    ));
163                }
164                if elements.is_empty() && root.is_some() {
165                    return Err(ParseError::new(
166                        ParseErrorKind::MultipleRoots,
167                        position,
168                        "document contains more than one root element",
169                    ));
170                }
171                let (element, undo) = parse_element(
172                    &ElementContext {
173                        reader: &reader,
174                        options,
175                        position,
176                        xml_version,
177                        span: Some(Span::new(position, reader.buffer_position())),
178                    },
179                    &value,
180                    false,
181                    &mut scope,
182                )?;
183                elements.push(element);
184                scope_undos.push(undo);
185            }
186            Event::Empty(value) => {
187                increment_nodes(&mut node_count, options, position)?;
188                if elements.len() + 1 > options.max_depth {
189                    return Err(ParseError::new(
190                        ParseErrorKind::DepthLimit,
191                        position,
192                        format!("depth exceeds limit {}", options.max_depth),
193                    ));
194                }
195                if elements.is_empty() && root.is_some() {
196                    return Err(ParseError::new(
197                        ParseErrorKind::MultipleRoots,
198                        position,
199                        "document contains more than one root element",
200                    ));
201                }
202                let (element, undo) = parse_element(
203                    &ElementContext {
204                        reader: &reader,
205                        options,
206                        position,
207                        xml_version,
208                        span: Some(Span::new(position, reader.buffer_position())),
209                    },
210                    &value,
211                    true,
212                    &mut scope,
213                )?;
214                append_element(element, &mut elements, &mut root)?;
215                restore_scope(&mut scope, undo);
216            }
217            Event::End(_) => {
218                let mut element = elements.pop().ok_or_else(|| {
219                    ParseError::new(
220                        ParseErrorKind::MalformedXml,
221                        position,
222                        "closing element has no matching start",
223                    )
224                })?;
225                let undo = scope_undos.pop().ok_or_else(|| {
226                    ParseError::new(
227                        ParseErrorKind::MalformedXml,
228                        position,
229                        "namespace scope underflow",
230                    )
231                })?;
232                restore_scope(&mut scope, undo);
233                element.set_close_span(Some(Span::new(position, reader.buffer_position())));
234                append_element(element, &mut elements, &mut root)?;
235            }
236            Event::Text(value) => {
237                increment_nodes(&mut node_count, options, position)?;
238                let decoded = value.xml_content(xml_version).map_err(|error| {
239                    ParseError::new(ParseErrorKind::InvalidEncoding, position, error.to_string())
240                })?;
241                let text = unescape(&decoded).map_err(|error| {
242                    ParseError::new(ParseErrorKind::UnknownEntity, position, error.to_string())
243                })?;
244                append_node(
245                    Node::Text(text.into_owned()),
246                    Some(Span::new(position, reader.buffer_position())),
247                    &mut elements,
248                    &mut prolog,
249                    &mut epilog,
250                    root.is_some(),
251                );
252            }
253            Event::CData(value) => {
254                increment_nodes(&mut node_count, options, position)?;
255                let text = value.xml_content(xml_version).map_err(|error| {
256                    ParseError::new(ParseErrorKind::InvalidEncoding, position, error.to_string())
257                })?;
258                append_node(
259                    Node::CData(text.into_owned()),
260                    Some(Span::new(position, reader.buffer_position())),
261                    &mut elements,
262                    &mut prolog,
263                    &mut epilog,
264                    root.is_some(),
265                );
266            }
267            Event::Comment(value) => {
268                increment_nodes(&mut node_count, options, position)?;
269                let text = decode(&reader, value.as_ref(), position)?;
270                append_node(
271                    Node::Comment(text),
272                    Some(Span::new(position, reader.buffer_position())),
273                    &mut elements,
274                    &mut prolog,
275                    &mut epilog,
276                    root.is_some(),
277                );
278            }
279            Event::PI(value) => {
280                increment_nodes(&mut node_count, options, position)?;
281                let text = decode(&reader, value.as_ref(), position)?;
282                append_node(
283                    Node::ProcessingInstruction(text),
284                    Some(Span::new(position, reader.buffer_position())),
285                    &mut elements,
286                    &mut prolog,
287                    &mut epilog,
288                    root.is_some(),
289                );
290            }
291            Event::GeneralRef(value) => {
292                increment_nodes(&mut node_count, options, position)?;
293                let reference = decode(&reader, value.as_ref(), position)?;
294                let resolved = resolve_reference(&reference).ok_or_else(|| {
295                    ParseError::new(
296                        ParseErrorKind::UnknownEntity,
297                        position,
298                        format!("entity &{reference}; is not predefined or numeric"),
299                    )
300                })?;
301                append_node(
302                    Node::Text(resolved),
303                    Some(Span::new(position, reader.buffer_position())),
304                    &mut elements,
305                    &mut prolog,
306                    &mut epilog,
307                    root.is_some(),
308                );
309            }
310            Event::DocType(_) => {
311                return Err(ParseError::new(
312                    ParseErrorKind::DoctypeForbidden,
313                    position,
314                    "DOCTYPE declarations are disabled",
315                ));
316            }
317            Event::Eof => break,
318        }
319    }
320
321    if !elements.is_empty() {
322        return Err(ParseError::new(
323            ParseErrorKind::MalformedXml,
324            reader.buffer_position(),
325            "document ended inside an element",
326        ));
327    }
328    let root = root.ok_or_else(|| {
329        ParseError::new(
330            ParseErrorKind::MissingRoot,
331            reader.buffer_position(),
332            "document has no root element",
333        )
334    })?;
335    Ok(Document::parsed(
336        declaration,
337        prolog,
338        root,
339        epilog,
340        Some(Arc::<str>::from(xml)),
341        declaration_span,
342    ))
343}
344
345fn strict_well_formedness_check(xml: &str, options: ParseOptions) -> Result<(), ParseError> {
346    let strict_options = ParsingOptions {
347        allow_dtd: false,
348        nodes_limit: u32::try_from(options.max_nodes).unwrap_or(u32::MAX),
349        entity_resolver: None,
350    };
351    StrictDocument::parse_with_options(xml, strict_options)
352        .map(|_| ())
353        .map_err(|error| {
354            let kind = match error {
355                StrictError::DtdDetected => ParseErrorKind::DoctypeForbidden,
356                StrictError::NodesLimitReached => ParseErrorKind::NodeLimit,
357                StrictError::UnknownNamespace(_, _) => ParseErrorKind::UndeclaredPrefix,
358                StrictError::UnknownEntityReference(_, _)
359                | StrictError::MalformedEntityReference(_) => ParseErrorKind::UnknownEntity,
360                StrictError::InvalidName(_) => ParseErrorKind::MalformedQName,
361                _ => ParseErrorKind::MalformedXml,
362            };
363            ParseError::new(kind, 0, error.to_string())
364        })
365}
366
367fn base_scope() -> NamespaceScope {
368    HashMap::from([("xml".to_owned(), Arc::<str>::from(XML_NAMESPACE))])
369}
370
371fn restore_scope(scope: &mut NamespaceScope, undo: NamespaceUndo) {
372    for (prefix, previous) in undo.into_iter().rev() {
373        if let Some(uri) = previous {
374            scope.insert(prefix, uri);
375        } else {
376            scope.remove(&prefix);
377        }
378    }
379}
380
381fn parse_declaration(
382    reader: &Reader<&[u8]>,
383    value: &quick_xml::events::BytesDecl<'_>,
384    position: u64,
385) -> Result<XmlDeclaration, ParseError> {
386    let version = value.version().map_err(|error| {
387        ParseError::new(ParseErrorKind::MalformedXml, position, error.to_string())
388    })?;
389    let encoding = value.encoding().transpose().map_err(|error| {
390        ParseError::new(ParseErrorKind::MalformedXml, position, error.to_string())
391    })?;
392    let standalone = value.standalone().transpose().map_err(|error| {
393        ParseError::new(ParseErrorKind::MalformedXml, position, error.to_string())
394    })?;
395    let version = decode(reader, version.as_ref(), position)?;
396    let encoding = encoding
397        .map(|raw| decode(reader, raw.as_ref(), position))
398        .transpose()?;
399    let standalone = standalone
400        .map(|raw| decode(reader, raw.as_ref(), position))
401        .transpose()?;
402
403    if let Some(value) = &encoding {
404        if !value.eq_ignore_ascii_case("UTF-8") && !value.eq_ignore_ascii_case("UTF8") {
405            return Err(ParseError::new(
406                ParseErrorKind::InvalidEncoding,
407                position,
408                format!("input is a UTF-8 Rust string but declares encoding `{value}`"),
409            ));
410        }
411    }
412    if let Some(value) = &standalone {
413        if value != "yes" && value != "no" {
414            return Err(ParseError::new(
415                ParseErrorKind::MalformedXml,
416                position,
417                format!("standalone must be `yes` or `no`, not `{value}`"),
418            ));
419        }
420    }
421
422    Ok(XmlDeclaration {
423        version,
424        encoding,
425        standalone,
426    })
427}
428
429/// The invariant inputs threaded through element parsing.
430///
431/// Grouped into one struct so adding a new piece of parse context does not
432/// keep widening `parse_element`'s signature.
433struct ElementContext<'a> {
434    reader: &'a Reader<&'a [u8]>,
435    options: ParseOptions,
436    position: u64,
437    xml_version: XmlVersion,
438    span: Option<Span>,
439}
440
441fn parse_element(
442    context: &ElementContext<'_>,
443    start: &BytesStart<'_>,
444    empty_style: bool,
445    scope: &mut NamespaceScope,
446) -> Result<(Element, NamespaceUndo), ParseError> {
447    let ElementContext {
448        reader,
449        options,
450        position,
451        xml_version,
452        span,
453    } = *context;
454    let qname = decode(reader, start.name().as_ref(), position)?;
455    let (prefix, local_name) = split_qname(&qname, position)?;
456    let raw_attributes: Vec<(String, Option<String>, String, String)> = start
457        .attributes()
458        .with_checks(true)
459        .map(|attribute| {
460            let attribute = attribute.map_err(|error| {
461                ParseError::new(ParseErrorKind::MalformedXml, position, error.to_string())
462            })?;
463            let qname = decode(reader, attribute.key.as_ref(), position)?;
464            let (prefix, local_name) = split_qname(&qname, position)?;
465            let value = attribute
466                .decoded_and_normalized_value(xml_version, reader.decoder())
467                .map_err(|error| {
468                    ParseError::new(ParseErrorKind::MalformedXml, position, error.to_string())
469                })?
470                .into_owned();
471            Ok((qname, prefix, local_name, value))
472        })
473        .collect::<Result<_, ParseError>>()?;
474
475    if raw_attributes.len() > options.max_attributes_per_element {
476        return Err(ParseError::new(
477            ParseErrorKind::AttributeLimit,
478            position,
479            format!(
480                "{} attributes exceeds limit {}",
481                raw_attributes.len(),
482                options.max_attributes_per_element
483            ),
484        ));
485    }
486
487    let mut undo = NamespaceUndo::new();
488    for (qname, prefix, local_name, value) in &raw_attributes {
489        if qname == "xmlns" {
490            validate_namespace_binding(None, value, position)?;
491            let previous = if value.is_empty() {
492                scope.remove("")
493            } else {
494                scope.insert(String::new(), Arc::<str>::from(value.as_str()))
495            };
496            undo.push((String::new(), previous));
497        } else if prefix.as_deref() == Some("xmlns") {
498            validate_namespace_binding(Some(local_name.as_str()), value, position)?;
499            let previous = scope.insert(local_name.clone(), Arc::<str>::from(value.as_str()));
500            undo.push((local_name.clone(), previous));
501        }
502    }
503    if let Some(prefix) = &prefix {
504        if !scope.contains_key(prefix) {
505            return Err(ParseError::new(
506                ParseErrorKind::UndeclaredPrefix,
507                position,
508                format!("element prefix `{prefix}` is not declared"),
509            ));
510        }
511    }
512    for (_, prefix, _, _) in &raw_attributes {
513        if let Some(prefix) = prefix {
514            if prefix != "xmlns" && !scope.contains_key(prefix) {
515                return Err(ParseError::new(
516                    ParseErrorKind::UndeclaredPrefix,
517                    position,
518                    format!("attribute prefix `{prefix}` is not declared"),
519                ));
520            }
521        }
522    }
523    let namespace_uri = scope.get(prefix.as_deref().unwrap_or_default()).cloned();
524    let attributes = raw_attributes
525        .into_iter()
526        .map(|(qname, prefix, local_name, value)| {
527            let namespace_uri = if qname == "xmlns" || prefix.as_deref() == Some("xmlns") {
528                Some(Arc::<str>::from(XMLNS_NAMESPACE))
529            } else {
530                prefix
531                    .as_ref()
532                    .and_then(|prefix| scope.get(prefix).cloned())
533            };
534            Attribute::parsed(qname, prefix, local_name, namespace_uri, value)
535        })
536        .collect();
537    Ok((
538        Element::parsed(
539            qname,
540            prefix,
541            local_name,
542            namespace_uri,
543            attributes,
544            empty_style,
545            span,
546        ),
547        undo,
548    ))
549}
550
551fn split_qname(qname: &str, position: u64) -> Result<(Option<String>, String), ParseError> {
552    match qname.split_once(':') {
553        None if !qname.is_empty() => Ok((None, qname.to_owned())),
554        Some((prefix, local))
555            if !prefix.is_empty() && !local.is_empty() && !local.contains(':') =>
556        {
557            Ok((Some(prefix.to_owned()), local.to_owned()))
558        }
559        _ => Err(ParseError::new(
560            ParseErrorKind::MalformedQName,
561            position,
562            format!("`{qname}` is not a namespace-qualified XML name"),
563        )),
564    }
565}
566
567fn validate_namespace_binding(
568    prefix: Option<&str>,
569    uri: &str,
570    position: u64,
571) -> Result<(), ParseError> {
572    let valid = match prefix {
573        Some("xmlns") => false,
574        Some("xml") => uri == XML_NAMESPACE,
575        Some(_) => !uri.is_empty() && uri != XML_NAMESPACE && uri != XMLNS_NAMESPACE,
576        None => uri != XML_NAMESPACE && uri != XMLNS_NAMESPACE,
577    };
578    if valid {
579        Ok(())
580    } else {
581        Err(ParseError::new(
582            ParseErrorKind::MalformedXml,
583            position,
584            format!("invalid reserved namespace binding for prefix {prefix:?}"),
585        ))
586    }
587}
588
589fn append_element(
590    element: Element,
591    parents: &mut [Element],
592    root: &mut Option<Element>,
593) -> Result<(), ParseError> {
594    // The element's own extent: `<a>` through `</a>`, or just `<a/>`. Derived
595    // from the element rather than passed in so the two callers (End and Empty)
596    // cannot disagree about what a child element's span covers.
597    let span = element.full_span();
598    if let Some(parent) = parents.last_mut() {
599        parent.push(Node::Element(element), span);
600        return Ok(());
601    }
602    if root.replace(element).is_some() {
603        return Err(ParseError::new(
604            ParseErrorKind::MultipleRoots,
605            0,
606            "document contains more than one root element",
607        ));
608    }
609    Ok(())
610}
611
612fn append_node(
613    node: Node,
614    span: Option<Span>,
615    parents: &mut [Element],
616    prolog: &mut NodeList,
617    epilog: &mut NodeList,
618    root_exists: bool,
619) {
620    if let Some(parent) = parents.last_mut() {
621        parent.push(node, span);
622    } else if root_exists {
623        epilog.push(node, span);
624    } else {
625        prolog.push(node, span);
626    }
627}
628
629fn increment_nodes(
630    count: &mut usize,
631    options: ParseOptions,
632    position: u64,
633) -> Result<(), ParseError> {
634    *count += 1;
635    if *count > options.max_nodes {
636        return Err(ParseError::new(
637            ParseErrorKind::NodeLimit,
638            position,
639            format!("node count exceeds limit {}", options.max_nodes),
640        ));
641    }
642    Ok(())
643}
644
645fn decode(reader: &Reader<&[u8]>, bytes: &[u8], position: u64) -> Result<String, ParseError> {
646    reader
647        .decoder()
648        .decode(bytes)
649        .map(|value| value.into_owned())
650        .map_err(|error| {
651            ParseError::new(ParseErrorKind::InvalidEncoding, position, error.to_string())
652        })
653}
654
655fn resolve_reference(reference: &str) -> Option<String> {
656    let character = match reference {
657        "lt" => '<',
658        "gt" => '>',
659        "amp" => '&',
660        "apos" => '\'',
661        "quot" => '"',
662        value if value.starts_with("#x") => {
663            char::from_u32(u32::from_str_radix(&value[2..], 16).ok()?)?
664        }
665        value if value.starts_with('#') => char::from_u32(value[1..].parse().ok()?)?,
666        _ => return None,
667    };
668    Some(character.to_string())
669}