From kde-core-devel Mon Jun 07 01:09:08 2004 From: "Arend van Beelen jr." Date: Mon, 07 Jun 2004 01:09:08 +0000 To: kde-core-devel Subject: Re: KFind patch for incremental searching Message-Id: <200406070309.08874.arend () auton ! nl> X-MARC-Message: https://marc.info/?l=kde-core-devel&m=108657060505642 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