///|
/// An RFC 6902 add, replace, or remove operation. The empty path points to
/// the entire document. An explicit JSON null is distinct from an absent value.
#derive(Eq, Debug)
pub(all) struct JsonPatch {
  op : String
  path : String
  value : Json?
}

///|
/// Serialize the RFC 6902 operation. The value member is present only when
/// the operation carries a value.
pub impl ToJson for JsonPatch with fn to_json(self) {
  let object : Map[String, Json] = { "op": self.op, "path": self.path }
  if self.value is Some(value) {
    object["value"] = value
  }
  Json::object(object)
}

///|
/// Snapshot of a JSON Pointer's source closure. Synthetic quotes and container
/// delimiters keep a value streaming, even after the transport has finished.
#derive(Eq, Debug)
pub(all) struct FieldSeal {
  pointer : String
  is_sealed : Bool
}

///|
/// Serialize the RFC 6901 pointer and its source-closure flag as sealed.
pub impl ToJson for FieldSeal with fn to_json(self) {
  { "pointer": self.pointer, "sealed": self.is_sealed }
}

///|
priv struct SealTrace {
  mut path : String
  fields : Array[FieldSeal]
}

///|
/// Operations and closure state for a successfully repaired stream prefix.
/// Apply the first frame to JSON null and subsequent frames in delivery order.
#derive(Eq, Debug, ToJson)
pub(all) struct PatchFrame {
  patches : Array[JsonPatch]
  fields : Array[FieldSeal]
  report : RepairReport
}

///|
fn pointer_child(path : String, key : String) -> String {
  path + "/" + key.replace_all(old="~", new="~0").replace_all(old="/", new="~1")
}

///|
fn exact_patch_scalar(a : Json, b : Json) -> Bool {
  match (a, b) {
    (Number(a, repr=ra), Number(b, repr=rb)) =>
      ra.unwrap_or_else(() => a.to_string()) ==
      rb.unwrap_or_else(() => b.to_string())
    (String(a), String(b)) => a == b
    (True, True) | (False, False) | (Null, Null) => true
    _ => false
  }
}

///|
fn patch_value_equal(a : Json, b : Json, depth : Int32) -> Bool {
  if depth > 256 {
    return false
  }
  match (a, b) {
    (Array(a), Array(b)) => {
      if a.length() != b.length() {
        return false
      }
      for index, value in a {
        if !patch_value_equal(value, b[index], depth + 1) {
          return false
        }
      }
      true
    }
    (Object(a), Object(b)) => {
      if a.length() != b.length() {
        return false
      }
      for key, value in a {
        guard b.get(key) is Some(other) else { return false }
        if !patch_value_equal(value, other, depth + 1) {
          return false
        }
      }
      true
    }
    _ => exact_patch_scalar(a, b)
  }
}

///|
fn clone_patch_value(value : Json) -> Json {
  match value {
    Array(items) => Json::array(items.map(clone_patch_value))
    Object(object) => {
      let copy = object.copy()
      for key, item in object {
        copy[key] = clone_patch_value(item)
      }
      Json::object(copy)
    }
    _ => value
  }
}

