-
-
Notifications
You must be signed in to change notification settings - Fork 5.4k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
fix(vim.iter): enable optimizations for arrays (lists with holes) #28781
Conversation
The optimizations that vim.iter uses for array-like tables don't strictly require that the underlying table has no holes. We track the head and tail positions manually and don't depend on the length operator, so holes don't present an issue. The only thing that needs to change is the determination if a table is "list-like": rather than requiring consecutive, integer keys, we can simply test for integer keys only.
Luckily, we have a function for that as well: |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Fantastic!
Does this potentially (in the future) expand the capabilities of pipelines to work on array-like stuff? For reference, currently we have defined :help list-iterator
and various pipeline operations say that they require that, in their docstrings.
This enables the whole vim.iter API to work with "array like" tables (i.e. lists with holes). If everything eventually uses vim.iter under the hood we could probably even relax the distinction between "list" and "array" (since both would be treated the same by the vim.iter API). It's still an important distinction though because Lua itself treats the two differently. |
runtime/lua/vim/iter.lua
Outdated
end | ||
return ListIter.new(t) | ||
return ArrayIter.new(t, length) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
IIUC, the length
parameter is the key improvement. But it looks like we're also changing t[k]
to store the original (non-contiguous) number keys; will that cause any problems for ArrayIter:next()
?
Do we actually need the original number keys, or would it make sense to store t
as a 1..n continguous "list" (as we did before)? Possibly I'm missing something, and maybe we need the number keys for get()
-like functionality, or maybe we want to pass the number keys as k
arg to the pipeline functions.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I think this could go either way. If we keep the non-contiguous keys in the new array, then we have the property that vim.iter(t):totable() == t
(holes and all). If we "strip" holes implicitly, then vim.iter(t):totable()
serves the same purpose that people are using vim.tbl_flatten()
for today in some cases (i.e. removing holes from an array).
I think I slightly favor stripping holes, if for no other reason than arrays with holes are so fraught in Lua that it's easier to avoid them as much as possible (eliminates all kinds of edge cases).
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
If we keep the non-contiguous keys in the new array, then we have the property that
vim.iter(t):totable() == t
(holes and all)
That seems desirable. OTOH, to preserve the non-contiguous keys the caller also has the option of passing vim.iter(pairs(t))
, right?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
That's right. Another benefit of stripping holes is that any functions used in the iterator can behave consistently for both arrays and function iterators. A function iterator will never return nil
(nil
is the signal that the function iterator is done), so if we strip holes in arrays then we preserve that property.
vim.iter(s):filter(function(v)
-- v can never be nil, regardless of the value of s
end)
I think it also makes the mental model more consistent. Right now if a pipeline stage returns nil
(e.g. :map()
) then that acts as removing an item from the iterator (future pipeline stages won't see that value). But if arrays were allowed to have nil values that would be inconsistent.
The more I think about it the more I do think that stripping nil
is the right call, but we can always change it later if I'm wrong.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
So the behavior is like the latter, i.e. vim.iter(t)
always strips holes, NOT vim.iter(t):totable() == t
; e.g. vim.iter({nil, 1, 2, nil, 3}):totable() == {1, 2, 3}
.
While I agree that what's proposed makes sense and has many benefits, I'm not 100% convinced whether this is the best choice, because: (1) vim.iter(t):totable() == t
also sounds sensible; (2) what if one wants to keep nil
for any reason (instead, use filter
explicitly to filter nil
)?
@@ -247,7 +249,7 @@ function ListIter:flatten(depth) | |||
|
|||
-- exit early if we try to flatten a dict-like table | |||
if flattened == nil then | |||
error('flatten() requires a list-like table') | |||
error('flatten() requires an array-like table') |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Due to L135:
-- short-circuit: this is not a list like table
flatten()
on lists with hole still might fail:
vim.iter({nil, {1, nil, 2}, 3}):flatten(math.huge):totable()
-- ERROR: flatten() requires an array-like table
-- Expected: {1, 2, 3}
-- BTW: vim.tbl_flatten { { 1, nil, 2 }, 3 } == { 1, 3 }. ?!?!??!?!????
For the following, an expected output could be {{1, nil, 2}, 3}
instead of an error, according to the array-like semantics:
vim.iter({nil, {1, nil, 2}, 3}):flatten():totable()
-- ERROR: flatten() requires an array-like table
where depth = 1.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Expected output of vim.iter({nil, {1, nil, 2}, 3}):flatten():totable()
should be {1, 2, 3}
.
vim.iter({nil, {1, nil, 2}, 3}):totable()
(no flatten) returns {{1, nil, 2}, 3}
. Calling flatten on that would result in {1, 2, 3}
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Oh that's right. My mistake; I was actually thinking about vim.iter(**{** {nil, {1, nil, 2}, 3} **}** ):flatten(1):totable()
(one more depth) == { {1, nil, 3}, 3 }
. So the current implementation after the update seems correct: no longer errors.
…8781) The optimizations that vim.iter uses for array-like tables don't require that the source table has no holes. The only thing that needs to change is the determination if a table is "list-like": rather than requiring consecutive, integer keys, we can simply test for (positive) integer keys only, and remove any holes in the original array when we make a copy for the iterator. (cherry picked from commit 4c0d18c)
Successfully created backport PR for |
* version bump * docs: news neovim#28773 * perf(treesitter): use child_containing_descendant() in has-ancestor? (neovim#28512) Problem: `has-ancestor?` is O(n²) for the depth of the tree since it iterates over each of the node's ancestors (bottom-up), and each ancestor takes O(n) time. This happens because tree-sitter's nodes don't store their parent nodes, and the tree is searched (top-down) each time a new parent is requested. Solution: Make use of new `ts_node_child_containing_descendant()` in tree-sitter v0.22.6 (which is now the minimum required version) to rewrite the `has-ancestor?` predicate in C to become O(n). For a sample file, decreases the time taken by `has-ancestor?` from 360ms to 6ms. * feat: remove deprecated features Remove following functions: - vim.lsp.util.extract_completion_items - vim.lsp.util.get_progress_messages - vim.lsp.util.parse_snippet() - vim.lsp.util.text_document_completion_list_to_complete_items - LanguageTree:for_each_child - health#report_error - health#report_info - health#report_ok - health#report_start - health#report_warn - vim.health.report_error - vim.health.report_info - vim.health.report_ok - vim.health.report_start - vim.health.report_warn * fix(version): fix vim.version().prerelease fixes neovim#28782 (when backported) * fix: extend the life of vim.tbl_flatten to 0.13 `vim.iter(t):flatten():totable()` doesn't handle nil so isn't a good enough replacement. * docs(gen_help_html.lua): handle modeline and note nodes Problem: 'modeline' and 'note' are unhandled in the online HTML documentation. Some (not all) modelines are parsed by the vimdoc parser as a node of type 'modeline'. Solution: - Ignore 'modeline' in HTML rendering. - Render 'note' text in boldface. * fix(health): broken ruby detect neovim#28804 * fix(path): avoid chdir() when resolving path (neovim#28799) Use uv_fs_realpath() instead. It seems that uv_fs_realpath() has some problems on non-Linux platforms: - macOS and other BSDs: this function will fail with UV_ELOOP if more than 32 symlinks are found while resolving the given path. This limit is hardcoded and cannot be sidestepped. - Windows: while this function works in the common case, there are a number of corner cases where it doesn't: - Paths in ramdisk volumes created by tools which sidestep the Volume Manager (such as ImDisk) cannot be resolved. - Inconsistent casing when using drive letters. - Resolved path bypasses subst'd drives. Ref: https://docs.libuv.org/en/v1.x/fs.html#c.uv_fs_realpath I don't know if the old implementation that uses uv_chdir() and uv_cwd() also suffers from the same problems. - For the ELOOP case, chdir() seems to have the same limitations. - On Windows, Vim doesn't use anything like chdir() either. It uses _wfullpath(), while libuv uses GetFinalPathNameByHandleW(). * feat(api): broadcast events to ALL channels neovim#28487 Problem: `vim.rpcnotify(0)` and `rpcnotify(0)` are documented as follows: If {channel} is 0, the event is broadcast to all channels. But that's not actually true. Channels must call `nvim_subscribe` to receive "broadcast" events, so it's actually "multicast". - Assuming there is a use-case for "broadcast", the current model adds an extra step for broadcasting: all channels need to "subscribe". - The presence of `nvim_subscribe` is a source of confusion for users, because its name implies something more generally useful than what it does. Presumably the use-case of `nvim_subscribe` is to avoid "noise" on RPC channels not expected a broadcast notification, and potentially an error if the channel client reports an unknown event. Solution: - Deprecate `nvim_subscribe`/`nvim_unsubscribe`. - If applications want to multicast, they can keep their own multicast list. Or they can use `nvim_list_chans()` and `nvim_get_chan_info()` to enumerate and filter the clients they want to target. - Always send "broadcast" events to ALL channels. Don't require channels to "subscribe" to receive broadcasts. This matches the documented behavior of `rpcnotify()`. * vim-patch:9.1.0414: Unable to leave long line with 'smoothscroll' and 'scrolloff' Problem: Unable to leave long line with 'smoothscroll' and 'scrolloff'. Corrupted screen near the end of a long line with 'scrolloff'. (Ernie Rael, after 9.1.0280) Solution: Only correct cursor in case scroll_cursor_bot() was not itself called to make the cursor visible. Avoid adjusting for 'scrolloff' beyond the text line height (Luuk van Baal) vim/vim@b32055e vim-patch:9.1.0416: some screen dump tests can be improved Problem: some screen dump tests can be improved (after 9.1.0414) Solution: Make sure screen state changes properly and is captured in the screen dumps (Luuk van Baal) vim/vim@2e64273 * fix(vim.iter): enable optimizations for arrays (lists with holes) (neovim#28781) The optimizations that vim.iter uses for array-like tables don't require that the source table has no holes. The only thing that needs to change is the determination if a table is "list-like": rather than requiring consecutive, integer keys, we can simply test for (positive) integer keys only, and remove any holes in the original array when we make a copy for the iterator. * ci: change label `backport` to `target:release` `backport` is too similar `ci:backport release-x.y` and causes confusion. * fix(move): half-page scrolling with resized grid at eob (neovim#28821) * vim-patch:9.1.0418: Cannot move to previous/next rare word (neovim#28822) Problem: Cannot move to previous/next rare word (Colin Kennedy) Solution: Add the ]r and [r motions (Christ van Willegen) fixes: vim/vim#14773 closes: vim/vim#14780 vim/vim@8e4c4c7 Co-authored-by: Christ van Willegen - van Noort <github.com@vanwillegen-vannoort.nl> * vim-patch:cf78d0df51f2 runtime(sshdconfig): add basic ftplugin file for sshdconfig (vim/vim#14790) vim/vim@cf78d0d Co-authored-by: Yinzuo Jiang <jiangyinzuo@foxmail.com> * vim-patch:94043780196c (neovim#28831) runtime(matchparen): fix :NoMatchParen not working (vim/vim#14797) fixes: neovim#28828 vim/vim@9404378 * refactor(path.c): add nonnull attributes (neovim#28829) This possibly fixes the coverity warning. * refactor!: remove `nvim` and `provider` module for checkhealth The namespacing for healthchecks for neovim modules is inconsistent and confusing. The completion for `:checkhealth` with `--clean` gives ``` nvim provider.clipboard provider.node provider.perl provider.python provider.ruby vim.lsp vim.treesitter ``` There are now three top-level module names for nvim: `nvim`, `provider` and `vim` with no signs of stopping. The `nvim` name is especially confusing as it does not contain all neovim checkhealths, which makes it almost a decoy healthcheck. The confusion only worsens if you add plugins to the mix: ``` lazy mason nvim nvim-treesitter provider.clipboard provider.node provider.perl provider.python provider.ruby telescope vim.lsp vim.treesitter ``` Another problem with the current approach is that it's not easy to run nvim-only healthchecks since they don't share the same namespace. The current approach would be to run `:che nvim vim.* provider.*` and would also require the user to know these are the neovim modules. Instead, use this alternative structure: ``` vim.health vim.lsp vim.provider.clipboard vim.provider.node vim.provider.perl vim.provider.python vim.provider.ruby vim.treesitter ``` and ``` lazy mason nvim-treesitter telescope vim.health vim.lsp vim.provider.clipboard vim.provider.node vim.provider.perl vim.provider.python vim.provider.ruby vim.treesitter ``` Now, the entries are properly sorted and running nvim-only healthchecks requires running only `:che vim.*`. * fix(diagnostic): show backtrace for deprecation warnings Problem: On nvim 11.0-dev, deprecation warnings due to an use of hard-deprecated APIs such as: - `vim.diagnostic.disable()` - `vim.diagnostic.is_disabled()` etc. are not accompanied by backtrace information. It makes difficult for users to figure out which lines or which plugins are still using deprecated APIs. Solution: use `backtrace = true` in vim.deprecate() call. * vim-patch:df859a36d390 runtime(sql): set commentstring for sql files in ftplugin closes: vim/vim#14800 vim/vim@df859a3 Co-authored-by: Riley Bruins <ribru17@hotmail.com> * vim-patch:36e974fdf3f5 runtime(graphql): basic ftplugin file for graphql closes: vim/vim#14801 vim/vim@36e974f Co-authored-by: Riley Bruins <ribru17@hotmail.com> * vim-patch:4d7892bfb1db runtime(dart): add basic dart ftplugin file fixes vim/vim#14793 closes vim/vim#14802 vim/vim@4d7892b Co-authored-by: Riley Bruins <ribru17@hotmail.com> * vim-patch:9.1.0421: filetype: hyprlang files are not recognized Problem: filetype: hyprlang files are not recognized Solution: recognize 'hypr{land,paper,idle,lock}.conf' files as 'hyprlang' filetype, add hyprlang ftplugin (Riley Bruins) closes: vim/vim#14803 vim/vim@5f1b115 Co-authored-by: Riley Bruins <ribru17@hotmail.com> * Update CMakeLists.txt * Create health.lua --------- Co-authored-by: Justin M. Keyes <justinkz@gmail.com> Co-authored-by: vanaigr <vanaigranov@gmail.com> Co-authored-by: dundargoc <gocdundar@gmail.com> Co-authored-by: bfredl <bjorn.linse@gmail.com> Co-authored-by: Lewis Russell <lewis6991@gmail.com> Co-authored-by: Jongwook Choi <wookayin@gmail.com> Co-authored-by: MoonFruit <dkmoonfruit@gmail.com> Co-authored-by: zeertzjq <zeertzjq@outlook.com> Co-authored-by: Luuk van Baal <luukvbaal@gmail.com> Co-authored-by: Gregory Anders <8965202+gpanders@users.noreply.github.com> Co-authored-by: Christ van Willegen - van Noort <github.com@vanwillegen-vannoort.nl> Co-authored-by: Christian Clason <c.clason@uni-graz.at> Co-authored-by: Yinzuo Jiang <jiangyinzuo@foxmail.com> Co-authored-by: Riley Bruins <ribru17@hotmail.com>
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Opened an issue #28941 to discuss splitting out ArrayIter
.
local v = src[count] | ||
if v == nil then | ||
-- O(n): scan the source table to decide if it is an array (only positive integer indices). | ||
for k, v in pairs(src) do |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I forgot that vim.ter
did a full scan and table allocation of the source.
Surely this means for single (or even few) operations on a very large tables, that vim.iter
is unfavourable when compared to the existing vim.tbl_*
functions?
I'm thinking about this in context to treesitter, that needs to be able to scan large region tables.
…ovim#28781) The optimizations that vim.iter uses for array-like tables don't require that the source table has no holes. The only thing that needs to change is the determination if a table is "list-like": rather than requiring consecutive, integer keys, we can simply test for (positive) integer keys only, and remove any holes in the original array when we make a copy for the iterator.
The optimizations that vim.iter uses for array-like tables don't strictly require that the underlying table has no holes. The only thing that needs to change is the determination if a table is "list-like": rather than requiring consecutive, integer keys, we can simply test for integer keys only, and remove any holes in the original array when we make a copy for the iterator.
This allows
vim.iter(t):flatten():totable()
to work as a proper replacement forvim.tbl_flatten
.Fixes #28777.