extmarks/bufhl: reimplement using new marktree data structure

Add new "splice" interface for tracking buffer changes at the byte
level. This will later be reused for byte-resolution buffer updates.
(Implementation has been started, but using undocumented "_on_bytes"
option now as interface hasn't been finalized).

Use this interface to improve many edge cases of extmark adjustment.
Changed tests indicate previously incorrect behavior. Adding tests for
more edge cases will be follow-up work (overlaps on_bytes tests)

Don't consider creation/deletion of marks an undoable event by itself.
This behavior was never documented, and imposes  complexity for little gain.

Add nvim__buf_add_decoration temporary API for direct access to the new
implementation. This should be refactored into a proper API for
decorations, probably involving a huge dict.

fixes #11598

1 files changed, 682 insertions, 911 deletions

diff --git a/src/nvim/mark_extended.c b/src/nvim/mark_extended.c
index 17776d438a..b60d847676 100644
--- a/src/nvim/mark_extended.c
+++ b/src/nvim/mark_extended.c
@@ -7,14 +7,13 @@
 // The btree provides efficient range lookups.
 // A map of pointers to the marks is used for fast lookup by mark id.
 //
-// Marks are moved by calls to: extmark_col_adjust, extmark_adjust, or
-// extmark_col_adjust_delete which are based on col_adjust and mark_adjust from
-// mark.c
+// Marks are moved by calls to extmark_splice. Additionally mark_adjust
+// might adjust extmarks to line inserts/deletes.
 //
 // Undo/Redo of marks is implemented by storing the call arguments to
-// extmark_col_adjust or extmark_adjust. The list of arguments
-// is applied in extmark_apply_undo. The only case where we have to
-// copy extmarks is for the area being effected by a delete.
+// extmark_splice. The list of arguments is applied in extmark_apply_undo.
+// The only case where we have to copy extmarks is for the area being effected
+// by a delete.
 //
 // Marks live in namespaces that allow plugins/users to segregate marks
 // from other users.
@@ -30,9 +29,11 @@
 // leave it in same position unless it is on the EOL of a line.
 
 #include <assert.h>
+#include "nvim/api/vim.h"
 #include "nvim/vim.h"
-#include "charset.h"
+#include "nvim/charset.h"
 #include "nvim/mark_extended.h"
+#include "nvim/buffer_updates.h"
 #include "nvim/memline.h"
 #include "nvim/pos.h"
 #include "nvim/globals.h"
@@ -40,93 +41,227 @@
 #include "nvim/lib/kbtree.h"
 #include "nvim/undo.h"
 #include "nvim/buffer.h"
+#include "nvim/syntax.h"
+#include "nvim/highlight.h"
 
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "mark_extended.c.generated.h"
 #endif
 
+static ExtmarkNs *buf_ns_ref(buf_T *buf, uint64_t ns_id, bool put) {
+  if (!buf->b_extmark_ns) {
+    if (!put) {
+      return NULL;
+    }
+    buf->b_extmark_ns = map_new(uint64_t, ExtmarkNs)();
+    buf->b_extmark_index = map_new(uint64_t, ExtmarkItem)();
+  }
+
+  ExtmarkNs *ns = map_ref(uint64_t, ExtmarkNs)(buf->b_extmark_ns, ns_id, put);
+  if (put && ns->map == NULL) {
+    ns->map = map_new(uint64_t, uint64_t)();
+    ns->free_id = 1;
+  }
+  return ns;
+}
+
 
 /// Create or update an extmark
 ///
 /// must not be used during iteration!
-/// @returns whether a new mark was created
-int extmark_set(buf_T *buf, uint64_t ns, uint64_t id,
-                linenr_T lnum, colnr_T col, ExtmarkOp op)
+/// @returns the mark id
+uint64_t extmark_set(buf_T *buf, uint64_t ns_id, uint64_t id,
+                     int row, colnr_T col, ExtmarkOp op)
 {
-  Extmark *extmark = extmark_from_id(buf, ns, id);
-  if (!extmark) {
-    extmark_create(buf, ns, id, lnum, col, op);
-    return true;
+  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, true);
+  mtpos_t old_pos;
+  uint64_t mark = 0;
+
+  if (id == 0) {
+    id = ns->free_id++;
   } else {
-    ExtmarkLine *extmarkline = extmark->line;
-    extmark_update(extmark, buf, ns, id, lnum,  col, op, NULL);
-    if (kb_size(&extmarkline->items) == 0) {
-      kb_del(extmarklines, &buf->b_extlines, extmarkline);
-      extmarkline_free(extmarkline);
+    uint64_t old_mark = map_get(uint64_t, uint64_t)(ns->map, id);
+    if (old_mark) {
+      if (old_mark & MARKTREE_PAIRED_FLAG) {
+        extmark_del(buf, ns_id, id);
+      } else {
+        // TODO(bfredl): we need to do more if "revising" a decoration mark.
+        MarkTreeIter itr[1];
+        old_pos = marktree_lookup(buf->b_marktree, old_mark, itr);
+        assert(itr->node);
+        if (old_pos.row == row && old_pos.col == col) {
+          map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index, old_mark);
+          mark = marktree_revise(buf->b_marktree, itr);
+          goto revised;
+        }
+        marktree_del_itr(buf->b_marktree, itr, false);
+      }
+    } else {
+      ns->free_id = MAX(ns->free_id, id+1);
     }
+  }
+
+  mark = marktree_put(buf->b_marktree, row, col, true);
+revised:
+  map_put(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark,
+                                 (ExtmarkItem){ ns_id, id, 0,
+                                                KV_INITIAL_VALUE });
+  map_put(uint64_t, uint64_t)(ns->map, id, mark);
+
+  if (op != kExtmarkNoUndo) {
+    // TODO(bfredl): this doesn't cover all the cases and probably shouldn't
+    // be done "prematurely". Any movement in undo history might necessitate
+    // adding new marks to old undo headers.
+    u_extmark_set(buf, mark, row, col);
+  }
+  return id;
+}
+
+static bool extmark_setraw(buf_T *buf, uint64_t mark, int row, colnr_T col)
+{
+  MarkTreeIter itr[1];
+  mtpos_t pos = marktree_lookup(buf->b_marktree, mark, itr);
+  if (pos.row == -1) {
     return false;
   }
+
+  if (pos.row == row && pos.col == col) {
+    return true;
+  }
+
+  marktree_move(buf->b_marktree, itr, row, col);
+  return true;
 }
 
 // Remove an extmark
 // Returns 0 on missing id
-int extmark_del(buf_T *buf, uint64_t ns, uint64_t id, ExtmarkOp op)
+bool extmark_del(buf_T *buf, uint64_t ns_id, uint64_t id)
 {
-  Extmark *extmark = extmark_from_id(buf, ns, id);
-  if (!extmark) {
-    return 0;
+  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, false);
+  if (!ns) {
+    return false;
+  }
+
+  uint64_t mark = map_get(uint64_t, uint64_t)(ns->map, id);
+  if (!mark) {
+    return false;
   }
-  return extmark_delete(extmark, buf, ns, id, op);
+
+  MarkTreeIter itr[1];
+  mtpos_t pos = marktree_lookup(buf->b_marktree, mark, itr);
+  assert(pos.row >= 0);
+  marktree_del_itr(buf->b_marktree, itr, false);
+  ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark);
+
+  if (mark & MARKTREE_PAIRED_FLAG) {
+    mtpos_t pos2 = marktree_lookup(buf->b_marktree,
+                                   mark|MARKTREE_END_FLAG, itr);
+    assert(pos2.row >= 0);
+    marktree_del_itr(buf->b_marktree, itr, false);
+    if (item.hl_id && pos2.row >= pos.row) {
+      redraw_buf_range_later(buf, pos.row+1, pos2.row+1);
+    }
+  }
+
+  if (kv_size(item.virt_text)) {
+    redraw_buf_line_later(buf, pos.row+1);
+  }
+  clear_virttext(&item.virt_text);
+
+  map_del(uint64_t, uint64_t)(ns->map, id);
+  map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark);
+
+  // TODO(bfredl): delete it from current undo header, opportunistically?
+
+  return true;
 }
 
 // Free extmarks in a ns between lines
 // if ns = 0, it means clear all namespaces
