[vim/vim] :find does not prune 'wildignore' matches during file system traversal for <Tab>-completions generation (Issue #9111)

[Andrey Mishchenko]

Steps to reproduce

1. Find to a folder foo/ with a large tree under foo/bar/ but no other large trees under foo/ (something like foo/node_modules/, for example).
2. cd foo/
3. vim
4. :set path+=**
5. :find (something)<Tab>. Generating the completions will take a while because foo/bar/ is a large tree.
6. :set wildignore+=*/bar/*
7. :find (something)<Tab>. Now this should be snappy (assuming there are no other large trees under foo/), but it isn't. No completions under foo/bar are returned, but the file system traversal is clearly still walking the whole tree.
8. This is easy to verify by executing mv foo/bar /tmp/bar repeating the above steps -- now :find (something)<Tab> will be snappy.

Expected behaviour

I expected that :set wildignore+=*/bar/* would make tab completion using :find fast, because the under-the-hood :find traversal would prune all of foo/bar/ from its search.

Operating system

macOS 11

Version of Vim

Vim 8.2.2029

Logs and stack traces

No response

—
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.

[Christian Brabandt]

Hm, the documentation does not mention, that wildignore applies to :find commands.

[Andrey Mishchenko]

Well IDK how precise "completing file or directory names" is meant to be but :find (something)<Tab> is a form of file/directory name completion.

In any case, wildignore does affect what the tab-completion returns, so there is no reason not to do the pruning in the search/traversal phase of completion generation.

Some more context in case it's helpful: if I am in my/project/folder with :set path+=**, I can get by with :find MyFile<Tab> and no FZF or anything else, except that if it's a Node project (say), there is this giant node_modules folder making :find slow.

[Romain Lafourcade]

TL;DR: wildignore applies to the completion, not to the search itself. If you want instant :find, use :help 'path' correctly.

What makes :find slow in your JS/TS project is a combination of two factors:

• your use of **, which tells Vim to look indiscriminately in every subdirectory of every subdirectory, which is insane with your typical node_modules/,
• the completion mechanism which, even with a finely crafted wildignore, is even more of a bottleneck than the search.

While both bottlenecks could theoretically be fixed, the solution is actually quite simple: use path as the whitelist it is supposed to be and not as a dumpster.

Instead of the lazy and greedy **, add a list of interesting directories:

set path+=src,whatever

You can even add /** after each of these directories if you want as the impact on performance will be negligible:

set path+=src/**,whatever/**

Illustration, with the bad **:

$ time vim -Nu NONE +set\ path+=** +find\ Accordion.vue +q
real	0m1,988s
user	0m0,955s
sys	0m1,001s

and with a proper value:

$ time vim -Nu NONE +set\ path+=components/** +find\ Accordion.vue +q
real	0m0,126s
user	0m0,038s
sys	0m0,039s

and without doing the search, to have a baseline:

$ time vim -Nu NONE +set\ path+=components/** +q
real	0m0,114s
user	0m0,035s
sys	0m0,036s

[Andrey Mishchenko]

Yep, that's exactly the workaround I went with.

But are you saying you don't consider it a bug that the completion file system traversal does not prune its search based on wildignore?

[Romain Lafourcade]

I would consider it a bug if it did.

[Andrey Mishchenko]

Hmm, I am confused. I might be misunderstanding something, please let me know if so.

The situation I am describing applies specifically to the case where we are tab-completing a :find against a path entry which contains a ** component, and where therefore we need to do a nested subdirectory search. My claim is that when we are performing such a nested subdirectory search (for tab completion, say), if we encounter a directory called foo, and */foo/* is in wildignore, we may safely skip traversing into foo (for the purposes of matching against this particular pattern in path) because we will anyway prune any result we obtain that way, because it will match a wildignore pattern. Am I missing something?

I am open to the idea that this is an optimization that isn't worth it or is too complicated or something. But I don't see why the pruning I am describing would itself be a bug.

[Andrey Mishchenko]

Put another way, I understand that wildignore does not in and of itself have anything to do with :find (thanks @chrisbra for that good point). I guess the real place to focus is the subsystem responsible for expanding the **, which is affected by wildignore, as far as I understand.

[Romain Lafourcade]

I guess the real place to focus is the subsystem responsible for expanding the **, which is affected by wildignore, as far as I understand.

No, wildignore affects completion/listing, not search.

When you do :find, the search is done in the directories listed in path and there is no other mechanism in place for excluding or adding directories or files from the search. The search itself could probably be improved (think breadth-firt vs depth-first) but it doesn't really need to because it works well enough given a correct path: 16ms with a correct path—that's basically indistinguishable from "instant"—versus almost 2 seconds with a misused path.

You will notice that those tests don't even factor in the completion part. If we add listing, with :help c_ctrl-d, we get it worse:

$ time vim -Nu NONE +set\ path+=** +call\ feedkeys\(\':find\ Accordion^D^CZQ\'\)

real	0m3,269s

user	0m0,840s

sys	0m2,393s

and adding a wildignore rule doesn't really improve the situation:

$ time vim -Nu NONE +set\ path+=** +set\ wig=*.html +call\ feedkeys\(\':find\ Accordion^D^CZQ\'\)

real	0m3,113s

user	0m0,802s

sys	0m2,267s

And that's with very few hits.

One last example, as above, but with a proper path:

$ time vim -Nu NONE +set\ path+=components/** +set\ wig=*.html +call\ feedkeys\(\':find\ Accordion^D^CZQ\'\)

real	0m0,258s

user	0m0,047s

sys	0m0,055s

wildignore helps with the user experience by limiting the noise when listing completions but that's about it. It doesn't substantially improve performance.

Again, the file searching feature could probably be modified to use wildignore (I don't see a strong technical reason against that) but the feature is already perfectly usable as-is so there is no need at all to perform that specific modification.

The key is to understand path and use it correctly. Misuse path and you get bad performance, use it correctly and you get instant :find. Simple.

[Andrey Mishchenko]

Saying that set path+=** is "misusing" path is one opinion, and I don't see it in the docs. Where does it say path should not be used that way? For example, :help file-searching talks about using a path with a ** entry.

wildignore does affect search, because it affects wildcard expansion. From the docs:

(:help wildcards, just below :help :find)

						*wildcard* *wildcards*
Wildcards in {file} are expanded, but as with file completion, 'wildignore'
and 'suffixes' apply. 

[Andrey Mishchenko]

Look, it's very simple. If I have a project folder with 10 subdirectories, all of which have interesting files, and one build/ subdirectory with a bunch of crap in it that I never want to open from Vim, I would rather set path+=** wildignore+=*/build/* than set path+=dir1 path+=dir2 ..., and I don't think that's unreasonable.

Furthermore, the first solution (using wildignore) does everything I want already (prunes build/ from tab completion and from :find results), except it makes :find slow, and I am claiming that in this circumstance :find is slow for no good reason.

[Romain Lafourcade]

Saying that set path+=** is "misusing" path is one opinion, and I don't see it in the docs. Where does it say path should not be used that way?

The reference manual is, for the most part, descriptive, not prescriptive. You are given a description of what the option do and it is up to you to understand it, experiment with it, and finally decide to use it or not and how. Experience helps a lot in that regard and it is perfectly natural for one's comprehension of a subject to evolve over time.

path is described as such:

This is a list of directories which will be searched when using the

|gf|, [f, ]f, ^Wf, |:find|, |:sfind|, |:tabfind| and other commands, […]

which doesn't tell us what directories to put there, and even the examples below are more here for explaining syntax issues than for prescribing purpose. Since what to put there is not prescribed, users can put whatever they want, even **, whether it makes sense or not.

Yes, ** is a perfectly valid value, just like 21 is a perfectly valid value for tabstop, but it has consequences and understanding those consequences is key to using path correctly.

I made the same mistake as you when I started. That +=** felt like a cool hack and wildignore felt like a cool escape hatch from the greediness of +=**. Except I was wrong, just like you are. :find foo<Tab> was slow for me, too, despite node_modules being in my finely crafted wildignore. I, too, complained about it and other vimmers explained the whole thing to me, I experimented, I read the source, and now I am at peace with :find, path, and wildignore, as they work wonderfully well together with no performance issue whatsoever.

No matter how hard you want it to be, wildignore is squarely ignored by the file search portion of :find foo<Tab> and only used by the completion portion, which only happens after the search part. In practice, this has zero negative effect if you use path and wildignore correctly.

I would rather set path+=** wildignore+=*/build/* than set path+=dir1 path+=dir2 ..., and I don't think that's unreasonable.

That is not unreasonable to want things. What is unreasonable is to expect them when the observable reality begs to differ. As for your path, yes, you should do set path+=dir1,dir2,dir3. That is exactly what your are supposed to do because that is how the option works best.

Furthermore, the first solution (using wildignore) does everything I want already (prunes build/ from tab completion and from :find results), except it makes tab completion on :find slow, and I am claiming that this is for no good reason.

And I am explaining to you that you are using it wrong, which is why tab completion on :find is slow for you. Using path, wildignore, and :find incorrectly is the cause of your problem and using them correctly is the solution. Asking others to change reality so that it matches your misconceptions is not a solution.

Unless you come up with a patch with demonstrable performance improvements.

[Andrey Mishchenko]

You are being condescending. I understand completely why the features, as I am trying to use them, are not performant. I claim it is a bug, because a simple change would make the interaction of :find/completion/path/wildignore performant, without breaking anything or making anything worse. You are claiming it is not a bug, because your preferred way of using those features is more "correct", and the performance issues are not present when someone uses these features the way you say they should.

But apparently set path+=** is a very natural thing to do -- you did it yourself. So more users will do it in the future. Some will encounter this problem, as apparently you did as well. And here is no reason that it has to work this way (that I can see), and there is no penalty/downside to it working the way I propose (that I can see). And in my universe, a strictly worse user experience (in some cases) for literally no benefit/tradeoff = bug.

[Romain Lafourcade]

:find foo<Tab> is slow because you set path incorrectly. Set path correctly and :find foo<Tab> will be instantaneous. It's as simple and straightforward as that.

Vim is full of bugs but that is definitely not one.

[bfrg]

Related: #2132

[Romain Lafourcade]

:find doesn't use that function, either directly or indirectly, though.

[Christian Brabandt]

Hm, I thought there was an issue/PR for making :find use breadth-first algorithm, ah apparently this was only on the mailing list: https://groups.google.com/g/vim_dev/c/_t5XILM6SCI I think breadth-first search could help with pruning searching directories that match the 'wildignorecase' option, but so far that is not possible.

[Bram Moolenaar]

This sounds like a corner case of using the expansion and ignoring matches. I don't think it is worth spending time on or adding code to do this better (after deciding what "better" is in this context). So let's close it.

[Bram Moolenaar]

Closed #9111.

[Andrey Mishchenko]

Would you consider a patch if it were well written and had tests, etc.?

On Mon, Nov 15, 2021, 6:32 AM Bram Moolenaar ***@***.***>
wrote:

> Closed #9111 <https://github.com/vim/vim/issues/9111>.
>
> —
> You are receiving this because you authored the thread.

> Reply to this email directly, view it on GitHub

> <https://github.com/vim/vim/issues/9111#event-5617541415>, or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/ABIP46GQCYB36WORLKSDHFLUMDVWLANCNFSM5HWGAWIA>

> .
> Triage notifications on the go with GitHub Mobile for iOS

> <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>
> or Android
> <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[Bram Moolenaar]

> Would you consider a patch if it were well written and had tests, etc.?

If it's clear what problem it is solving, sure.


--
There are 2 kinds of people in my world: those who know Unix, Perl, Vim, GNU,
Linux, etc, and those who know COBOL. It gets very difficult for me at
parties, not knowing which group to socialise with :-)
Sitaram Chamarty

/// 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 ///