respect completion-regexp-list

[jdtsmith]

• Server used: python-lsp-server
• Emacs version: GNU Emacs 27.2
• Operating system: MacOS
• Eglot version: 20210901.917
• Eglot installation method: package-install
• Using Doom: No

The basic completion docs for try-completion (also applying to test-completion, all-completions, etc.) state (emphasis added):

In addition, to be acceptable, a completion must also match all the
regular expressions in ‘completion-regexp-list’. (Unless
COLLECTION is a function, in which case that function has to handle
‘completion-regexp-list’ itself.)

The COLLECTION function provided by eglot does not appear to consider completion-regexp-list. This variable is important for completion styles such as orderless, which put completion-regexp-list to heavy work for candidate refinement. Since most in-built completion tables are obarrays, alists, hashes, etc., the issue really only pertains to programmed completion, such as in eglot. I have a small patch to the proxies lambda which implements this, and works well in my testing. Let me know if you'd like to see a PR. See also oantolin/orderless#78. Thanks for eglot!

[nemethf]

In Emacs version 26.1, the docstring at the end of try-completion says: Additionally to this predicate, ‘completion-regexp-list’
is used to further constrain the set of candidates. To me, this means that try-completion internally takes care of filtering candidates according to completion-regexp-list. However, Eglot doesn't use all-completion. Isn't that the root cause of this issue?

I'm guessing here, but appropriately changing cl-remove-if-not to all-completion after the "all-completion" comment might just fix the issue.

[joaotavora]

That's interesting @nemethf , can you confirm that it does the job. I need a suitable from-scratch reproduction recipe to be able to experience the incorrect behaviour and witness the correct behaviour after some fix. The issue-reporting template has intructions for providing such a thing.

[joaotavora]

I've converted this to a discussion. It can be a issue again once all the elements required to make one are provided, as per the template.

[jdtsmith]

Thanks for your thoughts.

My apologies for not including a reproduction recipe, this did not seem to me a "BUG" but rather a "FEATURE REQUEST". Here are the requested elements:

Minimal configuration (mandatory)

 # Type this in a shell to start an Emacs with Eglot configured
 $ emacs -Q -f package-initialize -L /path/to/git-cloned/eglot -l eglot.el 

