///| Content-level 3-way merge using Myers diff + diff3 algorithm

///|
pub(all) enum ConflictStyle {
  Merge
  Diff3
}

///|
pub(all) enum MergeFavor {
  NoFavor
  FavorOurs
  FavorTheirs
  FavorUnion
}

///|
pub(all) struct ContentMergeOptions {
  conflict_style : ConflictStyle
  ours_label : String
  base_label : String
  theirs_label : String
  marker_size : Int
  favor : MergeFavor
}

///|
pub fn ContentMergeOptions::default() -> ContentMergeOptions {
  {
    conflict_style: ConflictStyle::Merge,
    ours_label: "HEAD",
    base_label: "parent",
    theirs_label: "incoming",
    marker_size: 7,
    favor: MergeFavor::NoFavor,
  }
}

///|
pub fn ContentMergeOptions::favor_ours() -> ContentMergeOptions {
  { ..ContentMergeOptions::default(), favor: MergeFavor::FavorOurs }
}

///|
pub fn ContentMergeOptions::favor_theirs() -> ContentMergeOptions {
  { ..ContentMergeOptions::default(), favor: MergeFavor::FavorTheirs }
}

///|
pub fn ContentMergeOptions::favor_union() -> ContentMergeOptions {
  { ..ContentMergeOptions::default(), favor: MergeFavor::FavorUnion }
}

///|
pub fn ContentMergeOptions::new(
  conflict_style? : ConflictStyle = ConflictStyle::Merge,
  ours_label? : String = "HEAD",
  base_label? : String = "parent",
  theirs_label? : String = "incoming",
  marker_size? : Int = 7,
  favor? : MergeFavor = MergeFavor::NoFavor,
) -> ContentMergeOptions {
  { conflict_style, ours_label, base_label, theirs_label, marker_size, favor }
}

///|
pub fn ContentMergeOptions::with_diff3(
  self : ContentMergeOptions,
) -> ContentMergeOptions {
  { ..self, conflict_style: ConflictStyle::Diff3 }
}

///|
pub fn ContentMergeOptions::with_labels(
  self : ContentMergeOptions,
  ours~ : String,
  base~ : String,
  theirs~ : String,
) -> ContentMergeOptions {
  { ..self, ours_label: ours, base_label: base, theirs_label: theirs }
}

///|
pub fn ContentMergeOptions::with_marker_size(
  self : ContentMergeOptions,
  size : Int,
) -> ContentMergeOptions {
  { ..self, marker_size: size }
}

///|
pub(all) struct ContentMergeResult {
  content : String
  has_conflicts : Bool
  conflict_count : Int
}

///|
priv enum EditOp {
  Keep(Int, Int)
  Delete(Int)
  Insert(Int)
}

///|
priv struct ChangeRange {
  base_start : Int
  base_end : Int
  new_start : Int
  new_end : Int
}

///|
priv enum Diff3Section {
  Clean(Array[String])
  Conflict(
    ours~ : Array[String],
    base~ : Array[String],
    theirs~ : Array[String]
  )
}

///|
fn split_lines(text : String) -> Array[String] {
  if text.length() == 0 {
    return []
  }
  let lines : Array[String] = []
  let sb = StringBuilder()
  for c in text {
    sb.write_char(c)
    if c == '\n' {
      lines.push(sb.to_string())
      sb.reset()
    }
  }
  let remaining = sb.to_string()
  if remaining.length() > 0 {
    lines.push(remaining)
  }
  lines
}

