Re: scratch/backend-completion aaaa016056 2/2: Speed it up

Re: scratch/backend-completion aaaa016056 2/2: Speed it up

[Stefan Monnier]

> diff --git a/lisp/external-completion.el b/lisp/external-completion.el
> index da3a986b8c..25e94e540b 100644
> --- a/lisp/external-completion.el
> +++ b/lisp/external-completion.el
> @@ -104,8 +104,10 @@ taking a (STRING POINT) as arguments.  The default is to set to
>           `(external-completion-allc . ,(if pred (seq-filter pred all) all))))
>        (`(boundaries . ,_) nil)
>        (_
> -       (let ((all (funcall lookup string (length string))))
> -         (complete-with-action action all string pred))))))
> +       ;; FIXME: Stefan had a call to `lookup' and
> +       ;; `complete-with-action' again here, but that just seems to
> +       ;; slow down things for no good reason, so I took it out.
> +       ))))

The code was definitely needed for some cases like `try-completion`
and `all-completions` (e.g. to make sure we only return completion
of the `string` *prefix* as callers of those functions expect and to
make sure we obey `pred`).

But I'm surprised it made things slow: this code should only be involved
when the user choose some *other* completion style, so could you check
which method of the completion table was invoked?

Maybe we should only use that code when `action` is one of `t` or `nil`?


        Stefan

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[Stefan Monnier]

>     Integrate Stefan suggestions but rename it to "external-completion.el"

Ha!  Great minds thing alike!

> +(add-to-list 'completion-styles-alist
> +             '(external-completion-style

This sounds a bit like the RAS syndrome, just without the acronym.
Why not use just `external`?

> +(defun external-completion-table (lookup
> +                                 category &optional metadata
> +                                 try-completion-function)

Ah, I see you made tryc optional :-)
I'd put `category` on the first line, tho.
If you don't like the resulting indentation of the second line, then
just add a space before "lookup" :-).

> +TRY-COMPLETION-FUNCTION is an poorly understood implementation detail.

Not at all.  It's a functionality that only makes sense for some UIs
(not those based on the idea of selecting among a set of choices), and
it tends to work better with more "primitive" completion styles (it
asymptotically becomes useless the harder the completion style tries to
find completions).

The goal of "try completion" is, given STRING and POINT, to return
the longest string COMPLETION (together with a NEWPOINT) such that
(allc STRING POINT) = (allc COMPLETION NEWPOINT).