;; Eval in *scratch* as directed
;;; Here we demonstrate the role of completion-regexp-list
(eglot-lsp-server- ; hit M-Tab here, notice 5 results 
(setq completion-regexp-list '("-c[hm]")) ; eval this, then re-try above completion: 3 results
(setq completion-regexp-list nil) ; reset to avoid issues

Now open a temporary python file and M-x eglot within it. Try the following:

import os
os.l # Hit M-Tab: 10 results

# Now M-: (setq completion-regexp-list '("d")) And try completion again:
# still 10 results.  This is incorrect behavior

# Now try with M-: (setq completion-regexp-list '("i")) : 4 results starting li

# Don't forget to reset completion-regexp-list!

This demonstrates how eglot is not filtering based on completion-regexp-list in the same manner as, e.g. emacs-lisp completion. As mentioned in the documentation for this variable, the capf function is supposed to ensure all results match all of the regexps in this list.

What I discovered in preparing this example is that eglot does however, seem to be doing prefix matching based on the completion-regexp-list. I was actually surprised about the prefix matching given the documentation advising, for function collection tables, "that function has to handle completion-regexp-list itself". I.e. I didn't expect it to do anything at all, and I'm not sure how or why it does this. But in any case, it's not the correct behavior, as can be seen by comparison with the emacs-lisp example.

Obviously this is a contrived example that would have little practical purpose. The real purpose is to support completion styles such as orderless, which use completion-regexp-list to filter on multiple filter terms at once. This does not work with eglot at present.

That said, before we could proceed with a fix, I think the first order of business is understanding how and where the incorrect prefix filtering is getting triggered. Any thoughts you had on this would be appreciated.

[joaotavora]

Thanks. I think I can work with these examples.

[joaotavora]

If you'd like to make this into an issue again with all the elements you've now provided, you can. If you prefer to leave this discussion open, that's also fine. Your call.

[jdtsmith]

@nemethf I've finally understood your point, thank you! The documentation regarding collection functions is correct, but elgot's CAPF collection function queries the LSP server and then caches a normal collection list. It then re-calls try/test-completion with this list. When called with such a normal (non-function) collection, try/test-completion do respect completion-regexp-list. But since all-completions isn't called as you note, this works only partially. I suspect this explains the strange partial prefix-style completion-regexp-list behavior.

@joaotavora We can keep it a discussion for now, no worries.

[jdtsmith]

I find replacing the cl-remove-if-not with a proper all-completions call, as suggested by @nemethf, does the trick:

          ((eq action t)                                 ; all-completions
	   (all-completions "" (funcall proxies)
			    (lambda (cand)
			      (let* ((item (get-text-property 0 'eglot--lsp-item cand))
				     (text (or (plist-get item :filterText) cand)))
				(and (string-prefix-p probe text completion-ignore-case)
				     (or (not pred) (funcall pred cand)))))))))

As a bonus, all-completions is much faster as it's in C.

[joaotavora]

Having a cursory look at the Gorfu issue you opened, it seems you bumped exactly into the problem I described.

[joaotavora]

Here's another piece of information you may be missing. The LSP server will only return new completions if the text is actually in the buffer (in the "shared" LSP document between client and server). So tweaking the pattern in a widget without actually changing the buffer will not request new completions: the change has to be sent over to the server, processed by it, and then a new textDocument/completion request is issued that hopefully takes the new LSP document in consideration. If you "cache" any of these resulting tables, you might get lucky or you might bump into trouble (as I've explained already).

[joaotavora]

@jdtsmith please make a PR of the code change you propose, it's easier to analyse there.

[jdtsmith]

Thanks for the thoughts. Eglot does cache LSP completions, for as long as its collection lambda is alive. With company, that's not very long (several calls to test/try/all-completion). For other UIs like corfu and completion in minibuffer, it's much longer. I think @minad makes a good argument that correct caching is up to the backend. Apparently VSCode caches (for speed).

I see your point about the client being unable to predict whether LSP will return the same completion set. I hadn't thought about incomplete lists of candidates (based on an LSP limit). Right now company is "doing this for" eglot.

Let me make a PR and perhaps a few of us can discuss there.

[joaotavora]

makes a good argument that correct caching is up to the backend. Apparently VSCode caches (for speed).

I don't know that argument: I just know that completion-at-point-functions 's docstring says that the return value of the functions you put there is to complete an "entity":

....
or a list of the form (START END COLLECTION . PROPS), where:
 START and END delimit the entity to complete and should include point,
 COLLECTION is the completion table to use to complete the entity, and
 PROPS is a property list for additional information.
....

It was around this docstring, not someone's opinions, that I built the Eglot table (and I've also built completion UIs btw). COLLECTION is the completion entity to complete the entity, not the entity and some variations on that entity.

So it you change the "entity" to complete and don't re-request completion-at-point-functions you'll run into problems.

Is experimenting with adding a few characters "changing the entity"? Sometimes, maybe not. Company seems to think it is, and VSCode followers would think it's not?

What about removing characters from it? I think it is, undeniably. It's pretty clear that the UI has to re-request a table to me. The entity to complete has changed.

[jdtsmith]

The speedup comes primarily from searching through a number of regexps, which all-completions does internally. Orderless benefits the most from this, as it reruns this type of search over and over on every character input. And since it compiles regexps from user input with a custom dispatcher, they do tend to get some length and complexity. The general vertico/embark/consult/orderless group of packages all use native completion internally for speed.

Here's an example that shows a bit more than 3x speedup for me:

