Advanced search slowness

[Kornel Benko]

The slowness in normal search part happens, because we have very inefficient
algorithm.
Suppose we have a string "This is a string." at the cursor position, and we
search for "abcd".

The method MatchStringAdv::findAux() will be called now successively from 
findForwardAdv()
incrementing the cursor position.

In effect, we check whether following strings start with "abcd"

"This is a string."
"his is a string."
"is is a string."
"s is a string."
" is a string."
"is a string."
"s a string."
...

AT the first call, we already could know, the there is no "abcd" in the whole 
string, therefore
we need only to make findForwardAdv() notice it and increment the cursor 
position accordingly.

The patch I attach her is a hack, I know. But at least it shows, that somehow 
it should be possible.

With this patch the advanced search is about 50 times faster.
Could someone with more knowledge create a proper solution?

        Kornel
diff --git a/src/lyxfind.cpp b/src/lyxfind.cpp
index d6df0ef..6c34da7 100644
--- a/src/lyxfind.cpp
+++ b/src/lyxfind.cpp
@@ -893,6 +893,7 @@ MatchStringAdv::MatchStringAdv(lyx::Buffer & buf, FindAndReplaceOptions const &
 	}
 }
 
+static int ignore_positions = 0;
 
 int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) const
 {
@@ -900,6 +901,7 @@ int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) con
 	LYXERR(Debug::FIND, "Matching against     '" << lyx::to_utf8(docstr) << "'");
 	string str = normalize(docstr, true);
 	LYXERR(Debug::FIND, "After normalization: '" << str << "'");
+        ignore_positions = 0;
 	if (! use_regexp) {
 		LYXERR(Debug::FIND, "Searching in normal mode: par_as_string='" << par_as_string << "', str='" << str << "'");
 		LYXERR(Debug::FIND, "Searching in normal mode: lead_as_string='" << lead_as_string << "', par_as_string_nolead='" << par_as_string_nolead << "'");
@@ -907,6 +909,17 @@ int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) con
 			LYXERR(Debug::FIND, "size=" << par_as_string.size() << ", substr='" << str.substr(0, par_as_string.size()) << "'");
 			if (str.substr(0, par_as_string.size()) == par_as_string)
 				return par_as_string.size();
+                        else {
+                                size_t pos = str.find(par_as_string);
+                                if (pos == string::npos) {
+                                        // here we know, the search string cannot be in the rest
+                                        // of the same docstring, so we can advance
+                                        // But how make the calling method know?
+                                        ignore_positions = str.size();
+                                        if (ignore_positions > 100)
+                                                ignore_positions = 100;
+                                }
+                        }
 		} else {
 			size_t pos = str.find(par_as_string_nolead);
 			if (pos != string::npos)
@@ -1177,6 +1190,14 @@ int findForwardAdv(DocIterator & cur, MatchStringAdv & match)
 					if (len > 0)
 						return len;
 				}
+                                else {
+                                        // forward pos, we know here, we find nothing in
+                                        // the next ignore_positions
+                                        while (cur && (ignore_positions > 2)) {
+                                                cur.forwardPos();
+                                                ignore_positions--;
+                                        }
+                                }
 			}
 			if (!cur)
 				return 0;

signature.asc
Description: This is a digitally signed message part.