-void extmark_clear(buf_T *buf, uint64_t ns,
-                   linenr_T l_lnum, linenr_T u_lnum, ExtmarkOp undo)
+bool extmark_clear(buf_T *buf, uint64_t ns_id,
+                   int l_row, colnr_T l_col,
+                   int u_row, colnr_T u_col)
 {
   if (!buf->b_extmark_ns) {
-    return;
+    return false;
   }
 
   bool marks_cleared = false;
-  if (undo == kExtmarkUndo) {
-    // Copy marks that would be effected by clear
-    u_extmark_copy(buf, ns, l_lnum, 0, u_lnum, MAXCOL);
-  }
 
-  bool all_ns = ns == 0 ? true : false;
-  ExtmarkNs *ns_obj;
+  bool all_ns = (ns_id == 0);
+  ExtmarkNs *ns = NULL;
   if (!all_ns) {
-    ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-    if (!ns_obj) {
+    ns = buf_ns_ref(buf, ns_id, false);
+    if (!ns) {
       // nothing to do
-      return;
+      return false;
     }
+
+    // TODO(bfredl): if map_size(ns->map) << buf->b_marktree.n_nodes
+    // it could be faster to iterate over the map instead
   }
 
-  FOR_ALL_EXTMARKLINES(buf, l_lnum, u_lnum, {
-    FOR_ALL_EXTMARKS_IN_LINE(extmarkline->items, 0, MAXCOL, {
-            if (extmark->ns_id == ns || all_ns) {
-              marks_cleared = true;
-              if (all_ns) {
-                ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, extmark->ns_id);
-              } else {
-                ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-              }
-              pmap_del(uint64_t)(ns_obj->map, extmark->mark_id);
-              kb_del_itr(markitems, &extmarkline->items, &mitr);
-            }
-    });
-    if (kb_size(&extmarkline->items) == 0) {
-      kb_del_itr(extmarklines, &buf->b_extlines, &itr);
-      extmarkline_free(extmarkline);
+  // the value is either zero or the lnum (row+1) if highlight was present.
+  static Map(uint64_t, uint64_t) *delete_set = NULL;
+  if (delete_set == NULL) {
+    delete_set = map_new(uint64_t, uint64_t)();
+  }
+
+  MarkTreeIter itr[1];
+  marktree_itr_get(buf->b_marktree, l_row, l_col, itr);
+  while (true) {
+    mtmark_t mark = marktree_itr_current(itr);
+    if (mark.row < 0
+        || mark.row > u_row
+        || (mark.row == u_row && mark.col > u_col)) {
+      break;
     }
-  });
+    uint64_t *del_status = map_ref(uint64_t, uint64_t)(delete_set, mark.id,
+                                                       false);
+    if (del_status) {
+      marktree_del_itr(buf->b_marktree, itr, false);
+      map_del(uint64_t, uint64_t)(delete_set, mark.id);
+      if (*del_status > 0) {
+        redraw_buf_range_later(buf, (linenr_T)(*del_status), mark.row+1);
+      }
+      continue;
+    }
+
+    uint64_t start_id = mark.id & ~MARKTREE_END_FLAG;
+    ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index,
+                                                      start_id);
 
-  // Record the undo for the actual move
-  if (marks_cleared && undo == kExtmarkUndo) {
-    u_extmark_clear(buf, ns, l_lnum, u_lnum);
+    assert(item.ns_id > 0 && item.mark_id > 0);
+    if (item.mark_id > 0 && (item.ns_id == ns_id || all_ns)) {
+      if (kv_size(item.virt_text)) {
+        redraw_buf_line_later(buf, mark.row+1);
+      }
+      clear_virttext(&item.virt_text);
+      marks_cleared = true;
+      if (mark.id & MARKTREE_PAIRED_FLAG) {
+        uint64_t other = mark.id ^ MARKTREE_END_FLAG;
+        uint64_t status = item.hl_id ? ((uint64_t)mark.row+1) : 0;
+        map_put(uint64_t, uint64_t)(delete_set, other, status);
+      }
+      ExtmarkNs *my_ns = all_ns ? buf_ns_ref(buf, item.ns_id, false) : ns;
+      map_del(uint64_t, uint64_t)(my_ns->map, item.mark_id);
+      map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark.id);
+      marktree_del_itr(buf->b_marktree, itr, false);
+    } else {
+      marktree_itr_next(buf->b_marktree, itr);
+    }
   }
+  uint64_t id, status;
+  map_foreach(delete_set, id, status, {
+    mtpos_t pos = marktree_lookup(buf->b_marktree, id, itr);
+    assert(itr->node);
+    marktree_del_itr(buf->b_marktree, itr, false);
+    if (status > 0) {
+      redraw_buf_range_later(buf, (linenr_T)status, pos.row+1);
+    }
+  });
+  map_clear(uint64_t, uint64_t)(delete_set);
+  return marks_cleared;
 }
 
 // Returns the position of marks between a range,
