///|
pub(all) enum EditOp {
  Equal(String)
  Delete(String)
  Insert(String)
} derive(Eq, Debug)

///|
/// Counts of Unicode characters represented by an edit script.
pub(all) struct DiffStats {
  equal_count : Int
  delete_count : Int
  insert_count : Int
} derive(Eq, Debug)

///|
/// Return a Unicode character-oriented edit script that transforms `old_text`
/// into `new_text`.
///
/// Shared prefixes and suffixes are preserved as `Equal` operations while the
/// changed middle span is minimized with Myers/LCS-style ordering.
pub fn diff(old_text : String, new_text : String) -> Array[EditOp] {
  let old_chars = old_text.to_array()
  let new_chars = new_text.to_array()
  let old_len = old_chars.length()
  let new_len = new_chars.length()
  let prefix_len = common_prefix_len(old_chars, new_chars, old_len, new_len)
  let suffix_len = common_suffix_len(
    old_chars, new_chars, old_len, new_len, prefix_len,
  )
  let old_middle = copy_char_range(old_chars, prefix_len, old_len - suffix_len)
  let new_middle = copy_char_range(new_chars, prefix_len, new_len - suffix_len)
  let middle_script = diff_middle(old_middle, new_middle)
  let edit_script = Array::new(
    capacity=prefix_len + middle_script.length() + suffix_len,
  )
  push_equal_range(edit_script, old_chars, 0, prefix_len)
  push_script(edit_script, middle_script)
  push_equal_range(edit_script, old_chars, old_len - suffix_len, old_len)
  edit_script
}

///|
/// Render a unified diff string for line-oriented text changes.
///
/// Returns an empty string for equal input after CRLF, LF, and CR normalization.
/// The output uses `--- old`, `+++ new`, and one hunk covering the full input.
pub fn unified_diff(old_text : String, new_text : String) -> String {
  let old_source = normalize_line_endings(old_text)
  let new_source = normalize_line_endings(new_text)
  if old_source == new_source {
    return ""
  }
  let old_lines = split_lines(old_source)
  let new_lines = split_lines(new_source)
  let line_script = line_diff(old_lines, new_lines)
  render_unified_diff(line_script, old_lines.length(), new_lines.length())
}

///|
/// Merge adjacent operations of the same kind into larger text spans.
///
/// `diff` emits one operation per Unicode character. `compact` is convenient
/// for display and transport while preserving the represented old and new
/// texts.
pub fn compact(edit_script : Array[EditOp]) -> Array[EditOp] {
  let result = Array::new(capacity=edit_script.length())
  for offset = 0; offset < edit_script.length(); offset = offset + 1 {
    let operation = edit_script[offset]
    if result.length() == 0 {
      result.push(operation)
    } else {
      let last = result.length() - 1
      match (result[last], operation) {
        (Equal(left), Equal(right)) => result[last] = Equal(left + right)
        (Delete(left), Delete(right)) => result[last] = Delete(left + right)
        (Insert(left), Insert(right)) => result[last] = Insert(left + right)
        (_, next) => result.push(next)
      }
    }
  }
  result
}

///|
/// Reconstruct the original text represented by an edit script.
pub fn reconstruct_old(edit_script : Array[EditOp]) -> String {
  let output = StringBuilder()
  for operation in edit_script {
    match operation {
      Equal(text) | Delete(text) => output.write_string(text)
      Insert(_) => ()
    }
  }
  output.to_string()
}

///|
/// Reconstruct the updated text represented by an edit script.
pub fn reconstruct_new(edit_script : Array[EditOp]) -> String {
  let output = StringBuilder()
  for operation in edit_script {
    match operation {
      Equal(text) | Insert(text) => output.write_string(text)
      Delete(_) => ()
    }
  }
  output.to_string()
}

