perf(extmarks): add metadata for efficient filtering of special decorations

This expands on the global "don't pay for what you don't use" rules for
these special extmark decorations:

- inline virtual text, which needs to be processed in plines.c when we
  calculate the size of text on screen
- virtual lines, which are needed when calculating "filler" lines
- signs, with text and/or highlights, both of which needs to be
  processed for the entire line already at the beginning of a line.

This adds a count to each node of the marktree, for how many special
marks of each kind can be found in the subtree for this node. This makes
it possible to quickly skip over these extra checks, when working in
regions of the buffer not containing these kind of marks, instead of
before where this could just be skipped if the entire _buffer_
didn't contain such marks.

1 files changed, 300 insertions, 31 deletions

diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index dae59a36a1..dbb4c5a9d3 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -62,7 +62,7 @@
 #include "nvim/garray_defs.h"
 
 #define T MT_BRANCH_FACTOR
-#define ILEN (sizeof(MTNode) + (2 * T) * sizeof(void *))
+#define ILEN (sizeof(MTNode) + sizeof(struct mtnode_inner_s))
 
 #define ID_INCR (((uint64_t)1) << 2)
 
@@ -181,6 +181,8 @@ static MTNode *id2node(MarkTree *b, uint64_t id)
   return pmap_get(uint64_t)(b->id2node, id);
 }
 
+#define ptr s->i_ptr
+#define meta s->i_meta
 // put functions
 
 // x must be an internal node, which is not full
@@ -226,15 +228,17 @@ static inline void split_node(MarkTree *b, MTNode *x, const int i, MTKey next)
   }
   if (y->level) {
     memcpy(z->ptr, &y->ptr[T], sizeof(MTNode *) * T);
+    memcpy(z->meta, &y->meta[T], sizeof(z->meta[0]) * T);
     for (int j = 0; j < T; j++) {
       z->ptr[j]->parent = z;
       z->ptr[j]->p_idx = (int16_t)j;
     }
   }
   y->n = T - 1;
-  memmove(&x->ptr[i + 2], &x->ptr[i + 1],
-          sizeof(MTNode *) * (size_t)(x->n - i));
+  memmove(&x->ptr[i + 2], &x->ptr[i + 1], sizeof(MTNode *) * (size_t)(x->n - i));
+  memmove(&x->meta[i + 2], &x->meta[i + 1], sizeof(x->meta[0]) * (size_t)(x->n - i));
   x->ptr[i + 1] = z;
+  meta_describe_node(x->meta[i + 1], z);
   z->parent = x;  // == y->parent
   for (int j = i + 1; j < x->n + 2; j++) {
     x->ptr[j]->p_idx = (int16_t)j;
@@ -246,6 +250,13 @@ static inline void split_node(MarkTree *b, MTNode *x, const int i, MTKey next)
   refkey(b, x, i);
   x->n++;
 
+  uint32_t meta_inc[4];
+  meta_describe_key(meta_inc, x->key[i]);
+  for (int m = 0; m < kMTMetaCount; m++) {
+    // y used contain all of z and x->key[i], discount those
+    x->meta[i][m] -= (x->meta[i + 1][m] + meta_inc[m]);
+  }
+
   for (int j = 0; j < T - 1; j++) {
     relative(x->key[i].pos, &z->key[j].pos);
   }
@@ -262,7 +273,7 @@ static inline void split_node(MarkTree *b, MTNode *x, const int i, MTKey next)
 }
 
 // x must not be a full node (even if there might be internal space)
-static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k)
+static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k, uint32_t *meta_inc)
 {
   // TODO(bfredl): ugh, make sure this is the _last_ valid (pos, gravity) position,
   // to minimize movement
@@ -285,7 +296,10 @@ static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k)
     if (i > 0) {
       relative(x->key[i - 1].pos, &k.pos);
     }
-    marktree_putp_aux(b, x->ptr[i], k);
+    marktree_putp_aux(b, x->ptr[i], k, meta_inc);
+    for (int m = 0; m < kMTMetaCount; m++) {
+      x->meta[i][m] += meta_inc[m];
+    }
   }
 }
 
@@ -416,7 +430,7 @@ void marktree_intersect_pair(MarkTree *b, uint64_t id, MarkTreeIter *itr, MarkTr
         }
       }
     }
