Merge pull request #13243 from bfredl/intersection

feat(extmark): support highlighting and querying multiline ranges

13 files changed, 1660 insertions, 476 deletions

diff --git a/src/klib/kvec.h b/src/klib/kvec.h
index f6674a0adf..fd9096e1ad 100644
--- a/src/klib/kvec.h
+++ b/src/klib/kvec.h
@@ -207,6 +207,16 @@ static inline void *_memcpy_free(void *const restrict dest, void *const restrict
   /* 2^x initial array size. */ \
   kvi_resize(v, (v).capacity << 1)
 
+/// fit at least "len" more items
+#define kvi_ensure_more_space(v, len) \
+  do { \
+    if ((v).capacity < (v).size + len) { \
+      (v).capacity = (v).size + len; \
+      kv_roundup32((v).capacity); \
+      kvi_resize((v), (v).capacity); \
+    } \
+  } while (0)
+
 /// Get location where to store new element to a vector with preallocated array
 ///
 /// @param[in,out]  v  Vector to push to.
@@ -223,6 +233,19 @@ static inline void *_memcpy_free(void *const restrict dest, void *const restrict
 #define kvi_push(v, x) \
   (*kvi_pushp(v) = (x))
 
+/// Copy a vector to a preallocated vector
+///
+/// @param[out] v1 destination
+/// @param[in] v0 source (can be either vector or preallocated vector)
+#define kvi_copy(v1, v0) \
+    do { \
+      if ((v1).capacity < (v0).size) { \
+        kvi_resize(v1, (v0).size); \
+      } \
+      (v1).size = (v0).size; \
+      memcpy((v1).items, (v0).items, sizeof((v1).items[0]) * (v0).size); \
+    } while (0)
+
 /// Free array of elements of a vector with preallocated array if needed
 ///
 /// @param[out]  v  Vector to free.
diff --git a/src/nvim/api/extmark.c b/src/nvim/api/extmark.c
index 268fdded9a..b76a275c0d 100644
--- a/src/nvim/api/extmark.c
+++ b/src/nvim/api/extmark.c
@@ -308,6 +308,10 @@ ArrayOf(Integer) nvim_buf_get_extmark_by_id(Buffer buffer, Integer ns_id,
 /// If `end` is less than `start`, traversal works backwards. (Useful
 /// with `limit`, to get the first marks prior to a given position.)
 ///
+/// Note: when using extmark ranges (marks with a end_row/end_col position)
+/// the `overlap` option might be useful. Otherwise only the start position
+/// of an extmark will be considered.
+///
 /// Example:
 /// <pre>lua
 ///   local api = vim.api
@@ -334,11 +338,13 @@ ArrayOf(Integer) nvim_buf_get_extmark_by_id(Buffer buffer, Integer ns_id,
 ///          - limit:  Maximum number of marks to return
 ///          - details: Whether to include the details dict
 ///          - hl_name: Whether to include highlight group name instead of id, true if omitted
+///          - overlap: Also include marks which overlap the range, even if
+///                     their start position is less than `start`
 ///          - type: Filter marks by type: "highlight", "sign", "virt_text" and "virt_lines"
 /// @param[out] err   Error details, if any
 /// @return List of [extmark_id, row, col] tuples in "traversal order".
-Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object end, Dictionary opts,
-                            Error *err)
+Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object end,
+                            Dict(get_extmarks) *opts, Error *err)
   FUNC_API_SINCE(7)
 {
   Array rv = ARRAY_DICT_INIT;
@@ -348,63 +354,32 @@ Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object e
     return rv;
   }
 
-  bool all_ns;
-  if (ns_id == -1) {
-    all_ns = true;
-  } else {
-    VALIDATE_INT(ns_initialized((uint32_t)ns_id), "ns_id", ns_id, {
-      return rv;
-    });
-    all_ns = false;
-  }
+  VALIDATE_INT(ns_id == -1 || ns_initialized((uint32_t)ns_id), "ns_id", ns_id, {
+    return rv;
+  });
 
-  Integer limit = -1;
-  bool details = false;
-  bool hl_name = true;
-  ExtmarkType type = kExtmarkNone;
+  bool details = opts->details;
+  bool hl_name = GET_BOOL_OR_TRUE(opts, get_extmarks, hl_name);
 
-  for (size_t i = 0; i < opts.size; i++) {
-    String k = opts.items[i].key;
-    Object *v = &opts.items[i].value;
-    if (strequal("limit", k.data)) {
-      VALIDATE_T("limit", kObjectTypeInteger, v->type, {
-        return rv;
-      });
-      limit = v->data.integer;
-    } else if (strequal("details", k.data)) {
-      details = api_object_to_bool(*v, "details", false, err);
-      if (ERROR_SET(err)) {
-        return rv;
-      }
-    } else if (strequal("hl_name", k.data)) {
-      hl_name = api_object_to_bool(*v, "hl_name", false, err);
-      if (ERROR_SET(err)) {
-        return rv;
-      }
-    } else if (strequal("type", k.data)) {
-      VALIDATE_EXP(v->type == kObjectTypeString, "type", "String", api_typename(v->type), {
-        return rv;
-      });
-      if (strequal(v->data.string.data, "sign")) {
-        type = kExtmarkSign;
-      } else if (strequal(v->data.string.data, "virt_text")) {
-        type = kExtmarkVirtText;
-      } else if (strequal(v->data.string.data, "virt_lines")) {
-        type = kExtmarkVirtLines;
-      } else if (strequal(v->data.string.data, "highlight")) {
-        type = kExtmarkHighlight;
-      } else {
-        VALIDATE_EXP(false, "type", "sign, virt_text, virt_lines or highlight", v->data.string.data, {
-          return rv;
-        });
-      }
+  ExtmarkType type = kExtmarkNone;
+  if (HAS_KEY(opts, get_extmarks, type)) {
+    if (strequal(opts->type.data, "sign")) {
+      type = kExtmarkSign;
+    } else if (strequal(opts->type.data, "virt_text")) {
+      type = kExtmarkVirtText;
+    } else if (strequal(opts->type.data, "virt_lines")) {
+      type = kExtmarkVirtLines;
+    } else if (strequal(opts->type.data, "highlight")) {
+      type = kExtmarkHighlight;
     } else {
-      VALIDATE_S(false, "'opts' key", k.data, {
+      VALIDATE_EXP(false, "type", "sign, virt_text, virt_lines or highlight", opts->type.data, {
         return rv;
       });
     }
   }
 
+  Integer limit = HAS_KEY(opts, get_extmarks, limit) ? opts->limit : -1;
+
   if (limit == 0) {
     return rv;
   } else if (limit < 0) {
@@ -429,11 +404,12 @@ Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object e
     reverse = true;
   }
 
+  // note: ns_id=-1 allowed, represented as UINT32_MAX
   ExtmarkInfoArray marks = extmark_get(buf, (uint32_t)ns_id, l_row, l_col, u_row,
-                                       u_col, (int64_t)limit, reverse, all_ns, type);
+                                       u_col, (int64_t)limit, reverse, type, opts->overlap);
 
   for (size_t i = 0; i < kv_size(marks); i++) {
-    ADD(rv, ARRAY_OBJ(extmark_to_array(&kv_A(marks, i), true, (bool)details, hl_name)));
+    ADD(rv, ARRAY_OBJ(extmark_to_array(&kv_A(marks, i), true, details, hl_name)));
   }
 
   kv_destroy(marks);
@@ -451,6 +427,11 @@ Array nvim_buf_get_extmarks(Buffer buffer, Integer ns_id, Object start, Object e
 /// Using the optional arguments, it is possible to use this to highlight
 /// a range of text, and also to associate virtual text to the mark.
 ///
+/// If present, the position defined by `end_col` and `end_row` should be after
+/// the start position in order for the extmark to cover a range.
+/// An earlier end position is not an error, but then it behaves like an empty
+/// range (no highlighting).
+///
 /// @param buffer  Buffer handle, or 0 for current buffer
 /// @param ns_id  Namespace id from |nvim_create_namespace()|
 /// @param line  Line where to place the mark, 0-based. |api-indexing|
@@ -1230,3 +1211,14 @@ free_exit:
   clear_virttext(&virt_text);
   return virt_text;
 }
+
+String nvim__buf_debug_extmarks(Buffer buffer, Boolean keys, Boolean dot, Error *err)
+  FUNC_API_SINCE(7)
+{
+  buf_T *buf = find_buffer_by_handle(buffer, err);
+  if (!buf) {
+    return NULL_STRING;
+  }
+
+  return mt_inspect(buf->b_marktree, keys, dot);
+}
diff --git a/src/nvim/api/keysets.h b/src/nvim/api/keysets.h
index 0a07e8c16f..4e5e7af619 100644
--- a/src/nvim/api/keysets.h
+++ b/src/nvim/api/keysets.h
@@ -51,6 +51,15 @@ typedef struct {
 } Dict(set_extmark);
 
 typedef struct {
+  OptionalKeys is_set__get_extmarks_;
+  Integer limit;
+  Boolean details;
+  Boolean hl_name;
+  Boolean overlap;
+  String type;
+} Dict(get_extmarks);
+
+typedef struct {
   OptionalKeys is_set__keymap_;
   Boolean noremap;
   Boolean nowait;
diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c
index 8eacec4d5e..d2a5eab0a5 100644
--- a/src/nvim/buffer.c
+++ b/src/nvim/buffer.c
@@ -747,6 +747,7 @@ void buf_clear_file(buf_T *buf)
 void buf_clear(void)
 {
   linenr_T line_count = curbuf->b_ml.ml_line_count;
+  extmark_free_all(curbuf);   // delete any extmarks
   while (!(curbuf->b_ml.ml_flags & ML_EMPTY)) {
     ml_delete((linenr_T)1, false);
   }
diff --git a/src/nvim/decoration.c b/src/nvim/decoration.c
index d9d1417d2a..265bc11661 100644
--- a/src/nvim/decoration.c
+++ b/src/nvim/decoration.c
@@ -158,7 +158,7 @@ Decoration *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);
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0 || mark.pos.row > row) {
       break;
     } else if (marktree_decor_level(mark) < kDecorLevelVisible) {
@@ -189,7 +189,7 @@ bool decor_redraw_reset(win_T *wp, DecorState *state)
   return wp->w_buffer->b_marktree->n_keys;
 }
 
-Decoration get_decor(mtkey_t mark)
+Decoration get_decor(MTKey mark)
 {
   if (mark.decor_full) {
     return *mark.decor_full;
@@ -211,50 +211,20 @@ bool decor_redraw_start(win_T *wp, int top_row, DecorState *state)
 {
   buf_T *buf = wp->w_buffer;
   state->top_row = top_row;
-  marktree_itr_get(buf->b_marktree, top_row, 0, state->itr);
-  if (!state->itr->node) {
+  if (!marktree_itr_get_overlap(buf->b_marktree, top_row, 0, state->itr)) {
     return false;
   }
-  marktree_itr_rewind(buf->b_marktree, state->itr);
-  while (true) {
-    mtkey_t mark = marktree_itr_current(state->itr);
-    if (mark.pos.row < 0) {  // || mark.row > end_row
-      break;
-    }
-    if ((mark.pos.row < top_row && mt_end(mark))
-        || marktree_decor_level(mark) < kDecorLevelVisible) {
-      goto next_mark;
-    }
+  MTPair pair;
 
-    Decoration decor = get_decor(mark);
-
-    mtpos_t altpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
-
-    // Exclude start marks if the end mark position is above the top row
-    // Exclude end marks if we have already added the start mark
-    if ((mt_start(mark) && altpos.row < top_row && !decor_virt_pos(&decor))
-        || (mt_end(mark) && altpos.row >= top_row)) {
-      goto next_mark;
+  while (marktree_itr_step_overlap(buf->b_marktree, state->itr, &pair)) {
+    if (marktree_decor_level(pair.start) < kDecorLevelVisible) {
+      continue;
     }
 
-    if (mt_end(mark)) {
-      decor_add(state, altpos.row, altpos.col, mark.pos.row, mark.pos.col,
-                &decor, false, mark.ns, mark.id);
-    } else {
-      if (altpos.row == -1) {
-        altpos.row = mark.pos.row;
-        altpos.col = mark.pos.col;
-      }
-      decor_add(state, mark.pos.row, mark.pos.col, altpos.row, altpos.col,
-                &decor, false, mark.ns, mark.id);
-    }
+    Decoration decor = get_decor(pair.start);
 
-next_mark:
-    if (marktree_itr_node_done(state->itr)) {
-      marktree_itr_next(buf->b_marktree, state->itr);
-      break;
-    }
-    marktree_itr_next(buf->b_marktree, state->itr);
+    decor_add(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);
   }
 
   return true;  // TODO(bfredl): check if available in the region
@@ -268,7 +238,13 @@ bool decor_redraw_line(win_T *wp, int row, DecorState *state)
   state->row = row;
   state->col_until = -1;
   state->eol_col = -1;
-  return true;  // TODO(bfredl): be more precise
+
+  if (kv_size(state->active)) {
+    return true;
+  }
+
+  MTKey k = marktree_itr_current(state->itr);
+  return (k.pos.row >= 0 && k.pos.row <= row);
 }
 
 static void decor_add(DecorState *state, int start_row, int start_col, int end_row, int end_col,
@@ -302,7 +278,7 @@ int decor_redraw_col(win_T *wp, int col, int win_col, bool hidden, DecorState *s
   while (true) {
     // TODO(bfredl): check duplicate entry in "intersection"
     // branch
-    mtkey_t mark = marktree_itr_current(state->itr);
+    MTKey mark = marktree_itr_current(state->itr);
     if (mark.pos.row < 0 || mark.pos.row > state->row) {
       break;
     } else if (mark.pos.row == state->row && mark.pos.col > col) {
@@ -317,8 +293,7 @@ int decor_redraw_col(win_T *wp, int col, int win_col, bool hidden, DecorState *s
 
     Decoration decor = get_decor(mark);
 
-    mtpos_t endpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
-
+    MTPos endpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
     if (endpos.row == -1) {
       endpos = mark.pos;
     }
@@ -412,8 +387,28 @@ void decor_redraw_signs(buf_T *buf, int row, int *num_signs, SignTextAttrs sattr
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, row, 0, itr);
 
+  // TODO(bfredl): integrate with main decor loop.
+  if (!marktree_itr_get_overlap(buf->b_marktree, row, 0, itr)) {
+    return;
+  }
+
+  MTPair pair;
+  while (marktree_itr_step_overlap(buf->b_marktree, itr, &pair)) {
+    if (marktree_decor_level(pair.start) < kDecorLevelVisible) {
+      continue;
+    }
+
+    Decoration *decor = pair.start.decor_full;
+
+    if (!decor || !decor_has_sign(decor)) {
+      continue;
+    }
+
+    decor_to_sign(decor, num_signs, sattrs, num_id, line_id, cul_id);
+  }
+
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0 || mark.pos.row > row) {
       break;
     }
@@ -428,43 +423,49 @@ void decor_redraw_signs(buf_T *buf, int row, int *num_signs, SignTextAttrs sattr
       goto next_mark;
     }
 
-    if (decor->sign_text) {
-      int j;
-      for (j = (*num_signs); j > 0; j--) {
-        if (sattrs[j - 1].priority >= decor->priority) {
-          break;
-        }
-        if (j < SIGN_SHOW_MAX) {
-          sattrs[j] = sattrs[j - 1];
-        }
+    decor_to_sign(decor, num_signs, sattrs, num_id, line_id, cul_id);
+
+next_mark:
+    marktree_itr_next(buf->b_marktree, itr);
+  }
+}
+
+static void decor_to_sign(Decoration *decor, int *num_signs, SignTextAttrs sattrs[],
+                          HlPriId *num_id, HlPriId *line_id, HlPriId *cul_id)
+{
+  if (decor->sign_text) {
+    int j;
+    for (j = (*num_signs); j > 0; j--) {
+      if (sattrs[j - 1].priority >= decor->priority) {
+        break;
       }
       if (j < SIGN_SHOW_MAX) {
-        sattrs[j] = (SignTextAttrs) {
-          .text = decor->sign_text,
-          .hl_id = decor->sign_hl_id,
-          .priority = decor->priority
-        };
-        (*num_signs)++;
+        sattrs[j] = sattrs[j - 1];
       }
     }
-
-    struct { HlPriId *dest; int hl; } cattrs[] = {
-      { line_id, decor->line_hl_id        },
-      { num_id,  decor->number_hl_id      },
-      { cul_id,  decor->cursorline_hl_id  },
-      { NULL, -1 },
-    };
-    for (int i = 0; cattrs[i].dest; i++) {
-      if (cattrs[i].hl != 0 && decor->priority >= cattrs[i].dest->priority) {
-        *cattrs[i].dest = (HlPriId) {
-          .hl_id = cattrs[i].hl,
-          .priority = decor->priority
-        };
-      }
+    if (j < SIGN_SHOW_MAX) {
+      sattrs[j] = (SignTextAttrs) {
+        .text = decor->sign_text,
+        .hl_id = decor->sign_hl_id,
+        .priority = decor->priority
+      };
+      (*num_signs)++;
     }
+  }
 
-next_mark:
-    marktree_itr_next(buf->b_marktree, itr);
+  struct { HlPriId *dest; int hl; } cattrs[] = {
+    { line_id, decor->line_hl_id        },
+    { num_id,  decor->number_hl_id      },
+    { cul_id,  decor->cursorline_hl_id  },
+    { NULL, -1 },
+  };
+  for (int i = 0; cattrs[i].dest; i++) {
+    if (cattrs[i].hl != 0 && decor->priority >= cattrs[i].dest->priority) {
+      *cattrs[i].dest = (HlPriId) {
+        .hl_id = cattrs[i].hl,
+        .priority = decor->priority
+      };
+    }
   }
 }
 
@@ -488,7 +489,7 @@ int decor_signcols(buf_T *buf, DecorState *state, int row, int end_row, int max)
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, 0, -1, itr);
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0 || mark.pos.row > end_row) {
       break;
     }
@@ -525,7 +526,7 @@ int decor_signcols(buf_T *buf, DecorState *state, int row, int end_row, int max)
       goto next_mark;
     }
 
-    mtpos_t altpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
+    MTPos altpos = marktree_get_altpos(buf->b_marktree, mark, NULL);
 
     if (mt_end(mark)) {
       if (mark.pos.row >= row && altpos.row <= end_row) {
@@ -610,7 +611,7 @@ int decor_virt_lines(win_T *wp, linenr_T lnum, VirtLines *lines, TriState has_fo
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, start_row, 0, itr);
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0 || mark.pos.row >= end_row) {
       break;
     } else if (mt_end(mark)
diff --git a/src/nvim/drawline.c b/src/nvim/drawline.c
index 4b989fa59a..969021ef2c 100644
--- a/src/nvim/drawline.c
+++ b/src/nvim/drawline.c
@@ -2889,15 +2889,21 @@ int win_line(win_T *wp, linenr_T lnum, int startrow, int endrow, bool number_onl
         && !wp->w_p_wrap
         && wlv.filler_todo <= 0
         && (wp->w_p_rl ? wlv.col == 0 : wlv.col == grid->cols - 1)
-        && !has_fold
-        && (*ptr != NUL
-            || lcs_eol_one > 0
-            || (wlv.n_extra > 0 && (wlv.c_extra != NUL || *wlv.p_extra != NUL))
-            || wlv.more_virt_inline_chunks)) {
-      c = wp->w_p_lcs_chars.ext;
-      wlv.char_attr = win_hl_attr(wp, HLF_AT);
-      mb_c = c;
-      mb_utf8 = check_mb_utf8(&c, u8cc);
+        && !has_fold) {
+      if (*ptr == NUL && lcs_eol_one == 0 && has_decor) {
+        // Tricky: there might be a virtual text just _after_ the last char
+        decor_redraw_col(wp, (colnr_T)v, wlv.off, false, &decor_state);
+        handle_inline_virtual_text(wp, &wlv, v);
+      }
+      if (*ptr != NUL
+          || lcs_eol_one > 0
+          || (wlv.n_extra > 0 && (wlv.c_extra != NUL || *wlv.p_extra != NUL))
+          || wlv.more_virt_inline_chunks) {
+        c = wp->w_p_lcs_chars.ext;
+        wlv.char_attr = win_hl_attr(wp, HLF_AT);
+        mb_c = c;
+        mb_utf8 = check_mb_utf8(&c, u8cc);
+      }
     }
 
     // advance to the next 'colorcolumn'
@@ -3079,6 +3085,15 @@ int win_line(win_T *wp, linenr_T lnum, int startrow, int endrow, bool number_onl
       wlv.char_attr = saved_attr2;
     }
 
+    if ((wp->w_p_rl ? (wlv.col < 0) : (wlv.col >= grid->cols)) && has_decor) {
+      // At the end of screen line: might need to peek for decorations just after
+      // this position. Without wrapping, we might need to display win_pos overlays
+      // from the entire text line.
+      colnr_T nextpos = wp->w_p_wrap ? (colnr_T)(ptr - line) : (colnr_T)strlen(line);
+      decor_redraw_col(wp, nextpos, wlv.off, true, &decor_state);
+      handle_inline_virtual_text(wp, &wlv, v);
+    }
+
     // At end of screen line and there is more to come: Display the line
     // so far.  If there is no more to display it is caught above.
     if ((wp->w_p_rl ? (wlv.col < 0) : (wlv.col >= grid->cols))
diff --git a/src/nvim/ex_getln.c b/src/nvim/ex_getln.c
index 08b010c153..09781f392a 100644
--- a/src/nvim/ex_getln.c
+++ b/src/nvim/ex_getln.c
@@ -2410,6 +2410,9 @@ static void cmdpreview_restore_state(CpInfo *cpinfo)
 
     buf->b_changed = cp_bufinfo.save_b_changed;
 
+    // Clear preview highlights.
+    extmark_clear(buf, (uint32_t)cmdpreview_ns, 0, 0, MAXLNUM, MAXCOL);
+
     if (buf->b_u_seq_cur != cp_bufinfo.undo_info.save_b_u_seq_cur) {
       int count = 0;
 
@@ -2439,9 +2442,6 @@ static void cmdpreview_restore_state(CpInfo *cpinfo)
     }
 
     buf->b_p_ul = cp_bufinfo.save_b_p_ul;        // Restore 'undolevels'
-
-    // Clear preview highlights.
-    extmark_clear(buf, (uint32_t)cmdpreview_ns, 0, 0, MAXLNUM, MAXCOL);
   }
 
   for (size_t i = 0; i < cpinfo->win_info.size; i++) {
diff --git a/src/nvim/extmark.c b/src/nvim/extmark.c
index 77e41cb5cf..5140fe199e 100644
--- a/src/nvim/extmark.c
+++ b/src/nvim/extmark.c
@@ -82,7 +82,7 @@ void extmark_set(buf_T *buf, uint32_t ns_id, uint32_t *idp, int row, colnr_T col
     id = ++*ns;
   } else {
     MarkTreeIter itr[1] = { 0 };
-    mtkey_t old_mark = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, itr);
+    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) {
@@ -124,8 +124,8 @@ void extmark_set(buf_T *buf, uint32_t ns_id, uint32_t *idp, int row, colnr_T col
     }
   }
 
-  mtkey_t mark = { { row, col }, ns_id, id, 0,
-                   mt_flags(right_gravity, decor_level), 0, NULL };
+  MTKey mark = { { row, col }, ns_id, id, 0,
+                 mt_flags(right_gravity, decor_level), 0, NULL };
   if (decor_full) {
     mark.decor_full = decor;
   } else if (decor) {
@@ -180,7 +180,7 @@ error:
 static bool extmark_setraw(buf_T *buf, uint64_t mark, int row, colnr_T col)
 {
   MarkTreeIter itr[1] = { 0 };
-  mtkey_t key = marktree_lookup(buf->b_marktree, mark, itr);
+  MTKey key = marktree_lookup(buf->b_marktree, mark, itr);
   if (key.pos.row == -1) {
     return false;
   }
@@ -199,14 +199,14 @@ static bool extmark_setraw(buf_T *buf, uint64_t mark, int row, colnr_T col)
 bool extmark_del(buf_T *buf, uint32_t ns_id, uint32_t id)
 {
   MarkTreeIter itr[1] = { 0 };
-  mtkey_t key = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, itr);
+  MTKey key = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, itr);
   if (!key.id) {
     return false;
   }
   assert(key.pos.row >= 0);
   uint64_t other = marktree_del_itr(buf->b_marktree, itr, false);
 
-  mtkey_t key2 = key;
+  MTKey key2 = key;
 
   if (other) {
     key2 = marktree_lookup(buf->b_marktree, other, itr);
@@ -250,7 +250,7 @@ bool extmark_clear(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_r
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, l_row, l_col, itr);
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0
         || mark.pos.row > u_row
         || (mark.pos.row == u_row && mark.pos.col > u_col)) {
@@ -292,7 +292,7 @@ bool extmark_clear(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_r
   uint64_t id;
   ssize_t decor_id;
   map_foreach(&delete_set, id, decor_id, {
-    mtkey_t mark = marktree_lookup(buf->b_marktree, id, itr);
+    MTKey mark = marktree_lookup(buf->b_marktree, id, itr);
     assert(marktree_itr_valid(itr));
     marktree_del_itr(buf->b_marktree, itr, false);
     if (decor_id >= 0) {
@@ -313,17 +313,31 @@ bool extmark_clear(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_r
 /// dir can be set to control the order of the array
 /// amount = amount of marks to find or -1 for all
 ExtmarkInfoArray extmark_get(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_col, int u_row,
-                             colnr_T u_col, int64_t amount, bool reverse, bool all_ns,
-                             ExtmarkType type_filter)
+                             colnr_T u_col, int64_t amount, bool reverse, ExtmarkType type_filter,
+                             bool overlap)
 {
   ExtmarkInfoArray array = KV_INITIAL_VALUE;
   MarkTreeIter itr[1];
-  // Find all the marks
-  marktree_itr_get_ext(buf->b_marktree, mtpos_t(l_row, l_col),
-                       itr, reverse, false, NULL);
+
+  if (overlap) {
+    // Find all the marks overlapping the start position
+    if (!marktree_itr_get_overlap(buf->b_marktree, l_row, l_col, itr)) {
+      return array;
+    }
+
+    MTPair pair;
+    while (marktree_itr_step_overlap(buf->b_marktree, itr, &pair)) {
+      push_mark(&array, ns_id, type_filter, pair.start, pair.end_pos, pair.end_right_gravity);
+    }
+  } else {
+    // Find all the marks beginning with the start position
+    marktree_itr_get_ext(buf->b_marktree, MTPos(l_row, l_col),
+                         itr, reverse, false, NULL);
+  }
+
   int order = reverse ? -1 : 1;
   while ((int64_t)kv_size(array) < amount) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0
         || (mark.pos.row - u_row) * order > 0
         || (mark.pos.row == u_row && (mark.pos.col - u_col) * order > 0)) {
@@ -333,35 +347,8 @@ ExtmarkInfoArray extmark_get(buf_T *buf, uint32_t ns_id, int l_row, colnr_T l_co
       goto next_mark;
     }
 
-    uint16_t type_flags = kExtmarkNone;
-    if (type_filter != kExtmarkNone) {
-      Decoration *decor = mark.decor_full;
-      if (decor && (decor->sign_text || decor->number_hl_id)) {
-        type_flags |= kExtmarkSign;
-      }
-      if (decor && decor->virt_text.size) {
-        type_flags |= kExtmarkVirtText;
-      }
-      if (decor && decor->virt_lines.size) {
-        type_flags |= kExtmarkVirtLines;
-      }
-      if ((decor && (decor->line_hl_id || decor->cursorline_hl_id))
-          || mark.hl_id) {
-        type_flags |= kExtmarkHighlight;
-      }
-    }
-
-    if ((all_ns || mark.ns == ns_id) && type_flags & type_filter) {
-      mtkey_t end = marktree_get_alt(buf->b_marktree, mark, NULL);
-      kv_push(array, ((ExtmarkInfo) { .ns_id = mark.ns,
-                                      .mark_id = mark.id,
-                                      .row = mark.pos.row, .col = mark.pos.col,
-                                      .end_row = end.pos.row,
-                                      .end_col = end.pos.col,
-                                      .right_gravity = mt_right(mark),
-                                      .end_right_gravity = mt_right(end),
-                                      .decor = get_decor(mark) }));
-    }
+    MTKey end = marktree_get_alt(buf->b_marktree, mark, NULL);
+    push_mark(&array, ns_id, type_filter, mark, end.pos, mt_right(end));
 next_mark:
     if (reverse) {
       marktree_itr_prev(buf->b_marktree, itr);
@@ -372,16 +359,54 @@ next_mark:
   return array;
 }
 
+static void push_mark(ExtmarkInfoArray *array, uint32_t ns_id, ExtmarkType type_filter, MTKey mark,
+                      MTPos end_pos, bool end_right)
+{
+  if (!(ns_id == UINT32_MAX || mark.ns == ns_id)) {
+    return;
+  }
+  uint16_t type_flags = kExtmarkNone;
+  if (type_filter != kExtmarkNone) {
+    Decoration *decor = mark.decor_full;
+    if (decor && (decor->sign_text || decor->number_hl_id)) {
+      type_flags |= kExtmarkSign;
+    }
+    if (decor && decor->virt_text.size) {
+      type_flags |= kExtmarkVirtText;
+    }
+    if (decor && decor->virt_lines.size) {
+      type_flags |= kExtmarkVirtLines;
+    }
+    if ((decor && (decor->line_hl_id || decor->cursorline_hl_id))
+        || mark.hl_id) {
+      type_flags |= kExtmarkHighlight;
+    }
+
+    if (!(type_flags & type_filter)) {
+      return;
+    }
+  }
+
+  kv_push(*array, ((ExtmarkInfo) { .ns_id = mark.ns,
+                                   .mark_id = mark.id,
+                                   .row = mark.pos.row, .col = mark.pos.col,
+                                   .end_row = end_pos.row,
+                                   .end_col = end_pos.col,
+                                   .right_gravity = mt_right(mark),
+                                   .end_right_gravity = end_right,
+                                   .decor = get_decor(mark) }));
+}
+
 /// Lookup an extmark by id
 ExtmarkInfo extmark_from_id(buf_T *buf, uint32_t ns_id, uint32_t id)
 {
   ExtmarkInfo ret = { 0, 0, -1, -1, -1, -1, false, false, DECORATION_INIT };
-  mtkey_t mark = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, NULL);
+  MTKey mark = marktree_lookup_ns(buf->b_marktree, ns_id, id, false, NULL);
   if (!mark.id) {
     return ret;
   }
   assert(mark.pos.row >= 0);
-  mtkey_t end = marktree_get_alt(buf->b_marktree, mark, NULL);
+  MTKey end = marktree_get_alt(buf->b_marktree, mark, NULL);
 
   ret.ns_id = ns_id;
   ret.mark_id = id;
@@ -406,7 +431,7 @@ void extmark_free_all(buf_T *buf)
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, 0, 0, itr);
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0) {
       break;
     }
@@ -462,7 +487,7 @@ void u_extmark_copy(buf_T *buf, int l_row, colnr_T l_col, int u_row, colnr_T u_c
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get(buf->b_marktree, (int32_t)l_row, l_col, itr);
   while (true) {
-    mtkey_t mark = marktree_itr_current(itr);
+    MTKey mark = marktree_itr_current(itr);
     if (mark.pos.row < 0
         || mark.pos.row > u_row
         || (mark.pos.row == u_row && mark.pos.col > u_col)) {
diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index d07d176b6d..d8b8dbba29 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -14,8 +14,6 @@
 // Use marktree_itr_current and marktree_itr_next/prev to read marks in a loop.
 // marktree_del_itr deletes the current mark of the iterator and implicitly
 // moves the iterator to the next mark.
-//
-// Work is ongoing to fully support ranges (mark pairs).
 
 // Copyright notice for kbtree (included in heavily modified form):
 //
@@ -58,19 +56,27 @@
 #include "nvim/memory.h"
 #include "nvim/pos.h"
 
+// only for debug functions
+#include "nvim/api/private/helpers.h"
+
 #define T MT_BRANCH_FACTOR
-#define ILEN (sizeof(mtnode_t) + (2 * T) * sizeof(void *))
+#define ILEN (sizeof(MTNode) + (2 * T) * sizeof(void *))
 
 #define ID_INCR (((uint64_t)1) << 2)
 
-#define rawkey(itr) ((itr)->node->key[(itr)->i])
+#define rawkey(itr) ((itr)->x->key[(itr)->i])
 
-static bool pos_leq(mtpos_t a, mtpos_t b)
+static bool pos_leq(MTPos a, MTPos b)
 {
   return a.row < b.row || (a.row == b.row && a.col <= b.col);
 }
 
-static void relative(mtpos_t base, mtpos_t *val)
+static bool pos_less(MTPos a, MTPos b)
+{
+  return !pos_leq(b, a);
+}
+
+static void relative(MTPos base, MTPos *val)
 {
   assert(pos_leq(base, *val));
   if (val->row == base.row) {
@@ -81,7 +87,7 @@ static void relative(mtpos_t base, mtpos_t *val)
   }
 }
 
-static void unrelative(mtpos_t base, mtpos_t *val)
+static void unrelative(MTPos base, MTPos *val)
 {
   if (val->row == 0) {
     val->row = base.row;
@@ -91,7 +97,7 @@ static void unrelative(mtpos_t base, mtpos_t *val)
   }
 }
 
-static void compose(mtpos_t *base, mtpos_t val)
+static void compose(MTPos *base, MTPos val)
 {
   if (val.row == 0) {
     base->col += val.col;
@@ -101,12 +107,21 @@ static void compose(mtpos_t *base, mtpos_t val)
   }
 }
 
+// Used by `marktree_splice`. Need to keep track of marks which moved
+// in order to repair intersections.
+typedef struct {
+  uint64_t id;
+  MTNode *old, *new;
+  int old_i, new_i;
+} Damage;
+typedef kvec_withinit_t(Damage, 8) DamageList;
+
 #ifdef INCLUDE_GENERATED_DECLARATIONS
 # include "marktree.c.generated.h"
 #endif
 
 #define mt_generic_cmp(a, b) (((b) < (a)) - ((a) < (b)))
-static int key_cmp(mtkey_t a, mtkey_t b)
+static int key_cmp(MTKey a, MTKey b)
 {
   int cmp = mt_generic_cmp(a.pos.row, b.pos.row);
   if (cmp != 0) {
@@ -116,18 +131,25 @@ static int key_cmp(mtkey_t a, mtkey_t b)
   if (cmp != 0) {
     return cmp;
   }
-  // NB: keeping the events at the same pos sorted by id is actually not
-  // necessary only make sure that START is before END etc.
-  return mt_generic_cmp(a.flags, b.flags);
+
+  // TODO(bfredl): MT_FLAG_REAL could go away if we fix marktree_getp_aux for real
+  const uint16_t cmp_mask = MT_FLAG_RIGHT_GRAVITY | MT_FLAG_END | MT_FLAG_REAL | MT_FLAG_LAST;
+  return mt_generic_cmp(a.flags & cmp_mask, b.flags & cmp_mask);
 }
 
-static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r)
+/// @return position of k if it exists in the node, otherwise the position
+/// it should be inserted, which ranges from 0 to x->n _inclusively_
+/// @param match (optional) set to TRUE if match (pos, gravity) was found
+static inline int marktree_getp_aux(const MTNode *x, MTKey k, bool *match)
 {
-  int tr, *rr, begin = 0, end = x->n;
+  bool dummy_match;
+  bool *m = match ? match : &dummy_match;
+
+  int begin = 0, end = x->n;
   if (x->n == 0) {
+    *m = false;
     return -1;
   }
-  rr = r ? r : &tr;
   while (begin < end) {
     int mid = (begin + end) >> 1;
     if (key_cmp(x->key[mid], k) < 0) {
@@ -137,47 +159,84 @@ static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r)
     }
   }
   if (begin == x->n) {
-    *rr = 1; return x->n - 1;
+    *m = false;
+    return x->n - 1;
   }
-  if ((*rr = key_cmp(k, x->key[begin])) < 0) {
+  if (!(*m = (key_cmp(k, x->key[begin]) == 0))) {
     begin--;
   }
   return begin;
 }
 
-static inline void refkey(MarkTree *b, mtnode_t *x, int i)
+static inline void refkey(MarkTree *b, MTNode *x, int i)
 {
   pmap_put(uint64_t)(b->id2node, mt_lookup_key(x->key[i]), x);
 }
 
+static MTNode *id2node(MarkTree *b, uint64_t id)
+{
+  return pmap_get(uint64_t)(b->id2node, id);
+}
+
 // put functions
 
 // x must be an internal node, which is not full
 // x->ptr[i] should be a full node, i e x->ptr[i]->n == 2*T-1
-static inline void split_node(MarkTree *b, mtnode_t *x, const int i)
+static inline void split_node(MarkTree *b, MTNode *x, const int i, MTKey next)
 {
-  mtnode_t *y = x->ptr[i];
-  mtnode_t *z;
-  z = (mtnode_t *)xcalloc(1, y->level ? ILEN : sizeof(mtnode_t));
-  b->n_nodes++;
+  MTNode *y = x->ptr[i];
+  MTNode *z = marktree_alloc_node(b, y->level);
   z->level = y->level;
   z->n = T - 1;
-  memcpy(z->key, &y->key[T], sizeof(mtkey_t) * (T - 1));
+
+  // tricky: we might split a node in between inserting the start node and the end
+  // node of the same pair. Then we must not intersect this id yet (done later
+  // in marktree_intersect_pair).
+  uint64_t last_start = mt_end(next) ? mt_lookup_id(next.ns, next.id, false) : MARKTREE_END_FLAG;
+
+  // no alloc in the common case (less than 4 intersects)
+  kvi_copy(z->intersect, y->intersect);
+
+  if (!y->level) {
+    uint64_t pi = pseudo_index(y, 0);  // note: sloppy pseudo-index
+    for (int j = 0; j < T; j++) {
+      MTKey k = y->key[j];
+      uint64_t pi_end = pseudo_index_for_id(b, mt_lookup_id(k.ns, k.id, true), true);
+      if (mt_start(k) && pi_end > pi && mt_lookup_key(k) != last_start) {
+        intersect_node(b, z, mt_lookup_id(k.ns, k.id, false));
+      }
+    }
+
+    // note: y->key[T-1] is moved up and thus checked for both
+    for (int j = T - 1; j < (T * 2) - 1; j++) {
+      MTKey k = y->key[j];
+      uint64_t pi_start = pseudo_index_for_id(b, mt_lookup_id(k.ns, k.id, false), true);
+      if (mt_end(k) && pi_start > 0 && pi_start < pi) {
+        intersect_node(b, y, mt_lookup_id(k.ns, k.id, false));
+      }
+    }
+  }
+
+  memcpy(z->key, &y->key[T], sizeof(MTKey) * (T - 1));
   for (int j = 0; j < T - 1; j++) {
     refkey(b, z, j);
   }
   if (y->level) {
-    memcpy(z->ptr, &y->ptr[T], sizeof(mtnode_t *) * T);
+    memcpy(z->ptr, &y->ptr[T], sizeof(MTNode *) * T);
     for (int j = 0; j < T; j++) {
       z->ptr[j]->parent = z;
+      z->ptr[j]->p_idx = (int16_t)j;
     }
   }
   y->n = T - 1;
   memmove(&x->ptr[i + 2], &x->ptr[i + 1],
-          sizeof(mtnode_t *) * (size_t)(x->n - i));
+          sizeof(MTNode *) * (size_t)(x->n - i));
   x->ptr[i + 1] = z;
   z->parent = x;  // == y->parent
-  memmove(&x->key[i + 1], &x->key[i], sizeof(mtkey_t) * (size_t)(x->n - i));
+  for (int j = i + 1; j < x->n + 2; j++) {
+    x->ptr[j]->p_idx = (int16_t)j;
+  }
+  memmove(&x->key[i + 1], &x->key[i], sizeof(MTKey) * (size_t)(x->n - i));
 
   // move key to internal layer:
   x->key[i] = y->key[T - 1];
@@ -190,25 +249,32 @@ static inline void split_node(MarkTree *b, mtnode_t *x, const int i)
   if (i > 0) {
     unrelative(x->key[i - 1].pos, &x->key[i].pos);
   }
+
+  if (y->level) {
+    bubble_up(y);
+    bubble_up(z);
+  } else {
+    // code above goose here
+  }
 }
 
 // x must not be a full node (even if there might be internal space)
-static inline void marktree_putp_aux(MarkTree *b, mtnode_t *x, mtkey_t k)
+static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k)
 {
-  int i;
+  // TODO(bfredl): ugh, make sure this is the _last_ valid (pos, gravity) position,
+  // to minimize movement
+  int i = marktree_getp_aux(x, k, NULL) + 1;
   if (x->level == 0) {
-    i = marktree_getp_aux(x, k, 0);
-    if (i != x->n - 1) {
-      memmove(&x->key[i + 2], &x->key[i + 1],
-              (size_t)(x->n - i - 1) * sizeof(mtkey_t));
+    if (i != x->n) {
+      memmove(&x->key[i + 1], &x->key[i],
+              (size_t)(x->n - i) * sizeof(MTKey));
     }
-    x->key[i + 1] = k;
-    refkey(b, x, i + 1);
+    x->key[i] = k;
+    refkey(b, x, i);
     x->n++;
   } else {
-    i = marktree_getp_aux(x, k, 0) + 1;
     if (x->ptr[i]->n == 2 * T - 1) {
-      split_node(b, x, i);
+      split_node(b, x, i, k);
       if (key_cmp(k, x->key[i]) > 0) {
         i++;
       }
@@ -220,7 +286,7 @@ static inline void marktree_putp_aux(MarkTree *b, mtnode_t *x, mtkey_t k)
   }
 }
 
-void marktree_put(MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_right)
+void marktree_put(MarkTree *b, MTKey key, int end_row, int end_col, bool end_right)
 {
   assert(!(key.flags & ~MT_FLAG_EXTERNAL_MASK));
   if (end_row >= 0) {
@@ -230,32 +296,151 @@ void marktree_put(MarkTree *b, mtkey_t key, int end_row, int end_col, bool end_r
   marktree_put_key(b, key);
 
   if (end_row >= 0) {
-    mtkey_t end_key = key;
+    MTKey end_key = key;
     end_key.flags = (uint16_t)((uint16_t)(key.flags & ~MT_FLAG_RIGHT_GRAVITY)
                                |(uint16_t)MT_FLAG_END
                                |(uint16_t)(end_right ? MT_FLAG_RIGHT_GRAVITY : 0));
-    end_key.pos = (mtpos_t){ end_row, end_col };
+    end_key.pos = (MTPos){ end_row, end_col };
     marktree_put_key(b, end_key);
+    MarkTreeIter itr[1] = { 0 }, end_itr[1] = { 0 };
+    marktree_lookup(b, mt_lookup_key(key), itr);
+    marktree_lookup(b, mt_lookup_key(end_key), end_itr);
+
+    marktree_intersect_pair(b, mt_lookup_key(key), itr, end_itr, false);
+  }
+}
+
+// this is currently not used very often, but if it was it should use binary search
+static bool intersection_has(Intersection *x, uint64_t id)
+{
+  for (size_t i = 0; i < kv_size(*x); i++) {
+    if (kv_A(*x, i) == id) {
+      return true;
+    } else if (kv_A(*x, i) >= id) {
+      return false;
+    }
   }
+  return false;
 }
 
-void marktree_put_key(MarkTree *b, mtkey_t k)
+static void intersect_node(MarkTree *b, MTNode *x, uint64_t id)
+{
+  assert(!(id & MARKTREE_END_FLAG));
+  kvi_pushp(x->intersect);
+  // optimized for the common case: new key is always in the end
+  for (ssize_t i = (ssize_t)kv_size(x->intersect) - 1; i >= 0; i--) {
+    if (i > 0 && kv_A(x->intersect, i - 1) > id) {
+      kv_A(x->intersect, i) = kv_A(x->intersect, i - 1);
+    } else {
+      kv_A(x->intersect, i) = id;
+      break;
+    }
+  }
+}
+
+static void unintersect_node(MarkTree *b, MTNode *x, uint64_t id, bool strict)
+{
+  assert(!(id & MARKTREE_END_FLAG));
+  bool seen = false;
+  size_t i;
+  for (i = 0; i < kv_size(x->intersect); i++) {
+    if (kv_A(x->intersect, i) < id) {
+      continue;
+    } else if (kv_A(x->intersect, i) == id) {
+      seen = true;
+      break;
+    } else {  // (kv_A(x->intersect, i) > id)
+      break;
+    }
+  }
+  if (strict) {
+    assert(seen);
+  }
+
+  if (seen) {
+    if (i < kv_size(x->intersect) - 1) {
+      memmove(&kv_A(x->intersect, i), &kv_A(x->intersect, i + 1), (kv_size(x->intersect) - i - 1) *
+              sizeof(kv_A(x->intersect, i)));
+    }
+    kv_size(x->intersect)--;
+  }
+}
+
+/// @param itr mutated
+/// @param end_itr not mutated
+void marktree_intersect_pair(MarkTree *b, uint64_t id, MarkTreeIter *itr, MarkTreeIter *end_itr,
+                             bool delete)
+{
+  int lvl = 0, maxlvl = MIN(itr->lvl, end_itr->lvl);
+#define iat(itr, l, q) ((l == itr->lvl) ? itr->i + q : itr->s[l].i)
+  for (; lvl < maxlvl; lvl++) {
+    if (itr->s[lvl].i > end_itr->s[lvl].i) {
+      return;  // empty range
+    } else if (itr->s[lvl].i < end_itr->s[lvl].i) {
+      break;  // work to do
+    }
+  }
+  if (lvl == maxlvl && iat(itr, lvl, 1) > iat(end_itr, lvl, 0)) {
+    return;  // empty range
+  }
+
+  while (itr->x) {
+    bool skip = false;
+    if (itr->x == end_itr->x) {
+      if (itr->x->level == 0 || itr->i >= end_itr->i) {
+        break;
+      } else {
+        skip = true;
+      }
+    } else if (itr->lvl > lvl) {
+      skip = true;
+    } else {
+      if (iat(itr, lvl, 1) < iat(end_itr, lvl, 1)) {
+        skip = true;
+      } else {
+        lvl++;
+      }
+    }
+
+    if (skip) {
+      if (itr->x->level) {
+        MTNode *x = itr->x->ptr[itr->i + 1];
+        if (delete) {
+          unintersect_node(b, x, id, true);
+        } else {
+          intersect_node(b, x, id);
+        }
+      }
+    }
+    marktree_itr_next_skip(b, itr, skip, true, NULL);
+  }
+#undef iat
+}
+
+static MTNode *marktree_alloc_node(MarkTree *b, bool internal)
+{
+  MTNode *x = xcalloc(1, internal ? ILEN : sizeof(MTNode));
+  kvi_init(x->intersect);
+  b->n_nodes++;
+  return x;
+}
+
+void marktree_put_key(MarkTree *b, MTKey k)
 {
   k.flags |= MT_FLAG_REAL;  // let's be real.
   if (!b->root) {
-    b->root = (mtnode_t *)xcalloc(1, ILEN);
-    b->n_nodes++;
+    b->root = marktree_alloc_node(b, true);
   }
-  mtnode_t *r, *s;
+  MTNode *r, *s;
   b->n_keys++;
   r = b->root;
   if (r->n == 2 * T - 1) {
-    b->n_nodes++;
-    s = (mtnode_t *)xcalloc(1, ILEN);
+    s = marktree_alloc_node(b, true);
     b->root = s; s->level = r->level + 1; s->n = 0;
     s->ptr[0] = r;
     r->parent = s;
-    split_node(b, s, 0);
+    r->p_idx = 0;
+    split_node(b, s, 0, k);
     r = s;
   }
   marktree_putp_aux(b, r, k);
@@ -289,22 +474,31 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
 {
   int adjustment = 0;
 
-  mtnode_t *cur = itr->node;
+  MTNode *cur = itr->x;
   int curi = itr->i;
   uint64_t id = mt_lookup_key(cur->key[curi]);
-  // fprintf(stderr, "\nDELET %lu\n", id);
 
-  mtkey_t raw = rawkey(itr);
+  MTKey raw = rawkey(itr);
   uint64_t other = 0;
-  if (mt_paired(raw)) {
-    other = mt_lookup_id(raw.ns, raw.id, !mt_end(raw));
+  if (mt_paired(raw) && !(raw.flags & MT_FLAG_ORPHANED)) {
+    other = mt_lookup_key_side(raw, !mt_end(raw));
+
+    MarkTreeIter other_itr[1];
+    marktree_lookup(b, other, other_itr);
+    rawkey(other_itr).flags |= MT_FLAG_ORPHANED;
+    // Remove intersect markers. NB: must match exactly!
+    if (mt_start(raw)) {
+      MarkTreeIter this_itr[1] = { *itr };  // mutated copy
+      marktree_intersect_pair(b, id, this_itr, other_itr, true);
+    } else {
+      marktree_intersect_pair(b, other, other_itr, itr, true);
+    }
   }
 
-  if (itr->node->level) {
+  if (itr->x->level) {
     if (rev) {
       abort();
     } else {
-      // fprintf(stderr, "INTERNAL %d\n", cur->level);
       // steal previous node
       marktree_itr_prev(b, itr);
       adjustment = -1;
@@ -312,41 +506,72 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
   }
 
   // 3.
-  mtnode_t *x = itr->node;
+  MTNode *x = itr->x;
   assert(x->level == 0);
-  mtkey_t intkey = x->key[itr->i];
+  MTKey intkey = x->key[itr->i];
   if (x->n > itr->i + 1) {
     memmove(&x->key[itr->i], &x->key[itr->i + 1],
-            sizeof(mtkey_t) * (size_t)(x->n - itr->i - 1));
+            sizeof(MTKey) * (size_t)(x->n - itr->i - 1));
   }
   x->n--;
 
+  b->n_keys--;
+  pmap_del(uint64_t)(b->id2node, id, NULL);
+
   // 4.
   // if (adjustment == 1) {
   //   abort();
   // }
   if (adjustment == -1) {
     int ilvl = itr->lvl - 1;
-    const mtnode_t *lnode = x;
+    MTNode *lnode = x;
+    uint64_t start_id = 0;
+    bool did_bubble = false;
+    if (mt_end(intkey)) {
+      start_id = mt_lookup_key_side(intkey, false);
+    }
     do {
-      const mtnode_t *const p = lnode->parent;
+      MTNode *p = lnode->parent;
       if (ilvl < 0) {
         abort();
       }
-      const int i = itr->s[ilvl].i;
+      int i = itr->s[ilvl].i;
       assert(p->ptr[i] == lnode);
       if (i > 0) {
         unrelative(p->key[i - 1].pos, &intkey.pos);
       }
+
+      if (p != cur && start_id) {
+        if (intersection_has(&p->ptr[0]->intersect, start_id)) {
+          // if not the first time, we need to undo the addition in the
+          // previous step (`intersect_node` just below)
+          int last = (lnode != x) ? 1 : 0;
+          for (int k = 0; k < p->n + last; k++) {  // one less as p->ptr[n] is the last
+            unintersect_node(b, p->ptr[k], start_id, true);
+          }
+          intersect_node(b, p, start_id);
+          did_bubble = true;
+        }
+      }
+
       lnode = p;
       ilvl--;
     } while (lnode != cur);
 
-    mtkey_t deleted = cur->key[curi];
+    MTKey deleted = cur->key[curi];
     cur->key[curi] = intkey;
     refkey(b, cur, curi);
+    // if `did_bubble` then we already added `start_id` to some parent
+    if (mt_end(cur->key[curi]) && !did_bubble) {
+      uint64_t pi = pseudo_index(x, 0);  // note: sloppy pseudo-index
+      uint64_t pi_start = pseudo_index_for_id(b, start_id, true);
+      if (pi_start > 0 && pi_start < pi) {
+        intersect_node(b, x, start_id);
+      }
+    }
+
     relative(intkey.pos, &deleted.pos);
-    mtnode_t *y = cur->ptr[curi + 1];
+    MTNode *y = cur->ptr[curi + 1];
     if (deleted.pos.row || deleted.pos.col) {
       while (y) {
         for (int k = 0; k < y->n; k++) {
@@ -358,46 +583,48 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
     itr->i--;
   }
 
-  b->n_keys--;
-  pmap_del(uint64_t)(b->id2node, id, NULL);
-
   // 5.
   bool itr_dirty = false;
   int rlvl = itr->lvl - 1;
   int *lasti = &itr->i;
+  MTPos ppos = itr->pos;
   while (x != b->root) {
     assert(rlvl >= 0);
-    mtnode_t *p = x->parent;
+    MTNode *p = x->parent;
     if (x->n >= T - 1) {
       // we are done, if this node is fine the rest of the tree will be
       break;
     }
     int pi = itr->s[rlvl].i;
     assert(p->ptr[pi] == x);
+    if (pi > 0) {
+      ppos.row -= p->key[pi - 1].pos.row;
+      ppos.col = itr->s[rlvl].oldcol;
+    }
+    // ppos is now the pos of p
+
     if (pi > 0 && p->ptr[pi - 1]->n > T - 1) {
       *lasti += 1;
       itr_dirty = true;
       // steal one key from the left neighbour
-      pivot_right(b, p, pi - 1);
+      pivot_right(b, ppos, p, pi - 1);
       break;
     } else if (pi < p->n && p->ptr[pi + 1]->n > T - 1) {
       // steal one key from right neighbour
-      pivot_left(b, p, pi);
+      pivot_left(b, ppos, p, pi);
       break;
     } else if (pi > 0) {
-      // fprintf(stderr, "LEFT ");
       assert(p->ptr[pi - 1]->n == T - 1);
       // merge with left neighbour
       *lasti += T;
       x = merge_node(b, p, pi - 1);
       if (lasti == &itr->i) {
         // TRICKY: we merged the node the iterator was on
-        itr->node = x;
+        itr->x = x;
       }
       itr->s[rlvl].i--;
       itr_dirty = true;
     } else {
-      // fprintf(stderr, "RIGHT ");
       assert(pi < p->n && p->ptr[pi + 1]->n == T - 1);
       merge_node(b, p, pi);
       // no iter adjustment needed
@@ -414,18 +641,18 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
       itr->lvl--;
     }
     if (b->root->level) {
-      mtnode_t *oldroot = b->root;
+      MTNode *oldroot = b->root;
       b->root = b->root->ptr[0];
       b->root->parent = NULL;
-      xfree(oldroot);
+      marktree_free_node(b, oldroot);
     } else {
       // no items, nothing for iterator to point to
       // not strictly needed, should handle delete right-most mark anyway
-      itr->node = NULL;
+      itr->x = NULL;
     }
   }
 
-  if (itr->node && itr_dirty) {
+  if (itr->x && itr_dirty) {
     marktree_itr_fix_pos(b, itr);
   }
 
@@ -441,10 +668,10 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
     marktree_itr_next(b, itr);
     marktree_itr_next(b, itr);
   } else {
-    if (itr->node && itr->i >= itr->node->n) {
+    if (itr->x && itr->i >= itr->x->n) {
       // we deleted the last key of a leaf node
       // go to the inner key after that.
-      assert(itr->node->level == 0);
+      assert(itr->x->level == 0);
       marktree_itr_next(b, itr);
     }
   }
@@ -452,9 +679,229 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
   return other;
 }
 
-static mtnode_t *merge_node(MarkTree *b, mtnode_t *p, int i)
+/// similar to intersect_common but modify x and y in place to retain
+/// only the items which are NOT in common
+static void intersect_merge(Intersection *restrict m, Intersection *restrict x,
+                            Intersection *restrict y)
 {
-  mtnode_t *x = p->ptr[i], *y = p->ptr[i + 1];
+  size_t xi = 0, yi = 0;
+  size_t xn = 0, yn = 0;
+  while (xi < kv_size(*x) && yi < kv_size(*y)) {
+    if (kv_A(*x, xi) == kv_A(*y, yi)) {
+      // TODO(bfredl): kvi_pushp is actually quite complex, break out kvi_resize() to a function?
+      kvi_push(*m, kv_A(*x, xi));
+      xi++;
+      yi++;
+    } else if (kv_A(*x, xi) < kv_A(*y, yi)) {
+      kv_A(*x, xn++) = kv_A(*x, xi++);
+    } else {
+      kv_A(*y, yn++) = kv_A(*y, yi++);
+    }
+  }
+
+  if (xi < kv_size(*x)) {
+    memmove(&kv_A(*x, xn), &kv_A(*x, xi), sizeof(kv_A(*x, xn)) * (kv_size(*x) - xi));
+    xn += kv_size(*x) - xi;
+  }
+  if (yi < kv_size(*y)) {
+    memmove(&kv_A(*y, yn), &kv_A(*y, yi), sizeof(kv_A(*y, yn)) * (kv_size(*y) - yi));
+    yn += kv_size(*y) - yi;
+  }
+
+  kv_size(*x) = xn;
+  kv_size(*y) = yn;
+}
+
+// w used to be a child of x but it is now a child of y, adjust intersections accordingly
+// @param[out] d are intersections which should be added to the old children of y
+static void intersect_mov(Intersection *restrict x, Intersection *restrict y,
+                          Intersection *restrict w, Intersection *restrict d)
+{
+  size_t wi = 0, yi = 0;
+  size_t wn = 0, yn = 0;
+  size_t xi = 0;
+  while (wi < kv_size(*w) || xi < kv_size(*x)) {
+    if (wi < kv_size(*w) && (xi >= kv_size(*x) || kv_A(*x, xi) >= kv_A(*w, wi))) {
+      if (xi < kv_size(*x) && kv_A(*x, xi) == kv_A(*w, wi)) {
+        xi++;
+      }
+      // now w < x strictly
+      while (yi < kv_size(*y) && kv_A(*y, yi) < kv_A(*w, wi)) {
+        kvi_push(*d, kv_A(*y, yi));
+        yi++;
+      }
+      if (yi < kv_size(*y) && kv_A(*y, yi) == kv_A(*w, wi)) {
+        kv_A(*y, yn++) = kv_A(*y, yi++);
+        wi++;
+      } else {
+        kv_A(*w, wn++) = kv_A(*w, wi++);
+      }
+    } else {
+      // x < w strictly
+      while (yi < kv_size(*y) && kv_A(*y, yi) < kv_A(*x, xi)) {
+        kvi_push(*d, kv_A(*y, yi));
+        yi++;
+      }
+      if (yi < kv_size(*y) && kv_A(*y, yi) == kv_A(*x, xi)) {
+        kv_A(*y, yn++) = kv_A(*y, yi++);
+        xi++;
+      } else {
+        // add kv_A(x, xi) at kv_A(w, wn), pushing up wi if wi == wn
+        if (wi == wn) {
+          size_t n = kv_size(*w) - wn;
+          kvi_pushp(*w);
+          if (n > 0) {
+            memmove(&kv_A(*w, wn + 1), &kv_A(*w, wn), n * sizeof(kv_A(*w, 0)));
+          }
+          kv_A(*w, wi) = kv_A(*x, xi);
+          wn++;
+          wi++;  // no need to consider the added element again
+        } else {
+          assert(wn < wi);
+          kv_A(*w, wn++) = kv_A(*x, xi);
+        }
+        xi++;
+      }
+    }
+  }
+  if (yi < kv_size(*y)) {
+    // move remaining items to d
+    size_t n = kv_size(*y) - yi;  // at least one
+    kvi_ensure_more_space(*d, n);
+    memcpy(&kv_A(*d, kv_size(*d)), &kv_A(*y, yi), n * sizeof(kv_A(*d, 0)));
+    kv_size(*d) += n;
+  }
+  kv_size(*w) = wn;
+  kv_size(*y) = yn;
+}
+
+bool intersect_mov_test(uint64_t *x, size_t nx, uint64_t *y, size_t ny, uint64_t *win, size_t nwin,
+                        uint64_t *wout, size_t *nwout, uint64_t *dout, size_t *ndout)
+{
+  // x is immutable in the context of intersect_mov. y might shrink, but we
+  // don't care about it (we get it the deleted ones in d)
+  Intersection xi = { .items = x, .size = nx };
+  Intersection yi = { .items = y, .size = ny };
+
+  Intersection w;
+  kvi_init(w);
+  for (size_t i = 0; i < nwin; i++) {
+    kvi_push(w, win[i]);
+  }
+  Intersection d;
+  kvi_init(d);
+
+  intersect_mov(&xi, &yi, &w, &d);
+
+  if (w.size > *nwout || d.size > *ndout) {
+    return false;
+  }
+
+  memcpy(wout, w.items, sizeof(w.items[0]) * w.size);
+  *nwout = w.size;
+
+  memcpy(dout, d.items, sizeof(d.items[0]) * d.size);
+  *ndout = d.size;
+
+  return true;
+}
+
+/// intersection: i = x & y
+static void intersect_common(Intersection *i, Intersection *x, Intersection *y)
+{
+  size_t xi = 0, yi = 0;
+  while (xi < kv_size(*x) && yi < kv_size(*y)) {
+    if (kv_A(*x, xi) == kv_A(*y, yi)) {
+      kvi_push(*i, kv_A(*x, xi));
+      xi++;
+      yi++;
+    } else if (kv_A(*x, xi) < kv_A(*y, yi)) {
+      xi++;
+    } else {
+      yi++;
+    }
+  }
+}
+
+// inplace union: x |= y
+static void intersect_add(Intersection *x, Intersection *y)
+{
+  size_t xi = 0, yi = 0;
+  while (xi < kv_size(*x) && yi < kv_size(*y)) {
+    if (kv_A(*x, xi) == kv_A(*y, yi)) {
+      xi++;
+      yi++;
+    } else if (kv_A(*y, yi) < kv_A(*x, xi)) {
+      size_t n = kv_size(*x) - xi;  // at least one
+      kvi_pushp(*x);
+      memmove(&kv_A(*x, xi + 1), &kv_A(*x, xi), n * sizeof(kv_A(*x, 0)));
+      kv_A(*x, xi) = kv_A(*y, yi);
+      xi++;  // newly added element
+      yi++;
+    } else {
+      xi++;
+    }
+  }
+  if (yi < kv_size(*y)) {
+    size_t n = kv_size(*y) - yi;  // at least one
+    kvi_ensure_more_space(*x, n);
+    memcpy(&kv_A(*x, kv_size(*x)), &kv_A(*y, yi), n * sizeof(kv_A(*x, 0)));
+    kv_size(*x) += n;
+  }
+}
+
+// inplace assymetric difference: x &= ~y
+static void intersect_sub(Intersection *restrict x, Intersection *restrict y)
+{
+  size_t xi = 0, yi = 0;
+  size_t xn = 0;
+  while (xi < kv_size(*x) && yi < kv_size(*y)) {
+    if (kv_A(*x, xi) == kv_A(*y, yi)) {
+      xi++;
+      yi++;
+    } else if (kv_A(*x, xi) < kv_A(*y, yi)) {
+      kv_A(*x, xn++) = kv_A(*x, xi++);
+    } else {
+      yi++;
+    }
+  }
+  if (xi < kv_size(*x)) {
+    size_t n = kv_size(*x) - xi;
+    if (xn < xi) {  // otherwise xn == xi
+      memmove(&kv_A(*x, xn), &kv_A(*x, xi), n * sizeof(kv_A(*x, 0)));
+    }
+    xn += n;
+  }
+  kv_size(*x) = xn;
+}
+
+/// x is a node which shrunk, or the half of a split
+///
+/// this means that intervals which previously intersected all the (current)
+/// child nodes, now instead intersects `x` itself.
+static void bubble_up(MTNode *x)
+{
+  Intersection xi;
+  kvi_init(xi);
+  // due to invariants, the largest subset of _all_ subnodes is the intersection
+  // between the first and the last
+  intersect_common(&xi, &x->ptr[0]->intersect, &x->ptr[x->n]->intersect);
+  if (kv_size(xi)) {
+    for (int i = 0; i < x->n + 1; i++) {
+      intersect_sub(&x->ptr[i]->intersect, &xi);
+    }
+    intersect_add(&x->intersect, &xi);
+  }
+  kvi_destroy(xi);
+}
+
+static MTNode *merge_node(MarkTree *b, MTNode *p, int i)
+{
+  MTNode *x = p->ptr[i], *y = p->ptr[i + 1];
+  Intersection m;
+  kvi_init(m);
+
+  intersect_merge(&m, &x->intersect, &y->intersect);
 
   x->key[x->n] = p->key[i];
   refkey(b, x, x->n);
@@ -462,35 +909,78 @@ static mtnode_t *merge_node(MarkTree *b, mtnode_t *p, int i)
     relative(p->key[i - 1].pos, &x->key[x->n].pos);
   }
 
-  memmove(&x->key[x->n + 1], y->key, (size_t)y->n * sizeof(mtkey_t));
+  memmove(&x->key[x->n + 1], y->key, (size_t)y->n * sizeof(MTKey));
   for (int k = 0; k < y->n; k++) {
     refkey(b, x, x->n + 1 + k);
     unrelative(x->key[x->n].pos, &x->key[x->n + 1 + k].pos);
   }
   if (x->level) {
-    memmove(&x->ptr[x->n + 1], y->ptr, ((size_t)y->n + 1) * sizeof(mtnode_t *));
-    for (int k = 0; k < y->n + 1; k++) {
-      x->ptr[x->n + k + 1]->parent = x;
+    // bubble down: ranges that intersected old-x but not old-y or vice versa
+    // must be moved to their respective children
+    memmove(&x->ptr[x->n + 1], y->ptr, ((size_t)y->n + 1) * sizeof(MTNode *));
+    for (int k = 0; k < x->n + 1; k++) {
+      // TODO(bfredl): dedicated impl for "Z |= Y"
+      for (size_t idx = 0; idx < kv_size(x->intersect); idx++) {
+        intersect_node(b, x->ptr[k], kv_A(x->intersect, idx));
+      }
+    }
+    for (int ky = 0; ky < y->n + 1; ky++) {
+      int k = x->n + ky + 1;
+      // nodes that used to be in y, now the second half of x
+      x->ptr[k]->parent = x;
+      x->ptr[k]->p_idx = (int16_t)k;
+      // TODO(bfredl): dedicated impl for "Z |= X"
+      for (size_t idx = 0; idx < kv_size(y->intersect); idx++) {
+        intersect_node(b, x->ptr[k], kv_A(y->intersect, idx));
+      }
     }
   }
   x->n += y->n + 1;
-  memmove(&p->key[i], &p->key[i + 1], (size_t)(p->n - i - 1) * sizeof(mtkey_t));
+  memmove(&p->key[i], &p->key[i + 1], (size_t)(p->n - i - 1) * sizeof(MTKey));
   memmove(&p->ptr[i + 1], &p->ptr[i + 2],
-          (size_t)(p->n - i - 1) * sizeof(mtkey_t *));
+          (size_t)(p->n - i - 1) * sizeof(MTKey *));
+  for (int j = i + 1; j < p->n; j++) {  // note: one has been deleted
+    p->ptr[j]->p_idx = (int16_t)j;
+  }
   p->n--;
-  xfree(y);
-  b->n_nodes--;
+  marktree_free_node(b, y);
+
+  kvi_destroy(x->intersect);
+
+  // move of a kvec_withinit_t, messy!
+  // TODO(bfredl): special case version of intersect_merge(x_out, x_in_m_out, y) to avoid this
+  kvi_move(&x->intersect, &m);
+
   return x;
 }
 
+/// @param dest is overwritten (assumed to already been freed/moved)
+/// @param src consumed (don't free or use)
+void kvi_move(Intersection *dest, Intersection *src)
+{
+  dest->size = src->size;
+  dest->capacity = src->capacity;
+  if (src->items == src->init_array) {
+    memcpy(dest->init_array, src->init_array, src->size * sizeof(*src->init_array));
+    dest->items = dest->init_array;
+  } else {
+    dest->items = src->items;
+  }
+}
+
 // TODO(bfredl): as a potential "micro" optimization, pivoting should balance
 // the two nodes instead of stealing just one key
-static void pivot_right(MarkTree *b, mtnode_t *p, int i)
+// x_pos is the absolute position of the key just before x (or a dummy key strictly less than any
+// key inside x, if x is the first leaf)
+static void pivot_right(MarkTree *b, MTPos p_pos, MTNode *p, const int i)
 {
-  mtnode_t *x = p->ptr[i], *y = p->ptr[i + 1];
-  memmove(&y->key[1], y->key, (size_t)y->n * sizeof(mtkey_t));
+  MTNode *x = p->ptr[i], *y = p->ptr[i + 1];
+  memmove(&y->key[1], y->key, (size_t)y->n * sizeof(MTKey));
   if (y->level) {
-    memmove(&y->ptr[1], y->ptr, ((size_t)y->n + 1) * sizeof(mtnode_t *));
+    memmove(&y->ptr[1], y->ptr, ((size_t)y->n + 1) * sizeof(MTNode *));
+    for (int j = 1; j < y->n + 2; j++) {
+      y->ptr[j]->p_idx = (int16_t)j;
+    }
   }
   y->key[0] = p->key[i];
   refkey(b, y, 0);
@@ -499,6 +989,7 @@ static void pivot_right(MarkTree *b, mtnode_t *p, int i)
   if (x->level) {
     y->ptr[0] = x->ptr[x->n];
     y->ptr[0]->parent = y;
+    y->ptr[0]->p_idx = 0;
   }
   x->n--;
   y->n++;
@@ -509,11 +1000,46 @@ static void pivot_right(MarkTree *b, mtnode_t *p, int i)
   for (int k = 1; k < y->n; k++) {
     unrelative(y->key[0].pos, &y->key[k].pos);
   }
+
+  // repair intersections of x
+  if (x->level) {
+    // handle y and first new y->ptr[0]
+    Intersection d;
+    kvi_init(d);
+    // y->ptr[0] was moved from x to y
+    // adjust y->ptr[0] for a difference between the parents
+    // in addition, this might cause some intersection of the old y
+    // to bubble down to the old children of y (if y->ptr[0] wasn't intersected)
+    intersect_mov(&x->intersect, &y->intersect, &y->ptr[0]->intersect, &d);
+    if (kv_size(d)) {
+      for (int yi = 1; yi < y->n + 1; yi++) {
+        intersect_add(&y->ptr[yi]->intersect, &d);
+      }
+    }
+    kvi_destroy(d);
+
+    bubble_up(x);
+  } else {
+    // if the last element of x used to be an end node, check if it now covers all of x
+    if (mt_end(p->key[i])) {
+      uint64_t pi = pseudo_index(x, 0);  // note: sloppy pseudo-index
+      uint64_t start_id = mt_lookup_key_side(p->key[i], false);
+      uint64_t pi_start = pseudo_index_for_id(b, start_id, true);
+      if (pi_start > 0 && pi_start < pi) {
+        intersect_node(b, x, start_id);
+      }
+    }
+
+    if (mt_start(y->key[0])) {
+      // no need for a check, just delet it if it was there
+      unintersect_node(b, y, mt_lookup_key(y->key[0]), false);
+    }
+  }
 }
 
-static void pivot_left(MarkTree *b, mtnode_t *p, int i)
+static void pivot_left(MarkTree *b, MTPos p_pos, MTNode *p, int i)
 {
-  mtnode_t *x = p->ptr[i], *y = p->ptr[i + 1];
+  MTNode *x = p->ptr[i], *y = p->ptr[i + 1];
 
   // reverse from how we "always" do it. but pivot_left
   // is just the inverse of pivot_right, so reverse it literally.
@@ -532,40 +1058,88 @@ static void pivot_left(MarkTree *b, mtnode_t *p, int i)
   if (x->level) {
     x->ptr[x->n + 1] = y->ptr[0];
     x->ptr[x->n + 1]->parent = x;
+    x->ptr[x->n + 1]->p_idx = (int16_t)(x->n + 1);
   }
-  memmove(y->key, &y->key[1], (size_t)(y->n - 1) * sizeof(mtkey_t));
+  memmove(y->key, &y->key[1], (size_t)(y->n - 1) * sizeof(MTKey));
   if (y->level) {
-    memmove(y->ptr, &y->ptr[1], (size_t)y->n * sizeof(mtnode_t *));
+    memmove(y->ptr, &y->ptr[1], (size_t)y->n * sizeof(MTNode *));
+    for (int j = 0; j < y->n; j++) {  // note: last item deleted
+      y->ptr[j]->p_idx = (int16_t)j;
+    }
   }
   x->n++;
   y->n--;
+
+  // repair intersections of x,y
+  if (x->level) {
+    // handle y and first new y->ptr[0]
+    Intersection d;
+    kvi_init(d);
+    // x->ptr[x->n] was moved from y to x
+    // adjust x->ptr[x->n] for a difference between the parents
+    // in addition, this might cause some intersection of the old x
+    // to bubble down to the old children of x (if x->ptr[n] wasn't intersected)
+    intersect_mov(&y->intersect, &x->intersect, &x->ptr[x->n]->intersect, &d);
+    if (kv_size(d)) {
+      for (int xi = 0; xi < x->n; xi++) {  // ptr[x->n| deliberately skipped
+        intersect_add(&x->ptr[xi]->intersect, &d);
+      }
+    }
+    kvi_destroy(d);
+
+    bubble_up(y);
+  } else {
+    // if the first element of y used to be an start node, check if it now covers all of y
+    if (mt_start(p->key[i])) {
+      uint64_t pi = pseudo_index(y, 0);  // note: sloppy pseudo-index
+
+      uint64_t end_id = mt_lookup_key_side(p->key[i], true);
+      uint64_t pi_end = pseudo_index_for_id(b, end_id, true);
+
+      if (pi_end > pi) {
+        intersect_node(b, y, mt_lookup_key(p->key[i]));
+      }
+    }
+
+    if (mt_end(x->key[x->n - 1])) {
+      // no need for a check, just delet it if it was there
+      unintersect_node(b, x, mt_lookup_key_side(x->key[x->n - 1], false), false);
+    }
+  }
 }
 
 /// frees all mem, resets tree to valid empty state
 void marktree_clear(MarkTree *b)
 {
   if (b->root) {
-    marktree_free_node(b->root);
+    marktree_free_subtree(b, b->root);
     b->root = NULL;
   }
   map_destroy(uint64_t, b->id2node);
   *b->id2node = (PMap(uint64_t)) MAP_INIT;
   b->n_keys = 0;
-  b->n_nodes = 0;
+  assert(b->n_nodes == 0);
 }
 
-void marktree_free_node(mtnode_t *x)
+void marktree_free_subtree(MarkTree *b, MTNode *x)
 {
   if (x->level) {
     for (int i = 0; i < x->n + 1; i++) {
-      marktree_free_node(x->ptr[i]);
+      marktree_free_subtree(b, x->ptr[i]);
     }
   }
+  marktree_free_node(b, x);
+}
+
+static void marktree_free_node(MarkTree *b, MTNode *x)
+{
+  kvi_destroy(x->intersect);
   xfree(x);
+  b->n_nodes--;
 }
 
 /// NB: caller must check not pair!
-void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, mtkey_t key)
+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
@@ -578,49 +1152,108 @@ void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, mtkey_
   rawkey(itr).priority = key.priority;
 }
 
+/// @param itr iterator is invalid after call
 void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col)
 {
-  mtkey_t key = rawkey(itr);
-  // TODO(bfredl): optimize when moving a mark within a leaf without moving it
-  // across neighbours!
-  marktree_del_itr(b, itr, false);
-  key.pos = (mtpos_t){ row, col };
+  MTKey key = rawkey(itr);
+  MTNode *x = itr->x;
+  if (!x->level) {
+    bool internal = false;
+    MTPos newpos = MTPos(row, col);
+    if (x->parent != NULL) {
+      // strictly _after_ key before `x`
+      // (not optimal when x is very first leaf of the entire tree, but that's fine)
+      if (pos_less(itr->pos, newpos)) {
+        relative(itr->pos, &newpos);
+
+        // strictly before the end of x. (this could be made sharper by
+        // finding the internal key just after x, but meh)
+        if (pos_less(newpos, x->key[x->n - 1].pos)) {
+          internal = true;
+        }
+      }
+    } else {
+      // tree is one node. newpos thus is already "relative" itr->pos
+      internal = true;
+    }
+
+    if (internal) {
+      key.pos = newpos;
+      bool match;
+      // tricky: could minimize movement in either direction better
+      int new_i = marktree_getp_aux(x, key, &match);
+      if (!match) {
+        new_i++;
+      }
+      if (new_i == itr->i || key_cmp(key, x->key[new_i]) == 0) {
+        x->key[itr->i].pos = newpos;
+      } else if (new_i < itr->i) {
+        memmove(&x->key[new_i + 1], &x->key[new_i], sizeof(MTKey) * (size_t)(itr->i - new_i));
+        x->key[new_i] = key;
+      } else if (new_i > itr->i) {
+        memmove(&x->key[itr->i], &x->key[itr->i + 1], sizeof(MTKey) * (size_t)(new_i - itr->i));
+        x->key[new_i] = key;
+      }
+      return;
+    }
+  }
+  uint64_t other = marktree_del_itr(b, itr, false);
+  key.pos = (MTPos){ row, col };
 
   marktree_put_key(b, key);
-  itr->node = NULL;  // itr might become invalid by put
+
+  if (other) {
+    marktree_restore_pair(b, key);
+  }
+  itr->x = NULL;  // itr might become invalid by put
+}
+
+void marktree_restore_pair(MarkTree *b, MTKey key)
+{
+  MarkTreeIter itr[1];
+  MarkTreeIter end_itr[1];
+  marktree_lookup(b, mt_lookup_key_side(key, false), itr);
+  marktree_lookup(b, mt_lookup_key_side(key, true), end_itr);
+  if (!itr->x || !end_itr->x) {
+    // this could happen if the other end is waiting to be restored later
+    // this function will be called again for the other end.
+    return;
+  }
+  rawkey(itr).flags &= (uint16_t) ~MT_FLAG_ORPHANED;
+  rawkey(end_itr).flags &= (uint16_t) ~MT_FLAG_ORPHANED;
+
+  marktree_intersect_pair(b, mt_lookup_key_side(key, false), itr, end_itr, false);
 }
 
 // itr functions
 
-// TODO(bfredl): static inline?
 bool marktree_itr_get(MarkTree *b, int32_t row, int col, MarkTreeIter *itr)
 {
-  return marktree_itr_get_ext(b, (mtpos_t){ row, col },
-                              itr, false, false, NULL);
+  return marktree_itr_get_ext(b, MTPos(row, col), itr, false, false, NULL);
 }
 
-bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last, bool gravity,
-                          mtpos_t *oldbase)
+bool marktree_itr_get_ext(MarkTree *b, MTPos p, MarkTreeIter *itr, bool last, bool gravity,
+                          MTPos *oldbase)
 {
   if (b->n_keys == 0) {
-    itr->node = NULL;
+    itr->x = NULL;
     return false;
   }
 
-  mtkey_t k = { .pos = p, .flags = gravity ? MT_FLAG_RIGHT_GRAVITY : 0 };
+  MTKey k = { .pos = p, .flags = gravity ? MT_FLAG_RIGHT_GRAVITY : 0 };
   if (last && !gravity) {
     k.flags = MT_FLAG_LAST;
   }
-  itr->pos = (mtpos_t){ 0, 0 };
-  itr->node = b->root;
+  itr->pos = (MTPos){ 0, 0 };
+  itr->x = b->root;
   itr->lvl = 0;
   if (oldbase) {
     oldbase[itr->lvl] = itr->pos;
   }
   while (true) {
-    itr->i = marktree_getp_aux(itr->node, k, 0) + 1;
+    itr->i = marktree_getp_aux(itr->x, k, 0) + 1;
 
-    if (itr->node->level == 0) {
+    if (itr->x->level == 0) {
       break;
     }
 
@@ -628,10 +1261,10 @@ bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last,
     itr->s[itr->lvl].oldcol = itr->pos.col;
 
     if (itr->i > 0) {
-      compose(&itr->pos, itr->node->key[itr->i - 1].pos);
-      relative(itr->node->key[itr->i - 1].pos, &k.pos);
+      compose(&itr->pos, itr->x->key[itr->i - 1].pos);
+      relative(itr->x->key[itr->i - 1].pos, &k.pos);
     }
-    itr->node = itr->node->ptr[itr->i];
+    itr->x = itr->x->ptr[itr->i];
     itr->lvl++;
     if (oldbase) {
       oldbase[itr->lvl] = itr->pos;
@@ -640,7 +1273,7 @@ bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last,
 
   if (last) {
     return marktree_itr_prev(b, itr);
-  } else if (itr->i >= itr->node->n) {
+  } else if (itr->i >= itr->x->n) {
     return marktree_itr_next(b, itr);
   }
   return true;
@@ -648,19 +1281,20 @@ bool marktree_itr_get_ext(MarkTree *b, mtpos_t p, MarkTreeIter *itr, bool last,
 
 bool marktree_itr_first(MarkTree *b, MarkTreeIter *itr)
 {
-  itr->node = b->root;
   if (b->n_keys == 0) {
+    itr->x = NULL;
     return false;
   }
 
+  itr->x = b->root;
   itr->i = 0;
   itr->lvl = 0;
-  itr->pos = (mtpos_t){ 0, 0 };
-  while (itr->node->level > 0) {
+  itr->pos = MTPos(0, 0);
+  while (itr->x->level > 0) {
     itr->s[itr->lvl].i = 0;
     itr->s[itr->lvl].oldcol = 0;
     itr->lvl++;
-    itr->node = itr->node->ptr[0];
+    itr->x = itr->x->ptr[0];
   }
   return true;
 }
@@ -669,16 +1303,16 @@ bool marktree_itr_first(MarkTree *b, MarkTreeIter *itr)
 int marktree_itr_last(MarkTree *b, MarkTreeIter *itr)
 {
   if (b->n_keys == 0) {
-    itr->node = NULL;
+    itr->x = NULL;
     return false;
   }
-  itr->pos = (mtpos_t){ 0, 0 };
-  itr->node = b->root;
+  itr->pos = MTPos(0, 0);
+  itr->x = b->root;
   itr->lvl = 0;
   while (true) {
-    itr->i = itr->node->n;
+    itr->i = itr->x->n;
 
-    if (itr->node->level == 0) {
+    if (itr->x->level == 0) {
       break;
     }
 
@@ -686,63 +1320,71 @@ int marktree_itr_last(MarkTree *b, MarkTreeIter *itr)
     itr->s[itr->lvl].oldcol = itr->pos.col;
 
     assert(itr->i > 0);
-    compose(&itr->pos, itr->node->key[itr->i - 1].pos);
+    compose(&itr->pos, itr->x->key[itr->i - 1].pos);
 
-    itr->node = itr->node->ptr[itr->i];
+    itr->x = itr->x->ptr[itr->i];
     itr->lvl++;
   }
   itr->i--;
   return true;
 }
 
-// TODO(bfredl): static inline
 bool marktree_itr_next(MarkTree *b, MarkTreeIter *itr)
 {
-  return marktree_itr_next_skip(b, itr, false, NULL);
+  return marktree_itr_next_skip(b, itr, false, false, NULL);
 }
 
-static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, mtpos_t oldbase[])
+static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, bool preload,
+                                   MTPos oldbase[])
 {
-  if (!itr->node) {
+  if (!itr->x) {
     return false;
   }
   itr->i++;
-  if (itr->node->level == 0 || skip) {
-    if (itr->i < itr->node->n) {
+  if (itr->x->level == 0 || skip) {
+    if (preload && itr->x->level == 0 && skip) {
+      // skip rest of this leaf node
+      itr->i = itr->x->n;
+    } else if (itr->i < itr->x->n) {
       // TODO(bfredl): this is the common case,
       // and could be handled by inline wrapper
       return true;
     }
     // we ran out of non-internal keys. Go up until we find an internal key
-    while (itr->i >= itr->node->n) {
-      itr->node = itr->node->parent;
-      if (itr->node == NULL) {
+    while (itr->i >= itr->x->n) {
+      itr->x = itr->x->parent;
+      if (itr->x == NULL) {
         return false;
       }
       itr->lvl--;
       itr->i = itr->s[itr->lvl].i;
       if (itr->i > 0) {
-        itr->pos.row -= itr->node->key[itr->i - 1].pos.row;
+        itr->pos.row -= itr->x->key[itr->i - 1].pos.row;
         itr->pos.col = itr->s[itr->lvl].oldcol;
       }
     }
   } else {
     // we stood at an "internal" key. Go down to the first non-internal
     // key after it.
-    while (itr->node->level > 0) {
+    while (itr->x->level > 0) {
       // internal key, there is always a child after
       if (itr->i > 0) {
         itr->s[itr->lvl].oldcol = itr->pos.col;
-        compose(&itr->pos, itr->node->key[itr->i - 1].pos);
+        compose(&itr->pos, itr->x->key[itr->i - 1].pos);
       }
       if (oldbase && itr->i == 0) {
         oldbase[itr->lvl + 1] = oldbase[itr->lvl];
       }
       itr->s[itr->lvl].i = itr->i;
-      assert(itr->node->ptr[itr->i]->parent == itr->node);
-      itr->node = itr->node->ptr[itr->i];
-      itr->i = 0;
+      assert(itr->x->ptr[itr->i]->parent == itr->x);
       itr->lvl++;
+      itr->x = itr->x->ptr[itr->i];
+      if (preload && itr->x->level) {
+        itr->i = -1;
+        break;
+      } else {
+        itr->i = 0;
+      }
     }
   }
   return true;
@@ -750,10 +1392,10 @@ static bool marktree_itr_next_skip(MarkTree *b, MarkTreeIter *itr, bool skip, mt
 
 bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr)
 {
-  if (!itr->node) {
+  if (!itr->x) {
     return false;
   }
-  if (itr->node->level == 0) {
+  if (itr->x->level == 0) {
     itr->i--;
     if (itr->i >= 0) {
       // TODO(bfredl): this is the common case,
@@ -762,30 +1404,30 @@ bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr)
     }
     // we ran out of non-internal keys. Go up until we find a non-internal key
     while (itr->i < 0) {
-      itr->node = itr->node->parent;
-      if (itr->node == NULL) {
+      itr->x = itr->x->parent;
+      if (itr->x == NULL) {
         return false;
       }
       itr->lvl--;
       itr->i = itr->s[itr->lvl].i - 1;
       if (itr->i >= 0) {
-        itr->pos.row -= itr->node->key[itr->i].pos.row;
+        itr->pos.row -= itr->x->key[itr->i].pos.row;
         itr->pos.col = itr->s[itr->lvl].oldcol;
       }
     }
   } else {
     // we stood at an "internal" key. Go down to the last non-internal
     // key before it.
-    while (itr->node->level > 0) {
+    while (itr->x->level > 0) {
       // internal key, there is always a child before
       if (itr->i > 0) {
         itr->s[itr->lvl].oldcol = itr->pos.col;
-        compose(&itr->pos, itr->node->key[itr->i - 1].pos);
+        compose(&itr->pos, itr->x->key[itr->i - 1].pos);
       }
       itr->s[itr->lvl].i = itr->i;
-      assert(itr->node->ptr[itr->i]->parent == itr->node);
-      itr->node = itr->node->ptr[itr->i];
-      itr->i = itr->node->n;
+      assert(itr->x->ptr[itr->i]->parent == itr->x);
+      itr->x = itr->x->ptr[itr->i];
+      itr->i = itr->x->n;
       itr->lvl++;
     }
     itr->i--;
@@ -793,33 +1435,22 @@ bool marktree_itr_prev(MarkTree *b, MarkTreeIter *itr)
   return true;
 }
 
-void marktree_itr_rewind(MarkTree *b, MarkTreeIter *itr)
-{
-  if (!itr->node) {
-    return;
-  }
-  if (itr->node->level) {
-    marktree_itr_prev(b, itr);
-  }
-  itr->i = 0;
-}
-
 bool marktree_itr_node_done(MarkTreeIter *itr)
 {
-  return !itr->node || itr->i == itr->node->n - 1;
+  return !itr->x || itr->i == itr->x->n - 1;
 }
 
-mtpos_t marktree_itr_pos(MarkTreeIter *itr)
+MTPos marktree_itr_pos(MarkTreeIter *itr)
 {
-  mtpos_t pos = rawkey(itr).pos;
+  MTPos pos = rawkey(itr).pos;
   unrelative(itr->pos, &pos);
   return pos;
 }
 
-mtkey_t marktree_itr_current(MarkTreeIter *itr)
+MTKey marktree_itr_current(MarkTreeIter *itr)
 {
-  if (itr->node) {
-    mtkey_t key = rawkey(itr);
+  if (itr->x) {
+    MTKey key = rawkey(itr);
     key.pos = marktree_itr_pos(itr);
     return key;
   }
@@ -831,47 +1462,198 @@ static bool itr_eq(MarkTreeIter *itr1, MarkTreeIter *itr2)
   return (&rawkey(itr1) == &rawkey(itr2));
 }
 
-static void itr_swap(MarkTreeIter *itr1, MarkTreeIter *itr2)
+/// Get all marks which overlaps the position (row,col)
+///
+/// After calling this function, use marktree_itr_step_overlap to step through
+/// one overlapping mark at a time, until it returns false
+///
+/// NOTE: It's possible to get all marks which overlaps a region (row,col) to (row_end,col_end)
+/// To do this, first call marktree_itr_get_overlap with the start position and
+/// keep calling marktree_itr_step_overlap until it returns false.
+/// After this, as a second loop, keep calling the marktree_itr_next() until
+/// the iterator is invalid or reaches past (row_end, col_end). In this loop,
+/// consider all "start" marks (and unpaired marks if relevant), but skip over
+/// all "end" marks, using mt_end(mark).
+///
+/// @return false if we already know no marks can be found
+///               even if "true" the first call to marktree_itr_step_overlap
+///               could return false
+bool marktree_itr_get_overlap(MarkTree *b, int row, int col, MarkTreeIter *itr)
+{
+  if (b->n_keys == 0) {
+    itr->x = NULL;
+    return false;
+  }
+
+  itr->x = b->root;
+  itr->i = -1;
+  itr->lvl = 0;
+  itr->pos = MTPos(0, 0);
+  itr->intersect_pos = MTPos(row, col);
+  // intersect_pos but will be adjusted relative itr->x
+  itr->intersect_pos_x = MTPos(row, col);
+  itr->intersect_idx = 0;
+  return true;
+}
+
+static inline MTPair pair_from(MTKey start, MTKey end)
+{
+  return (MTPair){ .start = start, .end_pos = end.pos, .end_right_gravity = mt_right(end) };
+}
+
+/// Step through all overlapping pairs at a position.
+///
+/// This function must only be used with an iterator from |marktree_itr_step_overlap|
+///
+/// @return true if a valid pair was found (returned as `pair`)
+/// When all overlapping mark pairs have been found, false will be returned. `itr`
+/// is then valid as an ordinary iterator at the (row, col) position specified in
+/// marktree_itr_step_overlap
+bool marktree_itr_step_overlap(MarkTree *b, MarkTreeIter *itr, MTPair *pair)
+{
+  // phase one: we start at the root node and step inwards towards itr->intersect_pos
+  // (the position queried in marktree_itr_get_overlap)
+  //
+  // For each node (ancestor node to the node containing the sought position)
+  // we return all intersecting intervals, one at a time
+  while (itr->i == -1) {
+    if (itr->intersect_idx < kv_size(itr->x->intersect)) {
+      uint64_t id = kv_A(itr->x->intersect, itr->intersect_idx++);
+      *pair = pair_from(marktree_lookup(b, id, NULL),
+                        marktree_lookup(b, id|MARKTREE_END_FLAG, NULL));
+      return true;
+    }
+
+    if (itr->x->level == 0) {
+      itr->s[itr->lvl].i = itr->i = 0;
+      break;
+    }
+
+    MTKey k = { .pos = itr->intersect_pos_x, .flags = 0 };
+    itr->i = marktree_getp_aux(itr->x, k, 0) + 1;
+
+    itr->s[itr->lvl].i = itr->i;
+    itr->s[itr->lvl].oldcol = itr->pos.col;
+
+    if (itr->i > 0) {
+      compose(&itr->pos, itr->x->key[itr->i - 1].pos);
+      relative(itr->x->key[itr->i - 1].pos, &itr->intersect_pos_x);
+    }
+    itr->x = itr->x->ptr[itr->i];
+    itr->lvl++;
+    itr->i = -1;
+    itr->intersect_idx = 0;
+  }
+
+  // phase two: we now need to handle the node found at itr->intersect_pos
+  // first consider all start nodes in the node before this position.
+  while (itr->i < itr->x->n && pos_less(rawkey(itr).pos, itr->intersect_pos_x)) {
+    MTKey k = itr->x->key[itr->i++];
+    itr->s[itr->lvl].i = itr->i;
+    if (mt_start(k)) {
+      MTKey end = marktree_lookup(b, mt_lookup_id(k.ns, k.id, true), NULL);
+      if (pos_less(end.pos, itr->intersect_pos)) {
+        continue;
+      }
+
+      unrelative(itr->pos, &k.pos);
+      *pair = pair_from(k, end);
+      return true;  // it's a start!
+    }
+  }
+
+  // phase 2B: We also need to step to the end of this node and consider all end marks, which
+  // might end an interval overlapping itr->intersect_pos
+  while (itr->i < itr->x->n) {
+    MTKey k = itr->x->key[itr->i++];
+    if (mt_end(k)) {
+      uint64_t id = mt_lookup_id(k.ns, k.id, false);
+      if (id2node(b, id) == itr->x) {
+        continue;
+      }
+      unrelative(itr->pos, &k.pos);
+      MTKey start = marktree_lookup(b, id, NULL);
+      if (pos_less(itr->intersect_pos, start.pos)) {
+        continue;
+      }
+      *pair = pair_from(start, k);
+      return true;  // end of a range which began before us!
+    }
+  }
+
+  // when returning false, get back to the queried position, to ensure the caller
+  // can keep using it as an ordinary iterator at the queried position. The docstring
+  // for marktree_itr_get_overlap explains how this is useful.
+  itr->i = itr->s[itr->lvl].i;
+  assert(itr->i >= 0);
+  if (itr->i >= itr->x->n) {
+    marktree_itr_next(b, itr);
+  }
+
+  // either on or after the intersected position, bail out
+  return false;
+}
+
+static void swap_keys(MarkTree *b, MarkTreeIter *itr1, MarkTreeIter *itr2, DamageList *damage)
 {
-  mtkey_t key1 = rawkey(itr1);
-  mtkey_t key2 = rawkey(itr2);
+  if (itr1->x != itr2->x) {
+    if (mt_paired(rawkey(itr1))) {
+      kvi_push(*damage, ((Damage){ mt_lookup_key(rawkey(itr1)), itr1->x, itr2->x,
+                                   itr1->i, itr2->i }));
+    }
+    if (mt_paired(rawkey(itr2))) {
+      kvi_push(*damage, ((Damage){ mt_lookup_key(rawkey(itr2)), itr2->x, itr1->x,
+                                   itr2->i, itr1->i }));
+    }
+  }
+
+  MTKey key1 = rawkey(itr1);
+  MTKey key2 = rawkey(itr2);
   rawkey(itr1) = key2;
   rawkey(itr1).pos = key1.pos;
   rawkey(itr2) = key1;
   rawkey(itr2).pos = key2.pos;
+  refkey(b, itr1->x, itr1->i);
+  refkey(b, itr2->x, itr2->i);
+}
+
+static int damage_cmp(const void *s1, const void *s2)
+{
+  Damage *d1 = (Damage *)s1, *d2 = (Damage *)s2;
+  assert(d1->id != d2->id);
+  return d1->id > d2->id;
 }
 
 bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_extent_line,
                      int old_extent_col, int new_extent_line, int new_extent_col)
 {
-  mtpos_t start = { start_line, start_col };
-  mtpos_t old_extent = { old_extent_line, old_extent_col };
-  mtpos_t new_extent = { new_extent_line, new_extent_col };
+  MTPos start = { start_line, start_col };
+  MTPos old_extent = { old_extent_line, old_extent_col };
+  MTPos new_extent = { new_extent_line, new_extent_col };
 
   bool may_delete = (old_extent.row != 0 || old_extent.col != 0);
   bool same_line = old_extent.row == 0 && new_extent.row == 0;
   unrelative(start, &old_extent);
   unrelative(start, &new_extent);
-  MarkTreeIter itr[1] = { 0 };
-  MarkTreeIter enditr[1] = { 0 };
+  MarkTreeIter itr[1] = { 0 }, enditr[1] = { 0 };
 
-  mtpos_t oldbase[MT_MAX_DEPTH] = { 0 };
+  MTPos oldbase[MT_MAX_DEPTH] = { 0 };
 
   marktree_itr_get_ext(b, start, itr, false, true, oldbase);
-  if (!itr->node) {
+  if (!itr->x) {
     // den e FÄRDIG
     return false;
   }
-  mtpos_t delta = { new_extent.row - old_extent.row,
-                    new_extent.col - old_extent.col };
+  MTPos delta = { new_extent.row - old_extent.row,
+                  new_extent.col - old_extent.col };
 
   if (may_delete) {
-    mtpos_t ipos = marktree_itr_pos(itr);
+    MTPos ipos = marktree_itr_pos(itr);
     if (!pos_leq(old_extent, ipos)
         || (old_extent.row == ipos.row && old_extent.col == ipos.col
             && !mt_right(rawkey(itr)))) {
       marktree_itr_get_ext(b, old_extent, enditr, true, true, NULL);
-      assert(enditr->node);
+      assert(enditr->x);
       // "assert" (itr <= enditr)
     } else {
       may_delete = false;
@@ -880,14 +1662,16 @@ bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_ext
 
   bool past_right = false;
   bool moved = false;
+  DamageList damage;
+  kvi_init(damage);
 
   // Follow the general strategy of messing things up and fix them later
   // "oldbase" carries the information needed to calculate old position of
   // children.
   if (may_delete) {
-    while (itr->node && !past_right) {
-      mtpos_t loc_start = start;
-      mtpos_t loc_old = old_extent;
+    while (itr->x && !past_right) {
+      MTPos loc_start = start;
+      MTPos loc_old = old_extent;
       relative(itr->pos, &loc_start);
 
       relative(oldbase[itr->lvl], &loc_old);
@@ -905,9 +1689,7 @@ continue_same_node:
           marktree_itr_prev(b, enditr);
         }
         if (!mt_right(rawkey(enditr))) {
-          itr_swap(itr, enditr);
-          refkey(b, itr->node, itr->i);
-          refkey(b, enditr->node, enditr->i);
+          swap_keys(b, itr, enditr, &damage);
         } else {
           past_right = true;  // NOLINT
           (void)past_right;
@@ -921,14 +1703,14 @@ continue_same_node:
       }
 
       moved = true;
-      if (itr->node->level) {
+      if (itr->x->level) {
         oldbase[itr->lvl + 1] = rawkey(itr).pos;
         unrelative(oldbase[itr->lvl], &oldbase[itr->lvl + 1]);
         rawkey(itr).pos = loc_start;
-        marktree_itr_next_skip(b, itr, false, oldbase);
+        marktree_itr_next_skip(b, itr, false, false, oldbase);
       } else {
         rawkey(itr).pos = loc_start;
-        if (itr->i < itr->node->n - 1) {
+        if (itr->i < itr->x->n - 1) {
           itr->i++;
           if (!past_right) {
             goto continue_same_node;
@@ -938,10 +1720,10 @@ continue_same_node:
         }
       }
     }
-    while (itr->node) {
-      mtpos_t loc_new = new_extent;
+    while (itr->x) {
+      MTPos loc_new = new_extent;
       relative(itr->pos, &loc_new);
-      mtpos_t limit = old_extent;
+      MTPos limit = old_extent;
 
       relative(oldbase[itr->lvl], &limit);
 
@@ -951,16 +1733,16 @@ past_continue_same_node:
         break;
       }
 
-      mtpos_t oldpos = rawkey(itr).pos;
+      MTPos oldpos = rawkey(itr).pos;
       rawkey(itr).pos = loc_new;
       moved = true;
-      if (itr->node->level) {
+      if (itr->x->level) {
         oldbase[itr->lvl + 1] = oldpos;
         unrelative(oldbase[itr->lvl], &oldbase[itr->lvl + 1]);
 
-        marktree_itr_next_skip(b, itr, false, oldbase);
+        marktree_itr_next_skip(b, itr, false, false, oldbase);
       } else {
-        if (itr->i < itr->node->n - 1) {
+        if (itr->i < itr->x->n - 1) {
           itr->i++;
           goto past_continue_same_node;
         } else {
@@ -970,7 +1752,7 @@ past_continue_same_node:
     }
   }
 
-  while (itr->node) {
+  while (itr->x) {
     unrelative(oldbase[itr->lvl], &rawkey(itr).pos);
     int realrow = rawkey(itr).pos.row;
     assert(realrow >= old_extent.row);
@@ -978,7 +1760,6 @@ past_continue_same_node:
     if (realrow == old_extent.row) {
       if (delta.col) {
         rawkey(itr).pos.col += delta.col;
-        moved = true;
       }
     } else {
       if (same_line) {
@@ -994,22 +1775,78 @@ past_continue_same_node:
     if (done) {
       break;
     }
-    marktree_itr_next_skip(b, itr, true, NULL);
+    marktree_itr_next_skip(b, itr, true, false, NULL);
+  }
+
+  if (kv_size(damage)) {
+    // TODO(bfredl): a full sort is not really needed. we just need a "start" node to find
+    // its corresponding "end" node. Set up some dedicated hash for this later (c.f. the
+    // "grow only" variant of khash_t branch)
+    qsort((void *)&kv_A(damage, 0), kv_size(damage), sizeof(kv_A(damage, 0)),
+          damage_cmp);
+
+    for (size_t i = 0; i < kv_size(damage); i++) {
+      Damage d = kv_A(damage, i);
+      if (!(d.id & MARKTREE_END_FLAG)) {  // start
+        if (i + 1 < kv_size(damage) && kv_A(damage, i + 1).id == (d.id | MARKTREE_END_FLAG)) {
+          Damage d2 = kv_A(damage, i + 1);
+
+          // pair
+          marktree_itr_set_node(b, itr, d.old, d.old_i);
+          marktree_itr_set_node(b, enditr, d2.old, d2.old_i);
+          marktree_intersect_pair(b, d.id, itr, enditr, true);
+          marktree_itr_set_node(b, itr, d.new, d.new_i);
+          marktree_itr_set_node(b, enditr, d2.new, d2.new_i);
+          marktree_intersect_pair(b, d.id, itr, enditr, false);
+
+          i++;  // consume two items
+          continue;
+        }
+
+        // d is lone start, end didn't move
+        MarkTreeIter endpos[1];
+        marktree_lookup(b, d.id | MARKTREE_END_FLAG, endpos);
+        if (endpos->x) {
+          marktree_itr_set_node(b, itr, d.old, d.old_i);
+          *enditr = *endpos;
+          marktree_intersect_pair(b, d.id, itr, enditr, true);
+          marktree_itr_set_node(b, itr, d.new, d.new_i);
+          *enditr = *endpos;
+          marktree_intersect_pair(b, d.id, itr, enditr, false);
+        }
+      } else {
+        // d is lone end, start didn't move
+        MarkTreeIter startpos[1];
+        uint64_t start_id = d.id & ~MARKTREE_END_FLAG;
+
+        marktree_lookup(b, start_id, startpos);
+        if (startpos->x) {
+          *itr = *startpos;
+          marktree_itr_set_node(b, enditr, d.old, d.old_i);
+          marktree_intersect_pair(b, start_id, itr, enditr, true);
+          *itr = *startpos;
+          marktree_itr_set_node(b, enditr, d.new, d.new_i);
+          marktree_intersect_pair(b, start_id, itr, enditr, false);
+        }
+      }
+    }
   }
+  kvi_destroy(damage);
+
   return moved;
 }
 
 void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int extent_row,
                           colnr_T extent_col, int new_row, colnr_T new_col)
 {
-  mtpos_t start = { start_row, start_col }, size = { extent_row, extent_col };
-  mtpos_t end = size;
+  MTPos start = { start_row, start_col }, size = { extent_row, extent_col };
+  MTPos end = size;
   unrelative(start, &end);
   MarkTreeIter itr[1] = { 0 };
   marktree_itr_get_ext(b, start, itr, false, true, NULL);
-  kvec_t(mtkey_t) saved = KV_INITIAL_VALUE;
-  while (itr->node) {
-    mtkey_t k = marktree_itr_current(itr);
+  kvec_t(MTKey) saved = KV_INITIAL_VALUE;
+  while (itr->x) {
+    MTKey k = marktree_itr_current(itr);
     if (!pos_leq(k.pos, end) || (k.pos.row == end.row && k.pos.col == end.col
                                  && mt_right(k))) {
       break;
@@ -1020,57 +1857,101 @@ void marktree_move_region(MarkTree *b, int start_row, colnr_T start_col, int ext
   }
 
   marktree_splice(b, start.row, start.col, size.row, size.col, 0, 0);
-  mtpos_t new = { new_row, new_col };
+  MTPos new = { new_row, new_col };
   marktree_splice(b, new.row, new.col,
                   0, 0, size.row, size.col);
 
   for (size_t i = 0; i < kv_size(saved); i++) {
-    mtkey_t item = kv_A(saved, i);
+    MTKey item = kv_A(saved, i);
     unrelative(new, &item.pos);
     marktree_put_key(b, item);
+    if (mt_paired(item)) {
+      // other end might be later in `saved`, this will safely bail out then
+      marktree_restore_pair(b, item);
+    }
   }
   kv_destroy(saved);
 }
 
 /// @param itr OPTIONAL. set itr to pos.
-mtkey_t marktree_lookup_ns(MarkTree *b, uint32_t ns, uint32_t id, bool end, MarkTreeIter *itr)
+MTKey marktree_lookup_ns(MarkTree *b, uint32_t ns, uint32_t id, bool end, MarkTreeIter *itr)
 {
   return marktree_lookup(b, mt_lookup_id(ns, id, end), itr);
 }
 
+static uint64_t pseudo_index(MTNode *x, int i)
+{
+  int off = MT_LOG2_BRANCH * x->level;
+  uint64_t index = 0;
+
+  while (x) {
+    index |= (uint64_t)(i + 1) << off;
+    off += MT_LOG2_BRANCH;
+    i = x->p_idx;
+    x = x->parent;
+  }
+
+  return index;
+}
+
+/// @param itr OPTIONAL. set itr to pos.
+/// if sloppy, two keys at the same _leaf_ node has the same index
+static uint64_t pseudo_index_for_id(MarkTree *b, uint64_t id, bool sloppy)
+{
+  MTNode *n = id2node(b, id);
+  if (n == NULL) {
+    return 0;  // a valid pseudo-index is never zero!
+  }
+
+  int i = 0;
+  if (n->level || !sloppy) {
+    for (i = 0; i < n->n; i++) {
+      if (mt_lookup_key(n->key[i]) == id) {
+        break;
+      }
+    }
+    assert(i < n->n);
+    if (n->level) {
+      i += 1;  // internal key i comes after ptr[i]
+    }
+  }
+
+  return pseudo_index(n, i);
+}
+
 /// @param itr OPTIONAL. set itr to pos.
-mtkey_t marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
+MTKey marktree_lookup(MarkTree *b, uint64_t id, MarkTreeIter *itr)
 {
-  mtnode_t *n = pmap_get(uint64_t)(b->id2node, id);
+  MTNode *n = id2node(b, id);
   if (n == NULL) {
     if (itr) {
-      itr->node = NULL;
+      itr->x = NULL;
     }
     return MT_INVALID_KEY;
   }
   int i = 0;
   for (i = 0; i < n->n; i++) {
     if (mt_lookup_key(n->key[i]) == id) {
-      goto found;
+      return marktree_itr_set_node(b, itr, n, i);
     }
   }
+
   abort();
-found: {}
-  mtkey_t key = n->key[i];
+}
+
+MTKey marktree_itr_set_node(MarkTree *b, MarkTreeIter *itr, MTNode *n, int i)
+{
+  MTKey key = n->key[i];
   if (itr) {
     itr->i = i;
-    itr->node = n;
+    itr->x = n;
     itr->lvl = b->root->level - n->level;
   }
   while (n->parent != NULL) {
-    mtnode_t *p = n->parent;
-    for (i = 0; i < p->n + 1; i++) {
-      if (p->ptr[i] == n) {
-        goto found_node;
-      }
-    }
-    abort();
-found_node:
+    MTNode *p = n->parent;
+    i = n->p_idx;
+    assert(p->ptr[i] == n);
+
     if (itr) {
       itr->s[b->root->level - p->level].i = i;
     }
@@ -1085,14 +1966,14 @@ found_node:
   return key;
 }
 
-mtpos_t marktree_get_altpos(MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
+MTPos marktree_get_altpos(MarkTree *b, MTKey mark, MarkTreeIter *itr)
 {
   return marktree_get_alt(b, mark, itr).pos;
 }
 
-mtkey_t marktree_get_alt(MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
+MTKey marktree_get_alt(MarkTree *b, MTKey mark, MarkTreeIter *itr)
 {
-  mtkey_t end = MT_INVALID_KEY;
+  MTKey end = MT_INVALID_KEY;
   if (mt_paired(mark)) {
     end = marktree_lookup_ns(b, mark.ns, mark.id, !mt_end(mark), itr);
   }
@@ -1101,8 +1982,8 @@ mtkey_t marktree_get_alt(MarkTree *b, mtkey_t mark, MarkTreeIter *itr)
 
 static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
 {
-  itr->pos = (mtpos_t){ 0, 0 };
-  mtnode_t *x = b->root;
+  itr->pos = (MTPos){ 0, 0 };
+  MTNode *x = b->root;
   for (int lvl = 0; lvl < itr->lvl; lvl++) {
     itr->s[lvl].oldcol = itr->pos.col;
     int i = itr->s[lvl].i;
@@ -1112,23 +1993,36 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr)
     assert(x->level);
     x = x->ptr[i];
   }
-  assert(x == itr->node);
+  assert(x == itr->x);
 }
 
 // for unit test
-void marktree_put_test(MarkTree *b, uint32_t id, int row, int col, bool right_gravity)
+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)
 {
-  mtkey_t key = { { row, col }, UINT32_MAX, id, 0,
-                  mt_flags(right_gravity, 0), 0, NULL };
-  marktree_put(b, key, -1, -1, false);
+  MTKey key = { { row, col }, ns, id, 0,
+                mt_flags(right_gravity, 0), 0, NULL };
+  marktree_put(b, key, end_row, end_col, end_right);
 }
 
 // for unit test
-bool mt_right_test(mtkey_t key)
+bool mt_right_test(MTKey key)
 {
   return mt_right(key);
 }
 
+// for unit test
+void marktree_del_pair_test(MarkTree *b, uint32_t ns, uint32_t id)
+{
+  MarkTreeIter itr[1];
+  marktree_lookup_ns(b, ns, id, false, itr);
+
+  uint64_t other = marktree_del_itr(b, itr, false);
+  assert(other);
+  marktree_lookup(b, other, itr);
+  marktree_del_itr(b, itr, false);
+}
+
 void marktree_check(MarkTree *b)
 {
 #ifndef NDEBUG
@@ -1139,7 +2033,7 @@ void marktree_check(MarkTree *b)
     return;
   }
 
-  mtpos_t dummy;
+  MTPos dummy;
   bool last_right = false;
   size_t nkeys = marktree_check_node(b, b->root, &dummy, &last_right);
   assert(b->n_keys == nkeys);
@@ -1151,7 +2045,7 @@ void marktree_check(MarkTree *b)
 }
 
 #ifndef NDEBUG
-size_t marktree_check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_right)
+size_t marktree_check_node(MarkTree *b, MTNode *x, MTPos *last, bool *last_right)
 {
   assert(x->n <= 2 * T - 1);
   // TODO(bfredl): too strict if checking "in repair" post-delete tree.
@@ -1162,7 +2056,7 @@ size_t marktree_check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_r
     if (x->level) {
       n_keys += marktree_check_node(b, x->ptr[i], last, last_right);
     } else {
-      *last = (mtpos_t) { 0, 0 };
+      *last = (MTPos) { 0, 0 };
     }
     if (i > 0) {
       unrelative(x->key[i - 1].pos, last);
@@ -1182,6 +2076,7 @@ size_t marktree_check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_r
 
     for (int i = 0; i < x->n + 1; i++) {
       assert(x->ptr[i]->parent == x);
+      assert(x->ptr[i]->p_idx == i);
       assert(x->ptr[i]->level == x->level - 1);
       // PARANOIA: check no double node ref
       for (int j = 0; j < i; j++) {
@@ -1193,34 +2088,221 @@ size_t marktree_check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_r
   }
   return n_keys;
 }
+
+bool marktree_check_intersections(MarkTree *b)
+{
+  if (!b->root) {
+    return true;
+  }
+  PMap(ptr_t) checked = MAP_INIT;
+
+  // 1. move x->intersect to checked[x] and reinit x->intersect
+  mt_recurse_nodes(b->root, &checked);
+
+  // 2. iterate over all marks. for each START mark of a pair,
+  // intersect the nodes between the pair
+  MarkTreeIter itr[1];
+  marktree_itr_first(b, itr);
+  while (true) {
+    MTKey mark = marktree_itr_current(itr);
+    if (mark.pos.row < 0) {
+      break;
+    }
+
+    if (mt_start(mark)) {
+      MarkTreeIter start_itr[1];
+      MarkTreeIter end_itr[1];
+      uint64_t end_id = mt_lookup_id(mark.ns, mark.id, true);
+      MTKey k = marktree_lookup(b, end_id, end_itr);
+      if (k.pos.row >= 0) {
+        *start_itr = *itr;
+        marktree_intersect_pair(b, mt_lookup_key(mark), start_itr, end_itr, false);
+      }
+    }
+
+    marktree_itr_next(b, itr);
+  }
+
+  // 3. for each node check if the recreated intersection
+  // matches the old checked[x] intersection.
+  bool status = mt_recurse_nodes_compare(b->root, &checked);
+
+  uint64_t *val;
+  map_foreach_value(&checked, val, {
+    xfree(val);
+  });
+  map_destroy(ptr_t, &checked);
+
+  return status;
+}
+
+void mt_recurse_nodes(MTNode *x, PMap(ptr_t) *checked)
+{
+  if (kv_size(x->intersect)) {
+    kvi_push(x->intersect, (uint64_t)-1);  // sentinel
+    uint64_t *val;
+    if (x->intersect.items == x->intersect.init_array) {
+      val = xmemdup(x->intersect.items, x->intersect.size * sizeof(*x->intersect.items));
+    } else {
+      val = x->intersect.items;
+    }
+    pmap_put(ptr_t)(checked, x, val);
+    kvi_init(x->intersect);
+  }
+
+  if (x->level) {
+    for (int i = 0; i < x->n + 1; i++) {
+      mt_recurse_nodes(x->ptr[i], checked);
+    }
+  }
+}
+
+bool mt_recurse_nodes_compare(MTNode *x, PMap(ptr_t) *checked)
+{
+  uint64_t *ref = pmap_get(ptr_t)(checked, x);
+  if (ref != NULL) {
+    for (size_t i = 0;; i++) {
+      if (ref[i] == (uint64_t)-1) {
+        if (i != kv_size(x->intersect)) {
+          return false;
+        }
+
+        break;
+      } else {
+        if (kv_size(x->intersect) <= i || ref[i] != kv_A(x->intersect, i)) {
+          return false;
+        }
+      }
+    }
+  } else {
+    if (kv_size(x->intersect)) {
+      return false;
+    }
+  }
+
+  if (x->level) {
+    for (int i = 0; i < x->n + 1; i++) {
+      if (!mt_recurse_nodes_compare(x->ptr[i], checked)) {
+        return false;
+      }
+    }
+  }
+
+  return true;
+}
+
 #endif
 
-char *mt_inspect_rec(MarkTree *b)
+// TODO(bfredl): kv_print
+#define GA_PUT(x) ga_concat(ga, (char *)(x))
+#define GA_PRINT(fmt, ...) snprintf(buf, sizeof(buf), fmt, __VA_ARGS__); \
+  GA_PUT(buf);
+
+String mt_inspect(MarkTree *b, bool keys, bool dot)
 {
-  garray_T ga;
-  ga_init(&ga, (int)sizeof(char), 80);
-  mtpos_t p = { 0, 0 };
-  mt_inspect_node(b, &ga, b->root, p);
-  return ga.ga_data;
+  garray_T ga[1];
+  ga_init(ga, (int)sizeof(char), 80);
+  MTPos p = { 0, 0 };
+  if (b->root) {
+    if (dot) {
+      GA_PUT("digraph D {\n\n");
+      mt_inspect_dotfile_node(b, ga, b->root, p, NULL);
+      GA_PUT("\n}");
+    } else {
+      mt_inspect_node(b, ga, keys, b->root, p);
+    }
+  }
+  return ga_take_string(ga);
 }
 
-void mt_inspect_node(MarkTree *b, garray_T *ga, mtnode_t *n, mtpos_t off)
+void mt_inspect_node(MarkTree *b, garray_T *ga, bool keys, MTNode *n, MTPos off)
 {
   static char buf[1024];
-  ga_concat(ga, "[");
+  GA_PUT("[");
+  if (keys && kv_size(n->intersect)) {
+    for (size_t i = 0; i < kv_size(n->intersect); i++) {
+      GA_PUT(i == 0 ? "{" : ";");
+      // GA_PRINT("%"PRIu64, kv_A(n->intersect, i));
+      GA_PRINT("%" PRIu64, mt_dbg_id(kv_A(n->intersect, i)));
+    }
+    GA_PUT("},");
+  }
   if (n->level) {
-    mt_inspect_node(b, ga, n->ptr[0], off);
+    mt_inspect_node(b, ga, keys, n->ptr[0], off);
   }
   for (int i = 0; i < n->n; i++) {
-    mtpos_t p = n->key[i].pos;
+    MTPos p = n->key[i].pos;
     unrelative(off, &p);
-    snprintf(buf, sizeof(buf), "%d/%d", p.row, p.col);
-    ga_concat(ga, buf);
+    GA_PRINT("%d/%d", p.row, p.col);
+    if (keys) {
+      MTKey key = n->key[i];
+      GA_PUT(":");
+      if (mt_start(key)) {
+        GA_PUT("<");
+      }
+      // GA_PRINT("%"PRIu64, mt_lookup_id(key.ns, key.id, false));
+      GA_PRINT("%" PRIu32, key.id);
+      if (mt_end(key)) {
+        GA_PUT(">");
+      }
+    }
     if (n->level) {
-      mt_inspect_node(b, ga, n->ptr[i + 1], p);
+      mt_inspect_node(b, ga, keys, n->ptr[i + 1], p);
     } else {
       ga_concat(ga, ",");
     }
   }
   ga_concat(ga, "]");
 }
+
+void mt_inspect_dotfile_node(MarkTree *b, garray_T *ga, MTNode *n, MTPos off, char *parent)
+{
+  static char buf[1024];
+  char namebuf[64];
+  if (parent != NULL) {
+    snprintf(namebuf, sizeof namebuf, "%s_%c%d", parent, 'a' + n->level, n->p_idx);
+  } else {
+    snprintf(namebuf, sizeof namebuf, "Node");
+  }
+
+  GA_PRINT("  %s[shape=plaintext, label=<\n", namebuf);
+  GA_PUT("    <table border='0' cellborder='1' cellspacing='0'>\n");
+  if (kv_size(n->intersect)) {
+    GA_PUT("    <tr><td>");
+    for (size_t i = 0; i < kv_size(n->intersect); i++) {
+      if (i > 0) {
+        GA_PUT(", ");
+      }
+      GA_PRINT("%" PRIu64, mt_dbg_id(kv_A(n->intersect, i)));
+    }
+    GA_PUT("</td></tr>\n");
+  }
+
+  GA_PUT("    <tr><td>");
+  for (int i = 0; i < n->n; i++) {
+    MTKey k = n->key[i];
+    if (i > 0) {
+      GA_PUT(", ");
+    }
+    GA_PRINT("%d", k.id);
+    if (mt_paired(k)) {
+      GA_PUT(mt_end(k) ? "e" : "s");
+    }
+  }
+  GA_PUT("</td></tr>\n");
+  GA_PUT("    </table>\n");
+  GA_PUT(">];\n");
+  if (parent) {
+    GA_PRINT("  %s -> %s\n", parent, namebuf);
+  }
+  if (n->level) {
+    mt_inspect_dotfile_node(b, ga, n->ptr[0], off, namebuf);
+  }
+  for (int i = 0; i < n->n; i++) {
+    MTPos p = n->key[i].pos;
+    unrelative(off, &p);
+    if (n->level) {
+      mt_inspect_dotfile_node(b, ga, n->ptr[i + 1], p, namebuf);
+    }
+  }
+}
diff --git a/src/nvim/marktree.h b/src/nvim/marktree.h
index cd56115b58..f53a54f3cc 100644
--- a/src/nvim/marktree.h
+++ b/src/nvim/marktree.h
@@ -6,29 +6,37 @@
 #include <stddef.h>
 #include <stdint.h>
 
+#include "klib/kvec.h"
 #include "nvim/assert.h"
 #include "nvim/garray.h"
 #include "nvim/map.h"
 #include "nvim/pos.h"
 #include "nvim/types.h"
 
+// only for debug functions:
+#include "api/private/defs.h"
+
 struct mtnode_s;
 
 #define MT_MAX_DEPTH 20
 #define MT_BRANCH_FACTOR 10
+// note max branch is actually 2*MT_BRANCH_FACTOR
+// and strictly this is ceil(log2(2*MT_BRANCH_FACTOR + 1))
+// as we need a pseudo-index for "right before this node"
+#define MT_LOG2_BRANCH 5
 
 typedef struct {
   int32_t row;
   int32_t col;
-} mtpos_t;
-#define mtpos_t(r, c) ((mtpos_t){ .row = (r), .col = (c) })
+} MTPos;
+#define MTPos(r, c) ((MTPos){ .row = (r), .col = (c) })
 
-typedef struct mtnode_s mtnode_t;
+typedef struct mtnode_s MTNode;
 
 typedef struct {
-  mtpos_t pos;
+  MTPos pos;
   int lvl;
-  mtnode_t *node;
+  MTNode *x;
   int i;
   struct {
     int oldcol;
@@ -36,33 +44,43 @@ typedef struct {
   } s[MT_MAX_DEPTH];
 
   size_t intersect_idx;
-  mtpos_t intersect_pos;
+  MTPos intersect_pos;
+  MTPos intersect_pos_x;
 } MarkTreeIter;
 
-#define marktree_itr_valid(itr) ((itr)->node != NULL)
+#define marktree_itr_valid(itr) ((itr)->x != NULL)
 
 // Internal storage
 //
 // NB: actual marks have flags > 0, so we can use (row,col,0) pseudo-key for
 // "space before (row,col)"
 typedef struct {
-  mtpos_t pos;
+  MTPos pos;
   uint32_t ns;
   uint32_t id;
   int32_t hl_id;
   uint16_t flags;
   uint16_t priority;
   Decoration *decor_full;
-} mtkey_t;
-#define MT_INVALID_KEY (mtkey_t) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
+} MTKey;
+
+typedef struct {
+  MTKey start;
+  MTPos end_pos;
+  bool end_right_gravity;
+} MTPair;
+
+#define MT_INVALID_KEY (MTKey) { { -1, -1 }, 0, 0, 0, 0, 0, NULL }
 
 #define MT_FLAG_REAL (((uint16_t)1) << 0)
 #define MT_FLAG_END (((uint16_t)1) << 1)
 #define MT_FLAG_PAIRED (((uint16_t)1) << 2)
-#define MT_FLAG_HL_EOL (((uint16_t)1) << 3)
+// orphaned: the other side of this paired mark was deleted. this mark must be deleted very soon!
+#define MT_FLAG_ORPHANED (((uint16_t)1) << 3)
+#define MT_FLAG_HL_EOL (((uint16_t)1) << 4)
 
 #define DECOR_LEVELS 4
-#define MT_FLAG_DECOR_OFFSET 4
+#define MT_FLAG_DECOR_OFFSET 5
 #define MT_FLAG_DECOR_MASK (((uint16_t)(DECOR_LEVELS - 1)) << MT_FLAG_DECOR_OFFSET)
 
 // next flag is (((uint16_t)1) << 6)
@@ -73,39 +91,44 @@ typedef struct {
 
 #define MT_FLAG_EXTERNAL_MASK (MT_FLAG_DECOR_MASK | MT_FLAG_RIGHT_GRAVITY | MT_FLAG_HL_EOL)
 
-#define MARKTREE_END_FLAG (((uint64_t)1) << 63)
+// this is defined so that start and end of the same range have adjacent ids
+#define MARKTREE_END_FLAG ((uint64_t)1)
 static inline uint64_t mt_lookup_id(uint32_t ns, uint32_t id, bool enda)
 {
-  return (uint64_t)ns << 32 | id | (enda ? MARKTREE_END_FLAG : 0);
+  return (uint64_t)ns << 33 | (id <<1) | (enda ? MARKTREE_END_FLAG : 0);
 }
-#undef MARKTREE_END_FLAG
 
-static inline uint64_t mt_lookup_key(mtkey_t key)
+static inline uint64_t mt_lookup_key_side(MTKey key, bool end)
+{
+  return mt_lookup_id(key.ns, key.id, end);
+}
+
+static inline uint64_t mt_lookup_key(MTKey key)
 {
   return mt_lookup_id(key.ns, key.id, key.flags & MT_FLAG_END);
 }
 
-static inline bool mt_paired(mtkey_t key)
+static inline bool mt_paired(MTKey key)
 {
   return key.flags & MT_FLAG_PAIRED;
 }
 
-static inline bool mt_end(mtkey_t key)
+static inline bool mt_end(MTKey key)
 {
   return key.flags & MT_FLAG_END;
 }
 
-static inline bool mt_start(mtkey_t key)
+static inline bool mt_start(MTKey key)
 {
   return mt_paired(key) && !mt_end(key);
 }
 
-static inline bool mt_right(mtkey_t key)
+static inline bool mt_right(MTKey key)
 {
   return key.flags & MT_FLAG_RIGHT_GRAVITY;
 }
 
-static inline uint8_t marktree_decor_level(mtkey_t key)
+static inline uint8_t marktree_decor_level(MTKey key)
 {
   return (uint8_t)((key.flags&MT_FLAG_DECOR_MASK) >> MT_FLAG_DECOR_OFFSET);
 }
@@ -117,18 +140,27 @@ static inline uint16_t mt_flags(bool right_gravity, uint8_t decor_level)
                     | (decor_level << MT_FLAG_DECOR_OFFSET));
 }
 
+typedef kvec_withinit_t(uint64_t, 4) Intersection;
+
 struct mtnode_s {
   int32_t n;
-  int32_t level;
+  int16_t level;
+  int16_t p_idx;  // index in parent
+  Intersection intersect;
   // TODO(bfredl): we could consider having a only-sometimes-valid
   // index into parent for faster "cached" lookup.
-  mtnode_t *parent;
-  mtkey_t key[2 * MT_BRANCH_FACTOR - 1];
-  mtnode_t *ptr[];
+  MTNode *parent;
+  MTKey key[2 * MT_BRANCH_FACTOR - 1];
+  MTNode *ptr[];
 };
 
+static inline uint64_t mt_dbg_id(uint64_t id)
+{
+  return (id>>1)&0xffffffff;
+}
+
 typedef struct {
-  mtnode_t *root;
+  MTNode *root;
   size_t n_keys, n_nodes;
   // TODO(bfredl): the pointer to node could be part of the larger
   // Map(uint64_t, ExtmarkItem) essentially;
diff --git a/src/nvim/option_defs.h b/src/nvim/option_defs.h
index 1007925ccb..14f29682e1 100644
--- a/src/nvim/option_defs.h
+++ b/src/nvim/option_defs.h
@@ -630,6 +630,7 @@ EXTERN unsigned rdb_flags;
 #define RDB_NODELTA            0x008
 #define RDB_LINE               0x010
 #define RDB_FLUSH              0x020
+#define RDB_INTERSECT          0x040
 
 EXTERN long p_rdt;            // 'redrawtime'
 EXTERN long p_re;             // 'regexpengine'
diff --git a/src/nvim/plines.c b/src/nvim/plines.c
index 82554c7785..99f666ef3f 100644
--- a/src/nvim/plines.c
+++ b/src/nvim/plines.c
@@ -133,7 +133,7 @@ void init_chartabsize_arg(chartabsize_T *cts, win_T *wp, linenr_T lnum, colnr_T
 
   if (cts->cts_row >= 0 && wp->w_buffer->b_virt_text_inline > 0) {
     marktree_itr_get(wp->w_buffer->b_marktree, cts->cts_row, 0, cts->cts_iter);
-    mtkey_t mark = marktree_itr_current(cts->cts_iter);
+    MTKey mark = marktree_itr_current(cts->cts_iter);
     if (mark.pos.row == cts->cts_row) {
       cts->cts_has_virt_text = true;
     }
@@ -222,7 +222,7 @@ int win_lbr_chartabsize(chartabsize_T *cts, int *headp)
     int tab_size = size;
     int col = (int)(s - line);
     while (true) {
-      mtkey_t mark = marktree_itr_current(cts->cts_iter);
+      MTKey mark = marktree_itr_current(cts->cts_iter);
       if (mark.pos.row != cts->cts_row || mark.pos.col > col) {
         break;
       } else if (mark.pos.col == col) {
diff --git a/src/nvim/version.h b/src/nvim/version.h
index 484350edee..e0c7b76700 100644
--- a/src/nvim/version.h
+++ b/src/nvim/version.h
@@ -7,6 +7,9 @@
 // defined in version.c
 extern char *Version;
 extern char *longVersion;
+#ifndef NDEBUG
+extern char *version_cflags;
+#endif
 
 //
 // Vim version number, name, etc. Patchlevel is defined in version.c.