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

26 files changed, 1646 insertions, 2372 deletions

diff --git a/src/nvim/api/buffer.c b/src/nvim/api/buffer.c
index e6f8f73b9d..3106011fe2 100644
--- a/src/nvim/api/buffer.c
+++ b/src/nvim/api/buffer.c
@@ -170,6 +170,14 @@ Boolean nvim_buf_attach(uint64_t channel_id,
       }
       cb.on_lines = v->data.luaref;
       v->data.luaref = LUA_NOREF;
+    } else if (is_lua && strequal("_on_bytes", k.data)) {
+      // NB: undocumented, untested and incomplete interface!
+      if (v->type != kObjectTypeLuaRef) {
+        api_set_error(err, kErrorTypeValidation, "callback is not a function");
+        goto error;
+      }
+      cb.on_bytes = v->data.luaref;
+      v->data.luaref = LUA_NOREF;
     } else if (is_lua && strequal("on_changedtick", k.data)) {
       if (v->type != kObjectTypeLuaRef) {
         api_set_error(err, kErrorTypeValidation, "callback is not a function");
@@ -201,6 +209,7 @@ Boolean nvim_buf_attach(uint64_t channel_id,
 error:
   // TODO(bfredl): ASAN build should check that the ref table is empty?
   executor_free_luaref(cb.on_lines);
+  executor_free_luaref(cb.on_bytes);
   executor_free_luaref(cb.on_changedtick);
   executor_free_luaref(cb.on_detach);
   return false;
@@ -639,7 +648,6 @@ void nvim_buf_set_lines(uint64_t channel_id,
               (linenr_T)(end - 1),
               MAXLNUM,
               (long)extra,
-              false,
               kExtmarkUndo);
 
   changed_lines((linenr_T)start, 0, (linenr_T)end, (long)extra, true);
@@ -1119,12 +1127,12 @@ ArrayOf(Integer) nvim_buf_get_extmark_by_id(Buffer buffer, Integer ns_id,
     return rv;
   }
 
-  Extmark *extmark = extmark_from_id(buf, (uint64_t)ns_id, (uint64_t)id);
-  if (!extmark) {
+  ExtmarkInfo extmark = extmark_from_id(buf, (uint64_t)ns_id, (uint64_t)id);
+  if (extmark.row < 0) {
     return rv;
   }
-  ADD(rv, INTEGER_OBJ((Integer)extmark->line->lnum-1));
-  ADD(rv, INTEGER_OBJ((Integer)extmark->col-1));
+  ADD(rv, INTEGER_OBJ((Integer)extmark.row));
+  ADD(rv, INTEGER_OBJ((Integer)extmark.col));
   return rv;
 }
 
@@ -1204,43 +1212,39 @@ Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start,
 
   if (limit == 0) {
     return rv;
+  } else if (limit < 0) {
+    limit = INT64_MAX;
   }
 
 
   bool reverse = false;
 
-  linenr_T l_lnum;
+  int l_row;
   colnr_T l_col;
-  if (!extmark_get_index_from_obj(buf, ns_id, start, &l_lnum, &l_col, err)) {
+  if (!extmark_get_index_from_obj(buf, ns_id, start, &l_row, &l_col, err)) {
     return rv;
   }
 
-  linenr_T u_lnum;
+  int u_row;
   colnr_T u_col;
-  if (!extmark_get_index_from_obj(buf, ns_id, end, &u_lnum, &u_col, err)) {
+  if (!extmark_get_index_from_obj(buf, ns_id, end, &u_row, &u_col, err)) {
     return rv;
   }
 
-  if (l_lnum > u_lnum || (l_lnum == u_lnum && l_col > u_col)) {
+  if (l_row > u_row || (l_row == u_row && l_col > u_col)) {
     reverse = true;
-    linenr_T tmp_lnum = l_lnum;
-    l_lnum = u_lnum;
-    u_lnum = tmp_lnum;
-    colnr_T tmp_col = l_col;
-    l_col = u_col;
-    u_col = tmp_col;
   }
 
 
-  ExtmarkArray marks = extmark_get(buf, (uint64_t)ns_id, l_lnum, l_col, u_lnum,
+  ExtmarkArray marks = extmark_get(buf, (uint64_t)ns_id, l_row, l_col, u_row,
                                    u_col, (int64_t)limit, reverse);
 
   for (size_t i = 0; i < kv_size(marks); i++) {
     Array mark = ARRAY_DICT_INIT;
-    Extmark *extmark = kv_A(marks, i);
-    ADD(mark, INTEGER_OBJ((Integer)extmark->mark_id));
-    ADD(mark, INTEGER_OBJ(extmark->line->lnum-1));
-    ADD(mark, INTEGER_OBJ(extmark->col-1));
+    ExtmarkInfo extmark = kv_A(marks, i);
+    ADD(mark, INTEGER_OBJ((Integer)extmark.mark_id));
+    ADD(mark, INTEGER_OBJ(extmark.row));
+    ADD(mark, INTEGER_OBJ(extmark.col));
     ADD(rv, ARRAY_OBJ(mark));
   }
 
@@ -1301,17 +1305,15 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer id,
   }
 
   uint64_t id_num;
-  if (id == 0) {
-    id_num = extmark_free_id_get(buf, (uint64_t)ns_id);
-  } else if (id > 0) {
+  if (id >= 0) {
     id_num = (uint64_t)id;
   } else {
     api_set_error(err, kErrorTypeValidation, _("Invalid mark id"));
     return 0;
   }
 
-  extmark_set(buf, (uint64_t)ns_id, id_num,
-              (linenr_T)line+1, (colnr_T)col+1, kExtmarkUndo);
+  id_num = extmark_set(buf, (uint64_t)ns_id, id_num,
+                       (int)line, (colnr_T)col, kExtmarkUndo);
 
   return (Integer)id_num;
 }
@@ -1339,7 +1341,7 @@ Boolean nvim_buf_del_extmark(Buffer buffer,
     return false;
   }
 
-  return extmark_del(buf, (uint64_t)ns_id, (uint64_t)id, kExtmarkUndo);
+  return extmark_del(buf, (uint64_t)ns_id, (uint64_t)id);
 }
 
 /// Adds a highlight to buffer.
@@ -1373,7 +1375,7 @@ Boolean nvim_buf_del_extmark(Buffer buffer,
 /// @param[out] err   Error details, if any
 /// @return The ns_id that was used
 Integer nvim_buf_add_highlight(Buffer buffer,
-                               Integer ns_id,
+                               Integer src_id,
                                String hl_group,
                                Integer line,
                                Integer col_start,
@@ -1398,14 +1400,31 @@ Integer nvim_buf_add_highlight(Buffer buffer,
     col_end = MAXCOL;
   }
 
+  uint64_t ns_id = src2ns(&src_id);
+
+  if (!(0 <= line && line < buf->b_ml.ml_line_count)) {
+    // safety check, we can't add marks outside the range
+    return src_id;
+  }
+
   int hlg_id = 0;
   if (hl_group.size > 0) {
     hlg_id = syn_check_group((char_u *)hl_group.data, (int)hl_group.size);
+  } else {
+    return src_id;
+  }
+
+  int end_line = (int)line;
+  if (col_end == MAXCOL) {
+    col_end = 0;
+    end_line++;
   }
 
-  ns_id = bufhl_add_hl(buf, (int)ns_id, hlg_id, (linenr_T)line+1,
-                       (colnr_T)col_start+1, (colnr_T)col_end);
-  return ns_id;
+  ns_id = extmark_add_decoration(buf, ns_id, hlg_id,
+                                 (int)line, (colnr_T)col_start,
+                                 end_line, (colnr_T)col_end,
+                                 VIRTTEXT_EMPTY);
+  return src_id;
 }
 
 /// Clears namespaced objects (highlights, extmarks, virtual text) from
@@ -1439,12 +1458,9 @@ void nvim_buf_clear_namespace(Buffer buffer,
   if (line_end < 0 || line_end > MAXLNUM) {
     line_end = MAXLNUM;
   }
-
-  bufhl_clear_line_range(buf, (int)ns_id, (int)line_start+1, (int)line_end);
-  extmark_clear(buf, ns_id == -1 ? 0 : (uint64_t)ns_id,
-                (linenr_T)line_start+1,
-                (linenr_T)line_end,
-                kExtmarkUndo);
+  extmark_clear(buf, (ns_id < 0 ? 0 : (uint64_t)ns_id),
+                (int)line_start, 0,
+                (int)line_end-1, MAXCOL);
 }
 
 /// Clears highlights and virtual text from namespace and range of lines
@@ -1467,6 +1483,43 @@ void nvim_buf_clear_highlight(Buffer buffer,
   nvim_buf_clear_namespace(buffer, ns_id, line_start, line_end, err);
 }
 
+static VirtText parse_virt_text(Array chunks, Error *err)
+{
+  VirtText virt_text = KV_INITIAL_VALUE;
+  for (size_t i = 0; i < chunks.size; i++) {
+    if (chunks.items[i].type != kObjectTypeArray) {
+      api_set_error(err, kErrorTypeValidation, "Chunk is not an array");
+      goto free_exit;
+    }
+    Array chunk = chunks.items[i].data.array;
+    if (chunk.size == 0 || chunk.size > 2
+        || chunk.items[0].type != kObjectTypeString
+        || (chunk.size == 2 && chunk.items[1].type != kObjectTypeString)) {
+      api_set_error(err, kErrorTypeValidation,
+                    "Chunk is not an array with one or two strings");
+      goto free_exit;
+    }
+
+    String str = chunk.items[0].data.string;
+    char *text = transstr(str.size > 0 ? str.data : "");  // allocates
+
+    int hl_id = 0;
+    if (chunk.size == 2) {
+      String hl = chunk.items[1].data.string;
+      if (hl.size > 0) {
+        hl_id = syn_check_group((char_u *)hl.data, (int)hl.size);
+      }
+    }
+    kv_push(virt_text, ((VirtTextChunk){ .text = text, .hl_id = hl_id }));
+  }
+
+  return virt_text;
+
+free_exit:
+  clear_virttext(&virt_text);
+  return virt_text;
+}
+
 
 /// Set the virtual text (annotation) for a buffer line.
 ///
@@ -1496,7 +1549,7 @@ void nvim_buf_clear_highlight(Buffer buffer,
 /// @param[out] err   Error details, if any
 /// @return The ns_id that was used
 Integer nvim_buf_set_virtual_text(Buffer buffer,
-                                  Integer ns_id,
+                                  Integer src_id,
                                   Integer line,
                                   Array chunks,
                                   Dictionary opts,
@@ -1518,41 +1571,26 @@ Integer nvim_buf_set_virtual_text(Buffer buffer,
     return 0;
   }
 
-  VirtText virt_text = KV_INITIAL_VALUE;
-  for (size_t i = 0; i < chunks.size; i++) {
-    if (chunks.items[i].type != kObjectTypeArray) {
-      api_set_error(err, kErrorTypeValidation, "Chunk is not an array");
-      goto free_exit;
-    }
-    Array chunk = chunks.items[i].data.array;
-    if (chunk.size == 0 || chunk.size > 2
-        || chunk.items[0].type != kObjectTypeString
-        || (chunk.size == 2 && chunk.items[1].type != kObjectTypeString)) {
-      api_set_error(err, kErrorTypeValidation,
-                    "Chunk is not an array with one or two strings");
-      goto free_exit;
-    }
-
-    String str = chunk.items[0].data.string;
-    char *text = transstr(str.size > 0 ? str.data : "");  // allocates
+  uint64_t ns_id = src2ns(&src_id);
 
-    int hl_id = 0;
-    if (chunk.size == 2) {
-      String hl = chunk.items[1].data.string;
-      if (hl.size > 0) {
-        hl_id = syn_check_group((char_u *)hl.data, (int)hl.size);
-      }
-    }
-    kv_push(virt_text, ((VirtTextChunk){ .text = text, .hl_id = hl_id }));
+  VirtText virt_text = parse_virt_text(chunks, err);
+  if (ERROR_SET(err)) {
+    return 0;
   }
 
-  ns_id = bufhl_add_virt_text(buf, (int)ns_id, (linenr_T)line+1,
-                              virt_text);
-  return ns_id;
 
-free_exit:
-  kv_destroy(virt_text);
-  return 0;
+  VirtText *existing = extmark_find_virttext(buf, (int)line, ns_id);
+
+  if (existing) {
+    clear_virttext(existing);
+    *existing = virt_text;
+    return src_id;
+  }
+
+  extmark_add_decoration(buf, ns_id, 0,
+                         (int)line, 0, -1, -1,
+                         virt_text);
+  return src_id;
 }
 
 /// Get the virtual text (annotation) for a buffer line.
@@ -1570,7 +1608,7 @@ free_exit:
 /// @param line     Line to get the virtual text from (zero-indexed)
 /// @param[out] err Error details, if any
 /// @return         List of virtual text chunks
-Array nvim_buf_get_virtual_text(Buffer buffer, Integer lnum, Error *err)
+Array nvim_buf_get_virtual_text(Buffer buffer, Integer line, Error *err)
   FUNC_API_SINCE(7)
 {
   Array chunks = ARRAY_DICT_INIT;
@@ -1580,20 +1618,20 @@ Array nvim_buf_get_virtual_text(Buffer buffer, Integer lnum, Error *err)
     return chunks;
   }
 
-  if (lnum < 0 || lnum >= MAXLNUM) {
+  if (line < 0 || line >= MAXLNUM) {
     api_set_error(err, kErrorTypeValidation, "Line number outside range");
     return chunks;
   }
 
-  BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, (linenr_T)(lnum + 1),
-                                       false);
-  if (!lineinfo) {
+  VirtText *virt_text = extmark_find_virttext(buf, (int)line, 0);
+
+  if (!virt_text) {
     return chunks;
   }
 
-  for (size_t i = 0; i < lineinfo->virt_text.size; i++) {
+  for (size_t i = 0; i < virt_text->size; i++) {
     Array chunk = ARRAY_DICT_INIT;
-    VirtTextChunk *vtc = &lineinfo->virt_text.items[i];
+    VirtTextChunk *vtc = &virt_text->items[i];
     ADD(chunk, STRING_OBJ(cstr_to_string(vtc->text)));
     if (vtc->hl_id > 0) {
       ADD(chunk, STRING_OBJ(cstr_to_string(
@@ -1605,6 +1643,59 @@ Array nvim_buf_get_virtual_text(Buffer buffer, Integer lnum, Error *err)
   return chunks;
 }
 
+Integer nvim__buf_add_decoration(Buffer buffer, Integer ns_id, String hl_group,
+                                 Integer start_row, Integer start_col,
+                                 Integer end_row, Integer end_col,
+                                 Array virt_text,
+                                 Error *err)
+{
+  buf_T *buf = find_buffer_by_handle(buffer, err);
+  if (!buf) {
+    return 0;
+  }
+
+  if (!ns_initialized((uint64_t)ns_id)) {
+    api_set_error(err, kErrorTypeValidation, _("Invalid ns_id"));
+    return 0;
+  }
+
+
+  if (start_row < 0 || start_row >= MAXLNUM || end_row > MAXCOL) {
+    api_set_error(err, kErrorTypeValidation, "Line number outside range");
+    return 0;
+  }
+
+  if (start_col < 0 || start_col > MAXCOL || end_col > MAXCOL) {
+    api_set_error(err, kErrorTypeValidation, "Column value outside range");
+    return 0;
+  }
+  if (end_row < 0 || end_col < 0) {
+    end_row = -1;
+    end_col = -1;
+  }
+
+  if (start_row >= buf->b_ml.ml_line_count
+      || end_row >= buf->b_ml.ml_line_count) {
+    // safety check, we can't add marks outside the range
+    return 0;
+  }
+
+  int hlg_id = 0;
+  if (hl_group.size > 0) {
+    hlg_id = syn_check_group((char_u *)hl_group.data, (int)hl_group.size);
+  }
+
+  VirtText vt = parse_virt_text(virt_text, err);
+  if (ERROR_SET(err)) {
+    return 0;
+  }
+
+  uint64_t mark_id = extmark_add_decoration(buf, (uint64_t)ns_id, hlg_id,
+                                            (int)start_row, (colnr_T)start_col,
+                                            (int)end_row, (colnr_T)end_col, vt);
+  return (Integer)mark_id;
+}
+
 Dictionary nvim__buf_stats(Buffer buffer, Error *err)
 {
   Dictionary rv = ARRAY_DICT_INIT;
@@ -1626,6 +1717,16 @@ Dictionary nvim__buf_stats(Buffer buffer, Error *err)
   // this exists to debug issues
   PUT(rv, "dirty_bytes", INTEGER_OBJ((Integer)buf->deleted_bytes));
 
+  u_header_T *uhp = NULL;
+  if (buf->b_u_curhead != NULL) {
+    uhp = buf->b_u_curhead;
+  } else if (buf->b_u_newhead) {
+    uhp = buf->b_u_newhead;
+  }
+  if (uhp) {
+    PUT(rv, "uhp_extmark_size", INTEGER_OBJ((Integer)kv_size(uhp->uh_extmark)));
+  }
+
   return rv;
 }
 
diff --git a/src/nvim/api/private/helpers.c b/src/nvim/api/private/helpers.c
index 36331eee6e..37e31e0807 100644
--- a/src/nvim/api/private/helpers.c
+++ b/src/nvim/api/private/helpers.c
@@ -1511,61 +1511,6 @@ ArrayOf(Dictionary) keymap_array(String mode, buf_T *buf)
   return mappings;
 }
 
-// Returns an extmark given an id or a positional index
-// If throw == true then an error will be raised if nothing
-// was found
-// Returns NULL if something went wrong
-Extmark *extmark_from_id_or_pos(Buffer buffer, Integer ns, Object id,
-                                Error *err, bool throw)
-{
-  buf_T *buf = find_buffer_by_handle(buffer, err);
-
-  if (!buf) {
-    return NULL;
-  }
-
-  Extmark *extmark = NULL;
-  if (id.type == kObjectTypeArray) {
-    if (id.data.array.size != 2) {
-      api_set_error(err, kErrorTypeValidation,
-                    _("Position must have 2 elements"));
-      return NULL;
-    }
-    linenr_T row = (linenr_T)id.data.array.items[0].data.integer;
-    colnr_T col = (colnr_T)id.data.array.items[1].data.integer;
-    if (row < 1 || col < 1) {
-      if (throw) {
-      api_set_error(err, kErrorTypeValidation, _("Row and column MUST be > 0"));
-      }
-      return NULL;
-    }
-    extmark = extmark_from_pos(buf, (uint64_t)ns, row, col);
-  } else if (id.type != kObjectTypeInteger) {
-    if (throw) {
-      api_set_error(err, kErrorTypeValidation,
-                    _("Mark id must be an int or [row, col]"));
-    }
-    return NULL;
-  } else if (id.data.integer < 0) {
-    if (throw) {
-      api_set_error(err, kErrorTypeValidation, _("Mark id must be positive"));
-    }
-    return NULL;
-  } else {
-    extmark = extmark_from_id(buf,
-                              (uint64_t)ns,
-                              (uint64_t)id.data.integer);
-  }
-
-  if (!extmark) {
-    if (throw) {
-      api_set_error(err, kErrorTypeValidation, _("Mark doesn't exist"));
-    }
-    return NULL;
-  }
-  return extmark;
-}
-
 // Is the Namespace in use?
 bool ns_initialized(uint64_t ns)
 {
@@ -1584,29 +1529,29 @@ bool ns_initialized(uint64_t ns)
 /// @param[out] colnr extmark column
 ///
 /// @return true if the extmark was found, else false
-bool extmark_get_index_from_obj(buf_T *buf, Integer ns, Object obj, linenr_T
-                                *lnum, colnr_T *colnr, Error *err)
+bool extmark_get_index_from_obj(buf_T *buf, Integer ns_id, Object obj, int
+                                *row, colnr_T *col, Error *err)
 {
   // Check if it is mark id
   if (obj.type == kObjectTypeInteger) {
     Integer id = obj.data.integer;
     if (id == 0) {
-        *lnum = 1;
-        *colnr = 1;
+        *row = 0;
+        *col = 0;
         return true;
     } else if (id == -1) {
-        *lnum = MAXLNUM;
-        *colnr = MAXCOL;
+        *row = MAXLNUM;
+        *col = MAXCOL;
         return true;
     } else if (id < 0) {
       api_set_error(err, kErrorTypeValidation, _("Mark id must be positive"));
       return false;
     }
 
-    Extmark *extmark = extmark_from_id(buf, (uint64_t)ns, (uint64_t)id);
-    if (extmark) {
-      *lnum = extmark->line->lnum;
-      *colnr = extmark->col;
+    ExtmarkInfo extmark = extmark_from_id(buf, (uint64_t)ns_id, (uint64_t)id);
+    if (extmark.row >= 0) {
+      *row = extmark.row;
+      *col = extmark.col;
       return true;
     } else {
       api_set_error(err, kErrorTypeValidation, _("No mark with requested id"));
@@ -1623,10 +1568,10 @@ bool extmark_get_index_from_obj(buf_T *buf, Integer ns, Object obj, linenr_T
                     _("Position must have 2 integer elements"));
       return false;
     }
-    Integer line = pos.items[0].data.integer;
-    Integer col = pos.items[1].data.integer;
-    *lnum = (linenr_T)(line >= 0 ? line + 1 : MAXLNUM);
-    *colnr = (colnr_T)(col >= 0 ? col + 1 : MAXCOL);
+    Integer pos_row = pos.items[0].data.integer;
+    Integer pos_col = pos.items[1].data.integer;
+    *row = (int)(pos_row >= 0 ? pos_row  : MAXLNUM);
+    *col = (colnr_T)(pos_col >= 0 ? pos_col : MAXCOL);
     return true;
   } else {
     api_set_error(err, kErrorTypeValidation,
diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c
index 33ffff39f6..837fcb5cc1 100644
--- a/src/nvim/buffer.c
+++ b/src/nvim/buffer.c
@@ -81,12 +81,6 @@
 #include "nvim/os/input.h"
 #include "nvim/buffer_updates.h"
 
-typedef enum {
-  kBLSUnchanged = 0,
-  kBLSChanged = 1,
-  kBLSDeleted = 2,
-} BufhlLineStatus;
-
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "buffer.c.generated.h"
 #endif
@@ -818,7 +812,6 @@ static void free_buffer_stuff(buf_T *buf, int free_flags)
   uc_clear(&buf->b_ucmds);               // clear local user commands
   buf_delete_signs(buf, (char_u *)"*");  // delete any signs
   extmark_free_all(buf);                 // delete any extmarks
-  bufhl_clear_all(buf);                  // delete any highligts
   map_clear_int(buf, MAP_ALL_MODES, true, false);    // clear local mappings
   map_clear_int(buf, MAP_ALL_MODES, true, true);     // clear local abbrevs
   XFREE_CLEAR(buf->b_start_fenc);
@@ -5342,430 +5335,6 @@ int buf_signcols(buf_T *buf)
     return buf->b_signcols;
 }
 
-// bufhl: plugin highlights associated with a buffer
-
-/// Get reference to line in kbtree_t
-///
-/// @param b the three
-/// @param line the linenumber to lookup
-/// @param put if true, put a new line when not found
-///            if false, return NULL when not found
-BufhlLine *bufhl_tree_ref(BufhlInfo *b, linenr_T line, bool put)
-{
-  BufhlLine t = BUFHLLINE_INIT(line);
-
-  // kp_put() only works if key is absent, try get first
-  BufhlLine **pp = kb_get(bufhl, b, &t);
-  if (pp) {
-    return *pp;
-  } else if (!put) {
-    return NULL;
-  }
-
-  BufhlLine *p = xmalloc(sizeof(*p));
-  *p = (BufhlLine)BUFHLLINE_INIT(line);
-  kb_put(bufhl, b, p);
-  return p;
-}
-
-/// Adds a highlight to buffer.
-///
-/// Unlike matchaddpos() highlights follow changes to line numbering (as lines
-/// are inserted/removed above the highlighted line), like signs and marks do.
-///
-/// When called with "src_id" set to 0, a unique source id is generated and
-/// returned. Succesive calls can pass it in as "src_id" to add new highlights
-/// to the same source group. All highlights in the same group can be cleared
-/// at once. If the highlight never will be manually deleted pass in -1 for
-/// "src_id"
-///
-/// if "hl_id" or "lnum" is invalid no highlight is added, but a new src_id
-/// is still returned.
-///
-/// @param buf The 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 Id of the highlight group to use
-/// @param lnum The line to highlight
-/// @param col_start First column to highlight
-/// @param col_end The last column to highlight,
-///                or -1 to highlight to end of line
-/// @return The src_id that was used
-int bufhl_add_hl(buf_T *buf,
-                 int src_id,
-                 int hl_id,
-                 linenr_T lnum,
-                 colnr_T col_start,
-                 colnr_T col_end)
-{
-  if (src_id == 0) {
-    src_id = (int)nvim_create_namespace((String)STRING_INIT);
-  }
-  if (hl_id <= 0) {
-      // no highlight group or invalid line, just return src_id
-      return src_id;
-  }
-
-  BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, true);
-
-  BufhlItem *hlentry = kv_pushp(lineinfo->items);
-  hlentry->src_id = src_id;
-  hlentry->hl_id = hl_id;
-  hlentry->start = col_start;
-  hlentry->stop = col_end;
-
-  if (0 < lnum && lnum <= buf->b_ml.ml_line_count) {
-    redraw_buf_line_later(buf, lnum);
-  }
-  return src_id;
-}
-
-/// 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;
-
-  for (linenr_T lnum = pos_start.lnum; lnum <= pos_end.lnum; lnum ++) {
-    if (pos_start.lnum < lnum && lnum < pos_end.lnum) {
-      hl_start = offset;
-      hl_end = MAXCOL;
-    } else if (lnum == pos_start.lnum && lnum < pos_end.lnum) {
-      hl_start = pos_start.col + offset + 1;
-      hl_end = MAXCOL;
-    } else if (pos_start.lnum < lnum && lnum == pos_end.lnum) {
-      hl_start = offset;
-      hl_end = pos_end.col + offset;
-    } else if (pos_start.lnum == lnum && pos_end.lnum == lnum) {
-      hl_start = pos_start.col + offset + 1;
-      hl_end = pos_end.col + offset;
-    }
-    (void)bufhl_add_hl(buf, src_id, hl_id, lnum, hl_start, hl_end);
-  }
-}
-
-int bufhl_add_virt_text(buf_T *buf,
-                        int src_id,
-                        linenr_T lnum,
-                        VirtText virt_text)
-{
-  if (src_id == 0) {
-    src_id = (int)nvim_create_namespace((String)STRING_INIT);
-  }
-
-  BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, true);
-
-  bufhl_clear_virttext(&lineinfo->virt_text);
-  if (kv_size(virt_text) > 0) {
-    lineinfo->virt_text_src = src_id;
-    lineinfo->virt_text = virt_text;
-  } else {
-    lineinfo->virt_text_src = 0;
-    // currently not needed, but allow a future caller with
-    // 0 size and non-zero capacity
-    kv_destroy(virt_text);
-  }
-
-  if (0 < lnum && lnum <= buf->b_ml.ml_line_count) {
-    redraw_buf_line_later(buf, lnum);
-  }
-  return src_id;
-}
-
-static void bufhl_clear_virttext(VirtText *text)
-{
-  for (size_t i = 0; i < kv_size(*text); i++) {
-    xfree(kv_A(*text, i).text);
-  }
-  kv_destroy(*text);
-  *text = (VirtText)KV_INITIAL_VALUE;
-}
-
-/// Clear bufhl highlights from a given source group and range of lines.
-///
-/// @param buf The buffer to remove highlights from
-/// @param src_id highlight source group to clear, or -1 to clear all groups.
-/// @param line_start first line to clear
-/// @param line_end last line to clear or MAXLNUM to clear to end of file.
-void bufhl_clear_line_range(buf_T *buf,
-                            int src_id,
-                            linenr_T line_start,
-                            linenr_T line_end)
-{
-  // TODO(bfredl): implement kb_itr_interval to jump directly to the first line
-  kbitr_t(bufhl) itr;
-  BufhlLine *l, t = BUFHLLINE_INIT(line_start);
-  if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) {
-    kb_itr_next(bufhl, &buf->b_bufhl_info, &itr);
-  }
-  for (; kb_itr_valid(&itr); kb_itr_next(bufhl, &buf->b_bufhl_info, &itr)) {
-    l = kb_itr_key(&itr);
-    linenr_T line = l->line;
-    if (line > line_end) {
-      break;
-    }
-    if (line_start <= line) {
-      BufhlLineStatus status = bufhl_clear_line(l, src_id, line);
-      if (status != kBLSUnchanged) {
-        redraw_buf_line_later(buf, line);
-      }
-      if (status == kBLSDeleted) {
-        kb_del_itr(bufhl, &buf->b_bufhl_info, &itr);
-        xfree(l);
-      }
-    }
-  }
-}
-
-/// Clear bufhl highlights from a given source group and given line
-///
-/// @param bufhl_info The highlight info for the buffer
-/// @param src_id Highlight source group to clear, or -1 to clear all groups.
-/// @param lnum Linenr where the highlight should be cleared
-static BufhlLineStatus bufhl_clear_line(BufhlLine *lineinfo, int src_id,
-                                        linenr_T lnum)
-{
-  BufhlLineStatus changed = kBLSUnchanged;
-  size_t oldsize = kv_size(lineinfo->items);
-  if (src_id < 0) {
-    kv_size(lineinfo->items) = 0;
-  } else {
-    size_t newidx = 0;
-    for (size_t i = 0; i < kv_size(lineinfo->items); i++) {
-      if (kv_A(lineinfo->items, i).src_id != src_id) {
-        if (i != newidx) {
-          kv_A(lineinfo->items, newidx) = kv_A(lineinfo->items, i);
-        }
-        newidx++;
-      }
-    }
-    kv_size(lineinfo->items) = newidx;
-  }
-  if (kv_size(lineinfo->items) != oldsize) {
-    changed = kBLSChanged;
-  }
-
-  if (kv_size(lineinfo->virt_text) != 0
-      && (src_id < 0 || src_id == lineinfo->virt_text_src)) {
-    bufhl_clear_virttext(&lineinfo->virt_text);
-    lineinfo->virt_text_src = 0;
-    changed = kBLSChanged;
-  }
-
-  if (kv_size(lineinfo->items) == 0 && kv_size(lineinfo->virt_text) == 0) {
-    kv_destroy(lineinfo->items);
-    return kBLSDeleted;
-  }
-  return changed;
-}
-
-
-/// Remove all highlights and free the highlight data
-void bufhl_clear_all(buf_T *buf)
-{
-  bufhl_clear_line_range(buf, -1, 1, MAXLNUM);
-  kb_destroy(bufhl, (&buf->b_bufhl_info));
-  kb_init(&buf->b_bufhl_info);
-  kv_destroy(buf->b_bufhl_move_space);
-  kv_init(buf->b_bufhl_move_space);
-}
-
-/// Adjust a placed highlight for inserted/deleted lines.
-void bufhl_mark_adjust(buf_T* buf,
-                       linenr_T line1,
-                       linenr_T line2,
-                       long amount,
-                       long amount_after,
-                       bool end_temp)
-{
-  kbitr_t(bufhl) itr;
-  BufhlLine *l, t = BUFHLLINE_INIT(line1);
-  if (end_temp && amount < 0) {
-    // Move all items from b_bufhl_move_space to the btree.
-    for (size_t i = 0; i < kv_size(buf->b_bufhl_move_space); i++) {
-      l = kv_A(buf->b_bufhl_move_space, i);
-      l->line += amount;
-      kb_put(bufhl, &buf->b_bufhl_info, l);
-    }
-    kv_size(buf->b_bufhl_move_space) = 0;
-    return;
-  }
-
-  if (!kb_itr_get(bufhl, &buf->b_bufhl_info, &t, &itr)) {
-    kb_itr_next(bufhl, &buf->b_bufhl_info, &itr);
-  }
-  for (; kb_itr_valid(&itr); kb_itr_next(bufhl, &buf->b_bufhl_info, &itr)) {
-    l = kb_itr_key(&itr);
-    if (l->line >= line1 && l->line <= line2) {
-      if (end_temp && amount > 0) {
-        kb_del_itr(bufhl, &buf->b_bufhl_info, &itr);
-        kv_push(buf->b_bufhl_move_space, l);
-      }
-      if (amount == MAXLNUM) {
-        if (bufhl_clear_line(l, -1, l->line) == kBLSDeleted) {
-          kb_del_itr(bufhl, &buf->b_bufhl_info, &itr);
-          xfree(l);
-        } else {
-          assert(false);
-        }
-      } else {
-        l->line += amount;
-      }
-    } else if (l->line > line2) {
-      if (amount_after == 0) {
-        break;
-      }
-      l->line += amount_after;
-    }
-  }
-}
-
-/// Adjust a placed highlight for column changes and joined/broken lines
-bool bufhl_mark_col_adjust(buf_T *buf,
-                           linenr_T lnum,
-                           colnr_T mincol,
-                           long lnum_amount,
-                           long col_amount)
-{
-  bool moved = false;
-  BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, false);
-  if (!lineinfo) {
-    // Old line empty, nothing to do
-    return false;
-  }
-  // Create the new line below only if needed
-  BufhlLine *lineinfo2 = NULL;
-
-  colnr_T delcol = MAXCOL;
-  if (lnum_amount == 0 && col_amount < 0) {
-    delcol = mincol+(int)col_amount;
-  }
-
-  size_t newidx = 0;
-  for (size_t i = 0; i < kv_size(lineinfo->items); i++) {
-    BufhlItem *item = &kv_A(lineinfo->items, i);
-    bool delete = false;
-    if (item->start >= mincol) {
-      moved = true;
-      item->start += (int)col_amount;
-      if (item->stop < MAXCOL) {
-        item->stop += (int)col_amount;
-      }
-      if (lnum_amount != 0) {
-        if (lineinfo2 == NULL) {
-          lineinfo2 = bufhl_tree_ref(&buf->b_bufhl_info,
-                                     lnum+lnum_amount, true);
-        }
-        kv_push(lineinfo2->items, *item);
-        delete = true;
-      }
-    } else {
-      if (item->start >= delcol) {
-        moved = true;
-        item->start = delcol;
-      }
-      if (item->stop == MAXCOL || item->stop+1 >= mincol) {
-        if (item->stop == MAXCOL) {
-          if (delcol < MAXCOL
-              && delcol > (colnr_T)STRLEN(ml_get_buf(buf, lnum, false))) {
-            delete = true;
-          }
-        } else {
-          moved = true;
-          item->stop += (int)col_amount;
-        }
-        assert(lnum_amount >= 0);
-        if (lnum_amount > 0) {
-          item->stop = MAXCOL;
-        }
-      } else if (item->stop+1 >= delcol) {
-        moved = true;
-        item->stop = delcol-1;
-      }
-      // we covered the entire range with a visual delete or something
-      if (item->stop < item->start) {
-        delete = true;
-      }
-    }
-
-    if (!delete) {
-      if (i != newidx) {
-        kv_A(lineinfo->items, newidx) = kv_A(lineinfo->items, i);
-      }
-      newidx++;
-    }
-  }
-  kv_size(lineinfo->items) = newidx;
-
-  return moved;
-}
-
-
-/// Get highlights to display at a specific line
-///
-/// @param buf The buffer handle
-/// @param lnum The line number
-/// @param[out] info The highligts for the line
-/// @return true if there was highlights to display
-bool bufhl_start_line(buf_T *buf, linenr_T lnum, BufhlLineInfo *info)
-{
-  BufhlLine *lineinfo = bufhl_tree_ref(&buf->b_bufhl_info, lnum, false);
-  if (!lineinfo) {
-    return false;
-  }
-  info->valid_to = -1;
-  info->line = lineinfo;
-  return true;
-}
-
-/// get highlighting at column col
-///
-/// It is is assumed this will be called with
-/// non-decreasing column nrs, so that it is
-/// possible to only recalculate highlights
-/// at endpoints.
-///
-/// @param info The info returned by bufhl_start_line
-/// @param col The column to get the attr for
-/// @return The highilight attr to display at the column
-int bufhl_get_attr(BufhlLineInfo *info, colnr_T col)
-{
-  if (col <= info->valid_to) {
-    return info->current;
-  }
-  int attr = 0;
-  info->valid_to = MAXCOL;
-  for (size_t i = 0; i < kv_size(info->line->items); i++) {
-    BufhlItem entry = kv_A(info->line->items, i);
-    if (entry.start <= col && col <= entry.stop) {
-      int entry_attr = syn_id2attr(entry.hl_id);
-      attr = hl_combine_attr(attr, entry_attr);
-      if (entry.stop < info->valid_to) {
-        info->valid_to = entry.stop;
-      }
-    } else if (col < entry.start && entry.start-1 < info->valid_to) {
-      info->valid_to = entry.start-1;
-    }
-  }
-  info->current = attr;
-  return attr;
-}
-
-
 /*
  * Set 'buflisted' for curbuf to "on" and trigger autocommands if it changed.
  */
diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h
index 265fc05f67..a0379740b6 100644
--- a/src/nvim/buffer_defs.h
+++ b/src/nvim/buffer_defs.h
@@ -42,6 +42,8 @@ typedef struct {
 #include "nvim/map.h"
 // for kvec
 #include "nvim/lib/kvec.h"
+// for marktree
+#include "nvim/marktree.h"
 
 #define GETFILE_SUCCESS(x)    ((x) <= 0)
 #define MODIFIABLE(buf) (buf->b_p_ma)
@@ -109,15 +111,10 @@ typedef uint16_t disptick_T;  // display tick type
 #include "nvim/syntax_defs.h"
 // for signlist_T
 #include "nvim/sign_defs.h"
-// for bufhl_*_T
-#include "nvim/bufhl_defs.h"
 
 #include "nvim/os/fs_defs.h"    // for FileID
 #include "nvim/terminal.h"      // for Terminal
 
-#include "nvim/lib/kbtree.h"
-#include "nvim/mark_extended.h"
-
 /*
  * The taggy struct is used to store the information about a :tag command.
  */
@@ -461,11 +458,15 @@ typedef TV_DICTITEM_STRUCT(sizeof("changedtick")) ChangedtickDictItem;
 
 typedef struct {
   LuaRef on_lines;
+  LuaRef on_bytes;
   LuaRef on_changedtick;
   LuaRef on_detach;
   bool utf_sizes;
 } BufUpdateCallbacks;
-#define BUF_UPDATE_CALLBACKS_INIT { LUA_NOREF, LUA_NOREF, LUA_NOREF, false }
+#define BUF_UPDATE_CALLBACKS_INIT { LUA_NOREF, LUA_NOREF, LUA_NOREF, \
+                                    LUA_NOREF, false }
+
+EXTERN int curbuf_splice_pending INIT(= 0);
 
 #define BUF_HAS_QF_ENTRY 1
 #define BUF_HAS_LL_ENTRY 2
@@ -804,13 +805,9 @@ struct file_buffer {
 
   int b_mapped_ctrl_c;          // modes where CTRL-C is mapped
 
-  BufhlInfo b_bufhl_info;       // buffer stored highlights
-
-  kvec_t(BufhlLine *) b_bufhl_move_space;  // temporary space for highlights
-
-  PMap(uint64_t) *b_extmark_ns;         // extmark namespaces
-  kbtree_t(extmarklines) b_extlines;  // extmarks
-  kvec_t(ExtmarkLine *) b_extmark_move_space;  // temp space for extmarks
+  MarkTree b_marktree[1];
+  Map(uint64_t, ExtmarkItem) *b_extmark_index;
+  Map(uint64_t, ExtmarkNs) *b_extmark_ns;         // extmark namespaces
 
   // array of channel_id:s which have asked to receive updates for this
   // buffer.
diff --git a/src/nvim/buffer_updates.c b/src/nvim/buffer_updates.c
index d12527d6ac..80780a3aa3 100644
--- a/src/nvim/buffer_updates.c
+++ b/src/nvim/buffer_updates.c
@@ -281,6 +281,54 @@ void buf_updates_send_changes(buf_T *buf,
   kv_size(buf->update_callbacks) = j;
 }
 
+void buf_updates_send_splice(buf_T *buf,
+                             linenr_T start_line, colnr_T start_col,
+                             linenr_T oldextent_line, colnr_T oldextent_col,
+                             linenr_T newextent_line, colnr_T newextent_col)
+{
+  if (!buf_updates_active(buf)) {
+    return;
+  }
+
+  // notify each of the active callbakcs
+  size_t j = 0;
+  for (size_t i = 0; i < kv_size(buf->update_callbacks); i++) {
+    BufUpdateCallbacks cb = kv_A(buf->update_callbacks, i);
+    bool keep = true;
+    if (cb.on_bytes != LUA_NOREF) {
+      Array args = ARRAY_DICT_INIT;
+      Object items[8];
+      args.size = 8;
+      args.items = items;
+
+      // the first argument is always the buffer handle
+      args.items[0] = BUFFER_OBJ(buf->handle);
+
+      // next argument is b:changedtick
+      args.items[1] = INTEGER_OBJ(buf_get_changedtick(buf));
+
+      args.items[2] = INTEGER_OBJ(start_line);
+      args.items[3] = INTEGER_OBJ(start_col);
+      args.items[4] = INTEGER_OBJ(oldextent_line);
+      args.items[5] = INTEGER_OBJ(oldextent_col);
+      args.items[6] = INTEGER_OBJ(newextent_line);
+      args.items[7] = INTEGER_OBJ(newextent_col);
+
+      textlock++;
+      Object res = executor_exec_lua_cb(cb.on_bytes, "bytes", args, true, NULL);
+      textlock--;
+
+      if (res.type == kObjectTypeBoolean && res.data.boolean == true) {
+        free_update_callbacks(cb);
+        keep = false;
+      }
+    }
+    if (keep) {
+      kv_A(buf->update_callbacks, j++) = kv_A(buf->update_callbacks, i);
+    }
+  }
+  kv_size(buf->update_callbacks) = j;
+}
 void buf_updates_changedtick(buf_T *buf)
 {
   // notify each of the active channels
diff --git a/src/nvim/bufhl_defs.h b/src/nvim/bufhl_defs.h
deleted file mode 100644
index d0fb40ab88..0000000000
--- a/src/nvim/bufhl_defs.h
+++ /dev/null
@@ -1,41 +0,0 @@
-#ifndef NVIM_BUFHL_DEFS_H
-#define NVIM_BUFHL_DEFS_H
-
-#include "nvim/pos.h"
-#include "nvim/lib/kvec.h"
-#include "nvim/lib/kbtree.h"
-
-// bufhl: buffer specific highlighting
-
-typedef struct {
-  int src_id;
-  int hl_id;  // highlight group
-  colnr_T start;  // first column to highlight
-  colnr_T stop;  // last column to highlight
-} BufhlItem;
-
-typedef struct {
-  char *text;
-  int hl_id;
-} VirtTextChunk;
-
-typedef kvec_t(VirtTextChunk) VirtText;
-
-typedef struct {
-  linenr_T line;
-  kvec_t(BufhlItem) items;
-  int virt_text_src;
-  VirtText virt_text;
-} BufhlLine;
-#define BUFHLLINE_INIT(l) { l, KV_INITIAL_VALUE, 0,  KV_INITIAL_VALUE }
-
-typedef struct {
-  BufhlLine *line;
-  int current;
-  colnr_T valid_to;
-} BufhlLineInfo;
-
-#define BUFHL_CMP(a, b) ((int)(((a)->line - (b)->line)))
-KBTREE_INIT(bufhl, BufhlLine *, BUFHL_CMP, 10)  // -V512
-typedef kbtree_t(bufhl) BufhlInfo;
-#endif  // NVIM_BUFHL_DEFS_H
diff --git a/src/nvim/change.c b/src/nvim/change.c
index 05cacaf2c2..7eb6ea7328 100644
--- a/src/nvim/change.c
+++ b/src/nvim/change.c
@@ -363,15 +363,10 @@ void changed_bytes(linenr_T lnum, colnr_T col)
 ///
 /// Like changed_bytes() but also adjust extmark for "added" bytes.
 /// When "added" is negative text was deleted.
-static void inserted_bytes(linenr_T lnum, colnr_T col, int added)
+static void inserted_bytes(linenr_T lnum, colnr_T col, int old, int new)
 {
-  if (added > 0) {
-    extmark_col_adjust(curbuf, lnum, col+1, 0, added, kExtmarkUndo);
-  } else if (added < 0) {
-    // TODO(bfredl): next revision of extmarks should handle both these
-    // with the same entry point. Also with more sane params..
-    extmark_col_adjust_delete(curbuf, lnum, col+2,
-                              col+(-added)+1, kExtmarkUndo, 0);
+  if (curbuf_splice_pending == 0) {
+    extmark_splice(curbuf, (int)lnum-1, col, 0, old, 0, new, kExtmarkUndo);
   }
 
   changed_bytes(lnum, col);
@@ -391,7 +386,10 @@ void appended_lines_mark(linenr_T lnum, long count)
   // Skip mark_adjust when adding a line after the last one, there can't
   // be marks there. But it's still needed in diff mode.
   if (lnum + count < curbuf->b_ml.ml_line_count || curwin->w_p_diff) {
-    mark_adjust(lnum + 1, (linenr_T)MAXLNUM, count, 0L, false, kExtmarkUndo);
+    mark_adjust(lnum + 1, (linenr_T)MAXLNUM, count, 0L, kExtmarkUndo);
+  } else {
+    extmark_adjust(curbuf, lnum + 1, (linenr_T)MAXLNUM, count, 0L,
+                   kExtmarkUndo);
   }
   changed_lines(lnum + 1, 0, lnum + 1, count, true);
 }
@@ -409,7 +407,7 @@ void deleted_lines(linenr_T lnum, long count)
 /// be triggered to display the cursor.
 void deleted_lines_mark(linenr_T lnum, long count)
 {
-  mark_adjust(lnum, (linenr_T)(lnum + count - 1), (long)MAXLNUM, -count, false,
+  mark_adjust(lnum, (linenr_T)(lnum + count - 1), (long)MAXLNUM, -count,
               kExtmarkUndo);
   changed_lines(lnum, 0, lnum + count, -count, true);
 }
@@ -648,7 +646,7 @@ void ins_char_bytes(char_u *buf, size_t charlen)
   ml_replace(lnum, newp, false);
 
   // mark the buffer as changed and prepare for displaying
-  inserted_bytes(lnum, (colnr_T)col, (int)(newlen - oldlen));
+  inserted_bytes(lnum, (colnr_T)col, (int)oldlen, (int)newlen);
 
   // If we're in Insert or Replace mode and 'showmatch' is set, then briefly
   // show the match for right parens and braces.
@@ -694,7 +692,7 @@ void ins_str(char_u *s)
   assert(bytes >= 0);
   memmove(newp + col + newlen, oldp + col, (size_t)bytes);
   ml_replace(lnum, newp, false);
-  inserted_bytes(lnum, col, newlen);
+  inserted_bytes(lnum, col, 0, newlen);
   curwin->w_cursor.col += newlen;
 }
 
@@ -815,7 +813,7 @@ int del_bytes(colnr_T count, bool fixpos_arg, bool use_delcombine)
   }
 
   // mark the buffer as changed and prepare for displaying
-  inserted_bytes(lnum, col, -count);
+  inserted_bytes(lnum, col, count, 0);
 
   return OK;
 }
@@ -1583,6 +1581,7 @@ int open_line(
     end_comment_pending = NUL;  // turns out there was no leader
   }
 
+  curbuf_splice_pending++;
   old_cursor = curwin->w_cursor;
   if (dir == BACKWARD) {
     curwin->w_cursor.lnum--;
@@ -1597,7 +1596,7 @@ int open_line(
     // be marks there. But still needed in diff mode.
     if (curwin->w_cursor.lnum + 1 < curbuf->b_ml.ml_line_count
         || curwin->w_p_diff) {
-      mark_adjust(curwin->w_cursor.lnum + 1, (linenr_T)MAXLNUM, 1L, 0L, false,
+      mark_adjust(curwin->w_cursor.lnum + 1, (linenr_T)MAXLNUM, 1L, 0L,
                   kExtmarkUndo);
     }
     did_append = true;
@@ -1638,7 +1637,7 @@ int open_line(
       // it.  It gets restored at the function end.
       curbuf->b_p_pi = true;
     } else {
-      (void)set_indent(newindent, SIN_INSERT);
+      (void)set_indent(newindent, SIN_INSERT|SIN_NOMARK);
     }
     less_cols -= curwin->w_cursor.col;
 
@@ -1687,12 +1686,13 @@ int open_line(
         if (flags & OPENLINE_MARKFIX) {
           mark_col_adjust(curwin->w_cursor.lnum,
                           curwin->w_cursor.col + less_cols_off,
-                          1L, (long)-less_cols, 0, kExtmarkNOOP);
+                          1L, (long)-less_cols, 0);
         }
         // Always move extmarks - Here we move only the line where the
         // cursor is, the previous mark_adjust takes care of the lines after
-        extmark_col_adjust(curbuf, lnum, mincol, 1L, (long)-less_cols,
-                           kExtmarkUndo);
+        int cols_added = mincol-1+less_cols_off-less_cols;
+        extmark_splice(curbuf, (int)lnum-1, mincol-1, 0, less_cols_off,
+                       1, cols_added, kExtmarkUndo);
       } else {
         changed_bytes(curwin->w_cursor.lnum, curwin->w_cursor.col);
       }
@@ -1704,7 +1704,10 @@ int open_line(
   }
   if (did_append) {
     changed_lines(curwin->w_cursor.lnum, 0, curwin->w_cursor.lnum, 1L, true);
+    extmark_splice(curbuf, (int)curwin->w_cursor.lnum-1,
+                   0, 0, 0, 1, 0, kExtmarkUndo);
   }
+  curbuf_splice_pending--;
 
   curwin->w_cursor.col = newcol;
   curwin->w_cursor.coladd = 0;
diff --git a/src/nvim/diff.c b/src/nvim/diff.c
index dccde01d29..c31adc01fd 100644
--- a/src/nvim/diff.c
+++ b/src/nvim/diff.c
@@ -2711,7 +2711,7 @@ void ex_diffgetput(exarg_T *eap)
 
       // Adjust marks.  This will change the following entries!
       if (added != 0) {
-        mark_adjust(lnum, lnum + count - 1, (long)MAXLNUM, (long)added, false,
+        mark_adjust(lnum, lnum + count - 1, (long)MAXLNUM, (long)added,
                     kExtmarkUndo);
         if (curwin->w_cursor.lnum >= lnum) {
           // Adjust the cursor position if it's in/after the changed
diff --git a/src/nvim/edit.c b/src/nvim/edit.c
index d59924cd08..cdb4b127da 100644
--- a/src/nvim/edit.c
+++ b/src/nvim/edit.c
@@ -1826,11 +1826,14 @@ change_indent (
 
     /* We only put back the new line up to the cursor */
     new_line[curwin->w_cursor.col] = NUL;
+    int new_col = curwin->w_cursor.col;
 
     // Put back original line
     ml_replace(curwin->w_cursor.lnum, orig_line, false);
     curwin->w_cursor.col = orig_col;
 
+    curbuf_splice_pending++;
+
     /* Backspace from cursor to start of line */
     backspace_until_column(0);
 
@@ -1838,13 +1841,16 @@ change_indent (
     ins_bytes(new_line);
 
     xfree(new_line);
-  }
 
-  // change_indent seems to bec called twice, this combination only triggers
-  // once for both calls
-  if (new_cursor_col - vcol != 0) {
-    extmark_col_adjust(curbuf, curwin->w_cursor.lnum, 0, 0, amount,
-                       kExtmarkUndo);
+    curbuf_splice_pending--;
+
+    // TODO(bfredl): test for crazy edge cases, like we stand on a TAB or
+    // something? does this even do the right text change then?
+    int delta = orig_col - new_col;
+    extmark_splice(curbuf, curwin->w_cursor.lnum-1, new_col,
+                   0, delta < 0 ? -delta : 0,
+                   0, delta > 0 ? delta : 0,
+                   kExtmarkUndo);
   }
 }
 
diff --git a/src/nvim/ex_cmds.c b/src/nvim/ex_cmds.c
index 85048427b1..53caaa6a67 100644
--- a/src/nvim/ex_cmds.c
+++ b/src/nvim/ex_cmds.c
@@ -14,6 +14,7 @@
 #include <math.h>
 
 #include "nvim/api/private/defs.h"
+#include "nvim/api/vim.h"
 #include "nvim/api/buffer.h"
 #include "nvim/log.h"
 #include "nvim/vim.h"
@@ -659,10 +660,10 @@ void ex_sort(exarg_T *eap)
   deleted = (long)(count - (lnum - eap->line2));
   if (deleted > 0) {
     mark_adjust(eap->line2 - deleted, eap->line2, (long)MAXLNUM, -deleted,
-                false, kExtmarkUndo);
+                kExtmarkUndo);
     msgmore(-deleted);
   } else if (deleted < 0) {
-    mark_adjust(eap->line2, MAXLNUM, -deleted, 0L, false, kExtmarkUndo);
+    mark_adjust(eap->line2, MAXLNUM, -deleted, 0L, kExtmarkUndo);
   }
   if (change_occurred || deleted != 0) {
     changed_lines(eap->line1, 0, eap->line2 + 1, -deleted, true);
@@ -875,12 +876,10 @@ int do_move(linenr_T line1, linenr_T line2, linenr_T dest)
    * their final destination at the new text position -- webb
    */
   last_line = curbuf->b_ml.ml_line_count;
-  mark_adjust_nofold(line1, line2, last_line - line2, 0L, true, kExtmarkNoUndo);
-  extmark_adjust(curbuf, line1, line2, last_line - line2, 0L, kExtmarkNoUndo,
-                 true);
+  mark_adjust_nofold(line1, line2, last_line - line2, 0L, kExtmarkNOOP);
   changed_lines(last_line - num_lines + 1, 0, last_line + 1, num_lines, false);
   if (dest >= line2) {
-    mark_adjust_nofold(line2 + 1, dest, -num_lines, 0L, false, kExtmarkNoUndo);
+    mark_adjust_nofold(line2 + 1, dest, -num_lines, 0L, kExtmarkNOOP);
     FOR_ALL_TAB_WINDOWS(tab, win) {
       if (win->w_buffer == curbuf) {
         foldMoveRange(&win->w_folds, line1, line2, dest);
@@ -889,8 +888,7 @@ int do_move(linenr_T line1, linenr_T line2, linenr_T dest)
     curbuf->b_op_start.lnum = dest - num_lines + 1;
     curbuf->b_op_end.lnum = dest;
   } else {
-    mark_adjust_nofold(dest + 1, line1 - 1, num_lines, 0L, false,
-                       kExtmarkNoUndo);
+    mark_adjust_nofold(dest + 1, line1 - 1, num_lines, 0L, kExtmarkNOOP);
     FOR_ALL_TAB_WINDOWS(tab, win) {
       if (win->w_buffer == curbuf) {
         foldMoveRange(&win->w_folds, dest + 1, line1 - 1, line2);
@@ -901,9 +899,15 @@ int do_move(linenr_T line1, linenr_T line2, linenr_T dest)
   }
   curbuf->b_op_start.col = curbuf->b_op_end.col = 0;
   mark_adjust_nofold(last_line - num_lines + 1, last_line,
-                     -(last_line - dest - extra), 0L, true, kExtmarkNoUndo);
+                     -(last_line - dest - extra), 0L, kExtmarkNOOP);
+
+  // extmarks are handled separately
+  int size = line2-line1+1;
+  int off = dest >= line2 ? -size : 0;
+  extmark_move_region(curbuf, line1-1, 0,
+                      line2-line1+1, 0,
+                      dest+off, 0, kExtmarkUndo);
 
-  u_extmark_move(curbuf, line1, line2, last_line, dest, num_lines, extra);
   changed_lines(last_line - num_lines + 1, 0, last_line + 1, -extra, false);
 
   // send update regarding the new lines that were added
@@ -1285,16 +1289,19 @@ static void do_filter(
 
     if (do_in) {
       if (cmdmod.keepmarks || vim_strchr(p_cpo, CPO_REMMARK) == NULL) {
+        // TODO(bfredl): Currently not active for extmarks. What would we
+        // do if columns don't match, assume added/deleted bytes at the
+        // end of each line?
         if (read_linecount >= linecount) {
           // move all marks from old lines to new lines
-          mark_adjust(line1, line2, linecount, 0L, false, kExtmarkUndo);
+          mark_adjust(line1, line2, linecount, 0L, kExtmarkNOOP);
         } else {
           // move marks from old lines to new lines, delete marks
           // that are in deleted lines
-          mark_adjust(line1, line1 + read_linecount - 1, linecount, 0L, false,
-                      kExtmarkUndo);
-          mark_adjust(line1 + read_linecount, line2, MAXLNUM, 0L, false,
-                      kExtmarkUndo);
+          mark_adjust(line1, line1 + read_linecount - 1, linecount, 0L,
+                      kExtmarkNOOP);
+          mark_adjust(line1 + read_linecount, line2, MAXLNUM, 0L,
+                      kExtmarkNOOP);
         }
       }
 
@@ -3222,186 +3229,6 @@ static char_u *sub_parse_flags(char_u *cmd, subflags_T *subflags,
   return cmd;
 }
 
-static void extmark_move_regmatch_single(lpos_T startpos,
-                                         lpos_T endpos,
-                                         linenr_T lnum,
-                                         int sublen)
-{
-  colnr_T mincol;
-  colnr_T endcol;
-  colnr_T col_amount;
-
-  mincol = startpos.col + 1;
-  endcol = endpos.col + 1;
-
-  // There are cases such as :s/^/x/ where this happens
-  // a delete is simply not required.
-  if (mincol + 1 <= endcol) {
-    extmark_col_adjust_delete(curbuf,
-                              lnum, mincol + 1, endcol, kExtmarkUndo, 0);
-  }
-
-  // Insert, sublen seems to be the value we need but + 1...
-  col_amount = sublen - 1;
-  extmark_col_adjust(curbuf, lnum, mincol, 0, col_amount, kExtmarkUndo);
-}
-
-static void extmark_move_regmatch_multi(ExtmarkSubMulti s, long i)
-{
-  colnr_T mincol;
-  mincol = s.startpos.col + 1;
-
-  linenr_T n_u_lnum = s.lnum + s.endpos.lnum - s.startpos.lnum;
-  colnr_T n_after_newline_in_pat = s.endpos.col;
-  colnr_T n_before_newline_in_pat =  mincol - s.cm_start.col;
-  long n_after_newline_in_sub;
-  if (!s.newline_in_sub) {
-    n_after_newline_in_sub = s.cm_end.col - s.cm_start.col;
-  } else {
-    n_after_newline_in_sub = s.cm_end.col;
-  }
-
-  if (s.newline_in_pat && !s.newline_in_sub) {
-    // -- Delete Pattern --
-    // 1. Move marks in the pattern
-    mincol = s.startpos.col + 1;
-    linenr_T u_lnum = n_u_lnum;
-    assert(n_u_lnum == u_lnum);
-    extmark_copy_and_place(curbuf,
-                           s.lnum, mincol,
-                           u_lnum, n_after_newline_in_pat,
-                           s.lnum, mincol,
-                           kExtmarkUndo, true, NULL);
-    // 2. Move marks on last newline
-    mincol = mincol - n_before_newline_in_pat;
-    extmark_col_adjust(curbuf,
-                       u_lnum,
-                       n_after_newline_in_pat + 1,
-                       -s.newline_in_pat,
-                       mincol - n_after_newline_in_pat,
-                       kExtmarkUndo);
-    // Take care of the lines after
-    extmark_adjust(curbuf,
-                   u_lnum,
-                   u_lnum,
-                   MAXLNUM,
-                   -s.newline_in_pat,
-                   kExtmarkUndo,
-                   false);
-    // 1. first insert the text in the substitutaion
-    extmark_col_adjust(curbuf,
-                       s.lnum,
-                       mincol + 1,
-                       s.newline_in_sub,
-                       n_after_newline_in_sub,
-                       kExtmarkUndo);
-
-  } else {
-    // The data in sub_obj is as if the substituons above had already taken
-    // place. For our extmarks they haven't as we work from the bottom of the
-    // buffer up. Readjust the data.
-    n_u_lnum = s.lnum + s.endpos.lnum - s.startpos.lnum;
-    n_u_lnum = n_u_lnum - s.lnum_added;
-
-    // adjusted = L - (i-1)N
-    // where L = lnum value, N= lnum_added and i = iteration
-    linenr_T a_l_lnum = s.cm_start.lnum - ((i -1) * s.lnum_added);
-    linenr_T a_u_lnum = a_l_lnum + s.endpos.lnum;
-    assert(s.startpos.lnum == 0);
-
-    mincol = s.startpos.col + 1;
-
-    if (!s.newline_in_pat && s.newline_in_sub) {
-      // -- Delete Pattern --
-      // 1. Move marks in the pattern
-      extmark_col_adjust_delete(curbuf,
-                                a_l_lnum,
-                                mincol + 1,
-                                s.endpos.col + 1,
-                                kExtmarkUndo,
-                                s.eol);
-
-     extmark_adjust(curbuf,
-                    a_u_lnum + 1,
-                    MAXLNUM,
-                    (long)s.newline_in_sub,
-                    0,
-                    kExtmarkUndo,
-                    false);
-     // 3. Insert
-     extmark_col_adjust(curbuf,
-                        a_l_lnum,
-                        mincol,
-                        s.newline_in_sub,
-                        (long)-mincol + 1 + n_after_newline_in_sub,
-                        kExtmarkUndo);
-    } else if (s.newline_in_pat && s.newline_in_sub) {
-      if (s.lnum_added >= 0) {
-        linenr_T u_col = n_after_newline_in_pat == 0
-                         ? 1 : n_after_newline_in_pat;
-        extmark_copy_and_place(curbuf,
-                               a_l_lnum, mincol,
-                               a_u_lnum, u_col,
-                               a_l_lnum, mincol,
-                               kExtmarkUndo, true, NULL);
-        // 2. Move marks on last newline
-        mincol = mincol - (colnr_T)n_before_newline_in_pat;
-        extmark_col_adjust(curbuf,
-                           a_u_lnum,
-                           (colnr_T)(n_after_newline_in_pat + 1),
-                           -s.newline_in_pat,
-                           mincol - n_after_newline_in_pat,
-                           kExtmarkUndo);
-         // TODO(timeyyy): nothing to do here if lnum_added = 0
-         extmark_adjust(curbuf,
-                        a_u_lnum + 1,
-                        MAXLNUM,
-                        (long)s.lnum_added,
-                        0,
-                        kExtmarkUndo,
-                        false);
-
-         extmark_col_adjust(curbuf,
-                            a_l_lnum,
-                            mincol + 1,
-                            s.newline_in_sub,
-                            (long)-mincol + n_after_newline_in_sub,
-                            kExtmarkUndo);
-      } else {
-        mincol = s.startpos.col + 1;
-        a_l_lnum = s.startpos.lnum + 1;
-        a_u_lnum = s.endpos.lnum + 1;
-        extmark_copy_and_place(curbuf,
-                               a_l_lnum, mincol,
-                               a_u_lnum, n_after_newline_in_pat,
-                               a_l_lnum, mincol,
-                               kExtmarkUndo, true, NULL);
-        // 2. Move marks on last newline
-        mincol = mincol - (colnr_T)n_before_newline_in_pat;
-        extmark_col_adjust(curbuf,
-                           a_u_lnum,
-                           (colnr_T)(n_after_newline_in_pat + 1),
-                           -s.newline_in_pat,
-                           mincol - n_after_newline_in_pat,
-                           kExtmarkUndo);
-        extmark_adjust(curbuf,
-                       a_u_lnum,
-                       a_u_lnum,
-                       MAXLNUM,
-                       s.lnum_added,
-                       kExtmarkUndo,
-                       false);
-        // 3. Insert
-        extmark_col_adjust(curbuf,
-                           a_l_lnum,
-                           mincol + 1,
-                           s.newline_in_sub,
-                           (long)-mincol + n_after_newline_in_sub,
-                           kExtmarkUndo);
-      }
-    }
-  }
-}
 
 /// Perform a substitution from line eap->line1 to line eap->line2 using the
 /// command pointed to by eap->arg which should be of the form:
@@ -3449,11 +3276,6 @@ static buf_T *do_sub(exarg_T *eap, proftime_T timeout,
   int save_ma = 0;
   int save_b_changed = curbuf->b_changed;
   bool preview = (State & CMDPREVIEW);
-  extmark_sub_multi_vec_t extmark_sub_multi = KV_INITIAL_VALUE;
-  extmark_sub_single_vec_t extmark_sub_single = KV_INITIAL_VALUE;
-  linenr_T no_of_lines_changed = 0;
-  linenr_T newline_in_pat = 0;
-  linenr_T newline_in_sub = 0;
 
   // inccommand tests fail without this check
   if (!preview) {
@@ -4010,9 +3832,11 @@ static buf_T *do_sub(exarg_T *eap, proftime_T timeout,
           goto skip;
         }
 
+
         // 3. Substitute the string. During 'inccommand' preview only do this if
         //    there is a replace pattern.
         if (!preview || has_second_delim) {
+          long lnum_start = lnum;  // save the start lnum
           save_ma = curbuf->b_p_ma;
           if (subflags.do_count) {
             // prevent accidentally changing the buffer by a function
@@ -4060,7 +3884,8 @@ static buf_T *do_sub(exarg_T *eap, proftime_T timeout,
 
           // Finally, at this point we can know where the match actually will
           // start in the new text
-          current_match.start.col = new_end - new_start;
+          int start_col = new_end - new_start;
+          current_match.start.col = start_col;
 
           (void)vim_regsub_multi(&regmatch,
                                  sub_firstlnum - regmatch.startpos[0].lnum,
@@ -4092,8 +3917,7 @@ static buf_T *do_sub(exarg_T *eap, proftime_T timeout,
                 *p1 = NUL;                            // truncate up to the CR
                 ml_append(lnum - 1, new_start,
                           (colnr_T)(p1 - new_start + 1), false);
-                mark_adjust(lnum + 1, (linenr_T)MAXLNUM, 1L, 0L, false,
-                            kExtmarkNOOP);
+                mark_adjust(lnum + 1, (linenr_T)MAXLNUM, 1L, 0L, kExtmarkNOOP);
 
                 if (subflags.do_ask) {
                   appended_lines(lnum - 1, 1L);
@@ -4117,45 +3941,21 @@ static buf_T *do_sub(exarg_T *eap, proftime_T timeout,
               p1 += (*mb_ptr2len)(p1) - 1;
             }
           }
-          current_match.end.col = STRLEN(new_start);
+          size_t new_endcol = STRLEN(new_start);
+          current_match.end.col = new_endcol;
           current_match.end.lnum = lnum;
-        }
-
-        // Adjust extmarks, by delete and then insert
-        if (!preview) {
-          newline_in_pat = (regmatch.endpos[0].lnum
-                            - regmatch.startpos[0].lnum);
-          newline_in_sub = current_match.end.lnum - current_match.start.lnum;
-          if (newline_in_pat || newline_in_sub) {
-            ExtmarkSubMulti sub_multi;
-            no_of_lines_changed = newline_in_sub - newline_in_pat;
-
-            sub_multi.newline_in_pat = newline_in_pat;
-            sub_multi.newline_in_sub = newline_in_sub;
-            sub_multi.lnum = lnum;
-            sub_multi.lnum_added = no_of_lines_changed;
-            sub_multi.cm_start = current_match.start;
-            sub_multi.cm_end = current_match.end;
-
-            sub_multi.startpos = regmatch.startpos[0];
-            sub_multi.endpos = regmatch.endpos[0];
-            sub_multi.eol = extmark_eol_col(curbuf, lnum);
-
-            kv_push(extmark_sub_multi, sub_multi);
-            // Collect information required for moving extmarks WITHOUT \n, \r
-          } else {
-            no_of_lines_changed = 0;
-
-            if (regmatch.startpos[0].col != -1) {
-              ExtmarkSubSingle sub_single;
-              sub_single.sublen = sublen;
-              sub_single.lnum = lnum;
-              sub_single.startpos = regmatch.startpos[0];
-              sub_single.endpos = regmatch.endpos[0];
 
-              kv_push(extmark_sub_single, sub_single);
+          // TODO(bfredl): adjust in preview, because decorations?
+          // this has some robustness issues, will look into later.
+          if (!preview) {
+            lpos_T start = regmatch.startpos[0], end = regmatch.endpos[0];
+            int matchcols = end.col - ((end.lnum == start.lnum)
+                                       ? start.col : 0);
+            int subcols = new_endcol - ((lnum == lnum_start) ? start_col : 0);
+            extmark_splice(curbuf, lnum_start-1, start_col,
+                           end.lnum-start.lnum, matchcols,
+                           lnum-lnum_start, subcols, kExtmarkUndo);
             }
-          }
         }
 
 
@@ -4225,7 +4025,7 @@ skip:
                 ml_delete(lnum, false);
               }
               mark_adjust(lnum, lnum + nmatch_tl - 1,
-                          (long)MAXLNUM, -nmatch_tl, false, kExtmarkNOOP);
+                          (long)MAXLNUM, -nmatch_tl, kExtmarkNOOP);
               if (subflags.do_ask) {
                 deleted_lines(lnum, nmatch_tl);
               }
@@ -4387,7 +4187,7 @@ skip:
     } else if (*p_icm != NUL &&  pat != NULL) {
       if (pre_src_id == 0) {
         // Get a unique new src_id, saved in a static
-        pre_src_id = bufhl_add_hl(NULL, 0, -1, 0, 0, 0);
+        pre_src_id = (int)nvim_create_namespace((String)STRING_INIT);
       }
       if (pre_hl_id == 0) {
         pre_hl_id = syn_check_group((char_u *)S_LEN("Substitute"));
@@ -4396,40 +4196,11 @@ skip:
       preview_buf = show_sub(eap, old_cursor, &preview_lines,
                              pre_hl_id, pre_src_id);
       if (subsize > 0) {
-        bufhl_clear_line_range(orig_buf, pre_src_id, eap->line1,
-                               kv_last(preview_lines.subresults).end.lnum);
+        extmark_clear(orig_buf, pre_src_id, eap->line1-1, 0,
+                      kv_last(preview_lines.subresults).end.lnum-1, MAXCOL);
       }
     }
   }
-  if (newline_in_pat || newline_in_sub) {
-    long n = (long)kv_size(extmark_sub_multi);
-    ExtmarkSubMulti sub_multi;
-    if (no_of_lines_changed < 0) {
-      for (i = 0; i < n; i++) {
-        sub_multi = kv_A(extmark_sub_multi, i);
-        extmark_move_regmatch_multi(sub_multi, i);
-      }
-    } else {
-      // Move extmarks in reverse order to avoid moving marks we just moved...
-      for (i = 0; i < n; i++) {
-        sub_multi = kv_Z(extmark_sub_multi, i);
-        extmark_move_regmatch_multi(sub_multi, n - i);
-      }
-    }
-    kv_destroy(extmark_sub_multi);
-  } else {
-    long n = (long)kv_size(extmark_sub_single);
-    ExtmarkSubSingle sub_single;
-    for (i = 0; i < n; i++) {
-      sub_single = kv_Z(extmark_sub_single, i);
-      extmark_move_regmatch_single(sub_single.startpos,
-                                   sub_single.endpos,
-                                   sub_single.lnum,
-                                   sub_single.sublen);
-    }
-
-    kv_destroy(extmark_sub_single);
-  }
 
   kv_destroy(preview_lines.subresults);
 
diff --git a/src/nvim/fold.c b/src/nvim/fold.c
index b193b4005c..addfab8f08 100644
--- a/src/nvim/fold.c
+++ b/src/nvim/fold.c
@@ -22,6 +22,7 @@
 #include "nvim/func_attr.h"
 #include "nvim/indent.h"
 #include "nvim/buffer_updates.h"
+#include "nvim/mark_extended.h"
 #include "nvim/mark.h"
 #include "nvim/memline.h"
 #include "nvim/memory.h"
@@ -1610,6 +1611,7 @@ static void foldAddMarker(linenr_T lnum, const char_u *marker, size_t markerlen)
   // Allocate a new line: old-line + 'cms'-start + marker + 'cms'-end
   line = ml_get(lnum);
   size_t line_len = STRLEN(line);
+  size_t added = 0;
 
   if (u_save(lnum - 1, lnum + 1) == OK) {
     // Check if the line ends with an unclosed comment
@@ -1619,12 +1621,19 @@ static void foldAddMarker(linenr_T lnum, const char_u *marker, size_t markerlen)
     // Append the marker to the end of the line
     if (p == NULL || line_is_comment) {
       STRLCPY(newline + line_len, marker, markerlen + 1);
+      added = markerlen;
     } else {
       STRCPY(newline + line_len, cms);
       memcpy(newline + line_len + (p - cms), marker, markerlen);
       STRCPY(newline + line_len + (p - cms) + markerlen, p + 2);
+      added = markerlen + STRLEN(cms)-2;
     }
     ml_replace(lnum, newline, false);
+    if (added) {
+      extmark_splice(curbuf, (int)lnum-1, (int)line_len,
+                     0, 0,
+                     0, (int)added, kExtmarkUndo);
+    }
   }
 }
 
@@ -1692,6 +1701,9 @@ static void foldDelMarker(linenr_T lnum, char_u *marker, size_t markerlen)
       memcpy(newline, line, (size_t)(p - line));
       STRCPY(newline + (p - line), p + len);
       ml_replace(lnum, newline, false);
+      extmark_splice(curbuf, (int)lnum-1, (int)(p - line),
+                     0, (int)len,
+                     0, 0, kExtmarkUndo);
     }
     break;
   }
diff --git a/src/nvim/indent.c b/src/nvim/indent.c
index efbfea33aa..2c5fdd8ea6 100644
--- a/src/nvim/indent.c
+++ b/src/nvim/indent.c
@@ -13,6 +13,7 @@
 #include "nvim/charset.h"
 #include "nvim/cursor.h"
 #include "nvim/mark.h"
+#include "nvim/mark_extended.h"
 #include "nvim/memline.h"
 #include "nvim/memory.h"
 #include "nvim/misc1.h"
@@ -88,6 +89,7 @@ int get_indent_str(char_u *ptr, int ts, int list)
 //  SIN_CHANGED:    call changed_bytes() if the line was changed.
 //  SIN_INSERT: insert the indent in front of the line.
 //  SIN_UNDO:   save line for undo before changing it.
+//  SIN_NOMARK: don't move extmarks (because just after ml_append or something)
 //  @param size measured in spaces
 // Returns true if the line was changed.
 int set_indent(int size, int flags)
@@ -205,6 +207,7 @@ int set_indent(int size, int flags)
   // If 'preserveindent' and 'expandtab' are both set keep the original
   // characters and allocate accordingly.  We will fill the rest with spaces
   // after the if (!curbuf->b_p_et) below.
+  int skipcols = 0;  // number of columns (in bytes) that were presved
   if (orig_char_len != -1) {
     int newline_size;  // = orig_char_len + size - ind_done + line_len
     STRICT_ADD(orig_char_len, size, &newline_size, int);
@@ -219,6 +222,7 @@ int set_indent(int size, int flags)
     ind_len = orig_char_len + todo;
     p = oldline;
     s = newline;
+    skipcols = orig_char_len;
 
     while (orig_char_len > 0) {
       *s++ = *p++;
@@ -263,6 +267,7 @@ int set_indent(int size, int flags)
           ind_done++;
         }
         *s++ = *p++;
+        skipcols++;
       }
 
       // Fill to next tabstop with a tab, if possible.
@@ -290,6 +295,13 @@ int set_indent(int size, int flags)
   // Replace the line (unless undo fails).
   if (!(flags & SIN_UNDO) || (u_savesub(curwin->w_cursor.lnum) == OK)) {
     ml_replace(curwin->w_cursor.lnum, newline, false);
+    if (!(flags & SIN_NOMARK)) {
+      extmark_splice(curbuf,
+                     (int)curwin->w_cursor.lnum-1, skipcols,
+                     0, (int)(p-oldline) - skipcols,
+                     0, (int)(s-newline) - skipcols,
+                     kExtmarkUndo);
+    }
 
     if (flags & SIN_CHANGED) {
       changed_bytes(curwin->w_cursor.lnum, 0);
diff --git a/src/nvim/indent.h b/src/nvim/indent.h
index 6552157d20..f96732bf1c 100644
--- a/src/nvim/indent.h
+++ b/src/nvim/indent.h
@@ -3,10 +3,11 @@
 
 #include "nvim/vim.h"
 
-/* flags for set_indent() */
-#define SIN_CHANGED     1       /* call changed_bytes() when line changed */
-#define SIN_INSERT      2       /* insert indent before existing text */
-#define SIN_UNDO        4       /* save line for undo before changing it */
+// flags for set_indent()
+#define SIN_CHANGED     1       // call changed_bytes() when line changed
+#define SIN_INSERT      2       // insert indent before existing text
+#define SIN_UNDO        4       // save line for undo before changing it
+#define SIN_NOMARK      8       // don't adjust extmarks
 
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "indent.h.generated.h"
diff --git a/src/nvim/map.c b/src/nvim/map.c
index cdade5ee71..cba39f24b3 100644
--- a/src/nvim/map.c
+++ b/src/nvim/map.c
@@ -44,7 +44,8 @@
 
 #define INITIALIZER(T, U) T##_##U##_initializer
 #define INITIALIZER_DECLARE(T, U, ...) const U INITIALIZER(T, U) = __VA_ARGS__
-#define DEFAULT_INITIALIZER {0}
+#define DEFAULT_INITIALIZER { 0 }
+#define SSIZE_INITIALIZER { -1 }
 
 #define MAP_IMPL(T, U, ...) \
   INITIALIZER_DECLARE(T, U, __VA_ARGS__); \
@@ -178,10 +179,16 @@ MAP_IMPL(int, int, DEFAULT_INITIALIZER)
 MAP_IMPL(cstr_t, ptr_t, DEFAULT_INITIALIZER)
 MAP_IMPL(ptr_t, ptr_t, DEFAULT_INITIALIZER)
 MAP_IMPL(uint64_t, ptr_t, DEFAULT_INITIALIZER)
+MAP_IMPL(uint64_t, ssize_t, SSIZE_INITIALIZER)
+MAP_IMPL(uint64_t, uint64_t, DEFAULT_INITIALIZER)
+#define EXTMARK_NS_INITIALIZER { 0, 0 }
+MAP_IMPL(uint64_t, ExtmarkNs, EXTMARK_NS_INITIALIZER)
+#define KVEC_INITIALIZER { .size = 0, .capacity = 0, .items = NULL }
+#define EXTMARK_ITEM_INITIALIZER { 0, 0, 0, KVEC_INITIALIZER }
+MAP_IMPL(uint64_t, ExtmarkItem, EXTMARK_ITEM_INITIALIZER)
 MAP_IMPL(handle_T, ptr_t, DEFAULT_INITIALIZER)
 #define MSGPACK_HANDLER_INITIALIZER { .fn = NULL, .fast = false }
 MAP_IMPL(String, MsgpackRpcRequestHandler, MSGPACK_HANDLER_INITIALIZER)
-#define KVEC_INITIALIZER { .size = 0, .capacity = 0, .items = NULL }
 MAP_IMPL(HlEntry, int, DEFAULT_INITIALIZER)
 MAP_IMPL(String, handle_T, 0)
 
diff --git a/src/nvim/map.h b/src/nvim/map.h
index fec91ac0c2..761938776d 100644
--- a/src/nvim/map.h
+++ b/src/nvim/map.h
@@ -4,9 +4,9 @@
 #include <stdbool.h>
 
 #include "nvim/map_defs.h"
+#include "nvim/mark_extended_defs.h"
 #include "nvim/api/private/defs.h"
 #include "nvim/api/private/dispatch.h"
-#include "nvim/bufhl_defs.h"
 #include "nvim/highlight_defs.h"
 
 #if defined(__NetBSD__)
@@ -38,6 +38,18 @@ MAP_DECLS(int, int)
 MAP_DECLS(cstr_t, ptr_t)
 MAP_DECLS(ptr_t, ptr_t)
 MAP_DECLS(uint64_t, ptr_t)
+MAP_DECLS(uint64_t, ssize_t)
+MAP_DECLS(uint64_t, uint64_t)
+
+// NB: this is the only way to define a struct both containing and contained
+// in a map...
+typedef struct ExtmarkNs {  // For namespacing extmarks
+  Map(uint64_t, uint64_t) *map;  // For fast lookup
+  uint64_t free_id;         // For automatically assigning id's
+} ExtmarkNs;
+
+MAP_DECLS(uint64_t, ExtmarkNs)
+MAP_DECLS(uint64_t, ExtmarkItem)
 MAP_DECLS(handle_T, ptr_t)
 MAP_DECLS(String, MsgpackRpcRequestHandler)
 MAP_DECLS(HlEntry, int)
diff --git a/src/nvim/mark.c b/src/nvim/mark.c
index 8b2f342142..4a7452493a 100644
--- a/src/nvim/mark.c
+++ b/src/nvim/mark.c
@@ -20,6 +20,7 @@
 #include "nvim/ex_cmds.h"
 #include "nvim/fileio.h"
 #include "nvim/fold.h"
+#include "nvim/mark_extended.h"
 #include "nvim/mbyte.h"
 #include "nvim/memline.h"
 #include "nvim/memory.h"
@@ -915,10 +916,9 @@ void mark_adjust(linenr_T line1,
                  linenr_T line2,
                  long amount,
                  long amount_after,
-                 bool end_temp,
                  ExtmarkOp op)
 {
-  mark_adjust_internal(line1, line2, amount, amount_after, true, end_temp, op);
+  mark_adjust_internal(line1, line2, amount, amount_after, true, op);
 }
 
 // mark_adjust_nofold() does the same as mark_adjust() but without adjusting
@@ -927,15 +927,15 @@ void mark_adjust(linenr_T line1,
 // calling foldMarkAdjust() with arguments line1, line2, amount, amount_after,
 // for an example of why this may be necessary, see do_move().
 void mark_adjust_nofold(linenr_T line1, linenr_T line2, long amount,
-                        long amount_after, bool end_temp,
+                        long amount_after,
                         ExtmarkOp op)
 {
-  mark_adjust_internal(line1, line2, amount, amount_after, false, end_temp, op);
+  mark_adjust_internal(line1, line2, amount, amount_after, false, op);
 }
 
 static void mark_adjust_internal(linenr_T line1, linenr_T line2,
                                  long amount, long amount_after,
-                                 bool adjust_folds, bool end_temp,
+                                 bool adjust_folds,
                                  ExtmarkOp op)
 {
   int i;
@@ -991,9 +991,8 @@ static void mark_adjust_internal(linenr_T line1, linenr_T line2,
     }
 
     sign_mark_adjust(line1, line2, amount, amount_after);
-    bufhl_mark_adjust(curbuf, line1, line2, amount, amount_after, end_temp);
     if (op != kExtmarkNOOP) {
-      extmark_adjust(curbuf, line1, line2, amount, amount_after, op, end_temp);
+      extmark_adjust(curbuf, line1, line2, amount, amount_after, op);
     }
   }
 
@@ -1106,7 +1105,7 @@ static void mark_adjust_internal(linenr_T line1, linenr_T line2,
 // cursor is inside them.
 void mark_col_adjust(
     linenr_T lnum, colnr_T mincol, long lnum_amount, long col_amount,
-    int spaces_removed,  ExtmarkOp op)
+    int spaces_removed)
 {
   int i;
   int fnum = curbuf->b_fnum;
@@ -1126,13 +1125,6 @@ void mark_col_adjust(
       col_adjust(&(namedfm[i].fmark.mark));
   }
 
-  // Extmarks
-  if (op != kExtmarkNOOP) {
-    // TODO(timeyyy): consider spaces_removed? (behave like a delete)
-    extmark_col_adjust(curbuf, lnum, mincol, lnum_amount, col_amount,
-                       kExtmarkUndo);
-  }
-
   /* last Insert position */
   col_adjust(&(curbuf->b_last_insert.mark));
 
diff --git a/src/nvim/mark.h b/src/nvim/mark.h
index ed4e47907b..d8370c367a 100644
--- a/src/nvim/mark.h
+++ b/src/nvim/mark.h
@@ -6,6 +6,7 @@
 #include "nvim/buffer_defs.h"
 #include "nvim/func_attr.h"
 #include "nvim/mark_defs.h"
+#include "nvim/mark_extended_defs.h"
 #include "nvim/memory.h"
 #include "nvim/pos.h"
 #include "nvim/os/time.h"
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;
 }
-
-
diff --git a/src/nvim/mark_extended.h b/src/nvim/mark_extended.h
index ee1da26875..f809148d9b 100644
--- a/src/nvim/mark_extended.h
+++ b/src/nvim/mark_extended.h
@@ -1,236 +1,57 @@
 #ifndef NVIM_MARK_EXTENDED_H
 #define NVIM_MARK_EXTENDED_H
 
+#include "nvim/buffer_defs.h"
 #include "nvim/mark_extended_defs.h"
-#include "nvim/buffer_defs.h"  // for buf_T
+#include "nvim/marktree.h"
 
+EXTERN int extmark_splice_pending INIT(= 0);
 
-// Macro Documentation: FOR_ALL_?
-// Search exclusively using the range values given.
-// Use MAXCOL/MAXLNUM for the start and end of the line/col.
-// The ns parameter: Unless otherwise stated, this is only a starting point
-//    for the btree to searched in, the results being itterated over will
-//    still contain extmarks from other namespaces.
-
-// see FOR_ALL_? for documentation
-#define FOR_ALL_EXTMARKLINES(buf, l_lnum, u_lnum, code)\
-  kbitr_t(extmarklines) itr;\
-  ExtmarkLine t;\
-  t.lnum = l_lnum;\
-  if (!kb_itr_get(extmarklines, &buf->b_extlines, &t, &itr)) { \
-    kb_itr_next(extmarklines, &buf->b_extlines, &itr);\
-  }\
-  ExtmarkLine *extmarkline;\
-  for (; kb_itr_valid(&itr); kb_itr_next(extmarklines, \
-                                         &buf->b_extlines, &itr)) { \
-    extmarkline = kb_itr_key(&itr);\
-    if (extmarkline->lnum > u_lnum) { \
-      break;\
-    }\
-      code;\
-    }
-
-// see FOR_ALL_? for documentation
-#define FOR_ALL_EXTMARKLINES_PREV(buf, l_lnum, u_lnum, code)\
-  kbitr_t(extmarklines) itr;\
-  ExtmarkLine t;\
-  t.lnum = u_lnum;\
-  if (!kb_itr_get(extmarklines, &buf->b_extlines, &t, &itr)) { \
-    kb_itr_prev(extmarklines, &buf->b_extlines, &itr);\
-  }\
-  ExtmarkLine *extmarkline;\
-  for (; kb_itr_valid(&itr); kb_itr_prev(extmarklines, \
-                                         &buf->b_extlines, &itr)) { \
-    extmarkline = kb_itr_key(&itr);\
-    if (extmarkline->lnum < l_lnum) { \
-      break;\
-    }\
-    code;\
-  }
-
-// see FOR_ALL_? for documentation
-#define FOR_ALL_EXTMARKS(buf, ns, l_lnum, l_col, u_lnum, u_col, code)\
-  kbitr_t(markitems) mitr;\
-  Extmark mt;\
-  mt.ns_id = ns;\
-  mt.mark_id = 0;\
-  mt.line = NULL;\
-  FOR_ALL_EXTMARKLINES(buf, l_lnum, u_lnum, { \
-    mt.col = (extmarkline->lnum != l_lnum) ? MINCOL : l_col;\
-    if (!kb_itr_get(markitems, &extmarkline->items, mt, &mitr)) { \
-        kb_itr_next(markitems, &extmarkline->items, &mitr);\
-    } \
-    Extmark *extmark;\
-    for (; \
-         kb_itr_valid(&mitr); \
-         kb_itr_next(markitems, &extmarkline->items, &mitr)) { \
-      extmark = &kb_itr_key(&mitr);\
-      if (extmark->line->lnum == u_lnum \
-          && extmark->col > u_col) { \
-        break;\
-      }\
-      code;\
-    }\
-  })
-
-
-// see FOR_ALL_? for documentation
-#define FOR_ALL_EXTMARKS_PREV(buf, ns, l_lnum, l_col, u_lnum, u_col, code)\
-  kbitr_t(markitems) mitr;\
-  Extmark mt;\
-  mt.mark_id = sizeof(uint64_t);\
-  mt.ns_id = ns;\
-  FOR_ALL_EXTMARKLINES_PREV(buf, l_lnum, u_lnum, { \
-    mt.col = (extmarkline->lnum != u_lnum) ? MAXCOL : u_col;\
-    if (!kb_itr_get(markitems, &extmarkline->items, mt, &mitr)) { \
-        kb_itr_prev(markitems, &extmarkline->items, &mitr);\
-    } \
-    Extmark *extmark;\
-    for (; \
-         kb_itr_valid(&mitr); \
-         kb_itr_prev(markitems, &extmarkline->items, &mitr)) { \
-      extmark = &kb_itr_key(&mitr);\
-      if (extmark->line->lnum == l_lnum \
-          && extmark->col < l_col) { \
-          break;\
-      }\
-      code;\
-    }\
-  })
-
-
-#define FOR_ALL_EXTMARKS_IN_LINE(items, l_col, u_col, code)\
-  kbitr_t(markitems) mitr;\
-  Extmark mt;\
-  mt.ns_id = 0;\
-  mt.mark_id = 0;\
-  mt.line = NULL;\
-  mt.col = l_col;\
-  colnr_T extmarkline_u_col = u_col;\
-  if (!kb_itr_get(markitems, &items, mt, &mitr)) { \
-    kb_itr_next(markitems, &items, &mitr);\
-  } \
-  Extmark *extmark;\
-  for (; kb_itr_valid(&mitr); kb_itr_next(markitems, &items, &mitr)) { \
-    extmark = &kb_itr_key(&mitr);\
-    if (extmark->col > extmarkline_u_col) { \
-      break;\
-    }\
-    code;\
-  }
-
-
-typedef struct ExtmarkNs {  // For namespacing extmarks
-  PMap(uint64_t) *map;      // For fast lookup
-  uint64_t free_id;         // For automatically assigning id's
-} ExtmarkNs;
-
-
-typedef kvec_t(Extmark *) ExtmarkArray;
-
-
-// Undo/redo extmarks
-
-typedef enum {
-  kExtmarkNOOP,        // Extmarks shouldn't be moved
-  kExtmarkUndo,        // Operation should be reversable/undoable
-  kExtmarkNoUndo,      // Operation should not be reversable
-  kExtmarkUndoNoRedo,  // Operation should be undoable, but not redoable
-} ExtmarkOp;
-
+typedef struct
+{
+  uint64_t ns_id;
+  uint64_t mark_id;
+  int row;
+  colnr_T col;
+} ExtmarkInfo;
 
-// adjust line numbers only, corresponding to mark_adjust call
-typedef struct {
-  linenr_T line1;
-  linenr_T line2;
-  long amount;
-  long amount_after;
-} Adjust;
+typedef kvec_t(ExtmarkInfo) ExtmarkArray;
 
-// adjust columns after split/join line, like mark_col_adjust
-typedef struct {
-  linenr_T lnum;
-  colnr_T mincol;
-  long col_amount;
-  long lnum_amount;
-} ColAdjust;
 
 // delete the columns between mincol and endcol
 typedef struct {
-    linenr_T lnum;
-    colnr_T mincol;
-    colnr_T endcol;
-    int eol;
-} ColAdjustDelete;
-
-// adjust linenumbers after :move operation
+  int start_row;
+  colnr_T start_col;
+  int oldextent_row;
+  colnr_T oldextent_col;
+  int newextent_row;
+  colnr_T newextent_col;
+} ExtmarkSplice;
+
+// adjust marks after :move operation
 typedef struct {
-  linenr_T line1;
-  linenr_T line2;
-  linenr_T last_line;
-  linenr_T dest;
-  linenr_T num_lines;
-  linenr_T extra;
-} AdjustMove;
-
-// TODO(bfredl): reconsider if we really should track mark creation/updating
-// itself, these are not really "edit" operation.
-// extmark was created
-typedef struct {
-  uint64_t ns_id;
-  uint64_t mark_id;
-  linenr_T lnum;
-  colnr_T col;
-} ExtmarkSet;
+  int start_row;
+  int start_col;
+  int extent_row;
+  int extent_col;
+  int new_row;
+  int new_col;
+} ExtmarkMove;
 
 // extmark was updated
 typedef struct {
-  uint64_t ns_id;
-  uint64_t mark_id;
-  linenr_T old_lnum;
+  uint64_t mark;  // raw mark id of the marktree
+  int old_row;
   colnr_T old_col;
-  linenr_T lnum;
-  colnr_T col;
-} ExtmarkUpdate;
-
-// copied mark before deletion (as operation is destructive)
-typedef struct {
-  uint64_t ns_id;
-  uint64_t mark_id;
-  linenr_T lnum;
+  int row;
   colnr_T col;
-} ExtmarkCopy;
-
-// also used as part of :move operation? probably can be simplified to one
-// event.
-typedef struct {
-  linenr_T l_lnum;
-  colnr_T l_col;
-  linenr_T u_lnum;
-  colnr_T u_col;
-  linenr_T p_lnum;
-  colnr_T p_col;
-} ExtmarkCopyPlace;
-
-// extmark was cleared.
-// TODO(bfredl): same reconsideration as for ExtmarkSet/ExtmarkUpdate
-typedef struct {
-  uint64_t ns_id;
-  linenr_T l_lnum;
-  linenr_T u_lnum;
-} ExtmarkClear;
-
+} ExtmarkSavePos;
 
 typedef enum {
-  kLineAdjust,
-  kColAdjust,
-  kColAdjustDelete,
-  kAdjustMove,
-  kExtmarkSet,
-  kExtmarkDel,
+  kExtmarkSplice,
+  kExtmarkMove,
   kExtmarkUpdate,
-  kExtmarkCopy,
-  kExtmarkCopyPlace,
+  kExtmarkSavePos,
   kExtmarkClear,
 } UndoObjectType;
 
@@ -238,42 +59,32 @@ typedef enum {
 struct undo_object {
   UndoObjectType type;
   union {
-    Adjust adjust;
-    ColAdjust col_adjust;
-    ColAdjustDelete col_adjust_delete;
-    AdjustMove move;
-    ExtmarkSet set;
-    ExtmarkUpdate update;
-    ExtmarkCopy copy;
-    ExtmarkCopyPlace copy_place;
-    ExtmarkClear clear;
+    ExtmarkSplice splice;
+    ExtmarkMove move;
+    ExtmarkSavePos savepos;
   } data;
 };
 
 
-// For doing move of extmarks in substitutions
 typedef struct {
-  lpos_T startpos;
-  lpos_T endpos;
-  linenr_T lnum;
-  int sublen;
-} ExtmarkSubSingle;
+  int start_row;
+  int start_col;
+  int end_row;
+  int end_col;
+  int attr_id;
+  VirtText *virt_text;
+} HlRange;
 
-// For doing move of extmarks in substitutions
 typedef struct {
-  lpos_T startpos;
-  lpos_T endpos;
-  linenr_T lnum;
-  linenr_T newline_in_pat;
-  linenr_T newline_in_sub;
-  linenr_T lnum_added;
-  lpos_T cm_start;  // start of the match
-  lpos_T cm_end;    // end of the match
-  int eol;    // end of the match
-} ExtmarkSubMulti;
+  MarkTreeIter itr[1];
+  kvec_t(HlRange) active;
+  int top_row;
+  int row;
+  int col_until;
+  int current;
+  VirtText *virt_text;
+} DecorationState;
 
-typedef kvec_t(ExtmarkSubSingle) extmark_sub_single_vec_t;
-typedef kvec_t(ExtmarkSubMulti) extmark_sub_multi_vec_t;
 
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "mark_extended.h.generated.h"
diff --git a/src/nvim/mark_extended_defs.h b/src/nvim/mark_extended_defs.h
index 565c599d06..439f7f0b36 100644
--- a/src/nvim/mark_extended_defs.h
+++ b/src/nvim/mark_extended_defs.h
@@ -2,53 +2,36 @@
 #define NVIM_MARK_EXTENDED_DEFS_H
 
 #include "nvim/pos.h"  // for colnr_T
-#include "nvim/map.h"  // for uint64_t
-#include "nvim/lib/kbtree.h"
 #include "nvim/lib/kvec.h"
 
-struct ExtmarkLine;
+typedef struct {
+  char *text;
+  int hl_id;
+} VirtTextChunk;
 
-typedef struct Extmark
+typedef kvec_t(VirtTextChunk) VirtText;
+#define VIRTTEXT_EMPTY ((VirtText)KV_INITIAL_VALUE)
+
+typedef struct
 {
   uint64_t ns_id;
   uint64_t mark_id;
-  struct ExtmarkLine *line;
-  colnr_T col;
-} Extmark;
-
-
-// We only need to compare columns as rows are stored in a different tree.
-// Marks are ordered by: position, namespace, mark_id
-// This improves moving marks but slows down all other use cases (searches)
-static inline int extmark_cmp(Extmark a, Extmark b)
-{
-  int cmp = kb_generic_cmp(a.col, b.col);
-  if (cmp != 0) {
-    return cmp;
-  }
-  cmp = kb_generic_cmp(a.ns_id, b.ns_id);
-  if (cmp != 0) {
-    return cmp;
-  }
-  return kb_generic_cmp(a.mark_id, b.mark_id);
-}
-
-
-#define markitems_cmp(a, b) (extmark_cmp((a), (b)))
-KBTREE_INIT(markitems, Extmark, markitems_cmp, 10)
-
-typedef struct ExtmarkLine
-{
-  linenr_T lnum;
-  kbtree_t(markitems) items;
-} ExtmarkLine;
-
-#define EXTMARKLINE_CMP(a, b) (kb_generic_cmp((a)->lnum, (b)->lnum))
-KBTREE_INIT(extmarklines, ExtmarkLine *, EXTMARKLINE_CMP, 10)
-
+  int hl_id;  // highlight group
+  // TODO(bfredl): virt_text is pretty larger than the rest,
+  // pointer indirection?
+  VirtText virt_text;
+} ExtmarkItem;
 
 typedef struct undo_object ExtmarkUndoObject;
 typedef kvec_t(ExtmarkUndoObject) extmark_undo_vec_t;
 
+// Undo/redo extmarks
+
+typedef enum {
+  kExtmarkNOOP,        // Extmarks shouldn't be moved
+  kExtmarkUndo,        // Operation should be reversable/undoable
+  kExtmarkNoUndo,      // Operation should not be reversable
+  kExtmarkUndoNoRedo,  // Operation should be undoable, but not redoable
+} ExtmarkOp;
 
 #endif  // NVIM_MARK_EXTENDED_DEFS_H
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index 6ad283f5dc..52e602cd94 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -1095,6 +1095,7 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
 
 void marktree_check(MarkTree *b)
 {
+#ifndef NDEBUG
   if (b->root == NULL) {
     assert(b->n_keys == 0);
     assert(b->n_nodes == 0);
@@ -1107,9 +1108,15 @@ void marktree_check(MarkTree *b)
   size_t nkeys = check_node(b, b->root, &dummy, &last_right);
   assert(b->n_keys == nkeys);
   assert(b->n_keys == map_size(b->id2node));
+#else
+  // Do nothing, as assertions are required
+  (void)b;
+#endif
 }
 
-size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_right)
+#ifndef NDEBUG
+static size_t check_node(MarkTree *b, mtnode_t *x,
+                         mtpos_t *last, bool *last_right)
 {
   assert(x->n <= 2 * T - 1);
   // TODO(bfredl): too strict if checking "in repair" post-delete tree.
@@ -1153,6 +1160,7 @@ size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_right)
   }
   return n_keys;
 }
+#endif
 
 char *mt_inspect_rec(MarkTree *b)
 {
diff --git a/src/nvim/ops.c b/src/nvim/ops.c
index 6a621cdaa6..5da81dbff6 100644
--- a/src/nvim/ops.c
+++ b/src/nvim/ops.c
@@ -31,6 +31,7 @@
 #include "nvim/indent.h"
 #include "nvim/log.h"
 #include "nvim/mark.h"
+#include "nvim/mark_extended.h"
 #include "nvim/mbyte.h"
 #include "nvim/memline.h"
 #include "nvim/memory.h"
@@ -307,15 +308,6 @@ void shift_line(
     change_indent(INDENT_SET, count, false, NUL, call_changed_bytes);
   } else {
     (void)set_indent(count, call_changed_bytes ? SIN_CHANGED : 0);
-
-    colnr_T mincol = (curwin->w_cursor.col + 1) -p_sw;
-    colnr_T col_amount = left ? -p_sw : p_sw;
-    extmark_col_adjust(curbuf,
-                       curwin->w_cursor.lnum,
-                       mincol,
-                       0,
-                       col_amount,
-                       kExtmarkUndo);
   }
 }
 
@@ -352,6 +344,8 @@ static void shift_block(oparg_T *oap, int amount)
 
   char_u *const oldp = get_cursor_line_ptr();
 
+  int startcol, oldlen, newlen;
+
   if (!left) {
     /*
      *  1. Get start vcol
@@ -361,6 +355,7 @@ static void shift_block(oparg_T *oap, int amount)
      */
     total += bd.pre_whitesp;    // all virtual WS up to & incl a split TAB
     colnr_T ws_vcol = bd.start_vcol - bd.pre_whitesp;
+    char_u * old_textstart = bd.textstart;
     if (bd.startspaces) {
       if (has_mbyte) {
         if ((*mb_ptr2len)(bd.textstart) == 1) {
@@ -387,14 +382,19 @@ static void shift_block(oparg_T *oap, int amount)
       j = ((ws_vcol % p_ts) + total) % p_ts;       /* number of spp */
     else
       j = total;
-    /* if we're splitting a TAB, allow for it */
-    bd.textcol -= bd.pre_whitesp_c - (bd.startspaces != 0);
+
+    // if we're splitting a TAB, allow for it
+    int col_pre = bd.pre_whitesp_c - (bd.startspaces != 0);
+    bd.textcol -= col_pre;
     const int len = (int)STRLEN(bd.textstart) + 1;
     int col = bd.textcol + i +j + len;
     assert(col >= 0);
     newp = (char_u *)xmalloc((size_t)col);
     memset(newp, NUL, (size_t)col);
     memmove(newp, oldp, (size_t)bd.textcol);
+    startcol = bd.textcol;
+    oldlen = (int)(bd.textstart-old_textstart) + col_pre;
+    newlen = i+j;
     memset(newp + bd.textcol, TAB, (size_t)i);
     memset(newp + bd.textcol + i, ' ', (size_t)j);
     /* the end */
@@ -478,7 +478,10 @@ static void shift_block(oparg_T *oap, int amount)
     // - the rest of the line, pointed to by non_white.
     new_line_len = verbatim_diff + fill + STRLEN(non_white) + 1;
 
-    newp = (char_u *) xmalloc(new_line_len);
+    newp = (char_u *)xmalloc(new_line_len);
+    startcol = (int)verbatim_diff;
+    oldlen = bd.textcol + (int)(non_white - bd.textstart) - (int)verbatim_diff;
+    newlen = (int)fill;
     memmove(newp, oldp, verbatim_diff);
     memset(newp + verbatim_diff, ' ', fill);
     STRMOVE(newp + verbatim_diff + fill, non_white);
@@ -486,13 +489,12 @@ static void shift_block(oparg_T *oap, int amount)
   // replace the line
   ml_replace(curwin->w_cursor.lnum, newp, false);
   changed_bytes(curwin->w_cursor.lnum, (colnr_T)bd.textcol);
+  extmark_splice(curbuf, (int)curwin->w_cursor.lnum-1, startcol,
+                 0, oldlen, 0, newlen,
+                 kExtmarkUndo);
   State = oldstate;
   curwin->w_cursor.col = oldcol;
   p_ri = old_p_ri;
-
-  colnr_T col_amount = left ? -p_sw : p_sw;
-  extmark_col_adjust(curbuf, curwin->w_cursor.lnum,
-                     curwin->w_cursor.col, 0, col_amount, kExtmarkUndo);
 }
 
 /*
@@ -561,6 +563,7 @@ static void block_insert(oparg_T *oap, char_u *s, int b_insert, struct block_def
     // copy up to shifted part
     memmove(newp, oldp, (size_t)offset);
     oldp += offset;
+    int startcol = offset;
 
     // insert pre-padding
     memset(newp + offset, ' ', (size_t)spaces);
@@ -569,6 +572,7 @@ static void block_insert(oparg_T *oap, char_u *s, int b_insert, struct block_def
     memmove(newp + offset + spaces, s, s_len);
     offset += (int)s_len;
 
+    int skipped = 0;
     if (spaces && !bdp->is_short) {
       // insert post-padding
       memset(newp + offset + spaces, ' ', (size_t)(p_ts - spaces));
@@ -576,6 +580,7 @@ static void block_insert(oparg_T *oap, char_u *s, int b_insert, struct block_def
       oldp++;
       // We allowed for that TAB, remember this now
       count++;
+      skipped = 1;
     }
 
     if (spaces > 0)
@@ -583,6 +588,9 @@ static void block_insert(oparg_T *oap, char_u *s, int b_insert, struct block_def
     STRMOVE(newp + offset, oldp);
 
     ml_replace(lnum, newp, false);
+    extmark_splice(curbuf, (int)lnum-1, startcol,
+                   0, skipped,
+                   0, offset-startcol, kExtmarkUndo);
 
     if (lnum == oap->end.lnum) {
       /* Set "']" mark to the end of the block instead of the end of
@@ -642,14 +650,6 @@ void op_reindent(oparg_T *oap, Indenter how)
           first_changed = curwin->w_cursor.lnum;
         }
         last_changed = curwin->w_cursor.lnum;
-
-        // Adjust extmarks
-        extmark_col_adjust(curbuf,
-                           curwin->w_cursor.lnum,
-                           0,             // mincol
-                           0,             // lnum_amount
-                           amount,        // col_amount
-                           kExtmarkUndo);
       }
     }
     ++curwin->w_cursor.lnum;
@@ -1517,6 +1517,11 @@ int op_delete(oparg_T *oap)
       STRMOVE(newp + bd.textcol + bd.startspaces + bd.endspaces, oldp);
       // replace the line
       ml_replace(lnum, newp, false);
+
+      extmark_splice(curbuf, (int)lnum-1, bd.textcol,
+                     0, bd.textlen,
+                     0, bd.startspaces+bd.endspaces,
+                     kExtmarkUndo);
     }
 
     check_cursor_col();
@@ -1633,6 +1638,8 @@ int op_delete(oparg_T *oap)
               (linenr_T)(curwin->w_cursor.lnum + oap->line_count)) == FAIL)
         return FAIL;
 
+      curbuf_splice_pending++;
+      pos_T startpos = curwin->w_cursor;  // start position for delete
       truncate_line(true);        // delete from cursor to end of line
 
       curpos = curwin->w_cursor;  // remember curwin->w_cursor
@@ -1646,6 +1653,9 @@ int op_delete(oparg_T *oap)
                       oap->op_type == OP_DELETE && !oap->is_VIsual);
       curwin->w_cursor = curpos;  // restore curwin->w_cursor
       (void)do_join(2, false, false, false, false);
+      curbuf_splice_pending--;
+      extmark_splice(curbuf, (int)startpos.lnum-1, startpos.col,
+                     (int)oap->line_count-1, n, 0, 0, kExtmarkUndo);
     }
   }
 
@@ -1660,19 +1670,6 @@ setmarks:
   }
   curbuf->b_op_start = oap->start;
 
-  // TODO(timeyyy): refactor: Move extended marks
-  // + 1 to change to buf mode,
-  // and + 1 because we only move marks after the deleted col
-  colnr_T mincol = oap->start.col + 1 + 1;
-  colnr_T endcol;
-  if (oap->motion_type == kMTBlockWise) {
-    // TODO(timeyyy): refactor extmark_col_adjust to take lnumstart, lnum_end ?
-    endcol = bd.end_vcol + 1;
-    for (lnum = curwin->w_cursor.lnum; lnum <= oap->end.lnum; lnum++) {
-      extmark_col_adjust_delete(curbuf, lnum, mincol, endcol,
-                                kExtmarkUndo, 0);
-    }
-  }
   return OK;
 }
 
@@ -1695,8 +1692,11 @@ static void mb_adjust_opend(oparg_T *oap)
  */
 static inline void pbyte(pos_T lp, int c)
 {
-    assert(c <= UCHAR_MAX);
-    *(ml_get_buf(curbuf, lp.lnum, true) + lp.col) = (char_u)c;
+  assert(c <= UCHAR_MAX);
+  *(ml_get_buf(curbuf, lp.lnum, true) + lp.col) = (char_u)c;
+  if (!curbuf_splice_pending) {
+    extmark_splice(curbuf, (int)lp.lnum-1, lp.col, 0, 1, 0, 1, kExtmarkUndo);
+  }
 }
 
 // Replace the character under the cursor with "c".
@@ -1817,6 +1817,7 @@ int op_replace(oparg_T *oap, int c)
       size_t after_p_len = 0;
       int col = oldlen - bd.textcol - bd.textlen + 1;
       assert(col >= 0);
+      int newrows = 0, newcols = 0;
       if (had_ctrl_v_cr || (c != '\r' && c != '\n')) {
           // strlen(newp) at this point
           int newp_len = bd.textcol + bd.startspaces;
@@ -1829,21 +1830,27 @@ int op_replace(oparg_T *oap, int c)
             newp_len += bd.endspaces;
             // copy the part after the changed part
             memmove(newp + newp_len, oldp, (size_t)col);
-        }
+          }
+          newcols = newp_len - bd.textcol;
       } else {
         // Replacing with \r or \n means splitting the line.
         after_p_len = (size_t)col;
         after_p = (char_u *)xmalloc(after_p_len);
         memmove(after_p, oldp, after_p_len);
+        newrows = 1;
       }
       // replace the line
       ml_replace(curwin->w_cursor.lnum, newp, false);
+      linenr_T baselnum = curwin->w_cursor.lnum;
       if (after_p != NULL) {
         ml_append(curwin->w_cursor.lnum++, after_p, (int)after_p_len, false);
         appended_lines_mark(curwin->w_cursor.lnum, 1L);
         oap->end.lnum++;
         xfree(after_p);
       }
+      extmark_splice(curbuf, (int)baselnum-1, bd.textcol,
+                     0, bd.textlen,
+                     newrows, newcols, kExtmarkUndo);
     }
   } else {
     // Characterwise or linewise motion replace.
@@ -1856,6 +1863,8 @@ int op_replace(oparg_T *oap, int c)
     } else if (!oap->inclusive)
       dec(&(oap->end));
 
+    // TODO(bfredl): we could batch all the splicing
+    // done on the same line, at least
     while (ltoreq(curwin->w_cursor, oap->end)) {
       n = gchar_cursor();
       if (n != NUL) {
@@ -2262,10 +2271,6 @@ void op_insert(oparg_T *oap, long count1)
       xfree(ins_text);
     }
   }
-  colnr_T col = oap->start.col;
-  for (linenr_T lnum = oap->start.lnum; lnum <= oap->end.lnum; lnum++) {
-    extmark_col_adjust(curbuf, lnum, col, 0, 1, kExtmarkUndo);
-  }
 }
 
 /*
@@ -2380,6 +2385,9 @@ int op_change(oparg_T *oap)
           oldp += bd.textcol;
           STRMOVE(newp + offset, oldp);
           ml_replace(linenr, newp, false);
+          extmark_splice(curbuf, (int)linenr-1, bd.textcol,
+                         0, 0,
+                         0, vpos.coladd+(int)ins_len, kExtmarkUndo);
         }
       }
       check_cursor();
@@ -2735,28 +2743,6 @@ static void do_autocmd_textyankpost(oparg_T *oap, yankreg_T *reg)
   recursive = false;
 }
 
-
-static void extmarks_do_put(int dir,
-                            size_t totlen,
-                            MotionType y_type,
-                            linenr_T lnum,
-                            colnr_T col)
-{
-  // adjust extmarks
-  colnr_T col_amount = (colnr_T)(dir == FORWARD ? totlen-1 : totlen);
-  // Move extmark with char put
-  if (y_type == kMTCharWise) {
-    extmark_col_adjust(curbuf, lnum, col, 0, col_amount, kExtmarkUndo);
-  // Move extmark with blockwise put
-  } else if (y_type == kMTBlockWise) {
-    for (lnum = curbuf->b_op_start.lnum;
-         lnum <= curbuf->b_op_end.lnum;
-         lnum++) {
-      extmark_col_adjust(curbuf, lnum, col, 0, col_amount, kExtmarkUndo);
-    }
-  }
-}
-
 /*
  * Put contents of register "regname" into the text.
  * Caller must check "regname" to be valid!
@@ -3176,6 +3162,10 @@ void do_put(int regname, yankreg_T *reg, int dir, long count, int flags)
       assert(columns >= 0);
       memmove(ptr, oldp + bd.textcol + delcount, (size_t)columns);
       ml_replace(curwin->w_cursor.lnum, newp, false);
+      extmark_splice(curbuf, (int)curwin->w_cursor.lnum-1, bd.textcol,
+                     0, delcount,
+                     0, (int)totlen,
+                     kExtmarkUndo);
 
       ++curwin->w_cursor.lnum;
       if (i == 0)
@@ -3277,6 +3267,9 @@ void do_put(int regname, yankreg_T *reg, int dir, long count, int flags)
       if (totlen && (restart_edit != 0 || (flags & PUT_CURSEND)))
         ++curwin->w_cursor.col;
       changed_bytes(lnum, col);
+      extmark_splice(curbuf, (int)lnum-1, col,
+                     0, 0,
+                     0, (int)totlen, kExtmarkUndo);
     } else {
       // Insert at least one line.  When y_type is kMTCharWise, break the first
       // line in two.
@@ -3332,13 +3325,22 @@ void do_put(int regname, yankreg_T *reg, int dir, long count, int flags)
               first_indent = FALSE;
             } else if ((indent = get_indent() + indent_diff) < 0)
               indent = 0;
-            (void)set_indent(indent, 0);
+            (void)set_indent(indent, SIN_NOMARK);
             curwin->w_cursor = old_pos;
             /* remember how many chars were removed */
             if (cnt == count && i == y_size - 1)
               lendiff -= (int)STRLEN(ml_get(lnum));
           }
         }
+
+        if (y_type == kMTCharWise) {
+          extmark_splice(curbuf, (int)new_cursor.lnum-1, col, 0, 0,
+                         (int)y_size-1, (int)STRLEN(y_array[y_size-1]),
+                         kExtmarkUndo);
+        } else if (y_type == kMTLineWise && flags & PUT_LINE_SPLIT) {
+          extmark_splice(curbuf, (int)new_cursor.lnum-1, col, 0, 0,
+                         (int)y_size+1, 0, kExtmarkUndo);
+        }
       }
 
 error:
@@ -3352,8 +3354,10 @@ error:
       // can't be marks there.
       if (curbuf->b_op_start.lnum + (y_type == kMTCharWise) - 1 + nr_lines
           < curbuf->b_ml.ml_line_count) {
+        ExtmarkOp kind = (y_type == kMTLineWise && !(flags & PUT_LINE_SPLIT))
+                         ? kExtmarkUndo : kExtmarkNOOP;
         mark_adjust(curbuf->b_op_start.lnum + (y_type == kMTCharWise),
-                    (linenr_T)MAXLNUM, nr_lines, 0L, false, kExtmarkUndo);
+                    (linenr_T)MAXLNUM, nr_lines, 0L, kind);
       }
 
       // note changed text for displaying and folding
@@ -3415,9 +3419,7 @@ end:
 
   /* If the cursor is past the end of the line put it at the end. */
   adjust_cursor_eol();
-
-  extmarks_do_put(dir, totlen, y_type, lnum, col);
-}
+}  // NOLINT(readability/fn_size)
 
 /*
  * When the cursor is on the NUL past the end of the line and it should not be
@@ -3779,6 +3781,13 @@ int do_join(size_t count,
         }
       }
     }
+
+    if (t > 0 && curbuf_splice_pending == 0) {
+      extmark_splice(curbuf, (int)curwin->w_cursor.lnum-1, sumsize,
+                     1, (int)(curr- curr_start),
+                     0, spaces[t],
+                     kExtmarkUndo);
+    }
     currsize = (int)STRLEN(curr);
     sumsize += currsize + spaces[t];
     endcurr1 = endcurr2 = NUL;
@@ -3814,6 +3823,8 @@ int do_join(size_t count,
    * should not really be a problem.
    */
 
+  curbuf_splice_pending++;
+
   for (t = (linenr_T)count - 1;; t--) {
     cend -= currsize;
     memmove(cend, curr, (size_t)currsize);
@@ -3830,8 +3841,7 @@ int do_join(size_t count,
     long lnum_amount = (linenr_T)-t;
     long col_amount = (long)(cend - newp - spaces_removed);
 
-    mark_col_adjust(lnum, mincol, lnum_amount, col_amount, spaces_removed,
-                    kExtmarkUndo);
+    mark_col_adjust(lnum, mincol, lnum_amount, col_amount, spaces_removed);
 
     if (t == 0) {
       break;
@@ -3867,6 +3877,7 @@ int do_join(size_t count,
   curwin->w_cursor.lnum++;
   del_lines((long)count - 1, false);
   curwin->w_cursor.lnum = t;
+  curbuf_splice_pending--;
 
   /*
    * Set the cursor column:
@@ -4265,14 +4276,14 @@ format_lines(
         if (next_leader_len > 0) {
           (void)del_bytes(next_leader_len, false, false);
           mark_col_adjust(curwin->w_cursor.lnum, (colnr_T)0, 0L,
-                          (long)-next_leader_len, 0, kExtmarkNOOP);
+                          (long)-next_leader_len, 0);
         } else if (second_indent > 0) {   // the "leader" for FO_Q_SECOND
           int indent = (int)getwhitecols_curline();
 
           if (indent > 0) {
             (void)del_bytes(indent, false, false);
             mark_col_adjust(curwin->w_cursor.lnum,
-                            (colnr_T)0, 0L, (long)-indent, 0, kExtmarkNOOP);
+                            (colnr_T)0, 0L, (long)-indent, 0);
           }
         }
         curwin->w_cursor.lnum--;
diff --git a/src/nvim/screen.c b/src/nvim/screen.c
index 0612575e67..24ad012201 100644
--- a/src/nvim/screen.c
+++ b/src/nvim/screen.c
@@ -87,6 +87,7 @@
 #include "nvim/highlight.h"
 #include "nvim/main.h"
 #include "nvim/mark.h"
+#include "nvim/mark_extended.h"
 #include "nvim/mbyte.h"
 #include "nvim/memline.h"
 #include "nvim/memory.h"
@@ -622,6 +623,9 @@ bool win_cursorline_standout(const win_T *wp)
     || (wp->w_p_cole > 0 && (VIsual_active || !conceal_cursor_line(wp)));
 }
 
+static DecorationState decorations;
+bool decorations_active = false;
+
 /*
  * Update a single window.
  *
@@ -1221,6 +1225,7 @@ static void win_update(win_T *wp)
                          : (wp->w_topline + wp->w_height_inner));
     args.items[0] = WINDOW_OBJ(wp->handle);
     args.items[1] = BUFFER_OBJ(buf->handle);
+    // TODO(bfredl): we are not using this, but should be first drawn line?
     args.items[2] = INTEGER_OBJ(wp->w_topline-1);
     args.items[3] = INTEGER_OBJ(knownmax);
     // TODO(bfredl): we could allow this callback to change mod_top, mod_bot.
@@ -1232,6 +1237,8 @@ static void win_update(win_T *wp)
     }
   }
 
+  decorations_active = extmark_decorations_reset(buf, &decorations);
+
   for (;; ) {
     /* stop updating when reached the end of the window (check for _past_
      * the end of the window is at the end of the loop) */
@@ -2250,8 +2257,7 @@ win_line (
   int prev_c1 = 0;                      // first composing char for prev_c
 
   bool search_attr_from_match = false;  // if search_attr is from :match
-  BufhlLineInfo bufhl_info;             // bufhl data for this line
-  bool has_bufhl = false;               // this buffer has highlight matches
+  bool has_decorations = false;         // this buffer has decorations
   bool do_virttext = false;             // draw virtual text for this line
 
   /* draw_state: items that are drawn in sequence: */
@@ -2315,14 +2321,12 @@ win_line (
       }
     }
 
-    if (bufhl_start_line(wp->w_buffer, lnum, &bufhl_info)) {
-      if (kv_size(bufhl_info.line->items)) {
-        has_bufhl = true;
+    if (decorations_active) {
+      has_decorations = extmark_decorations_line(wp->w_buffer, lnum-1,
+                                                 &decorations);
+      if (has_decorations) {
         extra_check = true;
       }
-      if (kv_size(bufhl_info.line->virt_text)) {
-        do_virttext = true;
-      }
     }
 
     // Check for columns to display for 'colorcolumn'.
@@ -3515,19 +3519,25 @@ win_line (
             char_attr = hl_combine_attr(spell_attr, char_attr);
         }
 
-        if (has_bufhl && v > 0) {
-          int bufhl_attr = bufhl_get_attr(&bufhl_info, (colnr_T)v);
-          if (bufhl_attr != 0) {
+        if (has_decorations && v > 0) {
+          int extmark_attr = extmark_decorations_col(wp->w_buffer, (colnr_T)v-1,
+                                                     &decorations);
+          if (extmark_attr != 0) {
             if (!attr_pri) {
-              char_attr = hl_combine_attr(char_attr, bufhl_attr);
+              char_attr = hl_combine_attr(char_attr, extmark_attr);
             } else {
-              char_attr = hl_combine_attr(bufhl_attr, char_attr);
+              char_attr = hl_combine_attr(extmark_attr, char_attr);
             }
           }
         }
 
+        // TODO(bfredl): luahl should reuse the "active decorations" buffer
         if (buf->b_luahl && v > 0 && v < (long)lua_attr_bufsize+1) {
-          char_attr = hl_combine_attr(char_attr, lua_attr_buf[v-1]);
+          if (!attr_pri) {
+            char_attr = hl_combine_attr(char_attr, lua_attr_buf[v-1]);
+          } else {
+            char_attr = hl_combine_attr(lua_attr_buf[v-1], char_attr);
+          }
         }
 
         if (wp->w_buffer->terminal) {
@@ -4008,6 +4018,19 @@ win_line (
       if (draw_color_col)
         draw_color_col = advance_color_col(VCOL_HLC, &color_cols);
 
+      VirtText virt_text = KV_INITIAL_VALUE;
+      if (luatext) {
+        kv_push(virt_text, ((VirtTextChunk){ .text = luatext, .hl_id = 0 }));
+        do_virttext = true;
+      } else if (has_decorations) {
+        VirtText *vp = extmark_decorations_virt_text(wp->w_buffer,
+                                                     &decorations);
+        if (vp) {
+          virt_text = *vp;
+          do_virttext = true;
+        }
+      }
+
       if (((wp->w_p_cuc
             && (int)wp->w_virtcol >= VCOL_HLC - eol_hl_off
             && (int)wp->w_virtcol <
@@ -4018,14 +4041,6 @@ win_line (
         int rightmost_vcol = 0;
         int i;
 
-        VirtText virt_text;
-        if (luatext) {
-          virt_text = (VirtText)KV_INITIAL_VALUE;
-          kv_push(virt_text, ((VirtTextChunk){ .text = luatext, .hl_id = 0 }));
-        } else {
-          virt_text = do_virttext ? bufhl_info.line->virt_text
-                                  : (VirtText)KV_INITIAL_VALUE;
-        }
         size_t virt_pos = 0;
         LineState s = LINE_STATE((char_u *)"");
         int virt_attr = 0;
diff --git a/src/nvim/undo.c b/src/nvim/undo.c
index 980399a3ef..fda647106d 100644
--- a/src/nvim/undo.c
+++ b/src/nvim/undo.c
@@ -2244,7 +2244,7 @@ static void u_undoredo(int undo, bool do_buf_event)
     // Adjust marks
     if (oldsize != newsize) {
       mark_adjust(top + 1, top + oldsize, (long)MAXLNUM,
-                  (long)newsize - (long)oldsize, false, kExtmarkNOOP);
+                  (long)newsize - (long)oldsize, kExtmarkNOOP);
       if (curbuf->b_op_start.lnum > top + oldsize) {
         curbuf->b_op_start.lnum += newsize - oldsize;
       }
diff --git a/test/functional/api/mark_extended_spec.lua b/test/functional/api/mark_extended_spec.lua
index bf910568b1..8aa8ed07c5 100644
--- a/test/functional/api/mark_extended_spec.lua
+++ b/test/functional/api/mark_extended_spec.lua
@@ -11,6 +11,11 @@ local insert = helpers.insert
 local feed = helpers.feed
 local clear = helpers.clear
 local command = helpers.command
+local meths = helpers.meths
+
+local function expect(contents)
+  return eq(contents, helpers.curbuf_contents())
+end
 
 local function check_undo_redo(ns, mark, sr, sc, er, ec) --s = start, e = end
   local rv = curbufmeths.get_extmark_by_id(ns, mark)
@@ -37,9 +42,36 @@ local function get_extmarks(ns_id, start, end_, opts)
   return curbufmeths.get_extmarks(ns_id, start, end_, opts)
 end
 
+local function batch_set(ns_id, positions)
+  local ids = {}
+  for _, pos in ipairs(positions) do
+    table.insert(ids, set_extmark(ns_id, 0, pos[1], pos[2]))
+  end
+  return ids
+end
+
+local function batch_check(ns_id, ids, positions)
+  local actual, expected = {}, {}
+  for i,id in ipairs(ids) do
+    expected[id] = positions[i]
+  end
+  for _, mark in pairs(get_extmarks(ns_id, 0, -1, {})) do
+    actual[mark[1]] = {mark[2], mark[3]}
+  end
+  eq(expected, actual)
+end
+
+local function batch_check_undo_redo(ns_id, ids, before, after)
+  batch_check(ns_id, ids, after)
+  feed("u")
+  batch_check(ns_id, ids, before)
+  feed("<c-r>")
+  batch_check(ns_id, ids, after)
+end
+
 describe('API/extmarks', function()
   local screen
-  local marks, positions, ns_string2, ns_string, init_text, row, col
+  local marks, positions, init_text, row, col
   local ns, ns2
 
   before_each(function()
@@ -47,22 +79,18 @@ describe('API/extmarks', function()
     marks = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
     positions = {{0, 0,}, {0, 2}, {0, 3}}
 
-    ns_string = "my-fancy-plugin"
-    ns_string2 = "my-fancy-plugin2"
     init_text = "12345"
     row = 0
     col = 2
 
     clear()
-    screen = Screen.new(15, 10)
-    screen:attach()
 
     insert(init_text)
-    ns = request('nvim_create_namespace', ns_string)
-    ns2 = request('nvim_create_namespace', ns_string2)
+    ns = request('nvim_create_namespace', "my-fancy-plugin")
+    ns2 = request('nvim_create_namespace', "my-fancy-plugin2")
   end)
 
-  it('adds, updates  and deletes marks #extmarks', function()
+  it('adds, updates  and deletes marks', function()
     local rv = set_extmark(ns, marks[1], positions[1][1], positions[1][2])
     eq(marks[1], rv)
     rv = curbufmeths.get_extmark_by_id(ns, marks[1])
@@ -92,7 +120,7 @@ describe('API/extmarks', function()
     eq(false, curbufmeths.del_extmark(ns, 1000))
   end)
 
-  it('can clear a specific namespace range #extmarks', function()
+  it('can clear a specific namespace range', function()
     set_extmark(ns, 1, 0, 1)
     set_extmark(ns2, 1, 0, 1)
     -- force a new undo buffer
@@ -102,13 +130,13 @@ describe('API/extmarks', function()
     eq({}, get_extmarks(ns2, {0, 0}, {-1, -1}))
     feed('u')
     eq({{1, 0, 1}}, get_extmarks(ns, {0, 0}, {-1, -1}))
-    eq({{1, 0, 1}}, get_extmarks(ns2, {0, 0}, {-1, -1}))
+    eq({}, get_extmarks(ns2, {0, 0}, {-1, -1}))
     feed('<c-r>')
     eq({{1, 0, 1}}, get_extmarks(ns, {0, 0}, {-1, -1}))
     eq({}, get_extmarks(ns2, {0, 0}, {-1, -1}))
   end)
 
-  it('can clear a namespace range using 0,-1 #extmarks', function()
+  it('can clear a namespace range using 0,-1', function()
     set_extmark(ns, 1, 0, 1)
     set_extmark(ns2, 1, 0, 1)
     -- force a new undo buffer
@@ -117,14 +145,16 @@ describe('API/extmarks', function()
     eq({}, get_extmarks(ns, {0, 0}, {-1, -1}))
     eq({}, get_extmarks(ns2, {0, 0}, {-1, -1}))
     feed('u')
-    eq({{1, 0, 1}}, get_extmarks(ns, {0, 0}, {-1, -1}))
-    eq({{1, 0, 1}}, get_extmarks(ns2, {0, 0}, {-1, -1}))
+    eq({}, get_extmarks(ns, {0, 0}, {-1, -1}))
+    eq({}, get_extmarks(ns2, {0, 0}, {-1, -1}))
     feed('<c-r>')
     eq({}, get_extmarks(ns, {0, 0}, {-1, -1}))
     eq({}, get_extmarks(ns2, {0, 0}, {-1, -1}))
   end)
 
-  it('querying for information and ranges #extmarks', function()
+  it('querying for information and ranges', function()
+    --marks = {1, 2, 3}
+    --positions = {{0, 0,}, {0, 2}, {0, 3}}
     -- add some more marks
     for i, m in ipairs(marks) do
       if positions[i] ~= nil then
@@ -242,7 +272,7 @@ describe('API/extmarks', function()
     eq({{marks[1], positions[1][1], positions[1][2]}}, rv)
   end)
 
-  it('querying for information with limit #extmarks', function()
+  it('querying for information with limit', function()
     -- add some more marks
     for i, m in ipairs(marks) do
       if positions[i] ~= nil then
@@ -267,7 +297,7 @@ describe('API/extmarks', function()
     eq(3, table.getn(rv))
   end)
 
-  it('get_marks works when mark col > upper col #extmarks', function()
+  it('get_marks works when mark col > upper col', function()
     feed('A<cr>12345<esc>')
     feed('A<cr>12345<esc>')
     set_extmark(ns, 10, 0, 2)       -- this shouldn't be found
@@ -281,7 +311,7 @@ describe('API/extmarks', function()
        get_extmarks(ns, {0, 3}, {2, 0}))
   end)
 
-  it('get_marks works in reverse when mark col < lower col #extmarks', function()
+  it('get_marks works in reverse when mark col < lower col', function()
     feed('A<cr>12345<esc>')
     feed('A<cr>12345<esc>')
     set_extmark(ns, 10, 0, 1) -- this shouldn't be found
@@ -296,27 +326,27 @@ describe('API/extmarks', function()
        rv)
   end)
 
-  it('get_marks limit=0 returns nothing #extmarks', function()
+  it('get_marks limit=0 returns nothing', function()
     set_extmark(ns, marks[1], positions[1][1], positions[1][2])
     local rv = get_extmarks(ns, {-1, -1}, {-1, -1}, {limit=0})
     eq({}, rv)
   end)
 
 
-  it('marks move with line insertations #extmarks', function()
+  it('marks move with line insertations', function()
     set_extmark(ns, marks[1], 0, 0)
     feed("yyP")
     check_undo_redo(ns, marks[1], 0, 0, 1, 0)
   end)
 
-  it('marks move with multiline insertations #extmarks', function()
+  it('marks move with multiline insertations', function()
     feed("a<cr>22<cr>33<esc>")
     set_extmark(ns, marks[1], 1, 1)
     feed('ggVGyP')
     check_undo_redo(ns, marks[1], 1, 1, 4, 1)
   end)
 
-  it('marks move with line join #extmarks', function()
+  it('marks move with line join', function()
     -- do_join in ops.c
     feed("a<cr>222<esc>")
     set_extmark(ns, marks[1], 1, 0)
@@ -324,7 +354,9 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 0, 0, 6)
   end)
 
-  it('join works when no marks are present #extmarks', function()
+  it('join works when no marks are present', function()
+    screen = Screen.new(15, 10)
+    screen:attach()
     feed("a<cr>1<esc>")
     feed('kJ')
     -- This shouldn't seg fault
@@ -342,7 +374,7 @@ describe('API/extmarks', function()
     ]])
   end)
 
-  it('marks move with multiline join #extmarks', function()
+  it('marks move with multiline join', function()
     -- do_join in ops.c
     feed("a<cr>222<cr>333<cr>444<esc>")
     set_extmark(ns, marks[1], 3, 0)
@@ -350,14 +382,14 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 3, 0, 1, 8)
   end)
 
-  it('marks move with line deletes #extmarks', function()
+  it('marks move with line deletes', function()
     feed("a<cr>222<cr>333<cr>444<esc>")
     set_extmark(ns, marks[1], 2, 1)
     feed('ggjdd')
     check_undo_redo(ns, marks[1], 2, 1, 1, 1)
   end)
 
-  it('marks move with multiline deletes #extmarks', function()
+  it('marks move with multiline deletes', function()
     feed("a<cr>222<cr>333<cr>444<esc>")
     set_extmark(ns, marks[1], 3, 0)
     feed('gg2dd')
@@ -367,7 +399,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 3, 0, 0, 0)
   end)
 
-  it('marks move with open line #extmarks', function()
+  it('marks move with open line', function()
     -- open_line in misc1.c
     -- testing marks below are also moved
     feed("yyP")
@@ -381,8 +413,10 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 2, 4, 3, 4)
   end)
 
-  it('marks move with char inserts #extmarks', function()
+  it('marks move with char inserts', function()
     -- insertchar in edit.c (the ins_str branch)
+    screen = Screen.new(15, 10)
+    screen:attach()
     set_extmark(ns, marks[1], 0, 3)
     feed('0')
     insert('abc')
@@ -400,11 +434,11 @@ describe('API/extmarks', function()
     ]])
     local rv = curbufmeths.get_extmark_by_id(ns, marks[1])
     eq({0, 6}, rv)
-    -- check_undo_redo(ns, marks[1], 0, 2, 0, 5)
+    check_undo_redo(ns, marks[1], 0, 3, 0, 6)
   end)
 
   -- gravity right as definted in tk library
-  it('marks have gravity right #extmarks', function()
+  it('marks have gravity right', function()
     -- insertchar in edit.c (the ins_str branch)
     set_extmark(ns, marks[1], 0, 2)
     feed('03l')
@@ -417,7 +451,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 2, 0, 2)
   end)
 
-  it('we can insert multibyte chars #extmarks', function()
+  it('we can insert multibyte chars', function()
     -- insertchar in edit.c
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 1, 2)
@@ -426,7 +460,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 2, 1, 5)
   end)
 
-  it('marks move with blockwise inserts #extmarks', function()
+  it('marks move with blockwise inserts', function()
     -- op_insert in ops.c
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 1, 2)
@@ -434,7 +468,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 2, 1, 3)
   end)
 
-  it('marks move with line splits (using enter) #extmarks', function()
+  it('marks move with line splits (using enter)', function()
     -- open_line in misc1.c
     -- testing marks below are also moved
     feed("yyP")
@@ -445,14 +479,14 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 1, 4, 2, 4)
   end)
 
-  it('marks at last line move on insert new line #extmarks', function()
+  it('marks at last line move on insert new line', function()
     -- open_line in misc1.c
     set_extmark(ns, marks[1], 0, 4)
     feed('0i<cr><esc>')
     check_undo_redo(ns, marks[1], 0, 4, 1, 4)
   end)
 
-  it('yet again marks move with line splits #extmarks', function()
+  it('yet again marks move with line splits', function()
     -- the first test above wasn't catching all errors..
     feed("A67890<esc>")
     set_extmark(ns, marks[1], 0, 4)
@@ -460,7 +494,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 4, 1, 0)
   end)
 
-  it('and one last time line splits... #extmarks', function()
+  it('and one last time line splits...', function()
     set_extmark(ns, marks[1], 0, 1)
     set_extmark(ns, marks[2], 0, 2)
     feed("02li<cr><esc>")
@@ -468,7 +502,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 2, 1, 0)
   end)
 
-  it('multiple marks move with mark splits #extmarks', function()
+  it('multiple marks move with mark splits', function()
     set_extmark(ns, marks[1], 0, 1)
     set_extmark(ns, marks[2], 0, 3)
     feed("0li<cr><esc>")
@@ -476,21 +510,21 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 3, 1, 2)
   end)
 
-  it('deleting right before a mark works #extmarks', function()
+  it('deleting right before a mark works', function()
     -- op_delete in ops.c
     set_extmark(ns, marks[1], 0, 2)
     feed('0lx')
     check_undo_redo(ns, marks[1], 0, 2, 0, 1)
   end)
 
-  it('deleting on a mark works #extmarks', function()
+  it('deleting right after a mark works', function()
     -- op_delete in ops.c
     set_extmark(ns, marks[1], 0, 2)
     feed('02lx')
     check_undo_redo(ns, marks[1], 0, 2, 0, 2)
   end)
 
-  it('marks move with char deletes #extmarks', function()
+  it('marks move with char deletes', function()
     -- op_delete in ops.c
     set_extmark(ns, marks[1], 0, 2)
     feed('02dl')
@@ -500,7 +534,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 0, 0, 0)
   end)
 
-  it('marks move with char deletes over a range #extmarks', function()
+  it('marks move with char deletes over a range', function()
     -- op_delete in ops.c
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -513,7 +547,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 3, 0, 3)
   end)
 
-  it('deleting marks at end of line works #extmarks', function()
+  it('deleting marks at end of line works', function()
     -- mark_extended.c/extmark_col_adjust_delete
     set_extmark(ns, marks[1], 0, 4)
     feed('$x')
@@ -525,7 +559,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 4, 0, 4)
   end)
 
-  it('marks move with blockwise deletes #extmarks', function()
+  it('marks move with blockwise deletes', function()
     -- op_delete in ops.c
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 1, 4)
@@ -533,7 +567,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 4, 1, 1)
   end)
 
-  it('marks move with blockwise deletes over a range #extmarks', function()
+  it('marks move with blockwise deletes over a range', function()
     -- op_delete in ops.c
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 0, 1)
@@ -550,7 +584,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[3], 1, 2, 1, 2)
   end)
 
-  it('works with char deletes over multilines #extmarks', function()
+  it('works with char deletes over multilines', function()
     feed('a<cr>12345<cr>test-me<esc>')
     set_extmark(ns, marks[1], 2, 5)
     feed('gg')
@@ -558,7 +592,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 2, 5, 0, 0)
   end)
 
-  it('marks outside of deleted range move with visual char deletes #extmarks', function()
+  it('marks outside of deleted range move with visual char deletes', function()
     -- op_delete in ops.c
     set_extmark(ns, marks[1], 0, 3)
     feed('0vx<esc>')
@@ -577,7 +611,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 0, 0, 0)
   end)
 
-  it('marks outside of deleted range move with char deletes #extmarks', function()
+  it('marks outside of deleted range move with char deletes', function()
     -- op_delete in ops.c
     set_extmark(ns, marks[1], 0, 3)
     feed('0x<esc>')
@@ -597,7 +631,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 3, 0, 3)
   end)
 
-  it('marks move with P(backward) paste #extmarks', function()
+  it('marks move with P(backward) paste', function()
     -- do_put in ops.c
     feed('0iabc<esc>')
     set_extmark(ns, marks[1], 0, 7)
@@ -605,15 +639,15 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 7, 0, 15)
   end)
 
-  it('marks move with p(forward) paste #extmarks', function()
+  it('marks move with p(forward) paste', function()
     -- do_put in ops.c
     feed('0iabc<esc>')
     set_extmark(ns, marks[1], 0, 7)
     feed('0veyp')
-    check_undo_redo(ns, marks[1], 0, 7, 0, 14)
+    check_undo_redo(ns, marks[1], 0, 7, 0, 15)
   end)
 
-  it('marks move with blockwise P(backward) paste #extmarks', function()
+  it('marks move with blockwise P(backward) paste', function()
     -- do_put in ops.c
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 1, 4)
@@ -621,42 +655,84 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 4, 1, 7)
   end)
 
-  it('marks move with blockwise p(forward) paste #extmarks', function()
+  it('marks move with blockwise p(forward) paste', function()
     -- do_put in ops.c
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 1, 4)
     feed('<c-v>hhkyp<esc>')
-    check_undo_redo(ns, marks[1], 1, 4, 1, 6)
+    check_undo_redo(ns, marks[1], 1, 4, 1, 7)
   end)
 
-  it('replace works #extmarks', function()
+  describe('multiline regions', function()
+    before_each(function()
+      feed('dd')
+      -- Achtung: code has been spiced with some unicode,
+      -- to make life more interesting.
+      -- luacheck whines about TABs inside strings for whatever reason.
+      -- luacheck: push ignore 621
+      insert([[
+        static int nlua_rpcrequest(lua_State *lstate)
+        {
+          Ïf (!nlua_is_deferred_safe(lstate)) {
+        	// strictly not allowed
+            Яetörn luaL_error(lstate, e_luv_api_disabled, "rpcrequest");
+          }
+          return nlua_rpc(lstate, true);
+        }]])
+      -- luacheck: pop
+    end)
+
+    it('delete', function()
+      local pos1 = {
+        {2, 4}, {2, 12}, {2, 13}, {2, 14}, {2, 25},
+        {4, 8}, {4, 10}, {4, 20},
+        {5, 3}, {6, 10}
+      }
+      local ids = batch_set(ns, pos1)
+      batch_check(ns, ids, pos1)
+      feed('3Gfiv2+ftd')
+      batch_check_undo_redo(ns, ids, pos1, {
+        {2, 4}, {2, 12}, {2, 13}, {2, 13}, {2, 13},
+        {2, 13}, {2, 15}, {2, 25},
+        {3, 3}, {4, 10}
+      })
+    end)
+
+    -- TODO(bfredl): add more tests!
+  end)
+
+  it('replace works', function()
     set_extmark(ns, marks[1], 0, 2)
     feed('0r2')
     check_undo_redo(ns, marks[1], 0, 2, 0, 2)
   end)
 
-  it('blockwise replace works #extmarks', function()
+  it('blockwise replace works', function()
     feed('a<cr>12345<esc>')
     set_extmark(ns, marks[1], 0, 2)
     feed('0<c-v>llkr1<esc>')
-    check_undo_redo(ns, marks[1], 0, 2, 0, 2)
+    check_undo_redo(ns, marks[1], 0, 2, 0, 3)
   end)
 
-  it('shift line #extmarks', function()
+  it('shift line', function()
     -- shift_line in ops.c
     feed(':set shiftwidth=4<cr><esc>')
     set_extmark(ns, marks[1], 0, 2)
     feed('0>>')
     check_undo_redo(ns, marks[1], 0, 2, 0, 6)
+    expect('    12345')
 
     feed('>>')
-    check_undo_redo(ns, marks[1], 0, 6, 0, 10)
+    -- this is counter-intuitive. But what happens
+    -- is that 4 spaces gets extended to one tab (== 8 spaces)
+    check_undo_redo(ns, marks[1], 0, 6, 0, 3)
+    expect('\t12345')
 
     feed('<LT><LT>') -- have to escape, same as <<
-    check_undo_redo(ns, marks[1], 0, 10, 0, 6)
+    check_undo_redo(ns, marks[1], 0, 3, 0, 6)
   end)
 
-  it('blockwise shift #extmarks', function()
+  it('blockwise shift', function()
     -- shift_block in ops.c
     feed(':set shiftwidth=4<cr><esc>')
     feed('a<cr>12345<esc>')
@@ -664,13 +740,14 @@ describe('API/extmarks', function()
     feed('0<c-v>k>')
     check_undo_redo(ns, marks[1], 1, 2, 1, 6)
     feed('<c-v>j>')
-    check_undo_redo(ns, marks[1], 1, 6, 1, 10)
+    expect('\t12345\n\t12345')
+    check_undo_redo(ns, marks[1], 1, 6, 1, 3)
 
     feed('<c-v>j<LT>')
-    check_undo_redo(ns, marks[1], 1, 10, 1, 6)
+    check_undo_redo(ns, marks[1], 1, 3, 1, 6)
   end)
 
-  it('tab works with expandtab #extmarks', function()
+  it('tab works with expandtab', function()
     -- ins_tab in edit.c
     feed(':set expandtab<cr><esc>')
     feed(':set shiftwidth=2<cr><esc>')
@@ -679,7 +756,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 2, 0, 6)
   end)
 
-  it('tabs work #extmarks', function()
+  it('tabs work', function()
     -- ins_tab in edit.c
     feed(':set noexpandtab<cr><esc>')
     feed(':set shiftwidth=2<cr><esc>')
@@ -692,7 +769,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 4, 0, 6)
   end)
 
-  it('marks move when using :move #extmarks', function()
+  it('marks move when using :move', function()
     set_extmark(ns, marks[1], 0, 0)
     feed('A<cr>2<esc>:1move 2<cr><esc>')
     check_undo_redo(ns, marks[1], 0, 0, 1, 0)
@@ -701,7 +778,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 0, 0, 0)
   end)
 
-  it('marks move when using :move part 2 #extmarks', function()
+  it('marks move when using :move part 2', function()
     -- make sure we didn't get lucky with the math...
     feed('A<cr>2<cr>3<cr>4<cr>5<cr>6<esc>')
     set_extmark(ns, marks[1], 1, 0)
@@ -712,7 +789,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 3, 0, 1, 0)
   end)
 
-  it('undo and redo of set and unset marks #extmarks', function()
+  it('undo and redo of set and unset marks', function()
     -- Force a new undo head
     feed('o<esc>')
     set_extmark(ns, marks[1], 0, 1)
@@ -722,7 +799,7 @@ describe('API/extmarks', function()
 
     feed("u")
     local rv = get_extmarks(ns, {0, 0}, {-1, -1})
-    eq(1, table.getn(rv))
+    eq(3, table.getn(rv))
 
     feed("<c-r>")
     rv = get_extmarks(ns, {0, 0}, {-1, -1})
@@ -735,20 +812,22 @@ describe('API/extmarks', function()
     eq(1, table.getn(rv))
     feed("u")
     feed("<c-r>")
-    check_undo_redo(ns, marks[1], 0, 1, positions[1][1], positions[1][2])
+    -- old value is NOT kept in history
+    check_undo_redo(ns, marks[1], positions[1][1], positions[1][2], positions[1][1], positions[1][2])
 
     -- Test unset
     feed('o<esc>')
     curbufmeths.del_extmark(ns, marks[3])
     feed("u")
     rv = get_extmarks(ns, {0, 0}, {-1, -1})
-    eq(3, table.getn(rv))
+    -- undo does NOT restore deleted marks
+    eq(2, table.getn(rv))
     feed("<c-r>")
     rv = get_extmarks(ns, {0, 0}, {-1, -1})
     eq(2, table.getn(rv))
   end)
 
-  it('undo and redo of marks deleted during edits #extmarks', function()
+  it('undo and redo of marks deleted during edits', function()
     -- test extmark_adjust
     feed('A<cr>12345<esc>')
     set_extmark(ns, marks[1], 1, 2)
@@ -756,7 +835,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 1, 2, 1, 0)
   end)
 
-  it('namespaces work properly #extmarks', function()
+  it('namespaces work properly', function()
     local rv = set_extmark(ns, marks[1], positions[1][1], positions[1][2])
     eq(1, rv)
     rv = set_extmark(ns2, marks[1], positions[1][1], positions[1][2])
@@ -802,7 +881,7 @@ describe('API/extmarks', function()
     eq(2, table.getn(rv))
   end)
 
-  it('mark set can create unique identifiers #extmarks', function()
+  it('mark set can create unique identifiers', function()
     -- create mark with id 1
     eq(1, set_extmark(ns, 1, positions[1][1], positions[1][2]))
     -- ask for unique id, it should be the next one, i e 2
@@ -817,7 +896,7 @@ describe('API/extmarks', function()
     eq(8, set_extmark(ns, 0, positions[1][1], positions[1][2]))
   end)
 
-  it('auto indenting with enter works #extmarks', function()
+  it('auto indenting with enter works', function()
     -- op_reindent in ops.c
     feed(':set cindent<cr><esc>')
     feed(':set autoindent<cr><esc>')
@@ -835,7 +914,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[1], 0, 12, 1, 3)
   end)
 
-  it('auto indenting entire line works #extmarks', function()
+  it('auto indenting entire line works', function()
     feed(':set cindent<cr><esc>')
     feed(':set autoindent<cr><esc>')
     feed(':set shiftwidth=2<cr><esc>')
@@ -852,7 +931,7 @@ describe('API/extmarks', function()
     eq({1, 3}, rv)
   end)
 
-  it('removing auto indenting with <C-D> works #extmarks', function()
+  it('removing auto indenting with <C-D> works', function()
     feed(':set cindent<cr><esc>')
     feed(':set autoindent<cr><esc>')
     feed(':set shiftwidth=2<cr><esc>')
@@ -868,7 +947,7 @@ describe('API/extmarks', function()
     eq({0, 1}, rv)
   end)
 
-  it('indenting multiple lines with = works #extmarks', function()
+  it('indenting multiple lines with = works', function()
     feed(':set cindent<cr><esc>')
     feed(':set autoindent<cr><esc>')
     feed(':set shiftwidth=2<cr><esc>')
@@ -880,7 +959,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 2, 1, 2, 5)
   end)
 
-  it('substitutes by deleting inside the replace matches #extmarks_sub', function()
+  it('substitutes by deleting inside the replace matches', function()
     -- do_sub in ex_cmds.c
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -889,7 +968,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 3, 0, 4)
   end)
 
-  it('substitutes when insert text > deleted #extmarks_sub', function()
+  it('substitutes when insert text > deleted', function()
     -- do_sub in ex_cmds.c
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -898,7 +977,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 3, 0, 5)
   end)
 
-  it('substitutes when marks around eol #extmarks_sub', function()
+  it('substitutes when marks around eol', function()
     -- do_sub in ex_cmds.c
     set_extmark(ns, marks[1], 0, 4)
     set_extmark(ns, marks[2], 0, 5)
@@ -907,7 +986,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 5, 0, 7)
   end)
 
-  it('substitutes over range insert text > deleted #extmarks_sub', function()
+  it('substitutes over range insert text > deleted', function()
     -- do_sub in ex_cmds.c
     feed('A<cr>x34xx<esc>')
     feed('A<cr>xxx34<esc>')
@@ -920,7 +999,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[3], 2, 4, 2, 6)
   end)
 
-  it('substitutes multiple matches in a line #extmarks_sub', function()
+  it('substitutes multiple matches in a line', function()
     -- do_sub in ex_cmds.c
     feed('ddi3x3x3<esc>')
     set_extmark(ns, marks[1], 0, 0)
@@ -932,7 +1011,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[3], 0, 4, 0, 8)
   end)
 
-  it('substitions over multiple lines with newline in pattern #extmarks_sub', function()
+  it('substitions over multiple lines with newline in pattern', function()
     feed('A<cr>67890<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 3)
     set_extmark(ns, marks[2], 0, 4)
@@ -947,7 +1026,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 2, 0, 1, 0)
   end)
 
-  it('inserting #extmarks_sub', function()
+  it('inserting', function()
     feed('A<cr>67890<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 3)
     set_extmark(ns, marks[2], 0, 4)
@@ -964,7 +1043,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[6], 1, 2, 0, 5)
   end)
 
-  it('substitions with multiple newlines in pattern #extmarks_sub', function()
+  it('substitions with multiple newlines in pattern', function()
     feed('A<cr>67890<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 4)
     set_extmark(ns, marks[2], 0, 5)
@@ -979,7 +1058,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 2, 0, 0, 6)
   end)
 
-  it('substitions over multiple lines with replace in substition #extmarks_sub', function()
+  it('substitions over multiple lines with replace in substition', function()
     feed('A<cr>67890<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 1)
     set_extmark(ns, marks[2], 0, 2)
@@ -997,7 +1076,7 @@ describe('API/extmarks', function()
     eq({1, 3}, curbufmeths.get_extmark_by_id(ns, marks[3]))
   end)
 
-  it('substitions over multiple lines with replace in substition #extmarks_sub', function()
+  it('substitions over multiple lines with replace in substition', function()
     feed('A<cr>x3<cr>xx<esc>')
     set_extmark(ns, marks[1], 1, 0)
     set_extmark(ns, marks[2], 1, 1)
@@ -1008,7 +1087,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[3], 1, 2, 2, 0)
   end)
 
-  it('substitions over multiple lines with replace in substition #extmarks_sub', function()
+  it('substitions over multiple lines with replace in substition', function()
     feed('A<cr>x3<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 1)
     set_extmark(ns, marks[2], 0, 2)
@@ -1026,7 +1105,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[3], 0, 4, 1, 3)
   end)
 
-  it('substitions with newline in match and sub, delta is 0 #extmarks_sub', function()
+  it('substitions with newline in match and sub, delta is 0', function()
     feed('A<cr>67890<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 3)
     set_extmark(ns, marks[2], 0, 4)
@@ -1043,7 +1122,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[6], 2, 0, 2, 0)
   end)
 
-  it('substitions with newline in match and sub, delta > 0 #extmarks_sub', function()
+  it('substitions with newline in match and sub, delta > 0', function()
     feed('A<cr>67890<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 3)
     set_extmark(ns, marks[2], 0, 4)
@@ -1060,7 +1139,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[6], 2, 0, 3, 0)
   end)
 
-  it('substitions with newline in match and sub, delta < 0 #extmarks_sub', function()
+  it('substitions with newline in match and sub, delta < 0', function()
     feed('A<cr>67890<cr>xx<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 3)
     set_extmark(ns, marks[2], 0, 4)
@@ -1079,7 +1158,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[7], 3, 0, 2, 0)
   end)
 
-  it('substitions with backrefs, newline inserted into sub #extmarks_sub', function()
+  it('substitions with backrefs, newline inserted into sub', function()
     feed('A<cr>67890<cr>xx<cr>xx<esc>')
     set_extmark(ns, marks[1], 0, 3)
     set_extmark(ns, marks[2], 0, 4)
@@ -1096,7 +1175,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[6], 2, 0, 3, 0)
   end)
 
-  it('substitions a ^ #extmarks_sub', function()
+  it('substitions a ^', function()
     set_extmark(ns, marks[1], 0, 0)
     set_extmark(ns, marks[2], 0, 1)
     feed([[:s:^:x<cr>]])
@@ -1104,7 +1183,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[2], 0, 1, 0, 2)
   end)
 
-  it('using <c-a> without increase in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-a> without increase in order of magnitude', function()
     -- do_addsub in ops.c
     feed('ddiabc998xxx<esc>Tc')
     set_extmark(ns, marks[1], 0, 2)
@@ -1120,7 +1199,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 7, 0, 7)
   end)
 
-  it('using <c-a> when increase in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-a> when increase in order of magnitude', function()
     -- do_addsub in ops.c
     feed('ddiabc999xxx<esc>Tc')
     set_extmark(ns, marks[1], 0, 2)
@@ -1136,7 +1215,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 7, 0, 8)
   end)
 
-  it('using <c-a> when negative and without decrease in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-a> when negative and without decrease in order of magnitude', function()
     feed('ddiabc-999xxx<esc>T-')
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -1151,7 +1230,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 8, 0, 8)
   end)
 
-  it('using <c-a> when negative and decrease in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-a> when negative and decrease in order of magnitude', function()
     feed('ddiabc-1000xxx<esc>T-')
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -1166,7 +1245,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 9, 0, 8)
   end)
 
-  it('using <c-x> without decrease in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-x> without decrease in order of magnitude', function()
     -- do_addsub in ops.c
     feed('ddiabc999xxx<esc>Tc')
     set_extmark(ns, marks[1], 0, 2)
@@ -1182,7 +1261,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 7, 0, 7)
   end)
 
-  it('using <c-x> when decrease in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-x> when decrease in order of magnitude', function()
     -- do_addsub in ops.c
     feed('ddiabc1000xxx<esc>Tc')
     set_extmark(ns, marks[1], 0, 2)
@@ -1198,7 +1277,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 8, 0, 7)
   end)
 
-  it('using <c-x> when negative and without increase in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-x> when negative and without increase in order of magnitude', function()
     feed('ddiabc-998xxx<esc>T-')
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -1213,7 +1292,7 @@ describe('API/extmarks', function()
     check_undo_redo(ns, marks[5], 0, 8, 0, 8)
   end)
 
-  it('using <c-x> when negative and increase in order of magnitude #extmarks_inc_dec', function()
+  it('using <c-x> when negative and increase in order of magnitude', function()
     feed('ddiabc-999xxx<esc>T-')
     set_extmark(ns, marks[1], 0, 2)
     set_extmark(ns, marks[2], 0, 3)
@@ -1236,7 +1315,7 @@ describe('API/extmarks', function()
     eq("Invalid ns_id", pcall_err(curbufmeths.get_extmark_by_id, ns_invalid, marks[1]))
   end)
 
-  it('when col = line-length, set the mark on eol #extmarks', function()
+  it('when col = line-length, set the mark on eol', function()
     set_extmark(ns, marks[1], 0, -1)
     local rv = curbufmeths.get_extmark_by_id(ns, marks[1])
     eq({0, init_text:len()}, rv)
@@ -1246,19 +1325,19 @@ describe('API/extmarks', function()
     eq({0, init_text:len()}, rv)
   end)
 
-  it('when col = line-length, set the mark on eol #extmarks', function()
+  it('when col = line-length, set the mark on eol', function()
     local invalid_col = init_text:len() + 1
     eq("col value outside range", pcall_err(set_extmark, ns, marks[1], 0, invalid_col))
   end)
 
-  it('fails when line > line_count #extmarks', function()
+  it('fails when line > line_count', function()
     local invalid_col = init_text:len() + 1
     local invalid_lnum = 3
     eq('line value outside range', pcall_err(set_extmark, ns, marks[1], invalid_lnum, invalid_col))
     eq({}, curbufmeths.get_extmark_by_id(ns, marks[1]))
   end)
 
-  it('bug from check_col in extmark_set #extmarks_sub', function()
+  it('bug from check_col in extmark_set', function()
     -- This bug was caused by extmark_set always using check_col. check_col
     -- always uses the current buffer. This wasn't working during undo so we
     -- now use check_col and check_lnum only when they are required.
@@ -1282,6 +1361,16 @@ describe('API/extmarks', function()
     local id = bufmeths.set_extmark(buf, ns, 0, 1, 0, {})
     eq({{id, 1, 0}}, bufmeths.get_extmarks(buf, ns, 0, -1, {}))
   end)
+
+  it('does not crash with append/delete/undo seqence', function()
+     meths.exec([[
+      let ns = nvim_create_namespace('myplugin')
+      call nvim_buf_set_extmark(0, ns, 0, 0, 0, {})
+      call append(0, '')
+      %delete
+      undo]],false)
+    eq(2, meths.eval('1+1')) -- did not crash
+  end)
 end)
 
 describe('Extmarks buffer api with many marks', function()
@@ -1326,12 +1415,12 @@ describe('Extmarks buffer api with many marks', function()
     return marks
   end
 
-  it("can get marks #extmarks", function()
+  it("can get marks", function()
     eq(ns_marks[ns1], get_marks(ns1))
     eq(ns_marks[ns2], get_marks(ns2))
   end)
 
-  it("can clear all marks in ns #extmarks", function()
+  it("can clear all marks in ns", function()
     curbufmeths.clear_namespace(ns1, 0, -1)
     eq({}, get_marks(ns1))
     eq(ns_marks[ns2], get_marks(ns2))
@@ -1340,7 +1429,7 @@ describe('Extmarks buffer api with many marks', function()
     eq({}, get_marks(ns2))
   end)
 
-  it("can clear line range #extmarks", function()
+  it("can clear line range", function()
     curbufmeths.clear_namespace(ns1, 10, 20)
     for id, mark in pairs(ns_marks[ns1]) do
       if 10 <= mark[1] and mark[1] < 20 then
@@ -1351,7 +1440,7 @@ describe('Extmarks buffer api with many marks', function()
     eq(ns_marks[ns2], get_marks(ns2))
   end)
 
-  it("can delete line #extmarks", function()
+  it("can delete line", function()
     feed('10Gdd')
     for _, marks in pairs(ns_marks) do
       for id, mark in pairs(marks) do
@@ -1366,7 +1455,7 @@ describe('Extmarks buffer api with many marks', function()
     eq(ns_marks[ns2], get_marks(ns2))
   end)
 
-  it("can delete lines #extmarks", function()
+  it("can delete lines", function()
     feed('10G10dd')
     for _, marks in pairs(ns_marks) do
       for id, mark in pairs(marks) do
@@ -1381,7 +1470,7 @@ describe('Extmarks buffer api with many marks', function()
     eq(ns_marks[ns2], get_marks(ns2))
   end)
 
-  it("can wipe buffer #extmarks", function()
+  it("can wipe buffer", function()
     command('bwipe!')
     eq({}, get_marks(ns1))
     eq({}, get_marks(ns2))
diff --git a/test/functional/ui/bufhl_spec.lua b/test/functional/ui/bufhl_spec.lua
index f589bb0e83..3cb592c714 100644
--- a/test/functional/ui/bufhl_spec.lua
+++ b/test/functional/ui/bufhl_spec.lua
@@ -5,6 +5,7 @@ local clear, feed, insert = helpers.clear, helpers.feed, helpers.insert
 local command, neq = helpers.command, helpers.neq
 local meths = helpers.meths
 local curbufmeths, eq = helpers.curbufmeths, helpers.eq
+local pcall_err = helpers.pcall_err
 
 describe('Buffer highlighting', function()
   local screen
@@ -34,6 +35,7 @@ describe('Buffer highlighting', function()
       [17] = {foreground = Screen.colors.Magenta, background = Screen.colors.LightRed},
       [18] = {background = Screen.colors.LightRed},
       [19] = {foreground = Screen.colors.Blue1, background = Screen.colors.LightRed},
+      [20] = {underline = true, bold = true, foreground = Screen.colors.Cyan4},
     })
   end)
 
@@ -205,17 +207,116 @@ describe('Buffer highlighting', function()
                                                 |
       ]])
 
-      command(':3move 4')
-      screen:expect([[
+      -- TODO(bfedl): this behaves a bit weirdly due to the highlight on
+      -- the deleted line wrapping around. we should invalidate
+      -- highlights when they are completely inside deleted text
+      command('3move 4')
+      screen:expect{grid=[[
         a {5:longer} example                        |
                                                 |
+        {8:from different sources}                  |
+        {8:^in }{20:order}{8: to demonstrate}                 |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+                                                |
+      ]]}
+      --screen:expect([[
+      --  a {5:longer} example                        |
+      --                                          |
+      --  {9:from }{8:diff}{7:erent} sources                  |
+      --  ^in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+      --  {1:~                                       }|
+      --  {1:~                                       }|
+      --  {1:~                                       }|
+      --                                          |
+      --]])
+
+      command('undo')
+      screen:expect{grid=[[
+        a {5:longer} example                        |
+        ^                                        |
+        in {6:order} to {7:de}{5:monstr}{7:ate}                 |
         {9:from }{8:diff}{7:erent} sources                  |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+        1 change; before #4  {MATCH:.*}|
+      ]]}
+
+      command('undo')
+      screen:expect{grid=[[
+        ^a {5:longer} example                        |
+        in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {9:from }{8:diff}{7:erent} sources                  |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+        1 line less; before #3  {MATCH:.*}|
+      ]]}
+
+      command('undo')
+      screen:expect{grid=[[
+        a {5:longer} example                        |
+        in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {7:^combin}{8:ing}{9: hi}ghlights                    |
+        {9:from }{8:diff}{7:erent} sources                  |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+        1 more line; before #2  {MATCH:.*}|
+      ]]}
+    end)
+
+    it('and moving lines around', function()
+      command('2move 3')
+      screen:expect{grid=[[
+        a {5:longer} example                        |
+        {7:combin}{8:ing}{9: hi}ghlights                    |
         ^in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
         {1:~                                       }|
         {1:~                                       }|
                                                 |
-      ]])
+      ]]}
+
+      command('1,2move 4')
+      screen:expect{grid=[[
+        in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {9:from }{8:diff}{7:erent} sources                  |
+        a {5:longer} example                        |
+        {7:^combin}{8:ing}{9: hi}ghlights                    |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+                                                |
+      ]]}
+
+      command('undo')
+      screen:expect{grid=[[
+        a {5:longer} example                        |
+        {7:combin}{8:ing}{9: hi}ghlights                    |
+        ^in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {9:from }{8:diff}{7:erent} sources                  |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+        2 change3; before #3  {MATCH:.*}|
+      ]]}
+
+      command('undo')
+      screen:expect{grid=[[
+        a {5:longer} example                        |
+        ^in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {7:combin}{8:ing}{9: hi}ghlights                    |
+        {9:from }{8:diff}{7:erent} sources                  |
+        {1:~                                       }|
+        {1:~                                       }|
+        {1:~                                       }|
+        1 change; before #2  {MATCH:.*}|
+      ]]}
     end)
 
     it('and adjusting columns', function()
@@ -272,7 +373,7 @@ describe('Buffer highlighting', function()
       feed('u')
       screen:expect{grid=[[
         a {5:longer} example                        |
-        in {6:ordAAAAr} to^ demonstrate              |
+        in {6:ordAAAAr} to^ {7:de}{5:monstr}{7:ate}              |
         {7:combin}{8:ing}{9: hi}ghlights                    |
         {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
@@ -284,7 +385,7 @@ describe('Buffer highlighting', function()
       feed('u')
       screen:expect{grid=[[
         a {5:longer} example                        |
-        in {6:ord^er} to demonstrate                 |
+        in {6:ord^er} to {7:de}{5:monstr}{7:ate}                 |
         {7:combin}{8:ing}{9: hi}ghlights                    |
         {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
@@ -292,14 +393,14 @@ describe('Buffer highlighting', function()
         {1:~                                       }|
         1 change; before #3  {MATCH:.*}|
       ]]}
-      end)
+    end)
 
     it('and joining lines', function()
       feed('ggJJJ')
       screen:expect{grid=[[
         a {5:longer} example in {6:order} to {7:de}{5:monstr}{7:ate}|
-        {7: combin}{8:ing hi}{7:ghlights^ }{8:from diff}{7:erent sou}|
-        {7:rces}                                    |
+         {7:combin}{8:ing}{9: hi}ghlights^ {9:from }{8:diff}{7:erent} sou|
+        rces                                    |
         {1:~                                       }|
         {1:~                                       }|
         {1:~                                       }|
@@ -307,13 +408,12 @@ describe('Buffer highlighting', function()
                                                 |
       ]]}
 
-      -- TODO(bfredl): perhaps better undo
       feed('uuu')
       screen:expect{grid=[[
-        ^a longer example                        |
-        in order to demonstrate                 |
-        combining highlights                    |
-        from different sources                  |
+        ^a {5:longer} example                        |
+        in {6:order} to {7:de}{5:monstr}{7:ate}                 |
+        {7:combin}{8:ing}{9: hi}ghlights                    |
+        {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
         {1:~                                       }|
         {1:~                                       }|
@@ -334,25 +434,23 @@ describe('Buffer highlighting', function()
         {7:-- INSERT --}                            |
       ]]}
 
-      -- TODO(bfredl): keep both "parts" after split, requires proper extmark ranges
       feed('<esc>tsi<cr>')
       screen:expect{grid=[[
         a {5:longer} example                        |
         in {6:order}                                |
          to {7:de}{5:mo}                                |
-        ^nstrate                                 |
+        {5:^nstr}{7:ate}                                 |
         {7:combin}{8:ing}{9: hi}ghlights                    |
         {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
         {7:-- INSERT --}                            |
       ]]}
 
-      -- TODO(bfredl): perhaps better undo
       feed('<esc>u')
       screen:expect{grid=[[
         a {5:longer} example                        |
         in {6:order}                                |
-         to demo{7:^nstrat}{8:e}                         |
+         to {7:de}{5:mo^nstr}{7:ate}                         |
         {7:combin}{8:ing}{9: hi}ghlights                    |
         {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
@@ -363,7 +461,7 @@ describe('Buffer highlighting', function()
       feed('<esc>u')
       screen:expect{grid=[[
         a {5:longer} example                        |
-        in order^ to demonstrate                 |
+        in {6:order}^ to {7:de}{5:monstr}{7:ate}                 |
         {7:combin}{8:ing}{9: hi}ghlights                    |
         {9:from }{8:diff}{7:erent} sources                  |
         {1:~                                       }|
@@ -374,7 +472,7 @@ describe('Buffer highlighting', function()
     end)
   end)
 
-  it('prioritizes latest added highlight', function()
+  pending('prioritizes latest added highlight', function()
     insert([[
       three overlapping colors]])
     add_highlight(0, "Identifier", 0, 6, 17)
@@ -405,6 +503,37 @@ describe('Buffer highlighting', function()
     ]])
   end)
 
+  it('prioritizes earlier highlight groups (TEMP)', function()
+    insert([[
+      three overlapping colors]])
+    add_highlight(0, "Identifier", 0, 6, 17)
+    add_highlight(0, "String", 0, 14, 23)
+    local id = add_highlight(0, "Special", 0, 0, 9)
+
+    screen:expect{grid=[[
+      {4:three }{6:overlapp}{2:ing color}^s                |
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+                                              |
+    ]]}
+
+    clear_namespace(id, 0, 1)
+    screen:expect{grid=[[
+      three {6:overlapp}{2:ing color}^s                |
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+      {1:~                                       }|
+                                              |
+    ]]}
+  end)
+
   it('works with multibyte text', function()
     insert([[
       Ta båten över sjön!]])
@@ -451,7 +580,7 @@ describe('Buffer highlighting', function()
     ]])
   end)
 
-  describe('virtual text annotations', function()
+  describe('virtual text decorations', function()
     local set_virtual_text = curbufmeths.set_virtual_text
     local id1, id2
     before_each(function()
@@ -529,16 +658,35 @@ describe('Buffer highlighting', function()
       ]])
 
       feed("2Gdd")
-      screen:expect([[
+      -- TODO(bfredl): currently decorations get moved from a deleted line
+      -- to the next one. We might want to add "invalidation" when deleting
+      -- over a decoration.
+      screen:expect{grid=[[
         1 + 2                                   |
         ^5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5|
-        , 5, 5, 5, 5, 5, 5,  Lorem ipsum dolor s|
+        , 5, 5, 5, 5, 5, 5,  {12:暗x事zz速野谷質結育}|
         x = 4                                   |
         {1:~                                       }|
         {1:~                                       }|
         {1:~                                       }|
                                                 |
-      ]])
+      ]]}
+      --screen:expect([[
+      --  1 + 2                                   |
+      --  ^5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5|
+      --  , 5, 5, 5, 5, 5, 5,  Lorem ipsum dolor s|
+      --  x = 4                                   |
+      --  {1:~                                       }|
+      --  {1:~                                       }|
+      --  {1:~                                       }|
+      --                                          |
+      --]])
+    end)
+
+    it('validates contents', function()
+      -- this used to leak memory
+      eq('Chunk is not an array', pcall_err(set_virtual_text, id1, 0, {"texty"}, {}))
+      eq('Chunk is not an array', pcall_err(set_virtual_text, id1, 0, {{"very"}, "texty"}, {}))
     end)
 
     it('can be retrieved', function()
@@ -548,7 +696,9 @@ describe('Buffer highlighting', function()
       local s1 = {{'Köttbullar', 'Comment'}, {'Kräuterbutter'}}
       local s2 = {{'こんにちは', 'Comment'}}
 
-      set_virtual_text(-1, 0, s1, {})
+      -- TODO: only a virtual text from the same ns curretly overrides
+      -- an existing virtual text. We might add a prioritation system.
+      set_virtual_text(id1, 0, s1, {})
       eq(s1, get_virtual_text(0))
 
       set_virtual_text(-1, line_count(), s2, {})