///|
/// Count equal, deleted, and inserted Unicode characters in an edit script.
///
/// The function also accepts compacted scripts and counts their contents by
/// Unicode scalar value rather than UTF-16 code unit length.
pub fn stats(edit_script : Array[EditOp]) -> DiffStats {
  let mut equal_count = 0
  let mut delete_count = 0
  let mut insert_count = 0
  for operation in edit_script {
    match operation {
      Equal(text) => equal_count = equal_count + text.to_array().length()
      Delete(text) => delete_count = delete_count + text.to_array().length()
      Insert(text) => insert_count = insert_count + text.to_array().length()
    }
  }
  { equal_count, delete_count, insert_count }
}

///|
/// Render a Unified Diff with custom labels and a bounded amount of context.
///
/// Distant changes are emitted as separate hunks. A negative `context` value
/// is treated as zero. Labels have CR and LF characters replaced with spaces
/// so they cannot break the diff header.
pub fn unified_diff_with_context(
  old_text : String,
  new_text : String,
  old_label : String,
  new_label : String,
  context : Int,
) -> String {
  let old_source = normalize_line_endings(old_text)
  let new_source = normalize_line_endings(new_text)
  if old_source == new_source {
    return ""
  }
  let old_lines = split_lines(old_source)
  let new_lines = split_lines(new_source)
  let line_script = line_diff(old_lines, new_lines)
  render_context_diff(
    line_script,
    sanitize_label(old_label),
    sanitize_label(new_label),
    if context < 0 {
      0
    } else {
      context
    },
  )
}

///|
fn diff_middle(old_text : Array[Char], new_text : Array[Char]) -> Array[EditOp] {
  let total_len = old_text.length() + new_text.length()
  if total_len < 32 {
    return traceback_script(old_text, new_text, total_len)
  }
  let edit_distance = myers_distance(old_text, new_text)
  traceback_script(old_text, new_text, edit_distance)
}

///|
fn myers_distance(old_text : Array[Char], new_text : Array[Char]) -> Int {
  let old_len = old_text.length()
  let new_len = new_text.length()
  if old_len == 0 {
    return new_len
  }
  if new_len == 0 {
    return old_len
  }
  let max_depth = old_len + new_len
  let diagonal_offset = max_depth + 1
  let v_curr = Array::make(max_depth * 2 + 3, -1)
  v_curr[diagonal_offset + 1] = 0
  for depth = 0; depth <= max_depth; depth = depth + 1 {
    for diagonal = -depth; diagonal <= depth; diagonal = diagonal + 2 {
      let from_insert = v_curr[diagonal_offset + diagonal + 1]
      let from_delete = v_curr[diagonal_offset + diagonal - 1] + 1
      let x_start = if diagonal == -depth ||
        (diagonal != depth && from_insert > from_delete) {
        from_insert
      } else {
        from_delete
      }
      let mut x_curr = x_start
      let mut y_curr = x_curr - diagonal
      while x_curr < old_len &&
            y_curr < new_len &&
            old_text[x_curr] == new_text[y_curr] {
        x_curr = x_curr + 1
        y_curr = y_curr + 1
      }
      v_curr[diagonal_offset + diagonal] = x_curr
      if x_curr >= old_len && y_curr >= new_len {
        return depth
      }
    }
  }
  max_depth
}

