///|
/// Serialize a parsed value without insignificant whitespace. Object members
/// are sorted recursively using UTF-16 code units, as required by RFC 8785.
/// Number spelling is normalized by `canonical_number` and is kept separate
/// so its IEEE-754 policy can be tested independently.
pub fn canonicalize(value : JsonValue) -> Result[String, CanonicalError] {
  canonical_value(value)
}

///|
fn canonical_value(value : JsonValue) -> Result[String, CanonicalError] {
  match value {
    Null => Ok("null")
    Bool(value) => Ok(if value { "true" } else { "false" })
    Number(value) => canonical_number(value)
    String(value) => Ok(canonical_string(value))
    Array(values) => {
      let mut output = "["
      let mut first = true
      for value in values {
        if !first {
          output = output + ","
        }
        first = false
        match canonical_value(value) {
          Ok(serialized) => output = output + serialized
          Err(error) => return Err(error)
        }
      }
      Ok(output + "]")
    }
    Object(entries) => canonical_object(entries)
  }
}

///|
fn canonical_object(
  entries : Array[(String, JsonValue)],
) -> Result[String, CanonicalError] {
  let ordered : Array[(String, JsonValue)] = []
  for entry in entries {
    ordered.push(entry)
  }
  sort_entries(ordered)
  let mut output = "{"
  let mut first = true
  for entry in ordered {
    let (key, value) = entry
    if !first {
      output = output + ","
    }
    first = false
    let serialized = match canonical_value(value) {
      Ok(serialized) => serialized
      Err(error) => return Err(error)
    }
    output = output + canonical_string(key) + ":" + serialized
  }
  Ok(output + "}")
}

///|
fn sort_entries(entries : Array[(String, JsonValue)]) -> Unit {
  let mut index = 1
  while index < entries.length() {
    let current = entries[index]
    let mut cursor = index
    while cursor > 0 && compare_keys(entries[cursor - 1].0, current.0) > 0 {
      entries[cursor] = entries[cursor - 1]
      cursor = cursor - 1
    }
    entries[cursor] = current
    index = index + 1
  }
}

///|
fn compare_keys(left : String, right : String) -> Int {
  let left_units = utf16_units(left)
  let right_units = utf16_units(right)
  let common = if left_units.length() < right_units.length() {
    left_units.length()
  } else {
    right_units.length()
  }
  let mut index = 0
  while index < common {
    if left_units[index] < right_units[index] {
      return -1
    }
    if left_units[index] > right_units[index] {
      return 1
    }
    index = index + 1
  }
  if left_units.length() < right_units.length() {
    -1
  } else if left_units.length() > right_units.length() {
    1
  } else {
    0
  }
}

///|
fn utf16_units(text : String) -> Array[Int] {
  let units : Array[Int] = []
  for char in text {
    let code = char.to_int()
    if code <= 0xffff {
      units.push(code)
    } else {
      units.push(0xd800 + (code - 0x10000) / 0x400)
      units.push(0xdc00 + (code - 0x10000) % 0x400)
    }
  }
  units
}

///|
fn canonical_string(value : String) -> String {
  let mut output = "\""
  for char in value {
    let code = char.to_int()
    if char == '"' {
      output = output + "\\\""
    } else if char == '\\' {
      output = output + "\\\\"
    } else if char == '\b' {
      output = output + "\\b"
    } else if char == '\f' {
      output = output + "\\f"
    } else if char == '\n' {
      output = output + "\\n"
    } else if char == '\r' {
      output = output + "\\r"
    } else if char == '\t' {
      output = output + "\\t"
    } else if code < 0x20 {
      output = output + "\\u" + four_hex(code)
    } else {
      output = output + char.to_string()
    }
  }
  output + "\""
}

///|
fn four_hex(value : Int) -> String {
  hex_digit((value >> 12) & 0xf).to_string() +
  hex_digit((value >> 8) & 0xf).to_string() +
  hex_digit((value >> 4) & 0xf).to_string() +
  hex_digit(value & 0xf).to_string()
}

///|
fn hex_digit(value : Int) -> Char {
  if value < 10 {
    (value + '0'.to_int()).unsafe_to_char()
  } else {
    (value - 10 + 'a'.to_int()).unsafe_to_char()
  }
}

///|
/// Parse with the core correctly-rounded decimal parser, then use its Ryu
/// shortest-round-trip serializer for the canonical number spelling.
fn canonical_number(value : String) -> Result[String, CanonicalError] {
  let number = @string.parse_double(value) catch {
    _ => return Err(InvalidNumber(value, "invalid finite decimal"))
  }
  if number.is_nan() || number.is_inf() {
    Err(NonFiniteNumber(value))
  } else {
    Ok(number.to_string())
  }
}