> +(defun external-completion--try-completion (string table pred point)
> +  (external-completion--call 'external-completion-tryc string table pred point))

AFAICT the `external-completion-tryc/allc` symbols are not exposed to
users of this library any more so we could use ones with a double hyphen.


        Stefan

Re: scratch/backend-completion aaaa016056 2/2: Speed it up

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 852 bytes --]

> But I'm surprised it made things slow: this code should only be involved
> when the user choose some *other* completion style, so could you check
> which method of the completion table was invoked?

It seems to be called with both `nil` and `lambda`. I've added this to the
FIXME comment.

It made things slow because when selecting a candidate with
fido-vertical-mode it did another useless 0.5s/1s lookup for the thing
I had just selected.

> Maybe we should only use that code when `action` is one of `t` or `nil`?

Maybe.  Anyway in my tests it's working fine without it.  But `nil` doesn't
break them, so I'm fine if you add them.  I'm just confused about the
possible benefits that may come from that complexity.  I wish you could
post an illustrative example with some strings that a mere mortal might
follow along.

João

[-- Attachment #2: Type: text/html, Size: 1088 bytes --]

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 1781 bytes --]

On Sat, Dec 3, 2022 at 2:26 PM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:
> >     Integrate Stefan suggestions but rename it to
"external-completion.el"
> Ha!  Great minds thing alike!

Nice!

> > +(add-to-list 'completion-styles-alist
> > +             '(external-completion-style
>
> This sounds a bit like the RAS syndrome, just without the acronym.
> Why not use just `external`?

Good idea. Done.

> > +(defun external-completion-table (lookup
> > +                                 category &optional metadata
> > +                                 try-completion-function)
>
> Ah, I see you made tryc optional :-)
> I'd put `category` on the first line, tho.
> If you don't like the resulting indentation of the second line, then
> just add a space before "lookup" :-).

Haha.  Yes I fixed it.  And category is now the first argument, I think it's
slightly more logical.

> > +TRY-COMPLETION-FUNCTION is an poorly understood implementation detail.
>
> Not at all.  It's a functionality that only makes sense for some UIs
> (not those based on the idea of selecting among a set of choices), and
> it tends to work better with more "primitive" completion styles (it
> asymptotically becomes useless the harder the completion style tries to
> find completions).

I'm still confused, I need examples to understand this stuff, and I'm afraid
If I do I'll forget all about it next time around. But personally I don't
_have_ to
understand it, really.  Been using this for years successfully without
understanding it, so why should I start now? I made the docstring
even more cheeky so you can see what I mean.

> AFAICT the `external-completion-tryc/allc` symbols are not exposed to
> users of this library any more so we could use ones with a double hyphen.

Good idea. Done.

[-- Attachment #2: Type: text/html, Size: 2349 bytes --]

Re: scratch/backend-completion aaaa016056 2/2: Speed it up

[Stefan Monnier]

>> But I'm surprised it made things slow: this code should only be involved
>> when the user choose some *other* completion style, so could you check
>> which method of the completion table was invoked?
> It seems to be called with both `nil` and `lambda`. I've added this to the
> FIXME comment.

Hmm... can you get a backtrace for when it's called with `nil`?

> It made things slow because when selecting a candidate with
> fido-vertical-mode it did another useless 0.5s/1s lookup for the thing
> I had just selected.

Yes, it's only meant as a fallback case (and if we intend it to work
more or less acceptably we'd need to add some caching).

>> Maybe we should only use that code when `action` is one of `t` or `nil`?
> Maybe.  Anyway in my tests it's working fine without it.  But `nil` doesn't
> break them, so I'm fine if you add them.  I'm just confused about the
> possible benefits that may come from that complexity.  I wish you could
> post an illustrative example with some strings that a mere mortal might
> follow along.

As I said, it's for the case where the users want to use that completion
table with another completion-style.


        Stefan

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[Stefan Monnier]

>> > +TRY-COMPLETION-FUNCTION is an poorly understood implementation detail.
>>
>> Not at all.  It's a functionality that only makes sense for some UIs
>> (not those based on the idea of selecting among a set of choices), and
>> it tends to work better with more "primitive" completion styles (it
>> asymptotically becomes useless the harder the completion style tries to
>> find completions).
>
> I'm still confused, I need examples to understand this stuff, and I'm afraid

E.g. for the completion table of ELisp commands the `try-completion` for
the `partial-completion` style of "r-bu" might be "re-bu" because all
the completion candidates of "r-bu" have an "e" right after the "r", so
"re-bu" selects exactly the same set of candidates.  Similarly for
"di-hu" it may return "diff-hunk" because all the candidates have "ff"
after the "di" and "nk" after the "-hu".

This is the standard "TAB completion" behavior: instead of asking you to
*select* a candidate it "types the text for you" (hence the name
"completion") without trying to guess which candidate you're going to go
for: its only "guess" is that your goal is somewhere among
the candidates.

For prefix completion, it works great.
For completion styles like `flex`, it's rarely able to complete anything.


        Stefan

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 1202 bytes --]

On Sun, Dec 4, 2022, 00:31 Stefan Monnier <monnier@iro.umontreal.ca> wrote:.

>
> For prefix completion, it works great.
> For completion styles like `flex`, it's rarely able to complete anything.


Alright, that helps, thanks. But what use can you imagine try-completion
having with an external tool like LSP or my everything.exe client which
does regex-style?  Or some other external tool you can think of...

Is it perhaps that the caller of our new function might look at the tool's
results for PATTERN and then, knowing the implicit style the tool is
employing, use TRY-COMPLETION-FUNCTION to extend  the string being used for
PATTERN at the completion locus?  This would make some sense, but then
again probably only be actually useful if the caller is adept of caching
the results of the calls to LOOKUP.

Else, I think we end up contacting the external tool one too many times for
the same PATTERN. That's at least with the popular completion front-ends
such as fido/vertico who probably go for the 'allc' immediately.

Maybe  'external-completion-function' could be doing some
per-table-per-PATTERN caching, to relieve the caller of this complication.

João

>
>

[-- Attachment #2: Type: text/html, Size: 1917 bytes --]

Re: scratch/backend-completion aaaa016056 2/2: Speed it up

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 5049 bytes --]

On Sun, Dec 4, 2022 at 12:18 AM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:
>
> >> But I'm surprised it made things slow: this code should only be
involved
> >> when the user choose some *other* completion style, so could you check
> >> which method of the completion table was invoked?
> > It seems to be called with both `nil` and `lambda`. I've added this to
the
> > FIXME comment.
>
> Hmm... can you get a backtrace for when it's called with `nil`?

See after my sig:

> > It made things slow because when selecting a candidate with
> > fido-vertical-mode it did another useless 0.5s/1s lookup for the thing
> > I had just selected.
>
> Yes, it's only meant as a fallback case (and if we intend it to work
> more or less acceptably we'd need to add some caching).

Been there, done that :-)

> >> Maybe we should only use that code when `action` is one of `t` or
`nil`?
> > Maybe.  Anyway in my tests it's working fine without it.  But `nil`
doesn't
> > break them, so I'm fine if you add them.  I'm just confused about the
> > possible benefits that may come from that complexity.  I wish you could
> > post an illustrative example with some strings that a mere mortal might
> > follow along.
>
> As I said, it's for the case where the users want to use that completion
> table with another completion-style.