@@ -135,190 +270,65 @@ void extmark_clear(buf_T *buf, uint64_t ns,
 // will be searched to the start, or end
 // dir can be set to control the order of the array
 // amount = amount of marks to find or -1 for all
-ExtmarkArray extmark_get(buf_T *buf, uint64_t ns,
-                         linenr_T l_lnum, colnr_T l_col,
-                         linenr_T u_lnum, colnr_T u_col,
+ExtmarkArray extmark_get(buf_T *buf, uint64_t ns_id,
+                         int l_row, colnr_T l_col,
+                         int u_row, colnr_T u_col,
                          int64_t amount, bool reverse)
 {
   ExtmarkArray array = KV_INITIAL_VALUE;
+  MarkTreeIter itr[1];
   // Find all the marks
-  if (!reverse) {
-    FOR_ALL_EXTMARKS(buf, ns, l_lnum, l_col, u_lnum, u_col, {
-      if (extmark->ns_id == ns) {
-        kv_push(array, extmark);
-        if (kv_size(array) == (size_t)amount) {
-          return array;
-        }
-      }
-    })
-  } else {
-    FOR_ALL_EXTMARKS_PREV(buf, ns, l_lnum, l_col, u_lnum, u_col, {
-      if (extmark->ns_id == ns) {
-        kv_push(array, extmark);
-        if (kv_size(array) == (size_t)amount) {
-          return array;
-        }
-      }
-    })
-  }
-  return array;
-}
-
-static void extmark_create(buf_T *buf, uint64_t ns, uint64_t id,
-                           linenr_T lnum, colnr_T col, ExtmarkOp op)
-{
-  if (!buf->b_extmark_ns) {
-    buf->b_extmark_ns = pmap_new(uint64_t)();
-  }
-  ExtmarkNs *ns_obj = NULL;
-  ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-  // Initialize a new namespace for this buffer
-  if (!ns_obj) {
-    ns_obj = xmalloc(sizeof(ExtmarkNs));
-    ns_obj->map = pmap_new(uint64_t)();
-    pmap_put(uint64_t)(buf->b_extmark_ns, ns, ns_obj);
-  }
-
-  // Create or get a line
-  ExtmarkLine *extmarkline = extmarkline_ref(buf, lnum, true);
-  // Create and put mark on the line
-  extmark_put(col, id, extmarkline, ns);
-
-  // Marks do not have stable address so we have to look them up
-  // by using the line instead of the mark
-  pmap_put(uint64_t)(ns_obj->map, id, extmarkline);
-  if (op != kExtmarkNoUndo) {
-    u_extmark_set(buf, ns, id, lnum, col, kExtmarkSet);
-  }
-
-  // Set a free id so extmark_free_id_get works
-  extmark_free_id_set(ns_obj, id);
-}
-
-// update the position of an extmark
-// to update while iterating pass the markitems itr
-static void extmark_update(Extmark *extmark, buf_T *buf,
-                           uint64_t ns, uint64_t id,
-                           linenr_T lnum, colnr_T col,
-                           ExtmarkOp op, kbitr_t(markitems) *mitr)
-{
-  assert(op != kExtmarkNOOP);
-  if (op != kExtmarkNoUndo) {
-    u_extmark_update(buf, ns, id, extmark->line->lnum, extmark->col,
-                     lnum, col);
-  }
-  ExtmarkLine *old_line = extmark->line;
-  // Move the mark to a new line and update column
-  if (old_line->lnum != lnum) {
-    ExtmarkLine *ref_line = extmarkline_ref(buf, lnum, true);
-    extmark_put(col, id, ref_line, ns);
-    // Update the hashmap
-    ExtmarkNs *ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-    pmap_put(uint64_t)(ns_obj->map, id, ref_line);
-    // Delete old mark
-    if (mitr != NULL) {
-      kb_del_itr(markitems, &(old_line->items), mitr);
-    } else {
-      kb_del(markitems, &old_line->items, *extmark);
+  marktree_itr_get_ext(buf->b_marktree, (mtpos_t){ l_row, l_col },
+                       itr, reverse, false, NULL);
+  int order = reverse ? -1 : 1;
+  while ((int64_t)kv_size(array) < amount) {
+    mtmark_t mark = marktree_itr_current(itr);
+    if (mark.row < 0
+        || (mark.row - u_row) * order > 0
+        || (mark.row == u_row && (mark.col - u_col) * order > 0)) {
+      break;
     }
-  // Just update the column
-  } else {
-    if (mitr != NULL) {
-      // The btree stays organized during iteration with kbitr_t
-      extmark->col = col;
+    ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index,
+                                                      mark.id);
+    if (item.ns_id == ns_id) {
+      kv_push(array, ((ExtmarkInfo) { .ns_id = item.ns_id,
+                                      .mark_id = item.mark_id,
+                                      .row = mark.row, .col = mark.col }));
+    }
+    if (reverse) {
+      marktree_itr_prev(buf->b_marktree, itr);
     } else {
-      // Keep the btree in order
-      kb_del(markitems, &old_line->items, *extmark);
-      extmark_put(col, id, old_line, ns);
+      marktree_itr_next(buf->b_marktree, itr);
     }
   }
-}
-
-static int extmark_delete(Extmark *extmark,
-                          buf_T *buf,
-                          uint64_t ns,
-                          uint64_t id,
-                          ExtmarkOp op)
-{
-  if (op != kExtmarkNoUndo) {
-    u_extmark_set(buf, ns, id, extmark->line->lnum, extmark->col,
-                  kExtmarkDel);
-  }
-
-  // Remove our key from the namespace
-  ExtmarkNs *ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-  pmap_del(uint64_t)(ns_obj->map, id);
-
-  // Remove the mark mark from the line
-  ExtmarkLine *extmarkline = extmark->line;
-  kb_del(markitems, &extmarkline->items, *extmark);
-  // Remove the line if there are no more marks in the line
-  if (kb_size(&extmarkline->items) == 0) {
-    kb_del(extmarklines, &buf->b_extlines, extmarkline);
-    extmarkline_free(extmarkline);
-  }
-  return true;
+  return array;
 }
 
 // Lookup an extmark by id
-Extmark *extmark_from_id(buf_T *buf, uint64_t ns, uint64_t id)
+ExtmarkInfo extmark_from_id(buf_T *buf, uint64_t ns_id, uint64_t id)
 {
-  if (!buf->b_extmark_ns) {
-    return NULL;
-  }
-  ExtmarkNs *ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-  if (!ns_obj || !kh_size(ns_obj->map->table)) {
-    return NULL;
+  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, false);
+  ExtmarkInfo ret = { 0, 0, -1, -1 };
+  if (!ns) {
+    return ret;
   }
-  ExtmarkLine *extmarkline = pmap_get(uint64_t)(ns_obj->map, id);
-  if (!extmarkline) {
-    return NULL;
+
+  uint64_t mark = map_get(uint64_t, uint64_t)(ns->map, id);
+  if (!mark) {
+    return ret;
   }
 
-  FOR_ALL_EXTMARKS_IN_LINE(extmarkline->items, 0, MAXCOL, {
-    if (extmark->ns_id == ns
-        && extmark->mark_id == id) {
-      return extmark;
-    }
-  })
-  return NULL;
-}
+  mtpos_t pos = marktree_lookup(buf->b_marktree, mark, NULL);
+  assert(pos.row >= 0);
 
-// Lookup an extmark by position
-Extmark *extmark_from_pos(buf_T *buf, uint64_t ns, linenr_T lnum, colnr_T col)
-{
-  if (!buf->b_extmark_ns) {
-    return NULL;
-  }
-  FOR_ALL_EXTMARKS(buf, ns, lnum, col, lnum, col, {
-    if (extmark->ns_id == ns) {
-      if (extmark->col == col) {
-        return extmark;
-      }
-    }
-  })
-  return NULL;
-}
+  ret.ns_id = ns_id;
+  ret.mark_id = id;
+  ret.row = pos.row;
+  ret.col = pos.col;
 
-// Returns an available id in a namespace
-uint64_t extmark_free_id_get(buf_T *buf, uint64_t ns)
-{
-  if (!buf->b_extmark_ns) {
-    return 1;
-  }
-  ExtmarkNs *ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns, ns);
-  if (!ns_obj) {
-    return 1;
-  }
-  return ns_obj->free_id;
+  return ret;
 }
 
-// Set the next free id in a namesapce
-static void extmark_free_id_set(ExtmarkNs *ns_obj, uint64_t id)
-{
-  // Simply Heurstic, the largest id + 1
-  ns_obj->free_id = id + 1;
-}
 
 // free extmarks from the buffer
 void extmark_free_all(buf_T *buf)
@@ -327,813 +337,574 @@ void extmark_free_all(buf_T *buf)
     return;
   }
 
-  uint64_t ns;
-  ExtmarkNs *ns_obj;
+  uint64_t id;
+  ExtmarkNs ns;
+  ExtmarkItem item;
 
-  FOR_ALL_EXTMARKLINES(buf, 1, MAXLNUM, {
-    kb_del_itr(extmarklines, &buf->b_extlines, &itr);
-    extmarkline_free(extmarkline);
-  })
+  marktree_clear(buf->b_marktree);
 
-  map_foreach(buf->b_extmark_ns, ns, ns_obj, {
-    (void)ns;
-    pmap_free(uint64_t)(ns_obj->map);
-    xfree(ns_obj);
+  map_foreach(buf->b_extmark_ns, id, ns, {
+    (void)id;
+    map_free(uint64_t, uint64_t)(ns.map);
   });
-
-  pmap_free(uint64_t)(buf->b_extmark_ns);
+  map_free(uint64_t, ExtmarkNs)(buf->b_extmark_ns);
   buf->b_extmark_ns = NULL;
 
-  // k?_init called to set pointers to NULL
-  kb_destroy(extmarklines, (&buf->b_extlines));
-  kb_init(&buf->b_extlines);
-
-  kv_destroy(buf->b_extmark_move_space);
-  kv_init(buf->b_extmark_move_space);
+  map_foreach(buf->b_extmark_index, id, item, {
+    (void)id;
+    clear_virttext(&item.virt_text);
+  });
+  map_free(uint64_t, ExtmarkItem)(buf->b_extmark_index);
+  buf->b_extmark_index = NULL;
 }
 
 
 // Save info for undo/redo of set marks
-static void u_extmark_set(buf_T *buf, uint64_t ns, uint64_t id,
-                          linenr_T lnum, colnr_T col, UndoObjectType undo_type)
+static void u_extmark_set(buf_T *buf, uint64_t mark,
+                          int row, colnr_T col)
 {
   u_header_T  *uhp = u_force_get_undo_header(buf);
   if (!uhp) {
     return;
   }
 
-  ExtmarkSet set;
-  set.ns_id = ns;
-  set.mark_id = id;
-  set.lnum = lnum;
-  set.col = col;
+  ExtmarkSavePos pos;
+  pos.mark = mark;
+  pos.old_row = -1;
+  pos.old_col = -1;
+  pos.row = row;
+  pos.col = col;
 
-  ExtmarkUndoObject undo = { .type = undo_type,
-                             .data.set = set };
+  ExtmarkUndoObject undo = { .type = kExtmarkSavePos,
+                             .data.savepos = pos };
 
   kv_push(uhp->uh_extmark, undo);
 }
 
-// Save info for undo/redo of deleted marks
-static void u_extmark_update(buf_T *buf, uint64_t ns, uint64_t id,
-                             linenr_T old_lnum, colnr_T old_col,
-                             linenr_T lnum, colnr_T col)
+/// copy extmarks data between range
+///
+/// useful when we cannot simply reverse the operation. This will do nothing on
+/// redo, enforces correct position when undo.
+void u_extmark_copy(buf_T *buf,
+                    int l_row, colnr_T l_col,
+                    int u_row, colnr_T u_col)
 {
   u_header_T  *uhp = u_force_get_undo_header(buf);
   if (!uhp) {
     return;
   }
 
-  ExtmarkUpdate update;
-  update.ns_id = ns;
-  update.mark_id = id;
-  update.old_lnum = old_lnum;
-  update.old_col = old_col;
-  update.lnum = lnum;
-  update.col = col;
+  ExtmarkUndoObject undo;
 
-  ExtmarkUndoObject undo = { .type = kExtmarkUpdate,
-                             .data.update = update };
-  kv_push(uhp->uh_extmark, undo);
-}
+  MarkTreeIter itr[1];
+  marktree_itr_get(buf->b_marktree, l_row, l_col, itr);
+  while (true) {
+    mtmark_t mark = marktree_itr_current(itr);
+    if (mark.row < 0
+        || mark.row > u_row
+        || (mark.row == u_row && mark.col > u_col)) {
+      break;
+    }
+    ExtmarkSavePos pos;
+    pos.mark = mark.id;
+    pos.old_row = mark.row;
+    pos.old_col = mark.col;
+    pos.row = -1;
+    pos.col = -1;
+
+    undo.data.savepos = pos;
+    undo.type = kExtmarkSavePos;
+    kv_push(uhp->uh_extmark, undo);
 
-// Hueristic works only for when the user is typing in insert mode
-// - Instead of 1 undo object for each char inserted,
-//   we create 1 undo objet for all text inserted before the user hits esc
-// Return True if we compacted else False
-static bool u_compact_col_adjust(buf_T *buf, linenr_T lnum, colnr_T mincol,
-                                 long lnum_amount, long col_amount)
-{
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return false;
+    marktree_itr_next(buf->b_marktree, itr);
   }
+}
 
-  if (kv_size(uhp->uh_extmark) < 1) {
-    return false;
-  }
-  // Check the last action
-  ExtmarkUndoObject object = kv_last(uhp->uh_extmark);
+/// undo or redo an extmark operation
+void extmark_apply_undo(ExtmarkUndoObject undo_info, bool undo)
+{
+  // splice: any text operation changing position (except :move)
+  if (undo_info.type == kExtmarkSplice) {
+    // Undo
+    ExtmarkSplice splice = undo_info.data.splice;
+    if (undo) {
+      extmark_splice(curbuf,
+                     splice.start_row, splice.start_col,
+                     splice.newextent_row, splice.newextent_col,
+                     splice.oldextent_row, splice.oldextent_col,
+                     kExtmarkNoUndo);
 
-  if (object.type != kColAdjust) {
-    return false;
+    } else {
+      extmark_splice(curbuf,
+                     splice.start_row, splice.start_col,
+                     splice.oldextent_row, splice.oldextent_col,
+                     splice.newextent_row, splice.newextent_col,
+                     kExtmarkNoUndo);
+    }
+  // kExtmarkSavePos
+  } else if (undo_info.type == kExtmarkSavePos) {
+    ExtmarkSavePos pos = undo_info.data.savepos;
+    if (undo) {
+      if (pos.old_row >= 0) {
+        extmark_setraw(curbuf, pos.mark, pos.old_row, pos.old_col);
+      }
+    // Redo
+    } else {
+      if (pos.row >= 0) {
+        extmark_setraw(curbuf, pos.mark, pos.row, pos.col);
+      }
+    }
+  } else if (undo_info.type == kExtmarkMove) {
+    ExtmarkMove move = undo_info.data.move;
+    if (undo) {
+      extmark_move_region(curbuf,
+                          move.new_row, move.new_col,
+                          move.extent_row, move.extent_col,
+                          move.start_row, move.start_col,
+                          kExtmarkNoUndo);
+    } else {
+      extmark_move_region(curbuf,
+                          move.start_row, move.start_col,
+                          move.extent_row, move.extent_col,
+                          move.new_row, move.new_col,
+                          kExtmarkNoUndo);
+    }
   }
-  ColAdjust undo = object.data.col_adjust;
-  bool compactable = false;
+}
 
-  if (!undo.lnum_amount && !lnum_amount) {
-    if (undo.lnum == lnum) {
-      if ((undo.mincol + undo.col_amount) >= mincol) {
-          compactable = true;
-  } } }
 
-  if (!compactable) {
-    return false;
+// Adjust extmark row for inserted/deleted rows (columns stay fixed).
+void extmark_adjust(buf_T *buf,
+                    linenr_T line1,
+                    linenr_T line2,
+                    long amount,
+                    long amount_after,
+                    ExtmarkOp undo)
+{
+  if (!curbuf_splice_pending) {
+    int old_extent, new_extent;
+    if (amount == MAXLNUM) {
+      old_extent = (int)(line2 - line1+1);
+      new_extent = (int)(amount_after + old_extent);
+    } else {
+      // A region is either deleted (amount == MAXLNUM) or
+      // added (line2 == MAXLNUM). The only other case is :move
+      // which is handled by a separate entry point extmark_move_region.
+      assert(line2 == MAXLNUM);
+      old_extent = 0;
+      new_extent = (int)amount;
+    }
+    extmark_splice(buf,
+                   (int)line1-1, 0,
+                   old_extent, 0,
+                   new_extent, 0, undo);
   }
-
-  undo.col_amount = undo.col_amount + col_amount;
-  ExtmarkUndoObject new_undo = { .type = kColAdjust,
-                                 .data.col_adjust = undo };
-  kv_last(uhp->uh_extmark) = new_undo;
-  return true;
 }
 
-// Save col_adjust info so we can undo/redo
-void u_extmark_col_adjust(buf_T *buf, linenr_T lnum, colnr_T mincol,
-                          long lnum_amount, long col_amount)
+void extmark_splice(buf_T *buf,
+                    int start_row, colnr_T start_col,
+                    int oldextent_row, colnr_T oldextent_col,
+                    int newextent_row, colnr_T newextent_col,
+                    ExtmarkOp undo)
 {
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
-  }
-
-  if (!u_compact_col_adjust(buf, lnum, mincol, lnum_amount, col_amount)) {
-    ColAdjust col_adjust;
-    col_adjust.lnum = lnum;
-    col_adjust.mincol = mincol;
-    col_adjust.lnum_amount = lnum_amount;
-    col_adjust.col_amount = col_amount;
+  buf_updates_send_splice(buf, start_row, start_col,
+                          oldextent_row, oldextent_col,
+                          newextent_row, newextent_col);
 
-    ExtmarkUndoObject undo = { .type = kColAdjust,
-                               .data.col_adjust = col_adjust };
-
-    kv_push(uhp->uh_extmark, undo);
+  if (undo == kExtmarkUndo && (oldextent_row > 0 || oldextent_col > 0)) {
+    // Copy marks that would be effected by delete
+    // TODO(bfredl): Be "smart" about gravity here, left-gravity at the
+    // beginning and right-gravity at the end need not be preserved.
+    // Also be smart about marks that already have been saved (important for
+    // merge!)
+    int end_row = start_row + oldextent_row;
+    int end_col = (oldextent_row ? 0 : start_col) + oldextent_col;
+    u_extmark_copy(buf, start_row, start_col, end_row, end_col);
   }
-}
 
-// Save col_adjust_delete info so we can undo/redo
-void u_extmark_col_adjust_delete(buf_T *buf, linenr_T lnum,
-                                 colnr_T mincol, colnr_T endcol, int eol)
-{
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
-  }
 
-  ColAdjustDelete col_adjust_delete;
-  col_adjust_delete.lnum = lnum;
-  col_adjust_delete.mincol = mincol;
-  col_adjust_delete.endcol = endcol;
-  col_adjust_delete.eol = eol;
+  marktree_splice(buf->b_marktree, start_row, start_col,
+                  oldextent_row, oldextent_col,
+                  newextent_row, newextent_col);
 
-  ExtmarkUndoObject undo = { .type = kColAdjustDelete,
-                             .data.col_adjust_delete = col_adjust_delete };
+  if (undo == kExtmarkUndo) {
+    u_header_T  *uhp = u_force_get_undo_header(buf);
+    if (!uhp) {
+      return;
+    }
 
-  kv_push(uhp->uh_extmark, undo);
-}
+    bool merged = false;
+    // TODO(bfredl): this is quite rudimentary. We merge small (within line)
+    // inserts with each other and small deletes with each other. Add full
+    // merge algorithm later.
+    if (oldextent_row == 0 && newextent_row == 0 && kv_size(uhp->uh_extmark))  {
+      ExtmarkUndoObject *item = &kv_A(uhp->uh_extmark,
+                                      kv_size(uhp->uh_extmark)-1);
+      if (item->type == kExtmarkSplice) {
+        ExtmarkSplice *splice = &item->data.splice;
+        if (splice->start_row == start_row && splice->oldextent_row == 0
+            && splice->newextent_row == 0) {
+          if (oldextent_col == 0 && start_col >= splice->start_col
+              && start_col <= splice->start_col+splice->newextent_col) {
+            splice->newextent_col += newextent_col;
+            merged = true;
+          } else if (newextent_col == 0
+                     && start_col == splice->start_col+splice->newextent_col) {
+            splice->oldextent_col += oldextent_col;
+            merged = true;
+          } else if (newextent_col == 0
+                     && start_col + oldextent_col == splice->start_col) {
+            splice->start_col = start_col;
+            splice->oldextent_col += oldextent_col;
+            merged = true;
+          }
+        }
+      }
+    }
 
-// Save adjust info so we can undo/redo
-static void u_extmark_adjust(buf_T * buf, linenr_T line1, linenr_T line2,
-                             long amount, long amount_after)
-{
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
+    if (!merged) {
+      ExtmarkSplice splice;
+      splice.start_row = start_row;
+      splice.start_col = start_col;
+      splice.oldextent_row = oldextent_row;
+      splice.oldextent_col = oldextent_col;
+      splice.newextent_row = newextent_row;
+      splice.newextent_col = newextent_col;
+
+      kv_push(uhp->uh_extmark,
+              ((ExtmarkUndoObject){ .type = kExtmarkSplice,
+                                    .data.splice = splice }));
+    }
   }
-
-  Adjust adjust;
-  adjust.line1 = line1;
-  adjust.line2 = line2;
-  adjust.amount = amount;
-  adjust.amount_after = amount_after;
-
-  ExtmarkUndoObject undo = { .type = kLineAdjust,
-                             .data.adjust = adjust };
-
-  kv_push(uhp->uh_extmark, undo);
 }
 
-// save info to undo/redo a :move
-void u_extmark_move(buf_T *buf, linenr_T line1, linenr_T line2,
-                    linenr_T last_line, linenr_T dest, linenr_T num_lines,
-                    linenr_T extra)
+
+void extmark_move_region(buf_T *buf,
+                         int start_row, colnr_T start_col,
+                         int extent_row, colnr_T extent_col,
+                         int new_row, colnr_T new_col,
+                         ExtmarkOp undo)
 {
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
-  }
+  // TODO(bfredl): this is not synced to the buffer state inside the callback.
+  // But unless we make the undo implementation smarter, this is not ensured
+  // anyway.
+  buf_updates_send_splice(buf, start_row, start_col,
+                          extent_row, extent_col,
+                          0, 0);
 
-  AdjustMove move;
-  move.line1 = line1;
-  move.line2 = line2;
-  move.last_line = last_line;
-  move.dest = dest;
-  move.num_lines = num_lines;
-  move.extra = extra;
+  marktree_move_region(buf->b_marktree, start_row, start_col,
+                       extent_row, extent_col,
+                       new_row, new_col);
 
-  ExtmarkUndoObject undo = { .type = kAdjustMove,
-                             .data.move = move };
+  buf_updates_send_splice(buf, new_row, new_col,
+                          0, 0,
+                          extent_row, extent_col);
 
-  kv_push(uhp->uh_extmark, undo);
-}
 
-// copy extmarks data between range, useful when we cannot simply reverse
-// the operation. This will do nothing on redo, enforces correct position when
-// undo.
-// if ns = 0, it means copy all namespaces
-void u_extmark_copy(buf_T *buf, uint64_t ns,
-                    linenr_T l_lnum, colnr_T l_col,
-                    linenr_T u_lnum, colnr_T u_col)
-{
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
-  }
+  if (undo == kExtmarkUndo) {
+    u_header_T  *uhp = u_force_get_undo_header(buf);
+    if (!uhp) {
+      return;
+    }
 
-  bool all_ns = ns == 0 ? true : false;
+    ExtmarkMove move;
+    move.start_row = start_row;
+    move.start_col = start_col;
+    move.extent_row = extent_row;
+    move.extent_col = extent_col;
+    move.new_row = new_row;
+    move.new_col = new_col;
 
-  ExtmarkCopy copy;
-  ExtmarkUndoObject undo;
-  FOR_ALL_EXTMARKS(buf, 1, l_lnum, l_col, u_lnum, u_col, {
-    if (all_ns || extmark->ns_id == ns) {
-      copy.ns_id = extmark->ns_id;
-      copy.mark_id = extmark->mark_id;
-      copy.lnum = extmark->line->lnum;
-      copy.col = extmark->col;
-
-      undo.data.copy = copy;
-      undo.type = kExtmarkCopy;
-      kv_push(uhp->uh_extmark, undo);
-    }
-  });
+    kv_push(uhp->uh_extmark,
+            ((ExtmarkUndoObject){ .type = kExtmarkMove,
+                                  .data.move = move }));
+  }
 }
 
-void u_extmark_copy_place(buf_T *buf,
-                          linenr_T l_lnum, colnr_T l_col,
-                          linenr_T u_lnum, colnr_T u_col,
-                          linenr_T p_lnum, colnr_T p_col)
+uint64_t src2ns(Integer *src_id)
 {
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
+  if (*src_id == 0) {
+    *src_id = (Integer)nvim_create_namespace((String)STRING_INIT);
+  }
+  if (*src_id < 0) {
+    return UINT64_MAX;
+  } else {
+    return (uint64_t)(*src_id);
   }
+}
 
-  ExtmarkCopyPlace copy_place;
-  copy_place.l_lnum = l_lnum;
-  copy_place.l_col = l_col;
-  copy_place.u_lnum = u_lnum;
-  copy_place.u_col = u_col;
-  copy_place.p_lnum = p_lnum;
-  copy_place.p_col = p_col;
+/// Adds a decoration to a buffer.
+///
+/// Unlike matchaddpos() highlights, these follow changes to the the buffer
+/// texts. Decorations are represented internally and in the API as extmarks.
+///
+/// @param buf The buffer to add decorations to
+/// @param ns_id A valid namespace id.
+/// @param hl_id Id of the highlight group to use (or zero)
+/// @param start_row The line to highlight
+/// @param start_col First column to highlight
+/// @param end_row The line to highlight
+/// @param end_col The last column to highlight
+/// @param virt_text Virtual text (currently placed at the EOL of start_row)
+/// @return The extmark id inside the namespace
+uint64_t extmark_add_decoration(buf_T *buf, uint64_t ns_id, int hl_id,
+                                int start_row, colnr_T start_col,
+                                int end_row, colnr_T end_col,
+                                VirtText virt_text)
+{
+  ExtmarkNs *ns = buf_ns_ref(buf, ns_id, true);
+  ExtmarkItem item;
+  item.ns_id = ns_id;
+  item.mark_id = ns->free_id++;
+  item.hl_id = hl_id;
+  item.virt_text = virt_text;
+
+  uint64_t mark;
+
+  if (end_row > -1) {
+    mark = marktree_put_pair(buf->b_marktree,
+                             start_row, start_col, true,
+                             end_row, end_col, false);
+  } else {
+    mark = marktree_put(buf->b_marktree, start_row, start_col, true);
+  }
 
-  ExtmarkUndoObject undo = { .type = kExtmarkCopyPlace,
-                             .data.copy_place = copy_place };
+  map_put(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark, item);
+  map_put(uint64_t, uint64_t)(ns->map, item.mark_id, mark);
 
-  kv_push(uhp->uh_extmark, undo);
+  redraw_buf_range_later(buf, start_row+1,
+                         (end_row >= 0 ? end_row : start_row) + 1);
+  return item.mark_id;
 }
 
-// Save info for undo/redo of extmark_clear
-static void u_extmark_clear(buf_T *buf, uint64_t ns,
-                            linenr_T l_lnum, linenr_T u_lnum)
-{
-  u_header_T  *uhp = u_force_get_undo_header(buf);
-  if (!uhp) {
-    return;
+/// Add highlighting to a buffer, bounded by two cursor positions,
+/// with an offset.
+///
+/// @param buf Buffer to add highlights to
+/// @param src_id src_id to use or 0 to use a new src_id group,
+///               or -1 for ungrouped highlight.
+/// @param hl_id Highlight group id
+/// @param pos_start Cursor position to start the hightlighting at
+/// @param pos_end Cursor position to end the highlighting at
+/// @param offset Move the whole highlighting this many columns to the right
+void bufhl_add_hl_pos_offset(buf_T *buf,
+                             int src_id,
+                             int hl_id,
+                             lpos_T pos_start,
+                             lpos_T pos_end,
+                             colnr_T offset)
+{
+  colnr_T hl_start = 0;
+  colnr_T hl_end = 0;
+
+  // TODO(bfredl): if decoration had blocky mode, we could avoid this loop
+  for (linenr_T lnum = pos_start.lnum; lnum <= pos_end.lnum; lnum ++) {
+    if (pos_start.lnum < lnum && lnum < pos_end.lnum) {
+      hl_start = offset-1;
+      hl_end = MAXCOL;
+    } else if (lnum == pos_start.lnum && lnum < pos_end.lnum) {
+      hl_start = pos_start.col + offset;
+      hl_end = MAXCOL;
+    } else if (pos_start.lnum < lnum && lnum == pos_end.lnum) {
+      hl_start = offset-1;
+      hl_end = pos_end.col + offset;
+    } else if (pos_start.lnum == lnum && pos_end.lnum == lnum) {
+      hl_start = pos_start.col + offset;
+      hl_end = pos_end.col + offset;
+    }
+    (void)extmark_add_decoration(buf, (uint64_t)src_id, hl_id,
+                                 (int)lnum-1, hl_start, (int)lnum-1, hl_end,
+                                 VIRTTEXT_EMPTY);
   }
-
-  ExtmarkClear clear;
-  clear.ns_id = ns;
-  clear.l_lnum = l_lnum;
-  clear.u_lnum = u_lnum;
-
-  ExtmarkUndoObject undo = { .type = kExtmarkClear,
-                             .data.clear = clear };
-  kv_push(uhp->uh_extmark, undo);
 }
 
-// undo or redo an extmark operation
-void extmark_apply_undo(ExtmarkUndoObject undo_info, bool undo)
+void clear_virttext(VirtText *text)
 {
-  linenr_T lnum;
-  colnr_T mincol;
-  long lnum_amount;
-  long col_amount;
-  linenr_T line1;
-  linenr_T line2;
-  long amount;
-  long amount_after;
-
-  // use extmark_col_adjust
-  if (undo_info.type == kColAdjust) {
-    // Undo
-    if (undo) {
-      lnum = (undo_info.data.col_adjust.lnum
-              + undo_info.data.col_adjust.lnum_amount);
-      lnum_amount = -undo_info.data.col_adjust.lnum_amount;
-      col_amount = -undo_info.data.col_adjust.col_amount;
-      mincol = (undo_info.data.col_adjust.mincol
-                + (colnr_T)undo_info.data.col_adjust.col_amount);
-    // Redo
-    } else {
-      lnum = undo_info.data.col_adjust.lnum;
-      col_amount = undo_info.data.col_adjust.col_amount;
-      lnum_amount = undo_info.data.col_adjust.lnum_amount;
-      mincol = undo_info.data.col_adjust.mincol;
-    }
-    extmark_col_adjust(curbuf,
-                       lnum, mincol, lnum_amount, col_amount, kExtmarkNoUndo);
-  // use extmark_col_adjust_delete
-  } else if (undo_info.type == kColAdjustDelete) {
-    if (undo) {
-      mincol = undo_info.data.col_adjust_delete.mincol;
-      col_amount = (undo_info.data.col_adjust_delete.endcol
-                    - undo_info.data.col_adjust_delete.mincol) + 1;
-      extmark_col_adjust(curbuf,
-                         undo_info.data.col_adjust_delete.lnum,
-                         mincol,
-                         0,
-                         col_amount,
-                         kExtmarkNoUndo);
-    // Redo
-    } else {
-      extmark_col_adjust_delete(curbuf,
-                                undo_info.data.col_adjust_delete.lnum,
-                                undo_info.data.col_adjust_delete.mincol,
-                                undo_info.data.col_adjust_delete.endcol,
-                                kExtmarkNoUndo,
-                                undo_info.data.col_adjust_delete.eol);
-    }
-  // use extmark_adjust
-  } else if (undo_info.type == kLineAdjust) {
-    if (undo) {
-      // Undo - call signature type one - insert now
-      if (undo_info.data.adjust.amount == MAXLNUM) {
-        line1 = undo_info.data.adjust.line1;
-        line2 = MAXLNUM;
-        amount = -undo_info.data.adjust.amount_after;
-        amount_after = 0;
-      // Undo - call singature type two - delete now
-      } else if (undo_info.data.adjust.line2 == MAXLNUM) {
-        line1 = undo_info.data.adjust.line1;
-        line2 = undo_info.data.adjust.line2;
-        amount = -undo_info.data.adjust.amount;
-        amount_after = undo_info.data.adjust.amount_after;
-      // Undo - call signature three - move lines
-      } else {
-        line1 = (undo_info.data.adjust.line1
-                 + undo_info.data.adjust.amount);
-        line2 = (undo_info.data.adjust.line2
-                 + undo_info.data.adjust.amount);
-        amount = -undo_info.data.adjust.amount;
-        amount_after = -undo_info.data.adjust.amount_after;
-      }
-    // redo
-    } else {
-      line1 = undo_info.data.adjust.line1;
-      line2 = undo_info.data.adjust.line2;
-      amount = undo_info.data.adjust.amount;
-      amount_after = undo_info.data.adjust.amount_after;
-    }
-    extmark_adjust(curbuf,
-                   line1, line2, amount, amount_after, kExtmarkNoUndo, false);
-  // kExtmarkCopy
-  } else if (undo_info.type == kExtmarkCopy) {
-    // Redo should be handled by kColAdjustDelete or kExtmarkCopyPlace
-    if (undo) {
-      extmark_set(curbuf,
-                  undo_info.data.copy.ns_id,
-                  undo_info.data.copy.mark_id,
-                  undo_info.data.copy.lnum,
-                  undo_info.data.copy.col,
-                  kExtmarkNoUndo);
-    }
-  // uses extmark_copy_and_place
-  } else if (undo_info.type == kExtmarkCopyPlace) {
-    // Redo, undo is handle by kExtmarkCopy
-    if (!undo) {
-      extmark_copy_and_place(curbuf,
-                             undo_info.data.copy_place.l_lnum,
-                             undo_info.data.copy_place.l_col,
-                             undo_info.data.copy_place.u_lnum,
-                             undo_info.data.copy_place.u_col,
-                             undo_info.data.copy_place.p_lnum,
-                             undo_info.data.copy_place.p_col,
-                             kExtmarkNoUndo, true, NULL);
-    }
-  // kExtmarkClear
-  } else if (undo_info.type == kExtmarkClear) {
-    // Redo, undo is handle by kExtmarkCopy
-    if (!undo) {
-      extmark_clear(curbuf,
-                    undo_info.data.clear.ns_id,
-                    undo_info.data.clear.l_lnum,
-                    undo_info.data.clear.u_lnum,
-                    kExtmarkNoUndo);
-    }
-  // kAdjustMove
-  } else if (undo_info.type == kAdjustMove) {
-    apply_undo_move(undo_info, undo);
-  // extmark_set
-  } else if (undo_info.type == kExtmarkSet) {
-    if (undo) {
-      extmark_del(curbuf,
-                  undo_info.data.set.ns_id,
-                  undo_info.data.set.mark_id,
-                  kExtmarkNoUndo);
-    // Redo
-    } else {
-      extmark_set(curbuf,
-                  undo_info.data.set.ns_id,
-                  undo_info.data.set.mark_id,
-                  undo_info.data.set.lnum,
-                  undo_info.data.set.col,
-                  kExtmarkNoUndo);
-    }
-  // extmark_set into update
-  } else if (undo_info.type == kExtmarkUpdate) {
-    if (undo) {
-      extmark_set(curbuf,
-                  undo_info.data.update.ns_id,
-                  undo_info.data.update.mark_id,
-                  undo_info.data.update.old_lnum,
-                  undo_info.data.update.old_col,
-                  kExtmarkNoUndo);
-    // Redo
-    } else {
-      extmark_set(curbuf,
-                  undo_info.data.update.ns_id,
-                  undo_info.data.update.mark_id,
-                  undo_info.data.update.lnum,
-                  undo_info.data.update.col,
-                  kExtmarkNoUndo);
-    }
-  // extmark_del
-  } else if (undo_info.type == kExtmarkDel)  {
-    if (undo) {
-      extmark_set(curbuf,
-                  undo_info.data.set.ns_id,
-                  undo_info.data.set.mark_id,
-                  undo_info.data.set.lnum,
-                  undo_info.data.set.col,
-                  kExtmarkNoUndo);
-    // Redo
-    } else {
-      extmark_del(curbuf,
-                  undo_info.data.set.ns_id,
-                  undo_info.data.set.mark_id,
-                  kExtmarkNoUndo);
-    }
+  for (size_t i = 0; i < kv_size(*text); i++) {
+    xfree(kv_A(*text, i).text);
   }
+  kv_destroy(*text);
+  *text = (VirtText)KV_INITIAL_VALUE;
 }
 
-// undo/redo an kExtmarkMove operation
-static void apply_undo_move(ExtmarkUndoObject undo_info, bool undo)
+VirtText *extmark_find_virttext(buf_T *buf, int row, uint64_t ns_id)
 {
-  // 3 calls are required , see comment in function do_move (ex_cmds.c)
-  linenr_T line1 = undo_info.data.move.line1;
-  linenr_T line2 = undo_info.data.move.line2;
-  linenr_T last_line = undo_info.data.move.last_line;
-  linenr_T dest = undo_info.data.move.dest;
-  linenr_T num_lines = undo_info.data.move.num_lines;
-  linenr_T extra = undo_info.data.move.extra;
-
-  if (undo) {
-    if (dest >= line2) {
-      extmark_adjust(curbuf, dest - num_lines + 1, dest,
-                     last_line - dest + num_lines - 1, 0L, kExtmarkNoUndo,
-                     true);
-      extmark_adjust(curbuf, dest - line2, dest - line1,
-                     dest - line2, 0L, kExtmarkNoUndo, false);
-    } else {
-      extmark_adjust(curbuf, line1-num_lines, line2-num_lines,
-                     last_line - (line1-num_lines), 0L, kExtmarkNoUndo, true);
-      extmark_adjust(curbuf, (line1-num_lines) + 1, (line2-num_lines) + 1,
-                     -num_lines, 0L, kExtmarkNoUndo, false);
+  MarkTreeIter itr[1];
+  marktree_itr_get(buf->b_marktree, row, 0,  itr);
+  while (true) {
+    mtmark_t mark = marktree_itr_current(itr);
+    if (mark.row < 0 || mark.row > row) {
+      break;
     }
-    extmark_adjust(curbuf, last_line, last_line + num_lines - 1,
-                   line1 - last_line, 0L, kExtmarkNoUndo, true);
-  // redo
-  } else {
-    extmark_adjust(curbuf, line1, line2,
-                   last_line - line2, 0L, kExtmarkNoUndo, true);
-    if (dest >= line2) {
-      extmark_adjust(curbuf, line2 + 1, dest,
-                     -num_lines, 0L, kExtmarkNoUndo, false);
-    } else {
-      extmark_adjust(curbuf, dest + 1, line1 - 1,
-                     num_lines, 0L, kExtmarkNoUndo, false);
+    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
+                                                       mark.id, false);
+    if (item && (ns_id == 0 || ns_id == item->ns_id)
+        && kv_size(item->virt_text)) {
+      return &item->virt_text;
     }
-  extmark_adjust(curbuf, last_line - num_lines + 1, last_line,
-                 -(last_line - dest - extra), 0L, kExtmarkNoUndo, true);
+    marktree_itr_next(buf->b_marktree, itr);
   }
+  return NULL;
 }
 
 
-/// Get the column position for EOL on a line
-///
-/// If the lnum doesn't exist, returns 0
-colnr_T extmark_eol_col(buf_T *buf, linenr_T lnum)
+bool extmark_decorations_reset(buf_T *buf, DecorationState *state)
 {
-  if (lnum > buf->b_ml.ml_line_count) {
-    return 0;
-  }
-  return (colnr_T)STRLEN(ml_get_buf(buf, lnum, false)) + 1;
+  state->row = -1;
+  return buf->b_extmark_index;
 }
 
 
-// Adjust columns and rows for extmarks
-// based off mark_col_adjust in mark.c
-// returns true if something was moved otherwise false
-static bool extmark_col_adjust_impl(buf_T *buf, linenr_T lnum,
-                                    colnr_T mincol, long lnum_amount,
-                                    bool for_delete,
-                                    long update_col)
+bool extmark_decorations_start(buf_T *buf, int top_row, DecorationState *state)
 {
-  bool marks_exist = false;
-
-  ExtmarkLine *extmarkline = extmarkline_ref(buf, lnum, false);
-  if (!extmarkline) {
+  kv_size(state->active) = 0;
+  state->top_row = top_row;
+  marktree_itr_get(buf->b_marktree, top_row, 0, state->itr);
+  if (!state->itr->node) {
     return false;
   }
+  marktree_itr_rewind(buf->b_marktree, state->itr);
+  while (true) {
+    mtmark_t mark = marktree_itr_current(state->itr);
+    if (mark.row < 0) {  // || mark.row > end_row
+      break;
+    }
+    // TODO(bfredl): dedicated flag for being a decoration?
+    if ((mark.row < top_row && mark.id&MARKTREE_END_FLAG)) {
+      goto next_mark;
+    }
+    mtpos_t altpos = marktree_lookup(buf->b_marktree,
+                                     mark.id^MARKTREE_END_FLAG, NULL);
+
+    uint64_t start_id = mark.id & ~MARKTREE_END_FLAG;
+    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
+                                                       start_id, false);
+    if ((!(mark.id&MARKTREE_END_FLAG) && altpos.row < top_row
+         && !kv_size(item->virt_text))
+        || ((mark.id&MARKTREE_END_FLAG) && altpos.row >= top_row)) {
+      goto next_mark;
+    }
 
-  FOR_ALL_EXTMARKS_IN_LINE(extmarkline->items, mincol, MAXCOL, {
-    marks_exist = true;
-
-    // Calculate desired col amount where the adjustment should take place
-    // (not taking) eol into account
-    long col_amount;
-    if (for_delete) {
-      if (extmark->col < update_col) {
-        // When mark inside range
-        colnr_T start_effected_range = mincol - 1;
-        col_amount = -(extmark->col - start_effected_range);
+    if (item && (item->hl_id > 0 || kv_size(item->virt_text))) {
+      int attr_id = item->hl_id > 0 ? syn_id2attr(item->hl_id) : 0;
+      VirtText *vt = kv_size(item->virt_text) ? &item->virt_text : NULL;
+      HlRange range;
+      if (mark.id&MARKTREE_END_FLAG) {
+        range = (HlRange){ altpos.row, altpos.col, mark.row, mark.col,
+                           attr_id, vt };
       } else {
-        // Mark outside of range
-        // -1 because a delete of width 0 should still move marks
-        col_amount = -(update_col - mincol) - 1;
+        range = (HlRange){ mark.row, mark.col, altpos.row,
+                           altpos.col, attr_id, vt };
       }
-    } else {
-      // for anything other than deletes
-      col_amount = update_col;
+      kv_push(state->active, range);
     }
-
-    // No update required for this guy
-    if (col_amount == 0 && lnum_amount == 0) {
-      continue;
-    }
-
-    // Set mark to start of line
-    if (col_amount < 0
-        && extmark->col <= (colnr_T)-col_amount) {
-      extmark_update(extmark, buf, extmark->ns_id, extmark->mark_id,
-                     extmarkline->lnum + lnum_amount,
-                     1, kExtmarkNoUndo, &mitr);
-      // Update the mark
-    } else {
-      // Note: The undo is handled by u_extmark_col_adjust, NoUndo here
-      extmark_update(extmark, buf, extmark->ns_id, extmark->mark_id,
-                     extmarkline->lnum + lnum_amount,
-                     extmark->col + (colnr_T)col_amount, kExtmarkNoUndo, &mitr);
+next_mark:
+    if (marktree_itr_node_done(state->itr)) {
+      break;
     }
-  })
-
-  if (kb_size(&extmarkline->items) == 0) {
-    kb_del(extmarklines, &buf->b_extlines, extmarkline);
-    extmarkline_free(extmarkline);
+    marktree_itr_next(buf->b_marktree, state->itr);
   }
 
-  return marks_exist;
+  return true;  // TODO(bfredl): check if available in the region
 }
 
-// Adjust columns and rows for extmarks
-//
-// based off mark_col_adjust in mark.c
-// use extmark_col_adjust_impl to move columns by inserting
-// Doesn't take the eol into consideration (possible to put marks in invalid
-// positions)
-void extmark_col_adjust(buf_T *buf, linenr_T lnum,
-                        colnr_T mincol, long lnum_amount,
-                        long col_amount, ExtmarkOp undo)
+bool extmark_decorations_line(buf_T *buf, int row, DecorationState *state)
 {
-  assert(col_amount > INT_MIN && col_amount <= INT_MAX);
-
-  bool marks_moved =  extmark_col_adjust_impl(buf, lnum, mincol, lnum_amount,
-                                              false, col_amount);
-
-  marks_moved |= bufhl_mark_col_adjust(buf, lnum, mincol,
-                                       lnum_amount, col_amount);
-
-  if (undo == kExtmarkUndo && marks_moved) {
-    u_extmark_col_adjust(buf, lnum, mincol, lnum_amount, col_amount);
+  if (state->row == -1) {
+    extmark_decorations_start(buf, row, state);
   }
+  state->row = row;
+  state->col_until = -1;
+  return true;  // TODO(bfredl): be more precise
 }
 
-// Adjust marks after a delete on a line
-//
-// Automatically readjusts to take the eol into account
-// TODO(timeyyy): change mincol to be for the mark to be copied, not moved
-//
-// @param mincol First column that needs to be moved (start of delete range) + 1
-// @param endcol Last column which needs to be copied (end of delete range + 1)
-void extmark_col_adjust_delete(buf_T *buf, linenr_T lnum,
-                               colnr_T mincol, colnr_T endcol,
-                               ExtmarkOp undo, int _eol)
+int extmark_decorations_col(buf_T *buf, int col, DecorationState *state)
 {
-  colnr_T start_effected_range = mincol;
-
-  bool marks_moved;
-  if (undo == kExtmarkUndo) {
-    // Copy marks that would be effected by delete
-    // -1 because we need to restore if a mark existed at the start pos
-    u_extmark_copy(buf, 0, lnum, start_effected_range, lnum, endcol);
-  }
-
-  marks_moved = extmark_col_adjust_impl(buf, lnum, mincol, 0,
-                                        true, (long)endcol);
-
-  marks_moved |= bufhl_mark_col_adjust(buf, lnum, endcol, 0, mincol-(endcol+1));
-  // Deletes at the end of the line have different behaviour than the normal
-  // case when deleted.
-  // Cleanup any marks that are floating beyond the end of line.
-  // we allow this to be passed in as well because the buffer may have already
-  // been mutated.
-  int eol = _eol;
-  if (!eol) {
-    eol = extmark_eol_col(buf, lnum);
-  }
-  FOR_ALL_EXTMARKS(buf, 1, lnum, eol, lnum, -1, {
-    extmark_update(extmark, buf, extmark->ns_id, extmark->mark_id,
-                   extmarkline->lnum, (colnr_T)eol, kExtmarkNoUndo, &mitr);
-  })
-
-  // Record the undo for the actual move
-  if (marks_moved && undo == kExtmarkUndo) {
-    u_extmark_col_adjust_delete(buf, lnum, mincol, endcol, eol);
+  if (col <= state->col_until) {
+    return state->current;
   }
-}
+  state->col_until = MAXCOL;
+  while (true) {
+    mtmark_t mark = marktree_itr_current(state->itr);
+    if (mark.row < 0 || mark.row > state->row) {
+      break;
+    } else if (mark.row == state->row && mark.col > col) {
+      state->col_until = mark.col-1;
+      break;
+    }
 
-// Adjust extmark row for inserted/deleted rows (columns stay fixed).
-void extmark_adjust(buf_T *buf,
-                    linenr_T line1,
-                    linenr_T line2,
-                    long amount,
-                    long amount_after,
-                    ExtmarkOp undo,
-                    bool end_temp)
-{
-  ExtmarkLine *_extline;
-
-  // btree needs to be kept ordered to work, so far only :move requires this
-  // 2nd call with end_temp = true unpack the lines from the temp position
-  if (end_temp && amount < 0) {
-    for (size_t i = 0; i < kv_size(buf->b_extmark_move_space); i++) {
-      _extline = kv_A(buf->b_extmark_move_space, i);
-      _extline->lnum += amount;
-      kb_put(extmarklines, &buf->b_extlines, _extline);
+    if ((mark.id&MARKTREE_END_FLAG)) {
+       // TODO(bfredl): check decorations flag
+      goto next_mark;
     }
-    kv_size(buf->b_extmark_move_space) = 0;
-    return;
-  }
+    mtpos_t endpos = marktree_lookup(buf->b_marktree,
+                                     mark.id|MARKTREE_END_FLAG, NULL);
 
-  bool marks_exist = false;
-  linenr_T *lp;
-
-  linenr_T adj_start = line1;
-  if (amount == MAXLNUM) {
-    // Careful! marks from deleted region can end up on en extisting extmarkline
-    // that is goinig to be adjusted to the target position.
-    linenr_T join_num = line1 - amount_after;
-    ExtmarkLine *joinline = (join_num > line2
-                             ? extmarkline_ref(buf, join_num, false) : NULL);
-
-    // extmark_adjust is already redoable, the copy should only be for undo
-    marks_exist = extmark_copy_and_place(curbuf,
-                                         line1, 1,
-                                         line2, MAXCOL,
-                                         line1, 1,
-                                         kExtmarkUndoNoRedo, true, joinline);
-    adj_start = line2+1;
-  }
-  FOR_ALL_EXTMARKLINES(buf, adj_start, MAXLNUM, {
-    marks_exist = true;
-    lp = &(extmarkline->lnum);
-    if (*lp <= line2) {
-      // 1st call with end_temp = true, store the lines in a temp position
-      if (end_temp && amount > 0) {
-          kb_del_itr_extmarklines(&buf->b_extlines, &itr);
-          kv_push(buf->b_extmark_move_space, extmarkline);
-      }
+    ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
+                                                       mark.id, false);
 
-      *lp += amount;
-    } else if (amount_after && *lp > line2) {
-      *lp += amount_after;
+    if (endpos.row < mark.row
+        || (endpos.row == mark.row && endpos.col <= mark.col)) {
+      if (!kv_size(item->virt_text)) {
+        goto next_mark;
+      }
     }
-  })
 
-  if (undo == kExtmarkUndo && marks_exist) {
-    u_extmark_adjust(buf, line1, line2, amount, amount_after);
-  }
-}
-
-/// Range points to copy
-///
-/// if part of a larger iteration we can't delete, then the caller
-/// must check for empty lines.
-bool extmark_copy_and_place(buf_T *buf,
-                            linenr_T l_lnum, colnr_T l_col,
-                            linenr_T u_lnum, colnr_T u_col,
-                            linenr_T p_lnum, colnr_T p_col,
-                            ExtmarkOp undo, bool delete,
-                            ExtmarkLine *destline)
+    if (item && (item->hl_id > 0 || kv_size(item->virt_text))) {
+      int attr_id = item->hl_id > 0 ? syn_id2attr(item->hl_id) : 0;
+      VirtText *vt = kv_size(item->virt_text) ? &item->virt_text : NULL;
+      kv_push(state->active, ((HlRange){ mark.row, mark.col,
+                                         endpos.row, endpos.col,
+                                         attr_id, vt }));
+    }
 
-{
-  bool marks_moved = false;
-  if (undo == kExtmarkUndo || undo == kExtmarkUndoNoRedo) {
-    // Copy marks that would be effected by delete
-    u_extmark_copy(buf, 0, l_lnum, l_col, u_lnum, u_col);
+next_mark:
+    marktree_itr_next(buf->b_marktree, state->itr);
   }
 
-  // Move extmarks to their final position
-  // Careful: if we move items within the same line, we might change order of
-  // marks within the same extmarkline. Too keep it simple, first delete all
-  // items from the extmarkline and put them back in the right order.
-  FOR_ALL_EXTMARKLINES(buf, l_lnum, u_lnum, {
-    kvec_t(Extmark) temp_space = KV_INITIAL_VALUE;
-    bool same_line = extmarkline == destline;
-    FOR_ALL_EXTMARKS_IN_LINE(extmarkline->items,
-                             (extmarkline->lnum > l_lnum) ? 0 : l_col,
-                             (extmarkline->lnum < u_lnum) ? MAXCOL : u_col, {
-      if (!destline) {
-        destline = extmarkline_ref(buf, p_lnum, true);
-        same_line = extmarkline == destline;
+  int attr = 0;
+  size_t j = 0;
+  for (size_t i = 0; i < kv_size(state->active); i++) {
+    HlRange item = kv_A(state->active, i);
+    bool active = false, keep = true;
+    if (item.end_row < state->row
+        || (item.end_row == state->row && item.end_col <= col)) {
+      if (!(item.start_row >= state->row && item.virt_text)) {
+        keep = false;
       }
-      marks_moved = true;
-      if (!same_line) {
-        extmark_put(p_col, extmark->mark_id, destline, extmark->ns_id);
-        ExtmarkNs *ns_obj = pmap_get(uint64_t)(buf->b_extmark_ns,
-                                               extmark->ns_id);
-        pmap_put(uint64_t)(ns_obj->map, extmark->mark_id, destline);
+    } else {
+      if (item.start_row < state->row
+          || (item.start_row == state->row && item.start_col <= col)) {
+        active = true;
+        if (item.end_row == state->row) {
+          state->col_until = MIN(state->col_until, item.end_col-1);
+        }
       } else {
-        kv_push(temp_space, *extmark);
-      }
-      // Delete old mark
-      kb_del_itr(markitems, &extmarkline->items, &mitr);
-    })
-    if (same_line) {
-      for (size_t i = 0; i < kv_size(temp_space); i++) {
-        Extmark mark = kv_A(temp_space, i);
-        extmark_put(p_col, mark.mark_id, extmarkline, mark.ns_id);
+        if (item.start_row == state->row) {
+          state->col_until = MIN(state->col_until, item.start_col-1);
+        }
       }
-      kv_destroy(temp_space);
-    } else if (delete && kb_size(&extmarkline->items) == 0) {
-      kb_del_itr(extmarklines, &buf->b_extlines, &itr);
-      extmarkline_free(extmarkline);
     }
-  })
-
-  // Record the undo for the actual move
-  if (marks_moved && undo == kExtmarkUndo) {
-    u_extmark_copy_place(buf, l_lnum, l_col, u_lnum, u_col, p_lnum, p_col);
+    if (active && item.attr_id > 0) {
+      attr = hl_combine_attr(attr, item.attr_id);
+    }
+    if (keep) {
+      kv_A(state->active, j++) = kv_A(state->active, i);
+    }
   }
-
-  return marks_moved;
+  kv_size(state->active) = j;
+  state->current = attr;
+  return attr;
 }
 
-// Get reference to line in kbtree_t, allocating it if neccessary.
-ExtmarkLine *extmarkline_ref(buf_T *buf, linenr_T lnum, bool put)
+VirtText *extmark_decorations_virt_text(buf_T *buf, DecorationState *state)
 {
-  kbtree_t(extmarklines) *b = &buf->b_extlines;
-  ExtmarkLine t, **pp;
-  t.lnum = lnum;
-
-  pp = kb_get(extmarklines, b, &t);
-  if (!pp) {
-    if (!put) {
-      return NULL;
+  extmark_decorations_col(buf, MAXCOL, state);
+  for (size_t i = 0; i < kv_size(state->active); i++) {
+    HlRange item = kv_A(state->active, i);
+    if (item.start_row == state->row && item.virt_text) {
+      return item.virt_text;
     }
-    ExtmarkLine *p = xcalloc(sizeof(ExtmarkLine), 1);
-    p->lnum = lnum;
-    // p->items zero initialized
-    kb_put(extmarklines, b, p);
-    return p;
   }
-  // Return existing
-  return *pp;
-}
-
-void extmarkline_free(ExtmarkLine *extmarkline)
-{
-  kb_destroy(markitems, (&extmarkline->items));
-  xfree(extmarkline);
-}
-
-/// Put an extmark into a line,
-///
-/// caller must ensure combination of id and ns_id isn't in use.
-void extmark_put(colnr_T col, uint64_t id,
-                 ExtmarkLine *extmarkline, uint64_t ns)
-{
-  Extmark t;
-  t.col = col;
-  t.mark_id = id;
-  t.line = extmarkline;
-  t.ns_id = ns;
-
-  kbtree_t(markitems) *b = &(extmarkline->items);
-  // kb_put requries the key to not be there
-  assert(!kb_getp(markitems, b, &t));
-
-  kb_put(markitems, b, t);
+  return NULL;
 }
-
-