entropy-auth 2026.7.31

//! Minimal, namespace-aware XML parser with security hardening.
//!
//! This parser is intentionally limited in scope — it handles only the
//! subset of XML required for SAML 2.0 response processing. Processing
//! instructions, DTD declarations, and CDATA sections are rejected to
//! reduce attack surface.

use core::fmt;
use std::collections::HashSet;

// ---------------------------------------------------------------------------
// Limits
// ---------------------------------------------------------------------------

/// Maximum nesting depth for XML elements.
pub const MAX_XML_DEPTH: usize = 64;

/// Maximum input document size in bytes (10 MB).
pub const MAX_XML_SIZE: usize = 10 * 1024 * 1024;

/// Maximum length of an entity name between `&` and `;`.
const MAX_ENTITY_NAME_LEN: usize = 32;

/// Maximum number of attributes (including namespace declarations) on a
/// single element. Bounds the O(n) attribute/namespace lookups that run per
/// element so a pathological document cannot provoke quadratic behaviour
/// within the overall size limit. Set far above any legitimate SAML element.
const MAX_ATTRIBUTES: usize = 10_000;

// ---------------------------------------------------------------------------
// Error type
// ---------------------------------------------------------------------------

/// Errors that can occur during XML parsing.
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum XmlParseError {
    /// The input exceeds `MAX_XML_SIZE` (10 MB).
    InputTooLarge,
    /// Element nesting exceeds `MAX_XML_DEPTH` (64).
    MaxDepthExceeded,
    /// A DTD declaration (`<!DOCTYPE`) was encountered.
    DtdNotAllowed,
    /// A processing instruction (`<?...?>`) was encountered.
    ProcessingInstructionNotAllowed,
    /// A CDATA section was encountered.
    CdataNotAllowed,
    /// Generic syntax error with a human-readable message.
    Syntax(String),
}

impl fmt::Display for XmlParseError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InputTooLarge => {
                write!(f, "XML input exceeds maximum size of {MAX_XML_SIZE} bytes")
            }
            Self::MaxDepthExceeded => {
                write!(f, "XML nesting exceeds maximum depth of {MAX_XML_DEPTH}")
            }
            Self::DtdNotAllowed => write!(f, "DTD declarations are not allowed"),
            Self::ProcessingInstructionNotAllowed => {
                write!(f, "processing instructions are not allowed")
            }
            Self::CdataNotAllowed => write!(f, "CDATA sections are not allowed"),
            Self::Syntax(msg) => write!(f, "XML syntax error: {msg}"),
        }
    }
}

impl std::error::Error for XmlParseError {}

// ---------------------------------------------------------------------------
// XmlElement
// ---------------------------------------------------------------------------

/// A parsed XML element.
#[derive(Debug, Clone)]
pub struct XmlElement {
    /// Local name (without namespace prefix).
    name: String,
    /// Namespace URI, if any.
    namespace: Option<String>,
    /// Attribute list as `(name, value)` pairs.
    attributes: Vec<(String, String)>,
    /// Child elements.
    children: Vec<XmlElement>,
    /// Direct text content (concatenated text nodes).
    text: Option<String>,
}

impl XmlElement {
    /// Returns the local element name (without namespace prefix).
    #[must_use]
    #[inline]
    pub fn name(&self) -> &str {
        &self.name
    }

    /// Returns the namespace URI, if any.
    #[must_use]
    #[inline]
    pub fn namespace(&self) -> Option<&str> {
        self.namespace.as_deref()
    }

    /// Returns the child elements.
    #[must_use]
    #[inline]
    pub fn children(&self) -> &[XmlElement] {
        &self.children
    }

    /// Find the first child element by local name.
    #[must_use]
    pub fn find_child(&self, name: &str) -> Option<&XmlElement> {
        self.children.iter().find(|c| c.name == name)
    }

    /// Find the first child element by namespace URI and local name.
    #[must_use]
    pub fn find_child_ns(&self, namespace: &str, name: &str) -> Option<&XmlElement> {
        self.children
            .iter()
            .find(|c| c.name == name && c.namespace.as_deref() == Some(namespace))
    }

    /// Find all child elements by local name.
    #[must_use]
    pub fn find_children(&self, name: &str) -> Vec<&XmlElement> {
        self.children.iter().filter(|c| c.name == name).collect()
    }

    /// Get an attribute value by name.
    #[must_use]
    pub fn attribute(&self, name: &str) -> Option<&str> {
        self.attributes
            .iter()
            .find(|(k, _)| k == name)
            .map(|(_, v)| v.as_str())
    }

    /// Get the direct text content, if any.
    #[must_use]
    pub fn text_content(&self) -> Option<&str> {
        self.text.as_deref()
    }
}

// ---------------------------------------------------------------------------
// Parser internals
// ---------------------------------------------------------------------------

/// A list of `(key, value)` string pairs used for attributes and namespace
/// frames.
type StringPairs = Vec<(String, String)>;

/// Internal parser state.
struct Parser<'a> {
    input: &'a str,
    pos: usize,
    /// Stack of namespace mappings: `(prefix, uri)` per depth level.
    ns_stack: Vec<Vec<(String, String)>>,
}

impl<'a> Parser<'a> {
    fn new(input: &'a str) -> Self {
        Self {
            input,
            pos: 0,
            ns_stack: Vec::new(),
        }
    }