See the comment block.  I think we should just error if the user tries
to do that.

João

Here's the backtrace you ordered, sir:

Debugger entered: nil
  #f(compiled-function (--cl-lookup-internal-- string pred action method)
#<bytecode -0x1dfbb45767c3fc90>)(#f(compiled-function (string point)
#<bytecode -0x1a49dbcf59322b1d>) "doc/misc/eglot.texi" nil nil nil)
  #f(compiled-function (string pred action) #<bytecode
-0x6cbef0a719c4d65>)("doc/misc/eglot.texi" nil nil)
  try-completion("doc/misc/eglot.texi" #f(compiled-function (string pred
action) #<bytecode -0x6cbef0a719c4d65>) nil)
  completion--complete-and-exit(41 60 exit-minibuffer #f(compiled-function
() #<bytecode -0x18333a20a7fa497>))
  minibuffer-force-complete-and-exit()
  icomplete-force-complete-and-exit()
  icomplete-fido-ret()
  funcall-interactively(icomplete-fido-ret)
  call-interactively(icomplete-fido-ret nil nil)
  command-execute(icomplete-fido-ret)
  read-from-minibuffer("Eel find file in ~/Source/Emacs/emacs/: " nil
(keymap (menu-bar keymap (minibuf "Minibuf" keymap (tab menu-item
"Complete" minibuffer-complete :help "Complete as far as possible") (space
menu-item "Complete Word" minibuffer-complete-word :help "Complete at most
one word") (63 menu-item "List Completions" minibuffer-completion-help
:help "Display all possible completions") "Minibuf")) (M-down .
minibuffer-next-completion) (M-up . minibuffer-previous-completion) (27
keymap (13 . minibuffer-choose-completion) (103 keymap (27 keymap (99 .
switch-to-completions))) (118 . switch-to-completions)) (prior .
switch-to-completions) (63 . minibuffer-completion-help) (32 .
minibuffer-complete-word) (backtab . minibuffer-complete) (9 .
minibuffer-complete) keymap (menu-bar keymap (minibuf "Minibuf" keymap
(previous menu-item "Previous History Item" previous-history-element :help
"Put previous minibuffer history element in the min...") (next menu-item
"Next History Item" next-history-element :help "Put next minibuffer history
element in the minibuf...") (isearch-backward menu-item "Isearch History
Backward" isearch-backward :help "Incrementally search minibuffer history
backward") (isearch-forward menu-item "Isearch History Forward"
isearch-forward :help "Incrementally search minibuffer history forward")
(return menu-item "Enter" exit-minibuffer :key-sequence "\15" :help
"Terminate input and exit minibuffer") (quit menu-item "Quit"
abort-recursive-edit :help "Abort input and exit minibuffer") "Minibuf"))
(24 keymap (down . minibuffer-complete-defaults) (up .
minibuffer-complete-history)) (13 . exit-minibuffer) (10 . exit-minibuffer)
(7 . minibuffer-keyboard-quit) (C-tab . file-cache-minibuffer-complete) (9
. self-insert-command) (XF86Back . previous-history-element) (up .
previous-line-or-history-element) (prior . previous-history-element)
(XF86Forward . next-history-element) (down . next-line-or-history-element)
(next . next-history-element) (27 keymap (60 .
minibuffer-beginning-of-buffer) (114 . previous-matching-history-element)
(115 . next-matching-history-element) (112 . previous-history-element) (110
. next-history-element))) nil nil nil nil)
  completing-read-default("Eel find file in ~/Source/Emacs/emacs/: "
#f(compiled-function (string pred action) #<bytecode -0x6cbef0a719c4d65>)
nil nil nil nil nil nil)
  completing-read("Eel find file in ~/Source/Emacs/emacs/: "
#f(compiled-function (string pred action) #<bytecode -0x6cbef0a719c4d65>)
nil nil nil nil)
  eel-find-file("~/Source/Emacs/emacs/")
  funcall-interactively(eel-find-file "~/Source/Emacs/emacs/")
  call-interactively(eel-find-file nil nil)
  command-execute(eel-find-file)

[-- Attachment #2: Type: text/html, Size: 5890 bytes --]

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[Stefan Monnier]

>> For prefix completion, it works great.
>> For completion styles like `flex`, it's rarely able to complete anything.
> Alright, that helps, thanks. But what use can you imagine try-completion
> having with an external tool like LSP or my everything.exe client which
> does regex-style?  Or some other external tool you can think of...

There's one I can think of: SLY, because there external tool's
completion code can be tweaked to fit the needs of Emacs :-)

For most others it's probably difficult, indeed, which is why
I suggested to make it optional (unless you know how the tool
does its matching in which case you may be able to re-use
`completion-pcm--merge-try` or to implement something similar).

> Else, I think we end up contacting the external tool one too many times for
> the same PATTERN. That's at least with the popular completion front-ends
> such as fido/vertico who probably go for the 'allc' immediately.

The default UI uses either tryc (when you hit TAB) or allc (when you
ask the see *Completions*) not both.


        Stefan

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 1316 bytes --]

