extmark: refiy "Decoration" abstraction

one very important thought

5 files changed, 157 insertions, 135 deletions

diff --git a/src/nvim/api/buffer.c b/src/nvim/api/buffer.c
index 8e61976c4b..e813fc1dd4 100644
--- a/src/nvim/api/buffer.c
+++ b/src/nvim/api/buffer.c
@@ -1318,7 +1318,8 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer id,
   }
 
   id_num = extmark_set(buf, (uint64_t)ns_id, id_num,
-                       (int)line, (colnr_T)col, kExtmarkUndo);
+                       (int)line, (colnr_T)col,
+                       -1, -1, NULL, kExtmarkUndo);
 
   return (Integer)id_num;
 }
@@ -1425,10 +1426,13 @@ Integer nvim_buf_add_highlight(Buffer buffer,
     end_line++;
   }
 
-  extmark_add_decoration(buf, ns_id, hlg_id,
-                         (int)line, (colnr_T)col_start,
-                         end_line, (colnr_T)col_end,
-                         VIRTTEXT_EMPTY);
+  Decoration *decor = xcalloc(1, sizeof(*decor));
+  decor->hl_id = hlg_id;
+
+  ns_id = extmark_set(buf, ns_id, 0,
+                      (int)line, (colnr_T)col_start,
+                      end_line, (colnr_T)col_end,
+                      decor, kExtmarkUndo);
   return src_id;
 }
 
@@ -1592,9 +1596,10 @@ Integer nvim_buf_set_virtual_text(Buffer buffer,
     return src_id;
   }
 
-  extmark_add_decoration(buf, ns_id, 0,
-                         (int)line, 0, -1, -1,
-                         virt_text);
+  Decoration *decor = xcalloc(1, sizeof(*decor));
+  decor->virt_text = virt_text;
+
+  extmark_set(buf, ns_id, 0, (int)line, 0, -1, -1, decor, kExtmarkUndo);
   return src_id;
 }
 
@@ -1695,9 +1700,14 @@ Integer nvim__buf_add_decoration(Buffer buffer, Integer ns_id, String hl_group,
     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);
+  Decoration *decor = xcalloc(1, sizeof(*decor));
+  decor->hl_id = hlg_id;
+  decor->virt_text = vt;
+
+  uint64_t mark_id = extmark_set(buf, (uint64_t)ns_id, 0,
+                                 (int)start_row, (colnr_T)start_col,
+                                 (int)end_row, (colnr_T)end_col, decor,
+                                 kExtmarkUndo);
   return (Integer)mark_id;
 }
 
diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c
index 1457a1172d..ce8da43999 100644
--- a/src/nvim/extmark.c
+++ b/src/nvim/extmark.c
@@ -1,29 +1,24 @@
 // This is an open source non-commercial project. Dear PVS-Studio, please check
 // it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
 
-// Implements extended marks for plugins. Each mark exists in a btree of
-// lines containing btrees of columns.
+// Implements extended marks for plugins. Marks sit in a MarkTree
+// datastructure which provides both efficient mark insertations/lookups
+// and adjustment to text changes. See marktree.c for more details.
 //
-// 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_splice. Additionally mark_adjust
-// might adjust extmarks to line inserts/deletes.
+// Marks are moved by calls to extmark_splice. Some standard interfaces
+// mark_adjust and inserted_bytes already adjust marks, check if these are
+// being used before adding extmark_splice calls!
 //
 // Undo/Redo of marks is implemented by storing the call arguments to
 // 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.
+// We have to copy extmark positions when the extmarks are within a
+// deleted/changed region.
 //
 // Marks live in namespaces that allow plugins/users to segregate marks
 // from other users.
 //
-// For possible ideas for efficency improvements see:
-// http://blog.atom.io/2015/06/16/optimizing-an-important-atom-primitive.html
-// TODO(bfredl): These ideas could be used for an enhanced btree, which
-// wouldn't need separate line and column layers.
-// Other implementations exist in gtk and tk toolkits.
-//
 // Deleting marks only happens when explicitly calling extmark_del, deleteing
 // over a range of marks will only move the marks. Deleting on a mark will
 // leave it in same position unless it is on the EOL of a line.
