XML Streaming Parser

Deep dive

How it works

In: a byte slice (or chunks) holding XML, plus a strict/recover flag · Out: events Start(name, attributes), End, Text, CData in document order · State: read offset and the stack of open element names · Cost: O(n) time, O(depth) memory

1. Look at the next byte. Not <: scan to the next <, decode references, emit Text.
2. <![CDATA[, <!--, <?: find the terminator (]]>, -->, ?>). CDATA is emitted verbatim; comments and processing instructions are skipped.
3. <!DOCTYPE: refuse, in both modes. Without a DTD no custom entity can exist, so nothing can expand.
4. </name>: compare with the top of the stack. Equal: pop, emit End. Different: strict mode errors; recovery mode first closes the open children (re-reading this tag) or drops a stray tag.
5. <name a="v">: parse attributes (either quote), check the depth limit, push, emit Start. <name/> emits Start now and End on the next call.
6. At end of input, any element still open is an error (strict) or gets End events (recovery).

References. The five predefined entities are amp lt gt apos quot; &#N; and &#xH; are numeric (XML 1.0 §4.6). Feeds also carry HTML entities such as  , undefined in XML: strict mode errors, recovery keeps the text.

Namespaces. xmlns:p="uri" binds prefix p for its subtree. Keep a scope stack prefix → URI, pushed at Start and popped at End, and compare (URI, local name), never prefixes (Namespaces in XML). The code below only strips prefixes.

Encoding. A UTF-16 entity must start with a byte order mark, a UTF-8 one may; with neither a BOM nor an encoding declaration the entity must be UTF-8, else it is a fatal error. Transport metadata such as an HTTP charset is left to the higher-level protocol (Appendix F.2). Sniff BOM, then <?xml encoding=…?>, transcode to UTF-8, parse bytes.

Strict vs recovery. After a fatal error the processor must report it and must not go on passing data and structure to the application normally. Lenient tools break this on purpose: libxml2's XML_PARSE_RECOVER accepts non-well-formed documents with unspecified behaviour; Python's feedparser sets a bozo flag on such feeds and exposes the exception.

Hostile input. OWASP: disable DTDs or reject DOCTYPE; otherwise disable external entities and limit expansion. Also cap depth, token size and total bytes.

Extracting. Keep the path as a string (/rss/channel/item/title) and test it at Text events. Atom: entry/link carries href, and a missing rel means alternate (RFC 4287). RSS 2.0 items may omit any element except that title or description must exist (spec).

Code

