Zsh-autocomplete: TODO: Asynchronous `list-choices`

[marlonrichert]

Not sure if it will actually improve performance, since of all the completion code, it's the calls to compadd that cause the most overhead, and those need to happen in the main thread, to update the completion menu. I already tried it once and didn't succeed. However, the automatic list-choices code is quite a bit different now than originally. So, I might try to give it another go at some point.

[forivall]

Yeah, i'd need this to start using this plugin, since i encounter a lot of jank just typing git, which happens a lot. I do have a rather complex setup of dotfiles that i should clean up, but making the listing async would just solve it without tweaking performance.

I use the pure prompt, which uses zsh-async for async tasks, so that might help you too.

[marlonrichert]

I've tried using zsh-async, but the problem is that completions cannot be shown when the Zsh Line Editor is not active. And when you're not typing, it's not active. So, if the completions finish only when you've already stopped typing, you get to see nothing. Or worse, you get to see old completions.

I would appreciate all help that anyone can offer with this! I could not get it to work reliably myself.

I might give it another try later, but all my trials with asynchronous completions have been rather time-consuming, for very little pay-off so far.

[marlonrichert]

@weilbith @Mallchad @romzie @forivall Damn, I've solved it! 😃 I am now able to get non-blocking, asynchronous completion! 🥳 I am still testing it and cleaning up the code, but expect an update coming soon. 🙂

[weilbith]

Wow that sounds amazing! :scream:
But if I understood it correctly I would need zsh-async for that. And this was a fork of zsh? :thinking:

[romzie]

No, from reading the description and looking at the code, it is a plugin,

zsh-async is a small library for running asynchronous tasks in zsh without requiring any external tools.

Fantastic job though !

[Mallchad]

Ahhhh that sounds amazing : D.
I actually can't wait for this!
It's the one thing missing from modern CLI's that prevents me from enjoying it fully.
Edit:
You said you are testing and polishing?
Would you consider a testing branch that we can see what you're doing on?
This fairly common practice on GitHub these days and protects your work in the event of data loss.
It would also be good for you to get feedback before pushing to master.
:)
Again thanks for the great work man :)

[weilbith]

This will also solve the issues of all slow completions like for package managers, correct?

[romzie]

@weilbith I suppose completion will still be slow but it should remove input lag and prevent keystrokes from hanging.

[Mallchad]

@romzie @weilbith I think this could be improved with better caching of results.
But this is for another discussion :)

[marlonrichert]

Would you consider a testing branch that we can see what you're doing on?
This fairly common practice on GitHub these days and protects your work in the event of data loss.
It would also be good for you to get feedback before pushing to master.

Sounds like a good idea. Here you go: https://github.com/marlonrichert/zsh-autocomplete/pull/34

[marlonrichert]

@forivall @Mallchad @romzie @michaelpolonski @weilbith @wookayin @Dwight-D @nisavid @andreypopp @CallumHoward @joeatodd @z0rc @TanishBansal @NICHOLAS85 @sejgit @DanDobrick @Mellbourn @hliu202 @TheMasterOfE @CadaverLab @Ahira-hub @PSalant726

Hi all!

Asynchronous, non-blocking completion is now available on the dev branch. I would appreciate if you could checkout that branch to test the feature and let me know what you think. 🙂

[romzie]

From what I tested so far, it is a game changer how smooth it is !

[Dwight-D]

I only tried it really quickly but it works great so far, none of the old issues seem to be present. I got a little slowdown once while using Git but I haven't been able to replicate it, might have been a one-off.

I also really like the new configuration options. I removed the plugin for a while because I found it a little too opinionated but now I like it a lot.

Nice work!

[Dwight-D]

Actually I did notice one thing, it throws out the old suggestions and fetches new ones when you type a new character, even if matches the previous results. So you won't see any suggestions as you're typing if the suggestions take over N ms and you're typing moderately fast, since it just keeps waiting for the new results but never has time to complete them before a new search is performed.

Probably getting the results multiple times is redundant, any extra characters you type just make your search more specific and make the new valid results a subset of the first results. Unless a backspace char is typed, there should be no need for refreshing results cache, unless there is some limit to the amount of results returned but I don't think there is. Subsequent matching could be done locally instead of via a new search (I haven't looked at the implementation but I suspect that's what's happening).

[Mallchad]

Actually I did notice one thing, it throws out the old suggestions and fetches new ones when you type a new character, even if matches the previous results. So you won't see any suggestions as you're typing if the suggestions take over N ms and you're typing moderately fast, since it just keeps waiting for the new results but never has time to complete them before a new search is performed.

