feat(extmark): support proper multiline ranges

The removes the previous restriction that nvim_buf_set_extmark()
could not be used to highlight arbitrary multi-line regions

The problem can be summarized as follows: let's assume an extmark with a
hl_group is placed covering the region (5,0) to (50,0) Now, consider
what happens if nvim needs to redraw a window covering the lines 20-30.
It needs to be able to ask the marktree what extmarks cover this region,
even if they don't begin or end here.

Therefore the marktree needs to be augmented with the information covers
a point, not just what marks begin or end there. To do this, we augment
each node with a field "intersect" which is a set the ids of the
marks which overlap this node, but only if it is not part of the set of
any parent. This ensures the number of nodes that need to be explicitly
marked grows only logarithmically with the total number of explicitly
nodes (and thus the number of of overlapping marks).

Thus we can quickly iterate all marks which overlaps any query position
by looking up what leaf node contains that position. Then we only need
to consider all "start" marks within that leaf node, and the "intersect"
set of that node and all its parents.

Now, and the major source of complexity is that the tree restructuring
operations (to ensure that each node has T-1 <= size <= 2*T-1) also need
to update these sets. If a full inner node is split in two, one of the
new parents might start to completely overlap some ranges and its ids
will need to be moved from its children's sets to its own set.
Similarly, if two undersized nodes gets joined into one, it might no
longer completely overlap some ranges, and now the children which do
needs to have the have the ids in its set instead. And then there are
the pivots! Yes the pivot operations when a child gets moved from one
parent to another.

1 files changed, 58 insertions, 26 deletions

diff --git a/src/nvim/marktree.h b/src/nvim/marktree.h
index cd56115b58..f53a54f3cc 100644
--- a/src/nvim/marktree.h
+++ b/src/nvim/marktree.h
@@ -6,29 +6,37 @@
 #include <stddef.h>
 #include <stdint.h>
 
+#include "klib/kvec.h"
 #include "nvim/assert.h"
 #include "nvim/garray.h"
 #include "nvim/map.h"
 #include "nvim/pos.h"
 #include "nvim/types.h"
 
+// only for debug functions:
+#include "api/private/defs.h"
+
 struct mtnode_s;
 
 #define MT_MAX_DEPTH 20
 #define MT_BRANCH_FACTOR 10
+// note max branch is actually 2*MT_BRANCH_FACTOR
+// and strictly this is ceil(log2(2*MT_BRANCH_FACTOR + 1))
+// as we need a pseudo-index for "right before this node"
+#define MT_LOG2_BRANCH 5
 
 typedef struct {
   int32_t row;
   int32_t col;
-} mtpos_t;
-#define mtpos_t(r, c) ((mtpos_t){ .row = (r), .col = (c) })
+} MTPos;
+#define MTPos(r, c) ((MTPos){ .row = (r), .col = (c) })
 
-typedef struct mtnode_s mtnode_t;
+typedef struct mtnode_s MTNode;
 
 typedef struct {
-  mtpos_t pos;
+  MTPos pos;
   int lvl;
-  mtnode_t *node;
+  MTNode *x;
   int i;
   struct {
     int oldcol;
@@ -36,33 +44,43 @@ typedef struct {
   } s[MT_MAX_DEPTH];
 
   size_t intersect_idx;
-  mtpos_t intersect_pos;
+  MTPos intersect_pos;
+  MTPos intersect_pos_x;
 } MarkTreeIter;
 
-#define marktree_itr_valid(itr) ((itr)->node != NULL)
+#define marktree_itr_valid(itr) ((itr)->x != NULL)
 
 // Internal storage
 //
 // NB: actual marks have flags > 0, so we can use (row,col,0) pseudo-key for
 // "space before (row,col)"
 typedef struct {
-  mtpos_t pos;
+  MTPos pos;
   uint32_t ns;
   uint32_t id;
   int32_t hl_id;
   uint16_t flags;
   uint16_t priority;
   Decoration *decor_full;
-} mtkey_t;
-#define MT_INVALID_KEY (mtkey_t) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
+} MTKey;
+
+typedef struct {
+  MTKey start;
+  MTPos end_pos;
+  bool end_right_gravity;
+} MTPair;
+
+#define MT_INVALID_KEY (MTKey) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
 
 #define MT_FLAG_REAL (((uint16_t)1) << 0)
 #define MT_FLAG_END (((uint16_t)1) << 1)
 #define MT_FLAG_PAIRED (((uint16_t)1) << 2)