-    marktree_itr_next_skip(b, itr, skip, true, NULL);
+    marktree_itr_next_skip(b, itr, skip, true, NULL, NULL);
   }
 #undef iat
 }
@@ -429,24 +443,75 @@ static MTNode *marktree_alloc_node(MarkTree *b, bool internal)
   return x;
 }
 
+// really meta_inc[kMTMetaCount]
+static void meta_describe_key_inc(uint32_t *meta_inc, MTKey *k)
+{
+  if (!mt_end(*k)) {
+    meta_inc[kMTMetaInline] += (k->flags & MT_FLAG_DECOR_VIRT_TEXT_INLINE) ? 1 : 0;
+    meta_inc[kMTMetaLines] += (k->flags & MT_FLAG_DECOR_VIRT_LINES) ? 1 : 0;
+    meta_inc[kMTMetaSignHL] += (k->flags & MT_FLAG_DECOR_SIGNHL) ? 1 : 0;
+    meta_inc[kMTMetaSignText] += (k->flags & MT_FLAG_DECOR_SIGNTEXT) ? 1 : 0;
+  }
+}
+
+static void meta_describe_key(uint32_t *meta_inc, MTKey k)
+{
+  memset(meta_inc, 0, kMTMetaCount * sizeof(*meta_inc));
+  meta_describe_key_inc(meta_inc, &k);
+}
+
+// if x is internal, asumes x->meta[..] of children are correct
+static void meta_describe_node(uint32_t *meta_node, MTNode *x)
+{
+  memset(meta_node, 0, kMTMetaCount * sizeof(meta_node[0]));
+  for (int i = 0; i < x->n; i++) {
+    meta_describe_key_inc(meta_node, &x->key[i]);
+  }
+  if (x->level) {
+    for (int i = 0; i < x->n + 1; i++) {
+      for (int m = 0; m < kMTMetaCount; m++) {
+        meta_node[m] += x->meta[i][m];
+      }
+    }
+  }
+}
+
+static bool meta_has(const uint32_t *meta_count, MetaFilter meta_filter)
+{
+  uint32_t count = 0;
+  for (int m = 0; m < kMTMetaCount; m++) {
+    count += meta_count[m] & meta_filter[m];
+  }
+  return count > 0;
+}
+
 void marktree_put_key(MarkTree *b, MTKey k)
 {
   k.flags |= MT_FLAG_REAL;  // let's be real.
   if (!b->root) {
     b->root = marktree_alloc_node(b, true);
   }
-  b->n_keys++;
   MTNode *r = b->root;
   if (r->n == 2 * T - 1) {
     MTNode *s = marktree_alloc_node(b, true);
     b->root = s; s->level = r->level + 1; s->n = 0;
     s->ptr[0] = r;
+    for (int m = 0; m < kMTMetaCount; m++) {
+      s->meta[0][m] = b->meta_root[m];
+    }
     r->parent = s;
     r->p_idx = 0;
     split_node(b, s, 0, k);
     r = s;
   }
-  marktree_putp_aux(b, r, k);
+
+  uint32_t meta_inc[4];
+  meta_describe_key(meta_inc, k);
+  marktree_putp_aux(b, r, k, meta_inc);
+  for (int m = 0; m < 4; m++) {
+    b->meta_root[m] += meta_inc[m];
+  }
+  b->n_keys++;
 }
 
 /// INITIATING DELETION PROTOCOL:
@@ -498,6 +563,7 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
     }
   }
 
+  // 2.
   if (itr->x->level) {
     if (rev) {
       abort();
@@ -512,6 +578,9 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
   MTNode *x = itr->x;
   assert(x->level == 0);
   MTKey intkey = x->key[itr->i];
+
+  uint32_t meta_inc[4];
+  meta_describe_key(meta_inc, intkey);
   if (x->n > itr->i + 1) {
     memmove(&x->key[itr->i], &x->key[itr->i + 1],
             sizeof(MTKey) * (size_t)(x->n - itr->i - 1));
@@ -557,11 +626,16 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
         }
       }
 
+      for (int m = 0; m < kMTMetaCount; m++) {
+        p->meta[lnode->p_idx][m] -= meta_inc[m];
+      }
+
       lnode = p;
       ilvl--;
     } while (lnode != cur);
 
     MTKey deleted = cur->key[curi];
