Skip to content
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

Idea: Async CAPFs = ACAPFs #7

Closed
jdtsmith opened this issue Nov 22, 2021 · 61 comments
Closed

Idea: Async CAPFs = ACAPFs #7

jdtsmith opened this issue Nov 22, 2021 · 61 comments

Comments

@jdtsmith
Copy link
Contributor

jdtsmith commented Nov 22, 2021

I see you have as a TODO supporting company's async-flavoring. An interesting idea is to extend this to vanilla CAPFs as well, with a simple extra :async property, to make... async-capf's or ACAPFs.

The idea would be to extend the CAPF mechanism to allow it to return (if it thinks it can eventually complete something there) a null table, but include an :async callback-receiver property in the return:

(list start end nil :async callback-receiver)

This would "break nothing" for non-supporting UIs (though you'd get no completions). A supporting UI would pass the callback-receiver function it receives its own (unique!) callback function — a function which will accept just one argument: capf-result. The unique callback could be for example a closure that includes a request-id or some other disambiguator, so the UI knows which request is giving it results.

When the ACAPF eventually has some candidates (from a process or remote server, say), it can complete the CAPF operation by calling this callback with a regular CAPF response ((funcall callback `(,start ,end ,table ,@extra-props))), and then everything proceeds as a normal CAPF would have. The table could be a function (if it wants to specify some metadata and do something fancy) or just a simple collection, like always. The UI can either drop this request if the buffer has in the meantime changed, such that the completions are "no longer relevant", or pop-up the UI, if they have arrived "in time". Or a UI could allow the ACAPF to itself make that call in its table function (e.g. if the original region text includes a prefix of the current probe text), and only provide "relevant" completions. I'd suspect the former would be more robust.

To support both async-capable and "regular-old" completion UI's, the CAPF-author could wrap the async CAPF with a simple "polling" wrapper which supplies the ACAPF its own simple callback, and polls for completion (with timeout), before returning the full capf-result, seemingly synchronously.

@minad
Copy link
Owner

minad commented Nov 22, 2021

Yes, this is not a bad idea. I had something like this in mind in the longer term. For now I only implemented a very basic Company adapter, which forces synchronization by polling. It sounds reasonable to extend the capf specification with an asynchronous extension. In any case we should synchronize such efforts with Dmitry! cc @dgutov

@jdtsmith
Copy link
Contributor Author

Thanks. Not really a CAPE issue, but your TODO made me think of it. Plus I've been trying to get completions from a process and wishing I had an async approach available.

@jdtsmith
Copy link
Contributor Author

BTW, doesn't vertico have some async support for rgrep etc.?

@minad
Copy link
Owner

minad commented Nov 22, 2021

BTW, doesn't vertico have some async support for rgrep etc.?

No, in Vertico it works differently. Vertico is explicitly refreshed by the backend. See https://github.com/minad/consult/blob/37096d4bc4031a6a3d020ae225b6c675fa5ec0b7/consult-vertico.el#L50.

We could implement something similar here, where the Capf asks the frontend to retry. See my comment in the code:

cape/cape.el

Lines 550 to 553 in 31acb66

;; TODO When fetching candidates, support asynchronous operation. If a
;; future is returned, the capf should fail first. As soon as the future
;; callback is called, remember the result, refresh the UI and return the
;; remembered result the next time the capf is called.

@jdtsmith
Copy link
Contributor Author

The one addition we could consider is adding an :async-abort property, that specifies a callback letting the UI notify the backend if it has "already moved on" and is no longer interested in the results. That would allow lsp-clients to abort their requests for example.

@dgutov
Copy link

dgutov commented Nov 27, 2021

When the ACAPF eventually has some candidates (from a process or remote server, say), it can complete the CAPF operation by calling this callback with a regular CAPF response ((funcall callback `(,start ,end ,table ,@extra-props))), and then everything proceeds as a normal CAPF would have.

Leaving aside the fact that Company really wants to know start and end in advance before the full completion request is made, processed (with a certain latency) and the response is received, the table is usually expected to be a lazy computation...

(list start end nil :async callback-receiver)

...this doesn't look ideal. First of all, aside from completion table, the @extra-props tail contains operations that are themselves costly, per-item, and could as well be improved by an asynchronous way of working. E.g., some company-docsig resolver could be made to abort on user input when the user scrolls down through the completions in the displayed popup.

And both completion-at-point and company are known to call the c-a-p-f hook just to fetch the updated start and end after every user input. While the rest of the data might be stored longer.

Further, if we're talking about LSP, the delayed resolution of "correct" start and end aren't going to be a panacea since IIUC in that protocol every individual completion can use a different "prefix".

Completion table can also be more complicated than a list of strings, with "fields" and "boundaries", where it's not feasible to return all completions in all namespaces together (too many, too much memory used). And LSP also has a thing like "incomplete completion responses".

I would introduce a data type like "abortable promise", where the caller can set the callback, the errback, and abort the computation itself, and make it a possible return value for different operations. Completion table operations among them.

@minad
Copy link
Owner

minad commented Nov 27, 2021

Thank you for your response, Dmitry! I haven't thought much about the async issue yet, therefore I am just forcibly synchronizing the company calls in my wrapper. Could you point me to a good and simple asynchronous company backend, which I can use for experimentation?

I may try to implement a prototype capf extension at some point. The abortable promise you proposed sounds like the right direction. A long term plan could look like this:

1. Prototype for asynchronous table. The table should still support fully synchronous operation for backward compatibility.
2. Add asynchronous support to cape-company-to-capf.
3. Support it in Corfu.
2. Refine the prototype.
3. Agree on the design.
....
40. Support it in company-capf.
50. Possibly port over some asynchronous Company backends to Capfs with asynchronous completion tables.
...
600. Very long term - deprecate company backends. (Not sure if feasible/realistic, since I've heard there is also Company specific fuzzy filtering etc.)

@dgutov
Copy link

dgutov commented Nov 27, 2021

Could you point me to a good and simple asynchronous company backend, which I can use for experimentation?

That would be company-clang, for example.

But the asynchronous convention as implemented in "native" Company backends is a more simplistic one, without the capability to abort computations, for example.

  1. Support it in company-capf.
  1. Support in M-x completion-at-point, icomplete, etc?
  1. Very long term - deprecate company backends. (Not sure if feasible/realistic, since I've heard there is also Company specific fuzzy filtering etc.)

Yeah, capf completion tables also need native support for fuzzily matched completions. Maybe through an official "style", maybe in completion tables themselves, I'm not sure.

And completion sources' grouping.

The three features above should about cover the missing features compared to "native" company backends.

@minad
Copy link
Owner

minad commented Nov 27, 2021

But the asynchronous convention as implemented in "native" Company backends is a more simplistic one, without the capability to abort computations, for example.

Yes, the final design would probably be more full featured.

Support in M-x completion-at-point, icomplete, etc?

I'd argue to implement this first outside Emacs itself. The implementation from Corfu should transfer to Icomplete at least.

Yeah, capf completion tables also need native support for fuzzily matched completions. Maybe through an official "style", maybe in completion tables themselves, I'm not sure.

Can you explain this a bit more in detail? What does this mean "native support"? This means that filtering is performed on the side of the backend?

And completion sources' grouping.

Is this really needed? I can already implement merging/grouping for Capfs, see cape-super-capf. It is primitive and may have edge cases, but in the simple scenarios where one may want to use merging it works.

@dgutov
Copy link

dgutov commented Nov 27, 2021

I'd argue to implement this first outside Emacs itself. The implementation from Corfu should transfer to Icomplete at least.

Sure, but deprecating company-backends should depend on the acceptance of the above inside Emacs proper too, right?

Can you explain this a bit more in detail? What does this mean "native support"? This means that filtering is performed on the side of the backend?

Yes, pretty much. Whether it's inside its Lisp code, or even in the external process, without additional (costly) post-filtering in any completion style.

Is this really needed? I can already implement merging/grouping for Capfs, see cape-super-capf. It is primitive and may have edge cases, but in the simple scenarios where one may want to use merging it works.

It's a fairly popular feature in Company.

@minad
Copy link
Owner

minad commented Nov 27, 2021

Sure, but deprecating company-backends should depend on the acceptance of the above inside Emacs proper too, right?

Of course.

Yes, pretty much. Whether it's inside its Lisp code, or even in the external process, without additional (costly) post-filtering in any completion style.

From the side of the completion style this is no problem to implement this, one just needs a pass-through style. I am not exactly sure where the difficulty lies for the backend, since the backend can use the begin end positions and send the string to the backend for filtering?

It's a fairly popular feature in Company.

I don't doubt that. What I meant is that it seems to me that not all backends can be combined with each other. For example cape-super-capf can combine dict, ispell, keyword, symbol, dabbrev etc. But one cannot combine dabbrev+file for example due to the complexity of the file completion table and the completion boundaries. For which backends does grouping work well in Company?

@dgutov
Copy link

dgutov commented Nov 27, 2021

From the side of the completion style this is no problem to implement this, one just needs a pass-through style. I am not exactly sure where the difficulty lies for the backend, since the backend can use the begin end positions and send the string to the backend for filtering?

I don't think this is technically difficult either. But it needs a well-defined way to use such style. Perhaps a built-in category in completion-category-defaults. And the style itself to be in the core, of course.

For which backends does grouping work well in Company?

Those which return prefix strings equal to each other. That's not an insurmountable limitation, however, but it raises questions of how to treat and display combinations that do not fit that rule. I've just written a comment about it: company-mode/company-mode#1260 (comment)

company-backends is inherently simpler than completion tables, though (no "fields", or at least not yet), so that makes combination easier. We might want to add some similar feature, though, and I haven't really thought about all the possibilities there.

@minad
Copy link
Owner

minad commented Nov 27, 2021

Okay, so cape-super-capf has essentially the same limitation. It also requires the same prefix and it requires the sub capfs to not use boundaries. This means cape-super-capf should already be powerful enough for the current Company-style grouping. This may change in the future when you implement support for mixed prefixes.

@jdtsmith
Copy link
Contributor Author

@dgutov great point about asyncifying the property functions as well. But those requests, like for documentation, are coming only after you select a candidate, yes? So they could include their own async versions of the property (:async-docsig etc.), kicked off upon a show-doc command. I suppose you could "read ahead" and spawn some async requests for the first few docs/docsig/etc. in advance to be ready. By adding :async- flavored properties, an ACAPF could asyncify only what it needs to.

But really the only reason to stick to the current CAPF specification format is legacy value. It seems to me the synchronous completion system is so deeply ingrained, that any CPS-style async CAPF extension will need to interoperate with it, or at least not break things if ACAPFs and CAPFs get mixed and matched.

@jdtsmith
Copy link
Contributor Author

Yeah, capf completion tables also need native support for fuzzily matched completions. Maybe through an official "style", maybe in completion tables themselves, I'm not sure.

I mean lsp servers already return ~fuzzy completions of their own design. By native support do you mean affecting the backend server's output? Or just advanced filtering on the emacs/client side?

@dgutov
Copy link

dgutov commented Nov 27, 2021

So they could include their own async versions of the property (:async-docsig etc.), kicked off upon a show-doc command.

Possibly, yes, if those extra properties were the only problem.

OTOH, if we standardize on some "promise" value type, we wouldn't need to introduce any new properties. That value type could also be used by the completion function only when needed.

By native support do you mean affecting the backend server's output?

Yep. And without having additional post-filtering through a style like flex which does add overhead, and might even filter out some completions unnecessarily, given sufficiently exotic filtering approach on the backend.

@minad
Copy link
Owner

minad commented Nov 27, 2021

@dgutov @jdtsmith Can someone explain why asyncing all the functions is valuable? I only see a value in asyncing the call which initially checks if completion is possible at the current point and obtains the candidates. This only matters for the corfu-auto/company-idle mode, where these calls can be performed in the background. But as soon as the popup is visible it is better to use synchronous calls to obtain the additional metadata. Otherwise the UI would just have to synchronize everything itself. There is certainly a minor performance advantage if you can start the few required calls asynchronously and wait until all results have arrived, but does this matter and is it worth the complication? For the popup only a handful of calls are made (annotations, deprecation, kind, etc).

@dgutov
Copy link

dgutov commented Nov 27, 2021

But as soon as the popup is visible it is better to use synchronous calls to obtain the additional metadata.

Both docsig and doc-buffer (for example) could be used in asynchronous-ish fashion: displaying the info when Emacs is idle, and aborting the request when the user continues typing.

@minad
Copy link
Owner

minad commented Nov 27, 2021

Both docsig and doc-buffer (for example) could be used in asynchronous-ish fashion: displaying the info when Emacs is idle, and aborting the request when the user continues typing.

Okay, I agree with those two! Also for the others there is a theoretical but minor advantage, but I doubt it justifies the complication. I would prefer a design where only the functions which are relevant are actually made asynchronous. Maybe you prefer a uniform interface as in Company where every call can either return the value right away or a future? However most of the calls are forcibly synchronized, which then defeats any advantage.

@dgutov
Copy link

dgutov commented Nov 27, 2021

Maybe you prefer a uniform interface as in Company where every call can either return the value right away or a future? However most of the calls are forcibly synchronized, which then defeats any advantage.

A uniform interface is what I usually opt for, yes. Most of the implementations are indeed synchronized, though I don't see that as much of a problem (the performance overhead is negligible).

In any case, whether every such function must support async or not, is not a very important decision, I think. It probably doesn't affect any of the other design aspects. So there's not much point in talking about it at this stage.

I even think the overall arrangement should work even if the set of async-supporting functions varied by frontend.

@jdtsmith
Copy link
Contributor Author

Yep. And without having additional post-filtering through a style like flex which does add overhead,

Interesting. So there would have to be some mapping between LSP "styles" and emacs "styles". Sounds challenging/moving target.

and might even filter out some completions unnecessarily, given sufficiently exotic filtering approach on the backend.

In fact I was just experiencing this a few minutes ago by setting the style to basic. Many of the lsp-servers candidates are dropped. Orderless mostly retains everything. And then once you have the candidates and can operate from cache, it's much faster to select among them locally.

@minad
Copy link
Owner

minad commented Nov 27, 2021

@jdtsmith

In fact I was just experiencing this a few minutes ago by setting the style to basic. Many of the lsp-servers candidates are dropped. Orderless mostly retains everything. And then once you have the candidates and can operate from cache, it's much faster to select among them locally.

See what I wrote in minad/corfu#92 (comment). I guess you should either use flex or enable the orderless-flex matching style to retain most candidates. In order to retain all candidates one can also install an orderless style dispatcher which drops the first word entirely, since this is what triggered the completion and lead to filtering in lsp. I consider the split server/client filtering an almost solved issue with orderless.

@jdtsmith
Copy link
Contributor Author

I agree that getting anything working async on the CAPF side would be a good goal.

@jdtsmith
Copy link
Contributor Author

jdtsmith commented Nov 27, 2021

You beat me to it... I turned on orderless-flex for the 1st term only, and it works great. Honestly most of the candidates the server returns are pretty far-fetched — ar -> FLOATING_POINT_SUPPORT? Sure.....

I'll probably personally demand at least substring matching. Dispatching first match term as "" also works and is wicked fast... you just don't get match highlighting (for that term). [Update: extending the first term after completion starts does not do any filtering, you have to add a space-separated match term... so "" is not ideal. Possibly could configure the dispatcher as a one-time latch which only returns "" on 1st call "during" completion; not sure what "during" marker to take].

@minad
Copy link
Owner

minad commented Nov 27, 2021

All these async capf ideas sound nice but I keep wondering if it is not better to try to get away with a simple targeted extension. The problem with async tables is that they would require an async extension to all completion styles.

A possible simple extension could look like this:

Add a single :async-complete function to the plist returned by the capf. If this function is present, the capf is treated as matching successfully at the given point in the buffer. Only the results are not available now but in the future.

Then the frontend would call the :async-complete function with a callback. The :async-complete function will return another function/closure which can be called by the frontend to request cancellation.

When the refresh callback is called, processing continues as usual - synchronously. If the buffer is modified before the callback returns the frontend can cancel the async request. It seems that this extension is all that is needed to fit asynchronous completion into the current framework. (One may also add :async-docsig/:async-docbuffer functions which get a callback and return a cancellation function.)

Since querying the capf list must be fast one could always query the capfs immediately in the post command hook. The synchronous completion tables will be used after a timeout. The asynchronous tables can be used as soon as the asynchronous callback returns.

Basically one can write an adapter which transforms the synchronous to fake asynchronous backends. The fake asynchronous backend async function will return a function which cancels the timer and the callback will be called when the timer elapsed.

Now the problem is that this design does not fit well to the company design, since the candidates action of a company backend cannot be asked selectively to return a future. And it is not possible to ask a company backend if it is indeed asynchronous.

@minad
Copy link
Owner

minad commented Nov 27, 2021

Reading through @jdtsmith's initial comment here - I think what I just described is mostly the same. But @jdtsmith's description sounds even more elegant and simpler. Downside is of course also that it does not fit nicely to Company.

@minad
Copy link
Owner

minad commented Nov 27, 2021

I looked at the Company code and it seems to me that the whole async idea is pointless if one treats Capf completion tables as interruptible. As I argued in minad/corfu#71 (comment) and the discussion there, completion tables should be treated as interruptible since this is the only way one can use them in a responsive UI. Icomplete and Vertico treat completion tables as interruptible. Problematic completion tables can be wrapped by cape--noninterruptible-table and cape-noninterruptible-capf.

Company seems to explicitly disallow interruption of completion backend calls. In order to still allow responsive UIs, async future return values have been introduced. The frontend can wait for these futures to complete while still allowing interruption. See the sit-for in company--fetch-candidates (https://github.com/company-mode/company-mode/blob/6abb232acde15e1a7bf402a57f7bb982edf2de7d/company.el#L1439-L1440).

Now I can just do the same in cape-company-to-capf, such that the resulting capf is interruptible. I treat Company backend calls as non-interruptible, but still allow interruption during the async fetching/synchronization:

cape/cape.el

Lines 738 to 753 in e341f81

(defun cape--company-call (backend &rest args)
"Call Company BACKEND with ARGS."
;; Company backends are non-interruptible.
(pcase (let (throw-on-input) (apply backend args))
(`(:async . ,fetcher)
(let ((res 'trash)
(start (time-to-seconds)))
;; Company backends are non-interruptible.
(let (throw-on-input) (funcall fetcher (lambda (arg) (setq res arg))))
;; Force synchronization. The synchronization is interruptible!
(while (eq res 'trash)
(sleep-for cape-company-async-wait)
(when (> (- (time-to-seconds) start) cape-company-async-timeout)
(error "Cape company backend async timeout")))
res))
(res res)))

Therefore it seems to me that the introduction of asynchronous Capfs is unnecessary. The Capfs produced by cape-company-to-capf still profit from the asynchronous nature of Company backends. Furthermore usual Capf backends are just as efficient, as long as they are interruptible.


Copying my minad/corfu#71 (comment) here for context:

  1. The completion table returned by the capf should be interruptible by while-no-input. This is relevant if internal state is manipulated. Completion tables are treated as interruptible by Icomplete, Vertico and Corfu. See the Cape completion tables for reference.
  2. The capf function call should be fast and ideally not perform pre-filtering based on the given prefix. In practice only capfs returning trivial/static completion tables satisfy this. See the cape-symbol and cape-keyword table for reference.
  3. If (2) cannot be satisfied and the table performs pre-filtering, e.g., if it takes the initial prefix into account for candidate computation, then the table should drop its caches as soon as this prefix changes. See cape-ispell for reference.
  4. The completion table returned by a capf should not rely on the STR argument to dynamically compute the candidates, since this works only in conjunction with the basic completion style and is incompatible with advanced completion styles like substring, flex or orderless. This implies that completion-table-dynamic and completion-table-with-cache should not be used if the goal is to support advanced completion styles.

@minad
Copy link
Owner

minad commented Nov 27, 2021

So in summary, these are the differences between Company backends and Capfs:

  1. Async Company backends = Capfs returning interruptible completion tables, adapter cape-company-to-capf.
  2. Company grouping/merging = cape-super-capf
  3. Company native/fuzzy filtering can be supported by the Orderless completion style with a special style dispatcher, where the first word of the filter/input string is translate to "". The subsequent filter words are used for fast post-filtering on the side of Emacs. Since the first word is ignored by Orderless, it is only relevant for backend/native fuzzy filtering.

There is a Capf equivalent for every Company feature.

@jdtsmith
Copy link
Contributor Author

No. 3 (see above) — really, as I discovered, only if you can return "" just once does this work, since extending the 1st term then does nothing; not sure what convenient "I'm in the same completion" marker we could rig for the dispatcher. orderless-flex works fine (if adding overhead, as @dgutov mentioned).

To me a difference between "interruptible sync CAPF" and async CAPF, is for the latter (if they can be made to work), you could continue to make small edits to the buffer that do not affect the validity of the original completion call, such that its results can still be shown, even after some input has happened. You could of course cancel the request as soon as you see that the buffer is not valid, but you don't have to do so on every new input.

And the other big difference — brute force interruption is really not so kind. Remember when I was mentioning that my ipython mode was suffering from non-local exits to accept-process-output, that I simply could not understand the source of? I even posted on emacs-devel about it (they said: run under gdb and set a break in Fthrow).

After a long investigation, I ended up giving each call to A-P-E a timeout, and looping up to a maximum delay to fix it. I had thought that corfu had helped me uncover the bug by turning down corfu-auto-delay to a very short time, like 0.05s. Well, it turns out corfu itself was responsible for the interruption and non-local exit! I could have fixed it trivially by setting (let (throw-on-input) ...!

Why is a non-local throw a problem for a process-facing CAPF in the middle of its operation? Because process output is itself async, and will call the process filters function when new data arrive, whether or not you've pulled the rug out from under a corralling "output capturing" stanza (e.g. (while (A-P-E proc))). If you've set up temporary process filters to redirect and gather that output, a non-local throw does not "magically halt" the process output. It just halts the loop you are using to gather that info, and sends it where you don't want it (straight into the shell buffer!). Put another way, while-no-input does not cancel the entire async process call, instead it just cancels the async -> sync "transducer" you have setup to capture the output of that call! I.e., the opposite of what you want.

So I hope we can come up with a cancellation scheme more forgiving than brute force interruption (like a cancel callback).

In terms of supporting company async backends (which I haven't used) vs. extending the CAPF format to include ACAPFs, is there one advantage not being mentioned? An ACAPF allows an "easy upgrade path" for current or future CAPFs which later realize they should be async for some of their functions.

@dgutov
Copy link

dgutov commented Nov 28, 2021

@minad

I agree that cancellation is not nice and it will lead to brittle systems, in particular if the backend author is not prepared that interruption may happen. All I am saying is that if you use interruptible tables you are already equivalent to company in capabilities if we consider the status quo.

This doesn't sound right: after all, the current async backends of Company don't have similar correctness and debuggability problems resulting from having code interrupted in an arbitrary location, or even interrupting a random timer or a process sentinel belonging to another process that might be running at the present time (which is unlikely, but not unimaginable).

Furthermore, "real" asynchronous backends (with callbacks and stuff) allow multiple completion sources to run in parallel. So one could launch a request to a background language server then let the second one do the same or (more likely) do some in-process compulation (like company-dabbrev does) and then, when the response comes, combine their results. Grouping on top of async, boom. mike drop

Of course, I don't really think this is crucial now, but limiting ourselves to sequential processing of completions for the future evolution of the API seems wrong. Who knows what our descendants could manage to do with it.

Anyway, writing code that is resilient against being interrupted is hard (here's some essay on the subject: https://adamhooper.medium.com/in-ruby-dont-use-timeout-77d9d4e5a001). We can end up with unfinished assignments, connections (in the url library) that are not closed properly and not returned to the "free" pool. Or one-off processes which don't need to run anymore (and could have been killed in a proper errback handler) but continue running because the execution thread which knows about it has been killed out. I'm not saying this approach couldn't work, but I'm definitely not brave enough to try that road myself.

Would the design I described in my previous comment be satisfactory from your perspective? It is a straightforward extension of plain old capfs and completion tables. Every function (the table, the annotation, and the company-* functions) is simply allowed to return an (:async . function) future (in the style of Company) additionally to the usual synchronous values.

It sounds very similar to what Company does already, so sure (though we'll probably end up with some other container for futures than an anonymous function). But like you mentioned previously, these values would need to be passed through the completion styles, which can definitely raise the complexity of their implementations. I don't see a way around it, though. Aside from someone going in and magically rewriting a lot of that stuff (completion styles) in some simpler way first.

@minad
Copy link
Owner

minad commented Nov 28, 2021

Thank for your answer, Dmitry! I didn't mean to write it in an adversarial tone.

This doesn't sound right: after all, the current async backends of Company don't have similar correctness and debuggability problems resulting from having code interrupted in an arbitrary location, or even interrupting a random timer or a process sentinel belonging to another process that might be running at the present time (which is unlikely, but not unimaginable).

There is also manual interruption. If you want to write a robust process handler you should make sure that it is cleaned up afterwards.

Furthermore, "real" asynchronous backends (with callbacks and stuff) allow multiple completion sources to run in parallel. So one could launch a request to a background language server then let the second one do the same or (more likely) do some in-process compulation (like company-dabbrev does) and then, when the response comes, combine their results. Grouping on top of async, boom. mike drop

Of course, it is obvious that one should take advantage of parallel fetching of asynchronous sources. Do you take advantage of that in Company currently? Is it a common use case that people combine asynchronous sources and group them? I have looked at the Company code, but it is likely that I missed the code where you do this parallel fetching. Currently my cape-super-capf does not support parallel fetching, since it is synchronous. But this could be added without an issue if an async calling convention is adopted.

Anyway, writing code that is resilient against being interrupted is hard.

Of course, I am aware of that. But anyways - I haven't observed significant issues in practice. Minibuffer completion tables are usually pure and interruptible. In Corfu the situation may be a bit different, since there communication with an external process is much more common. And for the few completion tables which make problems one could wrap them on a case by case basis with a capf transformer like cape-noninterruptible-capf.

It sounds very similar to what Company does already, so sure (though we'll probably end up with some other container for futures than an anonymous function). But like you mentioned previously, these values would need to be passed through the completion styles, which can definitely raise the complexity of their implementations. I don't see a way around it, though. Aside from someone going in and magically rewriting a lot of that stuff (completion styles) in some simpler way first.

One could also use post filtering via the completion style. Fetch all candidates asynchronously and then run the completion style on the resulting list. Downside is that this approach is less efficient (in particular for regexp filtering) and does not work for any of the complicated dynamic tables. On the other hand there are probably either asynchronous completion tables or dynamic completion tables which make heavy use of boundaries. In any case such an asynchronous capf design seems okay, it does not have the potential correctness issues as interruptible tables have.

@minad
Copy link
Owner

minad commented Nov 28, 2021

To bring the discussion back on track - I think I didn't manage to convey my main point. It does not matter if we agree or disagree on interruptible/noninterruptible tables, for what I am going to describe now. I am only using interruptibilty as a trick to reuse the existing synchronous infrastructure.

If you query a completion table one could use the following call chain:

while-no-input (make the call interruptible)
  |
  v
completion-all-completions (use the completion style)
  |
  v
<mystyle-all-completions>
  |
  v
cape-async-to-interruptible-table (add support for async, everything below is async, noninterruptible and safe)
  |
  v
the actual table, nice and safe, can return async futures

;; called like this in the frontend:
(while-no-input (completion-all-completions str (cape-async-to-interruptible-table the-actual-table) ...))

If you want to query multiple tables one could use:

while-no-input
  |
  v
completion-all-completions
  |
  v
<mystyle-all-completions>
  |
  v
cape-async-to-interruptible-table
  |
  v
cape-async-super-table (fetch in parallel)
 |         |      |
 v         v      v
table1   table2   ....

The only requirement here is that the frontend must execute the completion table with while-no-input to take advantage of the async cancellation. Maybe this is a minor issue for disagreement, however note that below completion-all-completions there is the async transformer which makes sure that we are safe. The huge advantage of this layered extension of the design is that completion styles can just be used as is.

@jdtsmith
Copy link
Contributor Author

jdtsmith commented Nov 28, 2021

Random reactions:

  • a single latching “pass-through-once” style that does nothing on 1st invocation but present “all the results”, then converts itself to flex/substring/orderless with further input against the same table could be very helpful with speed/completeness. The flex highlighting is basically a lie anyway against server-provided results. And an expensive lie.

  • We are speaking implicitly of different capabilities of an asynchronous setup:

    1. Not blocking user input, being interruptible.
    2. Permitting multiple process/network-facing completion components to yield time and run “in parallel” (while not blocking).
    3. Permitting results which have arrived after the buffer has changed to still be displayed, if they are still relevant.

    @minad your wrapper design sounds like an interesting possible solution to 1. So it would be wrapped in while-no-input, use unwind-protect to catch non local exits, and call the cancellation callback(s)?

  • all of this would be infinitely easier if Elisp had some coroutine/cooperative multitask/non-thread yield primitives. Are we sure that’s not on the horizon?

@minad
Copy link
Owner

minad commented Nov 28, 2021

@jdtsmith

a single latching “pass-through-once” style that does nothing on 1st invocation but present “all the results”, then converts itself to flex/substring/orderless with further input against the same table could be very helpful with speed/completeness.

Let's keep out the completion style discussion for now. As I see it, it does not affect the design of an async capf very much. I agree with you that there is improvement potential, but I think orderless with all its flexibility goes a long way.

your wrapper design sounds like an interesting possible solution to 1. So it would be wrapped in while-no-input, use unwind-protect to catch non local exits, and call the cancellation callback(s)? But what of 2,3?

(i) is supported by cape-async-to-interruptible-capf, (ii) is supported by a potential cape-async-super-capf, which can be written in a similar style as the existing cape-super-capf, only difference being that it proceses futures and returns futures.

(iii) cannot be handled by this design and the capability also seems too unspecific. How can I determine if candidates are still relevant? I would like to exclude (iii). Both (i) and (ii) are at least well defined and as I've described also possible to implement without huge effort.

See cape--company-call to achieve the interruptible synchronization. (For Company without unwind-protect future cancellation, but this is easy to add.)

all of this would be infinitely easier if Elisp had some coroutine/cooperative multi-proc/non-thread yield primitives. Are we sure that’s not on the horizon?

As far as I know it is not on the horizon. But I am also not sure how it is signficant to the discussion, we would still need some kind of async future to wait for.

@jdtsmith
Copy link
Contributor Author

Both (i) and (ii) are at least well defined and as I've described also possible to implement without huge effort.

i) and ii) alone would represent good progress. But I'm still not fully sure how using while-no-input to pull the plug out randomly in the middle of process interaction will be improved with a cancel callback. I guess you could keep a buffer-local variable which the cancel callback sets, and if found, just swallow all output, but this could get confused with "real" process output you do want to keep. The way I see it, while-no-input is not the cooperative multitasking we seek, it's preemptive interruption. Once you've already non-locally exited deep (blocking) process IO, your state is problematic and hard to recover gracefully from. It's certainly better to have a "cancel" callback, but a more cooperative approach from frontend to backend would be "I noticed some input arrived, please cancel your current operation at your earliest convenience".

Let's keep out the completion style discussion for now. As I see it, it does not affect the design of an async capf very much.

It may seem ancillary, but it impacts the way in which external async completion providers like LSP can be dealt with. As a proof of principle, here is an example orderless dispatcher which delivers one time pass-through, only on a new table or same 1st match pattern:

(defun my/orderless-dispatch-passthrough-first ()
    (let (last-table initial-pattern)
      (lambda (pattern index _total)
	(if-let (((eq index 0))
		 (table (caddr completion-in-region--data)))
	    (if (not (eq table last-table))
		(progn 
		  (setq last-table table
			initial-pattern pattern)
		  "")
	      (and initial-pattern
		   (string-equal pattern initial-pattern) ""))))))

I.e. it does no filtering on first results from the server, but then permits more filtering right away with that set. If you extend the 1st match, you can "get back to" the original full results by deleting back to it.

But I am also not sure how it is signficant to the discussion, we would still need some kind of async future to wait for.

Presumably those would be developed in short order for general Emacs use if yield-style async capabilities were built in natively.

@minad
Copy link
Owner

minad commented Nov 28, 2021

i) and ii) alone would represent good progress.

Indeed.

But I'm still not fully sure how using while-no-input to pull the plug out randomly in the middle of process interaction will be improved with a cancel callback.

There won't be any pulling the plug randomly - no interrupts. You can kill the process in the cancel function.

The way I see it, while-no-input is not the cooperative multitasking we seek, it's preemptive interruption.

No, you misunderstood how this is supposed to work. There won't be any preemptive interrupts during the execution of the asynchronous completion table (except manual interrupt C-g). The cancel function is called the next time input arrives, but by the event loop. Not randomly, not preemptively. Please take a look at the following code. I commented it to be more explanatory.

(defun cape--async-call (fun &rest args)
  "Call FUN with ARGS and handle async future return values "
  ;; Backends are non-interruptible. Disable interrupts!
  (let ((toi throw-on-input)
        (throw-on-input nil))
    (pcase (apply fun args)
      ;; Handle future return value
      (`(:async . ,future)
       (let ((res 'cape--waiting)
             (start (time-to-seconds))
             cancel)
         (unwind-protect
             (progn
               (setq cancel
                     (funcall future (lambda (arg)
                                       ;; Enqueue cape--done event
                                       (when (eq res 'cape--waiting)
                                         (push 'cape--done unread-command-events))
                                       (setq res arg))))
               ;; Force synchronization.
               (while (eq res 'cape--waiting)
                 ;; When we've got input, interrupt the computation.
                 (when (and unread-command-events toi)
                   (throw toi nil))
                 (when (> (- (time-to-seconds) start) cape-company-timeout)
                   (error "Cape async timeout"))
                 ;; Wait for input or cape--done
                 (sit-for 0.1 'noredisplay)))
           ;; If the future didn't finish, ask it for cancellation.
           (when (and (eq res 'cape--waiting) (functionp cancel))
             (ignore-errors (funcall cancel)))
           ;; Remove cape--done introduced by future callback
           (setq unread-command-events (delq 'cape--done unread-command-events)))
         res))
      ;; Plain old return value (synchronous)
      (res res))))

(Also compare with cape--company-call, which is essentially the same, only without cancellation support.)

It's certainly better to have a "cancel" callback, but a more cooperative approach from frontend to backend would be "I noticed some input arrived, please cancel your current operation at your earliest convenience".

This is what the cancel callback is - it asks the backend to cancel.

@dgutov
Copy link

dgutov commented Nov 29, 2021

Hi Daniel,

Thank for your answer, Dmitry! I didn't mean to write it in an adversarial tone.

I didn't mean to imply that either. No more than would be sportsman-like, at least.

There is also manual interruption. If you want to write a robust process handler you should make sure that it is cleaned up afterwards.

This is a fair argument, but it probably just means that Emacs' commands are unreliable in the face of keyboard-quit. Yes, it's usually a good idea to write Elisp in a way resilient against aborts, but as we've discussed already, that's rather hard to do. So relying on aborts as an alternative to asynchronous computations probably isn't going to fly.

Of course, it is obvious that one should take advantage of parallel fetching of asynchronous sources. Do you take advantage of that in Company currently? Is it a common use case that people combine asynchronous sources and group them? I have looked at the Company code, but it is likely that I missed the code where you do this parallel fetching. Currently my cape-super-capf does not support parallel fetching, since it is synchronous. But this could be added without an issue if an async calling convention is adopted.

Check out the definition of company--multi-backend-adapter-candidates. It tries to support that scenario, at the very least.

But as for taking advantage -- alas, most of the popular backends out there are synchronous. The popular asynchronous ones fell to the wayside when LSP arrived.

One could also use post filtering via the completion style. Fetch all candidates asynchronously and then run the completion style on the resulting list. Downside is that this approach is less efficient (in particular for regexp filtering) and does not work for any of the complicated dynamic tables.

That sounds like it will require changes in how completion styles are organized. And anyway, yes, by design they are supposed to query the completion table themselves. But maybe it would still be able to retain the power and (most of) performance if things were done in a different way.

To bring the discussion back on track ...
(while-no-input (completion-all-completions str (cape-async-to-interruptible-table the-actual-table) ...))

No, you misunderstood how this is supposed to work. There won't be any preemptive interrupts during the execution of the asynchronous completion table (except manual interrupt C-g). The cancel function is called the next time input arrives, but by the event loop. Not randomly, not preemptively. Please take a look at the following code. I commented it to be more explanatory.

I was going to ask the same question as @jdtsmith.

With the illustration, it becomes a little clearer. So the only times the "synchronized" async backends would be able to throw, is between their sit-for calls, when manually detecting that some input has arrived? That might work, I guess. The design is a little exotic, I'd say, but some MVP and testing it in practice might as well prove it viable.

Only... perhaps don't use while-no-input? And instead catch a certain predefined symbol that the asynchronous "synchronized" tables are supposed to throw? This way the "normal" completion tables won't receive arbitrary interruptions, since they're not always prepared for them.

I'm still not crazy about it (as opposed to consistently using an async primitive and some standard functions and/or macros to manipulate them), but the tradeoffs could be worth it.

@dgutov
Copy link

dgutov commented Nov 29, 2021

@jdtsmith

Speaking of

all of this would be infinitely easier if Elisp had some coroutine/cooperative multitask/non-thread yield primitives. Are we sure that’s not on the horizon?

The "threads" in Emacs Lisp are actually more like cooperative coroutines than "real" threads. They might be lacking some convenience in the existing abstractions, but otherwise they are what you described.

Not sure how they are supposed to help, though.

@jdtsmith
Copy link
Contributor Author

Oh, I thought you were still set on throw-on-input; this looks quite good.

In a backend you could be doing something like:

(while (and (not completion-cancelled)
	    output-filter-in-progress
	    (or (eq max-cnt t) (< cnt max-cnt)))
  (accept-process-output process delay nil 1)
  (cl-incf cnt))

and just set completion-cancelled in your cancel-back. Then cleanup if you exited due to cancellation — no throwing. Would it perhaps be useful for the backend ACAPF to have the ability to specify its own timeout (including disabling it)? Some backends are slower than others, so probably no one-size-fits-all is possible.

@jdtsmith
Copy link
Contributor Author

@jdtsmith

Speaking of

all of this would be infinitely easier if Elisp had some coroutine/cooperative multitask/non-thread yield primitives. Are we sure that’s not on the horizon?

The "threads" in Emacs Lisp are actually more like cooperative coroutines than "real" threads. They might be lacking some convenience in the existing abstractions, but otherwise they are what you described.

Not sure how they are supposed to help, though.

Yeah, not very familiar, but what I've read about them hasn't been too encouraging. I know for example tramp had a thread branch for several years and hasn't been able to get it to work. Maybe there is some way to do async-completion in a thread. But the callback passing style @minad has proposed looks pretty flexible.

@jdtsmith
Copy link
Contributor Author

That sounds like it will require changes in how completion styles are organized.

You just need a self-morphing dispatching style like orderless ;). My "passthrough-once" approach above actually works surprisingly well, and cuts out all the overhead of flex-matching just to show all results.

@minad
Copy link
Owner

minad commented Nov 29, 2021

@dgutov

I didn't mean to imply that either. No more than would be sportsman-like, at least.

Good, I wasn't sure - I also didn't mean it in any different way than sports-man like. Btw, today I learned about elp-instrument-package :)

This is a fair argument, but it probably just means that Emacs' commands are unreliable in the face of keyboard-quit. Yes, it's usually a good idea to write Elisp in a way resilient against aborts, but as we've discussed already, that's rather hard to do. So relying on aborts as an alternative to asynchronous computations probably isn't going to fly.

I agree with that. It is different if quitting is slightly broken in comparison to hiccups because of new input. One could also make the async futures resilient against quitting, such that the cancel function would then be called. However this may lead to hangups, maybe one shouldn't do that.

Check out the definition of company--multi-backend-adapter-candidates. It tries to support that scenario, at the very least.
But as for taking advantage -- alas, most of the popular backends out there are synchronous. The popular asynchronous ones fell to the wayside when LSP arrived.

Good to hear that you have this supported. But I expected that there are not many asynchronous backends around in widespread use.

With the illustration, it becomes a little clearer. So the only times the "synchronized" async backends would be able to throw, is between their sit-for calls, when manually detecting that some input has arrived? That might work, I guess. The design is a little exotic, I'd say, but some MVP and testing it in practice might as well prove it viable.

Yes, there won't be any interrupt possible within the async table calls. The only interrupts can happen after the sit-for.

Only... perhaps don't use while-no-input? And instead catch a certain predefined symbol that the asynchronous "synchronized" tables are supposed to throw? This way the "normal" completion tables won't receive arbitrary interruptions, since they're not always prepared for them.

I see the problem with always wrapping with while-no-input. My idea was that capfs could report an :interruptible property and then the wrapping is applied. For other tables no while-no-input etc wrapping is applied.

On the other hand one could just treat completion all completion tables as interruptible and always wrap. The advantage is that this improves responsiveness for existing static tables at the risk of breaking some other tables. Furthermore there is a small advantage if the completion style performs expensive work, it could also be interrupted. My current solution is to use a cape-noninterruptible-capf wrapper. I don't know how often this is needed in practice.

But it seems the explicit symbol you propose is a good idea, maybe we should use that.

I'm still not crazy about it (as opposed to consistently using an async primitive and some standard functions and/or macros to manipulate them), but the tradeoffs could be worth it.

Well, I see it like this - the wrapping inside an interruptible completion table via the transformer allows us to basically keep all the existing infrastructure. And from the perspective of the backend, everything is asynchronous consistently.

See #14 for my recent version.

@jdtsmith
Copy link
Contributor Author

Do you envision backend authors need to tailor themselves to support either sync or async? Or is the idea that you only use a given async backend by wrapping it and presenting it as "synchronous, but unusually responsive given the slow process it connects to"?

I'm also not clear on why while-no-input would be much of an advantage, vs. the optional cooperative approach. This could easily be defeated by backend authors, and static in-process table aren't really the performance issue driving the need for async. I suspect many developers working on slow backends would be happy to have a simple way to increase responsiveness without breaking UI support, if things work as planned.

@minad
Copy link
Owner

minad commented Nov 29, 2021

Do you envision backend authors need to tailor themselves to support either sync or async?

Backend authors can either write synchronous or asynchronous backends. Both could be supported by Corfu/Cape/Company. So the answer is yes, but I don't know what you are actually asking.

Or is the idea that you only use a given async backend by wrapping it and presenting it as "synchronous, but unusually responsive given the slow process it connects to"?

I am not sure I understand you correctly. Do you ask - who is doing the wrapping? Is it the backend author or is the wrapping always applied by the frontend? The status quo in Corfu/Cape is that Corfu only knows interruptible capfs. Async capfs can be supported by wrapping them with cape-async-capf.

I'm also not clear on why while-no-input would be much of an advantage, vs. the optional cooperative approach. This could easily be defeated by backend authors.

For this I have the invincible cape-noninterruptible-capf, however it must be applied on a case by case basis.

But I have a good argument which may convince backend authors to write interruptible backends - performance/responsiveness. Noninterruptible Capfs lead to decreased responsiveness. However if it is too difficult or problematic to write a safe interruptible backend we can point them to cape-async-capf to the rescue. This is arguably a much nicer API. But note that for the async API the danger/difficulty lies elsewhere. Since this is a cooperative instead of a preemptive API it relies on the backend author to write code which does not hang up. Of course this is much less likely than writing code which behaves badly in the presence of interrupts.

and static in-process table aren't really the performance issue driving the need for async.

This is incorrect. For large static tables filtering can be slow. There is a reason why I use interruptible tables in Vertico/Corfu. In particular in Vertico C-h f and C-h v have large obarray tables with expensive predicates. Orderless filtering can also become slow if you use complicated regexps.

I suspect many developers working on slow backends would be happy to have a simple way to increase responsiveness without breaking UI support, if things work as planned.

Yes, they just have to return async values then, it should all be quite easy to use. Arbitrary frontends can be supported by wrapping the capf with cape-async-capf. This would work everywhere, Company/Corfu/default-ui.

However the frontend actively has to opt-in to the interruption by either using while-no-input like Corfu currently does or by setting the cape-async-throw-on-input variable to a symbol which signals interruption. This means with my prototype, currently only Corfu profits from the interruptibility. But see #14 where I write something about how the issue could be solved in company-capf.

The problem I am seeing is really to convince anyone of the backend authors to adopt this calling convention.

@jdtsmith
Copy link
Contributor Author

Do you envision backend authors need to tailor themselves to support either sync or async?
Backend authors can either write synchronous or asynchronous backends. Both could be supported by Corfu/Cape/Company. So the answer is yes, but I don't know what you are actually asking.

I think you figured me out despite my poor wording, but I'll rephrase perhaps more simply: are you authoring a new CAPF API for general use by many future UIs, or a single point of entry wrapper to translate ACAPFs -> CAPFs, such that UI's don't even know what happens (or both)?

So yes, who will wrap with cape-async-capf? A frontend like corfu, automatically? The user, in their config file? The backend author? And if the latter, are they then stuck with a backend that will otherwise NOT work well with e.g. company or default completion? Will you hope/expect company, for example, will directly support ACAPFs internally, such that backend-wrapping is counter-indicated? Or is it more desired to produce a CAPF which any current user-chosen UI (most of which will not interrupt) can make use of — "wrap once, use anywhere"? That will be important to document to get any adoption I suspect.

I'm happy to try out my (still unreleased) ipython mode as an async guinea pig once this settles down. I think I can see how to do it: set a buffer-local cancelled flag in the cancel callback, and if set, just discard process output until the prompt is seen, then reset everything. I don't have a way to ask the process to stop processing (though I could send it an interrupt signal I suppose).

It might also be sensible to make a fake process-facing backend which supplies random completions with arbitrary random delays to see how it performs (would also give bragging rights if it does much better than "just waiting" and is less error-prone than "interrupting without notice").

For this I have the invincible cape-noninterruptible-capf,

I meant can't a backend just (let (throw-on-input) (accept-process-output ....))) as kryptonite?

@minad
Copy link
Owner

minad commented Nov 29, 2021

So yes, who will wrap with cape-async-capf? A frontend like corfu, automatically? The user, in their config file? The backend author? And if the latter, are they then stuck with a backend that will otherwise NOT work well with e.g. company or default completion? Will you hope/expect company, for example, will directly support ACAPFs internally, such that backend-wrapping is counter-indicated? Or is it more desired to produce a CAPF which any current user-chosen UI (most of which will not interrupt) can make use of — "wrap once, use anywhere"? That will be important to document to get any adoption I suspect.

Most likely if we succeed - Company will support ACAPF directly since it has to be careful to integrate with its existing infrastructure. For Corfu one could just push Cape as a middleware during registration. But maybe I will simply detect asynchronous capfs in Corfu and also support them directly, moving that part from Cape to Corfu.

I'm happy to try out my (still unreleased) ipython mode as an async guinea pig once this settles down. I think I can see how to do it: set a buffer-local cancelled flag in the cancel callback, and if set, just discard process output until the prompt is seen, then reset everything. I don't have a way to ask the process to stop processing (though I could send it an interrupt signal I suppose).

Great. But instead of buffer local variables you should probably capture everything in closures.

I meant can't a backend just (let (throw-on-input) (accept-process-output ....))) as kryptonite?

Then it is non-interruptible and it will be slow and unresponsive. If that is the goal?

@minad
Copy link
Owner

minad commented Nov 29, 2021

@jdtsmith Btw, I am proposing to move to a five argument calling convention for the completion tables for safety reasons, see #14 (comment). Doing that would also make it easy to detect asynchronous completion tables (call with five args, if it fails treat the table as synchronous, otherwise continue to treat it as asynchronous).

@jdtsmith
Copy link
Contributor Author

I meant can't a backend just (let (throw-on-input) (accept-process-output ....))) as kryptonite?

Then it is non-interruptible and it will be slow and unresponsive. If that is the goal?

The goal is to solve the problem that unanticipated interruption leads to unwanted hidden output appearing in the inferior process buffer — a much worse problem than an extra 15ms pause. But now I'll have a much better way to solve it :).

But seriously part of the communication issue will be to (gently) convince backend authors that they either join the async API bandwagon, or risk being interrupted by brute force, with unpredictable consequences; i.e. async is the easier road. Which other UI's interrupt again?

@dgutov
Copy link

dgutov commented Dec 1, 2021

Most likely if we succeed - Company will support ACAPF directly since it has to be careful to integrate with its existing infrastructure.

But company-capf calls completion-all-completions, to have all completion requests go through the completion styles infrastructure.

For it to be able to use the asynchronous tables, won't that require completion-all-completions, completion-try-completion, etc (and that means the completion styles' code) to gain awareness of asynchronous tables?

Otherwise, company-capf--candidates would have to "synchronize" each such table first. Which would mean no possibility to use it in parallel with company-dabbrev-code, for example. Or company-yasnippet, or company-files.

@minad
Copy link
Owner

minad commented Dec 1, 2021

@dgutov Indeed.

For parallelization you would have to treat company capf specially. Parallelization multiple acapfs could work via a cape-super-acapf. To parallelize an acapf together with a company backend you would also have to handle the parallelization a level deeper and basically invert the handling. You could introduce a list of async calls to resolve and then the acapf synchronizer calls those too during synchronization and returns the results synchronously in the end.

The other approach would be to change the completion style infrastructure or to not make use of it. You could also implement your own asynchrouns completion styles in company. But this seems like more work and incompatibility with upstream?

See also my comment #14 (comment)

@minad
Copy link
Owner

minad commented Dec 1, 2021

@dgutov I m convinced that this can still be implemented in a reasonable clean way in Company. The only ugliness is really that when you resolve a group of backends with comoany-capf, then company-capf is in charge of synchronizing everything. If you synchronize a group of non-acapf backends you can synchronize them directly since you don't go through the synchronous completion style infrastructure. Arguably this promotes the company-capf backend to a bit of a special status.

But in practice it wouldn't be to bad. If you keep a variable company-async-call-list around which is a list of "jobs"/asynchronous calls, as soon as synchronization happens, this list is processed in parallel. This processing can then happen in the capf backend too and also at another place where we want to synchronize to get access to the results. But the code can be reused.

@dgutov
Copy link

dgutov commented Dec 2, 2021

The other approach would be to change the completion style infrastructure or to not make use of it. You could also implement your own asynchrouns completion styles in company. But this seems like more work and incompatibility with upstream?

I suppose that would be the way forward: to drop the company-backends support, basically. But that event has a whole list of requirements, as you probably recall.

The only ugliness is really that when you resolve a group of backends with comoany-capf, then company-capf is in charge of synchronizing everything. If you synchronize a group of non-acapf backends you can synchronize them directly since you don't go through the synchronous completion style infrastructure.

But company-capf works with the value of completion-at-point-functions, right? The value which may have been modified by the user, but more likely has been changed with add-hook by major and/or minor modes. And that very same value needs to work with M-x completion-at-point, Counsel, Corfu, and other frontends for CAPF. Right? Because otherwise we might as well go back to using company-backends.

And if M-x completion-at-point must be able to handle it, and it doesn't support async completion tables natively, then whatever completion tables are produced by said completion-at-point-functions elements, they must already be "synchronized". Maybe grouped at the same time, using a function combinator.

Which is to say, it probably can work, but company-capf won't be able to tell that those completion tables (or some of them) are "asynchronous" internally, and so no particular support for them would be possible or needed.

@minad
Copy link
Owner

minad commented Dec 2, 2021

I suppose that would be the way forward: to drop the company-backends support, basically. But that event has a whole list of requirements, as you probably recall.

Hmm, I would prefer to follow the approach with minimal impact as I proposed here instead of changing all the existing infrastructure.

But company-capf works with the value of completion-at-point-functions, right? The value which may have been modified by the user, but more likely has been changed with add-hook by major and/or minor modes. And that very same value needs to work with M-x completion-at-point, Counsel, Corfu, and other frontends for CAPF. Right? Because otherwise we might as well go back to using company-backends.

This is certainly an issue. But my idea would be to first support this in Company and Corfu (breaking support upstream if async capfs are registered in completion-at-point). Please keep in mind that this is reasonable, since people use older Emacsen. There is basically no way around this. But if you use Company or Corfu, there won't be an issue. In particular one could install an advice to the capf wrapper which fixes completion-at-point such that it works with acapfs if Company/Corfu are used.

And if M-x completion-at-point must be able to handle it, and it doesn't support async completion tables natively, then whatever completion tables are produced by said completion-at-point-functions elements, they must already be "synchronized". Maybe grouped at the same time, using a function combinator.

Multiple ways out:

  1. Fix via advice from outside
  2. We could also introduce a new variable completion-async-at-point-functions

You are right that you could just stick to company-backends. But this way one loses the advantage of inventing an API which is conceptually closer to the upstream infrastructure. I find this valuable and as we discussed it is possible to extend/overhaul this API gracefully with your idea of :async return values plus an adjusted filter argument to the table.

Which is to say, it probably can work, but company-capf won't be able to tell that those completion tables (or some of them) are "asynchronous" internally, and so no particular support for them would be possible or needed.

One could also do that - leave the entire support to a supplementary library like Cape. No special support in Corfu or Company needed, Cape would handle the synchronization and parallelization. In fact this is what the current implementation does - this is the MVP. The only question is if this would impede adoption. I am sure it would lead to friction. Probably it depends on if some major backends like lsp-mode are interested in this convention.

So I see all your points, you are right about them. I only disagree with the minimal vs major impact changes, where I would prefer the minimal impact approach even if it requires some unorthodox stacking of the capf transformations. The MVP I have in Cape would work as is, it leaves the entire process out of the existing infrastructure (Does not touch Corfu, Company or minibuffer.el). This is certainly nice and the whole idea of my Cape library - Cape is supposed to provide Capf transformers and a few useful Capfs. So from this point of view I am happy with Cape. I am also happy to maintain the async prototype infrastructure here.

What do you propose as next steps?

@dgutov
Copy link

dgutov commented Dec 6, 2021

I only disagree with the minimal vs major impact changes, where I would prefer the minimal impact approach even if it requires some unorthodox stacking of the capf transformations.

I suppose one reason for my disliking is it will stack a new and different design on top of an existing, already-complex one. Which would make the total sum more complicated further. To extend/develop/etc. Especially for future developers.

minibuffer.el is very ossified in its ways, and any new layer on top (instead of an approach favoring some big breakage) would encourage that ossification further. Whereas if we tried to bring "proper" futures into the core, it could encourage some constructive rewrites, better documentation, cutting off of edge cases, and so on. And, together with utility functions acting on futures, would encourage their use in other features that use asynchronous computations.

Anyway, it's a big job which I'm not itching to do myself, so I can't demand that of others either.

We could also introduce a new variable completion-async-at-point-functions

All right. But company-capf, as well as any other frontend, would still need to "pipe" the completion function through the completion styles, and that's usually the first thing they'd do. So aside from specifying the symbol that interrupted completion requests would throw, there's not much opportunity for it to benefit from the asynchronous nature of the table. company-capf would "synchronize" it and then pass to completion-all-completions and friends. It might as well be "synchronized" in advance by whatever piece of code set up the hook.

Then what's left of company-capf integration with the present proposal, is to just add a new dynamic binding.

Speaking further of completion-async-at-point-functions: one of the bits of information that a hook (such as completion-at-point-functions) stores is the ordering of functions. If some major/minor modes would use this hook, and others - the -async- one, the ordering between them can get lost.

@minad
Copy link
Owner

minad commented Dec 6, 2021

Okay, let's not pursue this here then.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants