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.

6 files changed, 318 insertions, 21 deletions

diff --git a/test/functional/api/extmark_spec.lua b/test/functional/api/extmark_spec.lua
index 6d8e3d8e0a..a917432dab 100644
--- a/test/functional/api/extmark_spec.lua
+++ b/test/functional/api/extmark_spec.lua
@@ -753,7 +753,14 @@ describe('API/extmarks', function()
       })
     end)
 
-    -- TODO(bfredl): add more tests!
+    it('can get overlapping extmarks', function()
+      set_extmark(ns, 1, 0, 0, {end_row = 5, end_col=0})
+      set_extmark(ns, 2, 2, 5, {end_row = 2, end_col=30})
+      set_extmark(ns, 3, 0, 5, {end_row = 2, end_col=10})
+      set_extmark(ns, 4, 0, 0, {end_row = 1, end_col=0})
+      eq({{ 2, 2, 5 }}, get_extmarks(ns, {2, 0}, {2, -1}, { overlap=false }))
+      eq({{ 1, 0, 0 }, { 3, 0, 5}, {2, 2, 5}}, get_extmarks(ns, {2, 0}, {2, -1}, { overlap=true }))
+    end)
   end)
 
   it('replace works', function()
diff --git a/test/functional/helpers.lua b/test/functional/helpers.lua
index b98cf97e7e..6f5397a089 100644
--- a/test/functional/helpers.lua
+++ b/test/functional/helpers.lua
@@ -857,6 +857,11 @@ function module.testprg(name)
   return ('%s/%s%s'):format(module.nvim_dir, name, ext)
 end
 
+function module.is_asan()
+  local version = module.eval('execute("verbose version")')
+  return version:match('-fsanitize=[a-z,]*address')
+end
+
 -- Returns a valid, platform-independent Nvim listen address.
 -- Useful for communicating with child instances.
 function module.new_pipename()
diff --git a/test/functional/legacy/memory_usage_spec.lua b/test/functional/legacy/memory_usage_spec.lua
index bf37315914..5f722e5190 100644
--- a/test/functional/legacy/memory_usage_spec.lua
+++ b/test/functional/legacy/memory_usage_spec.lua
@@ -11,14 +11,10 @@ local load_adjust = helpers.load_adjust
 local write_file = helpers.write_file
 local is_os = helpers.is_os
 local is_ci = helpers.is_ci
-
-local function isasan()
-  local version = eval('execute("verbose version")')
-  return version:match('-fsanitize=[a-z,]*address')
-end
+local is_asan = helpers.is_asan
 
 clear()
-if isasan() then
+if is_asan() then
   pending('ASAN build is difficult to estimate memory usage', function() end)
   return
 elseif is_os('win') then
diff --git a/test/functional/ui/decorations_spec.lua b/test/functional/ui/decorations_spec.lua
index a75290b400..4262f7ce77 100644
--- a/test/functional/ui/decorations_spec.lua
+++ b/test/functional/ui/decorations_spec.lua
@@ -691,6 +691,7 @@ describe('extmark decorations', function()
       [33] = {foreground = Screen.colors.DarkBlue, background = Screen.colors.LightGray};
       [34] = {background = Screen.colors.Yellow};
       [35] = {background = Screen.colors.Yellow, bold = true, foreground = Screen.colors.Blue};
+      [36] = {foreground = Screen.colors.Blue1, bold = true, background = Screen.colors.Red};
     }
 
     ns = meths.create_namespace 'test'
@@ -1652,6 +1653,70 @@ describe('extmark decorations', function()
       {24:-- VISUAL BLOCK --}                                |
     ]])
   end)