///|
fn myers_diff(old : Array[String], new : Array[String]) -> Array[EditOp] {
  let n = old.length()
  let m = new.length()
  if n == 0 && m == 0 {
    return []
  }
  if n == 0 {
    return Array::makei(m, fn(j) { EditOp::Insert(j) })
  }
  if m == 0 {
    return Array::makei(n, fn(i) { EditOp::Delete(i) })
  }
  let max = n + m
  let size = 2 * max + 1
  // v[k + max] = x-coordinate of the furthest reaching path for diagonal k
  let v : Array[Int] = Array::make(size, 0)
  // Store traces for backtracking
  let traces : Array[Array[Int]] = []
  let mut found = false
  let mut final_d = 0
  for d = 0; d <= max; d = d + 1 {
    traces.push(v.copy())
    for k = -d; k <= d; k = k + 2 {
      let idx = k + max
      let mut x = if k == -d || (k != d && v[idx - 1] < v[idx + 1]) {
        v[idx + 1]
      } else {
        v[idx - 1] + 1
      }
      let mut y = x - k
      while x < n && y < m && old[x] == new[y] {
        x = x + 1
        y = y + 1
      }
      v[idx] = x
      if x >= n && y >= m {
        final_d = d
        found = true
        break
      }
    }
    if found {
      break
    }
  }
  // Backtrack to find the edit sequence
  let edits : Array[EditOp] = []
  let mut cx = n
  let mut cy = m
  for d = final_d; d > 0; d = d - 1 {
    let prev_v = traces[d]
    let k = cx - cy
    let idx = k + max
    let prev_k = if k == -d || (k != d && prev_v[idx - 1] < prev_v[idx + 1]) {
      k + 1
    } else {
      k - 1
    }
    let prev_x = prev_v[prev_k + max]
    let prev_y = prev_x - prev_k
    // Diagonal moves (matches)
    while cx > prev_x && cy > prev_y {
      cx = cx - 1
      cy = cy - 1
      edits.push(EditOp::Keep(cx, cy))
    }
    if cx > prev_x {
      cx = cx - 1
      edits.push(EditOp::Delete(cx))
    } else if cy > prev_y {
      cy = cy - 1
      edits.push(EditOp::Insert(cy))
    }
  }
  // Remaining diagonal moves at d=0
  while cx > 0 && cy > 0 {
    cx = cx - 1
    cy = cy - 1
    edits.push(EditOp::Keep(cx, cy))
  }
  edits.rev()
}

///|
fn extract_changes(edits : Array[EditOp]) -> Array[ChangeRange] {
  let changes : Array[ChangeRange] = []
  let mut i = 0
  let len = edits.length()
  while i < len {
    match edits[i] {
      Keep(_, _) => i = i + 1
      _ => {
        let mut base_start = -1
        let mut base_end = -1
        let mut new_start = -1
        let mut new_end = -1
        while i < len {
          match edits[i] {
            Keep(_, _) => break
            Delete(bi) => {
              if base_start < 0 {
                base_start = bi
              }
              base_end = bi + 1
              i = i + 1
            }
            Insert(ni) => {
              if new_start < 0 {
                new_start = ni
              }
              new_end = ni + 1
              i = i + 1
            }
          }
        }
        // For insert-only changes, base range is empty at the insert point
        // We need to find the base position from the surrounding context
        if base_start < 0 && base_end < 0 {
          // Pure insert - find position from the new_start
          // The base position is where the insert happens in the base sequence
          // Look at the previous Keep to determine base position
          let pos = find_base_pos_for_insert(edits, i)
          base_start = pos
          base_end = pos
        }
        if base_start < 0 {
          base_start = base_end
        }
        if new_start < 0 && new_end < 0 {
          // Pure delete
          let pos = find_new_pos_for_delete(edits, i)
          new_start = pos
          new_end = pos
        }
        if new_start < 0 {
          new_start = new_end
        }
        changes.push({ base_start, base_end, new_start, new_end })
      }
    }
  }
  changes
}

///|
fn find_base_pos_for_insert(edits : Array[EditOp], current_idx : Int) -> Int {
  // Look backward for the last Keep or Delete to find base position
  let mut j = current_idx - 1
  while j >= 0 {
    match edits[j] {
      Keep(bi, _) => return bi + 1
      Delete(bi) => return bi + 1
      _ => j = j - 1
    }
  }
  0
}

///|
fn find_new_pos_for_delete(edits : Array[EditOp], current_idx : Int) -> Int {
  let mut j = current_idx - 1
  while j >= 0 {
    match edits[j] {
      Keep(_, ni) => return ni + 1
      Insert(ni) => return ni + 1
      _ => j = j - 1
    }
  }
  0
}

///|
fn ranges_overlap(a : ChangeRange, b : ChangeRange) -> Bool {
  // Empty ranges at the same position count as overlapping (both insert at same point)
  if a.base_start == a.base_end && b.base_start == b.base_end {
    a.base_start == b.base_start
  } else if a.base_start == a.base_end {
    // An insert touching either edge of the other side's changed region is
    // a conflict too: the insert's context (the lines right around it) was
    // itself changed by the other side, so there is no unambiguous anchor
    // to place it against. Matches git's merge behavior of conflicting
    // rather than silently reordering/dropping content in this case.
    a.base_start >= b.base_start && a.base_start <= b.base_end
  } else if b.base_start == b.base_end {
    b.base_start >= a.base_start && b.base_start <= a.base_end
  } else {
    a.base_start < b.base_end && b.base_start < a.base_end
  }
}

