///|
/// A pull-parser over an in-memory XML document.
///
/// The parser is lenient about constructs that do not affect RSS/Atom
/// interpretation (processing instructions and DOCTYPE declarations are
/// skipped) but strict about malformed tags, attributes and CDATA sections.
pub struct Reader {
  priv input : String
  priv mut pos : Int
} derive(Debug)

///|
/// Create a reader over `input`. A leading BOM is skipped.
pub fn Reader::new(input : String) -> Reader {
  let start = if input.length() > 0 && input[0].to_int() == 0xFEFF {
    1
  } else {
    0
  }
  { input, pos: start }
}

///|
/// Current code-unit offset of the scanner (for diagnostics).
pub fn Reader::position(self : Reader) -> Int {
  self.pos
}

///|
fn Reader::code(self : Reader, i : Int) -> Int {
  self.input[i].to_int()
}

///|
fn Reader::has_lit(self : Reader, i : Int, lit : String) -> Bool {
  let n = lit.length()
  if i + n > self.input.length() {
    return false
  }
  for k in 0.. Event raise XmlError {
  let len = self.input.length()
  while self.pos < len {
    let c = self.code(self.pos)
    if c != cu('<') {
      return self.scan_text()
    }
    // Markup dispatch.
    if self.has_lit(self.pos, "`.
fn Reader::scan_comment(self : Reader) -> Unit raise XmlError {
  let content_start = self.pos + 4
  let end = find_seq(self.input, content_start, "-->")
  guard end >= 0 else { raise Syntax(pos=self.pos, msg="unterminated comment") }
  let text = substring(self.input, content_start, end)
  ignore(text)
  self.pos = end + 3
}

///|
/// After ``; returns the raw contents.
fn Reader::scan_cdata(self : Reader) -> Event raise XmlError {
  let content_start = self.pos + 9
  let end = find_seq(self.input, content_start, "]]>")
  guard end >= 0 else {
    raise Syntax(pos=self.pos, msg="unterminated CDATA section")
  }
  let raw = substring(self.input, content_start, end)
  self.pos = end + 3
  CData(raw)
}

///|
/// After ``.
fn Reader::skip_pi(self : Reader) -> Unit raise XmlError {
  let end = find_seq(self.input, self.pos + 2, "?>")
  guard end >= 0 else {
    raise Syntax(pos=self.pos, msg="unterminated processing instruction")
  }
  self.pos = end + 2
}

///|
/// After ``,
/// honouring `[ ... ]` internal-subset nesting.
fn Reader::skip_declaration(self : Reader) -> Unit raise XmlError {
  let len = self.input.length()
  let mut i = self.pos + 2
  let mut depth = 0
  while i < len {
    match self.code(i) {
      c if c == cu('[') => depth += 1
      c if c == cu(']') => depth -= 1
      c if c == cu('>') && depth <= 0 => {
        self.pos = i + 1
        return
      }
      _ => ()
    }
    i += 1
  }
  raise Syntax(pos=self.pos, msg="unterminated declaration")
}

///|
/// At ``.
fn Reader::scan_end_tag(self : Reader) -> Event raise XmlError {
  let len = self.input.length()
  let name_start = self.pos + 2
  let mut i = name_start
  while i < len && !is_ws(self.code(i)) && self.code(i) != cu('>') {
    i += 1
  }
  if i >= len {
    raise Syntax(pos=self.pos, msg="unterminated end tag")
  }
  if i == name_start {
    raise Syntax(pos=self.pos, msg="empty end-tag name")
  }
  let name = trim(substring(self.input, name_start, i))
  // Skip whitespace then require '>'.
  while i < len && is_ws(self.code(i)) {
    i += 1
  }
  if i >= len || self.code(i) != cu('>') {
    raise Syntax(pos=i, msg="expected '>' to close end tag")
  }
  self.pos = i + 1
  End(name)
}

///|
/// At `<` naming an element; parse name and attributes.
fn Reader::scan_start_tag(self : Reader) -> Event raise XmlError {
  let len = self.input.length()
  let name_start = self.pos + 1
  let mut i = name_start
  while i < len &&
        !is_ws(self.code(i)) &&
        self.code(i) != cu('>') &&
        self.code(i) != cu('/') {
    i += 1
  }
  if i >= len {
    raise Syntax(pos=self.pos, msg="unterminated start tag")
  }
  if i == name_start {
    raise Syntax(pos=self.pos, msg="empty tag name")
  }
  let name = substring(self.input, name_start, i)
  let attrs : Array[Attribute] = []
  let mut empty = false
  while true {
    while i < len && is_ws(self.code(i)) {
      i += 1
    }
    if i >= len {
      raise Syntax(pos=self.pos, msg="unterminated start tag")
    }
    let c = self.code(i)
    if c == cu('/') {
      empty = true
      i += 1
      if i >= len || self.code(i) != cu('>') {
        raise Syntax(pos=i, msg="expected '>' after '/' in tag")
      }
      break
    } else if c == cu('>') {
      break
    } else if c == cu('=') {
      raise Syntax(pos=i, msg="unexpected '=' in tag")
    } else {
      // attribute name
      let key_start = i
      while i < len &&
            !is_ws(self.code(i)) &&
            self.code(i) != cu('=') &&
            self.code(i) != cu('>') &&
            self.code(i) != cu('/') {
        i += 1
      }
      if i == key_start {
        raise Syntax(pos=i, msg="invalid character in tag: expected attribute")
      }
      let key = substring(self.input, key_start, i)
      while i < len && is_ws(self.code(i)) {
        i += 1
      }
      if i >= len || self.code(i) != cu('=') {
        raise Syntax(pos=i, msg="expected '=' after attribute name '\{key}'")
      }
      i += 1
      while i < len && is_ws(self.code(i)) {
        i += 1
      }
      if i >= len || (self.code(i) != cu('"') && self.code(i) != cu('\'')) {
        raise Syntax(pos=i, msg="attribute '\{key}' has unquoted value")
      }
      let quote = self.code(i)
      i += 1
      let value_start = i
      while i < len && self.code(i) != quote {
        if self.code(i) == cu('<') {
          raise Syntax(pos=i, msg="'<' not allowed inside attribute value")
        }
        i += 1
      }
      if i >= len {
        raise Syntax(pos=self.pos, msg="unterminated attribute value")
      }
      let value = decode_entities(substring(self.input, value_start, i))
      i += 1 // closing quote
      attrs.push({ key, value })
    }
  }
  self.pos = i + 1
  if empty {
    Empty(name~, attrs~)
  } else {
    Start(name~, attrs~)
  }
}

///|
/// Find `needle` in `input` starting at `from`; returns the offset of the
/// first occurrence or `-1`.
fn find_seq(input : String, from : Int, needle : String) -> Int {
  let n = input.length()
  let m = needle.length()
  if m == 0 {
    return from
  }
  let first = needle[0]
  let mut i = from
  while i + m <= n {
    if input[i] == first {
      let mut ok = true
      for k in 1..