///|
/// The scanner.
///
/// A hand-written cursor over a `String`, following the WHATWG tokenizer
/// closely enough that a reader can check one against the other, and departing
/// from it in exactly one direction: it produces markup tokens rather than
/// driving a tree builder, so it has no insertion modes and no way to be told
/// what namespace it is in.
///
/// Indices are UTF-16 code units throughout, which is what a MoonBit `String`
/// is indexed in and what `@span.Span` measures. Every character the scanner
/// makes a decision about is ASCII, so a surrogate pair simply falls into the
/// "text" bucket a unit at a time and comes out whole.

///|
/// The replacement character, which the specification substitutes for NUL.
const REPLACEMENT : Char = '\u{FFFD}'

///|
priv struct Scanner {
  src : String
  len : Int
  mut pos : Int
  /// The raw-text run the next call has to scan, if the tag just emitted opened
  /// one. This is the specification's "appropriate end tag token" check, and it
  /// is the only piece of state the tokenizer needs from the document it is
  /// tokenizing.
  mut pending : Start
  problems : Array[(@kind.ErrorKind, @span.Span)]
}

///|
/// Tokenize a whole document, ending with exactly one `Eof`.
pub fn tokenize(src : String, start? : Start = Markup) -> Scanned {
  let s = { src, len: src.length(), pos: 0, pending: start, problems: [], }
  let out = []
  while true {
    let t = s.next()
    let done = t.kind == Eof
    out.push(t)
    if done {
      break
    }
  }
  { tokens: out, problems: s.problems, }
}

///|
/// Tokenize, keeping only the tokens.
pub fn tokens(src : String, start? : Start = Markup) -> Array[Token] {
  tokenize(src, start~).tokens
}

// ------------------------------------------------------------------- cursor

///|
/// The character at `i`, or NUL past the end.
///
/// NUL is safe as a sentinel because a real NUL in the input is replaced with
/// U+FFFD as it is read, so one can never appear as data.
fn Scanner::at(self : Scanner, i : Int) -> Char {
  if i >= self.len || i < 0 {
    '\u{0}'
  } else {
    self.src.unsafe_get(i).to_int().unsafe_to_char()
  }
}

///|
fn Scanner::peek(self : Scanner) -> Char {
  self.at(self.pos)
}

///|
fn Scanner::slice(self : Scanner, start : Int, end : Int) -> String {
  self.src.clamped_view(start~, end~).to_owned()
}

///|
fn Scanner::tok(self : Scanner, start : Int, kind : TokenKind) -> Token {
  { kind, span: @span.Span::new(start, self.pos), }
}

///|
fn Scanner::note(
  self : Scanner,
  kind : @kind.ErrorKind,
  span : @span.Span,
) -> Unit {
  self.problems.push((kind, span))
}

///|
/// Whether the input at `i` matches `what`, ASCII-case-insensitively.
fn Scanner::matches_ci(self : Scanner, i : Int, what : String) -> Bool {
  let n = what.length()
  if i + n > self.len {
    return false
  }
  let mut k = 0
  while k < n {
    if lower(self.at(i + k)) !=
      lower(what.unsafe_get(k).to_int().unsafe_to_char()) {
      return false
    }
    k = k + 1
  }
  true
}

// --------------------------------------------------------------- predicates

///|
fn lower(c : Char) -> Char {
  if c >= 'A' && c <= 'Z' {
    (c.to_int() + 32).unsafe_to_char()
  } else {
    c
  }
}

///|
/// The specification's input preprocessing, applied per run rather than to the
/// whole source: a CRLF pair and a lone CR both become a single LF.
///
/// Per run because doing it to the input up front would shift every offset
/// after every CRLF, and a diagnostic that points one character to the left of
/// the problem is worse than no diagnostic. The DECODED text is normalised and
/// the source spelling is kept in `raw`, which is the same bargain a character
/// reference already makes.
fn normalize_newlines(s : String) -> String {
  if !s.contains("\r") {
    return s
  }
  let buf = StringBuilder()
  let n = s.length()
  let mut i = 0
  while i < n {
    let c = s.unsafe_get(i).to_int().unsafe_to_char()
    if c == '\r' {
      buf.write_char('\n')
      i = i + 1
      if i < n && s.unsafe_get(i).to_int() == 10 {
        i = i + 1
      }
      continue
    }
    buf.write_char(c)
    i = i + 1
  }
  buf.to_string()
}

///|
fn is_ws(c : Char) -> Bool {
  c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == '\u{0C}'
}