-#define MT_FLAG_HL_EOL (((uint16_t)1) << 3)
+// orphaned: the other side of this paired mark was deleted. this mark must be deleted very soon!
+#define MT_FLAG_ORPHANED (((uint16_t)1) << 3)
+#define MT_FLAG_HL_EOL (((uint16_t)1) << 4)
 
 #define DECOR_LEVELS 4
-#define MT_FLAG_DECOR_OFFSET 4
+#define MT_FLAG_DECOR_OFFSET 5
 #define MT_FLAG_DECOR_MASK (((uint16_t)(DECOR_LEVELS - 1)) << MT_FLAG_DECOR_OFFSET)
 
 // next flag is (((uint16_t)1) << 6)
@@ -73,39 +91,44 @@ typedef struct {
 
 #define MT_FLAG_EXTERNAL_MASK (MT_FLAG_DECOR_MASK | MT_FLAG_RIGHT_GRAVITY | MT_FLAG_HL_EOL)
 
-#define MARKTREE_END_FLAG (((uint64_t)1) << 63)
+// this is defined so that start and end of the same range have adjacent ids
+#define MARKTREE_END_FLAG ((uint64_t)1)
 static inline uint64_t mt_lookup_id(uint32_t ns, uint32_t id, bool enda)
 {
-  return (uint64_t)ns << 32 | id | (enda ? MARKTREE_END_FLAG : 0);
+  return (uint64_t)ns << 33 | (id <<1) | (enda ? MARKTREE_END_FLAG : 0);
 }
-#undef MARKTREE_END_FLAG
 
-static inline uint64_t mt_lookup_key(mtkey_t key)
+static inline uint64_t mt_lookup_key_side(MTKey key, bool end)
+{
+  return mt_lookup_id(key.ns, key.id, end);
+}
+
+static inline uint64_t mt_lookup_key(MTKey key)
 {
   return mt_lookup_id(key.ns, key.id, key.flags & MT_FLAG_END);
 }
 
-static inline bool mt_paired(mtkey_t key)
+static inline bool mt_paired(MTKey key)
 {
   return key.flags & MT_FLAG_PAIRED;
 }
 
-static inline bool mt_end(mtkey_t key)
+static inline bool mt_end(MTKey key)
 {
   return key.flags & MT_FLAG_END;
 }
 
-static inline bool mt_start(mtkey_t key)
+static inline bool mt_start(MTKey key)
 {
   return mt_paired(key) && !mt_end(key);
 }
 
-static inline bool mt_right(mtkey_t key)
+static inline bool mt_right(MTKey key)
 {
   return key.flags & MT_FLAG_RIGHT_GRAVITY;
 }
 
-static inline uint8_t marktree_decor_level(mtkey_t key)
+static inline uint8_t marktree_decor_level(MTKey key)
 {
   return (uint8_t)((key.flags&MT_FLAG_DECOR_MASK) >> MT_FLAG_DECOR_OFFSET);
 }
@@ -117,18 +140,27 @@ static inline uint16_t mt_flags(bool right_gravity, uint8_t decor_level)
                     | (decor_level << MT_FLAG_DECOR_OFFSET));
 }
 
+typedef kvec_withinit_t(uint64_t, 4) Intersection;
+
 struct mtnode_s {
   int32_t n;
-  int32_t level;
+  int16_t level;
+  int16_t p_idx;  // index in parent
+  Intersection intersect;
   // TODO(bfredl): we could consider having a only-sometimes-valid
   // index into parent for faster "cached" lookup.
-  mtnode_t *parent;
-  mtkey_t key[2 * MT_BRANCH_FACTOR - 1];
-  mtnode_t *ptr[];
+  MTNode *parent;
+  MTKey key[2 * MT_BRANCH_FACTOR - 1];
+  MTNode *ptr[];
 };
 
+static inline uint64_t mt_dbg_id(uint64_t id)
+{
+  return (id>>1)&0xffffffff;
+}
+
 typedef struct {
-  mtnode_t *root;
+  MTNode *root;
   size_t n_keys, n_nodes;
   // TODO(bfredl): the pointer to node could be part of the larger
   // Map(uint64_t, ExtmarkItem) essentially;