@@ -71,7 +66,8 @@ static ExtmarkNs *buf_ns_ref(buf_T *buf, uint64_t ns_id, bool put) {
 /// must not be used during iteration!
 /// @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)
+                     int row, colnr_T col, int end_row, colnr_T end_col,
+                     Decoration *decor, ExtmarkOp op)
 {
   ExtmarkNs *ns = buf_ns_ref(buf, ns_id, true);
   mtpos_t old_pos;
@@ -82,7 +78,7 @@ uint64_t extmark_set(buf_T *buf, uint64_t ns_id, uint64_t id,
   } else {
     uint64_t old_mark = map_get(uint64_t, uint64_t)(ns->map, id);
     if (old_mark) {
-      if (old_mark & MARKTREE_PAIRED_FLAG) {
+      if (old_mark & MARKTREE_PAIRED_FLAG || end_row > -1) {
         extmark_del(buf, ns_id, id);
       } else {
         // TODO(bfredl): we need to do more if "revising" a decoration mark.
@@ -90,7 +86,12 @@ uint64_t extmark_set(buf_T *buf, uint64_t ns_id, uint64_t id,
         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);
+          ExtmarkItem it = map_del(uint64_t, ExtmarkItem)(buf->b_extmark_index,
+                                                          old_mark);
+          if (it.decor) {
+            decoration_redraw(buf, row, row, it.decor);
+            free_decoration(it.decor);
+          }
           mark = marktree_revise(buf->b_marktree, itr);
           goto revised;
         }
@@ -101,11 +102,17 @@ uint64_t extmark_set(buf_T *buf, uint64_t ns_id, uint64_t id,
     }
   }
 
-  mark = marktree_put(buf->b_marktree, row, col, true);
+  if (end_row > -1) {
+    mark = marktree_put_pair(buf->b_marktree,
+                             row, col, true,
+                             end_row, end_col, false);
+  } else {
+    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 });
+                                 (ExtmarkItem){ ns_id, id, decor });
   map_put(uint64_t, uint64_t)(ns->map, id, mark);
 
   if (op != kExtmarkNoUndo) {
@@ -114,6 +121,10 @@ revised:
     // adding new marks to old undo headers.
     u_extmark_set(buf, mark, row, col);
   }
+
+  if (decor) {
+    decoration_redraw(buf, row, end_row > -1 ? end_row : row, decor);
+  }
   return id;
 }
 
@@ -152,27 +163,23 @@ bool extmark_del(buf_T *buf, uint64_t ns_id, uint64_t id)
   assert(pos.row >= 0);
   marktree_del_itr(buf->b_marktree, itr, false);
   ExtmarkItem item = map_get(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark);
+  mtpos_t pos2 = pos;
 
   if (mark & MARKTREE_PAIRED_FLAG) {
-    mtpos_t pos2 = marktree_lookup(buf->b_marktree,
-                                   mark|MARKTREE_END_FLAG, itr);
+    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);
+  if (item.decor) {
+    decoration_redraw(buf, pos.row, pos2.row, item.decor);
+    free_decoration(item.decor);
   }
-  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;
 }
 
@@ -202,9 +209,11 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id,
   }
 
   // the value is either zero or the lnum (row+1) if highlight was present.
-  static Map(uint64_t, uint64_t) *delete_set = NULL;
+  static Map(uint64_t, ssize_t) *delete_set = NULL;
+  typedef struct { Decoration *decor; int row1; } DecorItem;
+  static kvec_t(DecorItem) decors;
   if (delete_set == NULL) {
-    delete_set = map_new(uint64_t, uint64_t)();
+    delete_set = map_new(uint64_t, ssize_t)();
   }
 
   MarkTreeIter itr[1] = { 0 };
@@ -216,14 +225,16 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id,
         || (mark.row == u_row && mark.col > u_col)) {
       break;
     }
-    uint64_t *del_status = map_ref(uint64_t, uint64_t)(delete_set, mark.id,
-                                                       false);
+    ssize_t *del_status = map_ref(uint64_t, ssize_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);
+      if (*del_status >= 0) {  // we had a decor_id
+        DecorItem it = kv_A(decors, *del_status);
+        decoration_redraw(buf, it.row1, mark.row, it.decor);
+        free_decoration(it.decor);
       }
+      map_del(uint64_t, ssize_t)(delete_set, mark.id);
       continue;
     }
 
@@ -233,15 +244,21 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id,
 
     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);
