xml-sec 0.1.23

//! Converts XML strings into a DOM structure
//!
//! ### Example
//!
//! ```
//! # #[cfg(not(feature = "embedded"))]
//! # {
//! use sxd_document_no_unsafe::parser;
//! let xml = r#"<?xml version="1.0"?>
//! <!-- Awesome data incoming -->
//! <data awesome="true">
//!   <datum>Science</datum>
//!   <datum><![CDATA[Literature]]></datum>
//!   <datum>Math &gt; others</datum>
//! </data>"#;
//! let doc = parser::parse(xml).expect("Failed to parse");
//! # }
//! ```

use std::{
    char,
    collections::{BTreeSet, HashMap},
    error, fmt,
    ops::Deref,
};

use peresil::{self, ParseMaster, Recoverable, StringPoint};

use self::Reference::*;

use super::{PrefixedName, QName, dom, str::XmlStr};

#[cfg(feature = "no-unsafe")]
use crate::string_pool::InternedString;

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum SpecificError {
    Expected(&'static str),

    ExpectedAttribute,
    ExpectedAttributeValue,

    ExpectedCData,

    ExpectedCharacterData,

    ExpectedComment,
    ExpectedCommentBody,

    ExpectedElement,
    ExpectedElementName,
    ExpectedElementEnd,
    ExpectedElementSelfClosed,

    ExpectedProcessingInstruction,
    ExpectedProcessingInstructionTarget,
    ExpectedProcessingInstructionValue,

    ExpectedVersionNumber,
    ExpectedEncoding,
    ExpectedYesNo,
    ExpectedWhitespace,

    ExpectedDocumentTypeName,
    ExpectedIntSubset,
    ExpectedSystemLiteral,

    ExpectedClosingQuote(&'static str),
    ExpectedOpeningQuote(&'static str),

    ExpectedDecimalReferenceValue,
    ExpectedHexReferenceValue,
    ExpectedNamedReferenceValue,

    ExpectedDecimalReference,
    ExpectedHexReference,
    ExpectedNamedReference,

    InvalidProcessingInstructionTarget,
    MismatchedElementEndName,

    InvalidDecimalReference,
    InvalidHexReference,
    UnknownNamedReference,

    DuplicateAttribute,
    RedefinedNamespace,
    RedefinedDefaultNamespace,
    EmptyNamespace,
    UnknownNamespacePrefix,
    UnclosedElement,
}

impl Recoverable for SpecificError {
    fn recoverable(&self) -> bool {
        use self::SpecificError::*;

        !matches!(
            self,
            ExpectedEncoding
                | ExpectedYesNo
                | InvalidProcessingInstructionTarget
                | MismatchedElementEndName
                | InvalidDecimalReference
                | InvalidHexReference
                | UnknownNamedReference
                | DuplicateAttribute
                | RedefinedNamespace
                | RedefinedDefaultNamespace
                | EmptyNamespace
                | UnknownNamespacePrefix
                | UnclosedElement
        )
    }
}

impl fmt::Display for SpecificError {
    #[allow(deprecated)]
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        use self::{SpecificError::*, error::Error};

        match *self {
            Expected(s) | ExpectedClosingQuote(s) | ExpectedOpeningQuote(s) => {
                write!(f, "Parser error: {} {}", self.description(), s)
            }
            _ => write!(f, "Parser error: {}", self.description()),
        }
    }
}

impl error::Error for SpecificError {
    fn description(&self) -> &str {
        use self::SpecificError::*;

        match *self {
            Expected(_) => "expected",
            ExpectedAttribute => "expected attribute",
            ExpectedAttributeValue => "expected attribute value",
            ExpectedCData => "expected CDATA",
            ExpectedCharacterData => "expected character data",
            ExpectedComment => "expected comment",
            ExpectedCommentBody => "expected comment body",
            ExpectedElement => "expected element",
            ExpectedElementName => "expected element name",
            ExpectedElementEnd => "expected element end",
            ExpectedElementSelfClosed => "expected element self closed",
            ExpectedProcessingInstruction => "expected processing instruction",
            ExpectedProcessingInstructionTarget => "expected processing instruction target",
            ExpectedProcessingInstructionValue => "expected processing instruction value",
            ExpectedVersionNumber => "expected version number",
            ExpectedEncoding => "expected encoding",
            ExpectedYesNo => "expected yes or no",
            ExpectedWhitespace => "expected whitespace",
            ExpectedDocumentTypeName => "expected document type name",
            ExpectedIntSubset => "expected int subset",
            ExpectedSystemLiteral => "expected system literal",
            ExpectedClosingQuote(_) => "expected closing quote",
            ExpectedOpeningQuote(_) => "expected opening quote",
            ExpectedDecimalReferenceValue => "expected decimal reference value",
            ExpectedHexReferenceValue => "expected hex reference value",
            ExpectedNamedReferenceValue => "expected named reference value",
            ExpectedDecimalReference => "expected decimal reference",
            ExpectedHexReference => "expected hex reference",
            ExpectedNamedReference => "expected named reference",
            InvalidProcessingInstructionTarget => "invalid processing instruction target",
            MismatchedElementEndName => "mismatched element end name",
            InvalidDecimalReference => "invalid decimal reference",
            InvalidHexReference => "invalid hex reference",
            UnknownNamedReference => "unknown named reference",
            DuplicateAttribute => "duplicate attribute",
            RedefinedNamespace => "redefined namespace",
            RedefinedDefaultNamespace => "redefined default namespace",
            EmptyNamespace => "empty namespace",
            UnknownNamespacePrefix => "unknown namespace prefix",
            UnclosedElement => "unclosed element",
        }
    }
}

type XmlMaster<'a> = peresil::ParseMaster<StringPoint<'a>, SpecificError>;
type XmlProgress<'a, T> = peresil::Progress<StringPoint<'a>, T, SpecificError>;

fn success<T>(data: T, point: StringPoint<'_>) -> XmlProgress<'_, T> {
    peresil::Progress {
        point,
        status: peresil::Status::Success(data),
    }
}

/// A truncated point; the string ends before the end of input
#[derive(Debug, Copy, Clone)]
struct Span<T> {
    offset: usize,
    value: T,
}

impl<T> Span<T> {
    // Should this just be the return type of the parser methods?
    fn parse<'a, F>(pt: StringPoint<'a>, f: F) -> XmlProgress<'a, Span<T>>
    where
        F: Fn(StringPoint<'a>) -> XmlProgress<'a, T>,
    {
        let (after, v) = try_parse!(f(pt));
        let span = Span {
            value: v,
            offset: pt.offset,
        };
        peresil::Progress {
            status: peresil::Status::Success(span),
            point: after,
        }
    }

    fn map<F, U>(self, f: F) -> Span<U>
    where
        F: FnOnce(T) -> U,
    {
        Span {
            value: f(self.value),
            offset: self.offset,
        }
    }
}

#[derive(Debug, Copy, Clone)]
enum Reference<'a> {
    Entity(Span<&'a str>),
    DecimalChar(Span<&'a str>),
    HexChar(Span<&'a str>),
}

/// Common reusable XML parsing methods
pub trait XmlParseExt<'a> {
    /// Parse XML whitespace
    fn consume_space(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()>;
    /// Parse XML decimal characters
    fn consume_decimal_chars(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()>;
    /// Parse an XML [NCName](http://www.w3.org/TR/REC-xml-names/#NT-NCName)
    fn consume_ncname(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()>;
    /// Parse an XML [prefixed name](http://www.w3.org/TR/REC-xml-names/#NT-QName)
    fn consume_prefixed_name(&self) -> peresil::Progress<StringPoint<'a>, PrefixedName<'a>, ()>;
}

impl<'a> XmlParseExt<'a> for StringPoint<'a> {
    fn consume_space(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()> {
        self.consume_to(self.s.end_of_space())
    }

    fn consume_decimal_chars(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()> {
        self.consume_to(self.s.end_of_decimal_chars())
    }

    fn consume_ncname(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()> {
        self.consume_to(self.s.end_of_ncname())
    }

    fn consume_prefixed_name(&self) -> peresil::Progress<StringPoint<'a>, PrefixedName<'a>, ()> {
        fn parse_local(xml: StringPoint<'_>) -> peresil::Progress<StringPoint<'_>, &str, ()> {
            let (xml, _) = try_parse!(xml.consume_literal(":"));
            xml.consume_ncname()
        }

        let (xml, prefix) = try_parse!(self.consume_ncname());
        let (xml, local) = parse_local(xml).optional(xml);

        let name = match local {
            Some(local) => PrefixedName::with_prefix(Some(prefix), local),
            None => PrefixedName::new(prefix),
        };

        peresil::Progress {
            point: xml,
            status: peresil::Status::Success(name),
        }
    }
}

trait PrivateXmlParseExt<'a> {
    fn consume_attribute_value(&self, quote: &str) -> XmlProgress<'a, &'a str>;
    fn consume_name(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()>;
    fn consume_hex_chars(&self) -> XmlProgress<'a, &'a str>;
    fn consume_char_data(&self) -> XmlProgress<'a, &'a str>;
    fn consume_cdata(&self) -> XmlProgress<'a, &'a str>;
    fn consume_int_subset(&self) -> XmlProgress<'a, &'a str>;
    fn consume_comment(&self) -> XmlProgress<'a, &'a str>;
    fn consume_pi_value(&self) -> XmlProgress<'a, &'a str>;
    fn consume_start_tag(&self) -> XmlProgress<'a, &'a str>;
    fn consume_encoding(&self) -> XmlProgress<'a, &'a str>;
}

impl<'a> PrivateXmlParseExt<'a> for StringPoint<'a> {
    fn consume_attribute_value(&self, quote: &str) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_attribute(quote))
            .map_err(|_| SpecificError::ExpectedAttributeValue)
    }

    fn consume_name(&self) -> peresil::Progress<StringPoint<'a>, &'a str, ()> {
        self.consume_to(self.s.end_of_name())
    }

    fn consume_hex_chars(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_hex_chars())
            .map_err(|_| SpecificError::ExpectedHexReferenceValue)
    }

    fn consume_char_data(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_char_data())
            .map_err(|_| SpecificError::ExpectedCharacterData)
    }

    fn consume_cdata(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_cdata())
            .map_err(|_| SpecificError::ExpectedCData)
    }

    fn consume_int_subset(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_int_subset())
            .map_err(|_| SpecificError::ExpectedIntSubset)
    }

    fn consume_comment(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_comment())
            .map_err(|_| SpecificError::ExpectedCommentBody)
    }

    fn consume_pi_value(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_pi_value())
            .map_err(|_| SpecificError::ExpectedProcessingInstructionValue)
    }

    fn consume_start_tag(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_start_tag())
            .map_err(|_| SpecificError::ExpectedElement)
    }

    fn consume_encoding(&self) -> XmlProgress<'a, &'a str> {
        self.consume_to(self.s.end_of_encoding())
            .map_err(|_| SpecificError::ExpectedEncoding)
    }
}

