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

///|
/// A validation failure while applying an edit script to source text.
///
/// Every offset is measured in Unicode scalar values.
pub(all) enum ApplyError {
  SourceExhausted(Int, String)
  SourceMismatch(Int, String, String)
  SourceNotFullyConsumed(Int, 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)

///|
priv enum DiffStep {
  Keep(Int)
  Remove(Int)
  Add(Int)
}

///|
/// 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 }
}

///|
/// Apply an edit script to `source` after validating all equal and deleted
/// spans against it.
///
/// The function accepts both per-character scripts from `diff` and merged
/// scripts from `compact`.
pub fn apply(
  edit_script : Array[EditOp],
  source : String,
) -> Result[String, ApplyError] {
  let source_chars = source.to_array()
  let output = StringBuilder()
  let mut source_offset = 0
  for operation in edit_script {
    match operation {
      Insert(text) => output.write_string(text)
      Equal(text) =>
        match consume_span(source_chars, source_offset, text) {
          Ok(next_offset) => {
            output.write_string(text)
            source_offset = next_offset
          }
          Err(error) => return Err(error)
        }
      Delete(text) =>
        match consume_span(source_chars, source_offset, text) {
          Ok(next_offset) => source_offset = next_offset
          Err(error) => return Err(error)
        }
    }
  }
  if source_offset < source_chars.length() {
    let remaining = StringBuilder()
    for offset = source_offset
        offset < source_chars.length()
        offset = offset + 1 {
      remaining.write_char(source_chars[offset])
    }
    return Err(SourceNotFullyConsumed(source_offset, remaining.to_string()))
  }
  Ok(output.to_string())
}

///|
/// Reverse the direction of an edit script.
///
/// Equal operations are preserved, deletes become inserts, and inserts become
/// deletes. Applying the inverted script to the new text reconstructs the old
/// text.
pub fn invert(edit_script : Array[EditOp]) -> Array[EditOp] {
  edit_script.map(operation => {
    match operation {
      Equal(text) => Equal(text)
      Delete(text) => Insert(text)
      Insert(text) => Delete(text)
    }
  })
}

///|
/// 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 steps = myers_steps(old_text, new_text)
  let edit_script = Array::new(capacity=steps.length())
  for step in steps {
    match step {
      Keep(index) => edit_script.push(Equal(old_text[index].to_string()))
      Remove(index) => edit_script.push(Delete(old_text[index].to_string()))
      Add(index) => edit_script.push(Insert(new_text[index].to_string()))
    }
  }
  edit_script
}

///|
fn[T : Eq] myers_steps(
  old_items : Array[T],
  new_items : Array[T],
) -> Array[DiffStep] {
  let old_len = old_items.length()
  let new_len = new_items.length()
  if old_len == 0 && new_len == 0 {
    return []
  }
  let max_depth = old_len + new_len
  let diagonal_offset = max_depth + 1
  let v_curr = Array::make(max_depth * 2 + 3, -1)
  let trace : Array[Array[Int]] = []
  v_curr[diagonal_offset + 1] = 0
  for depth = 0; depth <= max_depth; depth = depth + 1 {
    trace.push(v_curr.copy())
    for diagonal = -depth; diagonal <= depth; diagonal = diagonal + 2 {
      let x_start = if diagonal == -depth ||
        (
          diagonal != depth &&
          v_curr[diagonal_offset + diagonal - 1] <
          v_curr[diagonal_offset + diagonal + 1]
        ) {
        v_curr[diagonal_offset + diagonal + 1]
      } else {
        v_curr[diagonal_offset + diagonal - 1] + 1
      }
      let mut x_curr = x_start
      let mut y_curr = x_curr - diagonal
      while x_curr < old_len &&
            y_curr < new_len &&
            old_items[x_curr] == new_items[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 traceback_steps(old_len, new_len, trace, depth, diagonal_offset)
      }
    }
  }
  []
}

///|
fn traceback_steps(
  old_len : Int,
  new_len : Int,
  trace : Array[Array[Int]],
  edit_distance : Int,
  diagonal_offset : Int,
) -> Array[DiffStep] {
  let reversed = Array::new(capacity=old_len + new_len)
  let mut x_curr = old_len
  let mut y_curr = new_len
  for depth = edit_distance; depth > 0; depth = depth - 1 {
    let v_prev = trace[depth]
    let diagonal = x_curr - y_curr
    let prev_diagonal = if diagonal == -depth ||
      (
        diagonal != depth &&
        v_prev[diagonal_offset + diagonal - 1] <
        v_prev[diagonal_offset + diagonal + 1]
      ) {
      diagonal + 1
    } else {
      diagonal - 1
    }
    let prev_x = v_prev[diagonal_offset + prev_diagonal]
    let prev_y = prev_x - prev_diagonal
    while x_curr > prev_x && y_curr > prev_y {
      reversed.push(Keep(x_curr - 1))
      x_curr = x_curr - 1
      y_curr = y_curr - 1
    }
    if x_curr == prev_x {
      reversed.push(Add(y_curr - 1))
      y_curr = y_curr - 1
    } else {
      reversed.push(Remove(x_curr - 1))
      x_curr = x_curr - 1
    }
  }
  while x_curr > 0 && y_curr > 0 {
    reversed.push(Keep(x_curr - 1))
    x_curr = x_curr - 1
    y_curr = y_curr - 1
  }
  while x_curr > 0 {
    reversed.push(Remove(x_curr - 1))
    x_curr = x_curr - 1
  }
  while y_curr > 0 {
    reversed.push(Add(y_curr - 1))
    y_curr = y_curr - 1
  }
  reversed.rev_in_place()
  reversed
}

///|
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 steps = myers_steps(old_lines, new_lines)
  let line_script = Array::new(capacity=steps.length())
  for step in steps {
    match step {
      Keep(index) => line_script.push(Equal(old_lines[index]))
      Remove(index) => line_script.push(Delete(old_lines[index]))
      Add(index) => line_script.push(Insert(new_lines[index]))
    }
  }
  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 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 consume_span(
  source : Array[Char],
  start : Int,
  expected_text : String,
) -> Result[Int, ApplyError] {
  let expected = expected_text.to_array()
  let mut offset = start
  for expected_char in expected {
    let expected_string = expected_char.to_string()
    if offset >= source.length() {
      return Err(SourceExhausted(offset, expected_string))
    }
    let actual_string = source[offset].to_string()
    if source[offset] != expected_char {
      return Err(SourceMismatch(offset, expected_string, actual_string))
    }
    offset = offset + 1
  }
  Ok(offset)
}

///|
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
}