///|
fn is_alpha(c : Char) -> Bool {
  (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}

///|
fn is_digit(c : Char) -> Bool {
  c >= '0' && c <= '9'
}

///|
fn is_hex(c : Char) -> Bool {
  is_digit(c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F')
}

///|
/// A character that may appear in a tag name.
///
/// Almost anything: the specification's tag-name state sends `"`, `'`, `<` and
/// `=` to its "anything else" branch, which appends them. So `` is one tag
/// whose name is `a Bool {
  !is_ws(c) && c != '/' && c != '>'
}

///|
/// A character that may appear in an attribute name.
///
/// The same set less `=`, which is the one character that ends a name rather
/// than joining it. `"`, `'` and `<` are a parse error inside a name and are
/// still part of it -- `
` has one attribute called `a Bool {
  is_tag_name_char(c) && c != '='
}

// --------------------------------------------------------------- the stream

///|
fn Scanner::next(self : Scanner) -> Token {
  if self.pos >= self.len {
    return self.tok(self.pos, Eof)
  }
  // A raw-text or escapable-raw-text body runs to its own end tag and is
  // scanned as one piece. The check is here rather than in the tag branch
  // because the body follows the tag it belongs to, and `last_start` is what
  // remembers which tag that was.
  match self.pending {
    Markup => ()
    Raw(tag) => {
      self.pending = Markup
      return self.raw_text_body(tag)
    }
    Escapable(tag) => {
      self.pending = Markup
      return self.escapable_body(tag)
    }
  }
  if self.peek() == '<' {
    return self.markup()
  }
  self.text()
}

///|
/// Everything up to the next `<`, with character references resolved.
fn Scanner::text(self : Scanner) -> Token {
  let start = self.pos
  let buf = StringBuilder()
  let mut decoded = false
  let mut normalised = false
  while self.pos < self.len && self.peek() != '<' {
    let c = self.peek()
    if c == '&' {
      match self.reference(true) {
        Some(text) => {
          buf.write_string(text)
          decoded = true
          continue
        }
        None => ()
      }
    }
    if c == '\u{0}' {
      // The data state EMITS a NUL, it does not replace it. Every other state
      // replaces it with U+FFFD, which is the sort of asymmetry only a
      // conformance suite finds.
      self.note(
        UnexpectedNullCharacter,
        @span.Span::new(self.pos, self.pos + 1),
      )
    }
    if self.newline_at(buf) {
      normalised = true
      continue
    }
    buf.write_char(c)
    self.pos = self.pos + 1
  }
  let raw = if decoded || normalised {
    Some(self.slice(start, self.pos))
  } else {
    None
  }
  self.tok(start, Text(buf.to_string(), raw))
}

///|
/// A CR at the cursor, written as the LF the specification preprocesses it to.
///
/// Inline in the scan rather than over the finished buffer, because a resolved
/// character reference must NOT be normalised: preprocessing happens to the
/// input stream and `
` is resolved after it, so `
` really is a
/// carriage return and a literal one really is not.
fn Scanner::newline_at(self : Scanner, buf : StringBuilder) -> Bool {
  if self.peek() != '\r' {
    return false
  }
  buf.write_char('\n')
  self.pos = self.pos + 1
  if self.pos < self.len && self.peek() == '\n' {
    self.pos = self.pos + 1
  }
  true
}

///|
/// A `<`, and whatever follows it.
fn Scanner::markup(self : Scanner) -> Token {
  let start = self.pos
  let c1 = self.at(self.pos + 1)
  if c1 == '!' {
    if self.matches_ci(self.pos + 2, "--") {
      return self.comment()
    }
    if self.matches_ci(self.pos + 2, "doctype") {
      return self.doctype()
    }
    if self.matches_ci(self.pos + 2, "[CDATA[") {
      return self.cdata()
    }
    return self.bogus_comment(2)
  }
  if c1 == '/' {
    if is_alpha(self.at(self.pos + 2)) {
      return self.end_tag()
    }
    if self.pos + 2 >= self.len {
      // `' {
      // `` is dropped entirely, per the specification.
      self.pos = self.pos + 3
      self.note(MissingTagName, @span.Span::new(start, self.pos))
      return self.tok(start, Text("", None))
    }
    self.note(InvalidFirstCharacterOfTagName, @span.Span::new(start, start + 3))
    return self.bogus_comment(2)
  }
  if is_alpha(c1) {
    return self.start_tag()
  }
  if c1 == '?' {
    // The `?` is part of the comment's data, per the specification, so that
    // `` comes back as it went in.
    return self.bogus_comment(1)
  }
  // A `<` that begins nothing: literal text, per the specification.
  self.pos = self.pos + 1
  self.tok(start, Text("<", None))
}

// ------------------------------------------------------------------- tags