///|
fn traceback_script(
  old_text : Array[Char],
  new_text : Array[Char],
  edit_distance : Int,
) -> Array[EditOp] {
  let old_len = old_text.length()
  let new_len = new_text.length()
  if old_len == 0 && new_len == 0 {
    return Array::new(capacity=0)
  }
  if old_len == 0 {
    return insert_only_script(new_text)
  }
  if new_len == 0 {
    return delete_only_script(old_text)
  }
  if old_len == 1 && new_len == 1 {
    return single_pair_script(old_text, new_text)
  }
  let matrix_width = new_len + 1
  let lcs_score = Array::make((old_len + 1) * matrix_width, 0)
  for old_back = 0; old_back < old_len; old_back = old_back + 1 {
    let old_pos = old_len - old_back - 1
    for new_back = 0; new_back < new_len; new_back = new_back + 1 {
      let new_pos = new_len - new_back - 1
      let score_pos = score_index(old_pos, new_pos, matrix_width)
      if old_text[old_pos] == new_text[new_pos] {
        lcs_score[score_pos] = lcs_score[score_index(
            old_pos + 1,
            new_pos + 1,
            matrix_width,
          )] +
          1
      } else {
        let delete_score = lcs_score[score_index(
            old_pos + 1,
            new_pos,
            matrix_width,
          )]
        let insert_score = lcs_score[score_index(
            old_pos,
            new_pos + 1,
            matrix_width,
          )]
        lcs_score[score_pos] = if delete_score >= insert_score {
          delete_score
        } else {
          insert_score
        }
      }
    }
  }
  let edit_script = Array::new(capacity=edit_distance + lcs_score[0])
  let mut old_pos = 0
  let mut new_pos = 0
  while old_pos < old_len && new_pos < new_len {
    let old_slice = old_text[old_pos]
    let new_slice = new_text[new_pos]
    if old_slice == new_slice {
      edit_script.push(Equal(old_slice.to_string()))
      old_pos = old_pos + 1
      new_pos = new_pos + 1
    } else {
      let delete_score = lcs_score[score_index(
          old_pos + 1,
          new_pos,
          matrix_width,
        )]
      let insert_score = lcs_score[score_index(
          old_pos,
          new_pos + 1,
          matrix_width,
        )]
      if should_take_delete(delete_score, insert_score) {
        edit_script.push(Delete(old_slice.to_string()))
        old_pos = old_pos + 1
      } else {
        edit_script.push(Insert(new_slice.to_string()))
        new_pos = new_pos + 1
      }
    }
  }
  while old_pos < old_len {
    edit_script.push(Delete(old_text[old_pos].to_string()))
    old_pos = old_pos + 1
  }
  while new_pos < new_len {
    edit_script.push(Insert(new_text[new_pos].to_string()))
    new_pos = new_pos + 1
  }
  edit_script
}

///|
fn split_lines(text : String) -> Array[String] {
  if text.length() == 0 {
    return Array::new(capacity=0)
  }
  text.split("\n").map(line => line.to_owned()).to_array()
}

///|
fn normalize_line_endings(text : String) -> String {
  let output = StringBuilder()
  let chars = text.to_array()
  let mut offset = 0
  while offset < chars.length() {
    let current = chars[offset]
    if current == '\r' {
      output.write_string("\n")
      if offset + 1 < chars.length() && chars[offset + 1] == '\n' {
        offset = offset + 2
      } else {
        offset = offset + 1
      }
    } else {
      output.write_char(current)
      offset = offset + 1
    }
  }
  output.to_string()
}

///|
fn line_diff(
  old_lines : Array[String],
  new_lines : Array[String],
) -> Array[EditOp] {
  let old_len = old_lines.length()
  let new_len = new_lines.length()
  if old_len == 0 {
    return insert_lines(new_lines)
  }
  if new_len == 0 {
    return delete_lines(old_lines)
  }
  let matrix_width = new_len + 1
  let lcs_score = Array::make((old_len + 1) * matrix_width, 0)
  for old_back = 0; old_back < old_len; old_back = old_back + 1 {
    let old_pos = old_len - old_back - 1
    for new_back = 0; new_back < new_len; new_back = new_back + 1 {
      let new_pos = new_len - new_back - 1
      let score_pos = score_index(old_pos, new_pos, matrix_width)
      if old_lines[old_pos] == new_lines[new_pos] {
        lcs_score[score_pos] = lcs_score[score_index(
            old_pos + 1,
            new_pos + 1,
            matrix_width,
          )] +
          1
      } else {
        let delete_score = lcs_score[score_index(
            old_pos + 1,
            new_pos,
            matrix_width,
          )]
        let insert_score = lcs_score[score_index(
            old_pos,
            new_pos + 1,
            matrix_width,
          )]
        lcs_score[score_pos] = if delete_score >= insert_score {
          delete_score
        } else {
          insert_score
        }
      }
    }
  }
  let line_script = Array::new(capacity=old_len + new_len)
  let mut old_pos = 0
  let mut new_pos = 0
  while old_pos < old_len && new_pos < new_len {
    let old_line = old_lines[old_pos]
    let new_line = new_lines[new_pos]
    if old_line == new_line {
      line_script.push(Equal(old_line))
      old_pos = old_pos + 1
      new_pos = new_pos + 1
    } else {
      let delete_score = lcs_score[score_index(
          old_pos + 1,
          new_pos,
          matrix_width,
        )]
      let insert_score = lcs_score[score_index(
          old_pos,
          new_pos + 1,
          matrix_width,
        )]
      if should_take_delete(delete_score, insert_score) {
        line_script.push(Delete(old_line))
        old_pos = old_pos + 1
      } else {
        line_script.push(Insert(new_line))
        new_pos = new_pos + 1
      }
    }
  }
  while old_pos < old_len {
    line_script.push(Delete(old_lines[old_pos]))
    old_pos = old_pos + 1
  }
  while new_pos < new_len {
    line_script.push(Insert(new_lines[new_pos]))
    new_pos = new_pos + 1
  }
  line_script
}