+    meta_describe_key(meta_inc, deleted);
     cur->key[curi] = intkey;
     refkey(b, cur, curi);
     // if `did_bubble` then we already added `start_id` to some parent
@@ -586,6 +660,20 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
     itr->i--;
   }
 
+  MTNode *lnode = cur;
+  while (lnode->parent) {
+    uint32_t *meta_p = lnode->parent->meta[lnode->p_idx];
+    for (int m = 0; m < kMTMetaCount; m++) {
+      meta_p[m] -= meta_inc[m];
+    }
+
+    lnode = lnode->parent;
+  }
+  for (int m = 0; m < kMTMetaCount; m++) {
+    assert(b->meta_root[m] >= meta_inc[m]);
+    b->meta_root[m] -= meta_inc[m];
+  }
+
   // 5.
   bool itr_dirty = false;
   int rlvl = itr->lvl - 1;
@@ -646,6 +734,10 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
     if (b->root->level) {
       MTNode *oldroot = b->root;
       b->root = b->root->ptr[0];
+      for (int m = 0; m < kMTMetaCount; m++) {
+        assert(b->meta_root[m] == oldroot->meta[0][m]);
+      }
+
       b->root->parent = NULL;
       marktree_free_node(b, oldroot);
     } else {
@@ -910,10 +1002,10 @@ static MTNode *merge_node(MarkTree *b, MTNode *p, int i)
 {
   MTNode *x = p->ptr[i];
   MTNode *y = p->ptr[i + 1];
-  Intersection m;
-  kvi_init(m);
+  Intersection mi;
+  kvi_init(mi);
 
-  intersect_merge(&m, &x->intersect, &y->intersect);
+  intersect_merge(&mi, &x->intersect, &y->intersect);
 
   x->key[x->n] = p->key[i];
   refkey(b, x, x->n);
@@ -921,6 +1013,9 @@ static MTNode *merge_node(MarkTree *b, MTNode *p, int i)
     relative(p->key[i - 1].pos, &x->key[x->n].pos);
   }
 
+  uint32_t meta_inc[4];
+  meta_describe_key(meta_inc, x->key[x->n]);
+
   memmove(&x->key[x->n + 1], y->key, (size_t)y->n * sizeof(MTKey));
   for (int k = 0; k < y->n; k++) {
     refkey(b, x, x->n + 1 + k);
@@ -930,6 +1025,7 @@ static MTNode *merge_node(MarkTree *b, MTNode *p, int i)
     // bubble down: ranges that intersected old-x but not old-y or vice versa
     // must be moved to their respective children
     memmove(&x->ptr[x->n + 1], y->ptr, ((size_t)y->n + 1) * sizeof(MTNode *));
+    memmove(&x->meta[x->n + 1], y->meta, ((size_t)y->n + 1) * sizeof(y->meta[0]));
     for (int k = 0; k < x->n + 1; k++) {
       // TODO(bfredl): dedicated impl for "Z |= Y"
       for (size_t idx = 0; idx < kv_size(x->intersect); idx++) {
@@ -948,9 +1044,14 @@ static MTNode *merge_node(MarkTree *b, MTNode *p, int i)
     }
   }
   x->n += y->n + 1;
+  for (int m = 0; m < kMTMetaCount; m++) {
+    // x now contains everything of y plus old p->key[i]
+    p->meta[i][m] += (p->meta[i + 1][m] + meta_inc[m]);
+  }
+
   memmove(&p->key[i], &p->key[i + 1], (size_t)(p->n - i - 1) * sizeof(MTKey));
-  memmove(&p->ptr[i + 1], &p->ptr[i + 2],
-          (size_t)(p->n - i - 1) * sizeof(MTKey *));
+  memmove(&p->ptr[i + 1], &p->ptr[i + 2], (size_t)(p->n - i - 1) * sizeof(MTKey *));
+  memmove(&p->meta[i + 1], &p->meta[i + 2], (size_t)(p->n - i - 1) * sizeof(p->meta[0]));
   for (int j = i + 1; j < p->n; j++) {  // note: one has been deleted
     p->ptr[j]->p_idx = (int16_t)j;
   }
@@ -961,7 +1062,7 @@ static MTNode *merge_node(MarkTree *b, MTNode *p, int i)
 
   // move of a kvec_withinit_t, messy!
   // TODO(bfredl): special case version of intersect_merge(x_out, x_in_m_out, y) to avoid this
-  kvi_move(&x->intersect, &m);
+  kvi_move(&x->intersect, &mi);
 
   return x;
 }
@@ -991,16 +1092,34 @@ static void pivot_right(MarkTree *b, MTPos p_pos, MTNode *p, const int i)
   memmove(&y->key[1], y->key, (size_t)y->n * sizeof(MTKey));
   if (y->level) {
     memmove(&y->ptr[1], y->ptr, ((size_t)y->n + 1) * sizeof(MTNode *));
+    memmove(&y->meta[1], y->meta, ((size_t)y->n + 1) * sizeof(y->meta[0]));
     for (int j = 1; j < y->n + 2; j++) {
       y->ptr[j]->p_idx = (int16_t)j;
     }
   }
+
   y->key[0] = p->key[i];
   refkey(b, y, 0);
   p->key[i] = x->key[x->n - 1];
   refkey(b, p, i);
+
+  uint32_t meta_inc_y[4];
+  meta_describe_key(meta_inc_y, y->key[0]);
+  uint32_t meta_inc_x[4];
+  meta_describe_key(meta_inc_x, p->key[i]);
+
+  for (int m = 0; m < kMTMetaCount; m++) {
+    p->meta[i + 1][m] += meta_inc_y[m];
+    p->meta[i][m] -= meta_inc_x[m];
+  }
+
   if (x->level) {
     y->ptr[0] = x->ptr[x->n];
+    memcpy(y->meta[0], x->meta[x->n], sizeof(y->meta[0]));
+    for (int m = 0; m < kMTMetaCount; m++) {
+      p->meta[i + 1][m] += y->meta[0][m];
+      p->meta[i][m] -= y->meta[0][m];
+    }
     y->ptr[0]->parent = y;
     y->ptr[0]->p_idx = 0;
   }
@@ -1069,14 +1188,30 @@ static void pivot_left(MarkTree *b, MTPos p_pos, MTNode *p, int i)
   refkey(b, x, x->n);
   p->key[i] = y->key[0];
   refkey(b, p, i);
+
+  uint32_t meta_inc_x[4];
+  meta_describe_key(meta_inc_x, x->key[x->n]);
+  uint32_t meta_inc_y[4];
+  meta_describe_key(meta_inc_y, p->key[i]);
+  for (int m = 0; m < kMTMetaCount; m++) {
+    p->meta[i][m] += meta_inc_x[m];
+    p->meta[i + 1][m] -= meta_inc_y[m];
+  }
+
   if (x->level) {
     x->ptr[x->n + 1] = y->ptr[0];
+    memcpy(x->meta[x->n + 1], y->meta[0], sizeof(y->meta[0]));
+    for (int m = 0; m < kMTMetaCount; m++) {
+      p->meta[i + 1][m] -= y->meta[0][m];
+      p->meta[i][m] += y->meta[0][m];
+    }
     x->ptr[x->n + 1]->parent = x;
     x->ptr[x->n + 1]->p_idx = (int16_t)(x->n + 1);
   }
   memmove(y->key, &y->key[1], (size_t)(y->n - 1) * sizeof(MTKey));
   if (y->level) {
     memmove(y->ptr, &y->ptr[1], (size_t)y->n * sizeof(MTNode *));
+    memmove(y->meta, &y->meta[1], (size_t)y->n * sizeof(y->meta[0]));
     for (int j = 0; j < y->n; j++) {  // note: last item deleted
       y->ptr[j]->p_idx = (int16_t)j;
     }
@@ -1131,6 +1266,7 @@ void marktree_clear(MarkTree *b)
   }
   map_destroy(uint64_t, b->id2node);
   b->n_keys = 0;
+  memset(b->meta_root, 0, kMTMetaCount * sizeof(b->meta_root[0]));
   assert(b->n_nodes == 0);
 }
 