+        ssize_t decor_id = -1;
+        if (item.decor) {
+          // Save the decoration and the first pos. Clear the decoration
+          // later when we know the full range.
+          decor_id = (ssize_t)kv_size(decors);
+          kv_push(decors,
+                  ((DecorItem) { .decor = item.decor, .row1 = mark.row }));
+        }
+        map_put(uint64_t, ssize_t)(delete_set, other, decor_id);
+      } else if (item.decor) {
+        decoration_redraw(buf, mark.row, mark.row, item.decor);
+        free_decoration(item.decor);
       }
       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);
@@ -251,16 +268,20 @@ bool extmark_clear(buf_T *buf, uint64_t ns_id,
       marktree_itr_next(buf->b_marktree, itr);
     }
   }
-  uint64_t id, status;
-  map_foreach(delete_set, id, status, {
+  uint64_t id;
+  ssize_t decor_id;
+  map_foreach(delete_set, id, decor_id, {
     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);
+    if (decor_id >= 0) {
+      DecorItem it = kv_A(decors, decor_id);
+      decoration_redraw(buf, it.row1, pos.row, it.decor);
+      free_decoration(it.decor);
     }
   });
-  map_clear(uint64_t, uint64_t)(delete_set);
+  map_clear(uint64_t, ssize_t)(delete_set);
+  kv_size(decors) = 0;
   return marks_cleared;
 }
 
@@ -352,7 +373,7 @@ void extmark_free_all(buf_T *buf)
 
   map_foreach(buf->b_extmark_index, id, item, {
     (void)id;
-    clear_virttext(&item.virt_text);
+    free_decoration(item.decor);
   });
   map_free(uint64_t, ExtmarkItem)(buf->b_extmark_index);
   buf->b_extmark_index = NULL;
@@ -642,50 +663,6 @@ uint64_t src2ns(Integer *src_id)
   }
 }
 
-/// 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);
-  }
-
-  map_put(uint64_t, ExtmarkItem)(buf->b_extmark_index, mark, item);
-  map_put(uint64_t, uint64_t)(ns->map, item.mark_id, mark);
-
-  redraw_buf_range_later(buf, start_row+1,
-                         (end_row >= 0 ? end_row : start_row) + 1);
-  return item.mark_id;
-}
-
 /// Add highlighting to a buffer, bounded by two cursor positions,
 /// with an offset.
 ///
@@ -729,10 +706,30 @@ void bufhl_add_hl_pos_offset(buf_T *buf,
       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+end_off, hl_end,
-                                 VIRTTEXT_EMPTY);
+    Decoration *decor = xcalloc(1, sizeof(*decor));
+    decor->hl_id = hl_id;
+    (void)extmark_set(buf, (uint64_t)src_id, 0,
+                      (int)lnum-1, hl_start, (int)lnum-1+end_off, hl_end,
+                      decor, kExtmarkUndo);
+  }
+}
+
+void decoration_redraw(buf_T *buf, int row1, int row2, Decoration *decor)
+{
+  if (decor->hl_id && row2 >= row1) {
+    redraw_buf_range_later(buf, row1+1, row2+1);
+  }
+
+  if (kv_size(decor->virt_text)) {
+    redraw_buf_line_later(buf, row1+1);
+  }
+}
+
+void free_decoration(Decoration *decor)
+{
+  if (decor) {
+    clear_virttext(&decor->virt_text);
+    xfree(decor);
   }
 }
 
@@ -757,8 +754,8 @@ VirtText *extmark_find_virttext(buf_T *buf, int row, uint64_t ns_id)
     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;
+        && item->decor && kv_size(item->decor->virt_text)) {
+      return &item->decor->virt_text;
     }
     marktree_itr_next(buf->b_marktree, itr);
   }
@@ -787,7 +784,6 @@ bool decorations_redraw_start(buf_T *buf, int top_row,
     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;
     }
@@ -797,25 +793,30 @@ bool decorations_redraw_start(buf_T *buf, int top_row,
     uint64_t start_id = mark.id & ~MARKTREE_END_FLAG;
     ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
                                                        start_id, false);
+    if (!item || !item->decor) {
+    // TODO(bfredl): dedicated flag for being a decoration?
+      goto next_mark;
+    }
+    Decoration *decor = item->decor;
+
     if ((!(mark.id&MARKTREE_END_FLAG) && altpos.row < top_row
-         && item && !kv_size(item->virt_text))
+         && item && !kv_size(decor->virt_text))
         || ((mark.id&MARKTREE_END_FLAG) && altpos.row >= top_row)) {
       goto next_mark;
     }
 
