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.

1 files changed, 17 insertions, 1 deletions

diff --git a/runtime/lua/vim/_meta/api.lua b/runtime/lua/vim/_meta/api.lua
index bfff16933a..7cd0d825a1 100644
--- a/runtime/lua/vim/_meta/api.lua
+++ b/runtime/lua/vim/_meta/api.lua
@@ -7,6 +7,13 @@ vim.api = {}
 
 --- @private
 --- @param buffer integer
+--- @param keys boolean
+--- @param dot boolean
+--- @return string
+function vim.api.nvim__buf_debug_extmarks(buffer, keys, dot) end
+
+--- @private
+--- @param buffer integer
 --- @param first integer
 --- @param last integer
 function vim.api.nvim__buf_redraw_range(buffer, first, last) end
@@ -313,6 +320,9 @@ function vim.api.nvim_buf_get_extmark_by_id(buffer, ns_id, id, opts) end
 --- ```
 --- If `end` is less than `start`, traversal works backwards. (Useful with
 --- `limit`, to get the first marks prior to a given position.)
+--- Note: when using extmark ranges (marks with a end_row/end_col position)
+--- the `overlap` option might be useful. Otherwise only the start position of
+--- an extmark will be considered.
 --- Example:
 --- ```lua
 ---   local api = vim.api
@@ -337,11 +347,13 @@ function vim.api.nvim_buf_get_extmark_by_id(buffer, ns_id, id, opts) end
 --- @param end_ any End of range (inclusive): a 0-indexed (row, col) or valid
 ---               extmark id (whose position defines the bound).
 ---               `api-indexing`
---- @param opts table<string,any> Optional parameters. Keys:
+--- @param opts vim.api.keyset.get_extmarks Optional parameters. Keys:
 ---               • limit: Maximum number of marks to return
 ---               • details: Whether to include the details dict
 ---               • hl_name: Whether to include highlight group name instead
 ---                 of id, true if omitted
+---               • overlap: Also include marks which overlap the range, even
+---                 if their start position is less than `start`
 ---               • type: Filter marks by type: "highlight", "sign",
 ---                 "virt_text" and "virt_lines"
 --- @return any[]
@@ -457,6 +469,10 @@ function vim.api.nvim_buf_line_count(buffer) end
 --- waiting for the return value.)
 --- Using the optional arguments, it is possible to use this to highlight a
 --- range of text, and also to associate virtual text to the mark.
+--- If present, the position defined by `end_col` and `end_row` should be
+--- after the start position in order for the extmark to cover a range. An
+--- earlier end position is not an error, but then it behaves like an empty
+--- range (no highlighting).
 ---
 --- @param buffer integer Buffer handle, or 0 for current buffer
 --- @param ns_id integer Namespace id from `nvim_create_namespace()`