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;