@@ -1231,11 +1367,11 @@ void marktree_restore_pair(MarkTree *b, MTKey key)
 
 bool marktree_itr_get(MarkTree *b, int32_t row, int col, MarkTreeIter *itr)
 {
-  return marktree_itr_get_ext(b, MTPos(row, col), itr, false, false, NULL);
+  return marktree_itr_get_ext(b, MTPos(row, col), itr, false, false, NULL, NULL);
 }
 
 bool marktree_itr_get_ext(MarkTree *b, MTPos p, MarkTreeIter *itr, bool last, bool gravity,
-                          MTPos *oldbase)
+                          MTPos *oldbase, MetaFilter meta_filter)
 {
   if (b->n_keys == 0) {
     itr->x = NULL;
@@ -1258,6 +1394,12 @@ bool marktree_itr_get_ext(MarkTree *b, MTPos p, MarkTreeIter *itr, bool last, bo
     if (itr->x->level == 0) {
       break;
     }
+    if (meta_filter) {
+      if (!meta_has(itr->x->meta[itr->i], meta_filter)) {
+        // this takes us to the interal position after the first rejected node
+        break;
+      }
+    }
 
     itr->s[itr->lvl].i = itr->i;
     itr->s[itr->lvl].oldcol = itr->pos.col;
@@ -1276,6 +1418,7 @@ bool marktree_itr_get_ext(MarkTree *b, MTPos p, MarkTreeIter *itr, bool last, bo
   if (last) {
     return marktree_itr_prev(b, itr);
   } else if (itr->i >= itr->x->n) {
+    // no need for "meta_filter" here, this just goes up one step
     return marktree_itr_next(b, itr);
   }
   return true;
@@ -1333,16 +1476,21 @@ int marktree_itr_last(MarkTree *b, MarkTreeIter *itr)
 
 bool marktree_itr_next(MarkTree *b, MarkTreeIter *itr)
 {
-  return marktree_itr_next_skip(b, itr, false, false, NULL);
+  return marktree_itr_next_skip(b, itr, false, false, NULL, NULL);
 }
 
 static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, bool preload,
-                                   MTPos oldbase[])
+                                   MTPos oldbase[], MetaFilter meta_filter)
 {
   if (!itr->x) {
     return false;
   }
   itr->i++;
+  if (meta_filter && itr->x->level > 0) {
+    if (!meta_has(itr->x->meta[itr->i], meta_filter)) {
+      skip = true;
+    }
+  }
   if (itr->x->level == 0 || skip) {
     if (preload && itr->x->level == 0 && skip) {
       // skip rest of this leaf node
@@ -1384,14 +1532,96 @@ static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, bo
       if (preload && itr->x->level) {
         itr->i = -1;
         break;
-      } else {
-        itr->i = 0;
+      }
+      itr->i = 0;
+      if (meta_filter && itr->x->level) {
+        if (!meta_has(itr->x->meta[0], meta_filter)) {
+          // itr->x has filtered keys but x->ptr[0] does not, don't enter the latter
+          break;
+        }
       }
     }
   }
   return true;
 }
 
+bool marktree_itr_get_filter(MarkTree *b, int32_t row, int col, int stop_row, int stop_col,
+                             MetaFilter meta_filter, MarkTreeIter *itr)
+{
+  if (!meta_has(b->meta_root, meta_filter)) {
+    return false;
+  }
+  if (!marktree_itr_get_ext(b, MTPos(row, col), itr, false, false, NULL, meta_filter)) {
+    return false;
+  }
+
+  return marktree_itr_check_filter(b, itr, stop_row, stop_col, meta_filter);
+}
+
+/// use after marktree_itr_get_overlap() to continue in a filtered fashion
+///
+/// not strictly needed but steps out to the right parent node where there
+/// might be "start" keys matching the filter ("end" keys are properly handled
+/// by marktree_itr_step_overlap() already)
+bool marktree_itr_step_out_filter(MarkTree *b, MarkTreeIter *itr, MetaFilter meta_filter)
+{
+  if (!meta_has(b->meta_root, meta_filter)) {
+    itr->x = NULL;
+    return false;
+  }
+
+  while (itr->x && itr->x->parent) {
+    if (meta_has(itr->x->parent->meta[itr->x->p_idx], meta_filter)) {
+      return true;
+    }
+
+    itr->i = itr->x->n;
+    marktree_itr_next(b, itr);  // no filter, just reuse the code for step to parent
+  }
+
+  return itr->x;
+}
+
+bool marktree_itr_next_filter(MarkTree *b, MarkTreeIter *itr, int stop_row, int stop_col,
+                              MetaFilter meta_filter)
+{
+  if (!marktree_itr_next_skip(b, itr, false, false, NULL, meta_filter)) {
+    return false;
+  }
+
+  return marktree_itr_check_filter(b, itr, stop_row, stop_col, meta_filter);
+}
+
+const uint32_t meta_map[4] = { MT_FLAG_DECOR_VIRT_TEXT_INLINE, MT_FLAG_DECOR_VIRT_LINES,
+                               MT_FLAG_DECOR_SIGNHL, MT_FLAG_DECOR_SIGNTEXT };
+static bool marktree_itr_check_filter(MarkTree *b, MarkTreeIter *itr, int stop_row, int stop_col,
+                                      MetaFilter meta_filter)
+{
+  MTPos stop_pos = MTPos(stop_row, stop_col);
+
+  uint32_t key_filter = 0;
+  for (int m = 0; m < kMTMetaCount; m++) {
+    key_filter |= meta_map[m]&meta_filter[m];
+  }
+
+  while (true) {
+    if (pos_leq(stop_pos, marktree_itr_pos(itr))) {
+      itr->x = NULL;
+      return false;
+    }
+
+    MTKey k = rawkey(itr);
+    if (!mt_end(k) && (k.flags & key_filter)) {
+      return true;
+    }
+
+    // this skips subtrees, but not keys, thus the outer loop
+    if (!marktree_itr_next_skip(b, itr, false, false, NULL, meta_filter)) {
+      return false;
+    }
+  }
+}
+
 bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr)
 {
   if (!itr->x) {
@@ -1602,6 +1832,33 @@ static void swap_keys(MarkTree *b, MarkTreeIter *itr1, MarkTreeIter *itr2, Damag
       kvi_push(*damage, ((Damage){ mt_lookup_key(rawkey(itr2)), itr2->x, itr1->x,
                                    itr2->i, itr1->i }));
     }
+
+    uint32_t meta_inc_1[4];
+    meta_describe_key(meta_inc_1, rawkey(itr1));
+    uint32_t meta_inc_2[4];
+    meta_describe_key(meta_inc_2, rawkey(itr2));
+
+    if (memcmp(meta_inc_1, meta_inc_2, sizeof(meta_inc_1)) != 0) {
+      MTNode *x1 = itr1->x;
+      MTNode *x2 = itr2->x;
+      while (x1 != x2) {
+        if (x1->level <= x2->level) {
+          // as the root node uniquely has the highest level, x1 cannot be it
+          uint32_t *meta_node = x1->parent->meta[x1->p_idx];
+          for (int m = 0; m < kMTMetaCount; m++) {
+            meta_node[m] += meta_inc_2[m] - meta_inc_1[m];
+          }
+          x1 = x1->parent;
+        }
+        if (x2->level < x1->level) {
+          uint32_t *meta_node = x2->parent->meta[x2->p_idx];
+          for (int m = 0; m < kMTMetaCount; m++) {
+            meta_node[m] += meta_inc_1[m] - meta_inc_2[m];
+          }
+          x2 = x2->parent;
+        }
+      }
+    }
   }
 
   MTKey key1 = rawkey(itr1);
@@ -1638,7 +1895,7 @@ bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_ext
 
   MTPos oldbase[MT_MAX_DEPTH] = { 0 };
 
-  marktree_itr_get_ext(b, start, itr, false, true, oldbase);
+  marktree_itr_get_ext(b, start, itr, false, true, oldbase, NULL);
   if (!itr->x) {
     // den e FÄRDIG
     return false;
@@ -1651,7 +1908,7 @@ bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_ext
     if (!pos_leq(old_extent, ipos)
         || (old_extent.row == ipos.row && old_extent.col == ipos.col
             && !mt_right(rawkey(itr)))) {
-      marktree_itr_get_ext(b, old_extent, enditr, true, true, NULL);
+      marktree_itr_get_ext(b, old_extent, enditr, true, true, NULL, NULL);
       assert(enditr->x);
       // "assert" (itr <= enditr)
     } else {
@@ -1706,7 +1963,7 @@ continue_same_node:
         oldbase[itr->lvl + 1] = rawkey(itr).pos;
         unrelative(oldbase[itr->lvl], &oldbase[itr->lvl + 1]);
         rawkey(itr).pos = loc_start;
-        marktree_itr_next_skip(b, itr, false, false, oldbase);
+        marktree_itr_next_skip(b, itr, false, false, oldbase, NULL);
       } else {
         rawkey(itr).pos = loc_start;
         if (itr->i < itr->x->n - 1) {
@@ -1739,7 +1996,7 @@ past_continue_same_node:
         oldbase[itr->lvl + 1] = oldpos;
         unrelative(oldbase[itr->lvl], &oldbase[itr->lvl + 1]);
 
-        marktree_itr_next_skip(b, itr, false, false, oldbase);
+        marktree_itr_next_skip(b, itr, false, false, oldbase, NULL);
       } else {
         if (itr->i < itr->x->n - 1) {
           itr->i++;
@@ -1774,7 +2031,7 @@ past_continue_same_node:
     if (done) {
       break;
     }
-    marktree_itr_next_skip(b, itr, true, false, NULL);
+    marktree_itr_next_skip(b, itr, true, false, NULL, NULL);
   }
 
   if (kv_size(damage)) {
@@ -1844,7 +2101,7 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext
   MTPos end = size;
   unrelative(start, &end);
   MarkTreeIter itr[1] = { 0 };
-  marktree_itr_get_ext(b, start, itr, false, true, NULL);
+  marktree_itr_get_ext(b, start, itr, false, true, NULL, NULL);
   kvec_t(MTKey) saved = KV_INITIAL_VALUE;
   while (itr->x) {
     MTKey k = marktree_itr_current(itr);
@@ -1996,9 +2253,12 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
 
 // for unit test
 void marktree_put_test(MarkTree *b, uint32_t ns, uint32_t id, int row, int col, bool right_gravity,
-                       int end_row, int end_col, bool end_right)
+                       int end_row, int end_col, bool end_right, bool meta_inline)
 {
   uint16_t flags = mt_flags(right_gravity, false, false, false);
+  // The specific choice is irrelevant here, we pick one counted decor
+  // type to test the counting and filtering logic.
+  flags |= meta_inline ? MT_FLAG_DECOR_VIRT_TEXT_INLINE : 0;
   MTKey key = { { row, col }, ns, id, flags, { .hl = DECOR_HIGHLIGHT_INLINE_INIT } };
   marktree_put(b, key, end_row, end_col, end_right);
 }
@@ -2033,7 +2293,8 @@ void marktree_check(MarkTree *b)
 
   MTPos dummy;
   bool last_right = false;
-  size_t nkeys = marktree_check_node(b, b->root, &dummy, &last_right);
+
+  size_t nkeys = marktree_check_node(b, b->root, &dummy, &last_right, b->meta_root);
   assert(b->n_keys == nkeys);
   assert(b->n_keys == map_size(b->id2node));
 #else
@@ -2043,7 +2304,8 @@ void marktree_check(MarkTree *b)
 }
 
 #ifndef NDEBUG
-size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right)
+size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right,
+                           const uint32_t *meta_node_ref)
 {
   assert(x->n <= 2 * T - 1);
   // TODO(bfredl): too strict if checking "in repair" post-delete tree.
@@ -2052,7 +2314,7 @@ size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right
 
   for (int i = 0; i < x->n; i++) {
     if (x->level) {
-      n_keys += marktree_check_node(b, x->ptr[i], last, last_right);
+      n_keys += marktree_check_node(b, x->ptr[i], last, last_right, x->meta[i]);
     } else {
       *last = (MTPos) { 0, 0 };
     }
@@ -2069,7 +2331,7 @@ size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right
   }
 
   if (x->level) {
-    n_keys += marktree_check_node(b, x->ptr[x->n], last, last_right);
+    n_keys += marktree_check_node(b, x->ptr[x->n], last, last_right, x->meta[x->n]);
     unrelative(x->key[x->n - 1].pos, last);
 
     for (int i = 0; i < x->n + 1; i++) {
@@ -2084,6 +2346,13 @@ size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right
   } else if (x->n > 0) {
     *last = x->key[x->n - 1].pos;
   }
+
+  uint32_t meta_node[4];
+  meta_describe_node(meta_node, x);
+  for (int m = 0; m < kMTMetaCount; m++) {
+    assert(meta_node_ref[m] == meta_node[m]);
+  }
+
   return n_keys;
 }