feat: apply changes as text edits using LSP utils (#18)

* feat: apply changes as text edits using LSP utils

This means we can leverage all of the work that was done in the LSP
client to preserve marks, cursor position, etc

* log: add trace logging to debug performance

* feat: use the same diff -> TextEdit technique for bad LSP servers

Some LSP servers simply return a single TextEdit that replaces the whole
buffer. This is bad for extmarks, cursor, and if the buffer is open in
multiple windows the non-active window will jump to the top. We can
detect that situation and apply the same vim.diff logic to convert it
into more granular TextEdits.

7 files changed, 350 insertions, 91 deletions

diff --git a/lua/conform/health.lua b/lua/conform/health.lua
index 195a331..d36ef03 100644
--- a/lua/conform/health.lua
+++ b/lua/conform/health.lua
@@ -90,6 +90,9 @@ M.show_window = function()
     seen[formatter.name] = true
   end
   append_formatters(buf_formatters)
+  if vim.tbl_isempty(buf_formatters) then
+    table.insert(lines, "<none>")
+  end
 
   table.insert(lines, "")
   table.insert(lines, "Other formatters:")
diff --git a/lua/conform/init.lua b/lua/conform/init.lua
index b47d43e..4a6b226 100644
--- a/lua/conform/init.lua
+++ b/lua/conform/init.lua
@@ -52,6 +52,25 @@ M.formatters = {}
 
 M.notify_on_error = true
 
+---@private
+M.original_apply_text_edits = vim.lsp.util.apply_text_edits
+
+local function apply_text_edits(text_edits, bufnr, offset_encoding)
+  if
+    #text_edits == 1
+    and text_edits[1].range.start.line == 0
+    and text_edits[1].range.start.character == 0
+    and text_edits[1].range["end"].line == vim.api.nvim_buf_line_count(bufnr) + 1
+    and text_edits[1].range["end"].character == 0
+  then
+    local original_lines = vim.api.nvim_buf_get_lines(bufnr, 0, -1, true)
+    local new_lines = vim.split(text_edits[1].newText, "\n", { plain = true })
+    require("conform.runner").apply_format(bufnr, original_lines, new_lines, nil, false)
+  else
+    M.original_apply_text_edits(text_edits, bufnr, offset_encoding)
+  end
+end
+
 M.setup = function(opts)
   opts = opts or {}
 
@@ -100,17 +119,9 @@ M.setup = function(opts)
     require("conform.health").show_window()
   end, { desc = "Show information about Conform formatters" })
 
-  ---@diagnostic disable-next-line: duplicate-set-field
-  vim.lsp.handlers["textDocument/formatting"] = function(_, result, ctx, _)
-    if not result then
-      return
-    end
-    local client = vim.lsp.get_client_by_id(ctx.client_id)
-    assert(client)
-    local restore = require("conform.util").save_win_positions(ctx.bufnr)
-    vim.lsp.util.apply_text_edits(result, ctx.bufnr, client.offset_encoding)
-    restore()
-  end
+  -- Monkey patch lsp.util.apply_text_edits to handle LSP clients that replace the entire buffer
+  -- during formatting. This is unfortunately the best place to shim that logic in.
+  vim.lsp.util.apply_text_edits = apply_text_edits
 end
 
 ---@param bufnr integer
@@ -289,11 +300,7 @@ M.format = function(opts)
     end
   elseif opts.lsp_fallback and supports_lsp_format(opts.bufnr) then
     log.debug("Running LSP formatter on %s", vim.api.nvim_buf_get_name(opts.bufnr))
-    local restore = require("conform.util").save_win_positions(opts.bufnr)
     vim.lsp.buf.format(opts)
-    if not opts.async then
-      restore()
-    end
   elseif any_formatters_configured and not opts.quiet then
     vim.notify("No formatters found for buffer. See :ConformInfo", vim.log.levels.WARN)
   else
