From 42999a8d645ccf880222f0192671b8ce01bde361 Mon Sep 17 00:00:00 2001 From: bfredl Date: Mon, 30 Jan 2023 14:46:28 +0100 Subject: fix(test): fix issues detected by running unittests in ASAN/UBSAN --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 2036ddd21d..77ba6e6fa4 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1182,7 +1182,7 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig assert(x->ptr[i] != x->ptr[j]); } } - } else { + } else if (x->n > 0) { *last = x->key[x->n - 1].pos; } return n_keys; -- cgit From f1c5887377c9ae547a7564ec4fc52d72656a974f Mon Sep 17 00:00:00 2001 From: dundargoc <33953936+dundargoc@users.noreply.github.com> Date: Thu, 16 Feb 2023 00:15:09 +0100 Subject: ci: add GCC Release testing (#22274) ci: add GCC release testing We currently have no release testing, so it's good to check for any unwanted behavior on release builds as well. Prefer GCC over clang, as GCC release builds seem to create more warnings on release compared to debug. --- src/nvim/marktree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 77ba6e6fa4..cb981bb00c 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1135,7 +1135,7 @@ void marktree_check(MarkTree *b) mtpos_t dummy; bool last_right = false; - size_t nkeys = check_node(b, b->root, &dummy, &last_right); + size_t nkeys = marktree_check_node(b, b->root, &dummy, &last_right); assert(b->n_keys == nkeys); assert(b->n_keys == map_size(b->id2node)); #else @@ -1145,7 +1145,7 @@ void marktree_check(MarkTree *b) } #ifndef NDEBUG -static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_right) +size_t marktree_check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_right) { assert(x->n <= 2 * T - 1); // TODO(bfredl): too strict if checking "in repair" post-delete tree. @@ -1154,7 +1154,7 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig for (int i = 0; i < x->n; i++) { if (x->level) { - n_keys += check_node(b, x->ptr[i], last, last_right); + n_keys += marktree_check_node(b, x->ptr[i], last, last_right); } else { *last = (mtpos_t) { 0, 0 }; } @@ -1171,7 +1171,7 @@ static size_t check_node(MarkTree *b, mtnode_t *x, mtpos_t *last, bool *last_rig } if (x->level) { - n_keys += check_node(b, x->ptr[x->n], last, last_right); + n_keys += marktree_check_node(b, x->ptr[x->n], last, last_right); unrelative(x->key[x->n - 1].pos, last); for (int i = 0; i < x->n + 1; i++) { -- cgit From 8021300806e2ccf04b3ec33970b682ee3c7a9cc3 Mon Sep 17 00:00:00 2001 From: bfredl Date: Thu, 16 Mar 2023 13:56:05 +0100 Subject: refactor(extmarks): some minor internal API changes extranges and a bunch of other improvements are coming for 0.10 This gets in some minor surrounding API changes to avoid rebase conflicts until then. - decorations will be able to be specific to windows - adjust deletion API to fit with extranges --- src/nvim/marktree.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index cb981bb00c..7e900bafa2 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -279,13 +279,13 @@ 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; @@ -294,6 +294,12 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) uint64_t id = mt_lookup_key(cur->key[curi]); // fprintf(stderr, "\nDELET %lu\n", id); + mtkey_t raw = rawkey(itr); + uint64_t other = 0; + if (mt_paired(raw)) { + other = mt_lookup_id(raw.ns, raw.id, !mt_end(raw)); + } + if (itr->node->level) { if (rev) { abort(); @@ -442,6 +448,8 @@ void marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) marktree_itr_next(b, itr); } } + + return other; } static mtnode_t *merge_node(MarkTree *b, mtnode_t *p, int i) -- cgit From 2d78e656b715119ca11d131a1a932f22f1b4ad36 Mon Sep 17 00:00:00 2001 From: ii14 <59243201+ii14@users.noreply.github.com> Date: Fri, 7 Apr 2023 21:43:00 +0200 Subject: refactor: remove redundant casts --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 7e900bafa2..f1285b39e7 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1216,7 +1216,7 @@ void mt_inspect_node(MarkTree *b, garray_T *ga, mtnode_t *n, mtpos_t off) for (int i = 0; i < n->n; i++) { mtpos_t p = n->key[i].pos; unrelative(off, &p); - snprintf((char *)buf, sizeof(buf), "%d/%d", p.row, p.col); + snprintf(buf, sizeof(buf), "%d/%d", p.row, p.col); ga_concat(ga, buf); if (n->level) { mt_inspect_node(b, ga, n->ptr[i + 1], p); -- cgit From 3b0df1780e2c8526bda5dead18ee7cc45925caba Mon Sep 17 00:00:00 2001 From: dundargoc <33953936+dundargoc@users.noreply.github.com> Date: Wed, 26 Apr 2023 23:23:44 +0200 Subject: refactor: uncrustify Notable changes: replace all infinite loops to `while(true)` and remove `int` from `unsigned int`. --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index f1285b39e7..757906d42f 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -127,7 +127,7 @@ static inline int marktree_getp_aux(const mtnode_t *x, mtkey_t k, int *r) if (x->n == 0) { return -1; } - rr = r? r : &tr; + rr = r ? r : &tr; while (begin < end) { int mid = (begin + end) >> 1; if (key_cmp(x->key[mid], k) < 0) { -- cgit From e2fdd53d8c015913e8be4ff708fc3488558c8906 Mon Sep 17 00:00:00 2001 From: bfredl Date: Sun, 14 May 2023 18:45:56 +0200 Subject: refactor(map): avoid duplicated khash_t types for values This reduces the total number of khash_t instantiations from 22 to 8. Make the khash internal functions take the size of values as a runtime parameter. This is abstracted with typesafe Map containers which are still specialized for both key, value type. Introduce `Set(key)` type for when there is no value. Refactor shada.c to use Map/Set instead of khash directly. This requires `map_ref` operation to be more flexible. Return pointers to both key and value, plus an indicator for new_item. As a bonus, `map_key` is now redundant. Instead of Map(cstr_t, FileMarks), use a pointer map as the FileMarks struct is humongous. Make `event_strings` actually work like an intern pool instead of wtf it was doing before. --- src/nvim/marktree.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 757906d42f..840b6b646e 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -359,7 +359,7 @@ uint64_t marktree_del_itr(MarkTree *b, MarkTreeIter *itr, bool rev) } b->n_keys--; - pmap_del(uint64_t)(b->id2node, id); + pmap_del(uint64_t)(b->id2node, id, NULL); // 5. bool itr_dirty = false; @@ -549,8 +549,8 @@ void marktree_clear(MarkTree *b) b->root = NULL; } if (b->id2node->table.keys) { - pmap_destroy(uint64_t)(b->id2node); - pmap_init(uint64_t, b->id2node); + map_destroy(uint64_t, b->id2node); + *b->id2node = (PMap(uint64_t)) MAP_INIT; } b->n_keys = 0; b->n_nodes = 0; -- cgit From 5970157e1d22fd5e05ae5d3bd949f807fb7a744c Mon Sep 17 00:00:00 2001 From: bfredl Date: Wed, 17 May 2023 16:08:06 +0200 Subject: refactor(map): enhanced implementation, Clean Code™, etc etc MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This involves two redesigns of the map.c implementations: 1. Change of macro style and code organization The old khash.h and map.c implementation used huge #define blocks with a lot of backslash line continuations. This instead uses the "implementation file" .c.h pattern. Such a file is meant to be included multiple times, with different macros set prior to inclusion as parameters. we already use this pattern e.g. for eval/typval_encode.c.h to implement different typval encoders reusing a similar structure. We can structure this code into two parts. one that only depends on key type and is enough to implement sets, and one which depends on both key and value to implement maps (as a wrapper around sets, with an added value[] array) 2. Separate the main hash buckets from the key / value arrays Change the hack buckets to only contain an index into separate key / value arrays This is a common pattern in modern, state of the art hashmap implementations. Even though this leads to one more allocated array, it is this often is a net reduction of memory consumption. Consider key+value consuming at least 12 bytes per pair. On average, we will have twice as many buckets per item. Thus old implementation: 2*12 = 24 bytes per item New implementation 1*12 + 2*4 = 20 bytes per item And the difference gets bigger with larger items. One might think we have pulled a fast one here, as wouldn't the average size of the new key/value arrays be 1.5 slots per items due to amortized grows? But remember, these arrays are fully dense, and thus the accessed memory, measured in _cache lines_, the unit which actually matters, will be the fully used memory but just rounded up to the nearest cache line boundary. This has some other interesting properties, such as an insert-only set/map will be fully ordered by insert only. Preserving this ordering in face of deletions is more tricky tho. As we currently don't use ordered maps, the "delete" operation maintains compactness of the item arrays in the simplest way by breaking the ordering. It would be possible to implement an order-preserving delete although at some cost, like allowing the items array to become non-dense until the next rehash. Finally, in face of these two major changes, all code used in khash.h has been integrated into map.c and friends. Given the heavy edits it makes no sense to "layer" the code into a vendored and a wrapper part. Rather, the layered cake follows the specialization depth: code shared for all maps, code specialized to a key type (and its equivalence relation), and finally code specialized to value+key type. --- src/nvim/marktree.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 840b6b646e..d07d176b6d 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -548,10 +548,8 @@ void marktree_clear(MarkTree *b) marktree_free_node(b->root); b->root = NULL; } - if (b->id2node->table.keys) { - map_destroy(uint64_t, b->id2node); - *b->id2node = (PMap(uint64_t)) MAP_INIT; - } + map_destroy(uint64_t, b->id2node); + *b->id2node = (PMap(uint64_t)) MAP_INIT; b->n_keys = 0; b->n_nodes = 0; } -- cgit From b04286a187d57c50f01cd36cd4668b7a69026579 Mon Sep 17 00:00:00 2001 From: bfredl Date: Sun, 22 Nov 2020 10:10:37 +0100 Subject: feat(extmark): support proper multiline ranges The removes the previous restriction that nvim_buf_set_extmark() could not be used to highlight arbitrary multi-line regions The problem can be summarized as follows: let's assume an extmark with a hl_group is placed covering the region (5,0) to (50,0) Now, consider what happens if nvim needs to redraw a window covering the lines 20-30. It needs to be able to ask the marktree what extmarks cover this region, even if they don't begin or end here. Therefore the marktree needs to be augmented with the information covers a point, not just what marks begin or end there. To do this, we augment each node with a field "intersect" which is a set the ids of the marks which overlap this node, but only if it is not part of the set of any parent. This ensures the number of nodes that need to be explicitly marked grows only logarithmically with the total number of explicitly nodes (and thus the number of of overlapping marks). Thus we can quickly iterate all marks which overlaps any query position by looking up what leaf node contains that position. Then we only need to consider all "start" marks within that leaf node, and the "intersect" set of that node and all its parents. Now, and the major source of complexity is that the tree restructuring operations (to ensure that each node has T-1 <= size <= 2*T-1) also need to update these sets. If a full inner node is split in two, one of the new parents might start to completely overlap some ranges and its ids will need to be moved from its children's sets to its own set. Similarly, if two undersized nodes gets joined into one, it might no longer completely overlap some ranges, and now the children which do needs to have the have the ids in its set instead. And then there are the pivots! Yes the pivot operations when a child gets moved from one parent to another. --- src/nvim/marktree.c | 1596 ++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 1339 insertions(+), 257 deletions(-) (limited to 'src/nvim/marktree.c') 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(" \n"); + if (kv_size(n->intersect)) { + GA_PUT(" \n"); + } + + GA_PUT(" \n"); + GA_PUT("
"); + 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("
"); + 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("
\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); + } + } +} -- cgit From 585549625d8aef073e874d7cace9ab9df0d71847 Mon Sep 17 00:00:00 2001 From: L Lllvvuu Date: Fri, 15 Sep 2023 21:43:49 -0700 Subject: fix(marktree): off-by-one error in `marktree_move` If you would insert element X at position j, then if you are moving that same element X from position i < j, you should move it to position j - 1, because you are losing an element. This error caused a gap to be left in the array, so that it looked like [x, null, y] instead of [x, y], where len = 2. This triggered #25147. Fixes: #25147 --- src/nvim/marktree.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index d8b8dbba29..e0bc9ae347 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1191,8 +1191,8 @@ void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col) 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; + memmove(&x->key[itr->i], &x->key[itr->i + 1], sizeof(MTKey) * (size_t)(new_i - itr->i - 1)); + x->key[new_i - 1] = key; } return; } -- cgit From 34be915f6b9313d7554aa973a82277504de4e285 Mon Sep 17 00:00:00 2001 From: L Lllvvuu Date: Sat, 16 Sep 2023 01:08:06 -0700 Subject: fix(marktree): preserve ordering in `marktree_move` `marktree_move` is making the tree out of order at: https://github.com/neovim/neovim/blob/be10d65bfafe056025ffffa2c1131712b9a493a5/src/nvim/marktree.c#L1188 Because `key` is at the new position, and `x->key[new_i]` is also at the new position, this comparison spuriously returns true, which causes `x->key[i]` to be updated in-place even when it needs to be moved. This causes crashes down the line, since the ordering of `MTNode.key` is an invariant that must be preserved. Fixes: #25157 --- src/nvim/marktree.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index e0bc9ae347..627efa9e96 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1178,6 +1178,9 @@ void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col) } if (internal) { + if (key.pos.row == newpos.row && key.pos.col == newpos.col) { + return; + } key.pos = newpos; bool match; // tricky: could minimize movement in either direction better @@ -1185,7 +1188,7 @@ void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col) if (!match) { new_i++; } - if (new_i == itr->i || key_cmp(key, x->key[new_i]) == 0) { + if (new_i == itr->i) { 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)); -- cgit From cf8b2c0e74fd5e723b0c15c2ce84e6900fd322d3 Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Sat, 30 Sep 2023 12:05:28 +0800 Subject: build(iwyu): add a few more _defs.h mappings (#25435) --- src/nvim/marktree.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 627efa9e96..197cc21308 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -46,6 +46,7 @@ // at the repo root. #include +#include #include #include #include @@ -55,9 +56,10 @@ #include "nvim/marktree.h" #include "nvim/memory.h" #include "nvim/pos.h" - // only for debug functions +#include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" +#include "nvim/macros.h" #define T MT_BRANCH_FACTOR #define ILEN (sizeof(MTNode) + (2 * T) * sizeof(void *)) -- cgit From 62306a29add233958ead5311c0fc69a21c3acef3 Mon Sep 17 00:00:00 2001 From: L Lllvvuu Date: Thu, 5 Oct 2023 02:35:29 -0700 Subject: fix(marktree): correct qsort usage > The application shall ensure that the function returns an integer less than, equal to, or greater than 0, if the first argument is considered respectively less than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is unspecified. https://pubs.opengroup.org/onlinepubs/009696899/functions/qsort.html --- src/nvim/marktree.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 197cc21308..ff82c59783 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1626,7 +1626,7 @@ 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; + return d1->id > d2->id ? 1 : -1; } bool marktree_splice(MarkTree *b, int32_t start_line, int start_col, int old_extent_line, @@ -1792,6 +1792,7 @@ past_continue_same_node: for (size_t i = 0; i < kv_size(damage); i++) { Damage d = kv_A(damage, i); + assert(i == 0 || d.id > kv_A(damage, i - 1).id); 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); @@ -2267,7 +2268,7 @@ void mt_inspect_dotfile_node(MarkTree *b, garray_T *ga, MTNode *n, MTPos off, ch if (parent != NULL) { snprintf(namebuf, sizeof namebuf, "%s_%c%d", parent, 'a' + n->level, n->p_idx); } else { - snprintf(namebuf, sizeof namebuf, "Node"); + snprintf(namebuf, sizeof namebuf, "MTNode"); } GA_PRINT(" %s[shape=plaintext, label=<\n", namebuf); -- cgit From c3d21ad1bccd9a2975be73b1115213fd884eada3 Mon Sep 17 00:00:00 2001 From: dundargoc Date: Fri, 15 Sep 2023 09:43:48 +0200 Subject: docs: small fixes Co-authored-by: Wansmer Co-authored-by: Andrew Voynov Co-authored-by: David Moberg --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index ff82c59783..8ab9370e6c 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -852,7 +852,7 @@ static void intersect_add(Intersection *x, Intersection *y) } } -// inplace assymetric difference: x &= ~y +// inplace asymmetric difference: x &= ~y static void intersect_sub(Intersection *restrict x, Intersection *restrict y) { size_t xi = 0, yi = 0; -- cgit From 68cb4a7405ea9f8841d1f25ee8997c49e77fa679 Mon Sep 17 00:00:00 2001 From: bfredl Date: Fri, 3 Nov 2023 12:26:38 +0100 Subject: feat(extmarks): add "undo_restore" flag to opt out of undo-restoring It is a design goal of extmarks that they allow precise tracking of changes across undo/redo, including restore the exact positions after a do/undo or undo/redo cycle. However this behavior is not useful for all usecases. Many plugins won't keep marks around for long after text changes, but uses them more like a cache until some external source (like LSP semantic highlights) has fully updated to changed text and then will explicitly readjust/replace extmarks as needed. Add a "undo_restore" flag which is true by default (matches existing behavior) but can be set to false to opt-out of this behavior. Delete dead u_extmark_set() code. --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 8ab9370e6c..3df659b8e1 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -2007,7 +2007,7 @@ void marktree_put_test(MarkTree *b, uint32_t ns, uint32_t id, int row, int col, int end_row, int end_col, bool end_right) { MTKey key = { { row, col }, ns, id, 0, - mt_flags(right_gravity, 0), 0, NULL }; + mt_flags(right_gravity, 0, false), 0, NULL }; marktree_put(b, key, end_row, end_col, end_right); } -- cgit From 4e6f559b8c5f77924fdbe2e5abd9c6aa8efad13f Mon Sep 17 00:00:00 2001 From: Luuk van Baal Date: Tue, 24 Oct 2023 13:32:00 +0200 Subject: feat(extmarks): add 'invalidate' property to extmarks Problem: No way to have extmarks automatically removed when the range it is attached to is deleted. Solution: Add new 'invalidate' property that will hide a mark when the entirety of its range is deleted. When "undo_restore" is set to false, delete the mark from the buffer instead. --- src/nvim/marktree.c | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 3df659b8e1..214d228b2c 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1146,9 +1146,14 @@ void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, MTKey // TODO(bfredl): clean up this mess and re-instantiate &= and |= forms // once we upgrade to a non-broken version of gcc in functionaltest-lua CI rawkey(itr).flags = (uint16_t)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_DECOR_MASK); + rawkey(itr).flags = (uint16_t)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_INVALID); rawkey(itr).flags = (uint16_t)(rawkey(itr).flags | (uint16_t)(decor_level << MT_FLAG_DECOR_OFFSET) - | (uint16_t)(key.flags & MT_FLAG_DECOR_MASK)); + | (uint16_t)(key.flags & MT_FLAG_DECOR_MASK) + | (uint16_t)(key.flags & MT_FLAG_HL_EOL) + | (uint16_t)(key.flags & MT_FLAG_NO_UNDO) + | (uint16_t)(key.flags & MT_FLAG_INVALID) + | (uint16_t)(key.flags & MT_FLAG_INVALIDATE)); rawkey(itr).decor_full = key.decor_full; rawkey(itr).hl_id = key.hl_id; rawkey(itr).priority = key.priority; @@ -2006,8 +2011,8 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr) void marktree_put_test(MarkTree *b, uint32_t ns, uint32_t id, int row, int col, bool right_gravity, int end_row, int end_col, bool end_right) { - MTKey key = { { row, col }, ns, id, 0, - mt_flags(right_gravity, 0, false), 0, NULL }; + uint16_t flags = mt_flags(right_gravity, false, false, false, 0); + MTKey key = { { row, col }, ns, id, 0, flags, 0, NULL }; marktree_put(b, key, end_row, end_col, end_right); } -- cgit From 353a4be7e84fdc101318215bdcc8a7e780d737fe Mon Sep 17 00:00:00 2001 From: dundargoc Date: Sun, 12 Nov 2023 13:13:58 +0100 Subject: build: remove PVS We already have an extensive suite of static analysis tools we use, which causes a fair bit of redundancy as we get duplicate warnings. PVS is also prone to give false warnings which creates a lot of work to identify and disable. --- src/nvim/marktree.c | 3 --- 1 file changed, 3 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 214d228b2c..05aa4527ae 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 -- cgit From ec283e6b4ba85dcb61e97e089605e006e85cc273 Mon Sep 17 00:00:00 2001 From: bfredl Date: Sat, 18 Nov 2023 20:35:12 +0100 Subject: refactor(extmark): redundant ExtmarkInfo delenda est, use MTPair instead --- src/nvim/marktree.c | 13 ++++--------- 1 file changed, 4 insertions(+), 9 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 05aa4527ae..009c293d37 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -1503,11 +1503,6 @@ bool marktree_itr_get_overlap(MarkTree *b, int row, int col, MarkTreeIter *itr) 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| @@ -1526,8 +1521,8 @@ bool marktree_itr_step_overlap(MarkTree *b, MarkTreeIter *itr, MTPair *pair) 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)); + *pair = mtpair_from(marktree_lookup(b, id, NULL), + marktree_lookup(b, id|MARKTREE_END_FLAG, NULL)); return true; } @@ -1564,7 +1559,7 @@ bool marktree_itr_step_overlap(MarkTree *b, MarkTreeIter *itr, MTPair *pair) } unrelative(itr->pos, &k.pos); - *pair = pair_from(k, end); + *pair = mtpair_from(k, end); return true; // it's a start! } } @@ -1583,7 +1578,7 @@ bool marktree_itr_step_overlap(MarkTree *b, MarkTreeIter *itr, MTPair *pair) if (pos_less(itr->intersect_pos, start.pos)) { continue; } - *pair = pair_from(start, k); + *pair = mtpair_from(start, k); return true; // end of a range which began before us! } } -- cgit From ac1113ded5f8f09dd99a9894d7a7e795626fb728 Mon Sep 17 00:00:00 2001 From: dundargoc Date: Mon, 13 Nov 2023 23:40:37 +0100 Subject: refactor: follow style guide - reduce variable scope - prefer initialization over declaration and assignment --- src/nvim/marktree.c | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 009c293d37..5cc3d3d3ee 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -430,11 +430,10 @@ void marktree_put_key(MarkTree *b, MTKey k) if (!b->root) { b->root = marktree_alloc_node(b, true); } - MTNode *r, *s; b->n_keys++; - r = b->root; + MTNode *r = b->root; if (r->n == 2 * T - 1) { - s = marktree_alloc_node(b, true); + 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; -- cgit From 488038580934f301c1528a14548ec0cabd16c2cd Mon Sep 17 00:00:00 2001 From: dundargoc Date: Fri, 10 Nov 2023 14:06:04 +0100 Subject: build: adjust clang-tidy warning exclusion logic Enable all clang-tidy warnings by default instead of disabling them. This ensures that we don't miss useful warnings on each clang-tidy version upgrade. A drawback of this is that it will force us to either fix or adjust the warnings as soon as possible. --- src/nvim/marktree.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 5cc3d3d3ee..f350001977 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -773,13 +773,14 @@ static void intersect_mov(Intersection *restrict x, Intersection *restrict y, 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) +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 = x, .size = nx }; - Intersection yi = { .items = y, .size = ny }; + Intersection xi = { .items = (uint64_t *)x, .size = nx }; + Intersection yi = { .items = (uint64_t *)y, .size = ny }; Intersection w; kvi_init(w); -- cgit From 0b38fe4dbb77c15ae6f5779174855acab25fc86c Mon Sep 17 00:00:00 2001 From: bfredl Date: Wed, 8 Mar 2023 15:18:02 +0100 Subject: refactor(decorations): break up Decoration struct into smaller pieces Remove the monolithic Decoration struct. Before this change, each extmark could either represent just a hl_id + priority value as a inline decoration, or it would take a pointer to this monolitic 112 byte struct which has to be allocated. This change separates the decorations into two pieces: DecorSignHighlight for signs, highlights and simple set-flag decorations (like spell, ui-watched), and DecorVirtText for virtual text and lines. The main separation here is whether they are expected to allocate more memory. Currently this is not really true as sign text has to be an allocated string, but the plan is to get rid of this eventually (it can just be an array of two schar_T:s). Further refactors are expected to improve the representation of each decoration kind individually. The goal of this particular PR is to get things started by cutting the Gordian knot which was the monolithic struct Decoration. Now, each extmark can either contain chained indicies/pointers to these kinds of objects, or it can fit a subset of DecorSignHighlight inline. The point of this change is not only to make decorations smaller in memory. In fact, the main motivation is to later allow them to grow _larger_, but on a dynamic, on demand fashion. As a simple example, it would be possible to augment highlights to take a list of multiple `hl_group`:s, which then would trivially map to a chain of multiple DecorSignHighlight entries. One small feature improvement included with this refactor itself, is that the restriction that extmarks cannot be removed inside a decoration provider has been lifted. These are instead safely lifetime extended on a "to free" list until the current iteration of screen drawing is done. NB: flags is a mess. but DecorLevel is useless, this slightly less so --- src/nvim/marktree.c | 25 +++---------------------- 1 file changed, 3 insertions(+), 22 deletions(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index f350001977..110683a35c 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -287,7 +287,7 @@ static inline void marktree_putp_aux(MarkTree *b, MTNode *x, MTKey k) void marktree_put(MarkTree *b, MTKey key, int end_row, int end_col, bool end_right) { - assert(!(key.flags & ~MT_FLAG_EXTERNAL_MASK)); + assert(!(key.flags & ~(MT_FLAG_EXTERNAL_MASK | MT_FLAG_RIGHT_GRAVITY))); if (end_row >= 0) { key.flags |= MT_FLAG_PAIRED; } @@ -1137,25 +1137,6 @@ static void marktree_free_node(MarkTree *b, MTNode *x) b->n_nodes--; } -/// NB: caller must check not pair! -void marktree_revise(MarkTree *b, MarkTreeIter *itr, uint8_t decor_level, MTKey key) -{ - // TODO(bfredl): clean up this mess and re-instantiate &= and |= forms - // once we upgrade to a non-broken version of gcc in functionaltest-lua CI - rawkey(itr).flags = (uint16_t)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_DECOR_MASK); - rawkey(itr).flags = (uint16_t)(rawkey(itr).flags & (uint16_t) ~MT_FLAG_INVALID); - rawkey(itr).flags = (uint16_t)(rawkey(itr).flags - | (uint16_t)(decor_level << MT_FLAG_DECOR_OFFSET) - | (uint16_t)(key.flags & MT_FLAG_DECOR_MASK) - | (uint16_t)(key.flags & MT_FLAG_HL_EOL) - | (uint16_t)(key.flags & MT_FLAG_NO_UNDO) - | (uint16_t)(key.flags & MT_FLAG_INVALID) - | (uint16_t)(key.flags & MT_FLAG_INVALIDATE)); - rawkey(itr).decor_full = key.decor_full; - rawkey(itr).hl_id = key.hl_id; - rawkey(itr).priority = key.priority; -} - /// @param itr iterator is invalid after call void marktree_move(MarkTree *b, MarkTreeIter *itr, int row, int col) { @@ -2003,8 +1984,8 @@ static void marktree_itr_fix_pos(MarkTree *b, MarkTreeIter *itr) void marktree_put_test(MarkTree *b, uint32_t ns, uint32_t id, int row, int col, bool right_gravity, int end_row, int end_col, bool end_right) { - uint16_t flags = mt_flags(right_gravity, false, false, false, 0); - MTKey key = { { row, col }, ns, id, 0, flags, 0, NULL }; + uint16_t flags = mt_flags(right_gravity, false, false, false); + MTKey key = { { row, col }, ns, id, flags, { .hl = DECOR_HIGHLIGHT_INLINE_INIT } }; marktree_put(b, key, end_row, end_col, end_right); } -- cgit From 6361806aa28edca55ad3316a58bc3e936df9c0eb Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Sun, 26 Nov 2023 22:58:52 +0800 Subject: refactor: move garray_T to garray_defs.h (#26227) --- src/nvim/marktree.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 110683a35c..6f6a91eae0 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -56,6 +56,7 @@ // only for debug functions #include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" +#include "nvim/garray_defs.h" #include "nvim/macros.h" #define T MT_BRANCH_FACTOR -- cgit From 40139738eb479d0913ec6ce751ca5adfa50ad8c3 Mon Sep 17 00:00:00 2001 From: dundargoc Date: Sun, 26 Nov 2023 21:36:02 +0100 Subject: build: enable IWYU on mac --- src/nvim/marktree.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 6f6a91eae0..cffeb077f8 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -47,6 +47,7 @@ #include #include #include +#include #include "klib/kvec.h" #include "nvim/garray.h" -- cgit From f4aedbae4cb1f206f5b7c6142697b71dd473059b Mon Sep 17 00:00:00 2001 From: dundargoc Date: Mon, 27 Nov 2023 18:39:38 +0100 Subject: build(IWYU): fix includes for undo_defs.h --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index cffeb077f8..7a06d9d453 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -53,7 +53,7 @@ #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" -- cgit From 79b6ff28ad1204fbb4199b9092f5c578d88cb28e Mon Sep 17 00:00:00 2001 From: dundargoc Date: Tue, 28 Nov 2023 20:31:00 +0100 Subject: refactor: fix headers with IWYU --- src/nvim/marktree.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/marktree.c') diff --git a/src/nvim/marktree.c b/src/nvim/marktree.c index 7a06d9d453..b555b3b4ae 100644 --- a/src/nvim/marktree.c +++ b/src/nvim/marktree.c @@ -58,7 +58,7 @@ #include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" #include "nvim/garray_defs.h" -#include "nvim/macros.h" +#include "nvim/macros_defs.h" #define T MT_BRANCH_FACTOR #define ILEN (sizeof(MTNode) + (2 * T) * sizeof(void *)) -- cgit