KFind patch for incremental searching

[David Faure]

On Monday 07 June 2004 03:09, Arend van Beelen jr. wrote:
> 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. 

This sounds like a good idea to me.
IDs would fit very well with kotext's paragId()s, what's more :)

> > 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. 
Oh, I didn't think about that.
> 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.
I see.
I hope the applications will free the KFind object (or at least clear its cache) when
stopping the incr. search though; it sounds quite expensive to have a full copy of
the document's text in memory (think of a 150-pages kword document).
BTW the class docu should probably be extended to explain how to use incr. search
with KFind: should one call setData() for the whole document right away?

> > 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.
Agreed.

> > > +    // 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.

So does the new option have to be in setOptions()? Why not a separate
bool setting in KFind? After all the KFindDialog options are those coming from
the dialog :)

-- 
David Faure, faure at kde.org, sponsored by Trolltech to work on KDE,
Konqueror (http://www.konqueror.org), and KOffice (http://www.koffice.org).