    fn remaining(&self) -> &'a str {
        &self.input[self.pos..]
    }

    fn peek(&self) -> Option<char> {
        self.remaining().chars().next()
    }

    fn advance(&mut self, n: usize) {
        self.pos += n;
    }

    fn skip_whitespace(&mut self) {
        while let Some(c) = self.peek() {
            if c.is_ascii_whitespace() {
                self.advance(c.len_utf8());
            } else {
                break;
            }
        }
    }

    fn starts_with(&self, s: &str) -> bool {
        self.remaining().starts_with(s)
    }

    fn expect(&mut self, s: &str) -> Result<(), XmlParseError> {
        if self.starts_with(s) {
            self.advance(s.len());
            Ok(())
        } else {
            Err(XmlParseError::Syntax(format!("expected '{s}'")))
        }
    }

    /// Read a name token (element or attribute name).
    fn read_name(&mut self) -> Result<String, XmlParseError> {
        let start = self.pos;
        while let Some(c) = self.peek() {
            if c.is_ascii_alphanumeric() || c == '_' || c == '-' || c == '.' || c == ':' {
                self.advance(c.len_utf8());
            } else {
                break;
            }
        }
        if self.pos == start {
            return Err(XmlParseError::Syntax("expected name".to_string()));
        }
        let name = &self.input[start..self.pos];
        // SECURITY: enforce the XML Name / Namespaces QName shape — at most one
        // colon, and each part must begin with a letter or '_'. This rejects
        // `:Audience`, `a:b:c`, `Audience:`, and names starting with a digit /
        // '-' / '.'. `resolve_name` splits on the first colon, so a conformant
        // XML-DSig verifier and this parser would otherwise disagree on what a
        // malformed name resolves to — the parser-divergence class the
        // duplicate-attribute and trailing-content defenses also close. No
        // conformant SAML/XML producer emits such names.
        let well_formed = name.split(':').count() <= 2
            && name
                .split(':')
                .all(|part| matches!(part.chars().next(), Some(c) if c.is_ascii_alphabetic() || c == '_'));
        if !well_formed {
            return Err(XmlParseError::Syntax("malformed XML name".to_string()));
        }
        Ok(name.to_string())
    }

    /// Read a quoted attribute value and decode XML entities.
    fn read_attribute_value(&mut self) -> Result<String, XmlParseError> {
        let quote = self
            .peek()
            .ok_or_else(|| XmlParseError::Syntax("expected quote".to_string()))?;
        if quote != '"' && quote != '\'' {
            return Err(XmlParseError::Syntax("expected quote".to_string()));
        }
        self.advance(1);
        let start = self.pos;
        while let Some(c) = self.peek() {
            if c == quote {
                let raw = &self.input[start..self.pos];
                self.advance(1);
                // XML 1.0 §3.3.3 attribute-value normalization: a LITERAL tab,
                // newline or carriage return becomes a single space. A
                // character REFERENCE (`&#xA;`) must survive, so the
                // substitution happens before entity decoding, not after.
                let normalized: String = raw
                    .chars()
                    .map(|c| {
                        if matches!(c, '\t' | '\n' | '\r') {
                            ' '
                        } else {
                            c
                        }
                    })
                    .collect();
                return decode_entities(&normalized);
            }
            // XML 1.0 §3.1 WFC "No < in Attribute Values". Admitting it was the
            // one remaining way a raw markup character could reach a consumer
            // that re-serializes an attribute.
            if c == '<' {
                return Err(XmlParseError::Syntax(
                    "'<' is not allowed in an attribute value".to_string(),
                ));
            }
            self.advance(c.len_utf8());
        }
        Err(XmlParseError::Syntax(
            "unterminated attribute value".to_string(),
        ))
    }

    /// Read text content between tags and decode XML entities.
    fn read_text(&mut self) -> Result<String, XmlParseError> {
        let start = self.pos;
        while let Some(c) = self.peek() {
            if c == '<' {
                break;
            }
            self.advance(c.len_utf8());
        }
        let raw = &self.input[start..self.pos];
        decode_entities(raw)
    }

    /// Resolve a possibly-prefixed name to `(local_name, namespace_uri)`.
    fn resolve_name(&self, full_name: &str) -> (String, Option<String>) {
        if let Some((prefix, local)) = full_name.split_once(':') {
            let uri = self.lookup_ns(prefix);
            (local.to_string(), uri)
        } else {
            // Default namespace
            let uri = self.lookup_ns("");
            (full_name.to_string(), uri)
        }
    }

    /// Look up a namespace prefix in the current scope (most recent first).
    fn lookup_ns(&self, prefix: &str) -> Option<String> {
        for frame in self.ns_stack.iter().rev() {
            for (p, uri) in frame.iter().rev() {
                if p == prefix {
                    return if uri.is_empty() {
                        None
                    } else {
                        Some(uri.clone())
                    };
                }
            }
        }
        None
    }

    /// Skip the XML declaration `<?xml ... ?>`.
    fn skip_xml_declaration(&mut self) -> Result<(), XmlParseError> {
        self.skip_whitespace();
        // A declaration is `<?xml` followed by whitespace (any kind, per
        // XML 1.0 §2.8) or the closing `?`. Checking the following character
        // avoids mis-reading `<?xml...` PIs and accepts tab/newline-separated
        // declarations that some IdPs emit.
        let is_declaration = self.remaining().strip_prefix("<?xml").is_some_and(|rest| {
            rest.chars()
                .next()
                .is_none_or(|c| c == '?' || c.is_ascii_whitespace())
        });
        if is_declaration {
            // Skip to the closing `?>`
            if let Some(end) = self.remaining().find("?>") {
                self.advance(end + 2);
            } else {
                return Err(XmlParseError::Syntax(
                    "unterminated XML declaration".to_string(),
                ));
            }
        }
        Ok(())
    }

    /// Skip XML comments `<!-- ... -->`.
    fn skip_comment(&mut self) -> Result<(), XmlParseError> {
        if self.starts_with("<!--") {
            if let Some(end) = self.remaining().find("-->") {
                self.advance(end + 3);
                Ok(())
            } else {
                Err(XmlParseError::Syntax("unterminated comment".to_string()))
            }
        } else {
            Ok(())
        }
    }

    /// Parse a single element, including its children.
    fn parse_element(&mut self, depth: usize) -> Result<XmlElement, XmlParseError> {
        // `depth` is zero-based (the root element is depth 0), so `>=` caps
        // nesting at exactly `MAX_XML_DEPTH` elements: the deepest permitted
        // element sits at depth `MAX_XML_DEPTH - 1`.
        if depth >= MAX_XML_DEPTH {
            return Err(XmlParseError::MaxDepthExceeded);
        }

        self.expect("<")?;

        // SECURITY: Reject DTD declarations to prevent XXE attacks.
        if self.starts_with("!DOCTYPE") {
            return Err(XmlParseError::DtdNotAllowed);
        }

        // SECURITY: Reject CDATA sections.
        if self.starts_with("![CDATA[") {
            return Err(XmlParseError::CdataNotAllowed);
        }

        let tag_name = self.read_name()?;
        let (raw_attrs, ns_frame) = self.parse_attributes()?;

        // Push namespace frame before resolving names.
        self.ns_stack.push(ns_frame);

        // Resolve element name.
        let (local_name, namespace) = self.resolve_name(&tag_name);

        // Resolve attribute names (strip prefixes for simplicity — SAML
        // attribute names are rarely namespaced).
        let attributes: Vec<(String, String)> = raw_attrs
            .into_iter()
            .map(|(k, v)| {
                let local = if let Some((_prefix, local)) = k.split_once(':') {
                    local.to_string()
                } else {
                    k
                };
                (local, v)
            })
            .collect();

        // Self-closing tag?
        if self.peek() == Some('/') {
            self.advance(1);
            self.expect(">")?;
            self.ns_stack.pop();
            return Ok(XmlElement {
                name: local_name,
                namespace,
                attributes,
                children: Vec::new(),
                text: None,
            });
        }

        self.expect(">")?;

        let (children, text_buf) = self.parse_children(depth, &local_name)?;

        // Consume closing tag.
        self.expect("</")?;
        let close_name = self.read_name()?;
        self.skip_whitespace();
        self.expect(">")?;

        // Verify the closing tag matches (compare raw qualified names).
        if close_name != tag_name {
            return Err(XmlParseError::Syntax(format!(
                "mismatched closing tag: expected </{tag_name}>, found </{close_name}>"
            )));
        }

        self.ns_stack.pop();

        let text = if text_buf.is_empty() {
            None
        } else {
            Some(text_buf)
        };

        Ok(XmlElement {
            name: local_name,
            namespace,
            attributes,
            children,
            text,
        })
    }

    /// Parse attributes and namespace declarations from the current position
    /// until `>` or `/` is reached.
    fn parse_attributes(&mut self) -> Result<(StringPairs, StringPairs), XmlParseError> {
        let mut raw_attrs: StringPairs = Vec::new();
        let mut ns_frame: StringPairs = Vec::new();
        // O(1) duplicate detection (see the SECURITY note below).
        let mut seen_locals: HashSet<String> = HashSet::new();
        let mut seen_prefixes: HashSet<String> = HashSet::new();

        loop {
            self.skip_whitespace();
            match self.peek() {
                Some('>' | '/') => break,
                None => return Err(XmlParseError::Syntax("unexpected end of input".to_string())),
                _ => {}
            }
            let attr_name = self.read_name()?;
            self.skip_whitespace();
            self.expect("=")?;
            self.skip_whitespace();
            let attr_value = self.read_attribute_value()?;

            // SECURITY: a repeated attribute name is a fatal well-formedness
            // error (XML 1.0 §3.1, WFC: Unique Att Spec). Silently keeping the
            // first (as a naive push would) is a signature-wrapping surface:
            // an external XML-DSig verifier may canonicalize differently or
            // pick the last occurrence, so `Recipient="good" Recipient="evil"`
            // could be signed-as-one-value but read here as another. Reject.
            //
            // Membership is tracked in HashSets, not by scanning the
            // accumulated vectors: a linear scan per attribute is O(n^2) per
            // element, and with MAX_ATTRIBUTES at 10_000 — repeatable on every
            // element of an unauthenticated SAML document — that is a
            // quadratic-time CPU DoS. (The JSON parser's equivalent key check
            // was already converted for exactly this reason.)
            if attr_name == "xmlns" {
                if !seen_prefixes.insert(String::new()) {
                    return Err(XmlParseError::Syntax(
                        "duplicate 'xmlns' declaration".to_string(),
                    ));
                }
                ns_frame.push((String::new(), attr_value));
            } else if let Some(prefix) = attr_name.strip_prefix("xmlns:") {
                if !seen_prefixes.insert(prefix.to_string()) {
                    return Err(XmlParseError::Syntax(
                        "duplicate namespace declaration".to_string(),
                    ));
                }
                ns_frame.push((prefix.to_string(), attr_value));
            } else {
                // Dedup on the LOCAL name: `parse_element` strips attribute
                // prefixes and `attribute()` looks up by local name (first
                // match), so `Recipient` and `x:Recipient` collapse to one
                // attribute. Comparing the raw qualified name here would let
                // both through and re-open the wrapping gap this check closes.
                let local = attr_name
                    .split_once(':')
                    .map_or(attr_name.as_str(), |(_, l)| l);
                if !seen_locals.insert(local.to_string()) {
                    return Err(XmlParseError::Syntax(
                        "duplicate attribute name".to_string(),
                    ));
                }
                raw_attrs.push((attr_name, attr_value));
            }

            // SECURITY: cap attributes per element to bound the per-element
            // O(n) attribute/namespace lookups.
            if raw_attrs.len() + ns_frame.len() > MAX_ATTRIBUTES {
                return Err(XmlParseError::Syntax(
                    "element exceeds maximum attribute count".to_string(),
                ));
            }
        }

        Ok((raw_attrs, ns_frame))
    }

    /// Parse child elements and text content until a closing tag is reached.
    fn parse_children(
        &mut self,
        depth: usize,
        local_name: &str,
    ) -> Result<(Vec<XmlElement>, String), XmlParseError> {
        let mut children = Vec::new();
        let mut text_buf = String::new();
        // SECURITY: track whether a comment appeared inside this element so we
        // can reject comments that interleave with text content.
        let mut comment_seen = false;

        loop {
            if self.starts_with("</") {
                break;
            }

            if self.starts_with("<!--") {
                self.skip_comment()?;
                comment_seen = true;
                continue;
            }

            // SECURITY: Reject DTD declarations to prevent XXE attacks.
            if self.starts_with("<!DOCTYPE") {
                return Err(XmlParseError::DtdNotAllowed);
            }

            // SECURITY: Reject CDATA sections.
            if self.starts_with("<![CDATA[") {
                return Err(XmlParseError::CdataNotAllowed);
            }

            // SECURITY: Reject processing instructions to reduce attack surface.
            if self.starts_with("<?") {
                return Err(XmlParseError::ProcessingInstructionNotAllowed);
            }

            if self.starts_with("<") {
                children.push(self.parse_element(depth + 1)?);
                continue;
            }

            if self.peek().is_none() {
                return Err(XmlParseError::Syntax(format!(
                    "unexpected end of input inside <{local_name}>"
                )));
            }

            // Text content
            let t = self.read_text()?;
            text_buf.push_str(&t);
        }

        // SECURITY: An XML comment that sits inside a text-bearing element
        // splits the text into segments this parser would silently
        // concatenate (`<NameID>good@x<!---->.evil</NameID>` → `good@x.evil`).
        // A signature-verifying layer that canonicalizes comments differently
        // would then see different bytes than the value extracted here — the
        // SAML comment-truncation class (CVE-2018-0489). Reject any comment
        // that co-occurs with text content so the verified bytes and the
        // extracted value can never diverge. Comments between child elements
        // (no text) remain allowed.
        if comment_seen && !text_buf.bytes().all(is_xml_space) {
            return Err(XmlParseError::Syntax(
                "comment interleaved with text content is not allowed".to_string(),
            ));
        }

        // SECURITY: The element-interleaved sibling of the comment case above.
        // `<NameID>good@evil.com<x/></NameID>` would have this parser extract
        // `text_content()` == "good@evil.com" while an XML-DSig canonicalizer
        // sees text *and* a child element — the same parser/verifier divergence
        // (signature-wrapping surface). SAML 2.0 has no legitimate mixed-content
        // elements, so reject any element that carries both non-whitespace text
        // and child elements. XML whitespace (§2.3 `S`) between children is
        // allowed.
        if !children.is_empty() && !text_buf.bytes().all(is_xml_space) {
            return Err(XmlParseError::Syntax(
                "text interleaved with child elements is not allowed".to_string(),
            ));
        }

        Ok((children, text_buf))
    }
}