enum Ev { Start(String, Vec<(String, String)>), End(String), Text(String), CData(String) }
type R<T> = Result<T, &'static str>; fn lossy(b: &[u8]) -> String { String::from_utf8_lossy(b).into_owned() }
/// The 5 predefined entities + `&#N;`/`&#xH;`. With no DTD nothing else exists: `&nbsp;` is an error, or literal in recovery.
fn decode(s: &[u8], recover: bool) -> R<String> {
    if !s.contains(&b'&') { return Ok(lossy(s)); }
    let (mut out, mut i) = (Vec::with_capacity(s.len()), 0);
    while i < s.len() {
        if s[i] != b'&' { out.push(s[i]); i += 1; continue; }
        let end = s[i..].iter().take(12).position(|&c| c == b';');
        let ch = end.and_then(|e| match &s[i + 1..i + e] {
            b"amp" => Some('&'), b"lt" => Some('<'), b"gt" => Some('>'), b"quot" => Some('"'), b"apos" => Some('\''),
            [b'#', b'x' | b'X', h @ ..] => u32::from_str_radix(std::str::from_utf8(h).ok()?, 16).ok().and_then(char::from_u32),
            [b'#', d @ ..] => std::str::from_utf8(d).ok()?.parse().ok().and_then(char::from_u32), _ => None,
        });
        match (ch, end) {
            (Some(c), Some(e)) => { out.extend_from_slice(c.encode_utf8(&mut [0; 4]).as_bytes()); i += e + 1; }
            _ if recover => { out.push(b'&'); i += 1; } _ => return Err("bad entity"),
        }
    }
    Ok(lossy(&out))
}
/// `<name a="v" b='w'>` or `<name/>` at rest[0] -> (name, attrs, self-closing, bytes used); None = input ends inside it.
fn tag(rest: &[u8], rec: bool) -> R<Option<(String, Vec<(String, String)>, bool, usize)>> {
    let mut p = rest.iter().position(|c| c.is_ascii_whitespace() || *c == b'>' || *c == b'/').unwrap_or(rest.len());
    let (name, mut attrs) = (lossy(&rest[1..p]), vec![]);
    loop {
        while rest.get(p).is_some_and(|c| c.is_ascii_whitespace()) { p += 1; }
        match rest.get(p) {
            None => return Ok(None),
            Some(b'>') => return Ok(Some((name, attrs, false, p + 1))),
            Some(b'/') if rest.get(p + 1) == Some(&b'>') => return Ok(Some((name, attrs, true, p + 2))),
            _ => {}
        }
        let eq = rest[p..].iter().position(|&c| c == b'=' || c == b'>');
        let q = eq.and_then(|e| rest.get(p + e + 1).copied()).filter(|q| *q == b'"' || *q == b'\'');
        let (Some(eq), Some(q)) = (eq, q) else { return Err("malformed attribute") };
        let Some(ve) = rest[p + eq + 2..].iter().position(|&c| c == q) else { return Ok(None) };
        attrs.push((lossy(&rest[p..p + eq]).trim().into(), decode(&rest[p + eq + 2..p + eq + 2 + ve], rec)?));
        p += eq + ve + 3;
    }
}
struct Pull<'a> { b: &'a [u8], i: usize, stack: Vec<String>, empty: bool, max_depth: usize, recover: bool }
impl<'a> Pull<'a> {
    pub fn new(b: &'a [u8], recover: bool) -> Self { Pull { b, i: 0, stack: vec![], empty: false, max_depth: 64, recover } }
    fn cut(&mut self) -> R<()> { if self.recover { self.i = self.b.len(); Ok(()) } else { Err("truncated markup") } } // input ended inside markup
    pub fn next(&mut self) -> R<Option<Ev>> {
        if self.empty { self.empty = false; return Ok(self.stack.pop().map(Ev::End)); } // second half of <a/>
        loop {
            let rest = &self.b[self.i..];
            if rest.is_empty() { // recovery: auto-close whatever is still open
                return match self.stack.pop() { None => Ok(None), Some(n) if self.recover => Ok(Some(Ev::End(n))), _ => Err("unclosed element at EOF") };
            }
            if rest[0] != b'<' {
                let n = rest.iter().position(|&c| c == b'<').unwrap_or(rest.len());
                self.i += n;
                return Ok(Some(Ev::Text(decode(&rest[..n], self.recover)?)));
            }
            if rest.starts_with(b"<!DOCTYPE") { return Err("DOCTYPE refused"); } // XXE, billion laughs: never expand
            let (open, close) = if rest.starts_with(b"<![CDATA[") { (9, &b"]]>"[..]) } else if rest.starts_with(b"<!--") { (4, &b"-->"[..]) }
                else if rest.starts_with(b"<?") { (2, &b"?>"[..]) } else if rest.starts_with(b"</") { (2, &b">"[..]) } else { (0, &b""[..]) };
            if open > 0 { // CDATA yields text, end tags yield End, comments and PIs are skipped
                let Some(e) = rest.windows(close.len()).position(|w| w == close) else { self.cut()?; continue };
                self.i += e + close.len();
                if open == 9 { return Ok(Some(Ev::CData(lossy(&rest[9..e])))); }
                if open == 2 && close == b">" {
                    let name = lossy(&rest[2..e]).trim().to_string();
                    match self.stack.last() {
                        Some(top) if *top == name => return Ok(self.stack.pop().map(Ev::End)),
                        _ if self.recover && self.stack.contains(&name) => { self.i -= e + 1; return Ok(self.stack.pop().map(Ev::End)); } // close the child first, re-read this tag
                        _ if self.recover => {} // stray end tag
                        _ => return Err("mismatched end tag"),
                    }
                }
                continue;
            }
            let Some((name, attrs, empty, n)) = tag(rest, self.recover)? else { self.cut()?; continue };
            if self.stack.len() >= self.max_depth { return Err("too deep"); }
            (self.i, self.empty) = (self.i + n, empty);
            self.stack.push(name.clone());
            return Ok(Some(Ev::Start(name, attrs)));
        }
    }
}
/// (title, link) per RSS `item` / Atom `entry`, matched on a path like `/rss/channel/item/title`.
fn items(xml: &[u8], recover: bool) -> R<Vec<(String, String)>> {
    let (mut path, mut out, mut cur, mut pull) = (String::new(), vec![], (String::new(), String::new()), Pull::new(xml, recover));
    while let Some(ev) = pull.next()? {
        match ev {
            Ev::Start(name, attrs) => {
                path.push('/'); path.push_str(name.rsplit(':').next().unwrap()); // local name; real code resolves xmlns
                if path.ends_with("/item") || path.ends_with("/entry") { cur = Default::default(); }
                let alt = attrs.iter().all(|a| a.0 != "rel" || a.1 == "alternate");
                if let (true, Some(h)) = (path.ends_with("/entry/link") && cur.1.is_empty() && alt, attrs.iter().find(|a| a.0 == "href")) { cur.1 = h.1.clone(); }
            }
            Ev::Text(t) | Ev::CData(t) => {
                if path.ends_with("/item/title") || path.ends_with("/entry/title") { cur.0.push_str(&t) } else if path.ends_with("/item/link") { cur.1.push_str(&t) }
            }
            Ev::End(_) => {
                if path.ends_with("/item") || path.ends_with("/entry") { out.push(std::mem::take(&mut cur)); }
                path.truncate(path.rfind('/').unwrap());
            }
        }
    }
    Ok(out)
}
fn main() {
    let rss = br#"<rss><channel><title>F</title><item><title>A &amp; B &#x41;&#66;</title><link>http://a/1</link></item>
      <item><title><![CDATA[<C>]]></title><!-- c --><link>http://a/2</link></item></channel></rss>"#;
    let atom = br#"<feed xmlns="http://www.w3.org/2005/Atom"><entry><title>X</title><link rel="self" href="http://s"/><link href="http://x/1"/></entry>
      <entry><title type='text'>Y</title><link rel="alternate" href="http://x/2"/></entry></feed>"#;
    assert_eq!(items(rss, false).unwrap(), [("A & B AB".into(), "http://a/1".into()), ("<C>".into(), "http://a/2".into())]);
    assert_eq!(items(atom, false).unwrap(), [("X".into(), "http://x/1".into()), ("Y".into(), "http://x/2".into())]);
    let bad = b"<rss><channel><item><title>A</title></item><item><title>B &nbsp;</title><link>u</link></channel></rss>";
    assert!(items(bad, false).is_err()); // strict: fatal error, as XML 1.0 requires
    assert_eq!(items(bad, true).unwrap().len(), 2); // recovery: 2nd <item> auto-closed at </channel>
    assert_eq!(items(&bad[..bad.len() - 31], true).unwrap().len(), 2); // truncated mid-tag
    let laughs = b"<?xml version=\"1.0\"?><!DOCTYPE lolz [<!ENTITY lol \"lol\"><!ENTITY l2 \"&lol;&lol;\">]><lolz>&l2;</lolz>";
    assert_eq!(items(laughs, true), Err("DOCTYPE refused")); // refused even in recovery mode
    assert_eq!(items("<a>".repeat(100).as_bytes(), true), Err("too deep"));
}

Compiled and run with rustc stable; the asserts pass. Attributes must be quoted.

Complexity and constants

O(n) time, O(depth + largest token) memory. Measured on this Mac (Apple M4 Pro, release build, one thread, 200 MB generated RSS feed, 600,133 items of about 333 bytes, other jobs running): extraction 160-220 MB/s over four runs. Cost drivers: a String per name and text event, and the path test per event.

Efficiency

• Cost: about 1.5-2 µs per item of that feed (derived from the measured throughput, this Mac). Bound by compute and allocation, not I/O; memory is the name stack plus the output.
• Levers:
  • Borrow &str slices instead of allocating per event — gain not measured; quick-xml's README describes its reader as almost zero-copy — when most events are ignored.
  • Skip decoding outside the wanted path — not measured — when you need 2 of 10 fields.
  • Vectorised search for < — not measured — on text-heavy documents.
  • One thread per feed — scales with cores, feeds are independent — in a harvester with many feeds.
  • Skip unchanged feeds via conditional GET — avoids the parse — when polling.
• Naive → standard → state of the art:
  • Whole-document tree · memory grows with file size
  • Pull parser, owned strings (this page) · 160-220 MB/s, O(depth) memory (measured here)
  • Borrowed, buffer-reusing pull reader (quick-xml) · no per-event allocation; throughput not measured here

Implementation notes

• Parse bytes, not chars: markup is ASCII. Normalise \r\n first (XML 1.0 §2.11).
• Harvesters: parse strict, retry in recovery mode, flag the item as damaged.

Pitfalls

• Prefixes as names: <a:link> is the same element as <link> only if xmlns says so.
• DTD processing on with expansion: billion laughs, external entities (XXE).
• HTML entities in feeds fail a strict parse of the whole document.
• Text arrives in several events (CDATA, comments, entities): concatenate until End.
• Recovery can swallow later siblings into an unclosed element: flag the document.

Variants and alternatives

In production

• libxml2 (xmlReader), quick-xml, xml-rs; Python feedparser for RSS/Atom/JSON feeds; see Implementations.

Implementations

Sources

• W3C, Extensible Markup Language (XML) 1.0 (Fifth Edition). spec
• W3C, Namespaces in XML 1.0. spec
• Nottingham, Sayre, The Atom Syndication Format, RFC 4287. RFC
• RSS Advisory Board, RSS 2.0 Specification. spec
• OWASP, XML External Entity Prevention Cheat Sheet. cheat sheet
• libxml2, parser API (XML_PARSE_RECOVER). docs
• feedparser, Bozo detection. docs
• sitemaps.org, Sitemaps XML format. spec
• OASIS, OpenDocument 1.3, Part 2: Packages. spec
• OpenStreetMap wiki, Planet.osm. wiki