///|
fn lines_equal(
  a : Array[String],
  a_start : Int,
  a_end : Int,
  b : Array[String],
  b_start : Int,
  b_end : Int,
) -> Bool {
  let a_len = a_end - a_start
  let b_len = b_end - b_start
  if a_len != b_len {
    return false
  }
  for i in 0.. Array[String] {
  let result : Array[String] = []
  for i in start.. Array[Diff3Section] {
  let edits_ours = myers_diff(base, ours)
  let edits_theirs = myers_diff(base, theirs)
  let changes_ours = extract_changes(edits_ours)
  let changes_theirs = extract_changes(edits_theirs)
  let sections : Array[Diff3Section] = []
  let mut oi = 0
  let mut ti = 0
  let mut base_pos = 0
  while oi < changes_ours.length() || ti < changes_theirs.length() {
    let ours_change = if oi < changes_ours.length() {
      Some(changes_ours[oi])
    } else {
      None
    }
    let theirs_change = if ti < changes_theirs.length() {
      Some(changes_theirs[ti])
    } else {
      None
    }
    match (ours_change, theirs_change) {
      (Some(o), Some(t)) =>
        if ranges_overlap(o, t) {
          // The conflict spans the union of every change (from either side)
          // that overlaps it, transitively; each side's text is its version
          // of that whole base range (unchanged lines it kept included).
          let mut s0 = if o.base_start < t.base_start {
            o.base_start
          } else {
            t.base_start
          }
          let mut e0 = if o.base_end > t.base_end { o.base_end } else { t.base_end }
          let mut o_last = oi
          let mut t_last = ti
          let mut grew = true
          while grew {
            grew = false
            let span = { base_start: s0, base_end: e0, new_start: 0, new_end: 0 }
            if o_last + 1 < changes_ours.length() &&
              ranges_overlap(changes_ours[o_last + 1], span) {
              o_last = o_last + 1
              let c = changes_ours[o_last]
              if c.base_end > e0 {
                e0 = c.base_end
              }
              if c.base_start < s0 {
                s0 = c.base_start
              }
              grew = true
            }
            if t_last + 1 < changes_theirs.length() &&
              ranges_overlap(changes_theirs[t_last + 1], span) {
              t_last = t_last + 1
              let c = changes_theirs[t_last]
              if c.base_end > e0 {
                e0 = c.base_end
              }
              if c.base_start < s0 {
                s0 = c.base_start
              }
              grew = true
            }
          }
          let overlap_start = s0
          let overlap_end = e0
          if base_pos < overlap_start {
            sections.push(
              Diff3Section::Clean(slice_lines(base, base_pos, overlap_start)),
            )
          }
          let of = changes_ours[oi]
          let ol = changes_ours[o_last]
          let tf = changes_theirs[ti]
          let tl = changes_theirs[t_last]
          let ours_lines = slice_lines(
            ours,
            of.new_start - (of.base_start - overlap_start),
            ol.new_end + (overlap_end - ol.base_end),
          )
          let theirs_lines = slice_lines(
            theirs,
            tf.new_start - (tf.base_start - overlap_start),
            tl.new_end + (overlap_end - tl.base_end),
          )
          // Check if both sides made the same change
          if lines_equal(
              ours_lines,
              0,
              ours_lines.length(),
              theirs_lines,
              0,
              theirs_lines.length(),
            ) {
            sections.push(Diff3Section::Clean(ours_lines))
          } else {
            let base_lines = slice_lines(base, overlap_start, overlap_end)
            sections.push(
              Diff3Section::Conflict(
                ours=ours_lines,
                base=base_lines,
                theirs=theirs_lines,
              ),
            )
          }
          base_pos = overlap_end
          oi = o_last + 1
          ti = t_last + 1
        } else if o.base_start <= t.base_start {
          // Ours comes first, no overlap
          if base_pos < o.base_start {
            sections.push(
              Diff3Section::Clean(slice_lines(base, base_pos, o.base_start)),
            )
          }
          sections.push(
            Diff3Section::Clean(slice_lines(ours, o.new_start, o.new_end)),
          )
          base_pos = o.base_end
          oi = oi + 1
        } else {
          // Theirs comes first, no overlap
          if base_pos < t.base_start {
            sections.push(
              Diff3Section::Clean(slice_lines(base, base_pos, t.base_start)),
            )
          }
          sections.push(
            Diff3Section::Clean(slice_lines(theirs, t.new_start, t.new_end)),
          )
          base_pos = t.base_end
          ti = ti + 1
        }
      (Some(o), None) => {
        if base_pos < o.base_start {
          sections.push(
            Diff3Section::Clean(slice_lines(base, base_pos, o.base_start)),
          )
        }
        sections.push(
          Diff3Section::Clean(slice_lines(ours, o.new_start, o.new_end)),
        )
        base_pos = o.base_end
        oi = oi + 1
      }
      (None, Some(t)) => {
        if base_pos < t.base_start {
          sections.push(
            Diff3Section::Clean(slice_lines(base, base_pos, t.base_start)),
          )
        }
        sections.push(
          Diff3Section::Clean(slice_lines(theirs, t.new_start, t.new_end)),
        )
        base_pos = t.base_end
        ti = ti + 1
      }
      (None, None) => break
    }
  }
  // Remaining base lines
  if base_pos < base.length() {
    sections.push(
      Diff3Section::Clean(slice_lines(base, base_pos, base.length())),
    )
  }
  sections
}

///|
fn render_marker(
  ch : Char,
  size : Int,
  label : String,
  cr? : Bool = false,
) -> String {
  let sb = StringBuilder()
  for _ in 0.. 0 {
    sb.write_char(' ')
    sb.write_string(label)
  }
  if cr {
    sb.write_char('\r')
  }
  sb.write_char('\n')
  sb.to_string()
}

///|
/// git's is_eol_crlf: 1 when line `i` ends in CRLF, 0 for LF, -1 when it
/// cannot tell (an empty file, or a single line without an end of line).
fn eol_crlf(lines : Array[String], i : Int) -> Int {
  let n = lines.length()
  if n == 0 {
    return -1
  }
  let crlf = fn(l : String) { if l.has_suffix("\r\n") { 1 } else { 0 } }
  if i < n - 1 {
    return crlf(lines[i])
  }
  if lines[i].has_suffix("\n") {
    return crlf(lines[i])
  }
  if i == 0 {
    return -1
  }
  crlf(lines[i - 1])
}

///|
/// git's is_cr_needed: conflict markers follow the end-of-line style of the
/// line before the conflict (or the first line of ours / theirs), then of
/// the base's first line; LF when nothing decides.
fn conflict_needs_cr(
  prev_line : String?,
  ours : Array[String],
  theirs : Array[String],
  base : Array[String],
) -> Bool {
  let style = fn(file : Array[String]) {
    match prev_line {
      Some(l) => if l.has_suffix("\r\n") { 1 } else { 0 }
      None => eol_crlf(file, 0)
    }
  }
  let mut needs = style(ours)
  if needs != 0 {
    needs = style(theirs)
  }
  if needs != 0 {
    needs = eol_crlf(base, 0)
  }
  needs == 1
}

///|
pub fn content_merge(
  base_text : String,
  ours_text : String,
  theirs_text : String,
  options : ContentMergeOptions,
) -> ContentMergeResult {
  let base_lines = split_lines(base_text)
  let ours_lines = split_lines(ours_text)
  let theirs_lines = split_lines(theirs_text)
  let raw_sections = diff3_merge(base_lines, ours_lines, theirs_lines)
  // git's default merge level (XDL_MERGE_ZEALOUS) refines conflicts for the
  // plain "merge" style: lines both sides share move out of the markers,
  // and conflicts separated by at most 3 unchanged lines are joined again.
  let sections = match options.conflict_style {
    ConflictStyle::Merge => zealous_refine(raw_sections)
    ConflictStyle::Diff3 => raw_sections
  }
  let sb = StringBuilder()
  let mut conflict_count = 0
  // The line written just before a conflict (git's "preceding line").
  let mut prev_line : String? = None
  for section in sections {
    match section {
      Diff3Section::Clean(lines) =>
        for line in lines {
          sb.write_string(line)
          prev_line = Some(line)
        }
      Diff3Section::Conflict(ours~, base~, theirs~) =>
        match options.favor {
          MergeFavor::FavorOurs =>
            for line in ours {
              sb.write_string(line)
            }
          MergeFavor::FavorTheirs =>
            for line in theirs {
              sb.write_string(line)
            }
          MergeFavor::FavorUnion => {
            for line in ours {
              sb.write_string(line)
            }
            for line in theirs {
              sb.write_string(line)
            }
          }
          MergeFavor::NoFavor => {
            conflict_count = conflict_count + 1
            let cr = conflict_needs_cr(
              prev_line, ours_lines, theirs_lines, base_lines,
            )
            sb.write_string(
              render_marker('<', options.marker_size, options.ours_label, cr~),
            )
            write_conflict_section(sb, ours, cr~)
            match options.conflict_style {
              ConflictStyle::Diff3 => {
                sb.write_string(
                  render_marker(
                    '|',
                    options.marker_size,
                    options.base_label,
                    cr~,
                  ),
                )
                write_conflict_section(sb, base, cr~)
              }
              ConflictStyle::Merge => ()
            }
            sb.write_string(render_marker('=', options.marker_size, "", cr~))
            write_conflict_section(sb, theirs, cr~)
            sb.write_string(
              render_marker('>', options.marker_size, options.theirs_label, cr~),
            )
            prev_line = Some("\n")
          }
        }
    }
  }
  { content: sb.to_string(), has_conflicts: conflict_count > 0, conflict_count }
}

///|
pub fn is_binary_content(data : Bytes) -> Bool {
  let check_len = if data.length() < 8000 { data.length() } else { 8000 }
  for i in 0.. Unit {
  for line in lines {
    sb.write_string(line)
  }
  if lines.length() > 0 && !lines[lines.length() - 1].has_suffix("\n") {
    sb.write_string(if cr { "\r\n" } else { "\n" })
  }
}

///|
/// Refine and re-join conflict sections like git's xdl_refine_conflicts +
/// xdl_simplify_non_conflicts at XDL_MERGE_ZEALOUS.
fn zealous_refine(sections : Array[Diff3Section]) -> Array[Diff3Section] {
  // 1. Split each conflict along the ours/theirs diff.
  let refined : Array[Diff3Section] = []
  for section in sections {
    match section {
      Diff3Section::Clean(_) => refined.push(section)
      Diff3Section::Conflict(ours~, base~, theirs~) => {
        let changes = extract_changes(myers_diff(ours, theirs))
        if changes.length() == 0 {
          refined.push(Diff3Section::Clean(ours))
          continue
        }
        ignore(base)
        let mut po = 0
        for c in changes {
          if po < c.base_start {
            refined.push(Diff3Section::Clean(slice_lines(ours, po, c.base_start)))
          }
          refined.push(
            Diff3Section::Conflict(
              ours=slice_lines(ours, c.base_start, c.base_end),
              base=[],
              theirs=slice_lines(theirs, c.new_start, c.new_end),
            ),
          )
          po = c.base_end
        }
        if po < ours.length() {
          refined.push(Diff3Section::Clean(slice_lines(ours, po, ours.length())))
        }
      }
    }
  }
  // 2. Merge consecutive clean sections, then join conflicts whose gap is
  //    at most 3 lines.
  let flat : Array[Diff3Section] = []
  for section in refined {
    match (section, flat.last()) {
      (Diff3Section::Clean(a), Some(Diff3Section::Clean(prev))) => {
        ignore(flat.pop())
        let joined = prev.copy()
        joined.append(a)
        flat.push(Diff3Section::Clean(joined))
      }
      _ => flat.push(section)
    }
  }
  let out : Array[Diff3Section] = []
  let mut i = 0
  while i < flat.length() {
    match flat[i] {
      Diff3Section::Conflict(ours~, base~, theirs~) => {
        let o = ours.copy()
        let t = theirs.copy()
        let b = base.copy()
        let mut j = i + 1
        while j + 1 < flat.length() {
          match (flat[j], flat[j + 1]) {
            (Diff3Section::Clean(gap), Diff3Section::Conflict(ours=o2, base=b2, theirs=t2)) if gap.length() <=
              3 => {
              o.append(gap)
              o.append(o2)
              t.append(gap)
              t.append(t2)
              b.append(b2)
              j = j + 2
            }
            _ => break
          }
        }
        out.push(Diff3Section::Conflict(ours=o, base=b, theirs=t))
        i = j
      }
      section => {
        out.push(section)
        i = i + 1
      }
    }
  }
  out
}