/// XML 1.0 §2.3 whitespace (the `S` production): only #x20, #x9, #xD, #xA.
/// Deliberately narrower than Rust's Unicode `char::is_whitespace` /
/// `str::trim` so a text node of, e.g., U+00A0 is treated as content (not
/// whitespace) by the mixed-content / comment-truncation guards above.
fn is_xml_space(b: u8) -> bool {
    matches!(b, b' ' | b'\t' | b'\r' | b'\n')
}

// ---------------------------------------------------------------------------
// Entity decoding
// ---------------------------------------------------------------------------

/// Decode the five predefined XML entities.
fn decode_entities(input: &str) -> Result<String, XmlParseError> {
    // Literal characters are held to the same Char production as references.
    if let Some(bad) = input.chars().find(|c| !is_xml_char(*c as u32)) {
        return Err(XmlParseError::Syntax(format!(
            "character U+{:04X} is not allowed in XML 1.0",
            bad as u32
        )));
    }
    let mut result = String::with_capacity(input.len());
    let mut chars = input.chars().peekable();

    while let Some(c) = chars.next() {
        if c == '&' {
            let mut entity = String::new();
            loop {
                match chars.next() {
                    Some(';') => break,
                    Some(ec) => {
                        entity.push(ec);
                        if entity.len() > MAX_ENTITY_NAME_LEN {
                            return Err(XmlParseError::Syntax(
                                "entity name exceeds maximum length".to_string(),
                            ));
                        }
                    }
                    None => {
                        return Err(XmlParseError::Syntax(
                            "unterminated entity reference".to_string(),
                        ));
                    }
                }
            }
            match entity.as_str() {
                "amp" => result.push('&'),
                "lt" => result.push('<'),
                "gt" => result.push('>'),
                "apos" => result.push('\''),
                "quot" => result.push('"'),
                _ if entity.starts_with('#') => {
                    let decoded = decode_char_reference(&entity[1..])?;
                    result.push(decoded);
                }
                _ => {
                    return Err(XmlParseError::Syntax(format!(
                        "unknown entity reference: &{entity};"
                    )));
                }
            }
        } else {
            result.push(c);
        }
    }

    Ok(result)
}

