Merge remote-tracking branch 'upstream/master' into userreguserreg

1 files changed, 126 insertions, 57 deletions

diff --git a/src/nvim/marktree.h b/src/nvim/marktree.h
index 5ce4b2cd24..c76359d3f9 100644
--- a/src/nvim/marktree.h
+++ b/src/nvim/marktree.h
@@ -1,140 +1,209 @@
-#ifndef NVIM_MARKTREE_H
-#define NVIM_MARKTREE_H
+#pragma once
 
-#include <assert.h>
 #include <stdbool.h>
 #include <stddef.h>
 #include <stdint.h>
 
-#include "nvim/assert.h"
-#include "nvim/garray.h"
-#include "nvim/map.h"
+#include "klib/kvec.h"
+#include "nvim/decoration_defs.h"
+#include "nvim/garray_defs.h"  // IWYU pragma: keep
 #include "nvim/map_defs.h"
-#include "nvim/pos.h"
-#include "nvim/types.h"
-
-struct mtnode_s;
+#include "nvim/pos_defs.h"  // IWYU pragma: keep
+// only for debug functions:
+#include "nvim/api/private/defs.h"  // IWYU pragma: keep
 
 #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;
+} MTPos;
+#define MTPos(r, c) ((MTPos){ .row = (r), .col = (c) })
 
-typedef struct mtnode_s mtnode_t;
-typedef struct {
-  int oldcol;
-  int i;
-} iterstate_t;
+typedef struct mtnode_s MTNode;
 
 typedef struct {
-  mtpos_t pos;
+  MTPos pos;
   int lvl;
-  mtnode_t *node;
+  MTNode *x;
   int i;
-  iterstate_t s[MT_MAX_DEPTH];
+  struct {
+    int oldcol;
+    int i;
+  } s[MT_MAX_DEPTH];
+
+  size_t intersect_idx;
+  MTPos intersect_pos;
+  MTPos intersect_pos_x;
 } MarkTreeIter;
 
+#define marktree_itr_valid(itr) ((itr)->x != NULL)
+// access raw key: flags in MT_FLAG_EXTERNAL_MASK and decor_data are safe to modify.
+#define mt_itr_rawkey(itr) ((itr)->x->key[(itr)->i])
+
 // 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 }
+  DecorInlineData decor_data;  // "ext" tag in flags
+} MTKey;
+
+typedef struct {
+  MTKey start;
+  MTPos end_pos;
+  bool end_right_gravity;
+} MTPair;
+
+#define MT_INVALID_KEY (MTKey) { { -1, -1 }, 0, 0, 0, { .hl = DECOR_HIGHLIGHT_INLINE_INIT } }
 
 #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)
-
-#define DECOR_LEVELS 4
-#define MT_FLAG_DECOR_OFFSET 4
-#define MT_FLAG_DECOR_MASK (((uint16_t)(DECOR_LEVELS - 1)) << MT_FLAG_DECOR_OFFSET)
-
-// next flag is (((uint16_t)1) << 6)
+// 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_NO_UNDO (((uint16_t)1) << 4)
+#define MT_FLAG_INVALIDATE (((uint16_t)1) << 5)
+#define MT_FLAG_INVALID (((uint16_t)1) << 6)
+// discriminant for union
+#define MT_FLAG_DECOR_EXT (((uint16_t)1) << 7)
+
+// TODO(bfredl): flags for decorations. These cover the cases where we quickly needs
+// to skip over irrelevant marks internally. When we refactor this more, also make all info
+// for ExtmarkType included here
+#define MT_FLAG_DECOR_HL (((uint16_t)1) << 8)
+#define MT_FLAG_DECOR_SIGNTEXT (((uint16_t)1) << 9)
+// TODO(bfredl): for now this means specifically number_hl, line_hl, cursorline_hl
+// needs to clean up the name.
+#define MT_FLAG_DECOR_SIGNHL (((uint16_t)1) << 10)
+#define MT_FLAG_DECOR_VIRT_LINES (((uint16_t)1) << 11)
+#define MT_FLAG_DECOR_VIRT_TEXT_INLINE (((uint16_t)1) << 12)
 
 // These _must_ be last to preserve ordering of marks
 #define MT_FLAG_RIGHT_GRAVITY (((uint16_t)1) << 14)
 #define MT_FLAG_LAST (((uint16_t)1) << 15)
 
-#define MT_FLAG_EXTERNAL_MASK (MT_FLAG_DECOR_MASK | MT_FLAG_RIGHT_GRAVITY | MT_FLAG_HL_EOL)
+#define MT_FLAG_DECOR_MASK  (MT_FLAG_DECOR_EXT| MT_FLAG_DECOR_HL | MT_FLAG_DECOR_SIGNTEXT \
+                             | MT_FLAG_DECOR_SIGNHL | MT_FLAG_DECOR_VIRT_LINES \
+                             | MT_FLAG_DECOR_VIRT_TEXT_INLINE)
 
-#define MARKTREE_END_FLAG (((uint64_t)1) << 63)
+#define MT_FLAG_EXTERNAL_MASK (MT_FLAG_DECOR_MASK | MT_FLAG_NO_UNDO \
+                               | MT_FLAG_INVALIDATE | MT_FLAG_INVALID)
+
+// 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 bool mt_no_undo(MTKey key)
+{
+  return key.flags & MT_FLAG_NO_UNDO;
+}
+
+static inline bool mt_invalidate(MTKey key)
+{
+  return key.flags & MT_FLAG_INVALIDATE;
+}
+
+static inline bool mt_invalid(MTKey key)
 {
-  return (uint8_t)((key.flags&MT_FLAG_DECOR_MASK) >> MT_FLAG_DECOR_OFFSET);
+  return key.flags & MT_FLAG_INVALID;
 }
 
-static inline uint16_t mt_flags(bool right_gravity, uint8_t decor_level)
+static inline bool mt_decor_any(MTKey key)
+{
+  return key.flags & MT_FLAG_DECOR_MASK;
+}
+
+static inline bool mt_decor_sign(MTKey key)
+{
+  return key.flags & (MT_FLAG_DECOR_SIGNTEXT | MT_FLAG_DECOR_SIGNHL);
+}
+
+static inline uint16_t mt_flags(bool right_gravity, bool no_undo, bool invalidate, bool decor_ext)
 {
-  assert(decor_level < DECOR_LEVELS);
   return (uint16_t)((right_gravity ? MT_FLAG_RIGHT_GRAVITY : 0)
-                    | (decor_level << MT_FLAG_DECOR_OFFSET));
+                    | (no_undo ? MT_FLAG_NO_UNDO : 0)
+                    | (invalidate ? MT_FLAG_INVALIDATE : 0)
+                    | (decor_ext ? MT_FLAG_DECOR_EXT : 0));
+}
+
+static inline MTPair mtpair_from(MTKey start, MTKey end)
+{
+  return (MTPair){ .start = start, .end_pos = end.pos, .end_right_gravity = mt_right(end) };
 }
 
+static inline DecorInline mt_decor(MTKey key)
+{
+  return (DecorInline){ .ext = key.flags & MT_FLAG_DECOR_EXT, .data = key.decor_data };
+}
+
+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[];
 };
 
-// TODO(bfredl): the iterator is pretty much everpresent, make it part of the
-// tree struct itself?
+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;
   PMap(uint64_t) id2node[1];
 } MarkTree;
 
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "marktree.h.generated.h"
 #endif
-
-#endif  // NVIM_MARKTREE_H