///|
// Align a bounded pair of changing array middles. Streaming appends and
// suffix edits have an empty or single-cell side and take the direct path.
fn align_patch_array(
  before : ArrayView[Json],
  after : ArrayView[Json],
  path : String,
  offset : Int32,
  depth : Int32,
  patches : Array[JsonPatch],
) -> Unit {
  let old_length = before.length()
  let new_length = after.length()
  let row = new_length + 1
  let cost = FixedArray::make((old_length + 1) * row, 0)
  for i = old_length; i >= 0; i = i - 1 {
    for j = new_length; j >= 0; j = j - 1 {
      let at = i * row + j
      cost[at] = if i == old_length {
        new_length - j
      } else if j == new_length {
        old_length - i
      } else {
        let edit = if patch_value_equal(before[i], after[j], depth) {
          0
        } else {
          1
        }
        (cost[at + row + 1] + edit).min(cost[at + row].min(cost[at + 1]) + 1)
      }
    }
  }
  let mut i = 0
  let mut j = 0
  let mut index = offset
  while i < old_length || j < new_length {
    let at = i * row + j
    if i < old_length &&
      j < new_length &&
      patch_value_equal(before[i], after[j], depth) {
      i += 1
      j += 1
      index += 1
    } else if i < old_length &&
      j < new_length &&
      cost[at] == cost[at + row + 1] + 1 {
      patch_diff(before[i], after[j], "\{path}/\{index}", depth, patches)
      i += 1
      j += 1
      index += 1
    } else if i < old_length && cost[at] == cost[at + row] + 1 {
      patches.push({ op: "remove", path: "\{path}/\{index}", value: None, })
      i += 1
    } else {
      patches.push({
        op: "add",
        path: "\{path}/\{index}",
        value: Some(after[j]),
      })
      j += 1
      index += 1
    }
  }
}

///|
fn patch_array(
  before : Array[Json],
  after : Array[Json],
  path : String,
  depth : Int32,
  patches : Array[JsonPatch],
) -> Unit {
  let mut first = 0
  let mut last_before = before.length()
  let mut last_after = after.length()
  while first < last_before &&
        first < last_after &&
        patch_value_equal(before[first], after[first], depth) {
    first += 1
  }
  while last_before > first &&
        last_after > first &&
        patch_value_equal(before[last_before - 1], after[last_after - 1], depth) {
    last_before -= 1
    last_after -= 1
  }
  let old_middle = last_before - first
  let new_middle = last_after - first
  if old_middle > 1 && new_middle > 1 && old_middle <= 4096 / new_middle {
    align_patch_array(
      before[first:last_before],
      after[first:last_after],
      path,
      first,
      depth,
      patches,
    )
    return
  }
  let shared = if last_before < last_after { last_before } else { last_after }
  for index in first..= shared; index = index - 1 {
    patches.push({ op: "remove", path: "\{path}/\{index}", value: None, })
  }
  for index in shared.. Unit {
  if depth > 256 {
    patches.push({ op: "replace", path, value: Some(after), })
    return
  }
  match (before, after) {
    (Object(before), Object(after)) => {
      for key, value in before {
        match after.get(key) {
          Some(next) =>
            patch_diff(
              value,
              next,
              pointer_child(path, key),
              depth + 1,
              patches,
            )
          None =>
            patches.push({
              op: "remove",
              path: pointer_child(path, key),
              value: None,
            })
        }
      }
      for key, value in after {
        if !before.contains(key) {
          patches.push({
            op: "add",
            path: pointer_child(path, key),
            value: Some(value),
          })
        }
      }
    }
    (Array(before), Array(after)) =>
      patch_array(before, after, path, depth + 1, patches)
    _ =>
      if !exact_patch_scalar(before, after) {
        patches.push({ op: "replace", path, value: Some(after), })
      }
  }
}

///|
/// Generate deterministic structural changes, keeping unchanged branches and
/// common array edges intact. Short changed array runs use edit-distance
/// alignment. Large runs use bounded-memory positional edits. Numbers compare
/// their lossless decimal spelling.
///
/// ```mbt check
/// test {
///   let previous : Json = { "queue": [1] }
///   let current : Json = { "queue": [1, 2] }
///   let patches = @json_repair.diff_json_patches(previous, current)
///   assert_eq(patches[0].path, "/queue/1")
///   assert_eq(
///     @json_repair.apply_json_patches(previous, patches[:]).unwrap(),
///     current,
///   )
/// }
/// ```
pub fn diff_json_patches(previous : Json, next : Json) -> Array[JsonPatch] {
  let patches = []
  patch_diff(previous, next, "", 0, patches)
  patches
}

///|
priv suberror PatchFault {
  BadPatch(String)
}

///|
fn decode_pointer_token(token : StringView) -> String raise PatchFault {
  if !token.contains("~") {
    return token.to_owned()
  }
  let text = StringBuilder()
  let mut start = 0
  let mut index = 0
  while index < token.length() {
    if token[index] != '~' {
      index += 1
      continue
    }
    text.write_view(token.exact_view(start~, end=index))
    let decoded = match char_at(token, index + 1) {
      '0' => '~'
      '1' => '/'
      _ => raise BadPatch("invalid JSON Pointer escape")
    }
    text.write_char(decoded)
    index += 2
    start = index
  }
  text.write_view(token.exact_view(start~))
  text.to_string()
}

///|
fn pointer_tokens(path : String) -> Array[String] raise PatchFault {
  if path == "" {
    return []
  }
  guard path.has_prefix("/") else {
    raise BadPatch("JSON Pointer must start with /")
  }
  let tokens = []
  for token in path[:].exact_view(start=1).split("/") {
    if tokens.length() > 256 {
      raise BadPatch("JSON Pointer exceeds the depth limit")
    }
    tokens.push(decode_pointer_token(token))
  }
  tokens
}

///|
fn pointer_array_index(
  token : String,
  length : Int32,
  insert : Bool,
) -> Int32 raise PatchFault {
  if token == "-" && insert {
    return length
  }
  if token.is_empty() || (token.length() > 1 && token.has_prefix("0")) {
    raise BadPatch("invalid JSON Pointer array index")
  }
  let mut index = 0
  let limit = if insert { length } else { length - 1 }
  for i in 0.. 9 || digit > limit || index > (limit - digit) / 10 {
      raise BadPatch("invalid or out-of-range JSON Pointer array index")
    }
    index = index * 10 + digit
  }
  index
}

