Icicles - Progressive Completion

Previous: Icicles - Expanded-Common-Match CompletionIciclesIciclesIndexNext: Icicles - Regressive Completion

Progressive Completion

Perhaps the best way to explain this feature is to use a familiar analogy. Unix or GNU/Linux command ‘grep’ takes a regular-expression (regexp) argument, and matches it against lines in files. A common idiom that people use is to chain, or cascade, multiple calls to ‘grep’, using the output of one as the input to the next. For example:

  grep plant *.txt | grep food | grep mineral

The output of the search for “plant” is used as the input for the search for “food”, and the output of that search serves as the input for the search for “mineral”. The order of the three component searches can make a difference in terms of performance, but not in terms of the result, which is always the set of lines in files *.txt that match “plantand

foodandmineral”, in any order. Each of the ‘grep’ operations defines a set of matches, and the chain of ‘grep’ operations effects the intersection of those sets.

Of course, you could try to accomplish the same thing with a single call to ‘grep’ using a complex regexp. But why would you?

Moreover, it is in fact impossible to express such an unordered set intersection using a single regexp. On their own, regular expressions cannot express set intersection (conjunction) or complementing (negation). (However, most ‘grep’ programs provide a way to obtain the lines that do not match a regexp.)

The same idea of combining multiple regexp matches is behind the Icicles feature of progressive completion: instead of trying to come up with a single complex regexp that does what you want, try getting there a step at a time:

  1. Match an input regexp against the set of all possible completions.
  2. Narrow the set of matched candidates by matching them against another input regexp (or by filtering them with a predicate).
  3. Narrow those results down by matching them against a third input regexp (or by filtering them with another predicate).
  4. … And so on.

`M-*' and `S-SPC': Matching Additional Regexps

During completion, ‘M-*’ is bound in the minibuffer to command ‘icicle-narrow-candidates’, which prompts for a new regexp and matches it against the current set of completion candidates.

As is often the case in Icicles, you can think of the ‘*’ in ‘M-*’ as mnemonic for Boolean multiplication, that is, AND, or set intersection. (It is more common and handier to use ‘S-SPC’ than ‘M-*’ – see Successive Approximation.)

For example, suppose that you want to know about an Emacs function that deletes the character to the left of point (that is, backward). You do not recall if it is ‘delete-character-back’, ‘delete-backward-char’, ‘character-delete-backward’, or whatever. You take a guess that the name contains ‘delete’, ‘char’, and ‘back’.

  1. ‘C-h f char S-TAB’ displays function names that contain “char”.
  2. ‘M-* delete’ narrows that set of function names to those that also contain “delete”.
  3. ‘M-* back’ narrows the set of matching names further, to those that also contain “back”.

This displays a list of functions like this in ‘*Completions*’ (your list might be somewhat different):

     backward-delete-char             backward-delete-char-untabify
     delete-backward-char             icicle-backward-delete-char-untabify
     icicle-delete-backward-char      quail-conversion-backward-delete-char

Then, of course, you can pick one (or you can use ‘C-M-next’ repeatedly to view the doc string of each of these functions in turn – see Icicles - Help on Candidates).

You get the idea. This feature is both very simple to use and very useful. It’s easy to appreciate using multiple simple matching steps (regexp or not) instead of a single regexp. Try it once, and you’ll be hooked.

Successive Approximation...

