roxmltree/
tokenizer.rs

1use core::ops::Range;
2use core::str;
3use alloc::string::String;
4
5use memchr::memchr2;
6
7use crate::{Error, TextPos};
8
9type Result<T> = core::result::Result<T, Error>;
10
11/// Extension methods for XML-subset only operations.
12trait XmlCharExt {
13    /// Checks if the value is within the
14    /// [NameStartChar](https://www.w3.org/TR/xml/#NT-NameStartChar) range.
15    fn is_xml_name_start(&self) -> bool;
16
17    /// Checks if the value is within the
18    /// [NameChar](https://www.w3.org/TR/xml/#NT-NameChar) range.
19    fn is_xml_name(&self) -> bool;
20
21    /// Checks if the value is within the
22    /// [Char](https://www.w3.org/TR/xml/#NT-Char) range.
23    fn is_xml_char(&self) -> bool;
24}
25
26impl XmlCharExt for char {
27    #[inline]
28    fn is_xml_name_start(&self) -> bool {
29        // Check for ASCII first.
30        if *self as u32 <= 128 {
31            return (*self as u8).is_xml_name_start();
32        }
33
34        matches!(*self as u32,
35            0x0000C0..=0x0000D6
36            | 0x0000D8..=0x0000F6
37            | 0x0000F8..=0x0002FF
38            | 0x000370..=0x00037D
39            | 0x00037F..=0x001FFF
40            | 0x00200C..=0x00200D
41            | 0x002070..=0x00218F
42            | 0x002C00..=0x002FEF
43            | 0x003001..=0x00D7FF
44            | 0x00F900..=0x00FDCF
45            | 0x00FDF0..=0x00FFFD
46            | 0x010000..=0x0EFFFF)
47    }
48
49    #[inline]
50    fn is_xml_name(&self) -> bool {
51        // Check for ASCII first.
52        if *self as u32 <= 128 {
53            return (*self as u8).is_xml_name();
54        }
55
56        matches!(*self as u32, 0x0000B7
57                | 0x0000C0..=0x0000D6
58                | 0x0000D8..=0x0000F6
59                | 0x0000F8..=0x0002FF
60                | 0x000300..=0x00036F
61                | 0x000370..=0x00037D
62                | 0x00037F..=0x001FFF
63                | 0x00200C..=0x00200D
64                | 0x00203F..=0x002040
65                | 0x002070..=0x00218F
66                | 0x002C00..=0x002FEF
67                | 0x003001..=0x00D7FF
68                | 0x00F900..=0x00FDCF
69                | 0x00FDF0..=0x00FFFD
70                | 0x010000..=0x0EFFFF)
71    }
72
73    #[inline]
74    fn is_xml_char(&self) -> bool {
75        // Does not check for surrogate code points U+D800-U+DFFF,
76        // since that check was performed by Rust when the `&str` was constructed.
77        if (*self as u32) < 0x20 {
78            return (*self as u8).is_xml_space();
79        }
80
81        !matches!(*self as u32, 0xFFFF | 0xFFFE)
82    }
83}
84
85trait XmlByteExt {
86    /// Checks if byte is a space.
87    ///
88    /// `[ \r\n\t]`
89    fn is_xml_space(&self) -> bool;
90
91    /// Checks if the value is within the
92    /// [NameStartChar](https://www.w3.org/TR/xml/#NT-NameStartChar) range.
93    fn is_xml_name_start(&self) -> bool;
94
95    /// Checks if byte is within the ASCII
96    /// [Char](https://www.w3.org/TR/xml/#NT-Char) range.
97    fn is_xml_name(&self) -> bool;
98
99    /// Checks if the value is within the
100    /// [Char](https://www.w3.org/TR/xml/#NT-Char) range.
101    fn is_xml_char(&self) -> bool;
102}
103
104impl XmlByteExt for u8 {
105    #[inline]
106    fn is_xml_space(&self) -> bool {
107        matches!(*self, b' ' | b'\t' | b'\n' | b'\r')
108    }
109
110    #[inline]
111    fn is_xml_name_start(&self) -> bool {
112        matches!(*self, b'A'..=b'Z' | b'a'..=b'z' | b':' | b'_')
113    }
114
115    #[inline]
116    fn is_xml_name(&self) -> bool {
117        matches!(*self, b'A'..=b'Z' | b'a'..=b'z'| b'0'..=b'9'| b':' | b'_' | b'-' | b'.')
118    }
119
120    #[inline]
121    fn is_xml_char(&self) -> bool {
122        *self > 0x20 || self.is_xml_space()
123    }
124}
125
126#[inline]
127fn is_xml_str(s: &str, value_start: usize, stream: &mut Stream<'_>) -> Result<()> {
128    if s.as_bytes().is_ascii() {
129        for (i, b) in s.as_bytes().iter().enumerate() {
130            if !b.is_xml_char() {
131                return Err(Error::NonXmlChar(*b as char, stream.gen_text_pos_from(value_start + i)));
132            }
133        }
134
135        Ok(())
136    } else {
137        is_xml_str_unicode(s, value_start, stream)
138    }
139}
140
141
142#[cold]
143#[inline(never)]
144fn is_xml_str_unicode(s: &str, value_start: usize, stream: &mut Stream<'_>) -> Result<()> {
145    for (i, ch) in s.char_indices() {
146        if !ch.is_xml_char() {
147            return Err(Error::NonXmlChar(ch, stream.gen_text_pos_from(value_start + i)));
148        }
149    }
150
151    Ok(())
152}
153
154/// A string slice.
155///
156/// Like `&str`, but also contains the position in the input XML
157/// from which it was parsed.
158#[must_use]
159#[derive(Clone, Copy)]
160pub struct StrSpan<'input> {
161    text: &'input str,
162    start: usize,
163}
164
165impl<'input> From<&'input str> for StrSpan<'input> {
166    #[inline]
167    fn from(text: &'input str) -> Self {
168        StrSpan { text, start: 0 }
169    }
170}
171
172impl<'input> StrSpan<'input> {
173    #[inline]
174    pub fn from_substr(text: &'input str, start: usize, end: usize) -> Self {
175        debug_assert!(start <= end);
176        StrSpan {
177            text: &text[start..end],
178            start,
179        }
180    }
181
182    #[inline]
183    pub fn range(&self) -> Range<usize> {
184        self.start..(self.start + self.text.len())
185    }
186
187    #[inline]
188    pub fn as_str(&self) -> &'input str {
189        self.text
190    }
191
192    #[inline]
193    fn slice_region(&self, start: usize, end: usize) -> &'input str {
194        &self.text[start..end]
195    }
196}
197
198pub enum Token<'input> {
199    // <?target content?>
200    ProcessingInstruction(&'input str, Option<&'input str>, Range<usize>),
201
202    // <!-- text -->
203    Comment(&'input str, Range<usize>),
204
205    // <!ENTITY ns_extend "http://test.com">
206    EntityDeclaration(&'input str, StrSpan<'input>),
207
208    // <ns:elem
209    ElementStart(&'input str, &'input str, usize),
210
211    // ns:attr="value"
212    Attribute(Range<usize>, u16, u8, &'input str, &'input str, StrSpan<'input>),
213
214    ElementEnd(ElementEnd<'input>, Range<usize>),
215
216    // Contains text between elements including whitespaces.
217    // Basically everything between `>` and `<`.
218    // Except `]]>`, which is not allowed and will lead to an error.
219    Text(&'input str, Range<usize>),
220
221    // <![CDATA[text]]>
222    Cdata(&'input str, Range<usize>),
223}
224
225/// `ElementEnd` token.
226#[derive(Clone, Copy)]
227pub enum ElementEnd<'input> {
228    /// Indicates `>`
229    Open,
230    /// Indicates `</ns:name>`
231    Close(&'input str, &'input str),
232    /// Indicates `/>`
233    Empty,
234}
235
236pub trait XmlEvents<'input> {
237    fn token(&mut self, token: Token<'input>) -> Result<()>;
238
239    fn resolve_entity(&mut self, _pub_id: Option<&str>, _uri: &str) -> core::result::Result<Option<&'input str>, String> { Ok(None) }
240}
241
242// document ::= prolog element Misc*
243pub fn parse<'input>(
244    text: &'input str,
245    allow_dtd: bool,
246    events: &mut impl XmlEvents<'input>,
247) -> Result<()> {
248    let s = &mut Stream::new(text);
249
250    parse_declaration(s)?;
251
252    parse_misc(s, events)?;
253
254    s.skip_spaces();
255    if s.starts_with(b"<!DOCTYPE") {
256        if !allow_dtd {
257            return Err(Error::DtdDetected);
258        }
259
260        parse_doctype(s, events)?;
261        parse_misc(s, events)?;
262    }
263
264    s.skip_spaces();
265    if s.curr_byte().ok() == Some(b'<') && parse_start_tag(s, events)? {
266        parse_content(s, events)?;
267    }
268
269    parse_misc(s, events)?;
270
271    if !s.at_end() {
272        return Err(Error::UnknownToken(s.gen_text_pos()));
273    }
274
275    Ok(())
276}
277
278// Misc ::= Comment | PI | S
279fn parse_misc<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<()> {
280    while !s.at_end() {
281        s.skip_spaces();
282        if s.starts_with(b"<!--") {
283            parse_comment(s, events)?;
284        } else if s.starts_with(b"<?") {
285            parse_pi(s, events)?;
286        } else {
287            break;
288        }
289    }
290
291    Ok(())
292}
293
294// XMLDecl ::= '<?xml' VersionInfo EncodingDecl? SDDecl? S? '?>'
295//
296// We don't actually return a token for the XML declaration and only validate it.
297fn parse_declaration(s: &mut Stream) -> Result<()> {
298    // Skip UTF-8 BOM.
299    if s.starts_with(&[0xEF, 0xBB, 0xBF]) {
300        s.advance(3);
301    }
302
303    if !s.starts_with(b"<?xml ") {
304        return Ok(())
305    }
306
307    fn consume_spaces(s: &mut Stream) -> Result<()> {
308        if s.starts_with_space() {
309            s.skip_spaces();
310        } else if !s.starts_with(b"?>") && !s.at_end() {
311            return Err(Error::InvalidChar2(
312                "a whitespace",
313                s.curr_byte_unchecked(),
314                s.gen_text_pos(),
315            ));
316        }
317
318        Ok(())
319    }
320
321    s.advance(5); // <?xml
322    consume_spaces(s)?;
323
324    // The `version` "attribute" is mandatory.
325    if !s.starts_with(b"version") {
326        // Will trigger the InvalidString error, which is what we want.
327        return s.skip_string(b"version");
328    }
329    let _ = parse_attribute(s)?;
330    consume_spaces(s)?;
331
332    if s.starts_with(b"encoding") {
333        let _ = parse_attribute(s)?;
334        consume_spaces(s)?;
335    }
336
337    if s.starts_with(b"standalone") {
338        let _ = parse_attribute(s)?;
339    }
340
341    s.skip_spaces();
342    s.skip_string(b"?>")?;
343
344    Ok(())
345}
346
347// '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'
348fn parse_comment<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<()> {
349    let start = s.pos();
350    s.advance(4);
351    let text = s.consume_chars(|s, c| !(c == '-' && s.starts_with(b"-->")))?;
352    s.skip_string(b"-->")?;
353
354    if text.contains("--") {
355        return Err(Error::InvalidComment(s.gen_text_pos_from(start)));
356    }
357
358    if text.ends_with('-') {
359        return Err(Error::InvalidComment(s.gen_text_pos_from(start)));
360    }
361
362    let range = s.range_from(start);
363    events.token(Token::Comment(text, range))?;
364
365    Ok(())
366}
367
368// PI       ::= '<?' PITarget (S (Char* - (Char* '?>' Char*)))? '?>'
369// PITarget ::= Name - (('X' | 'x') ('M' | 'm') ('L' | 'l'))
370fn parse_pi<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<()> {
371    if s.starts_with(b"<?xml ") {
372        return Err(Error::UnexpectedDeclaration(s.gen_text_pos()));
373    }
374
375    let start = s.pos();
376    s.advance(2);
377    let target = s.consume_name()?;
378    s.skip_spaces();
379    let content = s.consume_chars(|s, c| !(c == '?' && s.starts_with(b"?>")))?;
380    let content = if !content.is_empty() {
381        Some(content)
382    } else {
383        None
384    };
385
386    s.skip_string(b"?>")?;
387
388    let range = s.range_from(start);
389    events.token(Token::ProcessingInstruction(target, content, range))?;
390    Ok(())
391}
392
393fn parse_doctype<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<()> {
394    let start = s.pos();
395    parse_doctype_start(s)?;
396    s.skip_spaces();
397
398    if s.curr_byte() == Ok(b'>') {
399        s.advance(1);
400        return Ok(());
401    }
402
403    s.advance(1); // [
404    while !s.at_end() {
405        s.skip_spaces();
406        if s.starts_with(b"<!ENTITY") {
407            parse_entity_decl(s, events)?;
408        } else if s.starts_with(b"<!--") {
409            parse_comment(s, events)?;
410        } else if s.starts_with(b"<?") {
411            parse_pi(s, events)?;
412        } else if s.starts_with(b"]") {
413            // DTD ends with ']' S? '>', therefore we have to skip possible spaces.
414            s.advance(1);
415            s.skip_spaces();
416            match s.curr_byte() {
417                Ok(b'>') => {
418                    s.advance(1);
419                    break;
420                }
421                Ok(c) => {
422                    return Err(Error::InvalidChar2("'>'", c, s.gen_text_pos()));
423                }
424                Err(_) => {
425                    return Err(Error::UnexpectedEndOfStream);
426                }
427            }
428        } else if s.starts_with(b"<!ELEMENT")
429            || s.starts_with(b"<!ATTLIST")
430            || s.starts_with(b"<!NOTATION")
431        {
432            if consume_decl(s).is_err() {
433                let pos = s.gen_text_pos_from(start);
434                return Err(Error::UnknownToken(pos));
435            }
436        } else {
437            return Err(Error::UnknownToken(s.gen_text_pos()));
438        }
439    }
440
441    Ok(())
442}
443
444// doctypedecl ::= '<!DOCTYPE' S Name (S ExternalID)? S? ('[' intSubset ']' S?)? '>'
445fn parse_doctype_start(s: &mut Stream) -> Result<()> {
446    s.advance(9);
447
448    s.consume_spaces()?;
449    s.skip_name()?;
450    s.skip_spaces();
451
452    let _ = parse_external_id(s)?;
453    s.skip_spaces();
454
455    let c = s.curr_byte()?;
456    if c != b'[' && c != b'>' {
457        return Err(Error::InvalidChar2("'[' or '>'", c, s.gen_text_pos()));
458    }
459
460    Ok(())
461}
462
463// ExternalID ::= 'SYSTEM' S SystemLiteral | 'PUBLIC' S PubidLiteral S SystemLiteral
464fn parse_external_id<'input>(s: &mut Stream<'input>) -> Result<Option<(Option<&'input str>, &'input str)>> {
465    let v = if s.starts_with(b"SYSTEM") || s.starts_with(b"PUBLIC") {
466        let start = s.pos();
467        s.advance(6);
468        let id = s.slice_back(start);
469
470        s.consume_spaces()?;
471        let quote = s.consume_quote()?;
472        let first = s.consume_bytes(|c| c != quote);
473        s.consume_byte(quote)?;
474
475        if id == "SYSTEM" {
476            Some((None, first))
477        } else {
478            s.consume_spaces()?;
479            let quote = s.consume_quote()?;
480            let second = s.consume_bytes(|c| c != quote);
481            s.consume_byte(quote)?;
482
483            Some((Some(first), second))
484        }
485    } else {
486        None
487    };
488
489    Ok(v)
490}
491
492// EntityDecl  ::= GEDecl | PEDecl
493// GEDecl      ::= '<!ENTITY' S Name S EntityDef S? '>'
494// PEDecl      ::= '<!ENTITY' S '%' S Name S PEDef S? '>'
495fn parse_entity_decl<'input>(
496    s: &mut Stream<'input>,
497    events: &mut impl XmlEvents<'input>,
498) -> Result<()> {
499    s.advance(8);
500    s.consume_spaces()?;
501
502    let is_ge = if s.try_consume_byte(b'%') {
503        s.consume_spaces()?;
504        false
505    } else {
506        true
507    };
508
509    let name = s.consume_name()?;
510    s.consume_spaces()?;
511    if let Some(definition) = parse_entity_def(s, events, is_ge)? {
512        events.token(Token::EntityDeclaration(name, definition))?;
513    }
514    s.skip_spaces();
515    s.consume_byte(b'>')?;
516
517    Ok(())
518}
519
520// EntityDef   ::= EntityValue | (ExternalID NDataDecl?)
521// PEDef       ::= EntityValue | ExternalID
522// EntityValue ::= '"' ([^%&"] | PEReference | Reference)* '"' |  "'" ([^%&']
523//                             | PEReference | Reference)* "'"
524// ExternalID  ::= 'SYSTEM' S SystemLiteral | 'PUBLIC' S PubidLiteral S SystemLiteral
525// NDataDecl   ::= S 'NDATA' S Name
526fn parse_entity_def<'input>(
527    s: &mut Stream<'input>,
528    events: &mut impl XmlEvents<'input>,
529    is_ge: bool,
530) -> Result<Option<StrSpan<'input>>> {
531    let c = s.curr_byte()?;
532    match c {
533        b'"' | b'\'' => {
534            let quote = s.consume_quote()?;
535            let start = s.pos();
536            s.skip_bytes(|c| c != quote);
537            let value = s.slice_back_span(start);
538            s.consume_byte(quote)?;
539            Ok(Some(value))
540        }
541        b'S' | b'P' => {
542            if let Some((pub_id, uri)) = parse_external_id(s)? {
543                if is_ge {
544                    s.skip_spaces();
545                    if s.starts_with(b"NDATA") {
546                        s.advance(5);
547                        s.consume_spaces()?;
548                        s.skip_name()?;
549                        // TODO: NDataDecl is not supported
550                    }
551                }
552
553                let value = events.resolve_entity(pub_id, uri).map_err(|msg| Error::EntityResolver(s.gen_text_pos(), msg))?;
554
555                match value {
556                    Some(value) => {
557                        let mut stream = Stream::new(value);
558                        parse_declaration(&mut stream)?;
559                        let value = StrSpan::from(&value[stream.pos..]);
560
561                        Ok(Some(value))
562                    }
563                    None => Ok(None),
564                }
565            } else {
566                Err(Error::InvalidExternalID(s.gen_text_pos()))
567            }
568        }
569        _ => {
570            let pos = s.gen_text_pos();
571            Err(Error::InvalidChar2("a quote, SYSTEM or PUBLIC", c, pos))
572        }
573    }
574}
575
576fn consume_decl(s: &mut Stream) -> Result<()> {
577    s.skip_bytes(|c| c != b'>');
578    s.consume_byte(b'>')?;
579    Ok(())
580}
581
582// EmptyElemTag ::= '<' Name (S Attribute)* S? '/>'
583// STag         ::= '<' Name (S Attribute)* S? '>'
584//
585// Returns `true` for a start tag, i.e. when the element's content still has to be parsed.
586fn parse_start_tag<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<bool> {
587    let start = s.pos();
588    s.advance(1); // <
589    let (prefix, local) = s.consume_qname()?;
590    events.token(Token::ElementStart(prefix, local, start))?;
591
592    let mut open = false;
593    while !s.at_end() {
594        let has_space = s.starts_with_space();
595        s.skip_spaces();
596        let start = s.pos();
597        match s.curr_byte()? {
598            b'/' => {
599                s.advance(1);
600                s.consume_byte(b'>')?;
601                let range = s.range_from(start);
602                events.token(Token::ElementEnd(ElementEnd::Empty, range))?;
603                break;
604            }
605            b'>' => {
606                s.advance(1);
607                let range = s.range_from(start);
608                events.token(Token::ElementEnd(ElementEnd::Open, range))?;
609                open = true;
610                break;
611            }
612            _ => {
613                // An attribute must be preceded with a whitespace.
614                if !has_space {
615                    // Will always trigger an error. Which is what we want.
616                    s.consume_spaces()?;
617                }
618
619                // Manual inlining of `parse_attribute` for performance.
620                // We cannot mark `parse_attribute` as `#[inline(always)]`
621                // because it will blow up the binary size.
622                let (prefix, local) = s.consume_qname()?;
623                let qname_end = s.pos();
624                let qname_len = u16::try_from(qname_end - start).unwrap_or(u16::MAX);
625                s.consume_eq()?;
626                let eq_len = u8::try_from(s.pos() - qname_end).unwrap_or(u8::MAX);
627                let quote = s.consume_quote()?;
628                // The attribute value must not contain the < character.
629                let value_start = s.pos();
630                s.advance_until2(quote, b'<')?;
631                let value = s.slice_back_span(value_start);
632                is_xml_str(value.as_str(), value_start, s)?;
633                s.consume_byte(quote)?;
634                let end = s.pos();
635                events.token(Token::Attribute(start..end, qname_len, eq_len, prefix, local, value))?;
636            }
637        }
638    }
639
640    Ok(open)
641}
642
643// Attribute ::= Name Eq AttValue
644fn parse_attribute<'input>(
645    s: &mut Stream<'input>,
646) -> Result<(&'input str, &'input str, StrSpan<'input>)> {
647    let (prefix, local) = s.consume_qname()?;
648    s.consume_eq()?;
649    let quote = s.consume_quote()?;
650    let quote_c = quote as char;
651    // The attribute value must not contain the < character.
652    let value_start = s.pos();
653    s.skip_chars(|_, c| c != quote_c && c != '<')?;
654    let value = s.slice_back_span(value_start);
655    s.consume_byte(quote)?;
656    Ok((prefix, local, value))
657}
658
659// content ::= CharData? ((element | Reference | CDSect | PI | Comment) CharData?)*
660// element ::= EmptyElemTag | STag content ETag
661//
662// Nested elements are parsed iteratively, tracking the depth explicitly
663// instead of recursing, so deeply nested documents cannot overflow the stack.
664// An end tag at depth 0 closes the caller's element and ends this call.
665pub fn parse_content<'input>(
666    s: &mut Stream<'input>,
667    events: &mut impl XmlEvents<'input>,
668) -> Result<()> {
669    let mut depth: u32 = 0;
670
671    while !s.at_end() {
672        match s.curr_byte() {
673            Ok(b'<') => match s.next_byte() {
674                Ok(b'!') => {
675                    if s.starts_with(b"<!--") {
676                        parse_comment(s, events)?;
677                    } else if s.starts_with(b"<![CDATA[") {
678                        parse_cdata(s, events)?;
679                    } else {
680                        return Err(Error::UnknownToken(s.gen_text_pos()));
681                    }
682                }
683                Ok(b'?') => parse_pi(s, events)?,
684                Ok(b'/') => {
685                    parse_close_element(s, events)?;
686                    if depth == 0 {
687                        break;
688                    }
689                    depth -= 1;
690                }
691                Ok(_) => {
692                    if parse_start_tag(s, events)? {
693                        depth = depth.checked_add(1).ok_or(Error::NodesLimitReached)?;
694                    }
695                }
696                Err(_) => return Err(Error::UnknownToken(s.gen_text_pos())),
697            },
698            Ok(_) => parse_text(s, events)?,
699            Err(_) => return Err(Error::UnknownToken(s.gen_text_pos())),
700        }
701    }
702
703    Ok(())
704}
705
706// CDSect  ::= CDStart CData CDEnd
707// CDStart ::= '<![CDATA['
708// CData   ::= (Char* - (Char* ']]>' Char*))
709// CDEnd   ::= ']]>'
710fn parse_cdata<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<()> {
711    let start = s.pos();
712    s.advance(9); // <![CDATA[
713    let text = s.consume_chars(|s, c| !(c == ']' && s.starts_with(b"]]>")))?;
714    s.skip_string(b"]]>")?;
715    let range = s.range_from(start);
716    events.token(Token::Cdata(text, range))?;
717    Ok(())
718}
719
720// '</' Name S? '>'
721fn parse_close_element<'input>(
722    s: &mut Stream<'input>,
723    events: &mut impl XmlEvents<'input>,
724) -> Result<()> {
725    let start = s.pos();
726    s.advance(2); // </
727
728    let (prefix, tag_name) = s.consume_qname()?;
729    s.skip_spaces();
730    s.consume_byte(b'>')?;
731
732    let range = s.range_from(start);
733    events.token(Token::ElementEnd(
734        ElementEnd::Close(prefix, tag_name),
735        range,
736    ))?;
737    Ok(())
738}
739
740fn parse_text<'input>(s: &mut Stream<'input>, events: &mut impl XmlEvents<'input>) -> Result<()> {
741    let start = s.pos();
742    let text = s.consume_chars(|_, c| c != '<')?;
743
744    // According to the spec, `]]>` must not appear inside a Text node.
745    // https://www.w3.org/TR/xml/#syntax
746    //
747    // Search for `>` first, since it's a bit faster than looking for `]]>`.
748    if text.contains('>') && text.contains("]]>") {
749        return Err(Error::InvalidCharacterData(s.gen_text_pos()));
750    }
751
752    let range = s.range_from(start);
753    events.token(Token::Text(text, range))?;
754    Ok(())
755}
756
757/// Representation of the [Reference](https://www.w3.org/TR/xml/#NT-Reference) value.
758#[derive(Clone, Copy)]
759pub enum Reference<'input> {
760    /// An entity reference.
761    ///
762    /// <https://www.w3.org/TR/xml/#NT-EntityRef>
763    Entity(&'input str),
764
765    /// A character reference.
766    ///
767    /// <https://www.w3.org/TR/xml/#NT-CharRef>
768    Char(char),
769}
770
771#[derive(Clone)]
772pub struct Stream<'input> {
773    pos: usize,
774    end: usize,
775    span: StrSpan<'input>,
776}
777
778impl<'input> Stream<'input> {
779    #[inline]
780    pub fn new(text: &'input str) -> Self {
781        Stream {
782            pos: 0,
783            end: text.len(),
784            span: text.into(),
785        }
786    }
787
788    #[inline]
789    pub fn from_substr(text: &'input str, fragment: Range<usize>) -> Self {
790        Stream {
791            pos: fragment.start,
792            end: fragment.end,
793            span: text.into(),
794        }
795    }
796
797    #[inline]
798    pub fn pos(&self) -> usize {
799        self.pos
800    }
801
802    #[inline]
803    pub fn at_end(&self) -> bool {
804        self.pos >= self.end
805    }
806
807    #[inline]
808    pub fn curr_byte(&self) -> Result<u8> {
809        if self.at_end() {
810            return Err(Error::UnexpectedEndOfStream);
811        }
812
813        Ok(self.curr_byte_unchecked())
814    }
815
816    #[inline]
817    pub fn curr_byte_unchecked(&self) -> u8 {
818        self.span.text.as_bytes()[self.pos]
819    }
820
821    #[inline]
822    fn next_byte(&self) -> Result<u8> {
823        if self.pos + 1 >= self.end {
824            return Err(Error::UnexpectedEndOfStream);
825        }
826
827        Ok(self.span.as_str().as_bytes()[self.pos + 1])
828    }
829
830    #[inline]
831    fn as_bytes(&self) -> &[u8] {
832        &self.span.text.as_bytes()[self.pos..self.end]
833    }
834
835    #[inline]
836    pub fn advance(&mut self, n: usize) {
837        debug_assert!(self.pos + n <= self.end);
838        self.pos += n;
839    }
840
841    #[inline]
842    fn starts_with(&self, text: &[u8]) -> bool {
843        self.span.text.as_bytes()[self.pos..self.end].starts_with(text)
844    }
845
846    fn consume_byte(&mut self, c: u8) -> Result<()> {
847        let curr = self.curr_byte()?;
848        if curr != c {
849            return Err(Error::InvalidChar(c, curr, self.gen_text_pos()));
850        }
851
852        self.advance(1);
853        Ok(())
854    }
855
856    // Unlike `consume_byte()` will not return any errors.
857    fn try_consume_byte(&mut self, c: u8) -> bool {
858        match self.curr_byte() {
859            Ok(b) if b == c => {
860                self.advance(1);
861                true
862            }
863            _ => false,
864        }
865    }
866
867    fn skip_string(&mut self, text: &'static [u8]) -> Result<()> {
868        if !self.starts_with(text) {
869            let pos = self.gen_text_pos();
870
871            // Assume that all input `text` are valid UTF-8 strings, so unwrap is safe.
872            let expected = str::from_utf8(text).unwrap();
873
874            return Err(Error::InvalidString(expected, pos));
875        }
876
877        self.advance(text.len());
878        Ok(())
879    }
880
881    #[inline]
882    fn consume_bytes<F: Fn(u8) -> bool>(&mut self, f: F) -> &'input str {
883        let start = self.pos;
884        self.skip_bytes(f);
885        self.slice_back(start)
886    }
887
888    fn skip_bytes<F: Fn(u8) -> bool>(&mut self, f: F) {
889        while !self.at_end() && f(self.curr_byte_unchecked()) {
890            self.advance(1);
891        }
892    }
893
894    #[inline]
895    fn consume_chars<F>(&mut self, f: F) -> Result<&'input str>
896    where
897        F: Fn(&Stream, char) -> bool,
898    {
899        let start = self.pos;
900        self.skip_chars(f)?;
901        Ok(self.slice_back(start))
902    }
903
904    #[inline]
905    fn skip_chars<F>(&mut self, f: F) -> Result<()>
906    where
907        F: Fn(&Stream, char) -> bool,
908    {
909        for c in self.chars() {
910            if !c.is_xml_char() {
911                return Err(Error::NonXmlChar(c, self.gen_text_pos()));
912            } else if f(self, c) {
913                self.advance(c.len_utf8());
914            } else {
915                break;
916            }
917        }
918
919        Ok(())
920    }
921
922    #[inline]
923    fn advance_until2(&mut self, needle1: u8, needle2: u8) -> Result<()> {
924        match memchr2(needle1, needle2, self.as_bytes()) {
925            Some(pos) => {
926                self.advance(pos);
927                Ok(())
928            }
929            None => Err(Error::UnexpectedEndOfStream),
930        }
931    }
932
933    #[inline]
934    fn chars(&self) -> str::Chars<'input> {
935        self.span.as_str()[self.pos..self.end].chars()
936    }
937
938    #[inline]
939    fn slice_back(&self, pos: usize) -> &'input str {
940        self.span.slice_region(pos, self.pos)
941    }
942
943    #[inline]
944    fn slice_back_span(&self, pos: usize) -> StrSpan<'input> {
945        StrSpan::from_substr(self.span.text, pos, self.pos)
946    }
947
948    #[inline]
949    fn range_from(&self, start: usize) -> Range<usize> {
950        start..self.pos
951    }
952
953    #[inline]
954    fn skip_spaces(&mut self) {
955        while self.starts_with_space() {
956            self.advance(1);
957        }
958    }
959
960    #[inline]
961    fn starts_with_space(&self) -> bool {
962        !self.at_end() && self.curr_byte_unchecked().is_xml_space()
963    }
964
965    // Like `skip_spaces()`, but checks that first char is actually a space.
966    fn consume_spaces(&mut self) -> Result<()> {
967        if self.at_end() {
968            return Err(Error::UnexpectedEndOfStream);
969        }
970
971        if !self.starts_with_space() {
972            return Err(Error::InvalidChar2(
973                "a whitespace",
974                self.curr_byte_unchecked(),
975                self.gen_text_pos(),
976            ));
977        }
978
979        self.skip_spaces();
980        Ok(())
981    }
982
983    /// Consumes according to: <https://www.w3.org/TR/xml/#NT-Reference>
984    #[inline(never)]
985    pub fn consume_reference(&mut self) -> Option<Reference<'input>> {
986        if !self.try_consume_byte(b'&') {
987            return None;
988        }
989
990        let reference = if self.try_consume_byte(b'#') {
991            let (value, radix) = if self.try_consume_byte(b'x') {
992                let value =
993                    self.consume_bytes(|c| c.is_ascii_hexdigit());
994                (value, 16)
995            } else {
996                let value = self.consume_bytes(|c| c.is_ascii_digit());
997                (value, 10)
998            };
999
1000            let n = u32::from_str_radix(value, radix).ok()?;
1001
1002            let c = char::from_u32(n).unwrap_or('\u{FFFD}');
1003            if !c.is_xml_char() {
1004                return None;
1005            }
1006
1007            Reference::Char(c)
1008        } else {
1009            let name = self.consume_name().ok()?;
1010            match name {
1011                "quot" => Reference::Char('"'),
1012                "amp" => Reference::Char('&'),
1013                "apos" => Reference::Char('\''),
1014                "lt" => Reference::Char('<'),
1015                "gt" => Reference::Char('>'),
1016                _ => Reference::Entity(name),
1017            }
1018        };
1019
1020        self.consume_byte(b';').ok()?;
1021
1022        Some(reference)
1023    }
1024
1025    /// Consumes according to: <https://www.w3.org/TR/xml/#NT-Name>
1026    fn consume_name(&mut self) -> Result<&'input str> {
1027        let start = self.pos();
1028        self.skip_name()?;
1029
1030        let name = self.slice_back(start);
1031        if name.is_empty() {
1032            return Err(Error::InvalidName(self.gen_text_pos_from(start)));
1033        }
1034
1035        Ok(name)
1036    }
1037
1038    /// The same as `consume_name()`, but does not return a consumed name.
1039    fn skip_name(&mut self) -> Result<()> {
1040        let start = self.pos();
1041        let mut iter = self.chars();
1042        if let Some(c) = iter.next() {
1043            if c.is_xml_name_start() {
1044                self.advance(c.len_utf8());
1045            } else {
1046                return Err(Error::InvalidName(self.gen_text_pos_from(start)));
1047            }
1048        }
1049
1050        for c in iter {
1051            if c.is_xml_name() {
1052                self.advance(c.len_utf8());
1053            } else {
1054                break;
1055            }
1056        }
1057
1058        Ok(())
1059    }
1060
1061    /// Consumes a qualified XML name and returns it.
1062    ///
1063    /// Consumes according to: <https://www.w3.org/TR/xml-names/#ns-qualnames>
1064    #[inline(never)]
1065    fn consume_qname(&mut self) -> Result<(&'input str, &'input str)> {
1066        let start = self.pos();
1067
1068        let mut splitter = None;
1069
1070        while !self.at_end() {
1071            // Check for ASCII first for performance reasons.
1072            let b = self.curr_byte_unchecked();
1073            if b < 128 {
1074                if b == b':' {
1075                    if splitter.is_none() {
1076                        splitter = Some(self.pos());
1077                        self.advance(1);
1078                    } else {
1079                        // Multiple `:` is an error.
1080                        return Err(Error::InvalidName(self.gen_text_pos_from(start)));
1081                    }
1082                } else if b.is_xml_name() {
1083                    self.advance(1);
1084                } else {
1085                    break;
1086                }
1087            } else {
1088                // Fallback to Unicode code point.
1089                match self.chars().next() {
1090                    Some(c) if c.is_xml_name() => {
1091                        self.advance(c.len_utf8());
1092                    }
1093                    _ => break,
1094                }
1095            }
1096        }
1097
1098        let (prefix, local) = if let Some(splitter) = splitter {
1099            let prefix = self.span.slice_region(start, splitter);
1100            let local = self.slice_back(splitter + 1);
1101            (prefix, local)
1102        } else {
1103            let local = self.slice_back(start);
1104            // Slice an empty prefix. This way we can preserve attribute start position.
1105            (self.span.slice_region(start, start), local)
1106        };
1107
1108        fn is_xml_name_start(name: &str) -> bool {
1109            if let Some(b) = name.as_bytes().first() {
1110                if *b < 128 {
1111                    return b.is_xml_name_start();
1112                } else if let Some(c) = name.chars().next() {
1113                    return c.is_xml_name_start();
1114                }
1115            }
1116
1117            false
1118        }
1119
1120        // Prefix must be empty or start with a `NameStartChar`.
1121        if !prefix.is_empty() && !is_xml_name_start(prefix) {
1122            return Err(Error::InvalidName(self.gen_text_pos_from(start)));
1123        }
1124
1125        // Local name must start with a `NameStartChar`.
1126        if !is_xml_name_start(local) {
1127            return Err(Error::InvalidName(self.gen_text_pos_from(start)));
1128        }
1129
1130        Ok((prefix, local))
1131    }
1132
1133    fn consume_eq(&mut self) -> Result<()> {
1134        self.skip_spaces();
1135        self.consume_byte(b'=')?;
1136        self.skip_spaces();
1137
1138        Ok(())
1139    }
1140
1141    fn consume_quote(&mut self) -> Result<u8> {
1142        let c = self.curr_byte()?;
1143        if c == b'\'' || c == b'"' {
1144            self.advance(1);
1145            Ok(c)
1146        } else {
1147            Err(Error::InvalidChar2("a quote", c, self.gen_text_pos()))
1148        }
1149    }
1150
1151    /// Calculates a current absolute position.
1152    ///
1153    /// This operation is very expensive. Use only for errors.
1154    #[inline(never)]
1155    pub fn gen_text_pos(&self) -> TextPos {
1156        let text = self.span.as_str();
1157        let end = self.pos;
1158
1159        let row = Self::calc_curr_row(text, end);
1160        let col = Self::calc_curr_col(text, end);
1161        TextPos::new(row, col)
1162    }
1163
1164    /// Calculates an absolute position at `pos`.
1165    ///
1166    /// This operation is very expensive. Use only for errors.
1167    #[inline(never)]
1168    pub fn gen_text_pos_from(&self, pos: usize) -> TextPos {
1169        let mut s = self.clone();
1170        s.pos = core::cmp::min(pos, s.span.as_str().len());
1171        s.gen_text_pos()
1172    }
1173
1174    fn calc_curr_row(text: &str, end: usize) -> u32 {
1175        let mut row = 1;
1176        for c in &text.as_bytes()[..end] {
1177            if *c == b'\n' {
1178                row += 1;
1179            }
1180        }
1181
1182        row
1183    }
1184
1185    fn calc_curr_col(text: &str, end: usize) -> u32 {
1186        let mut col = 1;
1187        for c in text[..end].chars().rev() {
1188            if c == '\n' {
1189                break;
1190            } else {
1191                col += 1;
1192            }
1193        }
1194
1195        col
1196    }
1197}
roxmltree/tokenizer.rs

roxmltree/
tokenizer.rs