-    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 {
-        range = (HlRange){ mark.row, mark.col, altpos.row,
-                           altpos.col, attr_id, vt };
-      }
-      kv_push(state->active, range);
+    int attr_id = decor->hl_id > 0 ? syn_id2attr(decor->hl_id) : 0;
+    VirtText *vt = kv_size(decor->virt_text) ? &decor->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 {
+      range = (HlRange){ mark.row, mark.col, altpos.row,
+                         altpos.col, attr_id, vt };
     }
+    kv_push(state->active, range);
+
 next_mark:
     if (marktree_itr_node_done(state->itr)) {
       break;
@@ -860,21 +861,24 @@ int decorations_redraw_col(buf_T *buf, int col, DecorationRedrawState *state)
 
     ExtmarkItem *item = map_ref(uint64_t, ExtmarkItem)(buf->b_extmark_index,
                                                        mark.id, false);
+    if (!item || !item->decor) {
+    // TODO(bfredl): dedicated flag for being a decoration?
+      goto next_mark;
+    }
+    Decoration *decor = item->decor;
 
     if (endpos.row < mark.row
         || (endpos.row == mark.row && endpos.col <= mark.col)) {
-      if (item && !kv_size(item->virt_text)) {
+      if (item && !kv_size(decor->virt_text)) {
         goto next_mark;
       }
     }
 
-    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 }));
-    }
+    int attr_id = decor->hl_id > 0 ? syn_id2attr(decor->hl_id) : 0;
+    VirtText *vt = kv_size(decor->virt_text) ? &decor->virt_text : NULL;
+    kv_push(state->active, ((HlRange){ mark.row, mark.col,
+                                       endpos.row, endpos.col,
+                                       attr_id, vt }));
 
 next_mark:
     marktree_itr_next(buf->b_marktree, state->itr);
diff --git a/src/nvim/extmark_defs.h b/src/nvim/extmark_defs.h
index c927048981..899fbdf38a 100644
--- a/src/nvim/extmark_defs.h
+++ b/src/nvim/extmark_defs.h
@@ -14,12 +14,19 @@ typedef kvec_t(VirtTextChunk) VirtText;
 
 typedef struct
 {
-  uint64_t ns_id;
-  uint64_t mark_id;
   int hl_id;  // highlight group
-  // TODO(bfredl): virt_text is pretty larger than the rest,
-  // pointer indirection?
   VirtText virt_text;
+  // TODO(bfredl): style, signs, etc
+} Decoration;
+
+typedef struct
+{
+  uint64_t ns_id;
+  uint64_t mark_id;
+  // TODO(bfredl): a lot of small allocations. Should probably use
+  // kvec_t(Decoration) as an arena. Alternatively, store ns_id/mark_id
+  // _inline_ in MarkTree and use the map only for decorations.
+  Decoration *decor;
 } ExtmarkItem;
 
 typedef struct undo_object ExtmarkUndoObject;
diff --git a/src/nvim/map.c b/src/nvim/map.c
index cba39f24b3..0c6bad7cb6 100644
--- a/src/nvim/map.c
+++ b/src/nvim/map.c
@@ -184,7 +184,7 @@ 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 }
+#define EXTMARK_ITEM_INITIALIZER { 0, 0, NULL }
 MAP_IMPL(uint64_t, ExtmarkItem, EXTMARK_ITEM_INITIALIZER)
 MAP_IMPL(handle_T, ptr_t, DEFAULT_INITIALIZER)
 #define MSGPACK_HANDLER_INITIALIZER { .fn = NULL, .fast = false }
diff --git a/src/nvim/screen.c b/src/nvim/screen.c
index 69de1de6b2..c68a90d6e3 100644
--- a/src/nvim/screen.c
+++ b/src/nvim/screen.c
@@ -2554,6 +2554,7 @@ win_line (
   }
 
   // If this line has a sign with line highlighting set line_attr.
+  // TODO(bfredl, vigoux): this should not take priority over decorations!
   v = buf_getsigntype(wp->w_buffer, lnum, SIGN_LINEHL, 0, 1);
   if (v != 0) {
     line_attr = sign_get_attr((int)v, SIGN_LINEHL);