///|
fn insert_lines(new_lines : Array[String]) -> Array[EditOp] {
  let line_script = Array::new(capacity=new_lines.length())
  for new_pos = 0; new_pos < new_lines.length(); new_pos = new_pos + 1 {
    line_script.push(Insert(new_lines[new_pos]))
  }
  line_script
}

///|
fn delete_lines(old_lines : Array[String]) -> Array[EditOp] {
  let line_script = Array::new(capacity=old_lines.length())
  for old_pos = 0; old_pos < old_lines.length(); old_pos = old_pos + 1 {
    line_script.push(Delete(old_lines[old_pos]))
  }
  line_script
}

///|
fn render_unified_diff(
  line_script : Array[EditOp],
  old_len : Int,
  new_len : Int,
) -> String {
  let output = StringBuilder()
  output.write_string("--- old\n")
  output.write_string("+++ new\n")
  output.write_string("@@ -1,\{old_len} +1,\{new_len} @@\n")
  for offset = 0; offset < line_script.length(); offset = offset + 1 {
    match line_script[offset] {
      Equal(line) => output.write_string(" \{line}\n")
      Delete(line) => output.write_string("-\{line}\n")
      Insert(line) => output.write_string("+\{line}\n")
    }
  }
  output.to_string()
}

///|
fn render_context_diff(
  line_script : Array[EditOp],
  old_label : String,
  new_label : String,
  context : Int,
) -> String {
  let hunk_starts : Array[Int] = []
  let hunk_ends : Array[Int] = []
  for offset = 0; offset < line_script.length(); offset = offset + 1 {
    if !(line_script[offset] is Equal(_)) {
      let start = if offset > context { offset - context } else { 0 }
      let proposed_end = offset + context + 1
      let end = if proposed_end < line_script.length() {
        proposed_end
      } else {
        line_script.length()
      }
      if hunk_starts.length() == 0 {
        hunk_starts.push(start)
        hunk_ends.push(end)
      } else {
        let last = hunk_ends.length() - 1
        if start <= hunk_ends[last] {
          if end > hunk_ends[last] {
            hunk_ends[last] = end
          }
        } else {
          hunk_starts.push(start)
          hunk_ends.push(end)
        }
      }
    }
  }
  let output = StringBuilder()
  output.write_string("--- \{old_label}\n")
  output.write_string("+++ \{new_label}\n")
  for hunk = 0; hunk < hunk_starts.length(); hunk = hunk + 1 {
    render_hunk(output, line_script, hunk_starts[hunk], hunk_ends[hunk])
  }
  output.to_string()
}