trait X<'a> {
    fn expect_space(&self) -> XmlProgress<'a, &'a str>;
    fn expect_literal(&self, s: &'static str) -> XmlProgress<'a, &'a str>;
}

impl<'a> X<'a> for StringPoint<'a> {
    fn expect_space(&self) -> XmlProgress<'a, &'a str> {
        self.consume_space()
            .map_err(|_| SpecificError::ExpectedWhitespace)
    }

    fn expect_literal(&self, s: &'static str) -> XmlProgress<'a, &'a str> {
        self.consume_literal(s)
            .map_err(|_| SpecificError::Expected(s))
    }
}

#[derive(Debug, Copy, Clone)]
enum Token<'a> {
    XmlDeclaration,
    DocumentTypeDeclaration,
    Comment(&'a str),
    ProcessingInstruction(&'a str, Option<&'a str>),
    Whitespace(#[allow(dead_code)] &'a str),
    ElementStart(Span<PrefixedName<'a>>),
    ElementStartClose,
    ElementSelfClose,
    ElementClose(Span<PrefixedName<'a>>),
    AttributeStart(Span<PrefixedName<'a>>, &'static str),
    AttributeEnd,
    LiteralAttributeValue(&'a str),
    ReferenceAttributeValue(Reference<'a>),
    CharData(&'a str),
    CData(&'a str),
    ContentReference(Reference<'a>),
}

#[derive(Debug, Copy, Clone)]
enum State {
    AtBeginning,
    AfterDeclaration,
    AfterElementStart(usize),
    AfterAttributeStart(usize, &'static str),
    Content(usize),
    AfterMainElement,
}

#[derive(Debug)]
struct PullParser<'a> {
    pm: XmlMaster<'a>,
    xml: StringPoint<'a>,
    state: State,
}

impl<'a> PullParser<'a> {
    fn new(xml: &str) -> PullParser<'_> {
        PullParser {
            pm: ParseMaster::new(),
            xml: StringPoint::new(xml),
            state: State::AtBeginning,
        }
    }
}

fn parse_comment<'a>(xml: StringPoint<'a>) -> XmlProgress<'a, Token<'a>> {
    let (xml, _) = try_parse!(
        xml.consume_literal("<!--")
            .map_err(|_| SpecificError::ExpectedComment)
    );
    let (xml, text) = try_parse!(xml.consume_comment());
    let (xml, _) = try_parse!(xml.expect_literal("-->"));

    success(Token::Comment(text), xml)
}

fn parse_one_quoted_value<'a, T, F>(
    xml: StringPoint<'a>,
    quote: &'static str,
    f: F,
) -> XmlProgress<'a, T>
where
    F: FnMut(StringPoint<'a>) -> XmlProgress<'a, T>,
{
    let mut f = f;
    let (xml, _) = try_parse!(
        xml.consume_literal(quote)
            .map_err(|_| SpecificError::ExpectedOpeningQuote(quote))
    );
    let (xml, value) = try_parse!(f(xml));
    let (xml, _) = try_parse!(
        xml.consume_literal(quote)
            .map_err(|_| SpecificError::ExpectedClosingQuote(quote))
    );

    success(value, xml)
}

fn parse_quoted_value<'a, T, F>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
    f: F,
) -> XmlProgress<'a, T>
where
    F: FnMut(&mut XmlMaster<'a>, StringPoint<'a>, &str) -> XmlProgress<'a, T>,
{
    let mut f = f;
    pm.alternate()
        .one(|pm| parse_one_quoted_value(xml, "'", |xml| f(pm, xml, "'")))
        .one(|pm| parse_one_quoted_value(xml, "\"", |xml| f(pm, xml, "\"")))
        .finish()
}

fn parse_eq(xml: StringPoint<'_>) -> XmlProgress<'_, ()> {
    let (xml, _) = xml.consume_space().optional(xml);
    let (xml, _) = try_parse!(xml.expect_literal("="));
    let (xml, _) = xml.consume_space().optional(xml);

    success((), xml)
}

fn parse_version_info<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, &'a str> {
    fn version_num(xml: StringPoint<'_>) -> peresil::Progress<StringPoint<'_>, &str, ()> {
        let start_point = xml;

        let (xml, _) = try_parse!(xml.consume_literal("1."));
        let (xml, _) = try_parse!(xml.consume_decimal_chars());

        peresil::Progress::success(xml, start_point.to(xml))
    }

    let (xml, _) = try_parse!(xml.expect_space());
    let (xml, _) = try_parse!(xml.expect_literal("version"));
    let (xml, _) = try_parse!(parse_eq(xml));
    let (xml, version) = try_parse!(parse_quoted_value(pm, xml, |_, xml, _| version_num(xml)
        .map_err(|_| SpecificError::ExpectedVersionNumber)));

    success(version, xml)
}

fn parse_encoding_declaration<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, &'a str> {
    let (xml, _) = try_parse!(xml.expect_space());
    let (xml, _) = try_parse!(xml.expect_literal("encoding"));
    let (xml, _) = try_parse!(parse_eq(xml));
    let (xml, encoding) =
        try_parse!(parse_quoted_value(pm, xml, |_, xml, _| xml.consume_encoding()));

    success(encoding, xml)
}

fn parse_standalone_declaration<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, &'a str> {
    let (xml, _) = try_parse!(xml.expect_space());
    let (xml, _) = try_parse!(xml.expect_literal("standalone"));
    let (xml, _) = try_parse!(parse_eq(xml));
    let (xml, standalone) = try_parse!(parse_quoted_value(pm, xml, |pm, xml, _| {
        pm.alternate()
            .one(|_| xml.expect_literal("yes"))
            .one(|_| xml.expect_literal("no"))
            .finish()
            .map_err(|_| SpecificError::ExpectedYesNo)
    }));

    success(standalone, xml)
}

fn parse_xml_declaration<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, Token<'a>> {
    let (xml, _) = try_parse!(xml.expect_literal("<?xml"));
    let (xml, _version) = try_parse!(parse_version_info(pm, xml));
    let (xml, _encoding) =
        try_parse!(pm.optional(xml, |pm, xml| { parse_encoding_declaration(pm, xml) }));
    let (xml, _standalone) =
        try_parse!(pm.optional(xml, |pm, xml| { parse_standalone_declaration(pm, xml) }));
    let (xml, _) = xml.consume_space().optional(xml);
    let (xml, _) = try_parse!(xml.expect_literal("?>"));

    success(Token::XmlDeclaration, xml)
}

/* only the SYSTEM variant */
fn parse_external_id<'a>(pm: &mut XmlMaster<'a>, xml: StringPoint<'a>) -> XmlProgress<'a, &'a str> {
    let (xml, _) = try_parse!(xml.expect_space());
    let (xml, _) = try_parse!(xml.expect_literal("SYSTEM"));
    let (xml, _) = try_parse!(xml.expect_space());
    let (xml, external_id) = try_parse!(parse_quoted_value(pm, xml, |_, xml, quote| xml
        .consume_attribute_value(quote)
        .map_err(|_| SpecificError::ExpectedSystemLiteral)));

    success(external_id, xml)
}

fn parse_int_subset<'a>(_pm: &mut XmlMaster<'a>, xml: StringPoint<'a>) -> XmlProgress<'a, &'a str> {
    let (xml, _) = try_parse!(xml.expect_literal("["));
    let (xml, _) = xml.consume_space().optional(xml);
    let (xml, elements) = try_parse!(
        xml.consume_int_subset()
            .map_err(|_| SpecificError::ExpectedIntSubset)
    );
    let (xml, _) = xml.consume_space().optional(xml);
    let (xml, _) = try_parse!(xml.expect_literal("]"));
    let (xml, _) = xml.consume_space().optional(xml);

    success(elements, xml)
}

fn parse_document_type_declaration<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, Token<'a>> {
    let (xml, _) = try_parse!(xml.expect_literal("<!DOCTYPE"));
    let (xml, _) = try_parse!(xml.expect_space());
    let (xml, _type_name) = try_parse!(
        xml.consume_name()
            .map_err(|_| SpecificError::ExpectedDocumentTypeName)
    );
    let (xml, _id) = try_parse!(pm.optional(xml, |p, x| parse_external_id(p, x)));
    let (xml, _) = xml.consume_space().optional(xml);
    let (xml, _int_subset) = try_parse!(pm.optional(xml, |p, x| parse_int_subset(p, x)));
    let (xml, _) = try_parse!(xml.expect_literal(">"));

    success(Token::DocumentTypeDeclaration, xml)
}