/// The XML 1.0 `Char` production (§2.2).
///
/// Applied to LITERAL characters as well as numeric references: enforcing it
/// only for `&#…;` let a raw C0 control byte (NUL, 0x0B, 0x0C, 0x01-0x08,
/// 0x0E-0x1F) pass straight through in text and attribute values, so the same
/// byte was rejected when escaped and accepted when literal.
fn is_xml_char(code: u32) -> bool {
    matches!(code,
        0x9 | 0xA | 0xD |
        0x20..=0xD7FF |
        0xE000..=0xFFFD |
        0x1_0000..=0x10_FFFF
    )
}

/// Decode a numeric character reference (`#123` or `#xAB`).
///
/// After converting to a `char`, validates that the character is in the
/// XML 1.0 allowed set: `#x9 | #xA | #xD | [#x20-#xD7FF] | [#xE000-#xFFFD] | [#x10000-#x10FFFF]`.
fn decode_char_reference(s: &str) -> Result<char, XmlParseError> {
    let code = if let Some(hex) = s.strip_prefix('x') {
        // SECURITY: `from_str_radix` accepts a leading `+`, but XML 1.0 §4.1
        // forbids a sign in a character reference; require pure hex digits so a
        // non-canonical `&#x+41;` is rejected rather than silently decoded.
        if hex.is_empty() || !hex.bytes().all(|b| b.is_ascii_hexdigit()) {
            return Err(XmlParseError::Syntax(format!(
                "invalid hex char ref: &#x{hex};"
            )));
        }
        u32::from_str_radix(hex, 16)
            .map_err(|_| XmlParseError::Syntax(format!("invalid hex char ref: &#x{hex};")))?
    } else {
        // SECURITY: likewise reject a signed decimal reference such as `&#+65;`.
        if s.is_empty() || !s.bytes().all(|b| b.is_ascii_digit()) {
            return Err(XmlParseError::Syntax(format!(
                "invalid decimal char ref: &#{s};"
            )));
        }
        s.parse::<u32>()
            .map_err(|_| XmlParseError::Syntax(format!("invalid decimal char ref: &#{s};")))?
    };
    let ch = char::from_u32(code)
        .ok_or_else(|| XmlParseError::Syntax(format!("invalid Unicode code point: {code}")))?;

    // Reject characters not allowed in XML 1.0.
    if !is_xml_char(code) {
        return Err(XmlParseError::Syntax(format!(
            "character reference &#x{code:X}; is not allowed in XML 1.0"
        )));
    }

    Ok(ch)
}