On Sun, Dec 4, 2022, 16:54 Stefan Monnier <monnier@iro.umontreal.ca> wrote:

There's one I can think of: SLY, because there external tool's
> completion code can be tweaked to fit the needs of Emacs :-)
>
> For most others it's probably difficult, indeed, which is why
> I suggested to make it optional (unless you know how the tool
> does its matching in which case you may be able to re-use
> `completion-pcm--merge-try` or to implement something similar).
>

Yup, this rhymes exactly with what I wrote in the docstring in the latest
version.  I understand how it could be used now. Another question is if I
as SLY author would use it. I don't think so, to be honest, seems to much
hassle for not a lot of benefit. But others may want to, of course.

> Else, I think we end up contacting the external tool one too many times
> for
> > the same PATTERN. That's at least with the popular completion front-ends
> > such as fido/vertico who probably go for the 'allc' immediately.
>
> The default UI uses either tryc (when you hit TAB) or allc (when you
> ask the see *Completions*) not both.


Yes and eventually if you hit TAB twice that's two requests. So we need
caching. But that's fine, I've implemented that already. Have a look at the
latest commit when you find the time.

João

[-- Attachment #2: Type: text/html, Size: 2018 bytes --]

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[Stefan Monnier]

> Yup, this rhymes exactly with what I wrote in the docstring in the latest
> version.  I understand how it could be used now.

Looks great to me, thanks,

> Another question is if I as SLY author would use it.  I don't think
> so, to be honest, seems to much hassle for not a lot of benefit.
> But others may want to, of course.


        Stefan

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 1210 bytes --]

On Tue, Dec 6, 2022 at 12:14 AM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:
>
> > Yup, this rhymes exactly with what I wrote in the docstring in the
latest
> > version.  I understand how it could be used now.
>
> Looks great to me, thanks,

Great!  I've now tidied up the branch and pushed it to
feature/external-completion

Eli, if you haven't been following this discussion closely, this is a
refactor of
functionality already present in Eglot that consolidates the support for
offering completions coming from external tools (like LSP servers, but not
only)
and makes it available to more third party packages.

I think there shouldn't be any adverse effects of pushing this to the
emacs-29
branch, but if you think it's better, I'll push it to master instead.

It shouldn't make much of a difference since the new external-completion.el
file is going to be a GNU ELPA :core package and as such it will be
available
in Emacs 28 anyway via package-install.

Let me know what you think.  The commentary of the new file, the docstring
of external-completion-table and the commit messages should give details.
I'll be happy to fix them further if you have comments.

João

[-- Attachment #2: Type: text/html, Size: 1539 bytes --]

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[Eli Zaretskii]

> From: João Távora <joaotavora@gmail.com>
> Date: Wed, 7 Dec 2022 11:09:02 +0000
> Cc: emacs-devel <emacs-devel@gnu.org>
> 
> Eli, if you haven't been following this discussion closely, this is a refactor of 
> functionality already present in Eglot that consolidates the support for
> offering completions coming from external tools (like LSP servers, but not only)
> and makes it available to more third party packages.
> 
> I think there shouldn't be any adverse effects of pushing this to the emacs-29
> branch, but if you think it's better, I'll push it to master instead.
> 
> It shouldn't make much of a difference since the new external-completion.el
> file is going to be a GNU ELPA :core package and as such it will be available
> in Emacs 28 anyway via package-install.
> 
> Let me know what you think.  The commentary of the new file, the docstring
> of external-completion-table and the commit messages should give details.
> I'll be happy to fix them further if you have comments.

I'm fine with installing this on the emacs-29 branch, but I think
external-completion.el warrants a NEWS entry.

Re: scratch/backend-completion 9a62da21c2 1/2: Integrate Stefan suggestions but rename it to "external-completion.el"

[João Távora]

[-- Attachment #1: Type: text/plain, Size: 483 bytes --]

On Wed, Dec 7, 2022 at 1:56 PM Eli Zaretskii <eliz@gnu.org> wrote:


> > Let me know what you think.  The commentary of the new file, the
> docstring
> > of external-completion-table and the commit messages should give details.
> > I'll be happy to fix them further if you have comments.
>
> I'm fine with installing this on the emacs-29 branch, but I think
> external-completion.el warrants a NEWS entry.
>

Okay.  I added a NEWS entry and pushed to emacs-29.

João

[-- Attachment #2: Type: text/html, Size: 814 bytes --]