fn parse_pi_value(xml: StringPoint<'_>) -> XmlProgress<'_, &str> {
    let (xml, _) = try_parse!(xml.expect_space());
    xml.consume_pi_value()
}

fn parse_pi<'a>(xml: StringPoint<'a>) -> XmlProgress<'a, Token<'a>> {
    let (xml, _) = try_parse!(
        xml.consume_literal("<?")
            .map_err(|_| SpecificError::ExpectedProcessingInstruction)
    );
    let target_xml = xml;
    let (xml, target) = try_parse!(
        xml.consume_name()
            .map_err(|_| SpecificError::ExpectedProcessingInstructionTarget)
    );
    let (xml, value) = parse_pi_value(xml).optional(xml);
    let (xml, _) = try_parse!(xml.expect_literal("?>"));

    if target.eq_ignore_ascii_case("xml") {
        return peresil::Progress::failure(
            target_xml,
            SpecificError::InvalidProcessingInstructionTarget,
        );
    }

    success(Token::ProcessingInstruction(target, value), xml)
}

fn parse_element_start(xml: StringPoint<'_>) -> XmlProgress<'_, Token<'_>> {
    let (xml, _) = try_parse!(xml.consume_start_tag());
    let (xml, name) = try_parse!(Span::parse(xml, |xml| xml
        .consume_prefixed_name()
        .map_err(|_| SpecificError::ExpectedElementName)));

    success(Token::ElementStart(name), xml)
}

fn parse_element_start_close(xml: StringPoint<'_>) -> XmlProgress<'_, Token<'_>> {
    let (xml, _) = xml.expect_space().optional(xml);

    xml.consume_literal(">")
        .map(|_| Token::ElementStartClose)
        .map_err(|_| SpecificError::ExpectedElementEnd)
}

fn parse_element_self_close(xml: StringPoint<'_>) -> XmlProgress<'_, Token<'_>> {
    let (xml, _) = xml.expect_space().optional(xml);

    xml.consume_literal("/>")
        .map(|_| Token::ElementSelfClose)
        .map_err(|_| SpecificError::ExpectedElementSelfClosed)
}

fn parse_element_close(xml: StringPoint<'_>) -> XmlProgress<'_, Token<'_>> {
    let (xml, _) = try_parse!(xml.expect_literal("</"));

    let (xml, name) = try_parse!(Span::parse(xml, |xml| xml
        .consume_prefixed_name()
        .map_err(|_| SpecificError::ExpectedElementName)));

    let (xml, _) = xml.consume_space().optional(xml);
    let (xml, _) = try_parse!(xml.expect_literal(">"));

    success(Token::ElementClose(name), xml)
}

const QUOT: &str = r#"""#;
const APOS: &str = r#"'"#;

fn parse_attribute_start<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, Token<'a>> {
    let (xml, _) = try_parse!(xml.expect_space());

    let (xml, name) = try_parse!(Span::parse(xml, |xml| xml
        .consume_prefixed_name()
        .map_err(|_| SpecificError::ExpectedAttribute)));

    let (xml, _) = try_parse!(parse_eq(xml));

    let (xml, q) = try_parse!(
        pm.alternate()
            .one(|_| xml
                .expect_literal(QUOT)
                .map_err(|_| SpecificError::ExpectedOpeningQuote(QUOT)))
            .one(|_| xml
                .expect_literal(APOS)
                .map_err(|_| SpecificError::ExpectedOpeningQuote(APOS)))
            .finish()
    );

    let q = if q == QUOT { QUOT } else { APOS };

    success(Token::AttributeStart(name, q), xml)
}

fn parse_attribute_end<'a>(
    xml: StringPoint<'a>,
    quote: &'static str,
) -> XmlProgress<'a, Token<'a>> {
    xml.consume_literal(quote)
        .map(|_| Token::AttributeEnd)
        .map_err(|_| SpecificError::ExpectedClosingQuote(quote))
}

fn parse_attribute_literal<'a>(xml: StringPoint<'a>, quote: &str) -> XmlProgress<'a, Token<'a>> {
    let (xml, val) = try_parse!(xml.consume_attribute_value(quote));

    success(Token::LiteralAttributeValue(val), xml)
}

fn parse_entity_ref(xml: StringPoint<'_>) -> XmlProgress<'_, Reference<'_>> {
    let (xml, _) = try_parse!(
        xml.consume_literal("&")
            .map_err(|_| SpecificError::ExpectedNamedReference)
    );
    let (xml, name) = try_parse!(Span::parse(xml, |xml| xml
        .consume_name()
        .map_err(|_| SpecificError::ExpectedNamedReferenceValue)));
    let (xml, _) = try_parse!(xml.expect_literal(";"));

    success(Entity(name), xml)
}

fn parse_decimal_char_ref(xml: StringPoint<'_>) -> XmlProgress<'_, Reference<'_>> {
    let (xml, _) = try_parse!(
        xml.consume_literal("&#")
            .map_err(|_| SpecificError::ExpectedDecimalReference)
    );
    let (xml, dec) = try_parse!(Span::parse(xml, |xml| xml
        .consume_decimal_chars()
        .map_err(|_| SpecificError::ExpectedDecimalReferenceValue)));
    let (xml, _) = try_parse!(xml.expect_literal(";"));

    success(DecimalChar(dec), xml)
}

fn parse_hex_char_ref(xml: StringPoint<'_>) -> XmlProgress<'_, Reference<'_>> {
    let (xml, _) = try_parse!(
        xml.consume_literal("&#x")
            .map_err(|_| SpecificError::ExpectedHexReference)
    );
    let (xml, hex) = try_parse!(Span::parse(xml, |xml| xml.consume_hex_chars()));
    let (xml, _) = try_parse!(xml.expect_literal(";"));

    success(HexChar(hex), xml)
}