+
+  it('supports multiline highlights', function()
+    insert(example_text)
+    feed 'gg'
+    for _,i in ipairs {1,2,3,5,6,7} do
+      for _,j in ipairs {2,5,10,15} do
+        meths.buf_set_extmark(0, ns, i, j, { end_col=j+2, hl_group = 'NonText'})
+      end
+    end
+    screen:expect{grid=[[
+      ^for _,item in ipairs(items) do                    |
+        {1:  }l{1:oc}al {1:te}xt,{1: h}l_id_cell, count = unpack(item)  |
+        {1:  }i{1:f }hl_{1:id}_ce{1:ll} ~= nil then                     |
+        {1:  } {1:  } hl{1:_i}d ={1: h}l_id_cell                        |
+          end                                           |
+        {1:  }f{1:or} _ {1:= }1, {1:(c}ount or 1) do                    |
+        {1:  } {1:  } lo{1:ca}l c{1:el}l = line[colpos]                 |
+        {1:  } {1:  } ce{1:ll}.te{1:xt} = text                          |
+              cell.hl_id = hl_id                        |
+              colpos = colpos+1                         |
+          end                                           |
+      end                                               |
+      {1:~                                                 }|
+      {1:~                                                 }|
+                                                        |
+    ]]}
+    feed'5<c-e>'
+    screen:expect{grid=[[
+      ^  {1:  }f{1:or} _ {1:= }1, {1:(c}ount or 1) do                    |
+        {1:  } {1:  } lo{1:ca}l c{1:el}l = line[colpos]                 |
+        {1:  } {1:  } ce{1:ll}.te{1:xt} = text                          |
+              cell.hl_id = hl_id                        |
+              colpos = colpos+1                         |
+          end                                           |
+      end                                               |
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+                                                        |
+    ]]}
+
+    meths.buf_set_extmark(0, ns, 1, 0, { end_line=8, end_col=10, hl_group = 'ErrorMsg'})
+    screen:expect{grid=[[
+      {4:^  }{36:  }{4:f}{36:or}{4: _ }{36:= }{4:1, }{36:(c}{4:ount or 1) do}                    |
+      {4:  }{36:  }{4: }{36:  }{4: lo}{36:ca}{4:l c}{36:el}{4:l = line[colpos]}                 |
+      {4:  }{36:  }{4: }{36:  }{4: ce}{36:ll}{4:.te}{36:xt}{4: = text}                          |
+      {4:        ce}ll.hl_id = hl_id                        |
+              colpos = colpos+1                         |
+          end                                           |
+      end                                               |
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+      {1:~                                                 }|
+                                                        |
+    ]]}
+  end)
 end)
 
 describe('decorations: inline virtual text', function()
@@ -4136,7 +4201,6 @@ l5
   end)
 
   it('can add multiple signs (single extmark)', function()
-    pending('TODO(lewis6991): Support ranged signs')
     insert(example_test3)
     feed 'gg'
 
@@ -4158,7 +4222,6 @@ l5
   end)
 
   it('can add multiple signs (multiple extmarks)', function()
-    pending('TODO(lewis6991): Support ranged signs')
     insert(example_test3)
     feed'gg'
 
@@ -4219,7 +4282,6 @@ l5
   end)
 
   it('can add multiple signs (multiple extmarks) 3', function()
-    pending('TODO(lewis6991): Support ranged signs')
 
     insert(example_test3)
     feed 'gg'
@@ -4289,7 +4351,6 @@ l5
   end)
 
   it('works with old signs (with range)', function()
-    pending('TODO(lewis6991): Support ranged signs')
     insert(example_test3)
     feed 'gg'
 
@@ -4304,7 +4365,7 @@ l5
 
     screen:expect{grid=[[
       S3S4S1^l1                                          |
-      S2S3x l2                                          |
+      x S2S3l2                                          |
       S5S3{1:  }l3                                          |
       S3{1:    }l4                                          |
       S3{1:    }l5                                          |
@@ -4317,8 +4378,6 @@ l5
   end)
 
   it('can add a ranged sign (with start out of view)', function()
-    pending('TODO(lewis6991): Support ranged signs')
-
     insert(example_test3)
     command 'set signcolumn=yes:2'
     feed 'gg'
diff --git a/test/unit/helpers.lua b/test/unit/helpers.lua
index e9b97266d0..43b6980702 100644
--- a/test/unit/helpers.lua
+++ b/test/unit/helpers.lua
@@ -849,6 +849,16 @@ local function ptr2key(ptr)
   return ffi.string(s)
 end
 
+local function is_asan()
+  cimport('./src/nvim/version.h')
+  local status, res = pcall(function() return lib.version_cflags end)
+  if status then
+    return ffi.string(res):match('-fsanitize=[a-z,]*address')
+  else
+    return false
+  end
+end
+
 local module = {
   cimport = cimport,
   cppimport = cppimport,
@@ -876,6 +886,7 @@ local module = {
   ptr2addr = ptr2addr,
   ptr2key = ptr2key,
   debug_log = debug_log,
+  is_asan = is_asan,
 }
 module = global_helpers.tbl_extend('error', module, global_helpers)
 return function()
diff --git a/test/unit/marktree_spec.lua b/test/unit/marktree_spec.lua
index 3c96bc5f58..32300c167c 100644
--- a/test/unit/marktree_spec.lua
+++ b/test/unit/marktree_spec.lua
@@ -87,13 +87,18 @@ local function dosplice(tree, shadow, start, old_extent, new_extent)
   shadowsplice(shadow, start, old_extent, new_extent)
 end
 
+local ns = 10
 local last_id = nil
 
-local function put(tree, row, col, gravitate)
+local function put(tree, row, col, gravitate, end_row, end_col, end_gravitate)
   last_id = last_id + 1
   local my_id = last_id
 
-  lib.marktree_put_test(tree, my_id, row, col, gravitate);
+  end_row = end_row or -1
+  end_col = end_col or -1
+  end_gravitate = end_gravitate or false
+
+  lib.marktree_put_test(tree, ns, my_id, row, col, gravitate, end_row, end_col, end_gravitate);
   return my_id
 end
 
@@ -102,7 +107,7 @@ describe('marktree', function()
     last_id = 0
   end)
 
- itp('works', function()
+  itp('works', function()
     local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit
     local shadow = {}
     local iter = ffi.new("MarkTreeIter[1]")
@@ -129,7 +134,7 @@ describe('marktree', function()
     eq({}, id2pos)
 
     for i,ipos in pairs(shadow) do
-      local p = lib.marktree_lookup_ns(tree, -1, i, false, iter)
+      local p = lib.marktree_lookup_ns(tree, ns, i, false, iter)
       eq(ipos[1], p.pos.row)
       eq(ipos[2], p.pos.col)
       local k = lib.marktree_itr_current(iter)
@@ -210,10 +215,224 @@ describe('marktree', function()
 
     lib.marktree_itr_get(tree, 10, 10, iter)
     lib.marktree_del_itr(tree, iter, false)
-    eq(11, iter[0].node.key[iter[0].i].pos.col)
+    eq(11, iter[0].x.key[iter[0].i].pos.col)
 
     lib.marktree_itr_get(tree, 11, 11, iter)
     lib.marktree_del_itr(tree, iter, false)
-    eq(12, iter[0].node.key[iter[0].i].pos.col)
- end)
+    eq(12, iter[0].x.key[iter[0].i].pos.col)
+  end)
+
+  itp("'intersect_mov' function works correctly", function()
+    local function mov(x, y, w)
+      local xa = ffi.new("uint64_t[?]", #x)
+      for i, xi in ipairs(x) do xa[i-1] = xi end
+      local ya = ffi.new("uint64_t[?]", #y)
+      for i, yi in ipairs(y) do ya[i-1] = yi end
+      local wa = ffi.new("uint64_t[?]", #w)
+      for i, wi in ipairs(w) do wa[i-1] = wi end
+
+      local dummy_size = #x + #y + #w
+      local wouta = ffi.new("uint64_t[?]", dummy_size)
+      local douta = ffi.new("uint64_t[?]", dummy_size)
+      local wsize = ffi.new("size_t[1]")
+      wsize[0] = dummy_size
+      local dsize = ffi.new("size_t[1]")
+      dsize[0] = dummy_size
+
+      local status = lib.intersect_mov_test(xa, #x, ya, #y, wa, #w, wouta, wsize, douta, dsize)
+      if status == 0 then error'wowza' end
+
+      local wout, dout = {}, {}
+      for i = 0,tonumber(wsize[0])-1 do table.insert(wout, tonumber(wouta[i])) end
+      for i = 0,tonumber(dsize[0])-1 do table.insert(dout, tonumber(douta[i])) end
+      return {wout, dout}
+    end
+
+    eq({{}, {}}, mov({}, {2, 3}, {2, 3}))
+    eq({{2, 3}, {}}, mov({}, {}, {2, 3}))
+    eq({{2, 3}, {}}, mov({2, 3}, {}, {}))
+    eq({{}, {2,3}}, mov({}, {2,3}, {}))
+
+    eq({{1, 5}, {}}, mov({1,2,5}, {2, 3}, {3}))
+    eq({{1, 2}, {}}, mov({1,2,5}, {5, 10}, {10}))
+    eq({{1, 2}, {5}}, mov({1,2}, {5, 10}, {10}))
+    eq({{1,3,5,7,9}, {2,4,6,8,10}}, mov({1,3,5,7,9}, {2,4,6,8,10}, {}))
+    eq({{1,3,5,7,9}, {2,6,10}}, mov({1,3,5,7,9}, {2,4,6,8,10}, {4, 8}))
+    eq({{1,4,7}, {2,5,8}}, mov({1,3,4,6,7,9}, {2,3,5,6,8,9}, {}))
+    eq({{1,4,7}, {}}, mov({1,3,4,6,7,9}, {2,3,5,6,8,9}, {2,5,8}))
+    eq({{0,1,4,7,10}, {}}, mov({1,3,4,6,7,9}, {2,3,5,6,8,9}, {0,2,5,8,10}))
+  end)
+
+
+  local function check_intersections(tree)
+    lib.marktree_check(tree)
+    -- to debug stuff disable this branch
+    if true == true then
+      ok(lib.marktree_check_intersections(tree))
+      return
+    end
+
+    local str1 = lib.mt_inspect(tree, true, true)
+    local dot1 = ffi.string(str1.data, str1.size)
+
+    local val = lib.marktree_check_intersections(tree)
+    if not val then
+      local str2 = lib.mt_inspect(tree, true, true)
+      local dot2 = ffi.string(str2.data, str2.size)
+      print("actual:\n\n".."Xafile.dot".."\n\nexpected:\n\n".."Xefile.dot".."\n")
+      print("nivå", tree[0].root.level);
+      io.stdout:flush()
+      local afil = io.open("Xafile.dot", "wb")
+      afil:write(dot1)
+      afil:close()
+      local efil = io.open("Xefile.dot", "wb")
+      efil:write(dot2)
+      efil:close()
+      ok(false)
+    else
+      ffi.C.xfree(str1.data)
+    end
+  end
+
+  itp('works with intersections', function()
+    local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit
+
+    local ids = {}
+
+    for i = 1,80 do
+      table.insert(ids, put(tree, 1, i, false, 2, 100-i, false))
+      check_intersections(tree)
+    end
+    for i = 1,80 do
+      lib.marktree_del_pair_test(tree, ns, ids[i])
+      check_intersections(tree)
+    end
+    ids = {}
+
+    for i = 1,80 do
+      table.insert(ids, put(tree, 1, i, false, 2, 100-i, false))
+      check_intersections(tree)
+    end
+
+    for i = 1,10 do
+      for j = 1,8 do
+        local ival = (j-1)*10+i
+        lib.marktree_del_pair_test(tree, ns, ids[ival])
+        check_intersections(tree)
+      end
+    end
+  end)
+
+  itp('works with intersections with a big tree', 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
+
+    check_intersections(tree)
+    eq(2000, tree[0].n_keys)
+    ok(tree[0].root.level >= 2)
+
+    local iter = ffi.new("MarkTreeIter[1]")
+
+    local k = 0
+    for i = 1,20 do
+      for j = 1,50 do
+        k = k + 1
+        local ival = (j-1)*20+i
+        if false == true then -- if there actually is a failure, this branch will fail out at the actual spot of the error
+          lib.marktree_lookup_ns(tree, ns, ids[ival], false, iter)
+          lib.marktree_del_itr(tree, iter, false)
+          check_intersections(tree)
+
+          lib.marktree_lookup_ns(tree, ns, ids[ival], true, iter)
+          lib.marktree_del_itr(tree, iter, false)
+          check_intersections(tree)
+        else
+          lib.marktree_del_pair_test(tree, ns, ids[ival])
+          if k % 5 == 1 then
+            check_intersections(tree)
+          end
+        end
+      end
+    end
+
+    eq(0, tree[0].n_keys)
+  end)
+
+  itp('works with intersections with a even bigger tree', function()
+    local tree = ffi.new("MarkTree[1]") -- zero initialized by luajit
+
+    local ids = {}
+
+    -- 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)
+          table.insert(ids, id)
+          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)
+
+    local iter = ffi.new("MarkTreeIter[1]")
+    local pair = ffi.new("MTPair[1]")
+    for i = 1,10 do
+      -- use array as set and not {[id]=true} map, to detect duplicates
+      local set = {}
+      eq(true, ffi.C.marktree_itr_get_overlap(tree, i, 0, iter))
+      while ffi.C.marktree_itr_step_overlap(tree, iter, pair) do
+        local id = tonumber(pair[0].start.id)
+        table.insert(set, id)
+      end
+      table.sort(set)
+      eq(at_row[i], set)
+    end
+
+    k = 0
+    for i = 1,100 do
+      for j = 1,(10*size_factor) do
+        k = k + 1
+        local ival = (j-1)*100+i
+        lib.marktree_del_pair_test(tree, ns, ids[ival])
+        -- just a few stickprov, if there is trouble we need to check
+        -- everyone using the code in the "big tree" case above
+        if k % 100*size_factor == 0 or (k > 3000 and k % 200 == 0) then
+          check_intersections(tree)
+        end
+      end
+    end
+
+    eq(0, tree[0].n_keys)
+  end)
 end)