From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "Drew Adams" Newsgroups: gmane.emacs.devel Subject: RE: Isearch: always try to find longest successful prefix [was: move to fail position in Isearch edit] Date: Tue, 11 Nov 2008 12:19:18 -0800 Message-ID: <004e01c9443a$c719f990$0200a8c0@us.oracle.com> References: <001101c943c8$adc09750$0200a8c0@us.oracle.com><001901c9440f$39133c90$0200a8c0@us.oracle.com> <87fxlyf9x7.fsf@jurta.org> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1226434852 5763 80.91.229.12 (11 Nov 2008 20:20:52 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 11 Nov 2008 20:20:52 +0000 (UTC) Cc: emacs-devel@gnu.org To: "'Juri Linkov'" Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Nov 11 21:21:52 2008 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1KzzkC-0005yt-1Y for ged-emacs-devel@m.gmane.org; Tue, 11 Nov 2008 21:21:48 +0100 Original-Received: from localhost ([127.0.0.1]:59993 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Kzzj3-00061C-Jx for ged-emacs-devel@m.gmane.org; Tue, 11 Nov 2008 15:20:37 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1Kzzhu-0005WB-Se for emacs-devel@gnu.org; Tue, 11 Nov 2008 15:19:27 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1Kzzht-0005V6-60 for emacs-devel@gnu.org; Tue, 11 Nov 2008 15:19:26 -0500 Original-Received: from [199.232.76.173] (port=52374 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Kzzhs-0005V0-Qp for emacs-devel@gnu.org; Tue, 11 Nov 2008 15:19:24 -0500 Original-Received: from acsinet11.oracle.com ([141.146.126.233]:26813) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1Kzzhr-0000Wr-Ta for emacs-devel@gnu.org; Tue, 11 Nov 2008 15:19:24 -0500 Original-Received: from acsinet13.oracle.com (acsinet13.oracle.com [141.146.126.235]) by acsinet11.oracle.com (Switch-3.3.1/Switch-3.3.1) with ESMTP id mABKJktO011838 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 11 Nov 2008 20:19:48 GMT Original-Received: from acsmt700.oracle.com (acsmt700.oracle.com [141.146.40.70]) by acsinet13.oracle.com (Switch-3.3.1/Switch-3.3.1) with ESMTP id mABKJR6o002310; Tue, 11 Nov 2008 20:19:28 GMT Original-Received: from dradamslap1 (/24.23.165.218) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Tue, 11 Nov 2008 20:19:15 +0000 X-Mailer: Microsoft Office Outlook 11 In-Reply-To: <87fxlyf9x7.fsf@jurta.org> Thread-Index: AclEJC625pwTp1XpSLqs8TK9mFJ3vwABlvlg X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3350 X-Source-IP: acsmt700.oracle.com [141.146.40.70] X-Auth-Type: Internal IP X-CT-RefId: str=0001.0A09020A.4919E8C5.0062:SCFSTAT928724,ss=1,fgs=0 X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 1) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:105576 Archived-At: > > 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.