Probably getting the results multiple times is redundant, any extra characters you type just make your search more specific and make the new valid results a subset of the first results. Unless a backspace char is typed, there should be no need for refreshing results cache, unless there is some limit to the amount of results returned but I don't think there is. Subsequent matching could be done locally instead of via a new search (I haven't looked at the implementation but I suspect that's what's happening).

I thought this was happening as well but I couldn't be sure because I don't understand how zsh refreshes the display.
I think a lot of the performance could be saved by improving caching, mainly by having multiple cache sources and filtering as needed,
1: You can keep a list of candidates for the current command from the first typed character
2: Cache results in memory and make sure the cache list is being searched in the event that the user tries to complete before the plugin has had a chance to read the disk+path for candidates
3: For semi-static/fairly persistent candidates like commands or directories and files that have existed for a long time (based on creation date), you can cache results to a file that's read asynchronously when the plugin starts to memory.
Note: This would need to be cleaned up every now and again to prevent stale and out of date candidates persisting in the cache, this should have a manual option to clean up and settings for disk cache size, "stale" age, when to scan the disk for updates to the candidate list, ie rescan past 10 querued paths for out of date results once a day or something.
4: Instead of throwing out old results for a single command completion request, append the new results to the given list and sort accordingly.
Note: This could be helpful for fuzzy search since if you realise you mistyped part way through and there are few new results the plugin could suggest an older result based on what the command was before. ie if you type
ln -sf /usr/lib/libpng19.so
and the pluign can't find anything exact it could give you an earlier result, for example
when the command was
ln -sf /usr/lib/libpng
and give you the result for that (ln -sf /usr/lib/libpng16.so.6).
Where as currently it had already (aparently) gotten rid of previous results and will try to search again, in some cases for the same results.
5: Also if the cache exceeds a certain set size or the current command to search is so widly different to the cached result (I'm talking like a 50% or greater failiure in substring matches you could throw out results from the cache for the current comand.

[marlonrichert]

As the famous quote says:

There are only two hard things in Computer Science: cache invalidation and naming things.

Phil Karlton

I'm pretty good at naming things, but I'm really not going to try my hand at caching. 😁

Only some Zsh completers, such as those for package managers, implement some kind of cache. Most do not. zsh-autocomplete cannot force completers to use caching if they don't have any implementation for it. 🤷🏽‍♂️

So you won't see any suggestions as you're typing if the suggestions take over N ms and you're typing moderately fast, since it just keeps waiting for the new results but never has time to complete them before a new search is performed.

If you want to see completions, can't you just stop typing for a moment? 🙂 And if you're still typing, do you really need to see completions?

Or to paraphrase an ancient philosophical question: If a completion shows on the command line, but there's no one around to read it, did it ever really show? 😉

Probably getting the results multiple times is redundant, any extra characters you type just make your search more specific and make the new valid results a subset of the first results.

That's not necessarily always true. What if you type a glob character? Or what if you insert a slash into the middle of a path? There's too many edge cases for this and it's going to get pretty complicated to try to check for them. As long as repeatedly fetching the same completions doesn't impact performance, is there really any payoff in trying to "solve" this?

[Mallchad]

When you have a large amount of candidates to sort through it can get very slow very quickly unfortunatly.
While I understand the caching problem, it is a hard one, at the very least you could insert candidates that have been fetched from the current command.
So if I haved typed git checkout by the time I've typed checkout it's already gotten a list of stuff to complete with and I may have already seen it, so then following this logic, assuming I get to typing some random commit like 8b1ad, and then I need/want to complete, why not allow me to see and complete with the already generated completions instantly instead of waiting on a new list.
This applies to many other examples but often you want to complete with a candidate you've already seen after you typed the first few characters, or perhaps you remember the name anyway and you're just using completion to save on typing and improve command accuracy.
This is similar to how vinilla zsh completion works and reguardless of if you've typing 30 characters, when you press tab it will complete with something, instead of making you wait for the completion to finish.
BTW I just realised this is one of times when the hang occurs, if the completion list is considered incomplete and you pres TAB, then you have to wait until it's finished collecting candidates or incur the wrath of the computer blocking your input momentarily.

[Dwight-D]

That's not necessarily always true. What if you type a glob character? Or what if you insert a slash into the middle of a path?

Many of these assume you type anywhere except the end of the current input. In most cases you are just typing more characters at the prompt, i.e. the end of the search string. This is just a more specific search, it cannot possibly result in any new matches that the latest string did not also match. Moving the cursor or deleting characters could invalidate the cache, to avoid complicated edge cases.

Globbing characters I guess are an exception but I would personally be completely fine with globbing suggestions not showing up. Normal wildcards would behave normally, ls myfile matches just as many files as ls myfile*, and extended globbing is such an unusual case that I don't think it needs to be taken into consideration for the default behavior. Auto-completions for globbing is not something that I've ever used or expected to work. But that's just my opinion.

If you want to see completions, can't you just stop typing for a moment? 🙂 And if you're still typing, do you really need to see completions?

Isn't this kind of saying that your entire plugin is pointless? We use it because we want suggestions as we type, not so that we can save one press of tab at the precis moment that we want suggestions. At least that's why I like it.

It's not a huge deal, but I'll try to explain my perception and behavior as a user.

When I'm for instance navigating through my files, I type more characters to narrow down the search until I see that I have a reasonably small set of suggestions, and then I tab through to the one I want. If I type more characters and there suddenly are no suggestions, then I know I have made a mistake and there are no matches. I'm in the wrong directory or I've misspelled.

However, if my completions don't appear until I stop typing, this does not work for anything where I fetch data remotely, such as checking out git branches. I would have to type until I think I've input enough, stop, wait, look at the results, and then select an option. If I'm not happy with the options I have to start typing again. I can't just type until I get the suggestions I want, as I would while navigating the file system, because I don't know if no suggestions means I've made a mistake or I'm just going too fast. What used to be a cue for me to stop and go back is now a possible false alarm.

So now I have to use my shell differently depending on if I'm doing something with fast suggestions or something with slow suggestions. The behavior of the plugin, and therefore the way I interact with my shell, becomes inconsistent. The implementation of the suggestions behind the scenes bleeds through into my interaction with it. So, instead of the plugin helping me, it becomes extra cognitive load.

I realize that this is a bit of an exaggeration, again it's really not a big deal to manage. But this is the reasoning for why one might want a coherent user experience instead of users slightly altering their behavior based on edge cases. Eventually you hit a point where the extra complexity becomes taxing for the user, and a less sophisticated but more straight-forward and consistent experience becomes preferable. This is for instance why I don't like magic space. I never know what it's going to do, so I prefer not to use it at all, because then at least I know what happens when I hit space. Even if it does the right thing 8/10 times, the uncertainty and inconsistency outweighs the extra utility for me in this instance.

I guess this comes across as complaining which is not the intention, again I really like the plugin and it works great 9 times out of 10. I totally understand if you don't think it's worth to spend time on.

Edit: I understand that caching is complex, but would it be possible to show the old suggestions, without extra filtering, until the new ones are fully loaded? IMO, showing inaccurate matches for a little while would be greatly preferable to showing no suggestions.

[forivall]

It breaks my bindkey '^[[A' up-line-or-beginning-search config 😢

[marlonrichert]

It breaks my bindkey '^[[A' up-line-or-beginning-search config 😢

@forivall That has nothing to do with the issue we're discussing here (asynchronous completion). Can you please open a new issue for that? Then I will see what I can do to fix it for you. 🙂

[marlonrichert]

When you have a large amount of candidates to sort through it can get very slow very quickly unfortunatly.

Even with asynchronous completion? Can you give me a test case for that, so I can reproduce it.

While I understand the caching problem, it is a hard one, at the very least you could insert candidates that have been fetched from the current command.

Easier said than done. Zsh does not provide any kind of API for accessing inserted completions. 🙁 I have been successful extracting them with the same method that fzf-tab uses (see here), but reinserting them is extremely error-prone (lots of edge cases where you don't end up with the original result) and, for most cases, appears to actually be _slower_ than regenerating them. What Zsh does in C code, I simply cannot do as efficiently in a shell script, it seems.

why not allow me to see and complete with the already generated completions instantly instead of waiting on a new list.

This seems to be a glitch of sorts in the Zsh Line Editor. When you call a completion widget in a hook function, listed completions instantly disappear, even if the widget tells the ZLE that it wants to keep the old list, which works under normal circumstance, but not in hook or callback functions for some reason. I could go back to wrapping/patching existing key widgets to call the autocompletion widget each time they're activated – which is what I did originally and what zsh-autosuggestions does - but that has worse performance, makes the code flow more complex and is not forward compatible with any new widgets that Zsh or the user might introduce.

BTW I just realised this is one of times when the hang occurs, if the completion list is considered incomplete and you pres TAB, then you have to wait until it's finished collecting candidates or incur the wrath of the computer blocking your input momentarily.

Again, can you please give me an exact test case? I have not seen this behavior yet.

[marlonrichert]

Many of these assume you type anywhere except the end of the current input. In most cases you are just typing more characters at the prompt, i.e. the end of the search string. This is just a more specific search, it cannot possibly result in any new matches that the latest string did not also match.

But the problem is that Zsh does not give direct access to the generated completions in any way. There's no way for me to tell it, "Hey, use the old set of matches, but filter them by this." It does not matter whether the set of matches would theoretically grow or shrink from new input. Short of writing my own completion system from scratch, I have no way to manipulate this. Every new list of completions is always generated anew.

I can't just type until I get the suggestions I want, as I would while navigating the file system, because I don't know if no suggestions means I've made a mistake or I'm just going too fast.

If you've made a mistake, then a message should appear in red, below the command line, that says "No matching completions found."

I understand that caching is complex, but would it be possible to show the old suggestions, without extra filtering, until the new ones are fully loaded? IMO, showing inaccurate matches for a little while would be greatly preferable to showing no suggestions.

Normally, yes, but when I call a completion widget from a hook function, as I currently do, then they always disappear, no matter what I tell the completion system to do.

[Dwight-D]

But the problem is that Zsh does not give direct access to the generated completions in any way.

Ah, I suspected it might be something like this. In that case I'd say you've done about as good a job as is possible under the circumstances!

[marlonrichert]

@weilbith @romzie @Mallchad @Dwight-D Alright, it took me some time and effort to figure out how, but there you have it: Asynchronous completion no longer makes any existing completion lists disappear. Completions now stay on screen for as long as until the next list of completions arrives. 🥳

[marlonrichert]

Please test and if there's no more concerns, then I think this is ready to be merged to the master branch. 🙂

[nhooyr]

Congrats!!!

[Dwight-D]

Works pretty good, well done!

It does hang the prompt sometimes, I think it's when the new suggestions have been fetched and are being loaded into the suggestions field. As long as I continue typing there is no slowdown, but when I stop typing I sometimes get a slight freeze right before the new suggestions appear.

I'm not sure if this is a new issue or if it's unrelated to the asynchronous suggestions. Either way it's probably better than it worked before, although I haven't used the plugin for a while so I can't tell for sure.

[marlonrichert]

It does hang the prompt sometimes, I think it's when the new suggestions have been fetched and are being loaded into the suggestions field. As long as I continue typing there is no slowdown, but when I stop typing I sometimes get a slight freeze right before the new suggestions appear.

Yeah, I've experienced the same. That is something I could improve in future, but it's rather a lot of work, so I'm not going to include it in this issue here. Also, I'm not sure I can even avoid for all cases, just for some.

I haven't used the plugin for a while

Oh, why not? 🙂

[Dwight-D]

Yeah, I've experienced the same. That is something I could improve in future, but it's rather a lot of work, so I'm not going to include it in this issue here.

Makes sense, then I agree it's ready for a merge!

Oh, why not? 🙂

I got a little fed up with the magic space thing and the difficulty of overriding configuration. This has since been fixed so I've recently started using it again, but I'm not really up to speed on how it behaves yet. I still like it! :)

[marlonrichert]

Alright, it's pushed to master, so I'm going to close this now. 🥳

If you notice any bugs, please open separate issues for them.

[weilbith]

Wow, thank you so much for investing that mass of time to make it possible. Respect. :pray:

Only one single thing: I think you must add zsh-async as dependency somewhere in the docs. I did just a simple update of this plugin and each new shell was spawning just a mass of errors while typing of missing zpty. Since I added the async plugin it works. Luckily I had an old shell still open. Else I would have been fu**** since I wasn't able to do anything, also not fixing it.

[marlonrichert]

@weilbith It's not about zsh-async. I had not added a statement to load the zsh/zpty module. It seems that in my config, something else loaded it already, or perhaps it's preloaded in my version of Zsh. It should be fixed now. Please update.

[forivall]

The issue I'm having with bindkey only happens on the async branch. Probably some event ordering thing, but i'm not an expert in zsh at all. https://github.com/marlonrichert/zsh-autocomplete/issues/28#issuecomment-637080075

_edit:_ nvm, scrolled up, you merged into master. I'll create a new issue

[weilbith]

@weilbith It's not about zsh-async. I had not added a statement to load the zsh/zpty module. It seems that in my config, something else loaded it already, or perhaps it's preloaded in my version of Zsh. It should be fixed now. Please update.

I did so and removed the zsh-async.

For some reason I now get no auto suggestions anymore, but just when I hit tab. Pretty sure it worked yesterday...

[marlonrichert]

@weilbith Can you open a new issue for this, please? And are you on the dev or master branch? I pushed the fix to master.

[marlonrichert]

Hey, I made a reddit post about this: https://www.reddit.com/r/zsh/comments/gwp58m/zshautocomplete_goes_asynchronous_nonblocking/

Go forth and upvote! 😉