diff --git a/lua/conform/log.lua b/lua/conform/log.lua
index b42d1f8..753a3c6 100644
--- a/lua/conform/log.lua
+++ b/lua/conform/log.lua
@@ -35,7 +35,7 @@ local function format(level, msg, ...)
   local ok, text = pcall(string.format, msg, vim.F.unpack_len(args))
   if ok then
     local str_level = levels[level]
-    return string.format("[%s] %s", str_level, text)
+    return string.format("%s[%s] %s", vim.fn.strftime("%H:%M:%S"), str_level, text)
   else
     return string.format("[ERROR] error formatting log line: '%s' args %s", msg, vim.inspect(args))
   end
diff --git a/lua/conform/runner.lua b/lua/conform/runner.lua
index 16790ab..1020a8a 100644
--- a/lua/conform/runner.lua
+++ b/lua/conform/runner.lua
@@ -44,51 +44,152 @@ local function indices_in_range(range, start_a, end_a)
   return not range or (start_a <= range["end"][1] and range["start"][1] <= end_a)
 end
 
+---@param a? string
+---@param b? string
+---@return integer
+local function common_prefix_len(a, b)
+  if not a or not b then
+    return 0
+  end
+  local min_len = math.min(#a, #b)
+  for i = 1, min_len do
+    if string.byte(a, i) ~= string.byte(b, i) then
+      return i - 1
+    end
+  end
+  return min_len
+end
+
+---@param a string
+---@param b string
+---@return integer
+local function common_suffix_len(a, b)
+  local a_len = #a
+  local b_len = #b
+  local min_len = math.min(a_len, b_len)
+  for i = 0, min_len - 1 do
+    if string.byte(a, a_len - i) ~= string.byte(b, b_len - i) then
+      return i
+    end
+  end
+  return min_len
+end
+
+local function create_text_edit(
+  original_lines,
+  replacement,
+  is_insert,
+  is_replace,
+  orig_line_start,
+  orig_line_end
+)
+  local start_line, end_line = orig_line_start - 1, orig_line_end - 1
+  local start_char, end_char = 0, 0
+  if is_replace then
+    -- If we're replacing text, see if we can avoid replacing the entire line
+    start_char = common_prefix_len(original_lines[orig_line_start], replacement[1])
+    if start_char > 0 then
+      replacement[1] = replacement[1]:sub(start_char + 1)
+    end
+
+    if original_lines[orig_line_end] then
+      local last_line = replacement[#replacement]
+      local suffix = common_suffix_len(original_lines[orig_line_end], last_line)
+      -- If we're only replacing one line, make sure the prefix/suffix calculations don't overlap
+      if orig_line_end == orig_line_start then
+        suffix = math.min(suffix, original_lines[orig_line_end]:len() - start_char)
+      end
+      end_char = original_lines[orig_line_end]:len() - suffix
+      if suffix > 0 then
+        replacement[#replacement] = last_line:sub(1, last_line:len() - suffix)
+      end
+    end
+  end
+  -- If we're inserting text, make sure the text includes a newline at the end.
+  -- The one exception is if we're inserting at the end of the file, in which case the newline is
+  -- implicit
+  if is_insert and start_line < #original_lines - 1 then
+    table.insert(replacement, "")
+  end
+  local new_text = table.concat(replacement, "\n")
+
+  return {
+    newText = new_text,
+    range = {
+      start = {
+        line = start_line,
+        character = start_char,
+      },
+      ["end"] = {
+        line = end_line,
+        character = end_char,
+      },
+    },
+  }
+end
+
 ---@param bufnr integer
 ---@param original_lines string[]
 ---@param new_lines string[]
 ---@param range? conform.Range
 ---@param only_apply_range boolean
-local function apply_format(bufnr, original_lines, new_lines, range, only_apply_range)
-  local original_text = table.concat(original_lines, "\n")
-  -- Trim off the final newline from the formatted text because that is baked in to
-  -- the vim lines representation
-  if new_lines[#new_lines] == "" then
-    new_lines[#new_lines] = nil
+M.apply_format = function(bufnr, original_lines, new_lines, range, only_apply_range)
+  local bufname = vim.api.nvim_buf_get_name(bufnr)
+  -- If the formatter output didn't have a trailing newline, add one
+  if new_lines[#new_lines] ~= "" then
+    table.insert(new_lines, "")
   end
+
+  -- Vim buffers end with an implicit newline, so append an empty line to stand in for that
+  if vim.bo[bufnr].eol then
+    table.insert(original_lines, "")
+  end
+  local original_text = table.concat(original_lines, "\n")
   local new_text = table.concat(new_lines, "\n")
+  log.trace("Creating diff for %s", bufname)
   local indices = vim.diff(original_text, new_text, {
     result_type = "indices",
     algorithm = "histogram",
   })
   assert(indices)
-  for i = #indices, 1, -1 do
-    local start_a, count_a, start_b, count_b = unpack(indices[i])
-    -- When count_a is 0, the diff is an insert after the line
-    if count_a == 0 then
-      -- This happens when the first line is blank and we're inserting text after it
-      if start_a == 0 then
-        count_a = 1
-      end
-      start_a = start_a + 1
-    end
+  local text_edits = {}
+  log.trace("Creating TextEdits for %s", bufname)
+  for _, idx in ipairs(indices) do
+    local orig_line_start, orig_line_count, new_line_start, new_line_count = unpack(idx)
+    local is_insert = orig_line_count == 0
+    local is_delete = new_line_count == 0
+    local is_replace = not is_insert and not is_delete
+    local orig_line_end = orig_line_start + orig_line_count
+    local new_line_end = new_line_start + new_line_count
 
-    -- If this diff range goes *up to* the last line in the original file, *and* the last line
-    -- after that is just an empty space, then the diff range here was calculated to include that
-    -- final newline, so we should bump up the count_a to include it
-    if (start_a + count_a) == #original_lines and original_lines[#original_lines] == "" then
-      count_a = count_a + 1
+    if is_insert then
+      -- When the diff is an insert, it actually means to insert after the mentioned line
+      orig_line_start = orig_line_start + 1
+      orig_line_end = orig_line_end + 1
     end
-    -- Same logic for the new lines
-    if (start_b + count_b) == #new_lines and new_lines[#new_lines] == "" then
-      count_b = count_b + 1
+
+    local replacement = util.tbl_slice(new_lines, new_line_start, new_line_end - 1)
+
+    -- For replacement edits, convert the end line to be inclusive
+    if is_replace then
+      orig_line_end = orig_line_end - 1
     end
-    local replacement = util.tbl_slice(new_lines, start_b, start_b + count_b - 1)
-    local end_a = start_a + count_a
-    if not only_apply_range or indices_in_range(range, start_a, end_a) then
-      vim.api.nvim_buf_set_lines(bufnr, start_a - 1, end_a - 1, true, replacement)
+    if not only_apply_range or indices_in_range(range, orig_line_start, orig_line_end) then
+      local text_edit = create_text_edit(
+        original_lines,
+        replacement,
+        is_insert,
+        is_replace,
+        orig_line_start,
+        orig_line_end
+      )
+      table.insert(text_edits, text_edit)
     end
   end
+
+  log.trace("Applying text edits for %s", bufname)
+  require("conform").original_apply_text_edits(text_edits, bufnr, "utf-8")
+  log.trace("Done formatting %s", bufname)
 end
 
 local last_run_errored = {}
@@ -130,16 +231,27 @@ local function run_formatter(bufnr, formatter, config, ctx, quiet, input_lines,
   end)
 
   log.info("Run %s on %s", formatter.name, vim.api.nvim_buf_get_name(bufnr))
+  local buffer_text
+  -- If the buffer has a newline at the end, make sure we include that in the input to the formatter
+  if vim.bo[bufnr].eol then
+    table.insert(input_lines, "")
+    buffer_text = table.concat(input_lines, "\n")
+    table.remove(input_lines)
+  else
+    buffer_text = table.concat(input_lines, "\n")
+  end
+
   if not config.stdin then
     log.debug("Creating temp file %s", ctx.filename)
     local fd = assert(uv.fs_open(ctx.filename, "w", 448)) -- 0700
-    uv.fs_write(fd, table.concat(input_lines, "\n"))
+    uv.fs_write(fd, buffer_text)
     uv.fs_close(fd)
     callback = util.wrap_callback(callback, function()
       log.debug("Cleaning up temp file %s", ctx.filename)
       uv.fs_unlink(ctx.filename)
     end)
   end
+
   log.debug("Run command: %s", cmd)
   if cwd then
     log.debug("Run CWD: %s", cwd)
@@ -197,8 +309,7 @@ local function run_formatter(bufnr, formatter, config, ctx, quiet, input_lines,
   elseif jid == -1 then
     callback(string.format("Formatter '%s' command is not executable", formatter.name))
   elseif config.stdin then
-    local text = table.concat(input_lines, "\n")
-    vim.api.nvim_chan_send(jid, text)
+    vim.api.nvim_chan_send(jid, buffer_text)
     vim.fn.chanclose(jid, "stdin")
   end
   vim.b[bufnr].conform_jid = jid
@@ -274,7 +385,7 @@ M.format_async = function(bufnr, formatters, quiet, range, callback)
     if not formatter then
       -- discard formatting if buffer has changed
       if vim.b[bufnr].changedtick == changedtick then
-        apply_format(bufnr, original_lines, input_lines, range, not all_support_range_formatting)
+        M.apply_format(bufnr, original_lines, input_lines, range, not all_support_range_formatting)
       else
         log.info(
           "Async formatter discarding changes for %s: concurrent modification",
@@ -387,7 +498,7 @@ M.format_sync = function(bufnr, formatters, timeout_ms, quiet, range)
   end
 
   local final_result = input_lines
-  apply_format(bufnr, original_lines, final_result, range, not all_support_range_formatting)
+  M.apply_format(bufnr, original_lines, final_result, range, not all_support_range_formatting)
 end
 
 return M
diff --git a/lua/conform/util.lua b/lua/conform/util.lua
index d0856ab..a408675 100644
--- a/lua/conform/util.lua
+++ b/lua/conform/util.lua
@@ -28,36 +28,6 @@ M.root_file = function(files)
   end
 end
 
----@param bufnr? integer
----@return fun() Function that restores the window positions
-M.save_win_positions = function(bufnr)
-  if bufnr == nil or bufnr == 0 then
-    bufnr = vim.api.nvim_get_current_buf()
-  end
-  local win_positions = {}
-  for _, winid in ipairs(vim.api.nvim_list_wins()) do
-    if vim.api.nvim_win_get_buf(winid) == bufnr then
-      vim.api.nvim_win_call(winid, function()
-        local view = vim.fn.winsaveview()
-        win_positions[winid] = view
-      end)
-    end
-  end
-
-  return function()
-    for winid, view in pairs(win_positions) do
-      if
-        vim.api.nvim_win_is_valid(winid)
-        and vim.deep_equal(vim.api.nvim_win_get_cursor(winid), { 1, 0 })
-      then
-        vim.api.nvim_win_call(winid, function()
-          pcall(vim.fn.winrestview, view)
-        end)
-      end
-    end
-  end
-end
-
 ---@param bufnr integer
 ---@param range conform.Range
 ---@return integer start_offset
diff --git a/tests/fuzzer_spec.lua b/tests/fuzzer_spec.lua
new file mode 100644
index 0000000..81c032f
--- /dev/null
+++ b/tests/fuzzer_spec.lua
@@ -0,0 +1,122 @@
+require("plenary.async").tests.add_to_env()
+local test_util = require("tests.test_util")
+local conform = require("conform")
+local runner = require("conform.runner")
+
+describe("fuzzer", function()
+  before_each(function()
+    conform.formatters.test = {
+      meta = { url = "", description = "" },
+      command = "tests/fake_formatter.sh",
+    }
+  end)
+
+  after_each(function()
+    test_util.reset_editor()
+  end)
+
+  ---@param buf_content string[]
+  ---@param expected string[]
+  ---@param opts? table
+  local function run_formatter(buf_content, expected, opts)
+    local bufnr = vim.fn.bufadd("testfile")
+    vim.fn.bufload(bufnr)
+    vim.api.nvim_set_current_buf(bufnr)
+    vim.api.nvim_buf_set_lines(bufnr, 0, -1, true, buf_content)
+    vim.bo[bufnr].modified = false
+    runner.apply_format(0, buf_content, expected, nil, false)
+    -- We expect the last newline to be effectively "swallowed" by the formatter
+    -- because vim will use that as the EOL at the end of the file. The exception is that we always
+    -- expect at least one line in the output
+    if #expected > 1 and expected[#expected] == "" then
+      table.remove(expected)
+    end
+    assert.are.same(expected, vim.api.nvim_buf_get_lines(0, 0, -1, false))
+  end
+
+  local function make_word()
+    local chars = {}
+    for _ = 1, math.random(1, 10) do
+      table.insert(chars, string.char(math.random(97, 122)))
+    end
+    return table.concat(chars, "")
+  end
+
+  local function make_line()
+    local words = {}
+    for _ = 1, math.random(0, 6) do
+      table.insert(words, make_word())
+    end
+    return table.concat(words, " ")
+  end
+
+  local function make_file(num_lines)
+    local lines = {}
+    for _ = 1, math.random(1, num_lines) do
+      table.insert(lines, make_line())
+    end
+    return lines
+  end
+
+  local function do_insert(lines)
+    local idx = math.random(1, #lines + 1)
+    for _ = 1, math.random(1, 3) do
+      table.insert(lines, idx, make_line())
+    end
+  end
+
+  local function do_replace(lines)
+    local num_lines = math.random(1, math.min(3, #lines))
+    local idx = math.random(1, #lines - num_lines + 1)
+    local replacement = {}
+    local num_replace = math.random(1, 5)
+    for _ = 1, num_replace do
+      table.insert(replacement, make_line())
+    end
+    local col = math.random(1, lines[idx]:len())
+    replacement[1] = lines[idx]:sub(1, col) .. replacement[1]
+    col = math.random(1, lines[idx + num_lines - 1]:len())
+    replacement[#replacement] = replacement[#replacement] .. lines[idx + num_lines - 1]:sub(col)
+
+    for _ = 1, num_lines - num_replace do
+      table.remove(lines, idx)
+    end
+    for _ = 1, num_replace - num_lines do
+      table.insert(lines, idx, "")
+    end
+    for i = 1, num_replace do
+      lines[idx + i - 1] = replacement[i]
+    end
+  end
+
+  local function do_delete(lines)
+    local num_lines = math.random(1, 3)
+    local idx = math.random(1, #lines - num_lines)
+    for _ = 1, num_lines do
+      table.remove(lines, idx)
+    end
+  end
+
+  local function make_edits(lines)
+    lines = vim.deepcopy(lines)
+    for _ = 1, math.random(0, 3) do
+      do_insert(lines)
+    end
+    for _ = 1, math.random(0, 3) do
+      do_replace(lines)
+    end
+    for _ = 1, math.random(0, 3) do
+      do_delete(lines)
+    end
+    return lines
+  end
+
+  it("formats correctly", function()
+    for i = 1, 50000 do
+      math.randomseed(i)
+      local content = make_file(20)
+      local formatted = make_edits(content)
+      run_formatter(content, formatted)
+    end
+  end)
+end)
diff --git a/tests/runner_spec.lua b/tests/runner_spec.lua
index f054d9e..8807d2d 100644
--- a/tests/runner_spec.lua
+++ b/tests/runner_spec.lua
@@ -124,16 +124,21 @@ describe("runner", function()
       vim.bo[bufnr].modified = false
       local expected_lines = vim.split(expected, "\n", { plain = true })
       test_util.set_formatter_output(expected_lines)
-      conform.format(vim.tbl_extend("force", opts or {}, { formatters = { "test" } }))
+      conform.format(vim.tbl_extend("force", opts or {}, { formatters = { "test" }, quiet = true }))
+      -- We expect the last newline to be effectively "swallowed" by the formatter
+      -- because vim will use that as the EOL at the end of the file. The exception is that we always
+      -- expect at least one line in the output
+      if #expected_lines > 1 and expected_lines[#expected_lines] == "" then
+        table.remove(expected_lines)
+      end
       return expected_lines
     end
 
     ---@param buf_content string
     ---@param new_content string
-    ---@param expected? string[]
-    local function run_formatter_test(buf_content, new_content, expected)
+    local function run_formatter_test(buf_content, new_content)
       local lines = run_formatter(buf_content, new_content)
-      assert.are.same(expected or lines, vim.api.nvim_buf_get_lines(0, 0, -1, false))
+      assert.are.same(lines, vim.api.nvim_buf_get_lines(0, 0, -1, false))
     end
 
     it("sets the correct output", function()
@@ -181,15 +186,18 @@ print("b")
 print("a")
       ]]
       )
-      run_formatter_test("hello\ngoodbye", "hello\n\n\ngoodbye", { "hello", "", "", "goodbye" })
-      run_formatter_test("hello", "hello\ngoodbye", { "hello", "goodbye" })
-      run_formatter_test("", "hello", { "hello" })
-      run_formatter_test("\nfoo", "\nhello\nfoo", { "", "hello", "foo" })
-      run_formatter_test("hello", "hello\n\n", { "hello", "" })
-      run_formatter_test("hello", "hello\n", { "hello" })
+      run_formatter_test("hello\ngoodbye", "hello\n\n\ngoodbye")
+      run_formatter_test("hello", "hello\ngoodbye")
+      run_formatter_test("hello\ngoodbye", "hello")
+      run_formatter_test("", "hello")
+      run_formatter_test("\nfoo", "\nhello\nfoo")
+      run_formatter_test("hello", "hello\n")
+      run_formatter_test("hello", "hello\n\n")
+      run_formatter_test("hello", "hello\n")
+      -- This should generate no changes to the buffer
       assert.falsy(vim.bo.modified)
-      run_formatter_test("hello\n", "hello", { "hello" })
-      run_formatter_test("hello\n ", "hello", { "hello" })
+      run_formatter_test("hello\n", "hello")
+      run_formatter_test("hello\n ", "hello")
     end)
 
     it("does not change output if formatter fails", function()
@@ -238,5 +246,43 @@ print("a")
       vim.fn.delete("tests/testfile.txt")
       assert.are.same({ "goodbye" }, lines)
     end)
+
+    describe("range formatting", function()
+      it("applies edits that overlap the range start", function()
+        run_formatter(
+          "a\nb\nc",
+          "d\nb\nd",
+          { range = {
+            start = { 1, 0 },
+            ["end"] = { 2, 0 },
+          } }
+        )
+        assert.are.same({ "d", "b", "c" }, vim.api.nvim_buf_get_lines(0, 0, -1, false))
+      end)
+
+      it("applies edits that overlap the range end", function()
+        run_formatter(
+          "a\nb\nc",
+          "d\nb\nd",
+          { range = {
+            start = { 3, 0 },
+            ["end"] = { 3, 1 },
+          } }
+        )
+        assert.are.same({ "a", "b", "d" }, vim.api.nvim_buf_get_lines(0, 0, -1, false))
+      end)
+
+      it("applies edits that are completely contained by the range", function()
+        run_formatter(
+          "a\nb\nc",
+          "a\nd\nc",
+          { range = {
+            start = { 1, 0 },
+            ["end"] = { 3, 0 },
+          } }
+        )
+        assert.are.same({ "a", "d", "c" }, vim.api.nvim_buf_get_lines(0, 0, -1, false))
+      end)
+    end)
   end)
 end)