extmarks/bufhl: reimplement using new marktree data structure

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

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

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

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

fixes #11598

1 files changed, 0 insertions, 431 deletions

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.
  */