// ---------------------------------------------------------------------------
// Public API
// ---------------------------------------------------------------------------

/// Escape special characters for safe embedding in XML attribute values
/// and text content.
///
/// Replaces the five predefined XML entities: `&`, `<`, `>`, `"`, `'`.
///
/// # Security
///
/// This is the correct primitive for interpolating untrusted text into
/// generated XML (e.g. SP metadata): escaping `&`, `<`, `>`, `"`, and `'`
/// prevents the value from breaking out of an element or attribute and
/// injecting markup. It escapes exactly those five characters and performs
/// no other transformation.
///
/// # Examples
///
/// ```
/// use entropy_auth::xml::xml_escape;
///
/// assert_eq!(xml_escape(r#"<a href="x">&'"#), "&lt;a href=&quot;x&quot;&gt;&amp;&apos;");
/// ```
#[must_use]
pub fn xml_escape(s: &str) -> String {
    let mut out = String::with_capacity(s.len());
    for c in s.chars() {
        match c {
            '&' => out.push_str("&amp;"),
            '<' => out.push_str("&lt;"),
            '>' => out.push_str("&gt;"),
            '"' => out.push_str("&quot;"),
            '\'' => out.push_str("&apos;"),
            _ => out.push(c),
        }
    }
    out
}

/// Parse an XML document string into an [`XmlElement`] tree.
///
/// # Errors
///
/// Returns [`XmlParseError`] if the document is malformed, exceeds size
/// or depth limits, or contains disallowed constructs (DTD, CDATA,
/// processing instructions).
pub fn parse_xml(input: &str) -> Result<XmlElement, XmlParseError> {
    // SECURITY: Enforce maximum document size.
    if input.len() > MAX_XML_SIZE {
        return Err(XmlParseError::InputTooLarge);
    }

    let mut parser = Parser::new(input);

    // Skip optional XML declaration.
    parser.skip_xml_declaration()?;
    parser.skip_whitespace();

    // Skip leading comments.
    while parser.starts_with("<!--") {
        parser.skip_comment()?;
        parser.skip_whitespace();
    }

    // SECURITY: Reject DTD declarations at the document level to prevent XXE attacks.
    if parser.starts_with("<!DOCTYPE") {
        return Err(XmlParseError::DtdNotAllowed);
    }

    let element = parser.parse_element(0)?;

    // SECURITY: An XML document has exactly one root element; only whitespace
    // and comments may follow it (XML 1.0 §2.1, the `Misc*` production).
    // Reject any trailing content. Silently dropping it (as a bare
    // `parse_element` does) would let an attacker append a second top-level
    // element — e.g. a second `<saml:Assertion>` or `<Response>` — that this
    // parser ignores but an external XML-DSig verifier canonicalizing the full
    // byte stream would see, opening a signature-wrapping / parser-divergence
    // surface in the SAML unverified-parse path.
    parser.skip_whitespace();
    while parser.starts_with("<!--") {
        parser.skip_comment()?;
        parser.skip_whitespace();
    }
    if !parser.remaining().is_empty() {
        return Err(XmlParseError::Syntax(
            "unexpected content after root element".to_string(),
        ));
    }

    Ok(element)
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;
    use std::fmt::Write as _;

    // -- Simple elements --------------------------------------------------

    #[test]
    fn parse_simple_element() {
        let xml = "<root/>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.name(), "root");
        assert!(el.children().is_empty());
        assert!(el.text_content().is_none());
    }

    #[test]
    fn parse_element_with_text() {
        let xml = "<greeting>hello</greeting>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.name(), "greeting");
        assert_eq!(el.text_content(), Some("hello"));
    }

    // -- Trailing content after the root element --------------------------

    #[test]
    fn trailing_content_after_root_is_rejected() {
        // Only whitespace/comments may follow the root element (XML 1.0 §2.1).
        // A second top-level element must be rejected, not silently dropped —
        // otherwise an appended `<evil/>` is invisible to this parser but seen
        // by an external signature verifier (a wrapping surface).
        assert!(parse_xml("<root/><evil/>").is_err());
        assert!(parse_xml("<root/>junk").is_err());
        assert!(parse_xml("<a>x</a><b>y</b>").is_err());
    }

    #[test]
    fn trailing_whitespace_and_comments_after_root_are_allowed() {
        // Whitespace and comments after the root are part of the legal
        // `Misc*` trailer and must still parse.
        assert!(parse_xml("<root/>\n  ").is_ok());
        assert!(parse_xml("<root/><!-- trailing -->").is_ok());
        assert!(parse_xml("<root/>\n<!-- c -->\n").is_ok());
    }

    #[test]
    fn duplicate_attribute_is_rejected() {
        // XML 1.0 §3.1 WFC: Unique Att Spec. A repeated attribute name is a
        // fatal error, not a first-wins silent drop (XSW surface).
        assert!(parse_xml(r#"<a Recipient="good" Recipient="evil"/>"#).is_err());
        assert!(parse_xml(r#"<a x="1" y="2" x="3"/>"#).is_err());
        // Distinct names still parse.
        assert!(parse_xml(r#"<a x="1" y="2"/>"#).is_ok());
        // A prefixed duplicate collapses to the same local name (the parser
        // strips prefixes and looks up by local name), so it must also be
        // rejected — not let through to a first-wins collision.
        assert!(parse_xml(r#"<a Recipient="A" x:Recipient="B"/>"#).is_err());
    }

    #[test]
    fn duplicate_namespace_declaration_is_rejected() {
        assert!(parse_xml(r#"<a xmlns="urn:1" xmlns="urn:2"/>"#).is_err());
        assert!(parse_xml(r#"<a xmlns:p="urn:1" xmlns:p="urn:2"/>"#).is_err());
        // A default plus a prefixed declaration is fine (different names).
        assert!(parse_xml(r#"<a xmlns="urn:1" xmlns:p="urn:2"/>"#).is_ok());
    }

    #[test]
    fn malformed_element_names_are_rejected() {
        // XML Name / QName well-formedness: closes a parser-divergence surface.
        assert!(parse_xml("<:Audience/>").is_err()); // empty prefix
        assert!(parse_xml("<Audience:/>").is_err()); // empty local part
        assert!(parse_xml("<a:b:c/>").is_err()); // multiple colons
        assert!(parse_xml("<1abc/>").is_err()); // leading digit
        assert!(parse_xml("<-x/>").is_err()); // leading hyphen
        // Well-formed names (incl. a single namespace prefix) still parse.
        assert!(parse_xml("<saml:Assertion/>").is_ok());
        assert!(parse_xml("<_foo/>").is_ok());
    }

    #[test]
    fn declaration_with_tab_separator_is_skipped() {
        // XML 1.0 §2.8 allows any whitespace after `<?xml`, not just a space.
        let el = parse_xml("<?xml\tversion=\"1.0\"?><root/>").unwrap();
        assert_eq!(el.name(), "root");
    }

    // -- Comment-truncation defense (CVE-2018-0489 class) -----------------

    #[test]
    fn comment_interleaved_with_text_is_rejected() {
        // The classic SAML comment-truncation payload: a comment splitting
        // a text node must NOT silently concatenate to "good@x.evil".
        let xml = "<a>good@x<!---->.evil</a>";
        assert!(
            parse_xml(xml).is_err(),
            "comment inside text content must be rejected, not merged",
        );
        // Leading/trailing comment around text is equally rejected.
        assert!(parse_xml("<a>x<!-- c --></a>").is_err());
        assert!(parse_xml("<a><!-- c -->x</a>").is_err());
    }

    #[test]
    fn text_interleaved_with_child_elements_is_rejected() {
        // Element-interleaved sibling of the comment-truncation case: a child
        // element splitting a text node must not silently concatenate to
        // "good@evil.com" while a DSig canonicalizer sees text + element.
        assert!(
            parse_xml("<NameID>good@evil.com<x/></NameID>").is_err(),
            "text alongside a child element must be rejected, not merged",
        );
        assert!(parse_xml("<a><x/>trailing</a>").is_err());
        assert!(parse_xml("<a>lead<x/></a>").is_err());
    }

    #[test]
    fn non_xml_whitespace_text_is_not_treated_as_whitespace() {
        // The mixed-content guard uses XML 1.0 §2.3 whitespace (#x20 #x9 #xD
        // #xA), NOT Rust's Unicode `trim`. A text node of only U+00A0
        // (no-break space) is content, so mixing it with a child element must
        // be rejected — a Unicode `trim().is_empty()` guard would wrongly pass.
        assert!(
            parse_xml("<a>\u{A0}<x/></a>").is_err(),
            "U+00A0 is XML content, not whitespace, and must not slip past the guard",
        );
        // Same for the comment-truncation guard.
        assert!(parse_xml("<a>\u{A0}<!-- c --></a>").is_err());
    }

    #[test]
    fn whitespace_between_child_elements_is_allowed() {
        // Whitespace (indentation/newlines) between children is not "text" and
        // must stay allowed — every real SAML document relies on this.
        let xml = "<root>\n  <a/>\n  <b/>\n</root>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.children().len(), 2);
    }

    #[test]
    fn comment_between_child_elements_is_allowed() {
        // A comment with no sibling text is harmless and stays allowed.
        let xml = "<root><a/><!-- between --><b/></root>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.children().len(), 2);
        assert!(el.text_content().is_none());
    }

    // -- Nested elements --------------------------------------------------

    #[test]
    fn parse_nested_elements() {
        let xml = "<root><child1/><child2>text</child2></root>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.children().len(), 2);
        assert_eq!(el.children()[0].name(), "child1");
        assert_eq!(el.children()[1].name(), "child2");
        assert_eq!(el.children()[1].text_content(), Some("text"));
    }

    #[test]
    fn parse_deeply_nested() {
        let xml = "<a><b><c><d>deep</d></c></b></a>";
        let el = parse_xml(xml).unwrap();
        let d = el
            .find_child("b")
            .unwrap()
            .find_child("c")
            .unwrap()
            .find_child("d")
            .unwrap();
        assert_eq!(d.text_content(), Some("deep"));
    }

    // -- Attributes -------------------------------------------------------

    #[test]
    fn parse_attributes() {
        let xml = r#"<tag id="123" class="main"/>"#;
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.attribute("id"), Some("123"));
        assert_eq!(el.attribute("class"), Some("main"));
    }

    #[test]
    fn parse_single_quoted_attributes() {
        let xml = "<tag attr='value'/>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.attribute("attr"), Some("value"));
    }

    // -- Namespaces -------------------------------------------------------

    #[test]
    fn parse_default_namespace() {
        let xml = r#"<root xmlns="urn:example">text</root>"#;
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.name(), "root");
        assert_eq!(el.namespace(), Some("urn:example"));
    }

    #[test]
    fn parse_prefixed_namespace() {
        let xml = r#"<saml:Assertion xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion"/>"#;
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.name(), "Assertion");
        assert_eq!(
            el.namespace(),
            Some("urn:oasis:names:tc:SAML:2.0:assertion")
        );
    }

    #[test]
    fn find_child_ns() {
        let xml = r#"<root xmlns:saml="urn:oasis:names:tc:SAML:2.0:assertion"><saml:Issuer>idp</saml:Issuer><other>x</other></root>"#;
        let el = parse_xml(xml).unwrap();
        let issuer = el
            .find_child_ns("urn:oasis:names:tc:SAML:2.0:assertion", "Issuer")
            .unwrap();
        assert_eq!(issuer.text_content(), Some("idp"));
    }

    // -- Entity decoding --------------------------------------------------

    #[test]
    fn decode_xml_entities() {
        let xml = "<tag>&amp; &lt; &gt; &apos; &quot;</tag>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.text_content(), Some("& < > ' \""));
    }

    #[test]
    fn decode_numeric_entities() {
        let xml = "<tag>&#65;&#x42;</tag>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.text_content(), Some("AB"));
    }

    #[test]
    fn entity_in_attribute() {
        let xml = r#"<tag val="a&amp;b"/>"#;
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.attribute("val"), Some("a&b"));
    }

    #[test]
    fn reject_unknown_entity() {
        // Only the five predefined entities (plus numeric refs) are allowed;
        // an undefined named entity is rejected, not silently dropped.
        let err = parse_xml("<tag>&nbsp;</tag>").unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn reject_unterminated_entity() {
        // `&` with no closing `;` before end of input.
        let err = parse_xml("<tag>&amp</tag>").unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn reject_overlong_entity_name() {
        // An entity name longer than MAX_ENTITY_NAME_LEN is rejected before
        // it can be used to amplify work.
        let long = "a".repeat(MAX_ENTITY_NAME_LEN + 1);
        let err = parse_xml(&format!("<tag>&{long};</tag>")).unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn reject_out_of_range_numeric_char_ref() {
        // Code point beyond U+10FFFF: char::from_u32 fails.
        let err = parse_xml("<tag>&#x110000;</tag>").unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
        // Overflows u32 entirely.
        let err = parse_xml("<tag>&#99999999999;</tag>").unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn reject_signed_numeric_char_ref() {
        // XML 1.0 §4.1 forbids a sign in a character reference; a leading `+`
        // (which Rust's integer parsing would otherwise accept) must be
        // rejected rather than silently decoded to its unsigned value.
        for input in ["<t>&#x+41;</t>", "<t>&#+65;</t>", "<t>&#x-41;</t>"] {
            let err = parse_xml(input).unwrap_err();
            assert!(matches!(err, XmlParseError::Syntax(_)), "input: {input}");
        }
    }

    #[test]
    fn multibyte_text_and_attribute_round_trip() {
        // The parser advances by char::len_utf8(); a regression that stepped by
        // a single byte would panic only on multi-byte content. Pin it.
        let doc = parse_xml("<a x=\"café\">naïve—€</a>").unwrap();
        assert_eq!(doc.attribute("x"), Some("café"));
        assert_eq!(doc.text_content(), Some("naïve—€"));
    }

    #[test]
    fn reject_disallowed_control_char_ref() {
        // NUL and other C0 controls are valid Unicode scalars but not allowed
        // in XML 1.0 text.
        let err = parse_xml("<tag>&#x0;</tag>").unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
        let err = parse_xml("<tag>&#x8;</tag>").unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn reject_excessive_attribute_count() {
        // More than MAX_ATTRIBUTES attributes on one element is rejected.
        let mut xml = String::from("<r");
        for i in 0..=MAX_ATTRIBUTES {
            write!(xml, " a{i}=\"v\"").unwrap();
        }
        xml.push_str("/>");
        let err = parse_xml(&xml).unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    // -- Security: DTD rejection ------------------------------------------

    #[test]
    fn reject_dtd_declaration() {
        // SECURITY: DTD declarations must be rejected to prevent XXE attacks.
        let xml = "<!DOCTYPE foo [<!ENTITY xxe SYSTEM 'file:///etc/passwd'>]><root/>";
        let err = parse_xml(xml).unwrap_err();
        assert_eq!(err, XmlParseError::DtdNotAllowed);
    }

    #[test]
    fn reject_dtd_after_xml_declaration() {
        let xml = "<?xml version=\"1.0\"?><!DOCTYPE foo><root/>";
        let err = parse_xml(xml).unwrap_err();
        assert_eq!(err, XmlParseError::DtdNotAllowed);
    }

    // -- Security: processing instruction rejection -----------------------

    #[test]
    fn reject_processing_instruction_in_content() {
        // SECURITY: Processing instructions are not allowed.
        let xml = "<root><?php echo 'hi'; ?></root>";
        let err = parse_xml(xml).unwrap_err();
        assert_eq!(err, XmlParseError::ProcessingInstructionNotAllowed);
    }

    // -- Security: CDATA rejection ----------------------------------------

    #[test]
    fn reject_cdata() {
        // SECURITY: CDATA sections are not allowed.
        let xml = "<root><![CDATA[data]]></root>";
        let err = parse_xml(xml).unwrap_err();
        assert_eq!(err, XmlParseError::CdataNotAllowed);
    }

    // -- Security: depth limit --------------------------------------------

    /// Builds `<d0>…<dN-1></dN-1>…</d0>` nesting exactly `levels` elements.
    fn nested_xml(levels: usize) -> String {
        let open = (0..levels).fold(String::new(), |mut acc, i| {
            write!(acc, "<d{i}>").unwrap();
            acc
        });
        let close = (0..levels).rev().fold(String::new(), |mut acc, i| {
            write!(acc, "</d{i}>").unwrap();
            acc
        });
        format!("{open}{close}")
    }

    #[test]
    fn reject_excessive_depth() {
        let err = parse_xml(&nested_xml(MAX_XML_DEPTH + 1)).unwrap_err();
        assert_eq!(err, XmlParseError::MaxDepthExceeded);
    }

    #[test]
    fn accept_exactly_max_depth() {
        // Exactly MAX_XML_DEPTH elements (deepest at depth MAX_XML_DEPTH - 1)
        // must parse; MAX_XML_DEPTH + 1 must not. This pins the boundary.
        assert!(parse_xml(&nested_xml(MAX_XML_DEPTH)).is_ok());
    }

    // -- Security: size limit ---------------------------------------------

    #[test]
    fn reject_oversized_input() {
        let xml = format!("<r>{}</r>", "x".repeat(MAX_XML_SIZE + 1));
        let err = parse_xml(&xml).unwrap_err();
        assert_eq!(err, XmlParseError::InputTooLarge);
    }

    // -- XML declaration skipping -----------------------------------------

    #[test]
    fn skip_xml_declaration() {
        let xml = "<?xml version=\"1.0\" encoding=\"UTF-8\"?><root>ok</root>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.name(), "root");
        assert_eq!(el.text_content(), Some("ok"));
    }

    // -- Comments ---------------------------------------------------------

    #[test]
    fn skip_comments() {
        let xml = "<!-- comment --><root><!-- inner --><child/></root>";
        let el = parse_xml(xml).unwrap();
        assert_eq!(el.name(), "root");
        assert_eq!(el.children().len(), 1);
    }

    // -- find_children ----------------------------------------------------

    #[test]
    fn find_children_multiple() {
        let xml = "<root><item>a</item><item>b</item><other/></root>";
        let el = parse_xml(xml).unwrap();
        let items = el.find_children("item");
        assert_eq!(items.len(), 2);
        assert_eq!(items[0].text_content(), Some("a"));
        assert_eq!(items[1].text_content(), Some("b"));
    }

    // -- Error cases ------------------------------------------------------

    #[test]
    fn mismatched_tags() {
        let xml = "<a></b>";
        let err = parse_xml(xml).unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn unterminated_element() {
        let xml = "<a>";
        let err = parse_xml(xml).unwrap_err();
        assert!(matches!(err, XmlParseError::Syntax(_)));
    }

    #[test]
    fn rejects_raw_markup_and_controls() {
        // XML 1.0 §3.1 WFC: no literal `<` in an attribute value.
        assert!(parse_xml(r#"<a b="x<y"/>"#).is_err());
        // §2.2 Char: a literal C0 control is invalid whether or not escaped.
        assert!(parse_xml("<a>\u{0}</a>").is_err());
        assert!(parse_xml("<a b=\"\u{b}\"/>").is_err());
        // The escaped form was already rejected; both must agree.
        assert!(parse_xml("<a>&#x0;</a>").is_err());
    }

    #[test]
    fn normalizes_literal_whitespace_in_attribute_values() {
        // §3.3.3: a LITERAL tab/newline/CR becomes a single space...
        let doc = parse_xml("<a b=\"x\ty\nz\"/>").unwrap();
        assert_eq!(doc.attribute("b"), Some("x y z"));
        // ...but a character REFERENCE survives verbatim.
        let doc = parse_xml(r#"<a b="x&#xA;y"/>"#).unwrap();
        assert_eq!(doc.attribute("b"), Some("x\ny"));
    }
}