roxmltree/
parse.rs

1use alloc::string::{String, ToString};
2use alloc::{vec, vec::Vec};
3use alloc::borrow::Cow;
4use core::ops::Range;
5use core::mem::take;
6use core::fmt;
7use memchr::{memchr, memchr2, memchr_iter};
8
9use crate::{
10    AttributeData, Document, ExpandedNameIndexed, NamespaceIdx, Namespaces, NodeData, NodeId,
11    NodeKind, ShortRange, StringStorage, TextPos, NS_XMLNS_URI, NS_XML_PREFIX, NS_XML_URI, PI,
12    XMLNS,
13};
14
15use crate::tokenizer::{self, Reference, StrSpan, Stream};
16
17type Result<T> = core::result::Result<T, Error>;
18
19/// A list of all possible errors.
20#[derive(Clone, PartialEq, Eq, Hash, Debug)]
21pub enum Error {
22    /// The `xmlns:xml` attribute must have an <http://www.w3.org/XML/1998/namespace> URI.
23    InvalidXmlPrefixUri(TextPos),
24
25    /// Only the `xmlns:xml` attribute can have the <http://www.w3.org/XML/1998/namespace> URI.
26    UnexpectedXmlUri(TextPos),
27
28    /// The <http://www.w3.org/2000/xmlns/> URI must not be declared.
29    UnexpectedXmlnsUri(TextPos),
30
31    /// `xmlns` can't be used as an element prefix.
32    InvalidElementNamePrefix(TextPos),
33
34    /// A namespace was already defined on this element.
35    DuplicatedNamespace(String, TextPos),
36
37    /// An unknown namespace.
38    ///
39    /// Indicates that an element or an attribute has an unknown qualified name prefix.
40    ///
41    /// The first value is a prefix.
42    UnknownNamespace(String, TextPos),
43
44    /// Incorrect tree structure.
45    ///
46    /// expected, actual, position
47    UnexpectedCloseTag(String, String, TextPos),
48
49    /// Entity value starts with a close tag.
50    ///
51    /// Example:
52    /// ```xml
53    /// <!DOCTYPE test [ <!ENTITY p '</p>'> ]>
54    /// <root>&p;</root>
55    /// ```
56    UnexpectedEntityCloseTag(TextPos),
57
58    /// A reference to an entity that was not defined in the DTD.
59    UnknownEntityReference(String, TextPos),
60
61    /// A malformed entity reference.
62    ///
63    /// A `&` character inside an attribute value or text indicates an entity reference.
64    /// Otherwise, the document is not well-formed.
65    MalformedEntityReference(TextPos),
66
67    /// A possible entity reference loop.
68    ///
69    /// The current depth limit is 10. The max number of references per reference is 255.
70    EntityReferenceLoop(TextPos),
71
72    /// Attribute value cannot have a `<` character.
73    InvalidAttributeValue(TextPos),
74
75    /// An element has a duplicated attributes.
76    ///
77    /// This also includes namespaces resolving.
78    /// So an element like this will lead to an error.
79    /// ```xml
80    /// <e xmlns:n1='http://www.w3.org' xmlns:n2='http://www.w3.org' n1:a='b1' n2:a='b2'/>
81    /// ```
82    DuplicatedAttribute(String, TextPos),
83
84    /// The XML document must have at least one element.
85    NoRootNode,
86
87    /// The root node was opened but never closed.
88    UnclosedRootNode,
89
90    /// An XML document can have only one XML declaration
91    /// and it must be at the start of the document.
92    UnexpectedDeclaration(TextPos),
93
94    /// An XML with DTD detected.
95    ///
96    /// This error will be emitted only when `ParsingOptions::allow_dtd` is set to `false`.
97    DtdDetected,
98
99    /// Indicates that the [`ParsingOptions::nodes_limit`] was reached,
100    /// or that elements are nested deeper than `u32::MAX` levels.
101    NodesLimitReached,
102
103    /// Indicates that too many attributes were parsed.
104    AttributesLimitReached,
105
106    /// Indicates that too many namespaces were parsed.
107    NamespacesLimitReached,
108
109    /// An invalid name.
110    InvalidName(TextPos),
111
112    /// A non-XML character has occurred.
113    ///
114    /// Valid characters are: <https://www.w3.org/TR/xml/#char32>
115    NonXmlChar(char, TextPos),
116
117    /// An invalid/unexpected character.
118    ///
119    /// expected, actual, position
120    InvalidChar(u8, u8, TextPos),
121
122    /// An invalid/unexpected character.
123    ///
124    /// expected, actual, position
125    InvalidChar2(&'static str, u8, TextPos),
126
127    /// An unexpected string.
128    ///
129    /// Contains what string was expected.
130    InvalidString(&'static str, TextPos),
131
132    /// An invalid ExternalID in the DTD.
133    InvalidExternalID(TextPos),
134
135    /// Resolving the given entity yielded an error.
136    EntityResolver(TextPos, String),
137
138    /// A comment cannot contain `--` or end with `-`.
139    InvalidComment(TextPos),
140
141    /// A Character Data node contains an invalid data.
142    ///
143    /// Currently, only `]]>` is not allowed.
144    InvalidCharacterData(TextPos),
145
146    /// An unknown token.
147    UnknownToken(TextPos),
148
149    /// The steam ended earlier than we expected.
150    ///
151    /// Should only appear on invalid input data.
152    UnexpectedEndOfStream,
153}
154
155impl Error {
156    /// Returns the error position.
157    pub fn pos(&self) -> TextPos {
158        match *self {
159            Error::InvalidXmlPrefixUri(pos) => pos,
160            Error::UnexpectedXmlUri(pos) => pos,
161            Error::UnexpectedXmlnsUri(pos) => pos,
162            Error::InvalidElementNamePrefix(pos) => pos,
163            Error::DuplicatedNamespace(_, pos) => pos,
164            Error::UnknownNamespace(_, pos) => pos,
165            Error::UnexpectedCloseTag(_, _, pos) => pos,
166            Error::UnexpectedEntityCloseTag(pos) => pos,
167            Error::UnknownEntityReference(_, pos) => pos,
168            Error::MalformedEntityReference(pos) => pos,
169            Error::EntityReferenceLoop(pos) => pos,
170            Error::InvalidAttributeValue(pos) => pos,
171            Error::DuplicatedAttribute(_, pos) => pos,
172            Error::NoRootNode => TextPos::new(1, 1),
173            Error::UnclosedRootNode => TextPos::new(1, 1),
174            Error::UnexpectedDeclaration(pos) => pos,
175            Error::DtdDetected => TextPos::new(1, 1),
176            Error::NodesLimitReached => TextPos::new(1, 1),
177            Error::AttributesLimitReached => TextPos::new(1, 1),
178            Error::NamespacesLimitReached => TextPos::new(1, 1),
179            Error::InvalidName(pos) => pos,
180            Error::NonXmlChar(_, pos) => pos,
181            Error::InvalidChar(_, _, pos) => pos,
182            Error::InvalidChar2(_, _, pos) => pos,
183            Error::InvalidString(_, pos) => pos,
184            Error::InvalidExternalID(pos) => pos,
185            Error::EntityResolver(pos, _) => pos,
186            Error::InvalidComment(pos) => pos,
187            Error::InvalidCharacterData(pos) => pos,
188            Error::UnknownToken(pos) => pos,
189            Error::UnexpectedEndOfStream => TextPos::new(1, 1),
190        }
191    }
192}
193
194impl core::fmt::Display for Error {
195    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
196        match self {
197            Error::InvalidXmlPrefixUri(pos) => {
198                write!(f, "'xml' namespace prefix mapped to wrong URI at {}", pos)
199            }
200            Error::UnexpectedXmlUri(pos) => {
201                write!(
202                    f,
203                    "the 'xml' namespace URI is used for not 'xml' prefix at {}",
204                    pos
205                )
206            }
207            Error::UnexpectedXmlnsUri(pos) => {
208                write!(
209                    f,
210                    "the 'xmlns' URI is used at {}, but it must not be declared",
211                    pos
212                )
213            }
214            Error::InvalidElementNamePrefix(pos) => {
215                write!(
216                    f,
217                    "the 'xmlns' prefix is used at {}, but it must not be",
218                    pos
219                )
220            }
221            Error::DuplicatedNamespace(ref name, pos) => {
222                write!(f, "namespace '{}' at {} is already defined", name, pos)
223            }
224            Error::UnknownNamespace(ref name, pos) => {
225                write!(f, "an unknown namespace prefix '{}' at {}", name, pos)
226            }
227            Error::UnexpectedCloseTag(ref expected, ref actual, pos) => {
228                write!(
229                    f,
230                    "expected '{}' tag, not '{}' at {}",
231                    expected, actual, pos
232                )
233            }
234            Error::UnexpectedEntityCloseTag(pos) => {
235                write!(f, "unexpected close tag at {}", pos)
236            }
237            Error::MalformedEntityReference(pos) => {
238                write!(f, "malformed entity reference at {}", pos)
239            }
240            Error::UnknownEntityReference(ref name, pos) => {
241                write!(f, "unknown entity reference '{}' at {}", name, pos)
242            }
243            Error::EntityReferenceLoop(pos) => {
244                write!(f, "a possible entity reference loop is detected at {}", pos)
245            }
246            Error::InvalidAttributeValue(pos) => {
247                write!(f, "unescaped '<' found at {}", pos)
248            }
249            Error::DuplicatedAttribute(ref name, pos) => {
250                write!(f, "attribute '{}' at {} is already defined", name, pos)
251            }
252            Error::NoRootNode => {
253                write!(f, "the document does not have a root node")
254            }
255            Error::UnclosedRootNode => {
256                write!(f, "the root node was opened but never closed")
257            }
258            Error::UnexpectedDeclaration(pos) => {
259                write!(f, "unexpected XML declaration at {}", pos)
260            }
261            Error::DtdDetected => {
262                write!(f, "XML with DTD detected")
263            }
264            Error::NodesLimitReached => {
265                write!(f, "nodes limit reached")
266            }
267            Error::AttributesLimitReached => {
268                write!(f, "more than 2^32 attributes were parsed")
269            }
270            Error::NamespacesLimitReached => {
271                write!(f, "more than 2^16 unique namespaces were parsed")
272            }
273            Error::InvalidName(pos) => {
274                write!(f, "invalid name token at {}", pos)
275            }
276            Error::NonXmlChar(c, pos) => {
277                write!(f, "a non-XML character {:?} found at {}", c, pos)
278            }
279            Error::InvalidChar(expected, actual, pos) => {
280                write!(
281                    f,
282                    "expected '{}' not '{}' at {}",
283                    *expected as char, *actual as char, pos
284                )
285            }
286            Error::InvalidChar2(expected, actual, pos) => {
287                write!(
288                    f,
289                    "expected {} not '{}' at {}",
290                    expected, *actual as char, pos
291                )
292            }
293            Error::InvalidString(expected, pos) => {
294                write!(f, "expected '{}' at {}", expected, pos)
295            }
296            Error::InvalidExternalID(pos) => {
297                write!(f, "invalid ExternalID at {}", pos)
298            }
299            Error::EntityResolver(pos, msg) => {
300                write!(f, "entity resolver failed at {}: {}", pos, msg)
301            }
302            Error::InvalidComment(pos) => {
303                write!(f, "comment at {} contains '--'", pos)
304            }
305            Error::InvalidCharacterData(pos) => {
306                write!(f, "']]>' at {} is not allowed inside a character data", pos)
307            }
308            Error::UnknownToken(pos) => {
309                write!(f, "unknown token at {}", pos)
310            }
311            Error::UnexpectedEndOfStream => {
312                write!(f, "unexpected end of stream")
313            }
314        }
315    }
316}
317
318#[cfg(feature = "std")]
319impl std::error::Error for Error {
320    fn description(&self) -> &str {
321        "an XML parsing error"
322    }
323}
324
325/// Parsing options.
326pub struct ParsingOptions<'input> {
327    /// Allow DTD parsing.
328    ///
329    /// When set to `false`, XML with DTD will cause an error.
330    /// Empty DTD block is not an error.
331    ///
332    /// Currently, there is no option to simply skip DTD.
333    /// Mainly because you will get `UnknownEntityReference` error later anyway.
334    ///
335    /// This flag is set to `false` by default for security reasons,
336    /// but `roxmltree` still has checks for billion laughs attack,
337    /// so this is just an extra security measure.
338    ///
339    /// Default: false
340    pub allow_dtd: bool,
341
342    /// Sets the maximum number of nodes to parse.
343    ///
344    /// Useful when dealing with random input to limit memory usage.
345    ///
346    /// Default: u32::MAX (no limit)
347    pub nodes_limit: u32,
348
349    /// Function to resolve external entities
350    ///
351    /// See [`EntityResolver`] for the signature
352    /// and the expected behaviour.
353    pub entity_resolver: Option<&'input EntityResolver<'input>>,
354}
355
356/// Function to resolve external entities
357///
358/// This function is passed the optional public ID
359/// and the mandatory URI of the external entity.
360///
361/// It is expected to yield the content defining
362/// the URI, possibly preceeded by a text declaration.
363///
364/// If it yields [`None`], the entity is discarded
365/// and will yield errors if referenced during parsing.
366///
367/// Errors must be stringified so they can be propagated
368/// via [`Error::EntityResolver`].
369pub type EntityResolver<'input> =
370    dyn Fn(Option<&str>, &str) -> core::result::Result<Option<&'input str>, String> + 'input;
371
372impl Default for ParsingOptions<'_> {
373    fn default() -> Self {
374        ParsingOptions {
375            allow_dtd: false,
376            nodes_limit: u32::MAX,
377            entity_resolver: None,
378        }
379    }
380}
381
382impl fmt::Debug for ParsingOptions<'_> {
383    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
384        let entity_resolver = if self.entity_resolver.is_some() {
385            "Some(..)"
386        } else {
387            "None"
388        };
389
390        fmt.debug_struct("ParsingOptions")
391            .field("allow_dtd", &self.allow_dtd)
392            .field("nodes_limit", &self.nodes_limit)
393            .field("entity_resolver", &entity_resolver)
394            .finish()
395    }
396}
397
398struct TempAttributeData<'input> {
399    prefix: &'input str,
400    local: &'input str,
401    value: StringStorage<'input>,
402    range: Range<usize>,
403    #[cfg(feature = "positions")]
404    qname_len: u16,
405    #[cfg(feature = "positions")]
406    eq_len: u8,
407}
408
409impl<'input> Document<'input> {
410    /// Parses the input XML string.
411    ///
412    /// We do not support `&[u8]` or `Reader` because the input must be an already allocated
413    /// UTF-8 string.
414    ///
415    /// This is a shorthand for `Document::parse_with_options(data, ParsingOptions::default())`.
416    ///
417    /// # Examples
418    ///
419    /// ```
420    /// let doc = roxmltree::Document::parse("<e/>").unwrap();
421    /// assert_eq!(doc.descendants().count(), 2); // root node + `e` element node
422    /// ```
423    #[inline]
424    pub fn parse(text: &'input str) -> Result<Self> {
425        Self::parse_with_options(text, ParsingOptions::default())
426    }
427
428    /// Parses the input XML string using to selected options.
429    ///
430    /// We do not support `&[u8]` or `Reader` because the input must be an already allocated
431    /// UTF-8 string.
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// let opt = roxmltree::ParsingOptions::default();
437    /// let doc = roxmltree::Document::parse_with_options("<e/>", opt).unwrap();
438    /// assert_eq!(doc.descendants().count(), 2); // root node + `e` element node
439    /// ```
440    #[inline]
441    pub fn parse_with_options(text: &'input str, opt: ParsingOptions<'input>) -> Result<Self> {
442        parse(text, opt)
443    }
444}
445
446struct Entity<'input> {
447    name: &'input str,
448    value: StrSpan<'input>,
449}
450
451#[derive(Clone, Copy)]
452struct TagNameSpan<'input> {
453    prefix: &'input str,
454    name: &'input str,
455    pos: usize,
456    prefix_pos: usize,
457}
458
459impl<'input> TagNameSpan<'input> {
460    #[inline]
461    fn new_null() -> Self {
462        Self {
463            prefix: "",
464            name: "",
465            pos: 0,
466            prefix_pos: 0,
467        }
468    }
469}
470
471/// An entity loop detector.
472///
473/// Limits:
474/// - Entities depth is 10.
475/// - Maximum number of entity references per entity reference is 255.
476///
477/// Basically, if a text or an attribute has an entity reference and this reference
478/// has more than 10 nested references - this is an error.
479///
480/// This is useful for simple loops like:
481///
482/// ```text
483/// <!ENTITY a '&b;'>
484/// <!ENTITY b '&a;'>
485/// ```
486///
487/// And, if a text or an attribute has an entity reference and it references more
488/// than 255 references - this is an error.
489///
490/// This is useful for cases like billion laughs attack, where depth can be pretty small,
491/// but the number of references is exponentially increasing:
492///
493/// ```text
494/// <!ENTITY lol "lol">
495/// <!ENTITY lol1 "&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;&lol;">
496/// <!ENTITY lol2 "&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;&lol1;">
497/// <!ENTITY lol3 "&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;&lol2;">
498/// <!ENTITY lol4 "&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;&lol3;">
499/// ```
500#[derive(Default)]
501struct LoopDetector {
502    /// References depth.
503    depth: u8,
504    /// Number of references resolved by the root reference.
505    references: u8,
506}
507
508impl LoopDetector {
509    #[inline]
510    fn inc_depth(&mut self, stream: &Stream) -> Result<()> {
511        if self.depth < 10 {
512            self.depth += 1;
513            Ok(())
514        } else {
515            Err(Error::EntityReferenceLoop(stream.gen_text_pos()))
516        }
517    }
518
519    #[inline]
520    fn dec_depth(&mut self) {
521        if self.depth > 0 {
522            self.depth -= 1;
523        }
524
525        // Reset references count after reaching zero depth.
526        if self.depth == 0 {
527            self.references = 0;
528        }
529    }
530
531    #[inline]
532    fn inc_references(&mut self, stream: &Stream) -> Result<()> {
533        if self.depth == 0 {
534            // Allow infinite amount of references at zero depth.
535            Ok(())
536        } else {
537            if self.references == u8::MAX {
538                return Err(Error::EntityReferenceLoop(stream.gen_text_pos()));
539            }
540
541            self.references += 1;
542            Ok(())
543        }
544    }
545}
546
547struct Context<'input> {
548    opt: ParsingOptions<'input>,
549    namespace_start_idx: usize,
550    current_attributes: Vec<TempAttributeData<'input>>,
551    awaiting_subtree: Vec<NodeId>,
552    parent_prefixes: Vec<&'input str>,
553    entities: Vec<Entity<'input>>,
554    after_text: Vec<Cow<'input, str>>,
555    parent_id: NodeId,
556    tag_name: TagNameSpan<'input>,
557    loop_detector: LoopDetector,
558    doc: Document<'input>,
559}
560
561impl<'input> Context<'input> {
562    fn append_node(&mut self, kind: NodeKind<'input>, range: Range<usize>) -> Result<NodeId> {
563        if self.doc.nodes.len() >= self.opt.nodes_limit as usize {
564            return Err(Error::NodesLimitReached);
565        }
566
567        #[cfg(not(feature = "positions"))]
568        let _ = range;
569
570        let new_child_id = NodeId::from(self.doc.nodes.len());
571
572        let appending_element = matches!(kind, NodeKind::Element { .. });
573        self.doc.nodes.push(NodeData {
574            parent: Some(self.parent_id),
575            prev_sibling: None,
576            next_subtree: None,
577            last_child: None,
578            kind,
579            #[cfg(feature = "positions")]
580            range,
581        });
582
583        let last_child_id = self.doc.nodes[self.parent_id.get_usize()].last_child;
584        self.doc.nodes[new_child_id.get_usize()].prev_sibling = last_child_id;
585        self.doc.nodes[self.parent_id.get_usize()].last_child = Some(new_child_id);
586
587        for id in &self.awaiting_subtree {
588            self.doc.nodes[id.get_usize()].next_subtree = Some(new_child_id);
589        }
590        self.awaiting_subtree.clear();
591
592        if !appending_element {
593            self.awaiting_subtree
594                .push(NodeId::from(self.doc.nodes.len() - 1));
595        }
596
597        Ok(new_child_id)
598    }
599
600    fn append_text(
601        &mut self,
602        text: Cow<'input, str>,
603        range: Range<usize>,
604    ) -> Result<()> {
605        if self.after_text.is_empty() {
606            let text = match &text {
607                Cow::Borrowed(text) => StringStorage::Borrowed(text),
608                Cow::Owned(text) => StringStorage::new_owned(text.as_str()),
609            };
610
611            self.append_node(NodeKind::Text(text), range)?;
612        }
613
614        self.after_text.push(text);
615        Ok(())
616    }
617
618    #[cold]
619    #[inline(never)]
620    fn merge_text(&mut self) {
621        let node = &mut self.doc.nodes.last_mut().unwrap();
622
623        let text = match &mut node.kind {
624            NodeKind::Text(text) => text,
625            _ => unreachable!(),
626        };
627
628        *text = StringStorage::new_owned(&self.after_text.join(""));
629    }
630
631    #[inline]
632    fn reset_after_text(&mut self) {
633        if self.after_text.is_empty() {
634            return;
635        }
636
637        if self.after_text.len() > 1 {
638            self.merge_text();
639        }
640
641        self.after_text.clear();
642    }
643}
644
645fn parse<'input>(text: &'input str, opt: ParsingOptions<'input>) -> Result<Document<'input>> {
646    // Trying to guess rough nodes and attributes amount.
647    let nodes_capacity = memchr_iter(b'<', text.as_bytes()).count();
648    let attributes_capacity = memchr_iter(b'=', text.as_bytes()).count();
649
650    // Init document.
651    let mut doc = Document {
652        text,
653        nodes: Vec::with_capacity(nodes_capacity),
654        attributes: Vec::with_capacity(attributes_capacity),
655        namespaces: Namespaces::default(),
656    };
657
658    // Add a root node.
659    doc.nodes.push(NodeData {
660        parent: None,
661        prev_sibling: None,
662        next_subtree: None,
663        last_child: None,
664        kind: NodeKind::Root,
665        #[cfg(feature = "positions")]
666        range: 0..text.len(),
667    });
668
669    doc.namespaces
670        .push_ns(Some(NS_XML_PREFIX), StringStorage::Borrowed(NS_XML_URI))?;
671
672    let allow_dtd = opt.allow_dtd;
673
674    let mut ctx = Context {
675        opt,
676        namespace_start_idx: 1,
677        current_attributes: Vec::with_capacity(16),
678        entities: Vec::new(),
679        awaiting_subtree: Vec::new(),
680        parent_prefixes: vec![""],
681        after_text: Vec::with_capacity(1),
682        parent_id: NodeId::new(0),
683        tag_name: TagNameSpan::new_null(),
684        loop_detector: LoopDetector::default(),
685        doc,
686    };
687
688    tokenizer::parse(text, allow_dtd, &mut ctx)?;
689
690    let mut doc = ctx.doc;
691    if !doc.root().children().any(|n| n.is_element()) {
692        return Err(Error::NoRootNode);
693    }
694
695    if ctx.parent_prefixes.len() > 1 {
696        return Err(Error::UnclosedRootNode);
697    }
698
699    doc.nodes.shrink_to_fit();
700    doc.attributes.shrink_to_fit();
701    doc.namespaces.shrink_to_fit();
702
703    Ok(doc)
704}
705
706impl<'input> tokenizer::XmlEvents<'input> for Context<'input> {
707    #[inline(always)]
708    fn token(&mut self, token: tokenizer::Token<'input>) -> Result<()> {
709        match token {
710            tokenizer::Token::ProcessingInstruction(target, value, range) => {
711                self.reset_after_text();
712                let pi = NodeKind::PI(PI { target, value });
713                self.append_node(pi, range)?;
714            }
715            tokenizer::Token::Comment(text, range) => {
716                self.reset_after_text();
717                self.append_node(NodeKind::Comment(StringStorage::Borrowed(text)), range)?;
718            }
719            tokenizer::Token::EntityDeclaration(name, definition) => {
720                self.entities.push(Entity {
721                    name,
722                    value: definition,
723                });
724            }
725            tokenizer::Token::ElementStart(prefix, local, start) => {
726                self.reset_after_text();
727
728                if prefix == XMLNS {
729                    let pos = self.doc.text_pos_at(start + 1);
730                    return Err(Error::InvalidElementNamePrefix(pos));
731                }
732
733                self.tag_name = TagNameSpan {
734                    prefix,
735                    name: local,
736                    pos: start,
737                    prefix_pos: start + 1,
738                };
739            }
740            tokenizer::Token::Attribute(range, qname_len, eq_len, prefix, local, value) => {
741                process_attribute(range, qname_len, eq_len, prefix, local, value, self)?;
742            }
743            tokenizer::Token::ElementEnd(end, range) => {
744                self.reset_after_text();
745                process_element(end, range, self)?;
746            }
747            tokenizer::Token::Text(text, range) => {
748                process_text(text, range, self)?;
749            }
750            tokenizer::Token::Cdata(text, range) => {
751                process_cdata(text, range, self)?;
752            }
753        }
754
755        Ok(())
756    }
757
758    fn resolve_entity(&mut self, pub_id: Option<&str>, uri: &str) -> core::result::Result<Option<&'input str>, String> {
759        match &mut self.opt.entity_resolver {
760            Some(entity_resolver) => entity_resolver(pub_id, uri),
761            None => Ok(None),
762        }
763    }
764
765}
766
767#[allow(clippy::too_many_arguments)]
768fn process_attribute<'input>(
769    range: Range<usize>,
770    qname_len: u16,
771    eq_len: u8,
772    prefix: &'input str,
773    local: &'input str,
774    value: StrSpan<'input>,
775    ctx: &mut Context<'input>,
776) -> Result<()> {
777    let value = normalize_attribute(value, ctx)?;
778
779    if prefix == XMLNS {
780        // The xmlns namespace MUST NOT be declared as the default namespace.
781        if value.as_str() == NS_XMLNS_URI {
782            let pos = ctx.doc.text_pos_at(range.start);
783            return Err(Error::UnexpectedXmlnsUri(pos));
784        }
785
786        let is_xml_ns_uri = value.as_str() == NS_XML_URI;
787
788        // The prefix 'xml' is by definition bound to the namespace name
789        // http://www.w3.org/XML/1998/namespace.
790        // It MUST NOT be bound to any other namespace name.
791        if local == NS_XML_PREFIX {
792            if !is_xml_ns_uri {
793                let pos = ctx.doc.text_pos_at(range.start);
794                return Err(Error::InvalidXmlPrefixUri(pos));
795            }
796        } else {
797            // The xml namespace MUST NOT be bound to a non-xml prefix.
798            if is_xml_ns_uri {
799                let pos = ctx.doc.text_pos_at(range.start);
800                return Err(Error::UnexpectedXmlUri(pos));
801            }
802        }
803
804        // Check for duplicated namespaces.
805        if ctx
806            .doc
807            .namespaces
808            .exists(ctx.namespace_start_idx, Some(local))
809        {
810            let pos = ctx.doc.text_pos_at(range.start);
811            return Err(Error::DuplicatedNamespace(local.to_string(), pos));
812        }
813
814        // Xml namespace should not be added to the namespaces.
815        if !is_xml_ns_uri {
816            ctx.doc.namespaces.push_ns(Some(local), value)?;
817        }
818    } else if local == XMLNS {
819        // The xml namespace MUST NOT be declared as the default namespace.
820        if value.as_str() == NS_XML_URI {
821            let pos = ctx.doc.text_pos_at(range.start);
822            return Err(Error::UnexpectedXmlUri(pos));
823        }
824
825        // The xmlns namespace MUST NOT be declared as the default namespace.
826        if value.as_str() == NS_XMLNS_URI {
827            let pos = ctx.doc.text_pos_at(range.start);
828            return Err(Error::UnexpectedXmlnsUri(pos));
829        }
830
831        ctx.doc.namespaces.push_ns(None, value)?;
832    } else {
833        #[cfg(not(feature = "positions"))]
834        let _ = (qname_len, eq_len);
835
836        ctx.current_attributes.push(TempAttributeData {
837            prefix,
838            local,
839            value,
840            range,
841            #[cfg(feature = "positions")]
842            qname_len,
843            #[cfg(feature = "positions")]
844            eq_len,
845        });
846    }
847
848    Ok(())
849}
850
851fn process_element<'input>(
852    end_token: tokenizer::ElementEnd<'input>,
853    token_range: Range<usize>,
854    ctx: &mut Context<'input>,
855) -> Result<()> {
856    if ctx.tag_name.name.is_empty() {
857        // May occur in XML like this:
858        // <!DOCTYPE test [ <!ENTITY p '</p>'> ]>
859        // <root>&p;</root>
860
861        if let tokenizer::ElementEnd::Close(..) = end_token {
862            return Err(Error::UnexpectedEntityCloseTag(
863                ctx.doc.text_pos_at(token_range.start),
864            ));
865        } else {
866            unreachable!("should be already checked by the tokenizer");
867        }
868    }
869
870    let namespaces = ctx.resolve_namespaces();
871    ctx.namespace_start_idx = ctx.doc.namespaces.tree_order.len();
872
873    let attributes = resolve_attributes(namespaces, ctx)?;
874
875    match end_token {
876        tokenizer::ElementEnd::Empty => {
877            let tag_ns_idx = get_ns_idx_by_prefix(
878                namespaces,
879                ctx.tag_name.prefix_pos,
880                ctx.tag_name.prefix,
881                &ctx.doc,
882            )?;
883            let new_element_id = ctx.append_node(
884                NodeKind::Element {
885                    tag_name: ExpandedNameIndexed {
886                        namespace_idx: tag_ns_idx,
887                        local_name: ctx.tag_name.name,
888                    },
889                    attributes,
890                    namespaces,
891                },
892                ctx.tag_name.pos..token_range.end,
893            )?;
894            ctx.awaiting_subtree.push(new_element_id);
895        }
896        tokenizer::ElementEnd::Close(prefix, local) => {
897            let parent_node = &mut ctx.doc.nodes[ctx.parent_id.get_usize()];
898            // should never panic as we start with the single prefix of the
899            // root node and always push another one when changing the parent
900            let parent_prefix = *ctx.parent_prefixes.last().unwrap();
901
902            #[cfg(feature = "positions")]
903            {
904                parent_node.range.end = token_range.end;
905            }
906
907            if let NodeKind::Element { ref tag_name, .. } = parent_node.kind {
908                if prefix != parent_prefix || local != tag_name.local_name {
909                    return Err(Error::UnexpectedCloseTag(
910                        gen_qname_string(parent_prefix, tag_name.local_name),
911                        gen_qname_string(prefix, local),
912                        ctx.doc.text_pos_at(token_range.start),
913                    ));
914                }
915            }
916            ctx.awaiting_subtree.push(ctx.parent_id);
917
918            if let Some(id) = parent_node.parent {
919                ctx.parent_id = id;
920                ctx.parent_prefixes.pop();
921                debug_assert!(!ctx.parent_prefixes.is_empty());
922            } else {
923                // May occur in XML like this:
924                // <!DOCTYPE test [ <!ENTITY p '<p></p></p>'> ]>
925                // <p>&p;&p;
926
927                return Err(Error::UnexpectedEntityCloseTag(
928                    ctx.doc.text_pos_at(token_range.start),
929                ));
930            }
931        }
932        tokenizer::ElementEnd::Open => {
933            let tag_ns_idx = get_ns_idx_by_prefix(
934                namespaces,
935                ctx.tag_name.prefix_pos,
936                ctx.tag_name.prefix,
937                &ctx.doc,
938            )?;
939            ctx.parent_id = ctx.append_node(
940                NodeKind::Element {
941                    tag_name: ExpandedNameIndexed {
942                        namespace_idx: tag_ns_idx,
943                        local_name: ctx.tag_name.name,
944                    },
945                    attributes,
946                    namespaces,
947                },
948                ctx.tag_name.pos..token_range.end,
949            )?;
950            ctx.parent_prefixes.push(ctx.tag_name.prefix);
951        }
952    }
953
954    Ok(())
955}
956
957impl Context<'_> {
958    fn resolve_namespaces(&mut self) -> ShortRange {
959        if let NodeKind::Element { ref namespaces, .. } =
960            self.doc.nodes[self.parent_id.get_usize()].kind
961        {
962            let parent_ns = *namespaces;
963            if self.namespace_start_idx == self.doc.namespaces.tree_order.len() {
964                return parent_ns;
965            }
966
967            for i in parent_ns.to_urange() {
968                if !self.doc.namespaces.exists(
969                    self.namespace_start_idx,
970                    self.doc
971                        .namespaces
972                        .get(self.doc.namespaces.tree_order[i])
973                        .name,
974                ) {
975                    self.doc.namespaces.push_ref(i);
976                }
977            }
978        }
979
980        (self.namespace_start_idx..self.doc.namespaces.tree_order.len()).into()
981    }
982}
983
984fn resolve_attributes(namespaces: ShortRange, ctx: &mut Context) -> Result<ShortRange> {
985    if ctx.current_attributes.is_empty() {
986        return Ok(ShortRange::new(0, 0));
987    }
988
989    if ctx.doc.attributes.len() + ctx.current_attributes.len() >= u32::MAX as usize {
990        return Err(Error::AttributesLimitReached);
991    }
992
993    let start_idx = ctx.doc.attributes.len();
994
995    for attr in ctx.current_attributes.drain(..) {
996        let namespace_idx = if attr.prefix == NS_XML_PREFIX {
997            // The prefix 'xml' is by definition bound to the namespace name
998            // http://www.w3.org/XML/1998/namespace. This namespace is added
999            // to the document on creation and is always element 0.
1000            Some(NamespaceIdx(0))
1001        } else if attr.prefix.is_empty() {
1002            // 'The namespace name for an unprefixed attribute name
1003            // always has no value.'
1004            None
1005        } else {
1006            get_ns_idx_by_prefix(namespaces, attr.range.start, attr.prefix, &ctx.doc)?
1007        };
1008
1009        let attr_name = ExpandedNameIndexed {
1010            namespace_idx,
1011            local_name: attr.local,
1012        };
1013
1014        // Check for duplicated attributes.
1015        if ctx.doc.attributes[start_idx..].iter().any(|attr| {
1016            attr.name.as_expanded_name(&ctx.doc) == attr_name.as_expanded_name(&ctx.doc)
1017        }) {
1018            let pos = ctx.doc.text_pos_at(attr.range.start);
1019            return Err(Error::DuplicatedAttribute(attr.local.to_string(), pos));
1020        }
1021
1022        ctx.doc.attributes.push(AttributeData {
1023            name: attr_name,
1024            value: attr.value,
1025            #[cfg(feature = "positions")]
1026            range: attr.range,
1027            #[cfg(feature = "positions")]
1028            qname_len: attr.qname_len,
1029            #[cfg(feature = "positions")]
1030            eq_len: attr.eq_len,
1031        });
1032    }
1033
1034    Ok((start_idx..ctx.doc.attributes.len()).into())
1035}
1036
1037fn process_text<'input>(
1038    text: &'input str,
1039    range: Range<usize>,
1040    ctx: &mut Context<'input>,
1041) -> Result<()> {
1042    // Add text as is if it has only valid characters.
1043    if memchr2(b'&', b'\r', text.as_bytes()).is_none() {
1044        ctx.append_text(Cow::Borrowed(text), range)?;
1045        return Ok(());
1046    }
1047
1048    let mut text_buffer = TextBuffer::new();
1049    let mut is_as_is = false; // TODO: explain
1050    let mut stream = Stream::from_substr(ctx.doc.text, range.clone());
1051    while !stream.at_end() {
1052        match parse_next_chunk(&mut stream, &ctx.entities)? {
1053            NextChunk::Byte(c) => {
1054                if is_as_is {
1055                    text_buffer.push_raw(c);
1056                    is_as_is = false;
1057                } else {
1058                    text_buffer.push_from_text(c, stream.at_end());
1059                }
1060            }
1061            NextChunk::Char(c) => {
1062                for b in CharToBytes::new(c) {
1063                    if ctx.loop_detector.depth > 0 {
1064                        text_buffer.push_from_text(b, stream.at_end());
1065                    } else {
1066                        // Characters not from entity should be added as is.
1067                        // Not sure why... At least `lxml` produces the same result.
1068                        text_buffer.push_raw(b);
1069                        is_as_is = true;
1070                    }
1071                }
1072            }
1073            NextChunk::Text(fragment) => {
1074                is_as_is = false;
1075
1076                if !text_buffer.is_empty() {
1077                    ctx.append_text(Cow::Owned(text_buffer.finish()), range.clone())?;
1078                }
1079
1080                ctx.loop_detector.inc_references(&stream)?;
1081                ctx.loop_detector.inc_depth(&stream)?;
1082
1083                let text = if fragment.range().start == 0 {
1084                    fragment.as_str()
1085                } else {
1086                    ctx.doc.text
1087                };
1088
1089                let mut stream = Stream::from_substr(text, fragment.range());
1090                let prev_tag_name = ctx.tag_name;
1091                ctx.tag_name = TagNameSpan::new_null();
1092                tokenizer::parse_content(&mut stream, ctx)?;
1093                ctx.tag_name = prev_tag_name;
1094                text_buffer.clear();
1095
1096                ctx.loop_detector.dec_depth();
1097            }
1098        }
1099    }
1100
1101    if !text_buffer.is_empty() {
1102        ctx.append_text(Cow::Owned(text_buffer.finish()), range)?;
1103    }
1104
1105    Ok(())
1106}
1107
1108// While the whole purpose of CDATA is to indicate to an XML library that this text
1109// has to be stored as is, carriage return (`\r`) is still has to be replaced with `\n`.
1110fn process_cdata<'input>(
1111    mut text: &'input str,
1112    range: Range<usize>,
1113    ctx: &mut Context<'input>,
1114) -> Result<()> {
1115    let mut pos = memchr(b'\r', text.as_bytes());
1116
1117    // Add text as is if it has only valid characters.
1118    if pos.is_none() {
1119        ctx.append_text(Cow::Borrowed(text), range)?;
1120        return Ok(());
1121    }
1122
1123    let mut buf = String::new();
1124
1125    while let Some(pos1) = pos {
1126        let (line, rest) = text.split_at(pos1);
1127
1128        buf.push_str(line);
1129        buf.push('\n');
1130
1131        text = if rest.as_bytes().get(1) == Some(&b'\n') {
1132            &rest[2..]
1133        } else {
1134            &rest[1..]
1135        };
1136
1137        pos = memchr(b'\r', text.as_bytes());
1138    }
1139
1140    buf.push_str(text);
1141
1142    ctx.append_text(Cow::Owned(buf), range)?;
1143    Ok(())
1144}
1145
1146enum NextChunk<'a> {
1147    Byte(u8),
1148    Char(char),
1149    Text(StrSpan<'a>),
1150}
1151
1152fn parse_next_chunk<'a>(stream: &mut Stream<'a>, entities: &[Entity<'a>]) -> Result<NextChunk<'a>> {
1153    debug_assert!(!stream.at_end());
1154
1155    // Safe, because we already checked that stream is not at the end.
1156    // But we have an additional `debug_assert` above just in case.
1157    let c = stream.curr_byte_unchecked();
1158
1159    // Check for character/entity references.
1160    if c == b'&' {
1161        let start = stream.pos();
1162        match stream.consume_reference() {
1163            Some(Reference::Char(ch)) => Ok(NextChunk::Char(ch)),
1164            Some(Reference::Entity(name)) => entities
1165                .iter()
1166                .find(|e| e.name == name)
1167                .map(|e| NextChunk::Text(e.value))
1168                .ok_or_else(|| {
1169                    let pos = stream.gen_text_pos_from(start);
1170                    Error::UnknownEntityReference(name.into(), pos)
1171                }),
1172            None => {
1173                let pos = stream.gen_text_pos_from(start);
1174                Err(Error::MalformedEntityReference(pos))
1175            }
1176        }
1177    } else {
1178        stream.advance(1);
1179        Ok(NextChunk::Byte(c))
1180    }
1181}
1182
1183// https://www.w3.org/TR/REC-xml/#AVNormalize
1184fn normalize_attribute<'input>(
1185    text: StrSpan<'input>,
1186    ctx: &mut Context<'input>,
1187) -> Result<StringStorage<'input>> {
1188    // We assume that `&` indicates an entity or a character reference.
1189    // But in rare cases it can be just an another character.
1190    if memchr2(b'&', b'\t', text.as_str().as_bytes()).is_some() || memchr2(b'\n', b'\r', text.as_str().as_bytes()).is_some() {
1191        let mut text_buffer = TextBuffer::new();
1192        _normalize_attribute(text, &mut text_buffer, ctx)?;
1193        Ok(StringStorage::new_owned(&text_buffer.finish()))
1194    } else {
1195        Ok(StringStorage::Borrowed(text.as_str()))
1196    }
1197}
1198
1199fn _normalize_attribute(text: StrSpan, buffer: &mut TextBuffer, ctx: &mut Context) -> Result<()> {
1200    let mut stream = Stream::from_substr(ctx.doc.text, text.range());
1201    while !stream.at_end() {
1202        // Safe, because we already checked that the stream is not at the end.
1203        let c = stream.curr_byte_unchecked();
1204
1205        if c != b'&' {
1206            stream.advance(1);
1207            buffer.push_from_attr(c, stream.curr_byte().ok());
1208            continue;
1209        }
1210
1211        // Check for character/entity references.
1212        let start = stream.pos();
1213        match stream.consume_reference() {
1214            Some(Reference::Char(ch)) => {
1215                for b in CharToBytes::new(ch) {
1216                    if ctx.loop_detector.depth > 0 {
1217                        // Escaped `<` inside an ENTITY is an error.
1218                        // Escaped `<` outside an ENTITY is ok.
1219                        if b == b'<' {
1220                            return Err(Error::InvalidAttributeValue(
1221                                stream.gen_text_pos_from(start),
1222                            ));
1223                        }
1224
1225                        buffer.push_from_attr(b, None);
1226                    } else {
1227                        // Characters not from entity should be added as is.
1228                        // Not sure why... At least `lxml` produces the same results.
1229                        buffer.push_raw(b);
1230                    }
1231                }
1232            }
1233            Some(Reference::Entity(name)) => match ctx.entities.iter().find(|e| e.name == name) {
1234                Some(entity) => {
1235                    ctx.loop_detector.inc_references(&stream)?;
1236                    ctx.loop_detector.inc_depth(&stream)?;
1237                    _normalize_attribute(entity.value, buffer, ctx)?;
1238                    ctx.loop_detector.dec_depth();
1239                }
1240                None => {
1241                    let pos = stream.gen_text_pos_from(start);
1242                    return Err(Error::UnknownEntityReference(name.into(), pos));
1243                }
1244            },
1245            None => {
1246                let pos = stream.gen_text_pos_from(start);
1247                return Err(Error::MalformedEntityReference(pos));
1248            }
1249        }
1250    }
1251
1252    Ok(())
1253}
1254
1255fn get_ns_idx_by_prefix(
1256    namespaces: ShortRange,
1257    prefix_pos: usize,
1258    prefix: &str,
1259    doc: &Document<'_>,
1260) -> Result<Option<NamespaceIdx>> {
1261    // Prefix CAN be empty when the default namespace was defined.
1262    //
1263    // Example:
1264    // <e xmlns='http://www.w3.org'/>
1265    let prefix_opt = if prefix.is_empty() {
1266        None
1267    } else {
1268        Some(prefix)
1269    };
1270
1271    let idx = doc.namespaces.tree_order[namespaces.to_urange()]
1272        .iter()
1273        .find(|idx| doc.namespaces.get(**idx).name == prefix_opt);
1274
1275    match idx {
1276        Some(idx) => Ok(Some(*idx)),
1277        None => {
1278            if !prefix.is_empty() {
1279                // If an URI was not found and prefix IS NOT empty than
1280                // we have an unknown namespace.
1281                //
1282                // Example:
1283                // <e random:a='b'/>
1284                let pos = doc.text_pos_at(prefix_pos);
1285                Err(Error::UnknownNamespace(prefix.to_string(), pos))
1286            } else {
1287                // If an URI was not found and prefix IS empty than
1288                // an element or an attribute doesn't have a namespace.
1289                //
1290                // Example:
1291                // <e a='b'/>
1292                Ok(None)
1293            }
1294        }
1295    }
1296}
1297
1298fn gen_qname_string(prefix: &str, local: &str) -> String {
1299    if prefix.is_empty() {
1300        local.to_string()
1301    } else {
1302        alloc::format!("{}:{}", prefix, local)
1303    }
1304}
1305
1306/// Iterate over `char` by `u8`.
1307struct CharToBytes {
1308    buf: [u8; 4],
1309    idx: u8,
1310}
1311
1312impl CharToBytes {
1313    #[inline]
1314    fn new(c: char) -> Self {
1315        let mut buf = [0xFF; 4];
1316        c.encode_utf8(&mut buf);
1317
1318        CharToBytes { buf, idx: 0 }
1319    }
1320}
1321
1322impl Iterator for CharToBytes {
1323    type Item = u8;
1324
1325    #[inline]
1326    fn next(&mut self) -> Option<Self::Item> {
1327        if self.idx < 4 {
1328            let b = self.buf[self.idx as usize];
1329
1330            if b != 0xFF {
1331                self.idx += 1;
1332                return Some(b);
1333            } else {
1334                self.idx = 4;
1335            }
1336        }
1337
1338        None
1339    }
1340}
1341
1342struct TextBuffer {
1343    buffer: Vec<u8>,
1344}
1345
1346impl TextBuffer {
1347    #[inline]
1348    fn new() -> Self {
1349        TextBuffer {
1350            buffer: Vec::with_capacity(32),
1351        }
1352    }
1353
1354    #[inline]
1355    fn push_raw(&mut self, c: u8) {
1356        self.buffer.push(c);
1357    }
1358
1359    fn push_from_attr(&mut self, mut current: u8, next: Option<u8>) {
1360        // \r in \r\n should be ignored.
1361        if current == b'\r' && next == Some(b'\n') {
1362            return;
1363        }
1364
1365        // \n, \r and \t should be converted into spaces.
1366        current = match current {
1367            b'\n' | b'\r' | b'\t' => b' ',
1368            _ => current,
1369        };
1370
1371        self.buffer.push(current);
1372    }
1373
1374    // Translate \r\n and any \r that is not followed by \n into a single \n character.
1375    //
1376    // https://www.w3.org/TR/xml/#sec-line-ends
1377    fn push_from_text(&mut self, c: u8, at_end: bool) {
1378        if self.buffer.last() == Some(&b'\r') {
1379            let idx = self.buffer.len() - 1;
1380            self.buffer[idx] = b'\n';
1381
1382            if at_end && c == b'\r' {
1383                self.buffer.push(b'\n');
1384            } else if c != b'\n' {
1385                self.buffer.push(c);
1386            }
1387        } else if at_end && c == b'\r' {
1388            self.buffer.push(b'\n');
1389        } else {
1390            self.buffer.push(c);
1391        }
1392    }
1393
1394    #[inline]
1395    fn clear(&mut self) {
1396        self.buffer.clear();
1397    }
1398
1399    #[inline]
1400    fn is_empty(&self) -> bool {
1401        self.buffer.is_empty()
1402    }
1403
1404    #[inline]
1405    fn finish(&mut self) -> String {
1406        // `unwrap` is safe, because buffer must contain a valid UTF-8 string.
1407        String::from_utf8(take(&mut self.buffer)).unwrap()
1408    }
1409}
roxmltree/parse.rs

roxmltree/
parse.rs
