///|
enum UnescapeState {
  Normal
  AfterAmp
  Named
  AfterHash
  Decimal
  AfterHexPrefix
  Hex
} derive(Eq)

///|
fn compare_entity_range(
  entity : String,
  input : String,
  begin : Int,
  end : Int,
) -> Int {
  let elen = entity.length()
  let ilen = end - begin
  let n = if elen < ilen { elen } else { ilen }
  let mut i = 0

  while i < n {
    let a = entity[i]
    let b = input[begin + i]
    if a < b {
      return -1
    }
    if a > b {
      return 1
    }
    i += 1
  }

  if elen < ilen {
    -1
  } else if elen > ilen {
    1
  } else {
    0
  }
}

///|
fn find_named_entity(input : String, begin : Int, end : Int) -> String? {
  let mut left = 0
  let mut right = html_entities.length()

  while left < right {
    let mid = (left + right) / 2
    let (name, value) = html_entities[mid]
    let cmp = compare_entity_range(name, input, begin, end)

    if cmp == 0 {
      return Some(value)
    }

    if cmp < 0 {
      left = mid + 1
    } else {
      right = mid
    }
  }

  None
}

///|
fn resolve_legacy_entity(input : String, begin : Int, end : Int) -> String? {
  let len = end - begin
  if len == 2 {
    let s = input[begin:end]
    if s == "lt" {
      return Some("<")
    }
    if s == "gt" {
      return Some(">")
    }
  } else if len == 3 {
    if input[begin:end] == "amp" {
      return Some("&")
    }
  } else if len == 4 {
    let s = input[begin:end]
    if s == "quot" {
      return Some("\"")
    }
    if s == "apos" {
      return Some("'")
    }
    if s == "nbsp" {
      return Some("\u00A0")
    }
  }
  None
}

///|
/// Decodes HTML entities contained in a string.
///
/// Supported entity forms:
///
/// Named entities:
/// - `&`
/// - `<`
/// - `>`
/// - and all entries contained in `html_entities`
///
/// Decimal numeric entities:
/// - `&`
/// - ` `
///
/// Hexadecimal numeric entities:
/// - `&`
/// - ` `
///
/// Legacy entities without semicolons:
/// - `&`
/// - `<`
/// - `>`
/// - `"`
/// - `&apos`
/// - ` `
pub fn unescape(text : String) -> String {
  let len = text.length()
  let mut state = UnescapeState::Normal
  let mut entity_start = 0
  let mut copy_start = 0
  let mut i = 0
  let mut found = false
  let buf = StringBuilder::new(size_hint=len)

  let flush_text = fn(end_idx : Int) {
    if end_idx > copy_start {
      buf.write(text[copy_start:end_idx])
    }
  }

  while i < len {
    let c = text[i]

    match state {
      UnescapeState::Normal =>
        if c == '&' {
          entity_start = i
          state = UnescapeState::AfterAmp
        }
      UnescapeState::AfterAmp =>
        match c {
          '#' => state = UnescapeState::AfterHash
          ';' => state = UnescapeState::Normal
          '&' => entity_start = i
          _ => state = UnescapeState::Named
        }
      UnescapeState::Named =>
        if c == ';' {
          match find_named_entity(text, entity_start + 1, i) {
            Some(decoded) => {
              found = true
              flush_text(entity_start)
              buf.write_string(decoded)
              copy_start = i + 1
            }
            None => ()
          }
          state = UnescapeState::Normal
        } else if c == '&' {
          match resolve_legacy_entity(text, entity_start + 1, i) {
            Some(decoded) => {
              found = true
              flush_text(entity_start)
              buf.write_string(decoded)
              copy_start = i
            }
            None => ()
          }
          entity_start = i
          state = UnescapeState::AfterAmp
        } else if !((c >= 'a' && c <= 'z') ||
          (c >= 'A' && c <= 'Z') ||
          (c >= '0' && c <= '9')) {
          match resolve_legacy_entity(text, entity_start + 1, i) {
            Some(decoded) => {
              found = true
              flush_text(entity_start)
              buf.write_string(decoded)
              copy_start = i
            }
            None => ()
          }
          state = UnescapeState::Normal
        }
      UnescapeState::AfterHash =>
        match c {
          'x' | 'X' => state = UnescapeState::AfterHexPrefix
          ';' => state = UnescapeState::Normal
          '&' => {
            entity_start = i
            state = UnescapeState::AfterAmp
          }
          _ =>
            if c >= '0' && c <= '9' {
              state = UnescapeState::Decimal
            } else {
              state = UnescapeState::Normal
            }
        }
      UnescapeState::Decimal =>
        if c == ';' {
          match parse_decimal(text, entity_start + 2, i) {
            Some(value) =>
              match Int::to_char(value) {
                Some(ch) => {
                  found = true
                  flush_text(entity_start)
                  buf.write_char(ch)
                  copy_start = i + 1
                }
                None => ()
              }
            None => ()
          }
          state = UnescapeState::Normal
        } else if !(c >= '0' && c <= '9') {
          state = UnescapeState::Normal
        }
      UnescapeState::AfterHexPrefix =>
        if c == ';' {
          state = UnescapeState::Normal
        } else if c == '&' {
          entity_start = i
          state = UnescapeState::AfterAmp
        } else if (c >= '0' && c <= '9') ||
          (c >= 'a' && c <= 'f') ||
          (c >= 'A' && c <= 'F') {
          state = UnescapeState::Hex
        } else {
          state = UnescapeState::Normal
        }
      UnescapeState::Hex =>
        if c == ';' {
          match parse_hex(text, entity_start + 3, i) {
            Some(value) =>
              match Int::to_char(value) {
                Some(ch) => {
                  found = true
                  flush_text(entity_start)
                  buf.write_char(ch)
                  copy_start = i + 1
                }
                None => ()
              }
            None => ()
          }
          state = UnescapeState::Normal
        } else if !((c >= '0' && c <= '9') ||
          (c >= 'a' && c <= 'f') ||
          (c >= 'A' && c <= 'F')) {
          state = UnescapeState::Normal
        }
    }
    i += 1
  }

  if !found {
    return text
  }

  if state == UnescapeState::Named {
    match resolve_legacy_entity(text, entity_start + 1, len) {
      Some(decoded) => {
        flush_text(entity_start)
        buf.write_string(decoded)
        copy_start = len
      }
      None => ()
    }
  }

  flush_text(len)

  buf.to_string()
}