(let ((candidates (cl-loop
		  repeat 10000
		  for len = (+ 5 (random 12))
		  for word = (cl-loop repeat len concat (string (+ ?a (random 26))))
		  collect word))
      (completion-regexp-list '("[a-d]$"
				"r..[pqr]"
				"\\([^mpqr]\\)\\{3\\}.*[b-n]\\1[a-x]"
				"[a-k][k-z]\\{5\\}.*?[a-m]")))

  (list
   (benchmark-run 100 (length (all-completions "" candidates)))
   (benchmark-run 100 (length
    (cl-remove-if-not
     (lambda (cand)
       (cl-every (lambda (regexp)
		   (string-match-p regexp cand))
		 completion-regexp-list))
     candidates)))))

((0.339078 0 0.0) (1.175021 0 0.0))

[joaotavora]

The speedup comes primarily from searching through a number of regexps,

Right: it's faster when there are regexps, but slower when there are none. This is why I asked what your benchmark case is.

[jdtsmith]

Indeed, the very case that motivated this discussion! With orderless, there are always regexps. Sometimes lots. I recognize that other completion environments don't have this particular issue.

[jdtsmith]

__

The speedup comes primarily from searching through a number of regexps,

Right: it's faster when there are regexps, but slower when there are none. This is why I asked what your benchmark case is.

Just an FYI, on my system all-completions is about 10% faster on your benchmark. So similar speed. How does it compare for you with the regexps? It's clearly quite dependent on how selective the early regexps are in my testing.

[joaotavora]

When regexps are involved, all-completions is much faster, as I've previously reported, I think.

[joaotavora]

The general vertico/embark/consult/orderless group of packages all use native completion internally for speed.

All completion tools I know use "native" completion (which I think is what you mean by calling into C code) to a certain degree. Here you are grouping completion UIs and completion tables and completion styles, if I'm not mistaken.

I understand that your general perception is that this combo is "fast", but as I said, I would like to see objective benchmarks and numbers, preferably measuring each of these in isolated and controlled conditions. But not need to provide this to for this particular matter regarding completion-regexp-list, it's just a general with of mine :-)

[jdtsmith]

The comparison is not against other completion tools, but other selection tools for buffers/files/variables/imenu listings/bookmarks/etc. Things like consult for example use completion to make filtering through these as fast as completion by using the speed of all-completions. I don't have specific benchmarks.

[joaotavora]

The comparison is not against other completion tools, but other selection tools for buffers/files/variables/imenu listings/bookmarks/etc. Things like consult for example use completion to make filtering through these as fast as completion by using the speed of all-completions. I don't have specific benchmarks.

In my limited understanding consult is a sort of completion table and vertico is an UI, both can be used with any other table/UI. So I'm still very confused (but that's ok).

When talking about speed, some kind of quantitative really is generally useful to understand what one is talking about, else my dentist is faster because she uses elephants :)

[jdtsmith]

Again without benchmarks, the quantitive (but broad) category is: how to rapidly select from a large number of possibilities by prefix, sub-string, multiple-regexps, etc. Those possibilities could be "things to insert in the buffer" aka completion, but also many many others. I think my example above proves that at least for some limited aspects of this problem space, using the internal completion (written in C) is a faster solution than reasonably efficient Elisp. And I really don't find that surprising at all. But maybe your dentist's elephants can make some more benchmarks for her to investigate :). This is for Emacs 27; I haven't tried the new JIT compiled Emacs 28, which may reduce the distance between approaches.

Consult is basically a tool that takes all kinds of Emacs selection problems, and runs them through mini-buffer completion (with all its configurability). Files (like ido/fido/etc.). Buffers. Macros to run. Bookmarks. Matching lines. Imenu items. Markers. Command history. (Rip)Grep search results. Yank history. Registers. You get the idea.

Once I get it working well maybe I'll make a small video of eglot + corfu[1] + orderless doing their thing.

[1] corfu is the vertico sibling which provides in-buffer completion, kind of like company

[jdtsmith]

For posterity, this got fixed in PR #733 and 9b63f21.