refactor(decorations): break up Decoration struct into smaller pieces

Remove the monolithic Decoration struct. Before this change, each extmark
could either represent just a hl_id + priority value as a inline
decoration, or it would take a pointer to this monolitic 112 byte struct
which has to be allocated.

This change separates the decorations into two pieces: DecorSignHighlight
for signs, highlights and simple set-flag decorations (like spell,
ui-watched), and DecorVirtText for virtual text and lines.

The main separation here is whether they are expected to allocate more
memory. Currently this is not really true as sign text has to be an
allocated string, but the plan is to get rid of this eventually (it can
just be an array of two schar_T:s). Further refactors are expected to
improve the representation of each decoration kind individually. The
goal of this particular PR is to get things started by cutting the
Gordian knot which was the monolithic struct Decoration.

Now, each extmark can either contain chained indicies/pointers to
these kinds of objects, or it can fit a subset of DecorSignHighlight
inline.

The point of this change is not only to make decorations smaller in
memory. In fact, the main motivation is to later allow them to grow
_larger_, but on a dynamic, on demand fashion. As a simple example, it
would be possible to augment highlights to take a list of multiple
`hl_group`:s, which then would trivially map to a chain of multiple
DecorSignHighlight entries.

One small feature improvement included with this refactor itself, is
that the restriction that extmarks cannot be removed inside a decoration
provider has been lifted. These are instead safely lifetime extended
on a "to free" list until the current iteration of screen drawing is done.

NB: flags is a mess. but DecorLevel is useless, this slightly less so

18 files changed, 1088 insertions, 615 deletions

diff --git a/src/nvim/api/deprecated.c b/src/nvim/api/deprecated.c
index 849897b529..b4aa6fe99e 100644
--- a/src/nvim/api/deprecated.c
+++ b/src/nvim/api/deprecated.c
@@ -154,21 +154,25 @@ Integer nvim_buf_set_virtual_text(Buffer buffer, Integer src_id, Integer line, A
     return 0;
   }
 
-  Decoration *existing = decor_find_virttext(buf, (int)line, ns_id);
+  DecorVirtText *existing = decor_find_virttext(buf, (int)line, ns_id);
 
   if (existing) {
-    clear_virttext(&existing->virt_text);
-    existing->virt_text = virt_text;
-    existing->virt_text_width = width;
+    clear_virttext(&existing->data.virt_text);
+    existing->data.virt_text = virt_text;
+    existing->width = width;
     return src_id;
   }
 
-  Decoration decor = DECORATION_INIT;
-  decor.virt_text = virt_text;
-  decor.virt_text_width = width;
-  decor.priority = 0;
+  DecorVirtText *vt = xmalloc(sizeof *vt);
+  *vt = (DecorVirtText)DECOR_VIRT_TEXT_INIT;
+  vt->data.virt_text = virt_text;
+  vt->width = width;
+  vt->priority = 0;
 
-  extmark_set(buf, ns_id, NULL, (int)line, 0, -1, -1, &decor, true, false, false, false, NULL);
+  DecorInline decor = { .ext = true, .data.ext.vt = vt, .data.ext.sh_idx = DECOR_ID_INVALID };
+
+  extmark_set(buf, ns_id, NULL, (int)line, 0, -1, -1, decor, 0, true,
+              false, false, false, NULL);
   return src_id;
 }
 
diff --git a/src/nvim/api/extmark.c b/src/nvim/api/extmark.c
index 31fc01403a..8a2cde8372 100644
--- a/src/nvim/api/extmark.c
+++ b/src/nvim/api/extmark.c
@@ -103,15 +103,6 @@ bool ns_initialized(uint32_t ns)
   return ns < (uint32_t)next_namespace_id;
 }
 
-static Object hl_group_name(int hl_id, bool hl_name)
-{
-  if (hl_name) {
-    return CSTR_TO_OBJ(syn_id2name(hl_id));
-  } else {
-    return INTEGER_OBJ(hl_id);
-  }
-}
-
 Array virt_text_to_array(VirtText vt, bool hl_name)
 {
   Array chunks = ARRAY_DICT_INIT;
@@ -176,85 +167,9 @@ static Array extmark_to_array(MTPair extmark, bool id, bool add_dict, bool hl_na
       PUT(dict, "invalid", BOOLEAN_OBJ(true));
     }
 
-    // pretend this is a pointer for a short while, Decoration will be factored away very soon
-    const Decoration decor[1] = { get_decor(start) };
-    if (decor->hl_id) {
-      PUT(dict, "hl_group", hl_group_name(decor->hl_id, hl_name));
-      PUT(dict, "hl_eol", BOOLEAN_OBJ(decor->hl_eol));
-    }
-    if (decor->hl_mode) {
-      PUT(dict, "hl_mode", CSTR_TO_OBJ(hl_mode_str[decor->hl_mode]));
-    }
-
-    if (kv_size(decor->virt_text)) {
-      Array chunks = virt_text_to_array(decor->virt_text, hl_name);
-      PUT(dict, "virt_text", ARRAY_OBJ(chunks));
-      PUT(dict, "virt_text_hide", BOOLEAN_OBJ(decor->virt_text_hide));
-      if (decor->virt_text_pos == kVTWinCol) {
-        PUT(dict, "virt_text_win_col", INTEGER_OBJ(decor->col));
-      }
-      PUT(dict, "virt_text_pos",
-          CSTR_TO_OBJ(virt_text_pos_str[decor->virt_text_pos]));
-    }
-
-    if (decor->ui_watched) {
-      PUT(dict, "ui_watched", BOOLEAN_OBJ(true));
-    }
-
-    if (kv_size(decor->virt_lines)) {
-      Array all_chunks = ARRAY_DICT_INIT;
-      bool virt_lines_leftcol = false;
-      for (size_t i = 0; i < kv_size(decor->virt_lines); i++) {
-        virt_lines_leftcol = kv_A(decor->virt_lines, i).left_col;
-        Array chunks = virt_text_to_array(kv_A(decor->virt_lines, i).line, hl_name);
-        ADD(all_chunks, ARRAY_OBJ(chunks));
-      }
-      PUT(dict, "virt_lines", ARRAY_OBJ(all_chunks));
-      PUT(dict, "virt_lines_above", BOOLEAN_OBJ(decor->virt_lines_above));
-      PUT(dict, "virt_lines_leftcol", BOOLEAN_OBJ(virt_lines_leftcol));
-    }
-
-    if (decor->sign_text) {
-      PUT(dict, "sign_text", CSTR_TO_OBJ(decor->sign_text));
-    }
-
-    // uncrustify:off
-
-    struct { char *name; const int val; } hls[] = {
-      { "sign_hl_group"      , decor->sign_hl_id       },
-      { "number_hl_group"    , decor->number_hl_id     },
-      { "line_hl_group"      , decor->line_hl_id       },
-      { "cursorline_hl_group", decor->cursorline_hl_id },
-      { NULL, 0 },
-    };
-
-    // uncrustify:on
-
-    for (int j = 0; hls[j].name; j++) {
-      if (hls[j].val) {
-        PUT(dict, hls[j].name, hl_group_name(hls[j].val, hl_name));
-      }
-    }
-
-    if (decor->sign_text
-        || decor->hl_id
-        || kv_size(decor->virt_text)
-        || decor->ui_watched) {
-      PUT(dict, "priority", INTEGER_OBJ(decor->priority));
-    }
-
-    if (decor->conceal) {
-      String name = cstr_to_string((char *)&decor->conceal_char);
-      PUT(dict, "conceal", STRING_OBJ(name));
-    }
-
-    if (decor->spell != kNone) {
-      PUT(dict, "spell", BOOLEAN_OBJ(decor->spell == kTrue));
-    }
+    decor_to_dict_legacy(&dict, mt_decor(start), hl_name);
 
-    if (dict.size) {
-      ADD(rv, DICTIONARY_OBJ(dict));
-    }
+    ADD(rv, DICTIONARY_OBJ(dict));
   }
 
   return rv;