///|
fn Scanner::start_tag(self : Scanner) -> Token {
  let start = self.pos
  self.pos = self.pos + 1
  let name_start = self.pos
  while self.pos < self.len && is_tag_name_char(self.peek()) {
    self.pos = self.pos + 1
  }
  // NUL is a name character too, replaced with U+FFFD: `` is a tag
  // called `a\u{FFFD}`, not a tag called `a`.
  let name = self.nul_free(name_start, self.pos).to_lower()
  let attrs : Array[RawAttr] = []
  let mut self_closing = false
  while true {
    while self.pos < self.len && is_ws(self.peek()) {
      self.pos = self.pos + 1
    }
    if self.pos >= self.len {
      // A tag that never closed is not a tag. The specification discards it,
      // and so does this -- as a `Bogus` carrying the source it covered, so
      // that the printer echoes exactly what was there instead of inventing a
      // `>` the input did not have.
      self.note(EofInTag, @span.Span::new(start, self.pos))
      return self.tok(start, Bogus(EofInTag, self.slice(start, self.pos)))
    }
    let c = self.peek()
    if c == '>' {
      self.pos = self.pos + 1
      break
    }
    if c == '/' {
      if self.at(self.pos + 1) == '>' {
        self_closing = true
        self.pos = self.pos + 2
        break
      }
      self.note(UnexpectedSolidusInTag, @span.Span::new(self.pos, self.pos + 1))
      self.pos = self.pos + 1
      continue
    }
    if c == '=' {
      // `
` is an attribute NAMED `=x`, per the specification: the `=`
      // is taken into the name rather than skipped. Skipping it silently
      // renames the attribute, which is the kind of difference only a
      // conforming parser notices.
      self.note(
        UnexpectedEqualsSignBeforeAttributeName,
        @span.Span::new(self.pos, self.pos + 1),
      )
      match self.attribute(lead_equals=true) {
        Some(a) => attrs.push(a)
        None => self.pos = self.pos + 1
      }
      continue
    }
    match self.attribute() {
      Some(a) => {
        let mut seen = false
        for existing in attrs {
          if existing.name == a.name {
            seen = true
          }
        }
        if seen {
          self.note(DuplicateAttribute(a.name), a.span)
        } else {
          attrs.push(a)
        }
      }
      // Nothing consumed: step over the character so recovery makes progress.
      None => self.pos = self.pos + 1
    }
  }
  if !self_closing {
    if @names.is_raw_text(name) {
      self.pending = Raw(name)
    } else if @names.is_escapable_raw_text(name) {
      self.pending = Escapable(name)
    }
  }
  self.tok(start, StartTag(name, attrs, self_closing))
}

///|
fn Scanner::end_tag(self : Scanner) -> Token {
  let start = self.pos
  self.pos = self.pos + 2
  let name_start = self.pos
  while self.pos < self.len && is_tag_name_char(self.peek()) {
    self.pos = self.pos + 1
  }
  let name = self.nul_free(name_start, self.pos).to_lower()
  // Attributes on an end tag are a parse error and are dropped, which is what
  // the specification says and what makes `
` harmless.
  while self.pos < self.len && self.peek() != '>' {
    self.pos = self.pos + 1
  }
  if self.pos < self.len {
    self.pos = self.pos + 1
  } else {
    self.note(EofInTag, @span.Span::new(start, self.pos))
    return self.tok(start, Bogus(EofInTag, self.slice(start, self.pos)))
  }
  self.tok(start, EndTag(name))
}

///|
fn Scanner::attribute(self : Scanner, lead_equals? : Bool = false) -> RawAttr? {
  let start = self.pos
  if lead_equals {
    self.pos = self.pos + 1
  }
  while self.pos < self.len && is_attr_name_char(self.peek()) {
    self.pos = self.pos + 1
  }
  if self.pos == start {
    return None
  }
  let name = self.nul_free(start, self.pos).to_lower()
  while self.pos < self.len && is_ws(self.peek()) {
    self.pos = self.pos + 1
  }
  if self.peek() != '=' {
    return Some({
      name,
      value: None,
      raw: None,
      span: @span.Span::new(start, self.pos),
    })
  }
  self.pos = self.pos + 1
  while self.pos < self.len && is_ws(self.peek()) {
    self.pos = self.pos + 1
  }
  let (value, raw) = self.attribute_value()
  Some({
    name,
    value: Some(value),
    raw,
    span: @span.Span::new(start, self.pos),
  })
}

///|
fn Scanner::attribute_value(self : Scanner) -> (String, String?) {
  let quote = self.peek()
  let quoted = quote == '"' || quote == '\''
  if quoted {
    self.pos = self.pos + 1
  }
  let start = self.pos
  let buf = StringBuilder()
  let mut decoded = false
  let mut normalised = false
  while self.pos < self.len {
    let c = self.peek()
    if quoted && c == quote {
      break
    }
    if !quoted && (is_ws(c) || c == '>') {
      break
    }
    if !quoted && (c == '"' || c == '\'' || c == '<' || c == '=' || c == '`') {
      self.note(
        UnexpectedCharacterInUnquotedAttributeValue,
        @span.Span::new(self.pos, self.pos + 1),
      )
    }
    if c == '&' {
      match self.reference(false) {
        Some(text) => {
          buf.write_string(text)
          decoded = true
          continue
        }
        None => ()
      }
    }
    if c == '\u{0}' {
      self.note(
        UnexpectedNullCharacter,
        @span.Span::new(self.pos, self.pos + 1),
      )
      buf.write_char(REPLACEMENT)
      decoded = true
      self.pos = self.pos + 1
      continue
    }
    if self.newline_at(buf) {
      normalised = true
      continue
    }
    buf.write_char(c)
    self.pos = self.pos + 1
  }
  let raw = if decoded || normalised {
    Some(self.slice(start, self.pos))
  } else {
    None
  }
  if quoted && self.pos < self.len {
    self.pos = self.pos + 1
  }
  (buf.to_string(), raw)
}

