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(-) 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 477458f7bf8dc70ff56d3d4af4ef44f83b95016a Mon Sep 17 00:00:00 2001 From: bfredl Date: Thu, 14 Sep 2023 11:45:19 +0200 Subject: fix(test): more tests for marktree Co-Authored-By: L Lllvvuu --- test/unit/marktree_spec.lua | 106 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 106 insertions(+) diff --git a/test/unit/marktree_spec.lua b/test/unit/marktree_spec.lua index 32300c167c..97b97b47bb 100644 --- a/test/unit/marktree_spec.lua +++ b/test/unit/marktree_spec.lua @@ -366,6 +366,68 @@ describe('marktree', function() eq(0, tree[0].n_keys) end) + itp('works with intersections and marktree_splice', function() + local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit + + for i = 1,1000 do + put(tree, 1, i, false, 2, 1000-i, false) + if i % 10 == 1 then + check_intersections(tree) + end + end + + check_intersections(tree) + eq(2000, tree[0].n_keys) + ok(tree[0].root.level >= 2) + + for _ = 1,10 do + lib.marktree_splice(tree, 0, 0, 0, 100, 0, 0) + check_intersections(tree) + end + end) + + itp('marktree_move should preserve key order', function() + local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit + local iter = ffi.new("MarkTreeIter[1]") + local ids = {} + + -- new index and old index look the same, but still have to move becase + -- pos will get updated + table.insert(ids, put(tree, 1, 1, false, 1, 3, false)) + table.insert(ids, put(tree, 1, 3, false, 1, 3, false)) + table.insert(ids, put(tree, 1, 3, false, 1, 3, false)) + table.insert(ids, put(tree, 1, 3, false, 1, 3, false)) + + lib.marktree_lookup_ns(tree, ns, ids[3], false, iter) + lib.marktree_move(tree, iter, 1, 2) + + check_intersections(tree) + end) + + itp('works with intersections and marktree_move', function() + local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit + + local ids = {} + + for i = 1,1000 do + table.insert(ids, put(tree, 1, i, false, 2, 1000-i, false)) + if i % 10 == 1 then + check_intersections(tree) + end + end + + local iter = ffi.new("MarkTreeIter[1]") + for i = 1,1000 do + local which = i%2 + lib.marktree_lookup_ns(tree, ns, ids[i], which, iter) + lib.marktree_move(tree, iter, 1+which, 500+i) + if i % 10 == 1 then + check_intersections(tree) + end + end + + end) + itp('works with intersections with a even bigger tree', function() local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit @@ -435,4 +497,48 @@ describe('marktree', function() eq(0, tree[0].n_keys) end) + + itp('works with intersections with a even bigger tree and splice', function() + local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit + + -- too much overhead on ASAN + local size_factor = helpers.is_asan() and 3 or 10 + + local at_row = {} + for i = 1, 10 do + at_row[i] = {} + end + + local size = 1000*size_factor + local k = 1 + while k <= size do + for row1 = 1,9 do + for row2 = row1,10 do -- note row2 can be == row1, leads to empty ranges being tested when k > size/2 + if k > size then + break + end + local id = put(tree, row1, k, false, row2, size-k, false) + for i = row1+1, row2 do + table.insert(at_row[i], id) + end + --if tree[0].root.level == 4 then error("kk"..k) end + if k % 100*size_factor == 1 or (k < 2000 and k%100 == 1) then + check_intersections(tree) + end + k = k + 1 + end + end + end + + eq(2*size, tree[0].n_keys) + ok(tree[0].root.level >= 3) + check_intersections(tree) + + for _ = 1,10 do + for j = 3, 8 do + lib.marktree_splice(tree, j, 0, 0, 200, 0, 0) + check_intersections(tree) + end + end + end) end) -- cgit