@@ -581,8 +496,14 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
                              Dict(set_extmark) *opts, Error *err)
   FUNC_API_SINCE(7)
 {
-  Decoration decor = DECORATION_INIT;
-  bool has_decor = false;
+  DecorHighlightInline hl = DECOR_HIGHLIGHT_INLINE_INIT;
+  // TODO(bfredl): in principle signs with max one (1) hl group and max 4 bytes of text.
+  // should be a candidate for inlining as well.
+  DecorSignHighlight sign = DECOR_SIGN_HIGHLIGHT_INIT;
+  DecorVirtText virt_text = DECOR_VIRT_TEXT_INIT;
+  DecorVirtText virt_lines = DECOR_VIRT_LINES_INIT;
+  bool has_hl = false;
+  String conceal_char_large = STRING_INIT;
 
   buf_T *buf = find_buffer_by_handle(buffer, err);
   if (!buf) {
@@ -643,11 +564,11 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
     Object *opt;
     int *dest;
   } hls[] = {
-    { "hl_group"           , &opts->hl_group           , &decor.hl_id            },
-    { "sign_hl_group"      , &opts->sign_hl_group      , &decor.sign_hl_id       },
-    { "number_hl_group"    , &opts->number_hl_group    , &decor.number_hl_id     },
-    { "line_hl_group"      , &opts->line_hl_group      , &decor.line_hl_id       },
-    { "cursorline_hl_group", &opts->cursorline_hl_group, &decor.cursorline_hl_id },
+    { "hl_group"           , &opts->hl_group           , &hl.hl_id            },
+    { "sign_hl_group"      , &opts->sign_hl_group      , &sign.hl_id       },
+    { "number_hl_group"    , &opts->number_hl_group    , &sign.number_hl_id     },
+    { "line_hl_group"      , &opts->line_hl_group      , &sign.line_hl_id       },
+    { "cursorline_hl_group", &opts->cursorline_hl_group, &sign.cursorline_hl_id },
     { NULL, NULL, NULL },
   };
 
@@ -655,26 +576,33 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
 
   for (int j = 0; hls[j].name && hls[j].dest; j++) {
     if (hls[j].opt->type != kObjectTypeNil) {
+      if (j > 0) {
+        sign.flags |= kSHIsSign;
+      } else {
+        has_hl = true;
+      }
       *hls[j].dest = object_to_hl_id(*hls[j].opt, hls[j].name, err);
       if (ERROR_SET(err)) {
         goto error;
       }
-      has_decor = true;
     }
   }
 
   if (HAS_KEY(opts, set_extmark, conceal)) {
+    hl.flags |= kSHConceal;
+    has_hl = true;
     String c = opts->conceal;
-    decor.conceal = true;
-    if (c.size) {
-      decor.conceal_char = utf_ptr2char(c.data);
+    if (c.size > 0) {
+      if (c.size <= 4) {
+        memcpy(hl.conceal_char, c.data, c.size + (c.size < 4 ? 1 : 0));
+      } else {
+        conceal_char_large = c;
+      }
     }
-    has_decor = true;
   }
 
   if (HAS_KEY(opts, set_extmark, virt_text)) {
-    decor.virt_text = parse_virt_text(opts->virt_text, err, &decor.virt_text_width);
-    has_decor = true;
+    virt_text.data.virt_text = parse_virt_text(opts->virt_text, err, &virt_text.width);
     if (ERROR_SET(err)) {
       goto error;
     }
@@ -683,13 +611,13 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
   if (HAS_KEY(opts, set_extmark, virt_text_pos)) {
     String str = opts->virt_text_pos;
     if (strequal("eol", str.data)) {
-      decor.virt_text_pos = kVTEndOfLine;
+      virt_text.pos = kVPosEndOfLine;
     } else if (strequal("overlay", str.data)) {
-      decor.virt_text_pos = kVTOverlay;
+      virt_text.pos = kVPosOverlay;
     } else if (strequal("right_align", str.data)) {
-      decor.virt_text_pos = kVTRightAlign;
+      virt_text.pos = kVPosRightAlign;
     } else if (strequal("inline", str.data)) {
-      decor.virt_text_pos = kVTInline;
+      virt_text.pos = kVPosInline;
     } else {
       VALIDATE_S(false, "virt_text_pos", str.data, {
         goto error;
@@ -698,26 +626,26 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
   }
 
   if (HAS_KEY(opts, set_extmark, virt_text_win_col)) {
-    decor.col = (int)opts->virt_text_win_col;
-    decor.virt_text_pos = kVTWinCol;
+    virt_text.col = (int)opts->virt_text_win_col;
+    virt_text.pos = kVPosWinCol;
   }
 
-  decor.hl_eol = opts->hl_eol;
-  decor.virt_text_hide = opts->virt_text_hide;
+  hl.flags |= opts->hl_eol ? kSHHlEol : 0;
+  virt_text.flags |= opts->virt_text_hide ? kVTHide : 0;
 
   if (HAS_KEY(opts, set_extmark, hl_mode)) {
     String str = opts->hl_mode;
     if (strequal("replace", str.data)) {
-      decor.hl_mode = kHlModeReplace;
+      virt_text.hl_mode = kHlModeReplace;
     } else if (strequal("combine", str.data)) {
-      decor.hl_mode = kHlModeCombine;
+      virt_text.hl_mode = kHlModeCombine;
     } else if (strequal("blend", str.data)) {
-      if (decor.virt_text_pos == kVTInline) {
+      if (virt_text.pos == kVPosInline) {
         VALIDATE(false, "%s", "cannot use 'blend' hl_mode with inline virtual text", {
           goto error;
         });
       }
-      decor.hl_mode = kHlModeBlend;
+      virt_text.hl_mode = kHlModeBlend;
     } else {
       VALIDATE_S(false, "hl_mode", str.data, {
         goto error;
@@ -735,29 +663,32 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
       });
       int dummig;
       VirtText jtem = parse_virt_text(a.items[j].data.array, err, &dummig);
-      kv_push(decor.virt_lines, ((struct virt_line){ jtem, virt_lines_leftcol }));
+      kv_push(virt_lines.data.virt_lines, ((struct virt_line){ jtem, virt_lines_leftcol }));
       if (ERROR_SET(err)) {
         goto error;
       }
-      has_decor = true;
     }
   }
 
-  decor.virt_lines_above = opts->virt_lines_above;
+  virt_lines.flags |= opts->virt_lines_above ? kVTLinesAbove : 0;
 
   if (HAS_KEY(opts, set_extmark, priority)) {
     VALIDATE_RANGE((opts->priority >= 0 && opts->priority <= UINT16_MAX), "priority", {
       goto error;
     });
-    decor.priority = (DecorPriority)opts->priority;
+    hl.priority = (DecorPriority)opts->priority;
+    sign.priority = (DecorPriority)opts->priority;
+    virt_text.priority = (DecorPriority)opts->priority;
+    virt_lines.priority = (DecorPriority)opts->priority;
   }
 
   if (HAS_KEY(opts, set_extmark, sign_text)) {
-    VALIDATE_S(init_sign_text(NULL, &decor.sign_text, opts->sign_text.data),
+    sign.text.ptr = NULL;
+    VALIDATE_S(init_sign_text(NULL, &sign.text.ptr, opts->sign_text.data),
                "sign_text", "", {
       goto error;
     });
-    has_decor = true;
+    sign.flags |= kSHIsSign;
   }
 
   bool right_gravity = GET_BOOL_OR_TRUE(opts, set_extmark, right_gravity);
@@ -771,16 +702,18 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
 
   size_t len = 0;
 
-  if (!HAS_KEY(opts, set_extmark, spell)) {
-    decor.spell = kNone;
-  } else {
-    decor.spell = opts->spell ? kTrue : kFalse;
-    has_decor = true;
+  if (HAS_KEY(opts, set_extmark, spell)) {
+    hl.flags |= (opts->spell) ? kSHSpellOn : kSHSpellOff;
+    has_hl = true;
   }
 
-  decor.ui_watched = opts->ui_watched;
-  if (decor.ui_watched) {
-    has_decor = true;
+  if (opts->ui_watched) {
+    hl.flags |= kSHUIWatched;
+    if (virt_text.pos == kVPosOverlay) {
+      // TODO(bfredl): in a revised interface this should be the default.
+      hl.flags |= kSHUIWatchedOverlay;
+    }
+    has_hl = true;
   }
 
   VALIDATE_RANGE((line >= 0), "line", {
@@ -829,28 +762,90 @@ Integer nvim_buf_set_extmark(Buffer buffer, Integer ns_id, Integer line, Integer
     col2 = 0;
   }
 
-  // TODO(bfredl): synergize these two branches even more
   if (opts->ephemeral && decor_state.win && decor_state.win->w_buffer == buf) {
-    decor_push_ephemeral((int)line, (int)col, line2, col2, &decor, (uint64_t)ns_id, id);
+    int r = (int)line;
+    int c = (int)col;
+    if (line2 == -1) {
+      line2 = r;
+      col2 = c;
+    }
+
+    if (kv_size(virt_text.data.virt_text)) {
+      decor_range_add_virt(&decor_state, r, c, line2, col2, decor_put_vt(virt_text, NULL), true);
+    }
+    if (kv_size(virt_lines.data.virt_lines)) {
+      decor_range_add_virt(&decor_state, r, c, line2, col2, decor_put_vt(virt_lines, NULL), true);
+    }
+    if (has_hl) {
+      DecorSignHighlight sh = decor_sh_from_inline(hl, conceal_char_large);
+      decor_range_add_sh(&decor_state, r, c, line2, col2, &sh, true, (uint32_t)ns_id, id);
+    }
+    if (sign.flags & kSHIsSign) {
+      decor_range_add_sh(&decor_state, r, c, line2, col2, &sign, true, (uint32_t)ns_id, id);
+    }
   } else {
     if (opts->ephemeral) {
       api_set_error(err, kErrorTypeException, "not yet implemented");
       goto error;
     }
 
+    uint16_t decor_flags = 0;
+
+    DecorVirtText *decor_alloc = NULL;
+    if (kv_size(virt_text.data.virt_text)) {
+      decor_alloc = decor_put_vt(virt_text, decor_alloc);
+      if (virt_text.pos == kVPosInline) {
+        decor_flags |= MT_FLAG_DECOR_VIRT_TEXT_INLINE;
+      }
+    }
+    if (kv_size(virt_lines.data.virt_lines)) {
+      decor_alloc = decor_put_vt(virt_lines, decor_alloc);
+      decor_flags |= MT_FLAG_DECOR_VIRT_LINES;
+    }
+
+    uint32_t decor_indexed = DECOR_ID_INVALID;
+    if (sign.flags & kSHIsSign) {
+      decor_indexed = decor_put_sh(sign);
+      if (sign.text.ptr != NULL) {
+        decor_flags |= MT_FLAG_DECOR_SIGNTEXT;
+      }
+      if (sign.number_hl_id || sign.line_hl_id || sign.cursorline_hl_id) {
+        decor_flags |= MT_FLAG_DECOR_SIGNHL;
+      }
+    }
+
+    DecorInline decor = DECOR_INLINE_INIT;
+    if (decor_alloc || decor_indexed != DECOR_ID_INVALID || conceal_char_large.size) {
+      if (has_hl) {
+        DecorSignHighlight sh = decor_sh_from_inline(hl, conceal_char_large);
+        sh.next = decor_indexed;
+        decor_indexed = decor_put_sh(sh);
+      }
+      decor.ext = true;
+      decor.data.ext = (DecorExt){ .sh_idx = decor_indexed, .vt = decor_alloc };
+    } else {
+      decor.data.hl = hl;
+    }
+
+    if (has_hl) {
+      decor_flags |= MT_FLAG_DECOR_HL;
+    }
+
     extmark_set(buf, (uint32_t)ns_id, &id, (int)line, (colnr_T)col, line2, col2,
-                has_decor ? &decor : NULL, right_gravity, opts->end_right_gravity,
+                decor, decor_flags, right_gravity, opts->end_right_gravity,
                 !GET_BOOL_OR_TRUE(opts, set_extmark, undo_restore),
                 opts->invalidate, err);
     if (ERROR_SET(err)) {
-      goto error;
+      decor_free(decor);
+      return 0;
     }
   }
 
   return (Integer)id;
 
 error:
-  decor_clear(&decor);
+  clear_virttext(&virt_text.data.virt_text);
+  clear_virtlines(&virt_lines.data.virt_lines);
   return 0;
 }
 
@@ -873,11 +868,6 @@ Boolean nvim_buf_del_extmark(Buffer buffer, Integer ns_id, Integer id, Error *er
     return false;
   });
 
-  if (decor_state.running_on_lines) {
-    api_set_error(err, kErrorTypeValidation, "Cannot remove extmarks during on_line callbacks");
-    return false;
-  }
-
   return extmark_del_id(buf, (uint32_t)ns_id, (uint32_t)id);
 }
 
@@ -962,13 +952,11 @@ Integer nvim_buf_add_highlight(Buffer buffer, Integer ns_id, String hl_group, In
     end_line++;
   }
 
-  Decoration decor = DECORATION_INIT;
-  decor.hl_id = hl_id;
+  DecorInline decor = DECOR_INLINE_INIT;
+  decor.data.hl.hl_id = hl_id;
 
-  extmark_set(buf, ns, NULL,
-              (int)line, (colnr_T)col_start,
-              end_line, (colnr_T)col_end,
-              &decor, true, false, false, false, NULL);
+  extmark_set(buf, ns, NULL, (int)line, (colnr_T)col_start, end_line, (colnr_T)col_end,
+              decor, MT_FLAG_DECOR_HL, true, false, false, false, NULL);
   return ns_id;
 }
 
@@ -997,11 +985,6 @@ void nvim_buf_clear_namespace(Buffer buffer, Integer ns_id, Integer line_start,
     return;
   });
 
-  if (decor_state.running_on_lines) {
-    api_set_error(err, kErrorTypeValidation, "Cannot remove extmarks during on_line callbacks");
-    return;
-  }
-
   if (line_end < 0 || line_end > MAXLNUM) {
     line_end = MAXLNUM;
   }
diff --git a/src/nvim/decoration.c b/src/nvim/decoration.c
index b784d8bea3..91d5bfcc54 100644
--- a/src/nvim/decoration.c
+++ b/src/nvim/decoration.c
@@ -1,6 +1,7 @@
 #include <assert.h>
 #include <limits.h>
 
+#include "nvim/api/extmark.h"
 #include "nvim/buffer.h"
 #include "nvim/decoration.h"
 #include "nvim/drawscreen.h"
@@ -17,6 +18,17 @@
 # include "decoration.c.generated.h"
 #endif
 
+// TODO(bfredl): These should maybe be per-buffer, so that all resources
+// asssociated with a buffer can be freed when the buffer is unloaded.
+kvec_t(DecorSignHighlight) decor_items = KV_INITIAL_VALUE;
+uint32_t decor_freelist = UINT32_MAX;
+
+// Decorations might be requested to be deleted in a callback in the middle of redrawing.
+// In this case, there might still be live references to the memory allocated for the decoration.
+// Keep a "to free" list which can be safely processed when redrawing is done.
+DecorVirtText *to_free_virt = NULL;
+uint32_t to_free_sh = UINT32_MAX;
+
 /// Add highlighting to a buffer, bounded by two cursor positions,
 /// with an offset.
 ///
@@ -35,8 +47,8 @@ void bufhl_add_hl_pos_offset(buf_T *buf, int src_id, int hl_id, lpos_T pos_start
 {
   colnr_T hl_start = 0;
   colnr_T hl_end = 0;
-  Decoration decor = DECORATION_INIT;
-  decor.hl_id = hl_id;
+  DecorInline decor = DECOR_INLINE_INIT;
+  decor.data.hl.hl_id = hl_id;
 
   // TODO(bfredl): if decoration had blocky mode, we could avoid this loop
   for (linenr_T lnum = pos_start.lnum; lnum <= pos_end.lnum; lnum++) {
@@ -61,113 +73,271 @@ void bufhl_add_hl_pos_offset(buf_T *buf, int src_id, int hl_id, lpos_T pos_start
       hl_start = pos_start.col + offset;
       hl_end = pos_end.col + offset;
     }
+
     extmark_set(buf, (uint32_t)src_id, NULL,
                 (int)lnum - 1, hl_start, (int)lnum - 1 + end_off, hl_end,
-                &decor, true, false, true, false, NULL);
+                decor, MT_FLAG_DECOR_HL, true, false, true, false, NULL);
   }
 }
 
-void decor_redraw(buf_T *buf, int row1, int row2, Decoration *decor)
+void decor_redraw(buf_T *buf, int row1, int row2, DecorInline decor)
 {
   if (row2 >= row1) {
-    if (!decor
-        || decor->hl_id
-        || decor_has_sign(decor)
-        || decor->conceal
-        || decor->spell != kNone) {
-      redraw_buf_range_later(buf, row1 + 1, row2 + 1);
+    redraw_buf_range_later(buf, row1 + 1, row2 + 1);
+  }
+
+  if (decor.ext) {
+    DecorVirtText *vt = decor.data.ext.vt;
+    while (vt) {
+      if (vt->flags & kVTIsLines) {
+        redraw_buf_line_later(buf, row1 + 1 + ((vt->flags & kVTLinesAbove) ? 0 : 1), true);
+        changed_line_display_buf(buf);
+      } else {
+        if (vt->pos == kVPosInline) {
+          changed_line_display_buf(buf);
+        }
+      }
+      vt = vt->next;
     }
+
+    uint32_t idx = decor.data.ext.sh_idx;
+    while (idx != DECOR_ID_INVALID) {
+      DecorSignHighlight *sh = &kv_A(decor_items, idx);
+      decor_redraw_sh(buf, row1, row2, *sh);
+      idx = sh->next;
+    }
+  } else {
+    decor_redraw_sh(buf, row1, row2, decor_sh_from_inline(decor.data.hl, (String)STRING_INIT));
   }
+}
 
-  if (decor && decor_virt_pos(decor)) {
-    redraw_buf_line_later(buf, row1 + 1, false);
-    if (decor->virt_text_pos == kVTInline) {
-      changed_line_display_buf(buf);
+void decor_redraw_sh(buf_T *buf, int row1, int row2, DecorSignHighlight sh)
+{
+  if (sh.hl_id || (sh.flags & (kSHIsSign|kSHSpellOn|kSHSpellOff))) {
+    if (row2 >= row1) {
+      redraw_buf_range_later(buf, row1 + 1, row2 + 1);
     }
   }
+  if (sh.flags & kSHUIWatched) {
+    redraw_buf_line_later(buf, row1 + 1, false);
+  }
+}
 
-  if (decor && kv_size(decor->virt_lines)) {
-    redraw_buf_line_later(buf, row1 + 1 + (decor->virt_lines_above ? 0 : 1), true);
-    changed_line_display_buf(buf);
+uint32_t decor_put_sh(DecorSignHighlight item)
+{
+  if (decor_freelist != UINT32_MAX) {
+    uint32_t pos = decor_freelist;
+    decor_freelist = kv_A(decor_items, decor_freelist).next;
+    kv_A(decor_items, pos) = item;
+    return pos;
+  } else {
+    uint32_t pos = (uint32_t)kv_size(decor_items);
+    kv_push(decor_items, item);
+    return pos;
   }
 }
 
-static int sign_add_id = 0;
+DecorVirtText *decor_put_vt(DecorVirtText vt, DecorVirtText *next)
+{
+  DecorVirtText *decor_alloc = xmalloc(sizeof *decor_alloc);
+  *decor_alloc = vt;
+  decor_alloc->next = next;
+  return decor_alloc;
+}
 
-void decor_add(buf_T *buf, int row, int row2, Decoration *decor, bool hl_id)
+DecorSignHighlight decor_sh_from_inline(DecorHighlightInline item, String conceal_large)
 {
-  if (decor) {
-    if (kv_size(decor->virt_text) && decor->virt_text_pos == kVTInline) {
-      buf->b_virt_text_inline++;
+  // TODO(bfredl): Eventually simple signs will be inlinable as well
+  assert(!(item.flags & kSHIsSign));
+  DecorSignHighlight conv = {
+    .flags = item.flags,
+    .priority = item.priority,
+    .text.data = { 0 },
+    .hl_id = item.hl_id,
+    .number_hl_id = 0,
+    .line_hl_id = 0,
+    .cursorline_hl_id = 0,
+    .next = DECOR_ID_INVALID,
+  };
+
+  // TODO(bfredl): 'tis a little bullshit. Won't need it once conceals and signs to use schar_T
+  if (conceal_large.size) {
+    String c = conceal_large;
+    if (c.size <= 8) {
+      memcpy(conv.text.data, c.data, c.size + (c.size < 8 ? 1 : 0));
+    } else {
+      conv.flags |= kSHConcealAlloc;
+      conv.text.ptr = xstrdup(conceal_large.data);
+    }
+  } else {
+    memcpy(conv.text.data, item.conceal_char, 4);
+    conv.text.data[4] = NUL;
+  }
+  return conv;
+}
+
+void buf_put_decor(buf_T *buf, DecorInline decor, int row)
+{
+  if (decor.ext) {
+    if (decor.data.ext.vt) {
+      buf_put_decor_virt(buf, decor.data.ext.vt);
     }
-    if (kv_size(decor->virt_lines)) {
-      buf->b_virt_line_blocks++;
+    if (decor.data.ext.sh_idx != DECOR_ID_INVALID) {
+      buf_put_decor_sh(buf, &kv_A(decor_items, decor.data.ext.sh_idx), row);
     }
-    if (decor_has_sign(decor)) {
-      decor->sign_add_id = sign_add_id++;
-      buf->b_signs++;
+  }
+}
+
+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 (decor->sign_text) {
+  }
+  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 row)
+{
+  if (sh->flags & kSHIsSign) {
+    sh->sign_add_id = sign_add_id++;
+    buf->b_signs++;
+    if (sh->text.ptr) {
       buf->b_signs_with_text++;
       buf_signcols_add_check(buf, row + 1);
     }
   }
-  if (decor || hl_id) {
-    decor_redraw(buf, row, row2 > -1 ? row2 : row, decor);
-  }
 }
 
-void decor_remove(buf_T *buf, int row, int row2, Decoration *decor, bool invalidate)
+void buf_decor_remove(buf_T *buf, int row, int row2, DecorInline decor, bool free)
 {
   decor_redraw(buf, row, row2, decor);
-  if (decor) {
-    if (kv_size(decor->virt_text) && decor->virt_text_pos == kVTInline) {
+  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);
+      buf_remove_decor_sh(buf, row, row2, sh);
+      idx = sh->next;
+    }
+    if (free) {
+      decor_free(decor);
+    }
+  }
+}
+
+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--;
     }
-    if (kv_size(decor->virt_lines)) {
-      assert(buf->b_virt_line_blocks > 0);
-      buf->b_virt_line_blocks--;
-    }
-    if (decor_has_sign(decor)) {
-      assert(buf->b_signs > 0);
-      buf->b_signs--;
-      if (decor->sign_text) {
-        assert(buf->b_signs_with_text > 0);
-        buf->b_signs_with_text--;
-        if (row2 >= row) {
-          buf_signcols_del_check(buf, row + 1, row2 + 1);
-        }
+  }
+}
+
+void buf_remove_decor_sh(buf_T *buf, int row, int row2, DecorSignHighlight *sh)
+{
+  if (sh->flags & kSHIsSign) {
+    assert(buf->b_signs > 0);
+    buf->b_signs--;
+    if (sh->text.ptr) {
+      assert(buf->b_signs_with_text > 0);
+      buf->b_signs_with_text--;
+      if (row2 >= row) {
+        buf_signcols_del_check(buf, row + 1, row2 + 1);
       }
     }
   }
-  if (!invalidate) {
-    decor_free(decor);
-  }
 }
 
-void decor_clear(Decoration *decor)
+void decor_free(DecorInline decor)
 {
-  clear_virttext(&decor->virt_text);
-  for (size_t i = 0; i < kv_size(decor->virt_lines); i++) {
-    clear_virttext(&kv_A(decor->virt_lines, i).line);
+  if (!decor.ext) {
+    return;
+  }
+  DecorVirtText *vt = decor.data.ext.vt;
+  uint32_t idx = decor.data.ext.sh_idx;
+
+  if (decor_state.running_decor_provider) {
+    while (vt) {
+      if (vt->next == NULL) {
+        vt->next = to_free_virt;
+        to_free_virt = decor.data.ext.vt;
+        break;
+      }
+      vt = vt->next;
+    }
+    while (idx != DECOR_ID_INVALID) {
+      DecorSignHighlight *sh = &kv_A(decor_items, idx);
+      if (sh->next == DECOR_ID_INVALID) {
+        sh->next = to_free_sh;
+        to_free_sh = decor.data.ext.sh_idx;
+        break;
+      }
+      idx = sh->next;
+    }
+  } else {
+    // safe to delete right now
+    decor_free_inner(vt, idx);
   }
-  kv_destroy(decor->virt_lines);
-  xfree(decor->sign_text);
-  xfree(decor->sign_name);
 }
 
-void decor_free(Decoration *decor)
+void decor_free_inner(DecorVirtText *vt, uint32_t first_idx)
 {
-  if (decor) {
-    decor_clear(decor);
-    xfree(decor);
+  while (vt) {
+    if (vt->flags & kVTIsLines) {
+      clear_virtlines(&vt->data.virt_lines);
+    } else {
+      clear_virttext(&vt->data.virt_text);
+    }
+    DecorVirtText *tofree = vt;
+    vt = vt->next;
+    xfree(tofree);
+  }
+
+  uint32_t idx = first_idx;
+  while (idx != DECOR_ID_INVALID) {
+    DecorSignHighlight *sh = &kv_A(decor_items, idx);
+    if (sh->flags & (kSHIsSign | kSHConcealAlloc)) {
+      xfree(sh->text.ptr);
+    }
+    if (sh->flags & kSHIsSign) {
+      xfree(sh->sign_name);
+    }
+    if (sh->next == DECOR_ID_INVALID) {
+      sh->next = decor_freelist;
+      decor_freelist = first_idx;
+      break;
+    }
+    idx = sh->next;
   }
 }
 
+void decor_check_to_be_deleted(void)
+{
+  assert(!decor_state.running_decor_provider);
+  decor_free_inner(to_free_virt, to_free_sh);
+  to_free_virt = NULL;
+  to_free_sh = DECOR_ID_INVALID;
+}
+
 void decor_state_free(DecorState *state)
 {
-  xfree(state->active.items);
+  kv_destroy(state->active);
 }
 
 void clear_virttext(VirtText *text)
@@ -179,6 +349,15 @@ void clear_virttext(VirtText *text)
   *text = (VirtText)KV_INITIAL_VALUE;
 }
 
+void clear_virtlines(VirtLines *lines)
+{
+  for (size_t i = 0; i < kv_size(*lines); i++) {
+    clear_virttext(&kv_A(*lines, i).line);
+  }
+  kv_destroy(*lines);
+  *lines = (VirtLines)KV_INITIAL_VALUE;
+}
+
 /// Get the next chunk of a virtual text item.
 ///
 /// @param[in]     vt    The virtual text item
@@ -197,7 +376,7 @@ char *next_virt_text_chunk(VirtText vt, size_t *pos, int *attr)
   return text;
 }
 
-Decoration *decor_find_virttext(buf_T *buf, int row, uint64_t ns_id)
+DecorVirtText *decor_find_virttext(buf_T *buf, int row, uint64_t ns_id)
 {
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, row, 0,  itr);
@@ -205,12 +384,14 @@ Decoration *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) || marktree_decor_level(mark) < kDecorLevelVisible) {
+    } else if (mt_invalid(mark) || !(mark.flags & MT_FLAG_DECOR_EXT)) {
       goto next_mark;
     }
-    Decoration *decor = mark.decor_full;
-    if ((ns_id == 0 || ns_id == mark.ns)
-        && decor && kv_size(decor->virt_text)) {
+    DecorVirtText *decor = mark.decor_data.ext.vt;
+    while (decor && (decor->flags & kVTIsLines)) {
+      decor = decor->next;
+    }
+    if ((ns_id == 0 || ns_id == mark.ns) && decor) {
       return decor;
     }
 next_mark:
@@ -225,30 +406,30 @@ bool decor_redraw_reset(win_T *wp, DecorState *state)
   state->win = wp;
   for (size_t i = 0; i < kv_size(state->active); i++) {
     DecorRange item = kv_A(state->active, i);
-    if (item.virt_text_owned) {
-      clear_virttext(&item.decor.virt_text);
+    if (item.owned && item.kind == kDecorKindVirtText) {
+      clear_virttext(&item.data.vt->data.virt_text);
+      xfree(item.data.vt);
     }
   }
   kv_size(state->active) = 0;
   return wp->w_buffer->b_marktree->n_keys;
 }
 
-Decoration get_decor(MTKey mark)
+/// @return true if decor has a virtual position (virtual text or ui_watched)
+bool decor_virt_pos(const DecorRange *decor)
 {
-  if (mark.decor_full) {
-    return *mark.decor_full;
-  }
-  Decoration fake = DECORATION_INIT;
-  fake.hl_id = mark.hl_id;
-  fake.priority = mark.priority;
-  fake.hl_eol = (mark.flags & MT_FLAG_HL_EOL);
-  return fake;
+  return (decor->kind == kDecorKindVirtText || decor->kind == kDecorKindUIWatched);
 }
 
-/// @return true if decor has a virtual position (virtual text or ui_watched)
-bool decor_virt_pos(const Decoration *const decor)
+VirtTextPos decor_virt_pos_kind(const DecorRange *decor)
 {
-  return kv_size(decor->virt_text) || decor->ui_watched;
+  if (decor->kind == kDecorKindVirtText) {
+    return decor->data.vt->pos;
+  }
+  if (decor->kind == kDecorKindUIWatched) {
+    return decor->data.ui.pos;
+  }
+  return kVPosEndOfLine;  // not used; return whatever
 }
 
 bool decor_redraw_start(win_T *wp, int top_row, DecorState *state)
@@ -261,14 +442,14 @@ bool decor_redraw_start(win_T *wp, int top_row, DecorState *state)
   MTPair pair;
 
   while (marktree_itr_step_overlap(buf->b_marktree, state->itr, &pair)) {
-    if (mt_invalid(pair.start) || marktree_decor_level(pair.start) < kDecorLevelVisible) {
+    MTKey m = pair.start;
+    if (mt_invalid(m) || !mt_decor_any(m)) {
       continue;
     }
 
-    Decoration decor = get_decor(pair.start);
-
-    decor_push(state, pair.start.pos.row, pair.start.pos.col, pair.end_pos.row, pair.end_pos.col,
-               &decor, false, pair.start.ns, pair.start.id);
+    decor_range_add_from_inline(state, pair.start.pos.row, pair.start.pos.col, pair.end_pos.row,
+                                pair.end_pos.col,
+                                mt_decor(m), false, m.ns, m.id);
   }
 
   return true;  // TODO(bfredl): check if available in the region
@@ -291,20 +472,35 @@ bool decor_redraw_line(win_T *wp, int row, DecorState *state)
   return (k.pos.row >= 0 && k.pos.row <= row);
 }
 
-static void decor_push(DecorState *state, int start_row, int start_col, int end_row, int end_col,
-                       Decoration *decor, bool owned, uint64_t ns_id, uint64_t mark_id)
+static void decor_range_add_from_inline(DecorState *state, int start_row, int start_col,
+                                        int end_row, int end_col, DecorInline decor, bool owned,
+                                        uint32_t ns, uint32_t mark_id)
 {
-  int attr_id = decor->hl_id > 0 ? syn_id2attr(decor->hl_id) : 0;
-
-  DecorRange range = { start_row, start_col, end_row, end_col,
-                       *decor, attr_id,
-                       kv_size(decor->virt_text) && owned, -10, ns_id, mark_id };
+  if (decor.ext) {
+    DecorVirtText *vt = decor.data.ext.vt;
+    while (vt) {
+      decor_range_add_virt(state, start_row, start_col, end_row, end_col, vt, owned);
+      vt = vt->next;
+    }
+    uint32_t idx = decor.data.ext.sh_idx;
+    while (idx != DECOR_ID_INVALID) {
+      DecorSignHighlight *sh = &kv_A(decor_items, idx);
+      decor_range_add_sh(state, start_row, start_col, end_row, end_col, sh, owned, ns, mark_id);
+      idx = sh->next;
+    }
+  } else {
+    DecorSignHighlight sh = decor_sh_from_inline(decor.data.hl, (String)STRING_INIT);
+    decor_range_add_sh(state, start_row, start_col, end_row, end_col, &sh, owned, ns, mark_id);
+  }
+}
 
+static void decor_range_insert(DecorState *state, DecorRange range)
+{
   kv_pushp(state->active);
   size_t index;
   for (index = kv_size(state->active) - 1; index > 0; index--) {
     DecorRange item = kv_A(state->active, index - 1);
-    if (item.decor.priority <= range.decor.priority) {
+    if (item.priority <= range.priority) {
       break;
     }
     kv_A(state->active, index) = kv_A(state->active, index - 1);
@@ -312,13 +508,60 @@ static void decor_push(DecorState *state, int start_row, int start_col, int end_
   kv_A(state->active, index) = range;
 }
 
+void decor_range_add_virt(DecorState *state, int start_row, int start_col, int end_row, int end_col,
+                          DecorVirtText *vt, bool owned)
+{
+  bool is_lines = vt->flags & kVTIsLines;
+  DecorRange range = {
+    .start_row = start_row, .start_col = start_col, .end_row = end_row, .end_col = end_col,
+    .kind = is_lines ? kDecorKindVirtLines : kDecorKindVirtText,
+    .data.vt = vt,
+    .attr_id = 0,
+    .owned = owned,
+    .priority = vt->priority,
+    .draw_col = -10,
+  };
+  decor_range_insert(state, range);
+}
+
+void decor_range_add_sh(DecorState *state, int start_row, int start_col, int end_row, int end_col,
+                        DecorSignHighlight *sh, bool owned, uint32_t ns, uint32_t mark_id)
+{
+  DecorRange range = {
+    .start_row = start_row, .start_col = start_col, .end_row = end_row, .end_col = end_col,
+    .kind = kDecorKindHighlight,
+    .data.sh = *sh,
+    .attr_id = 0,
+    .owned = owned,
+    .priority = sh->priority,
+    .draw_col = -10,
+  };
+
+  if (sh->hl_id || (sh->flags & (kSHIsSign | kSHConceal | kSHSpellOn | kSHSpellOff))) {
+    if (sh->hl_id) {
+      range.attr_id = syn_id2attr(sh->hl_id);
+    }
+    decor_range_insert(state, range);
+  }
+
+  if (sh->flags & (kSHUIWatched)) {
+    range.kind = kDecorKindUIWatched;
+    range.data.ui.ns_id = ns;
+    range.data.ui.mark_id = mark_id;
+    range.data.ui.pos = (sh->flags & kSHUIWatchedOverlay) ? kVPosOverlay : kVPosEndOfLine;
+    decor_range_insert(state, range);
+  }
+}
+
 /// Initialize the draw_col of a newly-added virtual text item.
 static void decor_init_draw_col(int win_col, bool hidden, DecorRange *item)
 {
-  if (win_col < 0 && item->decor.virt_text_pos != kVTInline) {
+  DecorVirtText *vt = item->kind == kDecorKindVirtText ? item->data.vt : NULL;
+  VirtTextPos pos = decor_virt_pos_kind(item);
+  if (win_col < 0 && pos != kVPosInline) {
     item->draw_col = win_col;
-  } else if (item->decor.virt_text_pos == kVTOverlay) {
-    item->draw_col = (item->decor.virt_text_hide && hidden) ? INT_MIN : win_col;
+  } else if (pos == kVPosOverlay) {
+    item->draw_col = (vt && (vt->flags & kVTHide) && hidden) ? INT_MIN : win_col;
   } else {
     item->draw_col = -1;
   }
@@ -352,19 +595,17 @@ int decor_redraw_col(win_T *wp, int col, int win_col, bool hidden, DecorState *s
       break;
     }
 
-    if (mt_invalid(mark) || mt_end(mark) || marktree_decor_level(mark) < kDecorLevelVisible) {
+    if (mt_invalid(mark) || mt_end(mark) || !mt_decor_any(mark)) {
       goto next_mark;
     }
 
-    Decoration decor = get_decor(mark);
-
     MTPos endpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
     if (endpos.row == -1) {
       endpos = mark.pos;
     }
 
-    decor_push(state, mark.pos.row, mark.pos.col, endpos.row, endpos.col,
-               &decor, false, mark.ns, mark.id);
+    decor_range_add_from_inline(state, mark.pos.row, mark.pos.col, endpos.row, endpos.col,
+                                mt_decor(mark), false, mark.ns, mark.id);
 
 next_mark:
     marktree_itr_next(buf->b_marktree, state->itr);
@@ -382,7 +623,7 @@ next_mark:
     bool active = false, keep = true;
     if (item.end_row < state->row
         || (item.end_row == state->row && item.end_col <= col)) {
-      if (!(item.start_row >= state->row && decor_virt_pos(&item.decor))) {
+      if (!(item.start_row >= state->row && decor_virt_pos(&item))) {
         keep = false;
       }
     } else {
@@ -401,26 +642,35 @@ next_mark:
     if (active && item.attr_id > 0) {
       attr = hl_combine_attr(attr, item.attr_id);
     }
-    if (active && item.decor.conceal) {
+    if (active && item.kind == kDecorKindHighlight && (item.data.sh.flags & kSHConceal)) {
       conceal = 1;
       if (item.start_row == state->row && item.start_col == col) {
+        DecorSignHighlight *sh = &item.data.sh;
         conceal = 2;
-        conceal_char = item.decor.conceal_char;
+        char *text = (sh->flags & kSHConcealAlloc) ? sh->text.ptr : sh->text.data;
+        // TODO(bfredl): kSHConcealAlloc is obviously a waste unless we change
+        // `conceal_char` to schar_T
+        conceal_char = utf_ptr2char(text);
         state->col_until = MIN(state->col_until, item.start_col);
         conceal_attr = item.attr_id;
       }
     }
-    if (active && item.decor.spell != kNone) {
-      spell = item.decor.spell;
+    if (active && item.kind == kDecorKindHighlight) {
+      if (item.data.sh.flags & kSHSpellOn) {
+        spell = kTrue;
+      } else if (item.data.sh.flags & kSHSpellOff) {
+        spell = kFalse;
+      }
     }
     if (item.start_row == state->row && item.start_col <= col
-        && decor_virt_pos(&item.decor) && item.draw_col == -10) {
+        && decor_virt_pos(&item) && item.draw_col == -10) {
       decor_init_draw_col(win_col, hidden, &item);
     }
     if (keep) {
       kv_A(state->active, j++) = item;
-    } else if (item.virt_text_owned) {
-      clear_virttext(&item.decor.virt_text);
+    } else if (item.owned && item.kind == kDecorKindVirtText) {
+      clear_virttext(&item.data.vt->data.virt_text);
+      xfree(item.data.vt);
     }
   }
   kv_size(state->active) = j;
@@ -432,6 +682,21 @@ next_mark:
   return attr;
 }
 
+typedef struct {
+  DecorSignHighlight *sh;
+  uint32_t id;
+} SignItem;
+
+int sign_item_cmp(const void *p1, const void *p2)
+{
+  const SignItem *s1 = (SignItem *)p1;
+  const SignItem *s2 = (SignItem *)p2;
+  int n = s2->sh->priority - s1->sh->priority;
+
+  return n ? n : (n = (int)(s2->id - s1->id))
+         ? n : (s2->sh->sign_add_id - s1->sh->sign_add_id);
+}
+
 /// Return the sign attributes on the currently refreshed row.
 ///
 /// @param[out] sattrs Output array for sign text and texthl id
@@ -450,13 +715,15 @@ void decor_redraw_signs(win_T *wp, buf_T *buf, int row, SignTextAttrs sattrs[],
 
   MTPair pair;
   int num_text = 0;
-  kvec_t(MTKey) signs = KV_INITIAL_VALUE;
+  kvec_t(SignItem) signs = KV_INITIAL_VALUE;
   // TODO(bfredl): integrate with main decor loop.
   while (marktree_itr_step_overlap(buf->b_marktree, itr, &pair)) {
-    if (!mt_invalid(pair.start) && pair.start.decor_full && decor_has_sign(pair.start.decor_full)) {
-      pair.start.pos.row = row;
-      num_text += (pair.start.decor_full->sign_text != NULL);
-      kv_push(signs, pair.start);
+    if (!mt_invalid(pair.start) && mt_decor_sign(pair.start)) {
+      DecorSignHighlight *sh = decor_find_sign(mt_decor(pair.start));
+      if (sh) {
+        num_text += (sh->text.ptr != NULL);
+        kv_push(signs, ((SignItem){ sh, pair.start.id }));
+      }
     }
   }
 
@@ -465,38 +732,60 @@ void decor_redraw_signs(win_T *wp, buf_T *buf, int row, SignTextAttrs sattrs[],
     if (mark.pos.row != row) {
       break;
     }
-    if (!mt_end(mark) && !mt_invalid(mark) && mark.decor_full && decor_has_sign(mark.decor_full)) {
-      num_text += (mark.decor_full->sign_text != NULL);
-      kv_push(signs, mark);
+    if (!mt_end(mark) && !mt_invalid(mark) && mt_decor_sign(mark)) {
+      DecorSignHighlight *sh = decor_find_sign(mt_decor(mark));
+      if (sh) {
+        num_text += (sh->text.ptr != NULL);
+        kv_push(signs, ((SignItem){ sh, mark.id }));
+      }
     }
+
     marktree_itr_next(buf->b_marktree, itr);
   }
 
   if (kv_size(signs)) {
     int width = wp->w_minscwidth == SCL_NUM ? 1 : wp->w_scwidth;
     int idx = MIN(width, num_text) - 1;
-    qsort((void *)&kv_A(signs, 0), kv_size(signs), sizeof(MTKey), sign_cmp);
+    qsort((void *)&kv_A(signs, 0), kv_size(signs), sizeof(kv_A(signs, 0)), sign_item_cmp);
 
     for (size_t i = 0; i < kv_size(signs); i++) {
-      Decoration *decor = kv_A(signs, i).decor_full;
-      if (idx >= 0 && decor->sign_text) {
-        sattrs[idx].text = decor->sign_text;
-        sattrs[idx--].hl_id = decor->sign_hl_id;
+      DecorSignHighlight *sh = kv_A(signs, i).sh;
+      if (idx >= 0 && sh->text.ptr) {
+        sattrs[idx].text = sh->text.ptr;
+        sattrs[idx--].hl_id = sh->hl_id;
       }
       if (*num_id == 0) {
-        *num_id = decor->number_hl_id;
+        *num_id = sh->number_hl_id;
       }
       if (*line_id == 0) {
-        *line_id = decor->line_hl_id;
+        *line_id = sh->line_hl_id;
       }
       if (*cul_id == 0) {
-        *cul_id = decor->cursorline_hl_id;
+        *cul_id = sh->cursorline_hl_id;
       }
     }
     kv_destroy(signs);
   }
 }
 
+DecorSignHighlight *decor_find_sign(DecorInline decor)
+{
+  if (!decor.ext) {
+    return NULL;
+  }
+  uint32_t decor_id = decor.data.ext.sh_idx;
+  while (true) {
+    if (decor_id == DECOR_ID_INVALID) {
+      return NULL;
+    }
+    DecorSignHighlight *sh = &kv_A(decor_items, decor_id);
+    if (sh->flags & kSHIsSign) {
+      return sh;
+    }
+    decor_id = sh->next;
+  }
+}
+
 // Get the maximum required amount of sign columns needed between row and
 // end_row.
 int decor_signcols(buf_T *buf, int row, int end_row, int max)
@@ -510,6 +799,8 @@ int decor_signcols(buf_T *buf, int row, int end_row, int max)
   }
 
   int signcols = 0;  // highest value of count
+  // TODO(bfredl): only need to use marktree_itr_get_overlap once.
+  // then we can process both start and end events and update state for each row
   for (int currow = row; currow <= end_row; currow++) {
     MarkTreeIter itr[1];
     if (!marktree_itr_get_overlap(buf->b_marktree, currow, 0, itr)) {
@@ -519,7 +810,7 @@ int decor_signcols(buf_T *buf, int row, int end_row, int max)
     int count = 0;
     MTPair pair;
     while (marktree_itr_step_overlap(buf->b_marktree, itr, &pair)) {
-      if (!mt_invalid(pair.start) && pair.start.decor_full && pair.start.decor_full->sign_text) {
+      if (!mt_invalid(pair.start) && (pair.start.flags & MT_FLAG_DECOR_SIGNTEXT)) {
         count++;
       }
     }
@@ -529,8 +820,11 @@ int decor_signcols(buf_T *buf, int row, int end_row, int max)
       if (mark.pos.row != currow) {
         break;
       }
-      if (!mt_invalid(mark) && !mt_end(mark) && mark.decor_full && mark.decor_full->sign_text) {
-        count++;
+      if (!mt_invalid(mark) && !mt_end(mark) && (mark.flags & MT_FLAG_DECOR_SIGNTEXT)) {
+        DecorSignHighlight *sh = decor_find_sign(mt_decor(mark));
+        if (sh && sh->text.ptr) {
+          count++;
+        }
       }
       marktree_itr_next(buf->b_marktree, itr);
     }
@@ -558,28 +852,19 @@ bool decor_redraw_eol(win_T *wp, DecorState *state, int *eol_attr, int eol_col)
 {
   decor_redraw_col(wp, MAXCOL, MAXCOL, false, state);
   state->eol_col = eol_col;
-  bool has_virttext = false;
+  bool has_virt_pos = false;
   for (size_t i = 0; i < kv_size(state->active); i++) {
     DecorRange item = kv_A(state->active, i);
-    if (item.start_row == state->row && decor_virt_pos(&item.decor)) {
-      has_virttext = true;
+    if (item.start_row == state->row && decor_virt_pos(&item)) {
+      has_virt_pos = true;
     }
 
-    if (item.decor.hl_eol && item.start_row <= state->row) {
+    if (item.kind == kDecorKindHighlight
+        && (item.data.sh.flags & kSHHlEol) && item.start_row <= state->row) {
       *eol_attr = hl_combine_attr(*eol_attr, item.attr_id);
     }
   }
-  return has_virttext;
-}
-
-void decor_push_ephemeral(int start_row, int start_col, int end_row, int end_col, Decoration *decor,
-                          uint64_t ns_id, uint64_t mark_id)
-{
-  if (end_row == -1) {
-    end_row = start_row;
-    end_col = start_col;
-  }
-  decor_push(&decor_state, start_row, start_col, end_row, end_col, decor, true, ns_id, mark_id);
+  return has_virt_pos;
 }
 
 /// @param has_fold  whether line "lnum" has a fold, or kNone when not calculated yet
@@ -612,18 +897,22 @@ int decor_virt_lines(win_T *wp, linenr_T lnum, VirtLines *lines, TriState has_fo
     MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0 || mark.pos.row >= end_row) {
       break;
-    } else if (mt_end(mark)
-               || marktree_decor_level(mark) < kDecorLevelVirtLine
-               || !mark.decor_full) {
+    } else if (mt_end(mark) || !(mark.flags & MT_FLAG_DECOR_VIRT_LINES)) {
       goto next_mark;
     }
-    Decoration *const decor = mark.decor_full;
-    const int draw_row = mark.pos.row + (decor->virt_lines_above ? 0 : 1);
-    if (draw_row == row) {
-      virt_lines += (int)kv_size(decor->virt_lines);
-      if (lines) {
-        kv_splice(*lines, decor->virt_lines);
+    DecorVirtText *vt = mark.decor_data.ext.vt;
+    while (vt) {
+      if (vt->flags & kVTIsLines) {
+        bool above = vt->flags & kVTLinesAbove;
+        int draw_row = mark.pos.row + (above ? 0 : 1);
+        if (draw_row == row) {
+          virt_lines += (int)kv_size(vt->data.virt_lines);
+          if (lines) {
+            kv_splice(*lines, vt->data.virt_lines);
+          }
+        }
       }
+      vt = vt->next;
     }
 next_mark:
     marktree_itr_next(buf->b_marktree, itr);
@@ -631,3 +920,153 @@ next_mark:
 
   return virt_lines;
 }
+
+/// This assumes maximum one entry of each kind, which will not always be the case.
+void decor_to_dict_legacy(Dictionary *dict, DecorInline decor, bool hl_name)
+{
+  DecorSignHighlight sh_hl = DECOR_SIGN_HIGHLIGHT_INIT;
+  DecorSignHighlight sh_sign = DECOR_SIGN_HIGHLIGHT_INIT;
+  DecorVirtText *virt_text = NULL;
+  DecorVirtText *virt_lines = NULL;
+  int32_t priority = -1;  // sentinel value which cannot actually be set
+
+  if (decor.ext) {
+    DecorVirtText *vt = decor.data.ext.vt;
+    while (vt) {
+      if (vt->flags & kVTIsLines) {
+        virt_lines = vt;
+      } else {
+        virt_text = vt;
+      }
+      vt = vt->next;
+    }
+
+    uint32_t idx = decor.data.ext.sh_idx;
+    while (idx != DECOR_ID_INVALID) {
+      DecorSignHighlight *sh = &kv_A(decor_items, idx);
+      if (sh->flags & (kSHIsSign)) {
+        sh_sign = *sh;
+      } else {
+        sh_hl = *sh;
+      }
+      idx = sh->next;
+    }
+  } else {
+    sh_hl = decor_sh_from_inline(decor.data.hl, (String)STRING_INIT);
+  }
+
+  if (sh_hl.hl_id) {
+    PUT(*dict, "hl_group", hl_group_name(sh_hl.hl_id, hl_name));
+    PUT(*dict, "hl_eol", BOOLEAN_OBJ(sh_hl.flags & kSHHlEol));
+    if (sh_hl.flags & kSHConceal) {
+      String name;
+      if (sh_hl.flags & kSHConcealAlloc) {
+        name = cstr_to_string(sh_hl.text.ptr);
+      } else {
+        name = cbuf_to_string(sh_hl.text.data, strnlen(sh_hl.text.data, 8));
+      }
+      PUT(*dict, "conceal", STRING_OBJ(name));
+    }
+
+    if (sh_hl.flags & kSHSpellOn) {
+      PUT(*dict, "spell", BOOLEAN_OBJ(true));
+    } else if (sh_hl.flags & kSHSpellOff) {
+      PUT(*dict, "spell", BOOLEAN_OBJ(false));
+    }
+
+    priority = sh_hl.priority;
+  }
+
+  if (sh_hl.flags & kSHUIWatched) {
+    PUT(*dict, "ui_watched", BOOLEAN_OBJ(true));
+  }
+
+  if (virt_text) {
+    if (virt_text->hl_mode) {
+      PUT(*dict, "hl_mode", CSTR_TO_OBJ(hl_mode_str[virt_text->hl_mode]));
+    }
+
+    Array chunks = virt_text_to_array(virt_text->data.virt_text, hl_name);
+    PUT(*dict, "virt_text", ARRAY_OBJ(chunks));
+    PUT(*dict, "virt_text_hide", BOOLEAN_OBJ(virt_text->flags & kVTHide));
+    if (virt_text->pos == kVPosWinCol) {
+      PUT(*dict, "virt_text_win_col", INTEGER_OBJ(virt_text->col));
+    }
+    PUT(*dict, "virt_text_pos",
+        CSTR_TO_OBJ(virt_text_pos_str[virt_text->pos]));
+    priority = virt_text->priority;
+  }
+
+  if (virt_lines) {
+    Array all_chunks = ARRAY_DICT_INIT;
+    bool virt_lines_leftcol = false;
+    for (size_t i = 0; i < kv_size(virt_lines->data.virt_lines); i++) {
+      virt_lines_leftcol = kv_A(virt_lines->data.virt_lines, i).left_col;
+      Array chunks = virt_text_to_array(kv_A(virt_lines->data.virt_lines, i).line, hl_name);
+      ADD(all_chunks, ARRAY_OBJ(chunks));
+    }
+    PUT(*dict, "virt_lines", ARRAY_OBJ(all_chunks));
+    PUT(*dict, "virt_lines_above", BOOLEAN_OBJ(virt_lines->flags & kVTLinesAbove));
+    PUT(*dict, "virt_lines_leftcol", BOOLEAN_OBJ(virt_lines_leftcol));
+    priority = virt_lines->priority;
+  }
+
+  if (sh_sign.flags & kSHIsSign) {
+    if (sh_sign.text.ptr) {
+      PUT(*dict, "sign_text", CSTR_TO_OBJ(sh_sign.text.ptr));
+    }
+
+    // uncrustify:off
+
+    struct { char *name; const int val; } hls[] = {
+      { "sign_hl_group"      , sh_sign.hl_id            },
+      { "number_hl_group"    , sh_sign.number_hl_id     },
+      { "line_hl_group"      , sh_sign.line_hl_id       },
+      { "cursorline_hl_group", sh_sign.cursorline_hl_id },
+      { NULL, 0 },
+    };
+
+    // uncrustify:on
+
+    for (int j = 0; hls[j].name; j++) {
+      if (hls[j].val) {
+        PUT(*dict, hls[j].name, hl_group_name(hls[j].val, hl_name));
+      }
+    }
+    priority = sh_sign.priority;
+  }
+
+  if (priority != -1) {
+    PUT(*dict, "priority", INTEGER_OBJ(priority));
+  }
+}
+
+uint16_t decor_type_flags(DecorInline decor)
+{
+  if (decor.ext) {
+    uint16_t type_flags = kExtmarkNone;
+    DecorVirtText *vt = decor.data.ext.vt;
+    while (vt) {
+      type_flags |= (vt->flags & kVTIsLines) ? kExtmarkVirtLines : kExtmarkVirtText;
+      vt = vt->next;
+    }
+    uint32_t idx = decor.data.ext.sh_idx;
+    while (idx != DECOR_ID_INVALID) {
+      DecorSignHighlight *sh = &kv_A(decor_items, idx);
+      type_flags |= (sh->flags & kSHIsSign) ? kExtmarkSign : kExtmarkHighlight;
+      idx = sh->next;
+    }
+    return type_flags;
+  } else {
+    return (decor.data.hl.flags & kSHIsSign) ? kExtmarkSign : kExtmarkHighlight;
+  }
+}
+
+Object hl_group_name(int hl_id, bool hl_name)
+{
+  if (hl_name) {
+    return CSTR_TO_OBJ(syn_id2name(hl_id));
+  } else {
+    return INTEGER_OBJ(hl_id);
+  }
+}
diff --git a/src/nvim/decoration.h b/src/nvim/decoration.h
index dacdc7683a..d5fd83e9d4 100644
--- a/src/nvim/decoration.h
+++ b/src/nvim/decoration.h
@@ -6,91 +6,54 @@
 
 #include "klib/kvec.h"
 #include "nvim/buffer_defs.h"
+#include "nvim/decoration_defs.h"
 #include "nvim/extmark_defs.h"
 #include "nvim/macros.h"
 #include "nvim/marktree.h"
 #include "nvim/pos.h"
 #include "nvim/types.h"
 
-// actual Decoration data is in extmark_defs.h
-
-typedef uint16_t DecorPriority;
-#define DECOR_PRIORITY_BASE 0x1000
-
-typedef enum {
-  kVTEndOfLine,
-  kVTOverlay,
-  kVTWinCol,
-  kVTRightAlign,
-  kVTInline,
-} VirtTextPos;
+// actual Decor* data is in decoration_defs.h
 
 EXTERN const char *const virt_text_pos_str[] INIT( = { "eol", "overlay", "win_col", "right_align",
                                                        "inline" });
 
-typedef enum {
-  kHlModeUnknown,
-  kHlModeReplace,
-  kHlModeCombine,
-  kHlModeBlend,
-} HlMode;
-
 EXTERN const char *const hl_mode_str[] INIT( = { "", "replace", "combine", "blend" });
 
-#define VIRTTEXT_EMPTY ((VirtText)KV_INITIAL_VALUE)
-
-typedef kvec_t(struct virt_line { VirtText line; bool left_col; }) VirtLines;
-
-struct Decoration {
-  VirtText virt_text;
-  VirtLines virt_lines;
-
-  int hl_id;  // highlight group
-  VirtTextPos virt_text_pos;
-  HlMode hl_mode;
-
-  // TODO(bfredl): at some point turn this into FLAGS
-  bool virt_text_hide;
-  bool hl_eol;
-  bool virt_lines_above;
-  bool conceal;
-  TriState spell;
-  // TODO(bfredl): style, etc
-  DecorPriority priority;
-  int col;  // fixed col value, like win_col
-  int virt_text_width;  // width of virt_text
-  char *sign_text;
-  char *sign_name;
-  int sign_hl_id;
-  int sign_add_id;
-  int number_hl_id;
-  int line_hl_id;
-  int cursorline_hl_id;
-  // TODO(bfredl): in principle this should be a schar_T, but we
-  // probably want some kind of glyph cache for that..
-  int conceal_char;
-  bool ui_watched;  // watched for win_extmark
-};
-#define DECORATION_INIT { KV_INITIAL_VALUE, KV_INITIAL_VALUE, 0, kVTEndOfLine, \
-                          kHlModeUnknown, false, false, false, false, kNone, \
-                          DECOR_PRIORITY_BASE, 0, 0, NULL, NULL, 0, 0, 0, 0, 0, 0, false }
+typedef enum {
+  kDecorKindHighlight,
+  kDecorKindSign,
+  kDecorKindVirtText,
+  kDecorKindVirtLines,
+  kDecorKindUIWatched,
+} DecorRangeKind;
 
 typedef struct {
   int start_row;
   int start_col;
   int end_row;
   int end_col;
-  Decoration decor;
-  int attr_id;  // cached lookup of decor.hl_id
-  bool virt_text_owned;
+  // next pointers MUST NOT be used, these are separate ranges
+  // vt->next could be pointing to freelist memory at this point
+  union {
+    DecorSignHighlight sh;
+    DecorVirtText *vt;
+    struct {
+      uint32_t ns_id;
+      uint32_t mark_id;
+      VirtTextPos pos;
+    } ui;
+  } data;
+  int attr_id;  // cached lookup of inl.hl_id if it was a highlight
+  bool owned;  // ephemeral decoration, free memory immediately
+  DecorPriority priority;
+  DecorRangeKind kind;
   /// Screen column to draw the virtual text.
   /// When -1, the virtual text may be drawn after deciding where.
   /// When -3, the virtual text should be drawn on the next screen line.
   /// When -10, the virtual text has just been added.
   /// When INT_MIN, the virtual text should no longer be drawn.
   int draw_col;
-  uint64_t ns_id;
-  uint64_t mark_id;
 } DecorRange;
 
 typedef struct {
@@ -109,23 +72,11 @@ typedef struct {
 
   TriState spell;
 
-  // This is used to prevent removing/updating extmarks inside
-  // on_lines callbacks which is not allowed since it can lead to
-  // heap-use-after-free errors.
-  bool running_on_lines;
+  bool running_decor_provider;
 } DecorState;
 
 EXTERN DecorState decor_state INIT( = { 0 });
 
-static inline bool decor_has_sign(Decoration *decor)
-{
-  return decor->sign_text
-         || decor->sign_hl_id
-         || decor->number_hl_id
-         || decor->line_hl_id
-         || decor->cursorline_hl_id;
-}
-
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "decoration.h.generated.h"
 #endif
diff --git a/src/nvim/decoration_defs.h b/src/nvim/decoration_defs.h
new file mode 100644
index 0000000000..d73fd669b7
--- /dev/null
+++ b/src/nvim/decoration_defs.h
@@ -0,0 +1,129 @@
+#pragma once
+
+#include <stdint.h>
+
+#include "klib/kvec.h"
+
+#define DECOR_ID_INVALID UINT32_MAX
+
+typedef struct {
+  char *text;
+  int hl_id;
+} VirtTextChunk;
+
+typedef kvec_t(VirtTextChunk) VirtText;
+#define VIRTTEXT_EMPTY ((VirtText)KV_INITIAL_VALUE)
+
+typedef enum {
+  kVPosEndOfLine,
+  kVPosOverlay,
+  kVPosWinCol,
+  kVPosRightAlign,
+  kVPosInline,
+} VirtTextPos;
+
+typedef kvec_t(struct virt_line { VirtText line; bool left_col; }) VirtLines;
+
+typedef uint16_t DecorPriority;
+#define DECOR_PRIORITY_BASE 0x1000
+
+typedef enum {
+  kHlModeUnknown,
+  kHlModeReplace,
+  kHlModeCombine,
+  kHlModeBlend,
+} HlMode;
+
+enum {
+  kSHIsSign = 1,
+  kSHHlEol = 2,
+  kSHUIWatched = 4,
+  kSHUIWatchedOverlay = 8,
+  kSHSpellOn = 16,
+  kSHSpellOff = 32,
+  kSHConceal = 64,
+  kSHConcealAlloc = 128,
+};
+
+typedef struct {
+  uint16_t flags;
+  DecorPriority priority;
+  int hl_id;
+  char conceal_char[4];
+} DecorHighlightInline;
+
+#define DECOR_HIGHLIGHT_INLINE_INIT { 0, DECOR_PRIORITY_BASE, 0, { 0 } }
+typedef struct {
+  uint16_t flags;
+  DecorPriority priority;
+  int hl_id;  // if sign: highlight of sign text
+  // TODO(bfredl): Later this should be schar_T[2], but then it needs to handle
+  // invalidations of the cache
+  union {
+    // for now:
+    // 1. sign is always allocated (drawline.c expects a `char *` for a sign)
+    // 2. conceal char is allocated if larger than 8 bytes.
+    char *ptr;  // sign or conceal text
+    char data[8];
+  } text;
+  // NOTE: if more functionality is added to a Highlight these should be overloaded
+  // or restructured
+  char *sign_name;
+  int sign_add_id;
+  int number_hl_id;
+  int line_hl_id;
+  int cursorline_hl_id;
+  uint32_t next;
+} DecorSignHighlight;
+
+#define DECOR_SIGN_HIGHLIGHT_INIT { 0, DECOR_PRIORITY_BASE, 0, { .ptr = NULL }, NULL, 0, 0, 0, 0, \
+                                    DECOR_ID_INVALID }
+
+enum {
+  kVTIsLines = 1,
+  kVTHide = 2,
+  kVTLinesAbove = 4,
+};
+
+typedef struct DecorVirtText DecorVirtText;
+struct DecorVirtText {
+  uint8_t flags;
+  uint8_t hl_mode;
+  DecorPriority priority;
+  int width;  // width of virt_text
+  int col;
+  VirtTextPos pos;
+  // TODO(bfredl): reduce this to one datatype, later
+  union {
+    VirtText virt_text;
+    VirtLines virt_lines;
+  } data;
+  DecorVirtText *next;
+};
+#define DECOR_VIRT_TEXT_INIT { 0, kHlModeUnknown, DECOR_PRIORITY_BASE, 0, 0, kVPosEndOfLine, \
+                               { .virt_text = KV_INITIAL_VALUE }, NULL, }
+#define DECOR_VIRT_LINES_INIT { kVTIsLines, kHlModeUnknown, DECOR_PRIORITY_BASE, 0, 0, \
+                                kVPosEndOfLine, { .virt_lines = KV_INITIAL_VALUE }, NULL, }
+
+typedef struct {
+  uint32_t sh_idx;
+  DecorVirtText *vt;
+} DecorExt;
+
+// Stored inline in marktree, with MT_FLAG_DECOR_EXT in MTKey.flags
+typedef union {
+  DecorHighlightInline hl;
+  DecorExt ext;
+} DecorInlineData;
+
+// Not stored in the marktree, but used when passing around args
+//
+// Convention: an empty "no decoration" value should always be encoded
+// with ext=false and an unset DecorHighlightInline (no flags, no hl_id)
+typedef struct {
+  bool ext;
+  DecorInlineData data;
+} DecorInline;
+
+// initializes in a valid state for the DecorHighlightInline branch
+#define DECOR_INLINE_INIT { .ext = false, .data.hl = DECOR_HIGHLIGHT_INLINE_INIT }
diff --git a/src/nvim/decoration_provider.c b/src/nvim/decoration_provider.c
index 2a00e9f373..2c0be2fe8a 100644
--- a/src/nvim/decoration_provider.c
+++ b/src/nvim/decoration_provider.c
@@ -122,6 +122,9 @@ void decor_providers_invoke_win(win_T *wp, DecorProviders *providers,
                                 DecorProviders *line_providers)
 {
   kvi_init(*line_providers);
+  // this might change in the future
+  // then we would need decor_state.running_decor_provider just like "on_line" below
+  assert(kv_size(decor_state.active) == 0);
 
   linenr_T knownmax = MIN(wp->w_buffer->b_ml.ml_line_count,
                           ((wp->w_valid & VALID_BOTLINE)
@@ -153,7 +156,7 @@ void decor_providers_invoke_win(win_T *wp, DecorProviders *providers,
 /// @param[out] err       Provider error
 void decor_providers_invoke_line(win_T *wp, DecorProviders *providers, int row, bool *has_decor)
 {
-  decor_state.running_on_lines = true;
+  decor_state.running_decor_provider = true;
   for (size_t k = 0; k < kv_size(*providers); k++) {
     DecorProvider *p = kv_A(*providers, k);
     if (p && p->redraw_line != LUA_NOREF) {
@@ -171,7 +174,7 @@ void decor_providers_invoke_line(win_T *wp, DecorProviders *providers, int row,
       hl_check_ns();
     }
   }
-  decor_state.running_on_lines = false;
+  decor_state.running_decor_provider = false;
 }
 
 /// For each provider invoke the 'buf' callback for a given buffer.
@@ -207,6 +210,7 @@ void decor_providers_invoke_end(DecorProviders *providers)
       decor_provider_invoke(p, "end", p->redraw_end, args, true);
     }
   }
+  decor_check_to_be_deleted();
 }
 
 /// Mark all cached state of per-namespace highlights as invalid. Revalidate
diff --git a/src/nvim/drawline.c b/src/nvim/drawline.c
index c1d4e55fe5..6f34767907 100644
--- a/src/nvim/drawline.c
+++ b/src/nvim/drawline.c
@@ -265,18 +265,25 @@ static void draw_virt_text(win_T *wp, buf_T *buf, int col_off, int *end_col, int
   bool do_eol = state->eol_col > -1;
   for (size_t i = 0; i < kv_size(state->active); i++) {
     DecorRange *item = &kv_A(state->active, i);
-    if (!(item->start_row == state->row && decor_virt_pos(&item->decor))) {
+    if (!(item->start_row == state->row && decor_virt_pos(item))) {
       continue;
     }
-    if (item->draw_col == -1) {
+
+    DecorVirtText *vt = NULL;
+    if (item->kind == kDecorKindVirtText) {
+      assert(item->data.vt);
+      vt = item->data.vt;
+    }
+    if (decor_virt_pos(item) && item->draw_col == -1) {
       bool updated = true;
-      if (item->decor.virt_text_pos == kVTRightAlign) {
-        right_pos -= item->decor.virt_text_width;
+      VirtTextPos pos = decor_virt_pos_kind(item);
+      if (pos == kVPosRightAlign) {
+        right_pos -= vt->width;
         item->draw_col = right_pos;
-      } else if (item->decor.virt_text_pos == kVTEndOfLine && do_eol) {
+      } else if (pos == kVPosEndOfLine && do_eol) {
         item->draw_col = state->eol_col;
-      } else if (item->decor.virt_text_pos == kVTWinCol) {
-        item->draw_col = MAX(col_off + item->decor.col, 0);
+      } else if (pos == kVPosWinCol) {
+        item->draw_col = MAX(col_off + vt->col, 0);
       } else {
         updated = false;
       }
@@ -289,19 +296,19 @@ static void draw_virt_text(win_T *wp, buf_T *buf, int col_off, int *end_col, int
       continue;
     }
     int col = 0;
-    if (item->decor.ui_watched) {
+    if (item->kind == kDecorKindUIWatched) {
       // send mark position to UI
       col = item->draw_col;
-      WinExtmark m = { (NS)item->ns_id, item->mark_id, win_row, col };
+      WinExtmark m = { (NS)item->data.ui.ns_id, item->data.ui.mark_id, win_row, col };
       kv_push(win_extmark_arr, m);
     }
-    if (kv_size(item->decor.virt_text)) {
+    if (vt) {
       int vcol = item->draw_col - col_off;
-      col = draw_virt_text_item(buf, item->draw_col, item->decor.virt_text,
-                                item->decor.hl_mode, max_col, vcol);
+      col = draw_virt_text_item(buf, item->draw_col, vt->data.virt_text,
+                                vt->hl_mode, max_col, vcol);
     }
     item->draw_col = INT_MIN;  // deactivate
-    if (item->decor.virt_text_pos == kVTEndOfLine && do_eol) {
+    if (vt && vt->pos == kVPosEndOfLine && do_eol) {
       state->eol_col = col + 1;
     }
 
@@ -807,9 +814,9 @@ static bool has_more_inline_virt(winlinevars_T *wlv, ptrdiff_t v)
   for (size_t i = 0; i < kv_size(state->active); i++) {
     DecorRange *item = &kv_A(state->active, i);
     if (item->start_row != state->row
-        || !kv_size(item->decor.virt_text)
-        || item->decor.virt_text_pos != kVTInline
-        || item->decor.virt_text_width == 0) {
+        || item->kind != kDecorKindVirtText
+        || item->data.vt->pos != kVPosInline
+        || item->data.vt->width == 0) {
       continue;
     }
     if (item->draw_col >= -1 && item->start_col >= v) {
@@ -830,14 +837,14 @@ static void handle_inline_virtual_text(win_T *wp, winlinevars_T *wlv, ptrdiff_t
       for (size_t i = 0; i < kv_size(state->active); i++) {
         DecorRange *item = &kv_A(state->active, i);
         if (item->start_row != state->row
-            || !kv_size(item->decor.virt_text)
-            || item->decor.virt_text_pos != kVTInline
-            || item->decor.virt_text_width == 0) {
+            || item->kind != kDecorKindVirtText
+            || item->data.vt->pos != kVPosInline
+            || item->data.vt->width == 0) {
           continue;
         }
         if (item->draw_col >= -1 && item->start_col == v) {
-          wlv->virt_inline = item->decor.virt_text;
-          wlv->virt_inline_hl_mode = item->decor.hl_mode;
+          wlv->virt_inline = item->data.vt->data.virt_text;
+          wlv->virt_inline_hl_mode = item->data.vt->hl_mode;
           item->draw_col = INT_MIN;
           break;
         }
diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c
index 3481f44064..08a1539bfc 100644
--- a/src/nvim/extmark.c
+++ b/src/nvim/extmark.c
@@ -50,67 +50,35 @@
 ///
 /// must not be used during iteration!
 void extmark_set(buf_T *buf, uint32_t ns_id, uint32_t *idp, int row, colnr_T col, int end_row,
-                 colnr_T end_col, Decoration *decor, bool right_gravity, bool end_right_gravity,
-                 bool no_undo, bool invalidate, Error *err)
+                 colnr_T end_col, DecorInline decor, uint16_t decor_flags, bool right_gravity,
+                 bool end_right_gravity, bool no_undo, bool invalidate, Error *err)
 {
   uint32_t *ns = map_put_ref(uint32_t, uint32_t)(buf->b_extmark_ns, ns_id, NULL, NULL);
   uint32_t id = idp ? *idp : 0;
-  bool decor_full = false;
-  bool hl_eol = false;
-
-  uint8_t decor_level = kDecorLevelNone;  // no decor
-  if (decor) {
-    if (kv_size(decor->virt_text)
-        || kv_size(decor->virt_lines)
-        || decor->conceal
-        || decor_has_sign(decor)
-        || decor->ui_watched
-        || decor->spell != kNone) {
-      decor_full = true;
-      decor = xmemdup(decor, sizeof *decor);
-    }
-    decor_level = kDecorLevelVisible;  // decor affects redraw
-    hl_eol = decor->hl_eol;
-    if (kv_size(decor->virt_lines)) {
-      decor_level = kDecorLevelVirtLine;  // decor affects horizontal size
-    }
-  }
-  uint16_t flags = mt_flags(right_gravity, hl_eol, no_undo, invalidate, decor_level);
 
+  uint16_t flags = mt_flags(right_gravity, no_undo, invalidate, decor.ext) | decor_flags;
   if (id == 0) {
     id = ++*ns;
   } else {
     MarkTreeIter itr[1] = { 0 };
     MTKey old_mark = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, itr);
     if (old_mark.id) {
-      if (decor_state.running_on_lines) {
-        if (err) {
-          api_set_error(err, kErrorTypeException,
-                        "Cannot change extmarks during on_line callbacks");
-        }
-        goto error;
-      }
       if (mt_paired(old_mark) || end_row > -1) {
         extmark_del_id(buf, ns_id, id);
       } else {
-        // TODO(bfredl): we need to do more if "revising" a decoration mark.
         assert(marktree_itr_valid(itr));
         if (old_mark.pos.row == row && old_mark.pos.col == col) {
-          if (marktree_decor_level(old_mark) > kDecorLevelNone) {
-            decor_remove(buf, row, row, old_mark.decor_full, false);
-            old_mark.decor_full = NULL;
+          if (mt_decor_any(old_mark)) {
+            buf_decor_remove(buf, row, row, mt_decor(old_mark), true);
           }
-          old_mark.flags = flags;
-          if (decor_full) {
-            old_mark.decor_full = decor;
-          } else if (decor) {
-            old_mark.hl_id = decor->hl_id;
-            old_mark.priority = decor->priority;
-          }
-          marktree_revise(buf->b_marktree, itr, decor_level, old_mark);
+
+          // not paired: we can revise in place
+          mt_itr_rawkey(itr).flags &= (uint16_t) ~MT_FLAG_EXTERNAL_MASK;
+          mt_itr_rawkey(itr).flags |= flags;
+          mt_itr_rawkey(itr).decor_data = decor.data;
           goto revised;
         }
-        decor_remove(buf, old_mark.pos.row, old_mark.pos.row, old_mark.decor_full, false);
+        buf_decor_remove(buf, old_mark.pos.row, old_mark.pos.row, mt_decor(old_mark), true);
         marktree_del_itr(buf->b_marktree, itr, false);
       }
     } else {
@@ -118,29 +86,19 @@ void extmark_set(buf_T *buf, uint32_t ns_id, uint32_t *idp, int row, colnr_T col
     }
   }
 
-  MTKey mark = { { row, col }, ns_id, id, 0, flags, 0, NULL };
-  if (decor_full) {
-    mark.decor_full = decor;
-  } else if (decor) {
-    mark.hl_id = decor->hl_id;
-    mark.priority = decor->priority;
-  }
+  MTKey mark = { { row, col }, ns_id, id, flags, decor.data };
 
   marktree_put(buf->b_marktree, mark, end_row, end_col, end_right_gravity);
 
 revised:
-  decor_add(buf, row, end_row, decor, decor && decor->hl_id);
+  if (decor_flags || decor.ext) {
+    buf_put_decor(buf, decor, row);
+    decor_redraw(buf, row, end_row > -1 ? end_row : row, decor);
+  }
 
   if (idp) {
     *idp = id;
   }
-
-  return;
-
-error:
-  if (decor_full) {
-    decor_free(decor);
-  }
 }
 
 static bool extmark_setraw(buf_T *buf, uint64_t mark, int row, colnr_T col)
@@ -189,8 +147,8 @@ void extmark_del(buf_T *buf, MarkTreeIter *itr, MTKey key, bool restore)
     }
   }
 
-  if (marktree_decor_level(key) > kDecorLevelNone) {
-    decor_remove(buf, key.pos.row, key2.pos.row, key.decor_full, false);
+  if (mt_decor_any(key)) {
+    buf_decor_remove(buf, key.pos.row, key2.pos.row, mt_decor(key), true);
   }
 
   // TODO(bfredl): delete it from current undo header, opportunistically?
@@ -231,7 +189,6 @@ bool extmark_clear(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_r
       marktree_itr_next(buf->b_marktree, itr);
     }
   }
-
   return marks_cleared;
 }
 
@@ -294,24 +251,11 @@ static void push_mark(ExtmarkInfoArray *array, uint32_t ns_id, ExtmarkType type_
   if (!(ns_id == UINT32_MAX || mark.start.ns == ns_id)) {
     return;
   }
-  uint16_t type_flags = kExtmarkNone;
   if (type_filter != kExtmarkNone) {
-    Decoration *decor = mark.start.decor_full;
-    if (decor && (decor->sign_text || decor->number_hl_id)) {
-      type_flags |= (kExtmarkSignHL|kExtmarkSign);
-    }
-    if (decor && (decor->line_hl_id || decor->cursorline_hl_id)) {
-      type_flags |= (kExtmarkSignHL|kExtmarkHighlight);
-    }
-    if (decor && decor->virt_text.size) {
-      type_flags |= kExtmarkVirtText;
-    }
-    if (decor && decor->virt_lines.size) {
-      type_flags |= kExtmarkVirtLines;
-    }
-    if (mark.start.hl_id) {
-      type_flags |= kExtmarkHighlight;
+    if (!mt_decor_any(mark.start)) {
+      return;
     }
+    uint16_t type_flags = decor_type_flags(mt_decor(mark.start));
 
     if (!(type_flags & type_filter)) {
       return;
@@ -349,9 +293,9 @@ void extmark_free_all(buf_T *buf)
       break;
     }
 
-    // don't free mark.decor_full twice for a paired mark.
+    // don't free mark.decor twice for a paired mark.
     if (!(mt_paired(mark) && mt_end(mark))) {
-      decor_free(mark.decor_full);
+      decor_free(mt_decor(mark));
     }
 
     marktree_itr_next(buf->b_marktree, itr);
@@ -398,9 +342,8 @@ void extmark_splice_delete(buf_T *buf, int l_row, colnr_T l_col, int u_row, coln
           continue;
         } else {
           invalidated = true;
-          mark.flags |= MT_FLAG_INVALID;
-          marktree_revise(curbuf->b_marktree, itr, marktree_decor_level(mark), mark);
-          decor_remove(buf, mark.pos.row, endpos.row, mark.decor_full, true);
+          mt_itr_rawkey(itr).flags |= MT_FLAG_INVALID;
+          buf_decor_remove(buf, mark.pos.row, endpos.row, mt_decor(mark), false);
         }
       }
     }
@@ -451,10 +394,8 @@ void extmark_apply_undo(ExtmarkUndoObject undo_info, bool undo)
       if (pos.invalidated) {
         MarkTreeIter itr[1] = { 0 };
         MTKey mark = marktree_lookup(curbuf->b_marktree, pos.mark, itr);
-        MTKey end = marktree_get_alt(curbuf->b_marktree, mark, NULL);
-        mark.flags &= (uint16_t) ~MT_FLAG_INVALID;
-        marktree_revise(curbuf->b_marktree, itr, marktree_decor_level(mark), mark);
-        decor_add(curbuf, mark.pos.row, end.pos.row, mark.decor_full, mark.hl_id);
+        mt_itr_rawkey(itr).flags &= (uint16_t) ~MT_FLAG_INVALID;
+        buf_put_decor(curbuf, mt_decor(mark), mark.pos.row);
       }
       if (pos.old_row >= 0) {
         extmark_setraw(curbuf, pos.mark, pos.old_row, pos.old_col);
diff --git a/src/nvim/extmark.h b/src/nvim/extmark.h
index 9d0795c947..1288714462 100644
--- a/src/nvim/extmark.h
+++ b/src/nvim/extmark.h
@@ -64,6 +64,8 @@ typedef enum {
   kExtmarkClear,
 } UndoObjectType;
 
+// TODO(bfredl): if possible unify these with marktree flags,
+// so it is possible to filter extmarks directly on top-level flags
 typedef enum {
   kExtmarkNone = 0x1,
   kExtmarkSign = 0x2,
diff --git a/src/nvim/extmark_defs.h b/src/nvim/extmark_defs.h
index 6615551df4..d1bc13f9f2 100644
--- a/src/nvim/extmark_defs.h
+++ b/src/nvim/extmark_defs.h
@@ -3,13 +3,6 @@
 #include "klib/kvec.h"
 #include "nvim/types.h"
 
-typedef struct {
-  char *text;
-  int hl_id;
-} VirtTextChunk;
-
-typedef kvec_t(VirtTextChunk) VirtText;
-
 typedef struct undo_object ExtmarkUndoObject;
 typedef kvec_t(ExtmarkUndoObject) extmark_undo_vec_t;
 
@@ -21,9 +14,3 @@ typedef enum {
   kExtmarkNoUndo,      // Operation should not be reversible
   kExtmarkUndoNoRedo,  // Operation should be undoable, but not redoable
 } ExtmarkOp;
-
-typedef enum {
-  kDecorLevelNone = 0,
-  kDecorLevelVisible = 1,
-  kDecorLevelVirtLine = 2,
-} DecorLevel;
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index f350001977..110683a35c 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -287,7 +287,7 @@ static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k)
 
 void marktree_put(MarkTree *b, MTKey key, int end_row, int end_col, bool end_right)
 {
-  assert(!(key.flags & ~MT_FLAG_EXTERNAL_MASK));
+  assert(!(key.flags & ~(MT_FLAG_EXTERNAL_MASK | MT_FLAG_RIGHT_GRAVITY)));
   if (end_row >= 0) {
     key.flags |= MT_FLAG_PAIRED;
   }
@@ -1137,25 +1137,6 @@ static void marktree_free_node(MarkTree *b, MTNode *x)
   b->n_nodes--;
 }
 
-/// NB: caller must check not pair!
-void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, MTKey key)
-{
-  // TODO(bfredl): clean up this mess and re-instantiate &= and |= forms
-  // once we upgrade to a non-broken version of gcc in functionaltest-lua CI
-  rawkey(itr).flags = (uint16_t)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_DECOR_MASK);
-  rawkey(itr).flags = (uint16_t)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_INVALID);
-  rawkey(itr).flags = (uint16_t)(rawkey(itr).flags
-                                 | (uint16_t)(decor_level << MT_FLAG_DECOR_OFFSET)
-                                 | (uint16_t)(key.flags & MT_FLAG_DECOR_MASK)
-                                 | (uint16_t)(key.flags & MT_FLAG_HL_EOL)
-                                 | (uint16_t)(key.flags & MT_FLAG_NO_UNDO)
-                                 | (uint16_t)(key.flags & MT_FLAG_INVALID)
-                                 | (uint16_t)(key.flags & MT_FLAG_INVALIDATE));
-  rawkey(itr).decor_full = key.decor_full;
-  rawkey(itr).hl_id = key.hl_id;
-  rawkey(itr).priority = key.priority;
-}
-
 /// @param itr iterator is invalid after call
 void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col)
 {
@@ -2003,8 +1984,8 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
 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)
 {
-  uint16_t flags = mt_flags(right_gravity, false, false, false, 0);
-  MTKey key = { { row, col }, ns, id, 0, flags, 0, NULL };
+  uint16_t flags = mt_flags(right_gravity, false, false, false);
+  MTKey key = { { row, col }, ns, id, flags, { .hl = DECOR_HIGHLIGHT_INLINE_INIT } };
   marktree_put(b, key, end_row, end_col, end_right);
 }
 
diff --git a/src/nvim/marktree.h b/src/nvim/marktree.h
index 6d014b5742..c692cd8863 100644
--- a/src/nvim/marktree.h
+++ b/src/nvim/marktree.h
@@ -7,6 +7,7 @@
 
 #include "klib/kvec.h"
 #include "nvim/assert.h"
+#include "nvim/decoration_defs.h"
 #include "nvim/garray.h"
 #include "nvim/map.h"
 #include "nvim/pos.h"
@@ -47,6 +48,8 @@ typedef struct {
 } MarkTreeIter;
 
 #define marktree_itr_valid(itr) ((itr)->x != NULL)
+// accces 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
 //
@@ -56,10 +59,8 @@ typedef struct {
   MTPos pos;
   uint32_t ns;
   uint32_t id;
-  int32_t hl_id;
   uint16_t flags;
-  uint16_t priority;
-  Decoration *decor_full;
+  DecorInlineData decor_data;  // "ext" tag in flags
 } MTKey;
 
 typedef struct {
@@ -68,28 +69,40 @@ typedef struct {
   bool end_right_gravity;
 } MTPair;
 
-#define MT_INVALID_KEY (MTKey) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
+#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)
 // 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 MT_FLAG_NO_UNDO (((uint16_t)1) << 5)
-#define MT_FLAG_INVALIDATE (((uint16_t)1) << 6)
-#define MT_FLAG_INVALID (((uint16_t)1) << 7)
-
-#define DECOR_LEVELS 4
-#define MT_FLAG_DECOR_OFFSET 8
-#define MT_FLAG_DECOR_MASK (((uint16_t)(DECOR_LEVELS - 1)) << MT_FLAG_DECOR_OFFSET)
+#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 \
-                               | MT_FLAG_NO_UNDO | MT_FLAG_INVALIDATE | MT_FLAG_INVALID)
+#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 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)
@@ -143,20 +156,22 @@ static inline bool mt_invalid(MTKey key)
   return key.flags & MT_FLAG_INVALID;
 }
 
-static inline uint8_t marktree_decor_level(MTKey key)
+static inline bool mt_decor_any(MTKey key)
+{
+  return key.flags & MT_FLAG_DECOR_MASK;
+}
+
+static inline bool mt_decor_sign(MTKey key)
 {
-  return (uint8_t)((key.flags&MT_FLAG_DECOR_MASK) >> MT_FLAG_DECOR_OFFSET);
+  return key.flags & (MT_FLAG_DECOR_SIGNTEXT | MT_FLAG_DECOR_SIGNHL);
 }
 
-static inline uint16_t mt_flags(bool right_gravity, bool hl_eol, bool no_undo, bool invalidate,
-                                uint8_t decor_level)
+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)
-                    | (hl_eol ? MT_FLAG_HL_EOL : 0)
                     | (no_undo ? MT_FLAG_NO_UNDO : 0)
                     | (invalidate ? MT_FLAG_INVALIDATE : 0)
-                    | (decor_level << MT_FLAG_DECOR_OFFSET));
+                    | (decor_ext ? MT_FLAG_DECOR_EXT : 0));
 }
 
 static inline MTPair mtpair_from(MTKey start, MTKey end)
@@ -164,6 +179,11 @@ 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 {
@@ -186,8 +206,6 @@ static inline uint64_t mt_dbg_id(uint64_t id)
 typedef struct {
   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;
 
diff --git a/src/nvim/plines.c b/src/nvim/plines.c
index b51d262cd9..acbb9637a4 100644
--- a/src/nvim/plines.c
+++ b/src/nvim/plines.c
@@ -222,21 +222,25 @@ int win_lbr_chartabsize(chartabsize_T *cts, int *headp)
       if (mark.pos.row != cts->cts_row || mark.pos.col > col) {
         break;
       } else if (mark.pos.col == col) {
-        if (!mt_end(mark)) {
-          Decoration decor = get_decor(mark);
-          if (decor.virt_text_pos == kVTInline) {
-            if (mt_right(mark)) {
-              cts->cts_cur_text_width_right += decor.virt_text_width;
-            } else {
-              cts->cts_cur_text_width_left += decor.virt_text_width;
-            }
-            size += decor.virt_text_width;
-            if (*s == TAB) {
-              // tab size changes because of the inserted text
-              size -= tab_size;
-              tab_size = win_chartabsize(wp, s, vcol + size);
-              size += tab_size;
+        if (!mt_end(mark) && mark.flags & (MT_FLAG_DECOR_VIRT_TEXT_INLINE)) {
+          DecorInline decor = mt_decor(mark);
+          DecorVirtText *vt = decor.ext ? decor.data.ext.vt : NULL;
+          while (vt) {
+            if (!(vt->flags & kVTIsLines) && vt->pos == kVPosInline) {
+              if (mt_right(mark)) {
+                cts->cts_cur_text_width_right += vt->width;
+              } else {
+                cts->cts_cur_text_width_left += vt->width;
+              }
+              size += vt->width;
+              if (*s == TAB) {
+                // tab size changes because of the inserted text
+                size -= tab_size;
+                tab_size = win_chartabsize(wp, s, vcol + size);
+                size += tab_size;
+              }
             }
+            vt = vt->next;
           }
         }
       }
diff --git a/src/nvim/sign.c b/src/nvim/sign.c
index 0136937ad2..9a48b1b1a5 100644
--- a/src/nvim/sign.c
+++ b/src/nvim/sign.c
@@ -71,9 +71,9 @@ static int64_t group_get_ns(const char *group)
   return ns ? ns : -1;
 }
 
-static const char *sign_get_name(MTKey mark)
+static const char *sign_get_name(DecorSignHighlight *sh)
 {
-  char *name = mark.decor_full->sign_name;
+  char *name = sh->sign_name;
   return !name ? "" : map_has(cstr_t, &sign_map, name) ? name : "[Deleted]";
 }
 
@@ -92,15 +92,24 @@ static void buf_set_sign(buf_T *buf, uint32_t *id, char *group, int prio, linenr
   }
 
   uint32_t ns = group ? (uint32_t)nvim_create_namespace(cstr_as_string(group)) : 0;
-  Decoration decor = DECORATION_INIT;
-  decor.sign_text = sp->sn_text ? xstrdup(sp->sn_text) : NULL;
-  decor.sign_name = xstrdup(sp->sn_name);
-  decor.sign_hl_id = sp->sn_text_hl;
-  decor.line_hl_id = sp->sn_line_hl;
-  decor.number_hl_id = sp->sn_num_hl;
-  decor.cursorline_hl_id = sp->sn_cul_hl;
-  decor.priority = (DecorPriority)prio;
-  extmark_set(buf, ns, id, lnum - 1, 0, -1, -1, &decor, true, false, true, true, NULL);
+  DecorSignHighlight sign = DECOR_SIGN_HIGHLIGHT_INIT;
+
+  sign.flags |= kSHIsSign;
+  sign.text.ptr = sp->sn_text ? xstrdup(sp->sn_text) : NULL;
+  sign.sign_name = xstrdup(sp->sn_name);
+  sign.hl_id = sp->sn_text_hl;
+  sign.line_hl_id = sp->sn_line_hl;
+  sign.number_hl_id = sp->sn_num_hl;
+  sign.cursorline_hl_id = sp->sn_cul_hl;
+  sign.priority = (DecorPriority)prio;
+
+  bool has_hl = (sp->sn_line_hl || sp->sn_num_hl || sp->sn_cul_hl);
+  uint16_t decor_flags = (sp->sn_text ? MT_FLAG_DECOR_SIGNTEXT : 0)
+                         | (has_hl ? MT_FLAG_DECOR_SIGNHL : 0);
+
+  DecorInline decor = { .ext = true, .data.ext = { .vt = NULL, .sh_idx = decor_put_sh(sign) } };
+  extmark_set(buf, ns, id, lnum - 1, 0, -1, -1, decor, decor_flags, true,
+              false, true, true, NULL);
 }
 
 /// For an existing, placed sign with "id", modify the sign, group or priority.
@@ -148,9 +157,18 @@ int sign_cmp(const void *p1, const void *p2)
   const MTKey *s2 = (MTKey *)p2;
   int n = s1->pos.row - s2->pos.row;
 
-  return n ? n : (n = s2->decor_full->priority - s1->decor_full->priority)
-         ? n : (n = (int)(s2->id - s1->id))
-         ? n : (s2->decor_full->sign_add_id - s1->decor_full->sign_add_id);
+  if (n) {
+    return n;
+  }
+
+  DecorSignHighlight *sh1 = decor_find_sign(mt_decor(*s1));
+  DecorSignHighlight *sh2 = decor_find_sign(mt_decor(*s2));
+  assert(sh1 && sh2);
+
+  n = sh2->priority - sh1->priority;
+
+  return n ? n : (n = (int)(s2->id - s1->id))
+         ? n : (sh2->sign_add_id - sh1->sign_add_id);
 }
 
 /// Delete the specified signs
@@ -177,8 +195,7 @@ static int buf_delete_signs(buf_T *buf, char *group, int id, linenr_T atlnum)
 
     MTPair pair;
     while (marktree_itr_step_overlap(buf->b_marktree, itr, &pair)) {
-      if ((ns == UINT32_MAX || ns == pair.start.ns)
-          && pair.start.decor_full && decor_has_sign(pair.start.decor_full)) {
+      if ((ns == UINT32_MAX || ns == pair.start.ns) && mt_decor_sign(pair.start)) {
         kv_push(signs, pair.start);
       }
     }
@@ -191,7 +208,7 @@ static int buf_delete_signs(buf_T *buf, char *group, int id, linenr_T atlnum)
     if (row && mark.pos.row > row) {
       break;
     }
-    if (!mt_end(mark) && mark.decor_full && decor_has_sign(mark.decor_full)
+    if (!mt_end(mark) && mt_decor_sign(mark)
         && (id == 0 || (int)mark.id == id)
         && (ns == UINT32_MAX || ns == mark.ns)) {
       if (atlnum > 0) {
@@ -248,7 +265,7 @@ static void sign_list_placed(buf_T *rbuf, char *group)
 
       while (itr->x) {
         MTKey mark = marktree_itr_current(itr);
-        if (!mt_end(mark) && mark.decor_full && decor_has_sign(mark.decor_full)
+        if (!mt_end(mark) && mt_decor_sign(mark)
             && (ns == UINT32_MAX || ns == mark.ns)) {
           kv_push(signs, mark);
         }
@@ -262,14 +279,16 @@ static void sign_list_placed(buf_T *rbuf, char *group)
           namebuf[0] = '\0';
           groupbuf[0] = '\0';
           MTKey mark = kv_A(signs, i);
-          if (mark.decor_full->sign_name != NULL) {
-            vim_snprintf(namebuf, MSG_BUF_LEN, _("  name=%s"), sign_get_name(mark));
+
+          DecorSignHighlight *sh = decor_find_sign(mt_decor(mark));
+          if (sh->sign_name != NULL) {
+            vim_snprintf(namebuf, MSG_BUF_LEN, _("  name=%s"), sign_get_name(sh));
           }
           if (mark.ns != 0) {
             vim_snprintf(groupbuf, MSG_BUF_LEN, _("  group=%s"), describe_ns((int)mark.ns, ""));
           }
           vim_snprintf(lbuf, MSG_BUF_LEN, _("    line=%" PRIdLINENR "  id=%u%s%s  priority=%d"),
-                       mark.pos.row + 1, mark.id, groupbuf, namebuf, mark.decor_full->priority);
+                       mark.pos.row + 1, mark.id, groupbuf, namebuf, sh->priority);
           msg_puts(lbuf);
           msg_putchar('\n');
         }
@@ -841,21 +860,12 @@ void ex_sign(exarg_T *eap)
   }
 }
 
-/// Append dictionary of information for a defined sign "sp", or placed
-/// sign "mark" to "retlist". Either "sp", or "mark" is NULL.
-static void sign_list_append_info(sign_T *sp, MTKey *mark, list_T *retlist)
+/// Get dictionary of information for a defined sign "sp"
+static dict_T *sign_get_info_dict(sign_T *sp)
 {
   dict_T *d = tv_dict_alloc();
-  tv_list_append_dict(retlist, d);
 
-  tv_dict_add_str(d, S_LEN("name"), sp ? sp->sn_name : sign_get_name(*mark));
-  if (mark != NULL) {
-    tv_dict_add_nr(d,  S_LEN("id"), (int)mark->id);
-    tv_dict_add_str(d, S_LEN("group"), describe_ns((int)mark->ns, ""));
-    tv_dict_add_nr(d,  S_LEN("lnum"), mark->pos.row + 1);
-    tv_dict_add_nr(d,  S_LEN("priority"), mark->decor_full->priority);
-    return;
-  }
+  tv_dict_add_str(d, S_LEN("name"), sp->sn_name);
 
   if (sp->sn_icon != NULL) {
     tv_dict_add_str(d, S_LEN("icon"), sp->sn_icon);
@@ -871,6 +881,22 @@ static void sign_list_append_info(sign_T *sp, MTKey *mark, list_T *retlist)
       tv_dict_add_str(d, arg[i], strlen(arg[i]), p ? p : "NONE");
     }
   }
+  return d;
+}
+
+/// Get dictionary of information for placed sign "mark"
+static dict_T *sign_get_placed_info_dict(MTKey mark)
+{
+  dict_T *d = tv_dict_alloc();
+
+  DecorSignHighlight *sh = decor_find_sign(mt_decor(mark));
+
+  tv_dict_add_str(d, S_LEN("name"), sign_get_name(sh));
+  tv_dict_add_nr(d,  S_LEN("id"), (int)mark.id);
+  tv_dict_add_str(d, S_LEN("group"), describe_ns((int)mark.ns, ""));
+  tv_dict_add_nr(d,  S_LEN("lnum"), mark.pos.row + 1);
+  tv_dict_add_nr(d,  S_LEN("priority"), sh->priority);
+  return d;
 }
 
 /// Returns information about signs placed in a buffer as list of dicts.
@@ -883,8 +909,8 @@ list_T *get_buffer_signs(buf_T *buf)
 
   while (itr->x) {
     MTKey mark = marktree_itr_current(itr);
-    if (!mt_end(mark) && mark.decor_full && decor_has_sign(mark.decor_full)) {
-      sign_list_append_info(NULL, &mark, l);
+    if (!mt_end(mark) && mt_decor_sign(mark)) {
+      tv_list_append_dict(l, sign_get_placed_info_dict(mark));
     }
     marktree_itr_next(buf->b_marktree, itr);
   }
@@ -918,13 +944,15 @@ static void sign_get_placed_in_buf(buf_T *buf, linenr_T lnum, int sign_id, const
     if (lnum && mark.pos.row >= lnum) {
       break;
     }
-    if (!mt_end(mark) && mark.decor_full && decor_has_sign(mark.decor_full)
+    if (!mt_end(mark)
         && (ns == UINT32_MAX || ns == mark.ns)
         && ((lnum == 0 && sign_id == 0)
             || (sign_id == 0 && lnum == mark.pos.row + 1)
             || (lnum == 0 && sign_id == (int)mark.id)
             || (lnum == mark.pos.row + 1 && sign_id == (int)mark.id))) {
-      kv_push(signs, mark);
+      if (mt_decor_sign(mark)) {
+        kv_push(signs, mark);
+      }
     }
     marktree_itr_next(buf->b_marktree, itr);
   }
@@ -932,7 +960,7 @@ static void sign_get_placed_in_buf(buf_T *buf, linenr_T lnum, int sign_id, const
   if (kv_size(signs)) {
     qsort((void *)&kv_A(signs, 0), kv_size(signs), sizeof(MTKey), sign_cmp);
     for (size_t i = 0; i < kv_size(signs); i++) {
-      sign_list_append_info(NULL, &kv_A(signs, i), l);
+      tv_list_append_dict(l, sign_get_placed_info_dict(kv_A(signs, i)));
     }
     kv_destroy(signs);
   }
@@ -1222,18 +1250,17 @@ void f_sign_define(typval_T *argvars, typval_T *rettv, EvalFuncData fptr)
 /// "sign_getdefined()" function
 void f_sign_getdefined(typval_T *argvars, typval_T *rettv, EvalFuncData fptr)
 {
-  sign_T *sp;
-
   tv_list_alloc_ret(rettv, 0);
 
   if (argvars[0].v_type == VAR_UNKNOWN) {
+    sign_T *sp;
     map_foreach_value(&sign_map, sp, {
-      sign_list_append_info(sp, NULL, rettv->vval.v_list);
+      tv_list_append_dict(rettv->vval.v_list, sign_get_info_dict(sp));
     });
   } else {
-    sp = pmap_get(cstr_t)(&sign_map, tv_get_string(&argvars[0]));
+    sign_T *sp = pmap_get(cstr_t)(&sign_map, tv_get_string(&argvars[0]));
     if (sp != NULL) {
-      sign_list_append_info(sp, NULL, rettv->vval.v_list);
+      tv_list_append_dict(rettv->vval.v_list, sign_get_info_dict(sp));
     }
   }
 }
diff --git a/src/nvim/types.h b/src/nvim/types.h
index 0e5f8e6504..623efe0c8d 100644
--- a/src/nvim/types.h
+++ b/src/nvim/types.h
@@ -43,6 +43,4 @@ typedef enum {
 
 #define TRISTATE_FROM_INT(val) ((val) == 0 ? kFalse : ((val) >= 1 ? kTrue : kNone))
 
-typedef struct Decoration Decoration;
-
 typedef int64_t OptInt;
diff --git a/test/functional/api/extmark_spec.lua b/test/functional/api/extmark_spec.lua
index 6e00be611d..2115c7c244 100644
--- a/test/functional/api/extmark_spec.lua
+++ b/test/functional/api/extmark_spec.lua
@@ -1579,6 +1579,7 @@ describe('API/extmarks', function()
     eq({0, 0, {
       ns_id = 1,
       cursorline_hl_group = "Statement",
+      priority = 4096,
       right_gravity = true,
     } }, get_extmark_by_id(ns, marks[3], { details = true }))
   end)
diff --git a/test/functional/ui/bufhl_spec.lua b/test/functional/ui/bufhl_spec.lua
index 5263fb4c24..81e514c9aa 100644
--- a/test/functional/ui/bufhl_spec.lua
+++ b/test/functional/ui/bufhl_spec.lua
@@ -762,8 +762,6 @@ describe('Buffer highlighting', function()
       local s1 = {{'Köttbullar', 'Comment'}, {'Kräuterbutter'}}
       local s2 = {{'こんにちは', 'Comment'}}
 
-      -- TODO: only a virtual text from the same ns currently overrides
-      -- an existing virtual text. We might add a prioritation system.
       set_virtual_text(id1, 0, s1, {})
       eq({{1, 0, 0, {
         ns_id = 1,
@@ -775,7 +773,6 @@ describe('Buffer highlighting', function()
         virt_text_hide = false,
       }}}, get_extmarks(id1, {0,0}, {0, -1}, {details=true}))
 
-      -- TODO: is this really valid? shouldn't the max be line_count()-1?
       local lastline = line_count()
       set_virtual_text(id1, line_count(), s2, {})
       eq({{3, lastline, 0, {
diff --git a/test/functional/ui/decorations_spec.lua b/test/functional/ui/decorations_spec.lua
index b3b3128fdd..59a41a6de6 100644
--- a/test/functional/ui/decorations_spec.lua
+++ b/test/functional/ui/decorations_spec.lua
@@ -663,7 +663,7 @@ describe('decorations providers', function()
     ]])
   end)
 
-  it('does not allow removing extmarks during on_line callbacks', function()
+  it('does allow removing extmarks during on_line callbacks', function()
     exec_lua([[
       eok = true
     ]])
@@ -676,7 +676,7 @@ describe('decorations providers', function()
       end
     ]])
     exec_lua([[
-      assert(eok == false)
+      assert(eok == true)
     ]])
   end)