// -------------------------------------------------------------- raw bodies

///|
/// How deep inside a comment a ``. Inside the
/// inner `` does not end the element. A scanner
/// that stopped at it cuts the script in half, which no browser does -- and a
/// formatter that then rewrote the file would be handing back something that
/// does not run.
priv enum ScriptMode {
  /// Ordinary script data: the next `` ends the element.
  Plain
  /// After a `") {
      mode = Plain
      self.pos = self.pos + 3
      continue
    }
    if mode == Escaped && self.opens_nested_script(self.pos) {
      mode = Double
      self.pos = self.pos + 7
      continue
    }
    if mode == Double && self.is_end_tag_at(self.pos, "script") {
      mode = Escaped
      self.pos = self.pos + 8
      continue
    }
    self.pos = self.pos + 1
  }
}

///|
/// ` Bool {
  if !self.matches_ci(i, "'
}

///|
/// Whether an end tag for `tag` actually begins here.
///
/// ``. `foo Bool {
  if !self.matches_ci(i, "= self.len {
    return false
  }
  let c = self.at(after)
  is_ws(c) || c == '/' || c == '>'
}

///|
/// Everything up to ` Token {
  let start = self.pos
  if tag == "script" {
    self.script_body()
  } else {
    while self.pos < self.len && !self.is_end_tag_at(self.pos, tag) {
      self.pos = self.pos + 1
    }
  }
  if self.pos >= self.len {
    self.note(EofInRawText(tag), @span.Span::new(start, self.pos))
  }
  self.tok(start, RawText(normalize_newlines(self.slice(start, self.pos))))
}

///|
/// Everything up to ` Token {
  let start = self.pos
  let buf = StringBuilder()
  let mut decoded = false
  let mut normalised = false
  while self.pos < self.len && !self.is_end_tag_at(self.pos, tag) {
    if self.peek() == '&' {
      match self.reference(true) {
        Some(text) => {
          buf.write_string(text)
          decoded = true
          continue
        }
        None => ()
      }
    }
    if self.newline_at(buf) {
      normalised = true
      continue
    }
    buf.write_char(self.peek())
    self.pos = self.pos + 1
  }
  if self.pos >= self.len {
    self.note(EofInRawText(tag), @span.Span::new(start, self.pos))
  }
  let raw = if decoded || normalised {
    Some(self.slice(start, self.pos))
  } else {
    None
  }
  self.tok(start, Text(buf.to_string(), raw))
}

// -------------------------------------------------------- declarations

///|
fn Scanner::comment(self : Scanner) -> Token {
  let start = self.pos
  self.pos = self.pos + 4
  // `` and `` close immediately, per the specification.
  if self.matches_ci(self.pos, ">") || self.matches_ci(self.pos, "->") {
    let end = if self.peek() == '>' { self.pos + 1 } else { self.pos + 2 }
    self.pos = end
    self.note(AbruptClosingOfEmptyComment, @span.Span::new(start, self.pos))
    return self.tok(start, Comment(""))
  }
  let body_start = self.pos
  while self.pos < self.len && !self.matches_ci(self.pos, "-->") {
    if self.matches_ci(self.pos, "--!>") {
      let body = self.comment_body(body_start, self.pos)
      self.pos = self.pos + 4
      self.note(IncorrectlyClosedComment, @span.Span::new(start, self.pos))
      return self.tok(start, Comment(body))
    }
    if self.matches_ci(self.pos, "