KFind patch for incremental searching

David Faure faure at kde.org
Mon Jun 7 01:20:16 BST 2004

On Monday 07 June 2004 01:55, Arend van Beelen jr. wrote:
> Hi guys,
> I've completed my patch for incremental search in KFind. It does involve quite 
> some extra logic to KFind though, so I'd like to post it for review before I 
> commit.
> The incremental search will be used by the type-ahead find feature so it will 
> be more efficient and can better respond to the path through which the user 
> searches. To accomplish this, all data block set by KFind::setData() are 
> cached and the search algorithm will track in which block and at which 
> position every match (of the current search pattern and its substrings) is. 
> If the incremental search then decrements it will select the same matches as 
> it encountered during its first run. This means if the user would press F3 a 
> few times between incrementing the search pattern, this path is followed in 
> reverse when decrementing the pattern.

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

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

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

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

> Finally, the patch also fixes a small memleak in KFind::setOptions().
Ah indeed. That one should be backported.


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

More information about the kde-core-devel mailing list