///|
fn patch_value(patch : JsonPatch) -> Json raise PatchFault {
  guard patch.value is Some(value) else {
    raise BadPatch("patch operation requires a value")
  }
  value
}

///|
fn apply_patch_at(
  node : Json,
  tokens : ArrayView[String],
  patch : JsonPatch,
) -> Json raise PatchFault {
  guard tokens is [token, .. rest] else {
    if patch.op == "remove" {
      raise BadPatch("removing the document root leaves no JSON value")
    }
    return patch_value(patch)
  }
  match node {
    Object(object) => {
      let copy = object.copy()
      if rest.length() == 0 && patch.op == "add" {
        copy[token] = patch_value(patch)
      } else {
        guard object.get(token) is Some(previous) else {
          raise BadPatch("JSON Pointer does not refer to an existing member")
        }
        if rest.length() == 0 && patch.op == "remove" {
          copy.remove(token)
        } else {
          copy[token] = apply_patch_at(previous, rest, patch)
        }
      }
      Json::object(copy)
    }
    Array(array) => {
      let insert = rest.length() == 0 && patch.op == "add"
      let index = pointer_array_index(token, array.length(), insert)
      let copy = array.copy()
      if insert {
        copy.insert(index, patch_value(patch))
      } else if rest.length() == 0 && patch.op == "remove" {
        ignore(copy.remove(index))
      } else {
        copy[index] = apply_patch_at(array[index], rest, patch)
      }
      Json::array(copy)
    }
    _ => raise BadPatch("JSON Pointer traverses a non-container value")
  }
}

///|
/// Apply add, replace, and remove transactionally, without mutating the input.
/// Root remove is rejected because the result type requires a JSON document.
pub fn apply_json_patches(
  input : Json,
  patches : ArrayView[JsonPatch],
) -> Result[Json, String] {
  let mut current = input
  for index, patch in patches {
    if !(patch.op is ("add" | "replace" | "remove")) {
      return Err("operation \{index}: unsupported patch operation")
    }
    current = try {
      let tokens = pointer_tokens(patch.path)
      apply_patch_at(current, tokens[:], patch)
    } catch {
      BadPatch(message) => return Err("operation \{index}: " + message)
    }
  }
  Ok(current)
}