| Age | Commit message (Collapse) | Author | Files |
|---|
|
Previous implementation used a full sort but this is unnecessary. Pairs
do not need to be processed in id-order, all that we did was make
"start" and "end" marks find each other. This can be done with a hash
table instead. The "grow only" khash_t mentioned in the TODO is
the since long merged #24985 5970157e refactor with dense value array,
to not regress on memory locality.
|
|
fix #37867
This bug happens when only one end is moved between different nodes,
but the other end is also moved but within the same node.
When this happens we need the correct previous position even for the
internal move. This code shall be refactored to make the intent clearer,
(and avoid some unnecessary processing) but this is a fix for the observable
bug.
Thanks to KevinGoodsell for providing a deterministic
reproduce using fuzzing techniques.
|
|
These are not needed after #35129 but making uncrustify still play nice
with them was a bit tricky.
Unfortunately `uncrustify --update-config-with-doc` breaks strings
with backslashes. This issue has been reported upstream,
and in the meanwhile auto-update on every single run has been disabled.
|
|
Workaround (not a fix) for #27196 and for #33067
Asserts are meant to apply to debug builds but not release
builds for users. However the intermediate RelWithDebInfo
build type is quite often used by end users, so we might
want to disable certain problematic asserts there, while
still preserving them in Debug mode for CI.
|
|
Implement an extmark property that conceals lines vertically.
|
|
In order to run the marktree unit test in release mode, the test functions need to be available even when NDEBUG is defined.
Keep the body of marktree_check a nop during release builds, which limits the usefulness of the testing, but at least lets the tests run.
|
|
Problem: Marktree meta count still includes invalidated marks, making
guards that check the meta total ineffective.
Solution: Revise marktree metadata when in/revalidating a mark.
|
|
ref https://github.com/neovim/neovim/pull/28432
ref https://github.com/neovim/neovim/issues/28469
|
|
Co-authored-by: C.D. MacEachern <craig.daniel.maceachern@gmail.com>
Co-authored-by: Ynda Jas <yndajas@gmail.com>
Co-authored-by: Owen Hines <TheOdd@users.noreply.github.com>
Co-authored-by: Wanten <41904684+WantenMN@users.noreply.github.com>
Co-authored-by: lukasvrenner <118417051+lukasvrenner@users.noreply.github.com>
Co-authored-by: cuinix <915115094@qq.com>
|
|
fixes #27046
|
|
Co-authored-by: zeertzjq <zeertzjq@outlook.com>
|
|
fixes #27211
|
|
|
|
fixes #27137
|
|
This expands on the global "don't pay for what you don't use" rules for
these special extmark decorations:
- inline virtual text, which needs to be processed in plines.c when we
calculate the size of text on screen
- virtual lines, which are needed when calculating "filler" lines
- signs, with text and/or highlights, both of which needs to be
processed for the entire line already at the beginning of a line.
This adds a count to each node of the marktree, for how many special
marks of each kind can be found in the subtree for this node. This makes
it possible to quickly skip over these extra checks, when working in
regions of the buffer not containing these kind of marks, instead of
before where this could just be skipped if the entire _buffer_
didn't contain such marks.
|
|
Avoids checking for invalid mark at callsite.
|
|
Remove `export` pramgas from defs headers as it causes IWYU to believe
that the definitions from the defs headers comes from main header, which
is not what we really want.
|
|
Reference: https://github.com/neovim/neovim/issues/6371.
|
|
Specifically, specify that each initialization should be done on a
separate line.
|
|
|
|
Discovered using __sanitizer_print_memory_profile().
|
|
|
|
|
|
|
|
|
|
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
|
|
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.
|
|
- reduce variable scope
- prefer initialization over declaration and assignment
|
|
|
|
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.
|
|
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.
|
|
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.
|
|
Co-authored-by: Wansmer <wansmer@gmail.com>
Co-authored-by: Andrew Voynov <andrewvoynov.b@gmail.com>
Co-authored-by: David Moberg <david.moberg@mediatek.com>
|
|
> 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
|
|
|
|
`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
|
|
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
|
|
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.
|
|
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.
|
|
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.
|
|
Notable changes: replace all infinite loops to `while(true)` and remove
`int` from `unsigned int`.
|
|
|
|
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
|
|
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.
|
|
|
|
Allow Include What You Use to remove unnecessary includes and only
include what is necessary. This helps with reducing compilation times
and makes it easier to visualise which dependencies are actually
required.
Work on https://github.com/neovim/neovim/issues/549, but doesn't close
it since this only works fully for .c files and not headers.
|
|
It's confusing to mix vendored dependencies with neovim source code. A
clean separation is simpler to keep track of and simpler to document.
|
|
related vim-8.2.{4402,4639}
|
|
|
|
Work on https://github.com/neovim/neovim/issues/567
|