fn parse_reference<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, Reference<'a>> {
    pm.alternate()
        .one(|_| parse_entity_ref(xml))
        .one(|_| parse_decimal_char_ref(xml))
        .one(|_| parse_hex_char_ref(xml))
        .finish()
}

fn parse_attribute_reference<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, Token<'a>> {
    let (xml, val) = try_parse!(parse_reference(pm, xml));

    success(Token::ReferenceAttributeValue(val), xml)
}

fn parse_char_data<'a>(xml: StringPoint<'a>) -> XmlProgress<'a, Token<'a>> {
    xml.consume_char_data().map(Token::CharData)
}

fn parse_cdata<'a>(xml: StringPoint<'a>) -> XmlProgress<'a, Token<'a>> {
    let (xml, _) = try_parse!(xml.expect_literal("<![CDATA["));
    let (xml, text) = try_parse!(xml.consume_cdata());
    let (xml, _) = try_parse!(xml.expect_literal("]]>"));

    success(Token::CData(text), xml)
}

fn parse_content_reference<'a>(
    pm: &mut XmlMaster<'a>,
    xml: StringPoint<'a>,
) -> XmlProgress<'a, Token<'a>> {
    let (xml, r) = try_parse!(parse_reference(pm, xml));
    success(Token::ContentReference(r), xml)
}

impl<'a> Iterator for PullParser<'a> {
    type Item = Result<Token<'a>, (usize, Vec<SpecificError>)>;

    fn next(&mut self) -> Option<Self::Item> {
        let pm = &mut self.pm;
        let xml = self.xml;

        let r = match self.state {
            State::AtBeginning => pm
                .alternate()
                .one(|pm| parse_xml_declaration(pm, xml))
                .one(|_| parse_element_start(xml))
                .one(|_| xml.expect_space().map(Token::Whitespace))
                .one(|_| parse_comment(xml))
                .one(|_| parse_pi(xml))
                .finish(),

            State::AfterDeclaration => pm
                .alternate()
                .one(|pm| parse_document_type_declaration(pm, xml))
                .one(|_| parse_element_start(xml))
                .one(|_| xml.expect_space().map(Token::Whitespace))
                .one(|_| parse_comment(xml))
                .one(|_| parse_pi(xml))
                .finish(),

            State::AfterElementStart(..) => pm
                .alternate()
                .one(|pm| parse_attribute_start(pm, xml))
                .one(|_| parse_element_start_close(xml))
                .one(|_| parse_element_self_close(xml))
                .finish(),

            State::AfterAttributeStart(_, quote) => pm
                .alternate()
                .one(|_| parse_attribute_literal(xml, quote))
                .one(|pm| parse_attribute_reference(pm, xml))
                .one(|_| parse_attribute_end(xml, quote))
                .finish(),

            State::Content(..) => pm
                .alternate()
                .one(|_| parse_element_start(xml))
                .one(|_| parse_element_close(xml))
                .one(|_| parse_char_data(xml))
                .one(|_| parse_cdata(xml))
                .one(|pm| parse_content_reference(pm, xml))
                .one(|_| parse_comment(xml))
                .one(|_| parse_pi(xml))
                .finish(),

            State::AfterMainElement => {
                if xml.is_empty() {
                    return None;
                }

                pm.alternate()
                    .one(|_| parse_comment(xml))
                    .one(|_| parse_pi(xml))
                    .one(|_| xml.expect_space().map(Token::Whitespace))
                    .finish()
            }
        };

        let (r, pt) = match pm.finish(r) {
            peresil::Progress {
                status: peresil::Status::Success(t),
                point,
            } => (t, point),
            peresil::Progress {
                status: peresil::Status::Failure(e),
                point,
            } => {
                return Some(Err((point.offset, e)));
            }
        };

        if pt == xml {
            return None;
        }

        let next_state = match (self.state, r) {
            (State::AtBeginning, Token::XmlDeclaration)
            | (State::AtBeginning, Token::ProcessingInstruction(..))
            | (State::AtBeginning, Token::Comment(..))
            | (State::AtBeginning, Token::Whitespace(..)) => State::AfterDeclaration,
            (State::AtBeginning, Token::ElementStart(..)) => State::AfterElementStart(0),

            (State::AfterDeclaration, Token::ProcessingInstruction(..))
            | (State::AfterDeclaration, Token::Comment(..))
            | (State::AfterDeclaration, Token::Whitespace(..)) => State::AfterDeclaration,
            (State::AfterDeclaration, Token::DocumentTypeDeclaration) => State::AfterDeclaration,
            (State::AfterDeclaration, Token::ElementStart(..)) => State::AfterElementStart(0),

            (State::AfterElementStart(d), Token::AttributeStart(_, q)) => {
                State::AfterAttributeStart(d, q)
            }
            (State::AfterElementStart(d), Token::ElementStartClose) => State::Content(d),
            (State::AfterElementStart(0), Token::ElementSelfClose) => State::AfterMainElement,
            (State::AfterElementStart(d), Token::ElementSelfClose) => State::Content(d - 1),

            (State::AfterAttributeStart(d, q), Token::LiteralAttributeValue(..))
            | (State::AfterAttributeStart(d, q), Token::ReferenceAttributeValue(..)) => {
                State::AfterAttributeStart(d, q)
            }
            (State::AfterAttributeStart(d, _), Token::AttributeEnd) => State::AfterElementStart(d),

            (State::Content(d), Token::CharData(..))
            | (State::Content(d), Token::CData(..))
            | (State::Content(d), Token::ContentReference(..))
            | (State::Content(d), Token::Comment(..))
            | (State::Content(d), Token::ProcessingInstruction(..)) => State::Content(d),
            (State::Content(d), Token::ElementStart(..)) => State::AfterElementStart(d + 1),
            (State::Content(0), Token::ElementClose(..)) => State::AfterMainElement,
            (State::Content(d), Token::ElementClose(..)) => State::Content(d - 1),

            (State::AfterMainElement, Token::Comment(..))
            | (State::AfterMainElement, Token::ProcessingInstruction(..))
            | (State::AfterMainElement, Token::Whitespace(..)) => State::AfterMainElement,

            (s, t) => {
                unreachable!("Transitioning from {:?} to {:?} is impossible", s, t);
            }
        };

        self.state = next_state;
        self.xml = pt;

        Some(Ok(r))
    }
}

struct DomBuilder<'d> {
    doc: dom::Document<'d>,
    elements: Vec<dom::Element<'d>>,
    element_names: Vec<Span<PrefixedName<'d>>>,
    attributes: Vec<DeferredAttribute<'d>>,
    seen_top_element: bool,
}

