bug#22407: Better support external completion tools

bug#22407: Better support external completion tools

[Stefan Monnier]

Package: Emacs
Version: 25.1.50


The current minibuffer.el code is sometimes inconvenient to use for some
packages because the only hooks it provides is for the package to give
the output of `all-completions' and `try-completion' (basically), which
is too limiting when the completion is performed by outside tools which
may provide natively things like "substring" matching.

We should add new methods to the completion-tables (beside the
existing try, all, test, boundaries, and metadata) that allow the
completion table to provide its own version of completion-try-completion
and completion-all-completions.

Clearly, that means that `completion-styles' wouldn't be automatically
honored, so it'd be up to those completion tables to do their best to
try and honor `completion-styles' (or not).

Note: checking (memq 'partial-completion completion-styles) is
fundamentally broken since the user may be using its own
`my-partial-completion' instead.  So maybe to avoid this problem and
make it easier for those completion-tables to honor `completion-styles',
we could extend `completion-styles-alist' so that each style can provide
some "description" of the kinds of candidates it would accept.  Not sure
what that "description" could look like, tho.  Maybe a function which
takes a user-input string and return a regexp, or maybe a simple
predicate taking a user input string and a candidate and returns whether
to keep it or not.  Probably neither would work well enough, tho
(e.g. if the completion-table includes candidates that fix typos in the
user-input string).


        Stefan



In GNU Emacs 25.1.50.1 (x86_64-unknown-linux-gnu, X toolkit, Xaw scroll bars)
 of 2016-01-14 built on pastel
Repository revision: b8d080b21a801fe70170b15b663888d19df4a32d
Windowing system distributor 'The X.Org Foundation', version 11.0.11604000
System Description:	Debian GNU/Linux 8.2 (jessie)

Configured using:
 'configure -C --enable-checking --enable-check-lisp-object-type
 'CFLAGS=-Wall -g3 -Og -Wno-pointer-sign'
 PKG_CONFIG_PATH=/home/monnier/lib/pkgconfig'

Configured features:
XPM JPEG TIFF GIF PNG SOUND NOTIFY GNUTLS LIBXML2 FREETYPE XFT ZLIB
TOOLKIT_SCROLL_BARS LUCID X11

Important settings:
  value of $LANG: fr_CH.UTF-8
  locale-coding-system: utf-8-unix

Major mode: InactiveMinibuffer

Minor modes in effect:
  c-electric-flag: t
  dired-omit-mode: t
  shell-dirtrack-mode: t
  diff-auto-refine-mode: t
  electric-pair-mode: t
  global-reveal-mode: t
  reveal-mode: t
  auto-insert-mode: t
  savehist-mode: t
  minibuffer-electric-default-mode: t
  url-handler-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  global-prettify-symbols-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Recent messages:
Finding changes in /home/monnier/src/emacs/work/lisp/nxml/nxml-mode.el...done
Hunk already applied
Saving file /home/monnier/src/emacs/work/lisp/nxml/nxml-mode.el...
Wrote /home/monnier/src/emacs/work/lisp/nxml/nxml-mode.el
Finding changes in /home/monnier/src/emacs/work/lisp/nxml/nxml-mode.el...done
Making completion list...
Quit

Making completion list...
Quit

Load-path shadows:
/home/monnier/src/emacs/elpa/packages/ada-mode/ada-ref-man hides /home/monnier/src/emacs/elpa/packages/ada-ref-man/ada-ref-man
/home/monnier/src/emacs/elpa/packages/avy/.dir-locals hides /home/monnier/src/emacs/elpa/packages/company-statistics/.dir-locals
/home/monnier/src/emacs/elpa/packages/avy/.dir-locals hides /home/monnier/src/emacs/elpa/packages/company/.dir-locals
/home/monnier/src/emacs/elpa/packages/avy/.dir-locals hides /home/monnier/src/emacs/elpa/packages/gnugo/.dir-locals
/home/monnier/src/emacs/elpa/packages/avy/.dir-locals hides /home/monnier/src/emacs/elpa/packages/hydra/.dir-locals
/home/monnier/src/emacs/elpa/packages/avy/.dir-locals hides /home/monnier/src/emacs/elpa/packages/js2-mode/.dir-locals
/home/monnier/src/emacs/elpa/packages/ada-mode/ada-prj hides /home/monnier/src/emacs/work/lisp/progmodes/ada-prj
/home/monnier/src/emacs/elpa/packages/ada-mode/ada-stmt hides /home/monnier/src/emacs/work/lisp/progmodes/ada-stmt
/home/monnier/src/emacs/elpa/packages/ada-mode/ada-mode hides /home/monnier/src/emacs/work/lisp/progmodes/ada-mode
/home/monnier/src/emacs/elpa/packages/ada-mode/ada-xref hides /home/monnier/src/emacs/work/lisp/progmodes/ada-xref
/home/monnier/src/emacs/elpa/packages/avy/.dir-locals hides /home/monnier/src/emacs/work/lisp/gnus/.dir-locals
/home/monnier/src/emacs/elpa/packages/crisp/crisp hides /home/monnier/src/emacs/work/lisp/obsolete/crisp
/home/monnier/src/emacs/elpa/packages/landmark/landmark hides /home/monnier/src/emacs/work/lisp/obsolete/landmark
/home/monnier/src/emacs/work/lisp/emacs-lisp/cl-generic hides /home/monnier/src/emacs/elpa/packages/cl-generic/cl-generic

Features:
(sort mail-extr emacsbug css-mode skeleton sm-c-mode ffap two-column
smerge-mode whitespace smie log-edit message sendmail rfc822 mml mml-sec
mm-decode mm-bodies mm-encode mail-parse rfc2231 rfc2047 rfc2045
ietf-drums mailabbrev mail-utils mailheader pcvs-util vc-bzr vc-src
vc-sccs vc-svn vc-cvs vc-rcs vc-dir let-alist derived inline epg subr-x
package-x dabbrev rect cc-mode cl-seq cc-fonts cc-guess cc-menus cc-cmds
cc-styles cc-align cc-engine cc-langs cc-vars cc-defs python tramp-sh
tramp tramp-compat tramp-loaddefs trampver format-spec json dired-x
dired dired-loaddefs bug-reference add-log eieio-opt speedbar sb-image
ezimage dframe texnfo-upd texinfo sgml-mode nxml-uchnm rng-xsd
xsd-regexp rng-cmpct character-fold misearch multi-isearch shell
pcomplete grep compile vc vc-dispatcher map rng-nxml rng-valid rng-loc
rng-uri rng-parse nxml-parse rng-match rng-dt rng-util rng-pttrn nxml-ns
nxml-mode nxml-outln nxml-rap nxml-util nxml-glyph nxml-enc xmltok
executable copyright xscheme warnings unsafep trace testcover shadow
scheme re-builder profiler inf-lisp ielm comint ansi-color ring
gmm-utils ert pp find-func ewoc debug elp edebug cl-indent cus-edit
cus-start cus-load wid-edit vc-git diff-mode filecache seq server
noutline outline easy-mmode flyspell ispell checkdoc thingatpt load-dir
elec-pair reveal autoinsert proof-site proof-autoloads cl pg-vars
savehist minibuf-eldef disp-table edmacro kmacro advice info finder-inf
package epg-config url-handlers url-parse auth-source eieio byte-opt
bytecomp byte-compile cl-extra cconv eieio-core cl-macs gv
eieio-loaddefs gnus-util time-date mm-util help-fns help-mode easymenu
cl-loaddefs pcase cl-lib mail-prsvr password-cache url-vars
bbdb-autoloads vm-autoloads mule-util tooltip eldoc electric uniquify
ediff-hook vc-hooks lisp-float-type mwheel x-win term/common-win x-dnd
tool-bar dnd fontset image regexp-opt fringe tabulated-list newcomment
elisp-mode lisp-mode prog-mode register page menu-bar rfn-eshadow timer
select scroll-bar mouse jit-lock font-lock syntax font-core frame
cl-generic cham georgian utf-8-lang misc-lang vietnamese tibetan thai
tai-viet lao korean japanese eucjp-ms cp51932 hebrew greek romanian
slovak czech european ethiopic indian cyrillic chinese charscript
case-table epa-hook jka-cmpr-hook help simple abbrev obarray minibuffer
cl-preloaded nadvice loaddefs button faces cus-face macroexp files
text-properties overlay sha1 md5 base64 format env code-pages mule
custom widget hashtable-print-readable backquote inotify dynamic-setting
font-render-setting x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 571183 143835)
 (symbols 48 44226 0) (miscs 40 10879 3055) (strings 32 116260 12700)
 (string-bytes 1 3071372)
 (vectors 16 68223) (vector-slots 8 2435977 194326) (floats 8 797 593)
 (intervals 56 51774 1418)
 (buffers 976 122) (heap 1024 766281 15256))

bug#22407: Better support external completion tools

[Dmitry Gutov]

On 01/19/2016 05:19 PM, Stefan Monnier wrote:

> Note: checking (memq 'partial-completion completion-styles) is
> fundamentally broken since the user may be using its own
> `my-partial-completion' instead.

On the other hand, the external tool might simply have a set of matcher 
styles you can ask it to use. Then memq could at least be helpful.

> So maybe to avoid this problem and
> make it easier for those completion-tables to honor `completion-styles',
> we could extend `completion-styles-alist' so that each style can provide
> some "description" of the kinds of candidates it would accept.  Not sure
> what that "description" could look like, tho.  Maybe a function which
> takes a user-input string and return a regexp, or maybe a simple
> predicate taking a user input string and a candidate and returns whether
> to keep it or not.

I don't see how the predicate could be used at all. As for regexp, we 
should make a survey of the existing external completion tools, and see 
how many of them take a regexp for this purpose.

There's also the issue of Emacs/basic/extended regexp syntax.

As an aside, I wonder if the current completion styles, at least, could 
each be automatically implemented on top of the input-to-regexp 
functions, without loss in efficiency. Is the completion boundaries, 
used by partial-completion, the main problem?

> Probably neither would work well enough, tho
> (e.g. if the completion-table includes candidates that fix typos in the
> user-input string).

Neither will be perfect, that's for sure. But maybe we don't have to 
worry about that too much: IME, users are mostly interested in the 
distinction between prefix and fuzzy completion, with many preferring 
the latter.

The next question becomes how to sort (or not) the returned list: fuzzy 
matching returns lots of matches, so they're usually sorted at the same 
time. If completion-at-point re-sorts them alphabetically, that 
advantage will be lost. Using #'identity as display-sort-function should 
work, though.

bug#22407: Better support external completion tools

[Stefan Monnier]

> I don't see how the predicate could be used at all. As for regexp, we should
> make a survey of the existing external completion tools, and see how many of
> them take a regexp for this purpose.

I was thinking of applying (within Emacs) the regexp/predicate to a list
of candidate returned by the external tool.  Not passing it directly to
the external tool

> As an aside, I wonder if the current completion styles, at least, could each
> be automatically implemented on top of the input-to-regexp functions,
> without loss in efficiency.

"input-to-regexp"?  Sorry, doesn't ring a bell.

>> Probably neither would work well enough, tho (e.g. if the
>> completion-table includes candidates that fix typos in the user-input
>> string).
> Neither will be perfect, that's for sure. But maybe we don't have to worry
> about that too much: IME, users are mostly interested in the distinction
> between prefix and fuzzy completion, with many preferring the latter.

Agreed.  Honoring completion-styles is not very important.

> Using #'identity as display-sort-function should work, though.

Exactly.


        Stefan

bug#22407: Better support external completion tools

[Dmitry Gutov]

On 01/20/2016 05:31 AM, Stefan Monnier wrote:

> I was thinking of applying (within Emacs) the regexp/predicate to a list
> of candidate returned by the external tool.  Not passing it directly to
> the external tool

That would make it harder to use external tools that operate on large 
datasets. And since essentially, with this approach we're not delegating 
filtering to the external tool, it seems like it should work with the 
current completion-styles mechanism. No need to allow overriding 
completion-all-completions.

>> As an aside, I wonder if the current completion styles, at least, could each
>> be automatically implemented on top of the input-to-regexp functions,
>> without loss in efficiency.
>
> "input-to-regexp"?  Sorry, doesn't ring a bell.

"a function which takes a user-input string and return a regexp".

Could we use that not just as "description", but as definition for 
existing styles. And maybe keep the current mechanism for the trickier ones.

bug#22407: Better support external completion tools

[Stefan Monnier]

>> I was thinking of applying (within Emacs) the regexp/predicate to a list
>> of candidate returned by the external tool.  Not passing it directly to
>> the external tool
> That would make it harder to use external tools that operate on large
> datasets. And since essentially, with this approach we're not delegating
> filtering to the external tool, it seems like it should work with the
> current completion-styles mechanism. No need to allow overriding
> completion-all-completions.

I guess you're right: it would only work in those cases where the
current system is already usable.  After all, all-completions already
has the completion-regexp-list at hand, if it wants to use it.

So for now, all we can do is to hope that the external tool can "honor"
the completion-styles somehow, but without providing any specific help
for that.

>>> As an aside, I wonder if the current completion styles, at least, could each
>>> be automatically implemented on top of the input-to-regexp functions,
>>> without loss in efficiency.
>> "input-to-regexp"?  Sorry, doesn't ring a bell.
> "a function which takes a user-input string and return a regexp".
> Could we use that not just as "description", but as definition for existing
> styles. And maybe keep the current mechanism for the trickier ones.

The current code already uses "turn input into a regexp, then use this
regexp to filter the worthy candidates".

We should add a `regexp' completion-style.  I never got around to do it,
but it shouldn't be very hard and it would probably provide the kinds of
function you're looking for.  Note that for the general "I just have
a regexp" case, implementing a good "try-completion" is hard.

And yes, partial-completion has additional complexity on top of that to
exploit boundaries so you can type C-x C-f ~/e/e/e TAB and have it
complete to ~/etc/emacs/emacs.el, but for the common boundary-free case
(or for completion-styles which don't want to do anything clever with
boundaries) it's not that hard.


        Stefan