1use 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#[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#[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#[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
429struct 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 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}