impl<'d> DomBuilder<'d> {
    fn new(doc: dom::Document<'d>) -> DomBuilder<'d> {
        DomBuilder {
            doc,
            elements: vec![],
            element_names: Vec::new(),
            attributes: Vec::new(),
            seen_top_element: false,
        }
    }

    fn append_to_either<T>(&self, child: T)
    where
        T: Into<dom::ChildOfRoot<'d>>,
    {
        match self.elements.last() {
            None => self.doc.root().append_child(child),
            Some(parent) => parent.append_child(child.into()),
        }
    }

    #[cfg(not(feature = "no-unsafe"))]
    fn default_namespace_uri(&self) -> Option<&str> {
        self.elements
            .last()
            .and_then(|e| e.recursive_default_namespace_uri())
    }

    #[cfg(feature = "no-unsafe")]
    fn default_namespace_uri(&self) -> Option<InternedString> {
        self.elements
            .last()
            .and_then(|e| e.recursive_default_namespace_uri())
    }

    #[cfg(not(feature = "no-unsafe"))]
    fn namespace_uri_for_prefix(&self, prefix: &str) -> Option<&str> {
        self.elements
            .last()
            .and_then(|e| e.namespace_uri_for_prefix(prefix))
    }

    #[cfg(feature = "no-unsafe")]
    fn namespace_uri_for_prefix(&self, prefix: &str) -> Option<InternedString> {
        self.elements
            .last()
            .and_then(|e| e.namespace_uri_for_prefix(prefix))
    }

    #[allow(clippy::needless_option_as_deref)]
    fn finish_opening_tag(&mut self) -> DomBuilderResult<()> {
        let deferred_element = self.element_names.last().expect("Unknown element name");
        let attributes = DeferredAttributes::new(std::mem::take(&mut self.attributes));

        attributes.check_duplicates()?;
        let default_namespace = attributes.default_namespace()?;

        let mut new_prefix_mappings = HashMap::new();
        for ns in attributes.namespaces() {
            let value = AttributeValueBuilder::convert(&ns.values)?;

            if value.is_empty() {
                return Err(ns.name.map(|_| SpecificError::EmptyNamespace));
            }

            new_prefix_mappings.insert(ns.name.value.local_part, value);
        }
        let new_prefix_mappings = new_prefix_mappings;

        let element_name = &deferred_element.value;

        let element = if let Some(prefix) = element_name.prefix {
            let ns_uri_from_map = new_prefix_mappings.get(prefix).map(|p| &p[..]);
            let ns_uri_from_parent = self.namespace_uri_for_prefix(prefix);
            let ns_uri: Option<&str> = ns_uri_from_map.or(ns_uri_from_parent.as_deref());

            if let Some(ns_uri) = ns_uri {
                let element = self.doc.create_element((ns_uri, element_name.local_part));
                element.set_preferred_prefix(Some(prefix));
                element
            } else {
                return Err(deferred_element.map(|_| SpecificError::UnknownNamespacePrefix));
            }
        } else if let Some(ns_uri) = default_namespace {
            if ns_uri.is_empty() {
                let element = self.doc.create_element(element_name.local_part);
                element.set_default_namespace_uri(None);
                element
            } else {
                let element = self
                    .doc
                    .create_element((&ns_uri[..], element_name.local_part));
                element.set_default_namespace_uri(Some(&ns_uri));
                element
            }
        } else {
            let ns_uri = self.default_namespace_uri();
            let name = QName::with_namespace_uri(ns_uri.as_deref(), element_name.local_part);
            self.doc.create_element(name)
        };

        for (prefix, ns_uri) in &new_prefix_mappings {
            element.register_prefix(prefix, ns_uri);
        }

        if !self.seen_top_element {
            self.seen_top_element = true;
            element.register_prefix(crate::XML_NS_PREFIX, crate::XML_NS_URI);
        }

        self.append_to_either(element);
        self.elements.push(element);

        let mut builder = AttributeValueBuilder::new();

        for attribute in attributes.attributes() {
            let name = &attribute.name.value;

            builder.clear();
            builder.ingest(&attribute.values)?;

            if let Some(prefix) = name.prefix {
                let ns_uri_from_map = new_prefix_mappings.get(prefix).map(|p| &p[..]);
                let ns_uri_from_parent = self.namespace_uri_for_prefix(prefix);
                let ns_uri: Option<&str> = ns_uri_from_map.or(ns_uri_from_parent.as_deref());

                if let Some(ns_uri) = ns_uri {
                    let attr = element.set_attribute_value((ns_uri, name.local_part), &builder);
                    attr.set_preferred_prefix(Some(prefix));
                } else {
                    return Err(attribute
                        .name
                        .map(|_| SpecificError::UnknownNamespacePrefix));
                }
            } else {
                element.set_attribute_value(name.local_part, &builder);
            }
        }

        Ok(())
    }

    fn add_attribute_value(&mut self, v: AttributeValue<'d>) {
        let a = self
            .attributes
            .last_mut()
            .expect("Cannot add attribute value without an attribute");
        a.values.push(v);
    }

    fn add_text_data(&self, text: &str) {
        let e = self
            .elements
            .last()
            .expect("Cannot add text node without a parent");
        let t = self.doc.create_text(text);
        e.append_child(t);
    }

    fn has_unclosed_elements(&self) -> bool {
        !self.elements.is_empty()
    }

    fn consume(&mut self, token: Token<'d>) -> DomBuilderResult<()> {
        use self::Token::*;

        match token {
            XmlDeclaration => {}

            DocumentTypeDeclaration => {}

            ElementStart(n) => {
                self.element_names.push(n);
            }

            ElementStartClose => {
                self.finish_opening_tag()?;
            }

            ElementSelfClose => {
                self.finish_opening_tag()?;

                self.element_names.pop();
                self.elements.pop();
            }

            ElementClose(n) => {
                let open_name = self.element_names.pop().expect("No open element");
                self.elements.pop();

                if n.value != open_name.value {
                    return Err(n.map(|_| SpecificError::MismatchedElementEndName));
                }
            }

            AttributeStart(n, _) => {
                let attr = DeferredAttribute {
                    name: n,
                    values: Vec::new(),
                };
                self.attributes.push(attr);
            }

            LiteralAttributeValue(v) => {
                self.add_attribute_value(AttributeValue::LiteralAttributeValue(v));
            }

            ReferenceAttributeValue(v) => {
                self.add_attribute_value(AttributeValue::ReferenceAttributeValue(v));
            }

            AttributeEnd => {}

            Whitespace(..) => {}

            CharData(t) | CData(t) => self.add_text_data(t),

            ContentReference(t) => {
                decode_reference(t, |s| self.add_text_data(s))?;
            }

            Comment(c) => {
                let c = self.doc.create_comment(c);
                self.append_to_either(c);
            }

            ProcessingInstruction(t, v) => {
                let pi = self.doc.create_processing_instruction(t, v);
                self.append_to_either(pi);
            }
        };

        Ok(())
    }
}

#[derive(Debug, PartialEq, Eq)]
pub struct Error {
    location: usize,
    errors: BTreeSet<SpecificError>,
}

impl Error {
    fn new(location: usize, error: SpecificError) -> Self {
        let mut errors = BTreeSet::new();
        errors.insert(error);
        Error { location, errors }
    }

    pub fn location(&self) -> usize {
        self.location
    }
}

impl From<(usize, Vec<SpecificError>)> for Error {
    fn from(other: (usize, Vec<SpecificError>)) -> Self {
        let (location, errors) = other;
        let errors = errors.into_iter().collect();
        Error { location, errors }
    }
}

impl From<Span<SpecificError>> for Error {
    fn from(other: Span<SpecificError>) -> Self {
        Self::new(other.offset, other.value)
    }
}

impl fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "XML parsing error at {}: {:?}",
            self.location, self.errors
        )
    }
}

impl error::Error for Error {
    fn description(&self) -> &str {
        "Unable to parse XML"
    }
}

/// Parses a string into a DOM. On failure, the location of the
/// parsing failure and all possible failures will be returned.
pub fn parse(xml: &str) -> Result<super::Package, Error> {
    let parser = PullParser::new(xml);
    let package = super::Package::new();

    {
        let doc = package.as_document();
        let mut builder = DomBuilder::new(doc);

        for token in parser {
            let token = token?;
            builder.consume(token)?;
        }

        if builder.has_unclosed_elements() {
            return Err(Error::new(xml.len(), SpecificError::UnclosedElement));
        }
    }

    Ok(package)
}

type DomBuilderResult<T> = Result<T, Span<SpecificError>>;