You can use as many invocations of ‘M-*’ (and of `M-&’, described in the next section) as you like, in any order. It works with both prefix completion and apropos completion.

You can, for instance, first use ‘TAB’ to require the target to start with some string, and then use ‘M-*’ to specify other patterns that parts of it must also match. However, it of course makes no sense to use ‘TAB’ instead of ‘S-TAB’ after you use ‘M-*’: once you’ve said that the target must start with “fo” there is no sense saying that it also starts with “ti”!

As a shortcut, instead of using ‘S-TAB’ followed by ‘M-*’, you can use ‘S-SPC’ (command ‘icicle-apropos-complete-and-narrow’) to do the same thing. You can thus use only ‘S-SPC’, any number of times, to choose a candidate by narrowing down the matches.

Note that if the current Icicles completion method is ‘basic’ (see Icicles - Completion Methods and Styles) and you initiate completion using prefix completion (‘TAB’), then Icicles implicitly prefixes your minibuffer input with “^” if you then use progressive completion (e.g. ‘S-SPC’). No such convenience is possible if the completion method is not ‘basic’, because completion does not necessarily match your input as a prefix. In this case, if you want to treat your input as a prefix then you need to prefix it with “^” explicitly.

With a prefix argument, ‘S-SPC’ uses predicate narrowing, that is, ‘C-u S-SPC’ is the same as ‘S-TAB’ followed by `M-&’ (described in the next section).

I call this process of completion by successive approximation, or progressively narrowing the candidate set, “progressive completion”. If the name “incremental completion” (= icompletion) were not already taken to mean incremental completion help (which actually performs no completion), then that might be a good name for this. This might also be called “stepped”, “cascaded”, or “piecewise” completion.

Another possible name for it would be “multiple completion”, but I use that to stand for simultaneous (parallel) completion of multiple parts of a compound target, which is something different (see Icicles - Multi-Completions). Progressive completion is a set of mini-completions that are wired in series, not in parallel.

Note that when you use candidate narrowing (‘M-*’, `M-&’, or ‘S-SPC’) in the minibuffer, it calls ‘completing-read’, which creates a recursive minibuffer. That is, the minibuffer depth is increased. In vanilla Emacs, there is no indicator of the current minibuffer depth, and this can sometimes be disorienting. Each time you narrow the set of current candidates, you push down one level of minibuffer recursion (that is, minibuffer depth is incremented). Each time you use, say, ‘C-g’, you pop up one level of minibuffer recursion (that is, minibuffer depth is decremented).

If you use library mb-depth.el, which is included with Emacs 23 and which also works with Emacs 22, Icicle mode takes advantage of this library by indicating the current depth in the minibuffer. I recommend you also use my library mb-depth+.el, which lets you customize the form and face of the depth indicator. See MinibufferDepthIndicator.

If you use my library oneonone.el, then you get visual feedback on the current minibuffer depth. OneOnOneEmacs gives you a standalone minibuffer frame, and it changes the background hue (color) of that frame slightly with each change in minibuffer depth. This is especially helpful with Icicles, where use of candidate narrowing (progressive completion) is common. See Dedicated Minibuffer Frame.

There is a slight difference in behavior between Icicles commands and some other Emacs commands when you accept input after narrowing. When possible, Icicles accepts your input and passes it immediately to the top level, bypassing any intermediate recursive minibuffer levels that are waiting for input. However, Emacs commands that are defined with ‘interactive’ specs, such as (interactive "fFile:"), do not use ‘completing-read’ or ‘read-file-name’, so there is no way for Icicles to take this shortcut with them. In that case, you will simply need to hit ‘RET’ again to accept your input at each recursive minibuffer level, until you get back to the top level. Sorry for this inconvenience! If you are an EmacsLisp programmer, note that this is one reason to use ‘completing-read’ and ‘read-file-name’ when you write commands that use completion.

Note: If you use progressive completion with file names in Emacs 20 or 21 then candidate narrowing invokes ‘completing-read’, not ‘read-file-name’. This is because ‘read-file-name’ does not accept a PREDICATE argument before Emacs 22. The effect is that instead of there being a default directory for completion, the current directory at the time you narrow is tacked onto each file name, to become part of the completion candidates themselves. Yes, this is a hack. It works, but be aware of the behavior.

Progressive completion lets you match multiple regexps, some of which could of course be literal substrings, with their regexp special characters, if any, escaped. If you need to match such substrings at particular locations in the target completion candidate, then progressive completion will not do the job – it matches its component regexps independently. You can regexp-quote (escape) parts or all of your input using `M-%’ (‘icicle-regexp-quote-input’). See Escaping Special Characters.

`M-&': Satisfying Additional Predicates

If you use Icicles, then you will use candidate narrowing (progressive completion) very often. This section describes `M-&’ (‘icicle-narrow-candidates-with-predicate’), which is like ‘M-*’ (‘icicle-narrow-candidates’) except that it also restricts candidates by using a predicate for filtering.

(If you are new to Icicles or you are unfamiliar with EmacsLisp, then you might want to just skim this section or skip it and come back to it later.)

Just as you can use ‘M-*’ or ‘S-SPC’ to narrow the set of candidates by matching an additional regexp, so you can use `M-&’ or ‘C-u S-SPC’ to narrow by satisfying an additional predicate. The idea is the same; the only difference is that are prompted for a predicate for the current candidates to satisfy.

This must be a Boolean function of a single completion candidate. At the prompt, you enter its name or its lambda-expression definition (anonymous function).

Completion is available for some existing predicate names appropriate for the current command. For example, if you use `C-x 4 f TAB M-&’ then you can complete against the file-name predicates named in option `icicle-cand-preds-for-file’. This lets you quickly filter by file type: directories, executables, compressed files, remote files, desktop files, and so on. If you use a prefix arg with `M-&’ then additional predicate completion candidates are available (they might or might not be appropriate for the current command).

The predicate you choose is used the same way as the PREDICATE argument to ‘completing-read’ and ‘read-file-name’. This means that the candidate argument to the predicate is a full completion candidate; it is not just a string such as you see in buffer ‘*Completions*’.

The type of full completion candidate expected by the predicate is, to start with, whatever is used in the original call to ‘completing-read’ or ‘read-file-name’; it is not just a string such as you see in buffer ‘*Completions*’. To provide an appropriate predicate, you must be familiar with the kind of candidate expected by the command you invoked before just before `M-&’.

For example:

The type of candidate expected by the current command might be a symbol, a string, or a cons with a string car. It might even be an Icicles multi-completion, which in its full form is a cons with a list of strings as its car.

Knowing what kind of completions the original ‘completing-read’ or ‘read-file-name’ call expects is not sufficient, however. You might use `M-&’ after otherwise narrowing the set of candidates, and narrowing changes the full candidates to be conses whose car is a string.

For example, command ‘describe-variable’ reads a variable name, using completion with Lisp symbols as its full candidates. But if you narrow your input matches (e.g. using ‘S-SPC’), then the full candidates are no longer symbols; they are conses with symbol names (strings) as their cars.

So if you define your own predicate for use with a command such as ‘describe-variable’ then it will need to work with either a symbol or a cons that has a symbol-name (string) as its car.

If you want to adapt an existing predicate that expects a ‘*Completions*’ display candidate (a string) then you can use function ‘icicle-display-cand-from-full-cand’ in your predicate definition. If multi-completion is involved then you can use function ‘icicle-transform-multi-completion’.

In sum: if you want to adapt an existing predicate that expects an argument that is not a cons with a string car, then convert the car to what you need. See the definition of function ‘icicle-custom-variable-p’ for an example.

User option `icicle-cand-preds-all’ defines the predefined candidate-filtering predicates, and these are grouped in user options named ‘icicle-cand-preds-for-TYPE’, where TYPE is the name of a completion type (‘bookmark’, ‘buffer’, ‘color’, ‘face’, ‘file’, ‘package’, ‘variable’, ‘window’,…). You can add a named predicate to one of these options.

(Note: Some commands provide minibuffer key bindings that also narrow the set of candidates. For example, during bookmark-name completion, there are keys to narrow to different types of bookmark. See On The Fly Minibuffer Bindings.)

For example, you can customize option `icicle-cand-preds-for-buffer’, to add a buffer-name predicate that you can then enter using completion. (You will also want to add it to option ‘icicle-cand-preds-all’.)

One of the completion-type options is `icicle-cand-preds-for-misc’. This is a catch-all category of predicates that apply generally, to pretty much all completion types. These predicates are included as candidates whenever you use `M-&’.

An important predicate in this catch-all group is ‘icicle-special-candidate-p’ (and its opposite, ‘icicle-not-special-candidate-p’). This filter keeps only candidates that are (or are not) “special candidates”. These are candidates that are highlighted in ‘*Completions*’ using face ‘icicle-special-candidate’ (actually, other faces can also be used, in which case the doc of the particular command explains this).

For example, command ‘icicle-apropos’ shows function names as special candidates, to help you distinguish them from variable names. And Icicles key completion distiguishes local key bindings by showing them as special candidates. And during file-name completion directory names are shown as special candidates.

Typing a lambda expression to define a predicate on the fly is handy and flexible, but it is of course much less convenient than choosing a predefined predicate by name. (Remember though, that you can retrieve previously entered predicates, using ‘M-p’ and so on.)

You can also use `C-M-&’ (bound to ‘icicle-save-predicate-to-variable’) at any time during completion to save the current predicate as a string-valued variable. By default, the variable is ‘icicle-input-string’. You can then retrieve the saved string later, using `C-=’ at the prompt for `M-&’. The current predicate is what is saved. You can build up a complex predicate, and then save it for later use.

The inconvenience of typing an EmacsLisp sexp must be balanced against the power of applying predicates on the fly. Whereas regexp matching is purely syntactic, with a predicate you can perform semantic tests. During search, for instance, you can look not only for a syntax match; you can look for matching search candidates that also belong to a particular class of objects (e.g. function, variable, type) or that satisfy some other semantic property. See also Icicles - Search Commands, Overview.

See Also:

Previous: Icicles - Expanded-Common-Match CompletionIciclesIciclesIndexNext: Icicles - Regressive Completion

DrewsElispLibraries referenced here: Lisp:icicles.el

CategoryCommands CategoryBufferSwitching CategoryCompletion CategoryRegexp CategoryDocumentation CategoryHelp CategoryDirectories CategoryFiles CategoryProgrammerUtils CategoryCode