KFind patch for incremental searching

[Arend van Beelen jr.]

On Monday 07 June 2004 02:20, David Faure wrote:
[...]
> Good work - but I have some reservations about the "caching" approach.
> Apart from the (probably inevitable) memory consumption, doesn't this
> create problems in case of editable text? I'm thinking mostly of KOffice,
> but even khtml's text areas fall into this case. If the user edits the
> current paragraph during a search, KOffice will re-set the current data
> with setData(). Or a much more general case which also applies to khtml: if
> you edit a paragraph that KFind already saw, then the "texts" cache will
> still contain the old data and if you press Backspace it will go back to
> the wrong place.
> I think the whole caching approach is very limited to readonly data like
> khtml (textareas excluded), whereas KFind's design (with the incremental
> setData) allows editable text.
>
> So the question is how to handle editable text and incremental search
> together. One could say: we don't. E.g. even emacs' incremental search
> doesn't allow modifying the text while searching. But I think we can manage
> to do it, if we give a little bit more control to the application, which
> would call setData() as much as needed when iterating over the data (e.g.
> paragraphs), just like we do already with e.g. find next.
One option I was thinking about, and which might also provide a solution to 
this problem, would be to add an optional ID to the data. This ID could then 
be used in the highlight() signal to check in which data block the match 
occurred, which would also be more efficient than comparing text blocks as is 
necessary right now. But then you could also do a setData(ID, text) to set 
new data. If an ID is given which is already used, that block would be 
overwritten in the cache and the block would possibly be marked dirty. If the 
incremental path then leads back to a dirty block, that block is re-searched. 

> I haven't put 
> much thought into incremental search, but isn't it very _very_ similar to
> "find next", except that the pattern can change (one letter added or
> removed) and the option "Backwards" can change (which IIRC is already
> handled)? It seems to me that the whole thing could be done much simpler if
> the app would simply use its findnext code for the incremental search. Not
> sure KFind would even need a change in that case...
Well, I started with an approach very much like Find Next (but without 
incrementing the current position between searches) as well, but quickly ran 
into various trouble. First of all, you need to temporarily flip the 
FindBackwards bit when your pattern decrements instead of increments. This 
isn't hard to do, but has the problem of always finding the last match before 
the current match, instead of the first (or previously visited) match. By 
tracking the path I can avoid this problem and I don't even have to search 
when decrementing, I can just look up the match from the path. Furthermore, 
if you just use the Find Next approach and you start going backwards because 
the pattern decremented and you can't find the new pattern in the same data 
block, you need to ask for a new one. Then when the pattern increments again 
you once again need a new block. This can easily lead to lots of unnecessary 
switching of blocks which can be solved by caching.

> Hmm, I see that the main point might be performance (we'd lose the QDict).
> Maybe KFind can provide some help there but still leave full control to
> the application (for iterating over the paragraphs, and possibly
> invalidating some data). Hmm. Or maybe all we need compared to the current
> patch is a way to invalidate a given entry in the 'texts' vector (and
> handle its associated matches somehow) - or even clear the whole texts
> vector if too much changed (e.g. one or more paragraphs were
> added/removed).
Yeah, and that could probably be achieved by using ID's as mentioned above.

> > +         !(m_options & KFindDialog::FindIncremental &&
> > d->patternChanged) )
>
> I strongly suggest () around (a&b), it's too easy to get that one wrong.
No problem.

> > +    // KDE4: move to KFind
> >     enum Options
>
> That's arguable. The idea is that KFindDialog can be used without KFind...
> OTOH I guess that if such apps have to include kfind.h just for the enum
> it's not a big deal either, and for apps that do use KFind+KFindDialog it
> would indeed look more consistent.
It's indeed arguable :) But now we have an option in KFindDialog which has 
nothing to do with the dialog. And the only dependancy KFind has on 
KFindDialog are the options, so the idea of being able to use KFindDialog 
without KFind would be changed to being able to use KFind without 
KFindDialog, which sounds more logical to me.

[...]

-- 
Arend van Beelen jr.
http://www.liacs.nl/~dvbeelen

So if you want my address, it's number one at the end of the bar.
-- Marillion