RE: Isearch: always try to find longest successful prefix [was: move to fail position in Isearch edit]

[Drew Adams]

> > You'll notice that this would be a lot handier if Isearch 
> > always started out (and resumed after Isearch edit) by
> > treating the search string incrementally.
> >
> > For example, suppose you search again with a previous 
> > search string `aaxbbb' by hitting `C-s C-s' in a buffer
> > where there is no match for `aaxbbb' but there are
> > matches for `aa'.
> >
> > Isearch fails immediately, showing the entire search 
> > string, `aaxbbb', as a failed match by highlighting it.
> > If, however, you had typed `aaxbbb' to a fresh
> > `C-s', then the `aa' match would be located, and the 
> > failure highlighting would correctly reflect the `aa'
> > prefix match success and the `xbbb' suffix match
> > failure.
> 
> We could try implementing the idea suggested by Stefan in
> http://thread.gmane.org/gmane.emacs.devel/74539/focus=74634
> to iteratively remove the last char until a search succeeds.

Yes. I forgot about that thread (which I in fact started!). FWIW, I've changed
my opinion about part of what I said in that thread. The change of opinion is
based on experience using a similar feature in Icicles minibuffer completion
(see below).

Stefan suggested in the thread you cite: "[S]tart from the user's input (which
doesn't match) and iteratively remove the last char until a search succeeds.  It
may not always give you the very best imaginable information, but least it gives
you the same info as Drew's proposed code in the case where the user just typed
the text one char at a time."

That's the same thing I'm saying now.

Or almost the same thing, depending on what he meant by "remove ... until a
search succeeds". Would that removal be just a way to _find_ the longest prefix
match, or would those non-matching chars also be removed from the user's input
string?

My suggestion is to (1) go ahead and find the longest prefix match (e.g. using
the method Stefan suggested: peel off chars at the end until you get a match),
and (2) move to that match location, but (3) do _not_ remove the failed part of
the input string.

Instead, just highlight the failed suffix and let the user optionally use a key
to edit the string with the cursor at the failure start position. IOW, treat
this case the same as the case where the user typed the search string
incrementally.

If the user doesn't want to edit at the failure position, s?he need only hit
`C-g' to remove the failed suffix altogether (as usual), instead of hitting the
edit-at-fail-position key.

IOW, give the user a choice; don't just remove the failed suffix automatically.
If the user wants to remove it, `C-g' will do that (nothing new here). If the
user wants to edit the string at the failure position, some new key would do
that (I proposed `M-e').

FWIW, this is exactly the approach I have used for some time now in Icicles, for
input completion failure highlighting. The failed suffix of your minibuffer
input is highlighted (by default). If you hit `C-M-l' then the cursor is moved
to the start of that failed suffix. If you hit `C-M-l' a second time then the
failed suffix is removed.

This two-step approach is great for editing the middle of your input, at a place
(where it failed) that you often want to tweak. And it's quick to hit the key
twice if you want to just delete the mismatch. (Originally, `C-M-l' just removed
the mismatch; the two-step behavior is better.)

In Isearch, however, if you are not editing the search string, then the "edit"
position (there is no cursor there) is always at the end of the input string. So
to edit a character in the middle of the input string, you must enter Isearch
edit mode (`M-e'). 

I see no way programmatically to enter edit mode and also move the cursor to the
failure position. That's why I proposed what I did: a first `M-e' to start
editing, and a second `M-e' to move to the failure position. That works fine.

What's missing is the piece I mentioned in the text quoted above that started
this thread: Isearch should _always_ act incrementally. That is apparently the
same thing Stefan was talking about, unless he meant to also remove the
non-matching suffix from the user's input. 

In my suggestion, Isearch would act no differently whether you type each
character or start a search with a complete string (e.g. `C-s C-s'). In both
cases, search would proceed as if you had typed each bit incrementally.

I don't know if that would be difficult to implement. It would be great if it
were somehow as simple as just telling the Isearch code to treat the input
string as if it were typed a bit at a time - analogously to just adding
`call-interactively' to a function call to pick up the interactive behavior. ;-)

Wrt Stefan's remark about the performance hit to find the failure position: It
should be about the same as what's needed for normal incremental search when you
type a char at a time - the same mechanism would be used. But of course extra
matches would be attempted - at most one for each failure character.

FWIW, in Icicles, the analogous highlighting can have a _much_ bigger
performance hit, because completion can be costly and it calls for multiple
completion attempts (with diminishing suffixes). It is especially costly for
some kinds of completion, such as possibly remote file-name completion. Because
of this, users can customize the use of such highlighting (during strict or lax
completion; on demand or automatically each time you update the input;
pending-input delay; max number of candidates; etc.).

FWIW, to optimize finding the longest matching prefix in Icicles, I do this:

1. Complete the input string through each of the last two chars, starting with
the last (whole string). That is, just as Stefan suggested, peel away one char
at a time. But do this only for the last two chars.

2. Then change to binary search (testing) for the other chars: split the input
and test, split half of that and test, etc.

The binary-search testing (#2) is (as always) very quick - much better than
checking each possible prefix with diminishing lengths, especially for long
input strings.

The reason for trying #1 first is that you often type at the end of the input
rather than in the middle, so it is common for a mismatch to start near the end.
And, especially with the feedback from mismatch highlighting, you tend to
correct a mismatch soon after you type it.

(Editing a directory component of existing file-name input would be a case where
you might introduce a mismatch that begins in the middle or near the beginning,
not near the end, of the input.)

For Isearch, I expect that simple right-to-left checking of diminishing prefixes
will be fine. Input is nearly always at the right end.

Except when it's not. ;-) For the case of `C-s C-s' or after yanking chunks, we
could try optimizing (e.g. binary testing). For yanking, the testing sequence
could take into account the position of the yank. But a simple right-to-left
approach should be tried first. My guess is that it will be sufficiently fast.