The greedy regexp matching, broken scoring and broken highlight were
sources of frequent complaints about the 'flex' matching style. This
commit fixes that.
Inspired by the 'hotfuzz' style (available at
https://github.com/axelf4/hotfuzz) it uses a modified version of Gotoh's
1982 dynamic programming algorithm. It is strictly more correct than the
"old" flex. For example, when matching the pattern 'goto' to no longer
will 'eglot-format' be sorted before some hypothetical much better
'goobarbaz-goto'. And of course the highlighting is also correctly
placed on the 'goto', not scattered across the candidate.
Regarding performance, it is faster than the naive 'flex', primarily
because of the Elisp rewrite in minibuffer.el. The matching and costing
algorithm matters but is not the bottleneck.
The Elisp parts of the style were almost completely decoupled from the
pcm/substring styles in lisp/minibuffer.el. Only
'completion-flex-try-completion' uses some of pcm's code for pattern
augmentation.
* src/minibuf.c (completion--flex-cost-gotoh): New function.
* lisp/minibuffer.el (completion-flex--pattern-str): New variable.
(flex-score-match-tightness): Make obsolete.
(completion--flex-all-completions-1): New helper function.
(completion-flex-try-completion, completion-flex-all-completions): Rewrite.
(completion-substring--all-completions): No longer take transform-pattern-fn.
(completion--flex-adjust-metadata): Tweak.
(completion--flex-score, completion--flex-score-1)
(completion--flex-score-last-md, completion-flex--make-flex-pattern): Delete.
* test/lisp/minibuffer-tests.el (completion--sorted-flex-completions):
New helper function.
(completion-flex-test-non-ascii): New test.
(completion--pcm-score): Delete.
(completion-pcm-test-3, completion-pcm-test-4)
(completion-substring-test-1, completion-substring-test-2)
(completion-flex-test-2, completion-flex-test-3): Tweak.
* etc/NEWS: Describe change.
The core of the problem is that `completion-pcm--prepare-delim-re`
is designed to match a "delimiter" in the pattern but was misused
to match a sequence of delimiter chars in the completions.
* lisp/minibuffer.el (completion-pcm--delim-re): Rename from
`completion-pcm--prepare-delim-re` and change its calling convention.
(completion-pcm--segments->regex): Use it.
(completion-pcm-word-delimiters): Adjust accordingly.
* test/lisp/minibuffer-tests.el (completion-pcm--test-zerowidth-delim):
New test.
When multiple wildcards occur in a PCM pattern,
completion-pcm--pattern->regex previously would generate one
instance of [^z-a]* for each of those wildcards, even if the
wildcards were adjacent and could therefore be matched by a
single [^z-a]*. This can make regex matching performance much
worse. For example, with a minibuffer containing "*/" with
point at the start, completion-pcm-all-completions would take
several seconds to match in project-find-file in the Emacs repo.
Now, we run completion-pcm--pattern->segments on the pattern
first, which adds additional structure to the pattern, including
consolidating adjacent regexes into a single sublist. Then
completion-pcm--segments->regex generates a single regex
wildcard for each of those pattern wildcards. As a consequence,
we need to update the callers of completion-pcm--pattern->regex
which pass non-nil GROUP. This provides a substantial
performance improvement in various edge cases.
* lisp/minibuffer.el (completion-pcm--pattern->segments)
(completion-pcm--segments->regex): Add. (bug#79693)
(completion-pcm--pattern->regex)
(completion-pcm--merge-completions): Call pattern->segments and
segments->regex.
(completion-pcm--pattern-point-idx): Delete.
(completion-pcm--segments-point-idx): Add.
(completion-pcm--hilit-commonality): Call
completion-pcm--segments-point-idx to find the submatch
containing point.
* test/lisp/minibuffer-tests.el (completion-pcm-test-5): Add
more tests of highlighting the first difference.
(completion-pcm-test-pattern->regex): Add tests showing the
regex form of PCM patterns.
When completion-ignore-case is non-nil, if all completions share
a common prefix ignoring case, try-completion has always
returned that. Now, if all completions also share a common
prefix including case, try-completion includes that common
prefix in its return value (bug#79377).
* lisp/minibuffer.el (completion-pcm--merge-completions): Always
use return value from try-completion, which may change case.
* src/minibuf.c (Ftry_completion): Return the common prefix
which changes case.
* test/lisp/minibuffer-tests.el (completion-pcm-bug4219)
(completion-substring-test-5): New tests.
* test/lisp/minibuffer-tests.el (with-minibuffer-setup)
(completing-read-with-minibuffer-setup): Prevent instrumenting
functions that call these macros from erroring due to an invalid
debug specification in the 'declare' form. Use 't' as the debug
spec since it is the most general and adequate here.
This patch makes 'next-completion' and 'previous-completion' work
in the vertical completions format analogously to how they work in
the default horizontal format (bug#78959). It also fixes wrapping
in the vertical format and confines navigation (including
wrapping) in column-wise movement in the vertical format to the
current line, analogously to how navigation (including wrapping)
in line-wise movement in the horizontal format is confined to the
current column.
* doc/emacs/mini.texi (Completion): Fix several typos and improve
wording is several places.
(Completion Commands): Document navigation of the *Completions*
buffer in the vertical format. Document the difference between
format-sensitive movement and strictly column-wise or line-wise
movement. Document 'minibuffer-complete-and-exit' and update the
documentation of 'minibuffer-completion-auto-choose' and
'minibuffer-choose-completion'. Document the use of a numeric
prefix argument with the navigation commands.
(Completion Options): Rearrange and improve documentation of
'completions-sort', 'completions-format' and
'completion-auto-wrap', updating the latter to document the new
behavior.
* lisp/minibuffer.el (minibuffer-visible-completions-map): Rebind
"<left>" to 'minibuffer-previous-column-completion' and "<right>"
to 'minibuffer-next-column-completion'.
(minibuffer-next-completion): Add check for whether completions
format is vertical to decide whether to call
'next-line-completion' and replace calling 'next-completion' by
'next-column-completion'.
(minibuffer-next-column-completion)
(minibuffer-previous-column-completion): New commands.
* lisp/simple.el (completion-list-mode-map): Rebind "<left>" to
'previous-column-completion' and "<right>" to 'next-column-completion'.
(last-completion): Add handling for vertical completions format.
(completion--move-to-candidate-end): Always move point to the
position immediately after the last character of the completion
candidate. This unifies the behavior, simplifies the
implementation and facilitates implementing the improved
navigation of the *Completions* buffer.
(previous-column-completion, next-column-completion): New
commands, replacing the previous definitions of
'previous-completion' and 'next-completion' to reflect their
column-wise operation. Confine navigation (including wrapping) in
vertical format to the current line.
(previous-line-completion, next-line-completion): Implement
line-wise navigation (including wrapping) through all completions
in vertical format, not just those in the current column as in
horiztonal format. Update doc strings.
(next-completion, previous-completion): Redefine to call
'{next,previous}-line-completion' when completions format is
vertical and '{next,previous}-column-completion' otherwise.
* test/lisp/minibuffer-tests.el
(completions-format-navigation--tests): New function providing a
template to define tests of the navigation and wrapping behavior
with specified numbers of completion candidates.
(completions-format-navigation-test-{2,3,4,5,10,15,16}): New tests.
* lisp/minibuffer.el (define-completion-category): New function.
(completion-category-get): New function, implements completion
category property lookup with (multiple) inheritance.
(completion-metadata-get, completion--styles)
(completion--cycle-threshold): Use it.
(completion-category-defaults): Mention it in docstring.
Remove entry for 'project-buffer' category, and instead...
* lisp/progmodes/project.el: ...have 'project-buffer' inherit
from 'buffer'.
* test/lisp/minibuffer-tests.el
(completion-category-inheritance): New test.
* etc/NEWS: Announce support for category inheritance.
Revert "Avoid duplicating strings in pcm--merge-completions",
commit b511c38bba. It broke
existing behavior, now covered by tests adding in this commit.
* lisp/minibuffer.el (completion-pcm--merge-completions):
* test/lisp/minibuffer-tests.el (completion-pcm-test-anydelim):
(completion-pcm-bug4219):
Previously, one could select a completion via M-<up>/M-<down>,
but then RET would not actually select the chosen completion.
With the addition of completion-auto-deselect, this is not
actually necessary: we can reasonably assume that when a
completion is selected, the user wants to use that, since their
last action must have been to select it. So, just choose the
selected completion on RET. This lets us default
minibuffer-completion-auto-choose to nil.
For minibuffers with require-match completion, this can be done
by changing the existing command bound to RET. For minibuffers
with nil require-match completion, RET was previously bound to
exit-minibuffer, and changing exit-minibuffer to have this logic
is risky. We handle that case by adding a new
minibuffer-completion-exit which wraps exit-minibuffer and bind
RET to it.
* lisp/minibuffer.el (minibuffer-insert-completion-if-selected)
(minibuffer-completion-exit, completion--selected-candidate):
Add.
(minibuffer-complete-and-exit): Call
minibuffer-choose-completion. (bug#77253)
(minibuffer-local-completion-map): Bind RET to
minibuffer-completion-exit, overriding exit-minibuffer.
(completion-in-region-mode-map): Bind RET to
minibuffer-choose-completion when there's a selected candidate.
(minibuffer-completion-auto-choose): Default to nil.
(minibuffer-visible-completions--filter)
(minibuffer-visible-completions-map): Delete RET binding, no
longer necessary.
* lisp/simple.el (completion-setup-function): Update completion
help text to show more correct bindings.
* test/lisp/minibuffer-tests.el (completions-header-format-test)
(minibuffer-next-completion): Set
minibuffer-completion-auto-choose=t explicitly.
(with-minibuffer-setup, minibuffer-completion-RET-prefix)
(completion-in-region-next-completion): Add new tests.
* etc/NEWS: Announce.
At various places, instead of just checking that there's any
window displaying a buffer named *Completions*, we should
additionally check that that *Completions* buffer is actually
for the current completion session.
minibuffer--completions-visible does that.
* lisp/comint.el (comint-complete-input-ring)
(comint-dynamic-list-completions): Call
minibuffer--completions-visible.
* lisp/minibuffer.el (minibuffer--completions-visible):
Add. (bug#77253)
(completion--do-completion, completions--post-command-update)
(completions--after-change, minibuffer-hide-completions)
(minibuffer-visible-completions)
(minibuffer-visible-completions--always-bind)
(minibuffer-visible-completions--filter)
(with-minibuffer-completions-window, minibuffer-complete-history)
(minibuffer-complete-defaults): Call
minibuffer--completions-visible.
* lisp/pcomplete.el (pcomplete-show-completions): Call
minibuffer--completions-visible.
* lisp/simple.el (switch-to-completions): Call
minibuffer--completions-visible.
* test/lisp/minibuffer-tests.el (completion-auto-help-test)
(completion-auto-select-test): Call
minibuffer--completions-visible.
Properly fix bug#38458, which is fundamentally an issue with
completion-ignore-case, by checking if the completions are
unique ignoring case. When the completions are unique, the
normal code to delete a wildcard naturally causes point to be
moved to the end of the minibuffer, which is the correct
behavior.
Now that the bug is fixed properly, remove a hack which
previously was used to "fix" it, which made point behave
inconsistently if it was in the middle of the minibuffer versus
at the end of the minibuffer.
* lisp/minibuffer.el (completion-pcm--merge-completions):
Respect completion-ignore-case when checking for completion
uniqueness. (bug#79265)
(completion-pcm--string->pattern)
(completion-pcm--optimize-pattern): Allow point at the end of
the pattern.
* test/lisp/minibuffer-tests.el (completion-table-test-quoting)
(completion-test--pcm-bug38458, completion-pcm-test-8): Update
tests for more correct behavior.
509cbe1c35 "Improve env var handling in read-file-name"
caused 'try-completion' and 'all-completion' operations with
'completion--file-name-table' to no longer update the case of
text which was already present in the input string. That is,
completions would be returned ignoring case, but the completions
would have letter-casing which matched the input string rather
than matching the actual file names.
This was caused by unnecessarily replacing text in the returned
file name completions with text from the input string ORIG,
which in turn was caused by the desire to preserve text from
ORIG even after 'substitute-in-file-name' changed it. Fix this
by detecting when ORIG was not substantially changed by
'substitute-in-file-name'; in that case, the returned file name
completions also don't need substantial changes.
* lisp/minibuffer.el (completion--file-name-table): Use text
from the completions, not the input string. (Bug#78323)
* test/lisp/minibuffer-tests.el (completion-table-test-quoting):
Test with 'completion-ignore-case' as well.
Fix various bugs, including bug#77718, by rewriting the way file
name completion handles environment variable expansion. Instead
of using completion-table-with-quoting to manipulate the string
being completed on, simply make the completion table itself
understand substitute-in-file-name.
Tests are updated: partial-completion now preserves unexpanded
environment variables. However, partial-completion no longer
works across environment variables containing delimiters; that's
an acceptable sacrifice.
* lisp/minibuffer.el (completion--sifn-boundaries): Add.
(completion--file-name-table): Rewrite to use
substitute-in-file-name explicitly. (bug#77718)
* test/lisp/minibuffer-tests.el (completion-table-test-quoting):
Update.
An explicitly typed * has different semantics from automatically
inserted PCM wildcards, so it should be preserved on try-completion. We
already do this in some cases, but now we do it more.
This is especially significant for filename completion: removing an
explicit * can take us from
~/src/emacs/trunk/*/minibuf
to
~/src/emacs/trunk//minibuf
The explicit double slash is interpreted by the file name completion
table to mean "start completing from the root directory", so deleting
the * here substantially changes semantics.
* lisp/minibuffer.el (completion-pcm--merge-completions): Don't drop
important wildcards. (bug#74420)
* test/lisp/minibuffer-tests.el (completion-pcm-test-7): Add tests.
In 03ac16ece4 I fixed a bug with the
PCM implementation of substring completion, relating to the handling
of PCM wildcards.
However, this fix was incomplete. This change completes the fix by
also including a fixed string if it appears before a 'prefix'
wildcard, even if 'try-completion' doesn't discover that fixed
string grows to a unique completion.
I discovered this bug while working on enhancements to PCM
completion related to 'completion-pcm-leading-wildcard'.
* lisp/minibuffer.el (completion-pcm--merge-completions): Include
fixed strings before 'prefix wildcard. (Bug#72819)
* test/lisp/minibuffer-tests.el (completion-substring-test-5): Add a
test for this behavior.
Simplify to not compare the result of 'move-to-column'
with the value 'column'. Such comparison prevented from moving
over lines without completion candidates such as group lines (bug#68688).
* test/lisp/minibuffer-tests.el (completions-group-navigation-test):
Add more group candidates to create more columns and to test
moving over group lines and over columns without candidates.
Previously it would not move out of a multi-line completion, and now it will.
* lisp/simple.el (next-line-completion): Move to the completion start
or end before going forward or backward lines. (bug#68688)
* doc/lispref/minibuf.texi (Completion Variables): Add
to the table of completion-extra-properties new items:
`group-function', `display-sort-function', `cycle-sort-function'.
* lisp/icomplete.el (icomplete--augment): Remove unnecessary
plist-get from completion-extra-properties since now
completion-metadata-get does this.
* lisp/minibuffer.el (completion-metadata-get): Use plist-get to
get prop from completion-extra-properties and cache the keyword.
Thanks to Daniel Mendler <mail@daniel-mendler.de>.
(completion-extra-properties): Mention new properties in docstring.
(minibuffer-completion-help): Remove unnecessary
plist-get from completion-extra-properties since now
completion-metadata-get does this.
* lisp/net/eww.el (eww-switch-to-buffer):
* test/lisp/minibuffer-tests.el (completions-affixation-navigation-test):
Unquote lambda in completion-extra-properties.
bug#48841, bug#47711
In some instances the test code needed to be updated to make different
assumptions about implementation details.
In others, like the ones about the completions-first-difference face,
minor parts of the actual user-visible behaviour were broken.
* test/lisp/minibuffer-tests.el (completion-test1): Robustify test.
(completion--pcm-score): Don't assume completion-score is stored
in string as a property.
* lisp/minibuffer.el (completion--hilit-from-re): Take new parameter.
(completion-pcm--hilit-commonality): Use it.
* lisp/simple.el (next-line-completion): Improve (bug#59486).
Better handle the case when completion-auto-wrap is nil.
* test/lisp/minibuffer-tests.el (completion-auto-wrap-test)
(completions-header-format-test)
(completions-affixation-navigation-test): Add calls to
'next-line-completion' and 'previous-line-completion'.
(completions-group-navigation-test): New test.
Substring completion would previously not complete the longest common
substring if that substring was a prefix of all the completion
alternatives. Now it does. An explanation of this bug
Substring completion is implemented by passing the `prefix' symbol as
part of the pattern passed to completion-pcm--merge-completions. This
symbol is supposed to cause completion-pcm--merge-completions to
"grow" a completion of a common substring only from the "right" of the
symbol (a common suffix), not from the "left" of the symbol (a common
prefix). Yes, this is the opposite of what the name `prefix' would
imply.
When processing a symbolic element of the pattern,
completion-pcm--merge-completions first finds the common prefix of all
the completions in that part of the pattern (using try-completion).
Then for `prefix' and other elements which want to complete a common
suffix, the common prefix is removed from each element and then the
common suffix is calculated with completion--common-suffix.
If the common prefix covers the entirety of all the alternatives
(i.e. when "unique" is true in the code), it's also a common suffix.
In that case, the common suffix calculation (if it runs) is basically
a no-op which will produce an empty string, since we removed the
common prefix before running it.
Before this change, `prefix' elements would unconditionally discard
the common prefix, which produced the wrong result in the case that
common prefix == common suffix. For example:
(completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
-> ("b")
Now we detect this situation and include the common prefix in this
case for `prefix' elements. Then we get:
(completion-pcm--merge-completions '("ab" "ab") '(prefix "b"))
-> ("b" "a")
which is correct.
* lisp/minibuffer.el (completion-pcm--merge-completions): Don't ignore
a common suffix in a `prefix' pattern element when it's also a common
prefix.
* test/lisp/minibuffer-tests.el (completion-substring-test-5): Add a
test.
* test/lisp/minibuffer-tests.el (completion-auto-help-test): Add
test for when 'completion-auto-help' is 'visible'. Also test
for successful completion message. (Bug#63913)
* lisp/simple.el (first-completion): Add the text-property 'first-completion'
when the first completion is at the beginning of the buffer.
* test/lisp/minibuffer-tests.el (completions-header-format-test):
Revert the recent change.
* lisp/ido.el: Use first-completion instead of next-completion.
* lisp/minibuffer.el (completion--insert): Put completion--string
text property on prefix and suffix as well.
* lisp/simple.el (first-completion, last-completion): New commands.
(next-completion): Rewrite to fix many bugs reported in
bug#54374, bug#55289, bug#55430.
(choose-completion): Use the text property completion--string that
allows to select a completion when point is on its prefix or suffix.
(switch-to-completions): Use first-completion instead of next-completion,
and last-completion instead of previous-completion.
* test/lisp/minibuffer-tests.el (completion-auto-select-test)
(completion-auto-wrap-test, completions-header-format-test)
(completions-affixation-navigation-test): Uncomment fixed lines.
* test/lisp/minibuffer-tests.el (completing-read-with-minibuffer-setup):
New macro based on xdisp-tests--in-minibuffer.
(completion-auto-help-test, completion-auto-select-test)
(completion-auto-wrap-test, completions-header-format-test)
(completions-affixation-navigation-test): New tests.
Preprocess the history (and the default) through the new function
`minibuffer--sort-preprocess-history` to filter out the completion
base for completion tables with boundaries (in particular the file
completion table).
* lisp/minibuffer.el (minibuffer--sort-preprocess-history_: New function.
(completion-all-sorted-completions): Use it.
* test/lisp/minibuffer-tests.el (completion-all-sorted-completions):
Add tests for various combinations of with/without history/base/default.
Even for a trivial underlying completion table (where the 'boundaries'
action returns nil), we need to provide nontrivial boundaries so that
they match the behavior of 'all-completions'.
* lisp/minibuffer.el (completion-table-subvert): Return boundaries
even for trivial underlying completion table.
* test/lisp/minibuffer-tests.el (completion-table-subvert-test):
Amend unit test to also test boundaries. While there, also test
the other completion functions.
* lisp/minibuffer.el (completion--insert-strings):
Don't add 'completions-annotations' face when the caller
specified own face in annotation-function.
Remove no-op code for 'unless prefix' branch.
(completion-metadata, completion-extra-properties):
Update docs of affixation-function.
Suggested by Clemens <clemera@posteo.net> (bug#45780)
* test/lisp/minibuffer-tests.el: Rename package name from
completion-tests.el to minibuffer-tests.el.
Add new test completion--insert-strings-faces.
* doc/lispref/minibuf.texi (Completion Variables)
(Programmed Completion): Update descriptions of
annotation-function and affixation-function.
