Auto-resolve merge conflict (neovim)

resolve_conflict.lua

---Automatically resolves a conflict line-by-line.
---@param buf? integer
local function resolve_conflict(buf)
  buf = buf or api.nvim_get_current_buf()

  ---@param buf integer
  ---@param regex string|vim.regex
  ---@param start integer line to start searching from
  ---@param backwards? boolean search backwards
  ---@return integer? lnum
  ---@return string? match
  local function findln(buf, regex, start, backwards)
    local stop, inc

    if backwards then
      stop, inc = 0, -1
    else
      stop, inc = api.nvim_buf_line_count(buf) - 1, 1
    end

    if type(regex) == 'string' then regex = vim.regex(regex) end

    for i = start, stop, inc do
      local scol, ecol = regex:match_line(buf, i)

      if scol then
        ---@cast ecol -?
        return i, api.nvim_buf_get_text(buf, i, scol, i, ecol, {})[1]
      end
    end
  end

  ---Automatically resolves a conflict line-by-line.
  ---@param base string[]
  ---@param ours string[]
  ---@param theirs string[]
  ---@return string[]
  local function resolve(base, ours, theirs)
    local res = {}

    -- TODO: This needs some work. Currently fails if text is added to start or
    -- end of base line.
    ---@param base_line string corresonding line from base
    ---@param line string corresponding changed line to compare
    ---@return integer offset the first differing byte from the start (incl)
    ---@return integer offset the first differing byte from the end (incl)
    local function getpos(base_line, line)
      local st, en
      for i = 1, #base_line do
        if base_line:sub(i, i) ~= line:sub(i, i) then
          st = i
          break
        end
      end

      for i = -1, -#base_line, -1 do
        if base_line:sub(i, i) ~= line:sub(i, i) then
          en = i
          break
        end
      end

      assert(st)
      assert(en)
      return st, en
    end

    for i = 1, math.max(#base, #ours, #theirs) do
      local b, o, t = base[i], ours[i], theirs[i]

      if b == nil then -- base is finished, rest of lines are added lines
        local ln = o or t
        if ln == nil then break end
        table.insert(res, ln)
      elseif b == o then -- handle only theirs changed
        table.insert(res, t)
      elseif b == t then -- handle only ours changed
        table.insert(res, o)
      elseif o == t then -- both changed equivalently
        table.insert(res, o)
      elseif (o and t) == nil then -- handle theirs or ours is finished
        table.insert(res, o or t or b)
      else
        -- Merge 2 lines using some kind of intraline (or word) diff algorithm.
        -- We'll try neovim's method since it seems to be more
        -- cautious/conservative.

        -- NOTE: This block is the hard part and is where most bugs will likely
        --       occur.

        local st1, en1 = getpos(b, o)
        local st2, en2 = getpos(b, t)
        local en1_abs = #o + en1 + 1
        local en2_abs = #o + en2 + 1

        if
          (st1 >= st2 and st1 <= en2_abs)
          or (en1_abs >= st2 and en1_abs <= en2_abs)
          or (st2 >= st1 and st2 <= en1_abs)
          or (en2_abs >= st1 and en2_abs <= en1_abs)
        then
          -- Merging line failed, so we'll just insert both with conflict markers
          table.insert(res, 'OURS <<<<< ' .. o)
          table.insert(res, 'THEIRS >>> ' .. t)
        else
          table.insert(
            res,
            st1 < st2
                and (o:sub(1, en1) .. b:sub(en1 + 1, st2 - 1) .. t:sub(st2))
              or (t:sub(1, en2) .. b:sub(en2 + 1, st1 - 1) .. o:sub(st1))
          )
        end
      end
    end

    return res
  end

  local start, match = findln(
    0,
    [=[\m^\%(<\{7}\|>\{7}\)]=],
    api.nvim_win_get_cursor(0)[1] - 1,
    true
  )

  assert(match == '<<<<<<<', 'no conflict at cursor position')

  local base = findln(0, [=[\m^|\{7}]=], start + 1)
  assert(base, 'no base found')

  local base_end = findln(0, [=[\m^=\{7}]=], base + 1)
  assert(base, 'no base found')

  local end_ = findln(0, [=[\m^>\{7}]=], base_end + 1)
  assert(end_, 'conflict end not found')

  api.nvim_buf_set_lines(
    buf,
    start,
    end_ + 1,
    true,
    resolve(
      api.nvim_buf_get_lines(buf, base + 1, base_end, true),
      api.nvim_buf_get_lines(buf, start + 1, base, true),
      api.nvim_buf_get_lines(buf, base_end + 1, end_, true)
    )
  )
end