fn decode_reference<F>(ref_data: Reference<'_>, cb: F) -> DomBuilderResult<()>
where
    F: FnOnce(&str),
{
    match ref_data {
        #[allow(clippy::from_str_radix_10)]
        DecimalChar(span) => u32::from_str_radix(span.value, 10)
            .ok()
            .and_then(char::from_u32)
            .ok_or_else(|| span.map(|_| SpecificError::InvalidDecimalReference))
            .map(|c| cb(&c.to_string())),
        HexChar(span) => u32::from_str_radix(span.value, 16)
            .ok()
            .and_then(char::from_u32)
            .ok_or_else(|| span.map(|_| SpecificError::InvalidHexReference))
            .map(|c| cb(&c.to_string())),
        Entity(span) => {
            let s = match span.value {
                "amp" => "&",
                "lt" => "<",
                "gt" => ">",
                "apos" => "'",
                "quot" => "\"",
                _ => return Err(span.map(|_| SpecificError::UnknownNamedReference)),
            };
            cb(s);
            Ok(())
        }
    }
}

#[derive(Debug, Copy, Clone)]
enum AttributeValue<'a> {
    ReferenceAttributeValue(Reference<'a>),
    LiteralAttributeValue(&'a str),
}

struct AttributeValueBuilder {
    value: String,
}

impl AttributeValueBuilder {
    fn convert(values: &[AttributeValue<'_>]) -> DomBuilderResult<String> {
        let mut builder = AttributeValueBuilder::new();
        builder.ingest(values)?;
        Ok(builder.implode())
    }

    fn new() -> AttributeValueBuilder {
        AttributeValueBuilder {
            value: String::new(),
        }
    }

    fn ingest(&mut self, values: &[AttributeValue<'_>]) -> DomBuilderResult<()> {
        use self::AttributeValue::*;

        for value in values.iter() {
            match *value {
                LiteralAttributeValue(v) => self.value.push_str(v),
                ReferenceAttributeValue(r) => decode_reference(r, |s| self.value.push_str(s))?,
            }
        }

        Ok(())
    }

    fn clear(&mut self) {
        self.value.clear();
    }

    fn implode(self) -> String {
        self.value
    }
}

impl Deref for AttributeValueBuilder {
    type Target = str;

    fn deref(&self) -> &str {
        &self.value
    }
}

#[derive(Debug)]
struct DeferredAttribute<'d> {
    name: Span<PrefixedName<'d>>,
    values: Vec<AttributeValue<'d>>,
}

struct DeferredAttributes<'a> {
    attributes: Vec<DeferredAttribute<'a>>,
    namespaces: Vec<DeferredAttribute<'a>>,
    default_namespaces: Vec<DeferredAttribute<'a>>,
}

impl<'a> DeferredAttributes<'a> {
    fn new(attributes: Vec<DeferredAttribute<'a>>) -> DeferredAttributes<'a> {
        let (mut namespaces, attributes): (Vec<_>, Vec<_>) = attributes
            .into_iter()
            .partition(|attr| attr.name.value.prefix == Some("xmlns"));

        let (mut default_namespaces, mut attributes): (Vec<_>, Vec<_>) = attributes
            .into_iter()
            .partition(|attr| attr.name.value.local_part == "xmlns");

        fn sort_by_name(
            a: &DeferredAttribute<'_>,
            b: &DeferredAttribute<'_>,
        ) -> ::std::cmp::Ordering {
            a.name.value.cmp(&b.name.value)
        }

        attributes.sort_by(sort_by_name);
        namespaces.sort_by(sort_by_name);
        default_namespaces.sort_by(sort_by_name);

        DeferredAttributes {
            attributes,
            namespaces,
            default_namespaces,
        }
    }

    fn check_duplicates(&self) -> DomBuilderResult<()> {
        for w in self.attributes.windows(2) {
            if w[0].name.value == w[1].name.value {
                return Err(w[1].name.map(|_| SpecificError::DuplicateAttribute));
            }
        }

        for w in self.namespaces.windows(2) {
            if w[0].name.value == w[1].name.value {
                return Err(w[1].name.map(|_| SpecificError::RedefinedNamespace));
            }
        }

        Ok(())
    }

    fn attributes(&self) -> &[DeferredAttribute<'a>] {
        &self.attributes
    }

    fn namespaces(&self) -> &[DeferredAttribute<'a>] {
        &self.namespaces
    }

    fn default_namespace(&self) -> DomBuilderResult<Option<String>> {
        match self.default_namespaces.len() {
            0 => Ok(None),
            1 => {
                let ns = &self.default_namespaces[0];
                let value = AttributeValueBuilder::convert(&ns.values)?;
                Ok(Some(value))
            }
            _ => {
                let last_namespace = self
                    .default_namespaces
                    .last()
                    .expect("this branch contains multiple default namespaces");
                Err(last_namespace
                    .name
                    .map(|_| SpecificError::RedefinedDefaultNamespace))
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::*;
    use crate::{Package, QName, dom};

    macro_rules! assert_qname_eq(
        ($l:expr, $r:expr) => (assert_eq!(crate::as_qname!($l), Into::<QName<'_>>::into($r)));
    );

    fn full_parse(xml: &str) -> Result<Package, Error> {
        super::parse(xml)
    }

    fn quick_parse(xml: &str) -> Package {
        full_parse(xml).expect("Failed to parse the XML string")
    }

    fn top<'d>(doc: &'d dom::Document<'d>) -> dom::Element<'d> {
        doc.root().children()[0].element().unwrap()
    }

    #[test]
    fn a_document_with_a_prolog() {
        let package = quick_parse("<?xml version='1.0' ?><hello />");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_document_with_a_prolog_with_double_quotes() {
        let package = quick_parse("<?xml version=\"1.0\" ?><hello />");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_prolog_with_an_encoding() {
        let package = quick_parse("<?xml version='1.0' encoding='UTF-8' ?><hello />");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_non_standalone_prolog() {
        let package = quick_parse("<?xml version='1.0' standalone='no'?><hello/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_complete_prolog() {
        let package =
            quick_parse("<?xml version='1.0' encoding='UTF-8' standalone='yes'?><hello/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_external_id() {
        let package = quick_parse(
            r#"<?xml version='1.0'?>
        <!DOCTYPE doc SYSTEM "http://example.com/doc.dtd">
        <hello/>"#,
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_int_subset() {
        let package = quick_parse(
            r#"<?xml version="1.0"?>
            <!DOCTYPE note [
            <!ELEMENT note (to,from,heading,body)>
            <!ELEMENT to (#PCDATA)>
            <!ELEMENT from (#PCDATA)>
            <!ELEMENT heading (#PCDATA)>
            <!ELEMENT body (#PCDATA)>
            ]>
            <note>
            <to>Tove</to>
            <from>Jani</from>
            <heading>Reminder</heading>
            <body>Don't forget me this weekend</body>
            </note>
        "#,
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "note");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_int_subset_trailing_ws() {
        let package = quick_parse(
            r#"<?xml version="1.0"?>
            <!DOCTYPE note
                [
                    <!ELEMENT note (to,from,heading,body)>
                    <!ELEMENT to (#PCDATA)>
                    <!ELEMENT from (#PCDATA)>
                    <!ELEMENT heading (#PCDATA)>
                    <!ELEMENT body (#PCDATA)>
                ]

            >
            <note>
            <to>Tove</to>
            <from>Jani</from>
            <heading>Reminder</heading>
            <body>Don't forget me this weekend</body>
            </note>
        "#,
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "note");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_zero_def() {
        let package = quick_parse(
            "<?xml version='1.0'?>
        <!DOCTYPE doc>
        <hello/>",
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_zero_def_trailing_ws() {
        let package = quick_parse(
            "<?xml version='1.0'?>
        <!DOCTYPE doc  >
        <hello/>",
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_both_int_subset_and_external_id() {
        let package = quick_parse(
            r#"<?xml version='1.0'?>
        <!DOCTYPE doc SYSTEM "http://example.com/doc.dtd" [
        <!ELEMENT hello (#PCDATA)>
        ]>
        <hello/>"#,
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_prolog_with_a_doc_type_declaration_both_int_subset_and_external_id_trailing_ws() {
        let package = quick_parse(
            r#"<?xml version='1.0'?>
        <!DOCTYPE doc SYSTEM "http://example.com/doc.dtd" [
        <!ELEMENT hello (#PCDATA)>
         ]  >
        <hello/>"#,
        );
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn a_document_with_a_single_element() {
        let package = quick_parse("<hello />");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn an_element_with_a_namespace() {
        let package = quick_parse("<ns:hello xmlns:ns='namespace'/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(crate::as_opt_str!(top.preferred_prefix()), Some("ns"));
        assert_qname_eq!(top.name(), ("namespace", "hello"));
    }

    #[test]
    fn an_element_with_a_default_namespace() {
        let package = quick_parse("<hello xmlns='namespace'/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(
            crate::as_opt_str!(top.default_namespace_uri()),
            Some("namespace")
        );
        assert_qname_eq!(top.name(), ("namespace", "hello"));
    }

    #[test]
    fn an_element_with_an_attribute() {
        let package = quick_parse("<hello scope='world'/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(
            crate::as_opt_str!(top.attribute_value("scope")),
            Some("world")
        );
    }

    #[test]
    fn an_element_with_an_attribute_using_double_quotes() {
        let package = quick_parse("<hello scope=\"world\"/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(
            crate::as_opt_str!(top.attribute_value("scope")),
            Some("world")
        );
    }

    #[test]
    fn an_element_with_multiple_attributes() {
        let package = quick_parse("<hello scope='world' happy='true'/>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(
            crate::as_opt_str!(top.attribute_value("scope")),
            Some("world")
        );
        assert_eq!(
            crate::as_opt_str!(top.attribute_value("happy")),
            Some("true")
        );
    }

    #[test]
    fn an_attribute_with_a_namespace() {
        let package = quick_parse("<hello ns:a='b' xmlns:ns='namespace'/>");
        let doc = package.as_document();
        let top = top(&doc);

        let attr = top.attribute(("namespace", "a")).unwrap();

        assert_eq!(crate::as_opt_str!(attr.preferred_prefix()), Some("ns"));
        assert_eq!(crate::as_str!(attr.value()), "b");
    }

    #[test]
    fn an_attribute_with_xml_space_preserve() {
        let package = quick_parse("<hello xml:space='preserve'> <a/> </hello>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(
            crate::as_str!(top.attribute((crate::XML_NS_URI, "space")).unwrap().value()),
            "preserve"
        );

        let children = top.children();
        assert_eq!(children.len(), 3);
        assert_eq!(crate::as_str!(children[0].text().unwrap().text()), " ");
        assert_qname_eq!(children[1].element().unwrap().name(), "a");
        assert_eq!(crate::as_str!(children[2].text().unwrap().text()), " ");
    }

    #[test]
    fn an_attribute_with_references() {
        let package = quick_parse("<log msg='I &lt;3 math' />");
        let doc = package.as_document();
        let top = top(&doc);

        assert_eq!(
            crate::as_opt_str!(top.attribute_value("msg")),
            Some("I <3 math")
        );
    }

    #[test]
    fn an_element_that_is_not_self_closing() {
        let package = quick_parse("<hello></hello>");
        let doc = package.as_document();
        let top = top(&doc);

        assert_qname_eq!(top.name(), "hello");
    }

    #[test]
    fn nested_elements() {
        let package = quick_parse("<hello><world/></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        assert_qname_eq!(world.name(), "world");
    }

    #[test]
    fn multiply_nested_elements() {
        let package = quick_parse("<hello><awesome><world/></awesome></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let awesome = hello.children()[0].element().unwrap();
        let world = awesome.children()[0].element().unwrap();

        assert_qname_eq!(world.name(), "world");
    }

    #[test]
    fn nested_elements_with_namespaces() {
        let package =
            quick_parse("<ns1:hello xmlns:ns1='outer'><ns2:world xmlns:ns2='inner'/></ns1:hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        assert_qname_eq!(world.name(), ("inner", "world"));
    }

    #[test]
    fn nested_elements_with_inherited_namespaces() {
        let package = quick_parse("<ns1:hello xmlns:ns1='outer'><ns1:world/></ns1:hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        assert_eq!(crate::as_opt_str!(world.preferred_prefix()), Some("ns1"));
        assert_qname_eq!(world.name(), ("outer", "world"));
    }

    #[test]
    fn nested_elements_with_inherited_default_namespace() {
        let package = quick_parse("<hello xmlns='outer'><world/></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        assert_qname_eq!(world.name(), ("outer", "world"));
    }

    #[test]
    fn nested_elements_with_reset_default_namespace() {
        let package = quick_parse("<hello xmlns='outer'><world xmlns=''/></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        assert_qname_eq!(world.name(), "world");
    }

    #[test]
    fn nested_elements_with_attributes() {
        let package = quick_parse("<hello><world name='Earth'/></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        assert_eq!(
            crate::as_opt_str!(world.attribute_value("name")),
            Some("Earth")
        );
    }

    #[test]
    fn nested_elements_with_attributes_with_inherited_namespaces() {
        let package = quick_parse("<hello xmlns:ns1='outer'><world ns1:name='Earth'/></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let world = hello.children()[0].element().unwrap();

        let attr = world.attribute(("outer", "name")).unwrap();

        assert_eq!(crate::as_opt_str!(attr.preferred_prefix()), Some("ns1"));
        assert_eq!(crate::as_str!(attr.value()), "Earth");
    }

    #[test]
    fn element_with_text() {
        let package = quick_parse("<hello>world</hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let text = hello.children()[0].text().unwrap();

        assert_eq!(crate::as_str!(text.text()), "world");
    }

    #[test]
    fn element_with_cdata() {
        let package = quick_parse("<words><![CDATA[I have & and < !]]></words>");
        let doc = package.as_document();
        let words = top(&doc);
        let text = words.children()[0].text().unwrap();

        assert_eq!(crate::as_str!(text.text()), "I have & and < !");
    }

    #[test]
    fn element_with_comment() {
        let package = quick_parse("<hello><!-- A comment --></hello>");
        let doc = package.as_document();
        let words = top(&doc);
        let comment = words.children()[0].comment().unwrap();

        assert_eq!(crate::as_str!(comment.text()), " A comment ");
    }

    #[test]
    fn comment_before_top_element() {
        let package = quick_parse("<!-- A comment --><hello />");
        let doc = package.as_document();
        let comment = doc.root().children()[0].comment().unwrap();

        assert_eq!(crate::as_str!(comment.text()), " A comment ");
    }

    #[test]
    fn multiple_comments_before_top_element() {
        let xml = r"
<!--Comment 1-->
<!--Comment 2-->
<hello />";
        let package = quick_parse(xml);
        let doc = package.as_document();
        let comment1 = doc.root().children()[0].comment().unwrap();
        let comment2 = doc.root().children()[1].comment().unwrap();

        assert_eq!(crate::as_str!(comment1.text()), "Comment 1");
        assert_eq!(crate::as_str!(comment2.text()), "Comment 2");
    }

    #[test]
    fn multiple_comments_after_top_element() {
        let xml = r"
<hello />
<!--Comment 1-->
<!--Comment 2-->";
        let package = quick_parse(xml);
        let doc = package.as_document();
        let comment1 = doc.root().children()[1].comment().unwrap();
        let comment2 = doc.root().children()[2].comment().unwrap();

        assert_eq!(crate::as_str!(comment1.text()), "Comment 1");
        assert_eq!(crate::as_str!(comment2.text()), "Comment 2");
    }

    #[test]
    fn element_with_processing_instruction() {
        let package = quick_parse("<hello><?device?></hello>");
        let doc = package.as_document();
        let hello = top(&doc);
        let pi = hello.children()[0].processing_instruction().unwrap();

        assert_eq!(crate::as_str!(pi.target()), "device");
        assert_eq!(crate::as_opt_str!(pi.value()), None);
    }

    #[test]
    fn top_level_processing_instructions() {
        let xml = r"
<?output printer?>
<hello />
<?validated?>";

        let package = quick_parse(xml);
        let doc = package.as_document();
        let pi1 = doc.root().children()[0].processing_instruction().unwrap();
        let pi2 = doc.root().children()[2].processing_instruction().unwrap();

        assert_eq!(crate::as_str!(pi1.target()), "output");
        assert_eq!(crate::as_opt_str!(pi1.value()), Some("printer"));

        assert_eq!(crate::as_str!(pi2.target()), "validated");
        assert_eq!(crate::as_opt_str!(pi2.value()), None);
    }

    #[test]
    fn element_with_decimal_char_reference() {
        let package = quick_parse("<math>2 &#62; 1</math>");
        let doc = package.as_document();
        let math = top(&doc);
        let text1 = math.children()[0].text().unwrap();
        let text2 = math.children()[1].text().unwrap();
        let text3 = math.children()[2].text().unwrap();

        assert_eq!(crate::as_str!(text1.text()), "2 ");
        assert_eq!(crate::as_str!(text2.text()), ">");
        assert_eq!(crate::as_str!(text3.text()), " 1");
    }

    #[test]
    fn element_with_hexidecimal_char_reference() {
        let package = quick_parse("<math>1 &#x3c; 2</math>");
        let doc = package.as_document();
        let math = top(&doc);
        let text1 = math.children()[0].text().unwrap();
        let text2 = math.children()[1].text().unwrap();
        let text3 = math.children()[2].text().unwrap();

        assert_eq!(crate::as_str!(text1.text()), "1 ");
        assert_eq!(crate::as_str!(text2.text()), "<");
        assert_eq!(crate::as_str!(text3.text()), " 2");
    }

    #[test]
    fn element_with_entity_reference() {
        let package = quick_parse("<math>I &lt;3 math</math>");
        let doc = package.as_document();
        let math = top(&doc);
        let text1 = math.children()[0].text().unwrap();
        let text2 = math.children()[1].text().unwrap();
        let text3 = math.children()[2].text().unwrap();

        assert_eq!(crate::as_str!(text1.text()), "I ");
        assert_eq!(crate::as_str!(text2.text()), "<");
        assert_eq!(crate::as_str!(text3.text()), "3 math");
    }

    #[test]
    fn element_with_mixed_children() {
        let package = quick_parse("<hello>to <!--fixme--><a><![CDATA[the]]></a><?world?></hello>");
        let doc = package.as_document();
        let hello = top(&doc);

        let text = hello.children()[0].text().unwrap();
        let comment = hello.children()[1].comment().unwrap();
        let element = hello.children()[2].element().unwrap();
        let pi = hello.children()[3].processing_instruction().unwrap();

        assert_eq!(crate::as_str!(text.text()), "to ");
        assert_eq!(crate::as_str!(comment.text()), "fixme");
        assert_qname_eq!(element.name(), "a");
        assert_eq!(crate::as_str!(pi.target()), "world");
    }

    // TODO: untested errors
    //
    // versionnumber
    // prefixedname
    // decimal chars
    // hex chars
    // chardata
    // cdata
    // commentbody
    // pinstructionvalue

    macro_rules! assert_parse_failure {
        ($actual:expr, $pos:expr, $($err:expr),+) => {
            {
                let errors = vec![$($err),+];
                let expected = Err(Error::from(($pos, errors)));
                assert_eq!($actual, expected);
            }
        }
    }

    #[test]
    fn failure_invalid_encoding() {
        use super::SpecificError::*;

        let r = full_parse("<?xml version='1.0' encoding='8BIT' ?><hi/>");

        assert_parse_failure!(r, 30, ExpectedEncoding);
    }

    #[test]
    fn failure_invalid_standalone() {
        use super::SpecificError::*;

        let r = full_parse("<?xml version='1.0' standalone='invalid'?><hello/>");

        assert_parse_failure!(r, 32, ExpectedYesNo);
    }

    #[test]
    fn failure_no_open_brace() {
        use super::SpecificError::*;

        let r = full_parse("hi />");

        assert_parse_failure!(
            r,
            0,
            Expected("<?xml"),
            ExpectedComment,
            ExpectedProcessingInstruction,
            ExpectedWhitespace,
            ExpectedElement
        );
    }

    #[test]
    fn failure_unclosed_tag() {
        use super::SpecificError::*;

        let r = full_parse("<hi");

        assert_parse_failure!(
            r,
            3,
            ExpectedWhitespace,
            ExpectedElementSelfClosed,
            ExpectedElementEnd
        );
    }

    #[test]
    fn failure_unexpected_space() {
        use super::SpecificError::*;

        let r = full_parse("<hi / >");

        assert_parse_failure!(
            r,
            4,
            ExpectedAttribute,
            ExpectedElementSelfClosed,
            ExpectedElementEnd
        );
    }

    #[test]
    fn failure_attribute_without_open_quote() {
        use super::SpecificError::*;

        let r = full_parse("<hi oops=value' />");

        assert_parse_failure!(r, 9, ExpectedOpeningQuote("\'"), ExpectedOpeningQuote("\""));
    }

    #[test]
    fn failure_attribute_without_close_quote() {
        use super::SpecificError::*;

        let r = full_parse("<hi oops='value />");

        assert_parse_failure!(
            r,
            18,
            ExpectedNamedReference,
            ExpectedDecimalReference,
            ExpectedAttributeValue,
            ExpectedHexReference,
            ExpectedClosingQuote("\'")
        );
    }

    #[test]
    fn failure_unclosed_attribute_and_tag() {
        use super::SpecificError::*;

        let r = full_parse("<hi oops='value");

        assert_parse_failure!(
            r,
            15,
            ExpectedNamedReference,
            ExpectedDecimalReference,
            ExpectedAttributeValue,
            ExpectedHexReference,
            ExpectedClosingQuote("\'")
        );
    }

    #[test]
    fn failure_nested_unclosed_tag() {
        use super::SpecificError::*;

        let r = full_parse("<hi><oops</hi>");

        assert_parse_failure!(
            r,
            9,
            ExpectedWhitespace,
            ExpectedElementSelfClosed,
            ExpectedElementEnd
        );
    }

    #[test]
    fn failure_missing_close_tag() {
        use super::SpecificError::*;

        let r = full_parse("<hi>wow");

        assert_parse_failure!(r, 7, UnclosedElement);
    }

    #[test]
    fn failure_nested_unexpected_space() {
        use super::SpecificError::*;

        let r = full_parse("<hi><oops / ></hi>");

        assert_parse_failure!(
            r,
            10,
            ExpectedAttribute,
            ExpectedElementSelfClosed,
            ExpectedElementEnd
        );
    }

    #[test]
    fn failure_malformed_entity_reference() {
        use super::SpecificError::*;

        let r = full_parse("<hi>Entity: &;</hi>");

        assert_parse_failure!(r, 13, ExpectedNamedReferenceValue);
    }

    #[test]
    fn failure_nested_malformed_entity_reference() {
        use super::SpecificError::*;

        let r = full_parse("<hi><bye>Entity: &;</bye></hi>");

        assert_parse_failure!(r, 18, ExpectedNamedReferenceValue);
    }

    #[test]
    fn failure_nested_attribute_without_open_quote() {
        use super::SpecificError::*;

        let r = full_parse("<hi><bye oops=value' /></hi>");

        assert_parse_failure!(
            r,
            14,
            ExpectedOpeningQuote("\'"),
            ExpectedOpeningQuote("\"")
        );
    }

    #[test]
    fn failure_nested_attribute_without_close_quote() {
        use super::SpecificError::*;

        let r = full_parse("<hi><bye oops='value /></hi>");

        assert_parse_failure!(
            r,
            23,
            ExpectedNamedReference,
            ExpectedDecimalReference,
            ExpectedAttributeValue,
            ExpectedHexReference,
            ExpectedClosingQuote("\'")
        );
    }

    #[test]
    fn failure_nested_unclosed_attribute_and_tag() {
        use super::SpecificError::*;

        let r = full_parse("<hi><bye oops='value</hi>");

        assert_parse_failure!(
            r,
            20,
            ExpectedNamedReference,
            ExpectedDecimalReference,
            ExpectedAttributeValue,
            ExpectedHexReference,
            ExpectedClosingQuote("\'")
        );
    }

    #[test]
    fn failure_pi_target_as_xml() {
        use super::SpecificError::*;

        let r = full_parse("<a><?xml?></a>");

        assert_parse_failure!(r, 5, InvalidProcessingInstructionTarget);
    }

    #[test]
    fn failure_end_tag_does_not_match() {
        use super::SpecificError::*;

        let r = full_parse("<a></b>");

        assert_parse_failure!(r, 5, MismatchedElementEndName);
    }

    #[test]
    fn failure_invalid_decimal_reference() {
        use super::SpecificError::*;

        let r = full_parse("<a>&#99999999;</a>");

        assert_parse_failure!(r, 5, InvalidDecimalReference);
    }

    #[test]
    fn failure_invalid_hex_reference() {
        use super::SpecificError::*;

        let r = full_parse("<a>&#x99999999;</a>");

        assert_parse_failure!(r, 6, InvalidHexReference);
    }

    #[test]
    fn failure_unknown_named_reference() {
        use super::SpecificError::*;

        let r = full_parse("<a>&fake;</a>");

        assert_parse_failure!(r, 4, UnknownNamedReference);
    }

    #[test]
    fn failure_duplicate_attribute() {
        use super::SpecificError::*;

        let r = full_parse("<a b='c' b='d'/>");

        assert_parse_failure!(r, 9, DuplicateAttribute);
    }

    #[test]
    fn failure_redefined_namespace() {
        use super::SpecificError::*;

        let r = full_parse("<a xmlns:b='c' xmlns:b='d'/>");

        assert_parse_failure!(r, 15, RedefinedNamespace);
    }

    #[test]
    fn failure_redefined_default_namespace() {
        use super::SpecificError::*;

        let r = full_parse("<a xmlns='a' xmlns='b'/>");

        assert_parse_failure!(r, 13, RedefinedDefaultNamespace);
    }

    #[test]
    fn failure_empty_namespace() {
        use super::SpecificError::*;

        let r = full_parse("<a xmlns:b=''/>");

        assert_parse_failure!(r, 3, EmptyNamespace);
    }

    #[test]
    fn failure_unknown_attribute_namespace_prefix() {
        use super::SpecificError::*;

        let r = full_parse("<a b:foo='a'/>");

        assert_parse_failure!(r, 3, UnknownNamespacePrefix);
    }

    #[test]
    fn failure_unknown_element_namespace_prefix() {
        use super::SpecificError::*;

        let r = full_parse("<b:a/>");

        assert_parse_failure!(r, 1, UnknownNamespacePrefix);
    }

    #[test]
    fn failure_is_an_error() {
        fn __assert_well_behaved_error()
        where
            Error: ::std::error::Error + Send + Sync + 'static,
        {
        }
    }
}