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

1 files changed, 1356 insertions, 282 deletions

diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c
index 2036ddd21d..b555b3b4ae 100644
--- a/src/nvim/marktree.c
+++ b/src/nvim/marktree.c
@@ -1,6 +1,3 @@
-// This is an open source non-commercial project. Dear PVS-Studio, please check
-// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
-
 // Tree data structure for storing marks at (row, col) positions and updating
 // them to arbitrary text changes. Derivative work of kbtree in klib, whose
 // copyright notice is reproduced below. Also inspired by the design of the
@@ -14,8 +11,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):
 //
@@ -48,29 +43,41 @@
 // at the repo root.
 
 #include <assert.h>
+#include <inttypes.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <sys/types.h>
 
 #include "klib/kvec.h"
 #include "nvim/garray.h"
 #include "nvim/marktree.h"
 #include "nvim/memory.h"
-#include "nvim/pos.h"
+#include "nvim/pos_defs.h"
+// only for debug functions
+#include "nvim/api/private/defs.h"
+#include "nvim/api/private/helpers.h"
+#include "nvim/garray_defs.h"
+#include "nvim/macros_defs.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 +88,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 +98,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 +108,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 +132,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 +160,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 +250,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,9 +287,9 @@ 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));
+  assert(!(key.flags & ~(MT_FLAG_EXTERNAL_MASK | MT_FLAG_RIGHT_GRAVITY)));
   if (end_row >= 0) {
     key.flags |= MT_FLAG_PAIRED;
   }
@@ -230,32 +297,150 @@ 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;
   b->n_keys++;
-  r = b->root;
+  MTNode *r = b->root;
   if (r->n == 2 * T - 1) {
-    b->n_nodes++;
-    s = (mtnode_t *)xcalloc(1, ILEN);
+    MTNode *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);
@@ -279,26 +464,41 @@ void marktree_put_key(MarkTree *b, mtkey_t k)
 /// 6. If 4 went all the way to the root node. The root node
 ///    might have ended up with size 0. Delete it then.
 ///
-/// NB: ideally keeps the iterator valid. Like point to the key after this
-/// if present.
+/// The iterator remains valid, and now points at the key _after_ the deleted
+/// one.
 ///
 /// @param rev should be true if we plan to iterate _backwards_ and delete
 ///            stuff before this key. Most of the time this is false (the
 ///            recommended strategy is to always iterate forward)
-void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
+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);
 
-  if (itr->node->level) {
+  MTKey raw = rawkey(itr);
+  uint64_t other = 0;
+  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->x->level) {
     if (rev) {
       abort();
     } else {
-      // fprintf(stderr, "INTERNAL %d\n", cur->level);
       // steal previous node
       marktree_itr_prev(b, itr);
       adjustment = -1;
@@ -306,41 +506,72 @@ void 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++) {
@@ -352,46 +583,48 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev)
     itr->i--;
   }
 
-  b->n_keys--;
-  pmap_del(uint64_t)(b->id2node, id);
-
   // 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
@@ -408,18 +641,18 @@ void 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);
   }
 
@@ -435,18 +668,241 @@ void 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);
     }
   }
+
+  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(const uint64_t *x, size_t nx, const uint64_t *y, size_t ny,
+                        const 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 = (uint64_t *)x, .size = nx };
+  Intersection yi = { .items = (uint64_t *)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 asymmetric 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);
@@ -454,35 +910,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);
@@ -491,6 +990,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++;
@@ -501,11 +1001,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);