17 files changed, 490 insertions, 155 deletions

diff --git a/src/nvim/api/buffer.c b/src/nvim/api/buffer.c
index 8a091f39e4..7e79087f10 100644
--- a/src/nvim/api/buffer.c
+++ b/src/nvim/api/buffer.c
@@ -32,6 +32,7 @@
 #include "nvim/mapping.h"
 #include "nvim/mark.h"
 #include "nvim/mark_defs.h"
+#include "nvim/marktree.h"
 #include "nvim/memline.h"
 #include "nvim/memline_defs.h"
 #include "nvim/memory.h"
@@ -1282,7 +1283,7 @@ Dictionary nvim__buf_stats(Buffer buffer, Error *err)
   // this exists to debug issues
   PUT(rv, "dirty_bytes", INTEGER_OBJ((Integer)buf->deleted_bytes));
   PUT(rv, "dirty_bytes2", INTEGER_OBJ((Integer)buf->deleted_bytes2));
-  PUT(rv, "virt_blocks", INTEGER_OBJ((Integer)buf->b_virt_line_blocks));
+  PUT(rv, "virt_blocks", INTEGER_OBJ((Integer)buf_meta_total(buf, kMTMetaLines)));
 
   u_header_T *uhp = NULL;
   if (buf->b_u_curhead != NULL) {
diff --git a/src/nvim/buffer.h b/src/nvim/buffer.h
index 4ad7144ad9..144573849c 100644
--- a/src/nvim/buffer.h
+++ b/src/nvim/buffer.h
@@ -81,3 +81,8 @@ static inline varnumber_T buf_get_changedtick(const buf_T *const buf)
 {
   return buf->changedtick_di.di_tv.vval.v_number;
 }
+
+static inline uint32_t buf_meta_total(const buf_T *b, MetaIndex m)
+{
+  return b->b_marktree->meta_root[m];
+}
diff --git a/src/nvim/buffer_defs.h b/src/nvim/buffer_defs.h
index 145a8435aa..79527176ab 100644
--- a/src/nvim/buffer_defs.h
+++ b/src/nvim/buffer_defs.h
@@ -701,10 +701,6 @@ struct file_buffer {
 
   MarkTree b_marktree[1];
   Map(uint32_t, uint32_t) b_extmark_ns[1];         // extmark namespaces
-  size_t b_virt_text_inline;                       // number of inline virtual texts
-  size_t b_virt_line_blocks;    // number of virt_line blocks
-  size_t b_signs;               // number of sign extmarks
-  size_t b_signs_with_text;     // number of sign extmarks with text
 
   // array of channel_id:s which have asked to receive updates for this
   // buffer.
diff --git a/src/nvim/change.c b/src/nvim/change.c
index 09312118f6..9103b43a24 100644
--- a/src/nvim/change.c
+++ b/src/nvim/change.c
@@ -33,6 +33,7 @@
 #include "nvim/macros_defs.h"
 #include "nvim/mark.h"
 #include "nvim/mark_defs.h"
+#include "nvim/marktree.h"
 #include "nvim/mbyte.h"
 #include "nvim/mbyte_defs.h"
 #include "nvim/memline.h"
@@ -329,7 +330,7 @@ static void changed_common(buf_T *buf, linenr_T lnum, colnr_T col, linenr_T lnum
             // changed line may become invalid.
             if (i == 0 || wp->w_lines[i].wl_lnum < lnume
                 || (wp->w_lines[i].wl_lnum == lnume
-                    && wp->w_buffer->b_virt_line_blocks > 0)) {
+                    && buf_meta_total(wp->w_buffer, kMTMetaLines) > 0)) {
               // line included in change
               wp->w_lines[i].wl_valid = false;
             } else if (xtra != 0) {
diff --git a/src/nvim/decoration.c b/src/nvim/decoration.c
index 5224a07fd9..d3517c077f 100644
--- a/src/nvim/decoration.c
+++ b/src/nvim/decoration.c
@@ -8,6 +8,7 @@
 #include "nvim/api/private/defs.h"
 #include "nvim/api/private/helpers.h"
 #include "nvim/ascii_defs.h"
+#include "nvim/buffer.h"
 #include "nvim/buffer_defs.h"
 #include "nvim/decoration.h"
 #include "nvim/drawscreen.h"
@@ -170,12 +171,6 @@ DecorSignHighlight decor_sh_from_inline(DecorHighlightInline item)
 void buf_put_decor(buf_T *buf, DecorInline decor, int row, int row2)
 {
   if (decor.ext) {
-    DecorVirtText *vt = decor.data.ext.vt;
-    while (vt) {
-      buf_put_decor_virt(buf, vt);
-      vt = vt->next;
-    }
-
     uint32_t idx = decor.data.ext.sh_idx;
     while (idx != DECOR_ID_INVALID) {
       DecorSignHighlight *sh = &kv_A(decor_items, idx);
@@ -185,28 +180,12 @@ void buf_put_decor(buf_T *buf, DecorInline decor, int row, int row2)
   }
 }
 
-void buf_put_decor_virt(buf_T *buf, DecorVirtText *vt)
-{
-  if (vt->flags &kVTIsLines) {
-    buf->b_virt_line_blocks++;
-  } else {
-    if (vt->pos == kVPosInline) {
-      buf->b_virt_text_inline++;
-    }
-  }
-  if (vt->next) {
-    buf_put_decor_virt(buf, vt->next);
-  }
-}
-
 static int sign_add_id = 0;
 void buf_put_decor_sh(buf_T *buf, DecorSignHighlight *sh, int row1, int row2)
 {
   if (sh->flags & kSHIsSign) {
     sh->sign_add_id = sign_add_id++;
-    buf->b_signs++;
     if (sh->text[0]) {
-      buf->b_signs_with_text++;
       buf_signcols_count_range(buf, row1, row2, 1, kFalse);
     }
   }
@@ -216,11 +195,6 @@ void buf_decor_remove(buf_T *buf, int row1, int row2, DecorInline decor, bool fr
 {
   decor_redraw(buf, row1, row2, decor);
   if (decor.ext) {
-    DecorVirtText *vt = decor.data.ext.vt;
-    while (vt) {
-      buf_remove_decor_virt(buf, vt);
-      vt = vt->next;
-    }
     uint32_t idx = decor.data.ext.sh_idx;
     while (idx != DECOR_ID_INVALID) {
       DecorSignHighlight *sh = &kv_A(decor_items, idx);
@@ -233,28 +207,11 @@ void buf_decor_remove(buf_T *buf, int row1, int row2, DecorInline decor, bool fr
   }
 }
 
-void buf_remove_decor_virt(buf_T *buf, DecorVirtText *vt)
-{
-  if (vt->flags &kVTIsLines) {
-    assert(buf->b_virt_line_blocks > 0);
-    buf->b_virt_line_blocks--;
-  } else {
-    if (vt->pos == kVPosInline) {
-      assert(buf->b_virt_text_inline > 0);
-      buf->b_virt_text_inline--;
-    }
-  }
-}
-
 void buf_remove_decor_sh(buf_T *buf, int row1, int row2, DecorSignHighlight *sh)
 {
   if (sh->flags & kSHIsSign) {
-    assert(buf->b_signs > 0);
-    buf->b_signs--;
     if (sh->text[0]) {
-      assert(buf->b_signs_with_text > 0);
-      buf->b_signs_with_text--;
-      if (buf->b_signs_with_text) {
+      if (buf_meta_total(buf, kMTMetaSignText)) {
         buf_signcols_count_range(buf, row1, row2, -1, kFalse);
       } else {
         buf->b_signcols.resized = true;
@@ -395,10 +352,10 @@ DecorVirtText *decor_find_virttext(buf_T *buf, int row, uint64_t ns_id)
     MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0 || mark.pos.row > row) {
       break;
-    } else if (mt_invalid(mark) || !(mark.flags & MT_FLAG_DECOR_EXT)) {
+    } else if (mt_invalid(mark)) {
       goto next_mark;
     }
-    DecorVirtText *decor = mark.decor_data.ext.vt;
+    DecorVirtText *decor = mt_decor_virt(mark);
     while (decor && (decor->flags & kVTIsLines)) {
       decor = decor->next;
     }
@@ -705,6 +662,9 @@ int sign_item_cmp(const void *p1, const void *p2)
          ? n : (s2->sh->sign_add_id - s1->sh->sign_add_id);
 }
 
+const uint32_t sign_filter[4] = {[kMTMetaSignText] = kMTFilterSelect,
+                                 [kMTMetaSignHL] = kMTFilterSelect };
+
 /// Return the sign attributes on the currently refreshed row.
 ///
 /// @param[out] sattrs Output array for sign text and texthl id
@@ -731,6 +691,8 @@ void decor_redraw_signs(win_T *wp, buf_T *buf, int row, SignTextAttrs sattrs[],
     }
   }
 
+  marktree_itr_step_out_filter(buf->b_marktree, itr, sign_filter);
+
   while (itr->x) {
     MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row != row) {
@@ -742,7 +704,7 @@ void decor_redraw_signs(win_T *wp, buf_T *buf, int row, SignTextAttrs sattrs[],
       kv_push(signs, ((SignItem){ sh, mark.id }));
     }
 
-    marktree_itr_next(buf->b_marktree, itr);
+    marktree_itr_next_filter(buf->b_marktree, itr, row + 1, 0, sign_filter);
   }
 
   if (kv_size(signs)) {
@@ -788,6 +750,8 @@ DecorSignHighlight *decor_find_sign(DecorInline decor)
   }
 }
 
+const uint32_t signtext_filter[4] = {[kMTMetaSignText] = kMTFilterSelect };
+
 /// Count the number of signs in a range after adding/removing a sign, or to
 /// (re-)initialize a range in "b_signcols.count".
 ///
@@ -795,7 +759,7 @@ DecorSignHighlight *decor_find_sign(DecorInline decor)
 /// @param clear  kFalse, kTrue or kNone for an, added/deleted, cleared, or initialized range.
 void buf_signcols_count_range(buf_T *buf, int row1, int row2, int add, TriState clear)
 {
-  if (!buf->b_signcols.autom || !buf->b_signs_with_text) {
+  if (!buf->b_signcols.autom || !buf_meta_total(buf, kMTMetaSignText)) {
     return;
   }
 
@@ -821,6 +785,8 @@ void buf_signcols_count_range(buf_T *buf, int row1, int row2, int add, TriState
     }
   }
 
+  marktree_itr_step_out_filter(buf->b_marktree, itr, signtext_filter);
+
   // Continue traversing the marktree until beyond "row2".
   while (itr->x) {
     MTKey mark = marktree_itr_current(itr);
@@ -835,7 +801,7 @@ void buf_signcols_count_range(buf_T *buf, int row1, int row2, int add, TriState
       }
     }
 
-    marktree_itr_next(buf->b_marktree, itr);
+    marktree_itr_next_filter(buf->b_marktree, itr, row2 + 1, 0, signtext_filter);
   }
 
   // For each row increment "b_signcols.count" at the number of counted signs,
@@ -884,11 +850,13 @@ bool decor_redraw_eol(win_T *wp, DecorState *state, int *eol_attr, int eol_col)
   return has_virt_pos;
 }
 
+uint32_t lines_filter[4] = {[kMTMetaLines] = kMTFilterSelect };
+
 /// @param has_fold  whether line "lnum" has a fold, or kNone when not calculated yet
 int decor_virt_lines(win_T *wp, linenr_T lnum, VirtLines *lines, TriState has_fold)
 {
   buf_T *buf = wp->w_buffer;
-  if (!buf->b_virt_line_blocks) {
+  if (!buf_meta_total(buf, kMTMetaLines)) {
     // Only pay for what you use: in case virt_lines feature is not active
     // in a buffer, plines do not need to access the marktree at all
     return 0;
@@ -907,17 +875,15 @@ int decor_virt_lines(win_T *wp, linenr_T lnum, VirtLines *lines, TriState has_fo
     return 0;
   }
 
-  int virt_lines = 0;
   MarkTreeIter itr[1] = { 0 };
-  marktree_itr_get(buf->b_marktree, start_row, 0, itr);
+  if (!marktree_itr_get_filter(buf->b_marktree, start_row, 0, end_row, 0, lines_filter, itr)) {
+    return 0;
+  }
+
+  int virt_lines = 0;
   while (true) {
     MTKey mark = marktree_itr_current(itr);
-    if (mark.pos.row < 0 || mark.pos.row >= end_row) {
-      break;
-    } else if (mt_end(mark) || !(mark.flags & MT_FLAG_DECOR_VIRT_LINES)) {
-      goto next_mark;
-    }
-    DecorVirtText *vt = mark.decor_data.ext.vt;
+    DecorVirtText *vt = mt_decor_virt(mark);
     while (vt) {
       if (vt->flags & kVTIsLines) {
         bool above = vt->flags & kVTLinesAbove;
@@ -931,8 +897,10 @@ int decor_virt_lines(win_T *wp, linenr_T lnum, VirtLines *lines, TriState has_fo
       }
       vt = vt->next;
     }
-next_mark:
-    marktree_itr_next(buf->b_marktree, itr);
+
+    if (!marktree_itr_next_filter(buf->b_marktree, itr, end_row, 0, lines_filter)) {
+      break;
+    }
   }
 
   return virt_lines;
diff --git a/src/nvim/drawline.c b/src/nvim/drawline.c
index ae538ed7a6..62b937f810 100644
--- a/src/nvim/drawline.c
+++ b/src/nvim/drawline.c
@@ -32,6 +32,7 @@
 #include "nvim/highlight_group.h"
 #include "nvim/indent.h"
 #include "nvim/mark_defs.h"
+#include "nvim/marktree.h"
 #include "nvim/match.h"
 #include "nvim/mbyte.h"
 #include "nvim/memline.h"
@@ -1645,7 +1646,7 @@ int win_line(win_T *wp, linenr_T lnum, int startrow, int endrow, int col_rows, s
                                           &decor_state);
         }
 
-        if (!has_foldtext && wp->w_buffer->b_virt_text_inline > 0) {
+        if (!has_foldtext && buf_meta_total(wp->w_buffer, kMTMetaInline) > 0) {
           handle_inline_virtual_text(wp, &wlv, ptr - line);
           if (wlv.n_extra > 0 && wlv.virt_inline_hl_mode <= kHlModeReplace) {
             // restore search_attr and area_attr when n_extra is down to zero
@@ -1662,9 +1663,8 @@ int win_line(win_T *wp, linenr_T lnum, int startrow, int endrow, int col_rows, s
         }
       }
 
-      int *area_attr_p
-        = wlv.extra_for_extmark && wlv.virt_inline_hl_mode <= kHlModeReplace
-          ? &saved_area_attr : &area_attr;
+      int *area_attr_p = wlv.extra_for_extmark && wlv.virt_inline_hl_mode <= kHlModeReplace
+                         ? &saved_area_attr : &area_attr;
 
       // handle Visual or match highlighting in this line
       if (wlv.vcol == wlv.fromcol
diff --git a/src/nvim/drawscreen.c b/src/nvim/drawscreen.c
index 1cc04d2588..a9bdafd58b 100644
--- a/src/nvim/drawscreen.c
+++ b/src/nvim/drawscreen.c
@@ -88,6 +88,7 @@
 #include "nvim/highlight_defs.h"
 #include "nvim/highlight_group.h"
 #include "nvim/insexpand.h"
+#include "nvim/marktree.h"
 #include "nvim/match.h"
 #include "nvim/mbyte.h"
 #include "nvim/memline.h"
@@ -1220,7 +1221,7 @@ static bool win_redraw_signcols(win_T *wp)
   if (rebuild_stc) {
     wp->w_nrwidth_line_count = 0;
   } else if (wp->w_minscwidth == 0 && wp->w_maxscwidth == 1) {
-    width = buf->b_signs_with_text > 0;
+    width = buf_meta_total(buf, kMTMetaSignText) > 0;
   }
 
   int scwidth = wp->w_scwidth;
@@ -2628,7 +2629,7 @@ int number_width(win_T *wp)
 
   // If 'signcolumn' is set to 'number' and there is a sign to display, then
   // the minimal width for the number column is 2.
-  if (n < 2 && wp->w_buffer->b_signs_with_text && wp->w_minscwidth == SCL_NUM) {
+  if (n < 2 && buf_meta_total(wp->w_buffer, kMTMetaSignText) && wp->w_minscwidth == SCL_NUM) {
     n = 2;
   }
 
diff --git a/src/nvim/edit.c b/src/nvim/edit.c
index 1415f0ca35..25d2c964ed 100644
--- a/src/nvim/edit.c
+++ b/src/nvim/edit.c
@@ -41,6 +41,7 @@
 #include "nvim/mapping.h"
 #include "nvim/mark.h"
 #include "nvim/mark_defs.h"
+#include "nvim/marktree.h"
 #include "nvim/mbyte.h"
 #include "nvim/mbyte_defs.h"
 #include "nvim/memline.h"
@@ -240,7 +241,7 @@ static void insert_enter(InsertState *s)
 
   // need to position cursor again when on a TAB and
   // when on a char with inline virtual text
-  if (gchar_cursor() == TAB || curbuf->b_virt_text_inline > 0) {
+  if (gchar_cursor() == TAB || buf_meta_total(curbuf, kMTMetaInline) > 0) {
     curwin->w_valid &= ~(VALID_WROW|VALID_WCOL|VALID_VIRTCOL);
   }
 
@@ -3472,7 +3473,7 @@ static bool ins_esc(int *count, int cmdchar, bool nomove)
   may_trigger_modechanged();
   // need to position cursor again when on a TAB and
   // when on a char with inline virtual text
-  if (gchar_cursor() == TAB || curbuf->b_virt_text_inline > 0) {
+  if (gchar_cursor() == TAB || buf_meta_total(curbuf, kMTMetaInline) > 0) {
     curwin->w_valid &= ~(VALID_WROW|VALID_WCOL|VALID_VIRTCOL);
   }
 
diff --git a/src/nvim/eval/buffer.c b/src/nvim/eval/buffer.c
index 291a57657d..c43ef50410 100644
--- a/src/nvim/eval/buffer.c
+++ b/src/nvim/eval/buffer.c
@@ -507,7 +507,7 @@ static dict_T *get_buffer_info(buf_T *buf)
   }
   tv_dict_add_list(dict, S_LEN("windows"), windows);
 
-  if (buf->b_signs) {
+  if (buf_has_signs(buf)) {
     // List of signs placed in this buffer
     tv_dict_add_list(dict, S_LEN("signs"), get_buffer_signs(buf));
   }
diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c
index 4e4db93a7b..20a701d5a1 100644
--- a/src/nvim/extmark.c
+++ b/src/nvim/extmark.c
@@ -225,7 +225,7 @@ ExtmarkInfoArray extmark_get(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_co
   } else {
     // Find all the marks beginning with the start position
     marktree_itr_get_ext(buf->b_marktree, MTPos(l_row, l_col),
-                         itr, reverse, false, NULL);
+                         itr, reverse, false, NULL, NULL);
   }
 
   int order = reverse ? -1 : 1;
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;
 }
 
diff --git a/src/nvim/marktree.h b/src/nvim/marktree.h
index b31feaad3c..1fb1a74487 100644
--- a/src/nvim/marktree.h
+++ b/src/nvim/marktree.h
@@ -125,6 +125,11 @@ static inline DecorInline mt_decor(MTKey key)
   return (DecorInline){ .ext = key.flags & MT_FLAG_DECOR_EXT, .data = key.decor_data };
 }
 
+static inline DecorVirtText *mt_decor_virt(MTKey mark)
+{
+  return (mark.flags & MT_FLAG_DECOR_EXT) ? mark.decor_data.ext.vt : NULL;
+}
+
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "marktree.h.generated.h"
 #endif
diff --git a/src/nvim/marktree_defs.h b/src/nvim/marktree_defs.h
index 5dc901b9bd..d43130db6f 100644
--- a/src/nvim/marktree_defs.h
+++ b/src/nvim/marktree_defs.h
@@ -22,6 +22,21 @@ typedef struct {
 } MTPos;
 #define MTPos(r, c) ((MTPos){ .row = (r), .col = (c) })
 
+// Currently there are four counts, which makes for a uint32_t[4] per node
+// which makes for nice autovectorization into a single XMM or NEON register
+typedef enum {
+  kMTMetaInline,
+  kMTMetaLines,
+  kMTMetaSignHL,
+  kMTMetaSignText,
+  kMTMetaCount,  // sentinel, must be last
+} MetaIndex;
+
+#define kMTFilterSelect ((uint32_t)-1)
+
+// a filter should be set to kMTFilterSelect for the selected kinds, zero otherwise
+typedef const uint32_t *MetaFilter;
+
 typedef struct mtnode_s MTNode;
 
 typedef struct {
@@ -63,20 +78,26 @@ typedef struct {
 
 typedef kvec_withinit_t(uint64_t, 4) Intersection;
 
+// part of mtnode_s which is only allocated for inner nodes:
+// pointer to children as well as their meta counts
+struct mtnode_inner_s {
+  MTNode *i_ptr[2 * MT_BRANCH_FACTOR];
+  uint32_t i_meta[2 * MT_BRANCH_FACTOR][kMTMetaCount];
+};
+
 struct mtnode_s {
   int32_t n;
   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 *parent;
   MTKey key[2 * MT_BRANCH_FACTOR - 1];
-  MTNode *ptr[];
+  struct mtnode_inner_s s[];
 };
 
 typedef struct {
   MTNode *root;
+  uint32_t meta_root[kMTMetaCount];
   size_t n_keys, n_nodes;
   PMap(uint64_t) id2node[1];
 } MarkTree;
diff --git a/src/nvim/plines.c b/src/nvim/plines.c
index c59c23179e..631c847898 100644
--- a/src/nvim/plines.c
+++ b/src/nvim/plines.c
@@ -6,6 +6,7 @@
 #include <string.h>
 
 #include "nvim/ascii_defs.h"
+#include "nvim/buffer.h"
 #include "nvim/buffer_defs.h"
 #include "nvim/charset.h"
 #include "nvim/decoration.h"
@@ -75,6 +76,7 @@ int linetabsize(win_T *wp, linenr_T lnum)
   return win_linetabsize(wp, lnum, ml_get_buf(wp->w_buffer, lnum), (colnr_T)MAXCOL);
 }
 
+const uint32_t inline_filter[4] = {[kMTMetaInline] = kMTFilterSelect };
 /// Prepare the structure passed to charsize functions.
 ///
 /// "line" is the start of the line.
@@ -90,10 +92,9 @@ CSType init_charsize_arg(CharsizeArg *csarg, win_T *wp, linenr_T lnum, char *lin
   csarg->indent_width = INT_MIN;
   csarg->use_tabstop = !wp->w_p_list || wp->w_p_lcs_chars.tab1;
 
-  if (lnum > 0 && wp->w_buffer->b_virt_text_inline > 0) {
-    marktree_itr_get(wp->w_buffer->b_marktree, lnum - 1, 0, csarg->iter);
-    MTKey mark = marktree_itr_current(csarg->iter);
-    if (mark.pos.row == lnum - 1) {
+  if (lnum > 0) {
+    if (marktree_itr_get_filter(wp->w_buffer->b_marktree, lnum - 1, 0, lnum, 0,
+                                inline_filter, csarg->iter)) {
       csarg->virt_row = lnum - 1;
     }
   }
@@ -173,7 +174,8 @@ CharSize charsize_regular(CharsizeArg *csarg, char *const cur, colnr_T const vco
           }
         }
       }
-      marktree_itr_next(wp->w_buffer->b_marktree, csarg->iter);
+      marktree_itr_next_filter(wp->w_buffer->b_marktree, csarg->iter, csarg->virt_row + 1, 0,
+                               inline_filter);
     }
   }
 
@@ -661,7 +663,8 @@ void getvcols(win_T *wp, pos_T *pos1, pos_T *pos2, colnr_T *left, colnr_T *right
 /// Check if there may be filler lines anywhere in window "wp".
 bool win_may_fill(win_T *wp)
 {
-  return (wp->w_p_diff && diffopt_filler()) || wp->w_buffer->b_virt_line_blocks;
+  return ((wp->w_p_diff && diffopt_filler())
+          || buf_meta_total(wp->w_buffer, kMTMetaLines));
 }
 
 /// Return the number of filler lines above "lnum".
diff --git a/src/nvim/sign.c b/src/nvim/sign.c
index 0cf35c4921..b1a2d1ad08 100644
--- a/src/nvim/sign.c
+++ b/src/nvim/sign.c
@@ -250,13 +250,18 @@ static int buf_delete_signs(buf_T *buf, char *group, int id, linenr_T atlnum)
 
   // When deleting the last sign need to redraw the windows to remove the
   // sign column. Not when curwin is NULL (this means we're exiting).
-  if (!buf->b_signs_with_text && curwin != NULL) {
+  if (!buf_meta_total(buf, kMTMetaSignText) && curwin != NULL) {
     changed_line_abv_curs();
   }
 
   return OK;
 }
 
+bool buf_has_signs(const buf_T *buf)
+{
+  return (buf_meta_total(buf, kMTMetaSignHL) + buf_meta_total(buf, kMTMetaSignText));
+}
+
 /// List placed signs for "rbuf".  If "rbuf" is NULL do it for all buffers.
 static void sign_list_placed(buf_T *rbuf, char *group)
 {
@@ -270,7 +275,7 @@ static void sign_list_placed(buf_T *rbuf, char *group)
   msg_putchar('\n');
 
   while (buf != NULL && !got_int) {
-    if (buf->b_signs) {
+    if (buf_has_signs(buf)) {
       vim_snprintf(lbuf, MSG_BUF_LEN, _("Signs for %s:"), buf->b_fname);
       msg_puts_attr(lbuf, HL_ATTR(HLF_D));
       msg_putchar('\n');
@@ -415,7 +420,7 @@ static int sign_define_by_name(char *name, char *icon, char *text, char *linehl,
   } else {
     // Signs may already exist, a redraw is needed in windows with a non-empty sign list.
     FOR_ALL_WINDOWS_IN_TAB(wp, curtab) {
-      if (wp->w_buffer->b_signs) {
+      if (buf_has_signs(wp->w_buffer)) {
         redraw_buf_later(wp->w_buffer, UPD_NOT_VALID);
       }
     }
@@ -542,7 +547,7 @@ static int sign_place(uint32_t *id, char *group, char *name, buf_T *buf, linenr_
 
 static int sign_unplace_inner(buf_T *buf, int id, char *group, linenr_T atlnum)
 {
-  if (!buf->b_signs) {  // No signs in the buffer
+  if (!buf_has_signs(buf)) {  // No signs in the buffer
     return FAIL;
   }
 
@@ -562,7 +567,7 @@ static int sign_unplace_inner(buf_T *buf, int id, char *group, linenr_T atlnum)
   // When all the signs in a buffer are removed, force recomputing the
   // number column width (if enabled) in all the windows displaying the
   // buffer if 'signcolumn' is set to 'number' in that window.
-  if (!buf->b_signs_with_text) {
+  if (!buf_meta_total(buf, kMTMetaSignText)) {
     may_force_numberwidth_recompute(buf, true);
   }
 
@@ -962,7 +967,7 @@ static void sign_get_placed_in_buf(buf_T *buf, linenr_T lnum, int sign_id, const
   tv_dict_add_list(d, S_LEN("signs"), l);
 
   int64_t ns = group_get_ns(group);
-  if (!buf->b_signs || ns < 0) {
+  if (!buf_has_signs(buf) || ns < 0) {
     return;
   }
 
@@ -1006,7 +1011,7 @@ static void sign_get_placed(buf_T *buf, linenr_T lnum, int id, const char *group
     sign_get_placed_in_buf(buf, lnum, id, group, retlist);
   } else {
     FOR_ALL_BUFFERS(cbuf) {
-      if (cbuf->b_signs) {
+      if (buf_has_signs(cbuf)) {
         sign_get_placed_in_buf(cbuf, 0, id, group, retlist);
       }
     }
diff --git a/src/nvim/undo.c b/src/nvim/undo.c
index d517f07b32..11ebbb9bf1 100644
--- a/src/nvim/undo.c
+++ b/src/nvim/undo.c
@@ -67,6 +67,7 @@
 // Uncomment the next line for including the u_check() function.  This warns
 // for errors in the debug information.
 // #define U_DEBUG 1
+#include "nvim/marktree.h"
 #define UH_MAGIC 0x18dade       // value for uh_magic when in use
 #define UE_MAGIC 0xabc123       // value for ue_magic when in use
 
@@ -2390,7 +2391,7 @@ static void u_undoredo(bool undo, bool do_buf_event)
     // may have SpellCap that should be removed or it needs to be
     // displayed.  Schedule the next line for redrawing just in case.
     // Also just in case the line had a sign which needs to be removed.
-    if ((spell_check_window(curwin) || curbuf->b_signs_with_text)
+    if ((spell_check_window(curwin) || buf_meta_total(curbuf, kMTMetaSignText))
         && bot <= curbuf->b_ml.ml_line_count) {
       redrawWinline(curwin, bot);
     }
@@ -2431,7 +2432,7 @@ static void u_undoredo(bool undo, bool do_buf_event)
   int row3 = -1;
   // Tricky: ExtmarkSavePos may come after ExtmarkSplice which does call
   // buf_signcols_count_range() but then misses the yet unrestored marks.
-  if (curbuf->b_signcols.autom && curbuf->b_signs_with_text) {
+  if (curbuf->b_signcols.autom && buf_meta_total(curbuf, kMTMetaSignText)) {
     for (int i = 0; i < (int)kv_size(curhead->uh_extmark); i++) {
       ExtmarkUndoObject undo_info = kv_A(curhead->uh_extmark, i);
       if (undo_info.type == kExtmarkSplice) {
diff --git a/test/unit/marktree_spec.lua b/test/unit/marktree_spec.lua
index 6c70225f0a..676190a440 100644
--- a/test/unit/marktree_spec.lua
+++ b/test/unit/marktree_spec.lua
@@ -34,21 +34,8 @@ local function shadoworder(tree, shadow, iter, giveorder)
     local mark = lib.marktree_itr_current(iter)
     local id = tonumber(mark.id)
     local spos = shadow[id]
-    if mark.pos.row ~= spos[1] or mark.pos.col ~= spos[2] then
-      error(
-        'invalid pos for '
-          .. id
-          .. ':('
-          .. mark.pos.row
-          .. ', '
-          .. mark.pos.col
-          .. ') instead of ('
-          .. spos[1]
-          .. ', '
-          .. spos[2]
-          .. ')'
-      )
-    end
+    eq(mark.pos.row, spos[1], mark.id)
+    eq(mark.pos.col, spos[2], mark.id)
     if lib.mt_right_test(mark) ~= spos[3] then
       error('invalid gravity for ' .. id .. ':(' .. mark.pos.row .. ', ' .. mark.pos.col .. ')')
     end
@@ -100,31 +87,31 @@ local function shadowsplice(shadow, start, old_extent, new_extent)
   end
 end
 
-local function dosplice(tree, shadow, start, old_extent, new_extent)
-  lib.marktree_splice(
-    tree,
-    start[1],
-    start[2],
-    old_extent[1],
-    old_extent[2],
-    new_extent[1],
-    new_extent[2]
-  )
-  shadowsplice(shadow, start, old_extent, new_extent)
+local function dosplice(tree, shadow, start, old, new)
+  lib.marktree_splice(tree, start[1], start[2], old[1], old[2], new[1], new[2])
+  shadowsplice(shadow, start, old, new)
 end
 
 local ns = 10
 local last_id = nil
 
-local function put(tree, row, col, gravitate, end_row, end_col, end_gravitate)
+local function put(tree, row, col, gravity, end_row, end_col, end_gravity)
   last_id = last_id + 1
   local my_id = last_id
 
   end_row = end_row or -1
   end_col = end_col or -1
-  end_gravitate = end_gravitate or false
+  end_gravity = end_gravity or false
 
-  lib.marktree_put_test(tree, ns, my_id, row, col, gravitate, end_row, end_col, end_gravitate)
+  lib.marktree_put_test(tree, ns, my_id, row, col, gravity, end_row, end_col, end_gravity, false)
+  return my_id
+end
+
+local function put_meta(tree, row, col, gravitate, meta)
+  last_id = last_id + 1
+  local my_id = last_id
+
+  lib.marktree_put_test(tree, ns, my_id, row, col, gravitate, -1, -1, false, meta)
   return my_id
 end
 
@@ -580,4 +567,75 @@ describe('marktree', function()
       end
     end
   end)
+
+  itp('works with meta counts', function()
+    local tree = ffi.new('MarkTree[1]') -- zero initialized by luajit
+
+    -- add
+    local shadow = {}
+    for i = 1, 100 do
+      for j = 1, 100 do
+        local gravitate = (i % 2) > 0
+        local inline = (j == 3 or j == 50 or j == 51 or j == 55) and i % 11 == 1
+        inline = inline or ((j >= 80 and j < 85) and i % 3 == 1)
+        local id = put_meta(tree, j, i, gravitate, inline)
+        if inline then
+          shadow[id] = { j, i, gravitate }
+        end
+      end
+      -- checking every insert is too slow, but this is ok
+      lib.marktree_check(tree)
+    end
+
+    lib.marktree_check(tree)
+    local iter = ffi.new('MarkTreeIter[1]')
+    local filter = ffi.new('uint32_t[4]')
+    filter[0] = -1
+    ok(lib.marktree_itr_get_filter(tree, 0, 0, 101, 0, filter, iter))
+    local seen = {}
+    repeat
+      local mark = lib.marktree_itr_current(iter)
+      eq(nil, seen[mark.id])
+      seen[mark.id] = true
+      eq(mark.pos.row, shadow[mark.id][1])
+      eq(mark.pos.col, shadow[mark.id][2])
+    until not lib.marktree_itr_next_filter(tree, iter, 101, 0, filter)
+    eq(tablelength(seen), tablelength(shadow))
+
+    -- delete
+    for id = 1, 10000, 2 do
+      lib.marktree_lookup_ns(tree, ns, id, false, iter)
+      if shadow[id] then
+        local mark = lib.marktree_itr_current(iter)
+        eq(mark.pos.row, shadow[id][1])
+        eq(mark.pos.col, shadow[id][2])
+        shadow[id] = nil
+      end
+      lib.marktree_del_itr(tree, iter, false)
+      if id % 100 == 1 then
+        lib.marktree_check(tree)
+      end
+    end
+
+    -- Splice!
+    dosplice(tree, shadow, { 82, 0 }, { 0, 50 }, { 0, 0 })
+    lib.marktree_check(tree)
+
+    dosplice(tree, shadow, { 81, 50 }, { 2, 50 }, { 1, 0 })
+    lib.marktree_check(tree)
+
+    dosplice(tree, shadow, { 2, 50 }, { 1, 50 }, { 0, 10 })
+    lib.marktree_check(tree)
+
+    ok(lib.marktree_itr_get_filter(tree, 0, 0, 101, 0, filter, iter))
+    seen = {}
+    repeat
+      local mark = lib.marktree_itr_current(iter)
+      eq(nil, seen[mark.id])
+      seen[mark.id] = true
+      eq(mark.pos.row, shadow[mark.id][1])
+      eq(mark.pos.col, shadow[mark.id][2])
+    until not lib.marktree_itr_next_filter(tree, iter, 101, 0, filter)
+    eq(tablelength(seen), tablelength(shadow))
+  end)
 end)