///|
fn render_hunk(
  output : StringBuilder,
  line_script : Array[EditOp],
  start : Int,
  end : Int,
) -> Unit {
  let mut old_before = 0
  let mut new_before = 0
  for offset = 0; offset < start; offset = offset + 1 {
    match line_script[offset] {
      Equal(_) => {
        old_before = old_before + 1
        new_before = new_before + 1
      }
      Delete(_) => old_before = old_before + 1
      Insert(_) => new_before = new_before + 1
    }
  }
  let mut old_count = 0
  let mut new_count = 0
  for offset = start; offset < end; offset = offset + 1 {
    match line_script[offset] {
      Equal(_) => {
        old_count = old_count + 1
        new_count = new_count + 1
      }
      Delete(_) => old_count = old_count + 1
      Insert(_) => new_count = new_count + 1
    }
  }
  let old_start = if old_count == 0 { old_before } else { old_before + 1 }
  let new_start = if new_count == 0 { new_before } else { new_before + 1 }
  output.write_string(
    "@@ -\{old_start},\{old_count} +\{new_start},\{new_count} @@\n",
  )
  for offset = start; offset < end; offset = offset + 1 {
    match line_script[offset] {
      Equal(line) => output.write_string(" \{line}\n")
      Delete(line) => output.write_string("-\{line}\n")
      Insert(line) => output.write_string("+\{line}\n")
    }
  }
}

///|
fn sanitize_label(label : String) -> String {
  let output = StringBuilder()
  for character in label {
    if character == '\r' || character == '\n' {
      output.write_char(' ')
    } else {
      output.write_char(character)
    }
  }
  output.to_string()
}

///|
fn should_take_delete(delete_score : Int, insert_score : Int) -> Bool {
  delete_score >= insert_score
}

///|
fn common_prefix_len(
  old_text : Array[Char],
  new_text : Array[Char],
  old_len : Int,
  new_len : Int,
) -> Int {
  let max_len = if old_len < new_len { old_len } else { new_len }
  let mut offset = 0
  while offset < max_len && old_text[offset] == new_text[offset] {
    offset = offset + 1
  }
  offset
}

///|
fn common_suffix_len(
  old_text : Array[Char],
  new_text : Array[Char],
  old_len : Int,
  new_len : Int,
  prefix_len : Int,
) -> Int {
  let max_len = if old_len < new_len { old_len } else { new_len }
  let mut offset = 0
  while offset < max_len - prefix_len &&
        old_text[old_len - offset - 1] == new_text[new_len - offset - 1] {
    offset = offset + 1
  }
  offset
}

///|
fn push_equal_range(
  edit_script : Array[EditOp],
  text : Array[Char],
  start : Int,
  end : Int,
) -> Unit {
  for offset = start; offset < end; offset = offset + 1 {
    edit_script.push(Equal(text[offset].to_string()))
  }
}

///|
fn push_script(
  edit_script : Array[EditOp],
  other_script : Array[EditOp],
) -> Unit {
  for offset = 0; offset < other_script.length(); offset = offset + 1 {
    edit_script.push(other_script[offset])
  }
}

///|
fn insert_only_script(new_text : Array[Char]) -> Array[EditOp] {
  let new_len = new_text.length()
  let edit_script = Array::new(capacity=new_len)
  for new_pos = 0; new_pos < new_len; new_pos = new_pos + 1 {
    edit_script.push(Insert(new_text[new_pos].to_string()))
  }
  edit_script
}

///|
fn delete_only_script(old_text : Array[Char]) -> Array[EditOp] {
  let old_len = old_text.length()
  let edit_script = Array::new(capacity=old_len)
  for old_pos = 0; old_pos < old_len; old_pos = old_pos + 1 {
    edit_script.push(Delete(old_text[old_pos].to_string()))
  }
  edit_script
}

///|
fn single_pair_script(
  old_text : Array[Char],
  new_text : Array[Char],
) -> Array[EditOp] {
  let old_slice = old_text[0]
  let new_slice = new_text[0]
  let edit_script = Array::new(capacity=2)
  if old_slice == new_slice {
    edit_script.push(Equal(old_slice.to_string()))
  } else {
    edit_script.push(Delete(old_slice.to_string()))
    edit_script.push(Insert(new_slice.to_string()))
  }
  edit_script
}

///|
fn score_index(old_pos : Int, new_pos : Int, matrix_width : Int) -> Int {
  old_pos * matrix_width + new_pos
}

///|
fn copy_char_range(chars : Array[Char], start : Int, end : Int) -> Array[Char] {
  let result = Array::new(capacity=end - start)
  for offset = start; offset < end; offset = offset + 1 {
    result.push(chars[offset])
  }
  result
}