[vim/vim] [FEATURE REQUEST] A solution for getting all the text properties in a buffer (Issue #9128)

[Boris Staletic]

prop_list_profile.txt

The problem

If a plugin wants to grab all of the previously placed text properties that the same plugin has placed, the current prop_list requires some work:

1. Loop over the lines of the buffer.
2. Grab all the text properties from each line and aggregate in some list.
3. Filter out all properties that are not produced by the plugin. A plugin might need to grab two types of properties, so making vim filter by type isn't perfect either.

This results in a ton of vimscript API calls and is a similar thing to what lead to #8675.

Basically, what a plugin is running is this:

function! g:UpdateMatches()

  let properties = []

  for line in range( line('$') )

    call extend(properties, filter(prop_list( line + 1, { 'bufnr': 1 } ), 'v:val[ "type" ][ :3 ] ==# "Ycm"' ))

  endfor

endfunction

The profile is here: https://gist.github.com/bstaletic/84c10b75be93c99f321a27af73278a8d

The neovim API

I'm not the biggest fan of neovim, but its API here is really nice.

Each plugin gets a unique namespace ID. Then, when getting (neovim's equivalent of) all the properties in a buffer, besides the buffer number, the ID is passed as well. Introducing this namespace ID thing to text property APIs would be perfect. Vim's sign_foo() family of functions already has the group thing.

Alternative

A simpler solution is just introducing something like prop_list_range(), where not only a single line would be passed, but rather a range of lines. That way plugins could request all text properties from line N to line M. It would still leave filtering to the users.

Note that the two ideas aren't exactly exclusive.

Context

I'm a maintainer of YouCompleteMe. The way YCM updates text properties for a specific buffer is basically described in the "problem" section. In more detail:

• We define two property types: https://github.com/ycm-core/YouCompleteMe/blob/master/autoload/youcompleteme.vim#L418-L433
• When we update the diagnostics, we do it like this:
  • First, we grab all placed properties
  • For each new diagnostic
  • if the exact same has already been placed, just skip
  • else, place a new one
    • Could be optimized with prop_add_list(). In the TODO list.
  • Once we have skipped all the ones we want to keep and added the new ones, what remains is to remove the stale ones
    • There's no batch remove of properties, but so far that hasn't been a problem.

The algorithm is made that way, because in common cases it's faster than removing all old and then placing all new - i.e. paying attention to overlap between the two sets is beneficial.

 

But I digress. The problem is that call to vimsupport.GetTextProperties( bufnr ). It's defined here:

https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/vimsupport.py#L213-L226

Doing that on an extra long file is very inefficient. For a file that is 1'010'000 lines long, with no props either placed, or to place (i.e. all work is in GetTextProperties()), it takes ~1 minute on my machine.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub.
Triage notifications on the go with GitHub Mobile for iOS or Android.

[Boris Staletic]

One more possible alternative is "get all props of type N in buffer B". That way a plugin like YCM could get all the properties in just two vim.eval() calls.

[Yegappan Lakshmanan]

Hi,

On Fri, Nov 12, 2021 at 5:45 AM Boris Staletic <vim-dev...@256bit.org> wrote:

prop_list_profile.txt

The problem

If a plugin wants to grab all of the previously placed text properties that the same plugin has placed, the current prop_list requires some work:

1. Loop over the lines of the buffer.
2. Grab all the text properties from each line and aggregate in some list.
3. Filter out all properties that are not produced by the plugin. A plugin might need to grab two types of properties, so making vim filter by type isn't perfect either.

How are you using the property dict value returned by prop_list()? I see that you cannot

modify the value returned by prop_list() and then update the text property by using

the prop_add() or the prop_add_list() function.

BTW, I have implemented the prop_list_range() function to return the list of text

properties placed on a range of lines in a specified buffer:

https://github.com/yegappan/vim/tree/textprop

But I am trying to understand how the returned value will be used. If you have a text

property that spans multiple lines, then you cannot simply modify the value returned

by prop_list_range() and place the text properties again.

Regards,

Yegappan

[vim-dev ML]

Hi,

On Fri, Nov 12, 2021 at 5:45 AM Boris Staletic ***@***.***>
wrote:

> prop_list_profile.txt
> <https://github.com/vim/vim/files/7527900/prop_list_profile.txt>

> The problem
>
> If a plugin wants to grab all of the previously placed text properties
> that the same plugin has placed, the current prop_list requires some work:
>

> 1. Loop over the lines of the buffer.
> 2. Grab all the text properties from each line and aggregate in some
> list.
> 3. Filter out all properties that are not produced by the plugin. A

> plugin might need to grab two types of properties, so making vim filter by
> type isn't perfect either.
>
>

How are you using the property dict value returned by prop_list()? I see
that you cannot
modify the value returned by prop_list() and then update the text property
by using
the prop_add() or the prop_add_list() function.

BTW, I have implemented the prop_list_range() function to return the list
of text
properties placed on a range of lines in a specified buffer:

https://github.com/yegappan/vim/tree/textprop

But I am trying to understand how the returned value will be used. If you
have a text
property that spans multiple lines, then you cannot simply modify the value
returned
by prop_list_range() and place the text properties again.

Regards,
Yegappan


>
>

> This results in a ton of vimscript API calls and is a similar thing to

> what lead to #8675 <https://github.com/vim/vim/issues/8675>.

> - We define two property types:
> https://github.com/ycm-core/YouCompleteMe/blob/master/autoload/youcompleteme.vim#L418-L433
> - When we update the diagnostics, we do it like this:
> - First, we grab all placed properties
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L133>
> - For each new diagnostic
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L137>
> - if the exact same has already been placed, just skip
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L149>
> - else, place a new one
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L151-L156>
> - Could be optimized with prop_add_list(). In the TODO list.
> - Once we have skipped all the ones we want to keep and added the

> new ones, what remains is to remove the stale ones

> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L158-L159>
> - There's no batch remove of properties, but *so far* that

[Bram Moolenaar]

> [prop_list_profile.txt](https://github.com/vim/vim/files/7527900/prop_list_profile.txt)
> #### The problem

>
> If a plugin wants to grab all of the previously placed text properties that the same plugin has placed, the current `prop_list` requires some work:
>

> 1. Loop over the lines of the buffer.
> 2. Grab all the text properties from each line and aggregate in some list.
> 3. Filter out all properties that are not produced by the plugin. A plugin might need to grab two types of properties, so making vim filter by `type` isn't perfect either.
>
> This results in a ton of vimscript API calls and is a similar thing to what lead to https://github.com/vim/vim/issues/8675.

>
> Basically, what a plugin is running is this:
>

> ```viml

> function! g:UpdateMatches()
> let properties = []
> for line in range( line('$') )
> call extend(properties, filter(prop_list( line + 1, { 'bufnr': 1 } ), 'v:val[ "type" ][ :3 ] ==# "Ycm"' ))
> endfor
> endfunction
> ```
> The profile is here: https://gist.github.com/bstaletic/84c10b75be93c99f321a27af73278a8d
>

> ### The neovim API

>
> I'm not the biggest fan of neovim, but its API here is really nice.
>
> Each plugin gets a unique namespace ID. Then, when getting (neovim's equivalent of) all the properties in a buffer, besides the buffer number, the ID is passed as well. Introducing this namespace ID thing to text property APIs would be perfect. Vim's `sign_foo()` family of functions already has the `group` thing.
>

> #### Alternative
>
> A simpler solution is just introducing something like `prop_list_range()`, where not only a single line would be passed, but rather a range of lines. That way plugins could request all text properties from line N to line M. It would still leave filtering to the users.

>
> Note that the two ideas aren't exactly exclusive.
>

> #### Context

>
> I'm a maintainer of YouCompleteMe. The way YCM updates text properties for a specific buffer is basically described in the "problem" section. In more detail:
>

> - We define two property types: https://github.com/ycm-core/YouCompleteMe/blob/master/autoload/youcompleteme.vim#L418-L433
> - When we update the diagnostics, we do it like this:
> - [First, we grab all placed properties](https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L133)
> - [For each new diagnostic](https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L137)
> - [if the exact same has already been placed, just skip](https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L149)
> - [else, place a new one](https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L151-L156)
> - Could be optimized with `prop_add_list()`. In the TODO list.
> - Once we have skipped all the ones we want to keep and added the new ones, what remains is [to remove the stale ones](https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L158-L159)
> - There's no batch remove of properties, but *so far* that hasn't been a problem.

>
> The algorithm is made that way, because in common cases it's faster than removing all old and then placing all new - i.e. paying attention to overlap between the two sets is beneficial.
>

> &nbsp;
>
> But I digress. The problem is that call to `vimsupport.GetTextProperties( bufnr )`. It's defined here:

>
> https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/vimsupport.py#L213-L226
>
> Doing that on an extra long file is very inefficient. For a file that
> is 1'010'000 lines long, with no props either placed, or to place

> (i.e. all work is in `GetTextProperties()`), it takes ~1 minute on my
> machine.

What is the overhead caused by? If it's calling prop_list() for every
line, we could add an entry in the {props} argument "linecount". Making
it very high would return properties for all lines from {lnum} to the
last line. The returned list would have "lnum" added in each entry.

If the overhead is caused by returning lots of properties that are not
related to the plugin, they are dropped when filtering, we could add a
pattern to match with "type". If you want to find two types you can use
'name_one\|name_two".

Whatever solution we pick, it is likely still slow for a very long file.
Have you considered only dealing with visible lines?

If you need a unique ID for a plugin, use the script ID of the plugin
file. It is unique, and when the plugin is reloaded it will remain the
same.

--
WOMAN: Dennis, there's some lovely filth down here. Oh -- how d'you do?
ARTHUR: How do you do, good lady. I am Arthur, King of the Britons.
Who's castle is that?
WOMAN: King of the who?
The Quest for the Holy Grail (Monty Python)

/// Bram Moolenaar -- ***@***.*** -- http://www.Moolenaar.net \\\
/// \\\
\\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///

—
You are receiving this because you commented.

[puremo...@gmail.com]

We are not trying to modify them per se, in fact we're trying _not to_.

YCM receives a batch of diagnostics, say:

  - A:  an error on line 10 spanning { 10, 4 } to { 10, 8 }.

  - B: a warning on line 13 spanning { 13,1 } to { 14, 2 }

YCM creates text props spanning those ranges with the some YcmError/YcmWarning highlight group.

Some time later, YCM receives another batch of diagnostics, perhaps the following:

  - A: an error on line 10 spanning { 10, 4 } to { 10, 8 }

  - C: an error on line 20 spanning { 20, 10 } to { 20,10 }

YCM is trying to make minimal changes to the props, ie:

 - leave A as is

 - remove B

 - add C

[puremo...@gmail.com]

Bram, we _think_ the overhead is calling prop_list for every line, and that doing that in one call spanning the whole buffer would be more efficient. (currently we're doing a request per line, filtering the result for the types that start with Ycm, then adding them to a python list).

That said, it would be certainly useful for our use case to be able to only return props of a given list of types as well. That allows us to say "return us all the properties of <these types> in <this range> of the buffer". I'd suspect that for _most_ plugin authors that they would only be interested in props that they created themselves. I can imagine scenarios where PluginA looks at PluginB's text properties, but would expect that to be the rare case rather than the norm.

I think that would be relatively faster when scanning the memlines than doing a request per-line and filtering in vimscript land.

> Whatever solution we pick, it is likely still slow for a very long file.

Yes, this is true. In fact, we already disable this functionality on very large files (the inefficiency was actually discovered because of a bug in that!); we're now more thinking about efficiency on moderate usage as that affects more users of course.

> Have you considered only dealing with visible lines?

I don't think we had considered this. Certainly this adds quite a lot of complexity - we would have to listen for scrolling events and update the properties as the user scrolls, handling there being multiple windows per buffer etc. I had previously assumed this wasn't even possible (is there an autocmd for "window scrolled"?), but I admit I haven't thought hard about it.

[Boris Staletic]

@brammool @yegappan Thanks for replying.

How are you using the property dict value returned by prop_list()?

That's over here:

1. Gathering and filtering: https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/vimsupport.py#L217-L224
2. Skipping the ones we want to keep: https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L149
3. Dropping stale ones: https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L158-L159

If you have a text property that spans multiple lines, then you cannot simply modify the value returned by prop_list_range() and place the text properties again.

I'm pretty sure we don't handle multiline properties 100% correctly. Is it okay if we ignore them for the sake of this discussion?

What is the overhead caused by? If it's calling prop_list() for every
line, we could add an entry in the {props} argument "linecount".

The test case was with zero actually placed properties, so there was nothing to actually filter. That suggests the repeated calls to prop_list() is the slow part.

As for returning (and subsequently filtering) tons of properties belonging to a different plugin, that seems like a much more unlikely situation. I'm leaning towards ignoring it until a user complains.

Whatever solution we pick, it is likely still slow for a very long file.

Yeah, for really long files we do bail out early and just refuse to even try. At least now we do - there was a bug where we tried do update text properties even for files where b:ycm_largefile was set.

Still, it feels like there should be a way to optimize the "get all props for buffer B placed by me" use case.

Have you considered only dealing with visible lines?

Can't say that I have, but it's definitely worth considering. It shouldn't even be a very intrusive change.

—
You are receiving this because you commented.

[Bram Moolenaar]

Have you tried putting the loop that calls prop_list() in a :def function? It would be interesting to know how much difference this makes.

—
You are receiving this because you commented.

[Boris Staletic]

Okay, wow... That's about 9 times faster. Scanned a buffer of million lines in about 10 seconds.

vim9-profile.txt

—
You are receiving this because you commented.

[lacygoill]

If I read the log correctly, it seems the slowest part comes from this line:

call extend(properties, filter(prop_list( line + 1, { 'bufnr': 1 } ), 'v:val[ "type" ][ : 3 ] ==# "Ycm"' ))

I don't know whether it will make a difference, but you could try to replace the eval string containing v:val with a Vim9 lambda. Something like this (untested):

properties->extend(filter(prop_list(line + 1, {bufnr: 1}), (_, v: dict<any>): bool => v['type'][: 3] == 'Ycm'))

You could also try to replace filter() with a :for loop and remove(). The reason why I say this is because sometimes a :for loop is significantly faster than map():

vim -es -Nu NONE -i NONE -U NONE -S <(cat <<'EOF'

    vim9script

    var mylist = pow(10, 6)->float2nr()->range()



    def Lambda()

        var time = reltime()

        map(mylist, (_, v) => v + 1)

        setline(1, reltime(time)->reltimestr()->matchstr('.*\..\{,3}') .. ' seconds to run Lambda()')

    enddef

    Lambda()



    def ForLoop()

        var time = reltime()

        var i = 0

        for _ in mylist

            mylist[i] = mylist[i] + 1

            i += 1

        endfor

        setline(2, reltime(time)->reltimestr()->matchstr('.*\..\{,3}') .. ' seconds to run ForLoop()')

    enddef

    ForLoop()



    :%p

    qa!

EOF

)



0.565 seconds to run Lambda()

0.169 seconds to run ForLoop()

So, maybe the same can be true for filter(); I don't know.

---

A few remarks:

• you can drop :call
• you can drop quotes around keys in a dictionary (if they match \%(\w\|-\)\+)
• you can drop the # suffix at the end of comparison operators ('ignorecase' is always ignored)

---

Here is an example of refactoring for a legacy eval string:

                                          v-----------------------v

:legacy echo getcompletion('', 'option')->filter('v:val =~ "func"')->join("\n")

→

:vim9 echo getcompletion('', 'option')->filter((_, v) => v =~ 'func')->join("\n")

                                        ^---------------------------^

---

Providing the types is not necessary, but it might improve the reliability of the code and maybe let the Vim compiler optimize it (not sure about that), which is why I wrote dict<any> and bool earlier:

properties->extend(filter(prop_list(line + 1, {bufnr: 1}), (_, v: dict<any>): bool => v['type'][: 3] == 'Ycm'))

                                                                  ^-------^   ^--^

If the type of the members of the v dictionary is more accurate, you can replace any with it. You can inspect the exact type of v with typename().

—
You are receiving this because you commented.

[Yegappan Lakshmanan]

Hi,

On Mon, Nov 15, 2021 at 7:33 AM Boris Staletic <vim-dev...@256bit.org> wrote:

@brammool @yegappan Thanks for replying.

How are you using the property dict value returned by prop_list()?

That's over here:

1. Gathering and filtering: https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/vimsupport.py#L217-L224
2. Skipping the ones we want to keep: https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L149
3. Dropping stale ones: https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L158-L159

If you have a text property that spans multiple lines, then you cannot simply modify the value returned by prop_list_range() and place the text properties again.

I'm pretty sure we don't handle multiline properties 100% correctly. Is it okay if we ignore them for the sake of this discussion?

What is the overhead caused by? If it's calling prop_list() for every
line, we could add an entry in the {props} argument "linecount".

The test case was with zero actually placed properties, so there was nothing to actually filter. That suggests the repeated calls to prop_list() is the slow part.

As for returning (and subsequently filtering) tons of properties belonging to a different plugin, that seems like a much more unlikely situation. I'm leaning towards ignoring it until a user complains.

Whatever solution we pick, it is likely still slow for a very long file.

Yeah, for really long files we do bail out early and just refuse to even try. At least now we do - there was a bug where we tried do update text properties even for files where b:ycm_largefile was set.

Still, it feels like there should be a way to optimize the "get all props for buffer B placed by me" use case.

Based on Bram's comment, I have modified the prop_list() function to accept an optional

end_lnum, type and id items in {props}. If end_lnum is specified, then the function returns

all the text properties between lnum and end_lnum. If 'type' is specified, then returns only

the text properties with type 'type' (same for 'id').

The changes are available at:

https://github.com/yegappan/vim/tree/textprop

Can you try this out?

Thanks,

Yegappan

[vim-dev ML]

Hi,

On Mon, Nov 15, 2021 at 7:33 AM Boris Staletic ***@***.***>
wrote:

> @brammool <https://github.com/brammool> @yegappan
> <https://github.com/yegappan> Thanks for replying.

>
> How are you using the property dict value returned by prop_list()?
>
> That's over here:
>

> 1. Gathering and filtering:
> https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/vimsupport.py#L217-L224
> 2. Skipping the ones we want to keep:
> https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L149
> 3. Dropping stale ones:

[Yegappan Lakshmanan]

Hi,

Patch 8.2.3652 extends the prop_list() function to support getting text properties across

multiple lines and filter them based on the text property type and identifier. Let me know if

this works for your plugin and solves this issue.

Regards,

Yegappan

[vim-dev ML]

Hi,

On Fri, Nov 12, 2021 at 5:45 AM Boris Staletic ***@***.***>
wrote:

> prop_list_profile.txt
> <https://github.com/vim/vim/files/7527900/prop_list_profile.txt>

> The problem
>
> If a plugin wants to grab all of the previously placed text properties
> that the same plugin has placed, the current prop_list requires some work:
>

> 1. Loop over the lines of the buffer.
> 2. Grab all the text properties from each line and aggregate in some
> list.
> 3. Filter out all properties that are not produced by the plugin. A

> plugin might need to grab two types of properties, so making vim filter by
> type isn't perfect either.
>
> This results in a ton of vimscript API calls and is a similar thing to

> what lead to #8675 <https://github.com/vim/vim/issues/8675>.

> - We define two property types:
> https://github.com/ycm-core/YouCompleteMe/blob/master/autoload/youcompleteme.vim#L418-L433
> - When we update the diagnostics, we do it like this:
> - First, we grab all placed properties
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L133>

> - For each new diagnostic

> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L137>
> - if the exact same has already been placed, just skip
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L149>
> - else, place a new one
> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L151-L156>
> - Could be optimized with prop_add_list(). In the TODO list.
> - Once we have skipped all the ones we want to keep and added the

> new ones, what remains is to remove the stale ones

> <https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/diagnostic_interface.py#L158-L159>
> - There's no batch remove of properties, but *so far* that

> hasn't been a problem.
>
> The algorithm is made that way, because in common cases it's faster than
> removing all old and then placing all new - i.e. paying attention to
> overlap between the two sets is beneficial.
>
>
>
> But I digress. The problem is that call to vimsupport.GetTextProperties(
> bufnr ). It's defined here:
>
>
> https://github.com/ycm-core/YouCompleteMe/blob/master/python/ycm/vimsupport.py#L213-L226
>
> Doing that on an extra long file is very inefficient. For a file that is
> 1'010'000 lines long, with no props either placed, or to place (i.e. all
> work is in GetTextProperties()), it takes ~1 minute on my machine.
>
>
>

Patch 8.2.3652 extends the prop_list() function to support getting text
properties across
multiple lines and filter them based on the text property type and
identifier. Let me know if
this works for your plugin and solves this issue.

Regards,
Yegappan

[Boris Staletic]

First of all, apologies for a very late reply.

I have just tested the pathological case that prompted me to open this feature request. The result? Vim is now able to complete the task in 0.2 seconds, which is astonishing.

@yegappan Thanks a lot for providing the feature so quickly! I'm off to update the plugin.

—
You are receiving this because you commented.

[Ben Jackson]

This can be closed now. Fixed by e021662

—
You are receiving this because you commented.

[Bram Moolenaar]

Closed #9128.

—
You are receiving this because you commented.