]> git.lyx.org Git - lyx.git/blobdiff - src/lyxfind.cpp
FindAdv: Try to use a better algorithm to find begin of a searched string
[lyx.git] / src / lyxfind.cpp
index 2a70c54b68cdb17b29dd118824c3213c4a2a7eb3..b7ab4d755b979bb9b9d7f792dee16ff19e590039 100644 (file)
@@ -739,17 +739,20 @@ string escape_for_regex(string s, bool match_latex)
                size_t new_pos = s.find("\\regexp{", pos);
                if (new_pos == string::npos)
                        new_pos = s.size();
-               LYXERR(Debug::FIND, "new_pos: " << new_pos);
-               string t = apply_escapes(s.substr(pos, new_pos - pos), get_lyx_unescapes());
-               LYXERR(Debug::FIND, "t [lyx]: " << t);
-               t = apply_escapes(t, get_regexp_escapes());
-               LYXERR(Debug::FIND, "t [rxp]: " << t);
-               s.replace(pos, new_pos - pos, t);
-               new_pos = pos + t.size();
-               LYXERR(Debug::FIND, "Regexp after escaping: " << s);
-               LYXERR(Debug::FIND, "new_pos: " << new_pos);
-               if (new_pos == s.size())
-                       break;
+               string t;
+               if (new_pos > pos) {
+                       LYXERR(Debug::FIND, "new_pos: " << new_pos);
+                       t = apply_escapes(s.substr(pos, new_pos - pos), get_lyx_unescapes());
+                       LYXERR(Debug::FIND, "t [lyx]: " << t);
+                       t = apply_escapes(t, get_regexp_escapes());
+                       LYXERR(Debug::FIND, "t [rxp]: " << t);
+                       s.replace(pos, new_pos - pos, t);
+                       new_pos = pos + t.size();
+                       LYXERR(Debug::FIND, "Regexp after escaping: " << s);
+                       LYXERR(Debug::FIND, "new_pos: " << new_pos);
+                       if (new_pos == s.size())
+                               break;
+               }
                // Might fail if \\endregexp{} is preceeded by unexpected stuff (weird escapes)
                size_t end_pos = s.find("\\endregexp{}}", new_pos + 8);
                LYXERR(Debug::FIND, "end_pos: " << end_pos);
@@ -832,6 +835,14 @@ bool braces_match(string::const_iterator const & beg,
 }
 
 
+class MatchResult {
+public:
+       int match_len;
+       int match2end;
+       int pos;
+       MatchResult(): match_len(0),match2end(0), pos(0) {};
+};
+
 /** The class performing a match between a position in the document and the FindAdvOptions.
  **/
 class MatchStringAdv {
@@ -848,7 +859,7 @@ public:
         ** @return
         ** The length of the matching text, or zero if no match was found.
         **/
-       int operator()(DocIterator const & cur, int len = -1, bool at_begin = true) const;
+       MatchResult operator()(DocIterator const & cur, int len = -1, bool at_begin = true) const;
 
 public:
        /// buffer
@@ -860,7 +871,7 @@ public:
 
 private:
        /// Auxiliary find method (does not account for opt.matchword)
-       int findAux(DocIterator const & cur, int len = -1, bool at_begin = true) const;
+       MatchResult findAux(DocIterator const & cur, int len = -1, bool at_begin = true) const;
 
        /** Normalize a stringified or latexified LyX paragraph.
         **
@@ -903,7 +914,7 @@ static docstring buffer_to_latex(Buffer & buffer)
        otexstream os(ods);
        runparams.nice = true;
        runparams.flavor = OutputParams::LATEX;
-       runparams.linelen = 100000; //lyxrc.plaintext_linelen;
+       runparams.linelen = 10000; //lyxrc.plaintext_linelen;
        // No side effect of file copying and image conversion
        runparams.dryrun = true;
        runparams.for_search = true;
@@ -925,7 +936,7 @@ static docstring stringifySearchBuffer(Buffer & buffer, FindAndReplaceOptions co
                OutputParams runparams(&buffer.params().encoding());
                runparams.nice = true;
                runparams.flavor = OutputParams::LATEX;
-               runparams.linelen = 100000; //lyxrc.plaintext_linelen;
+               runparams.linelen = 10000; //lyxrc.plaintext_linelen;
                runparams.dryrun = true;
                runparams.for_search = true;
                for (pos_type pit = pos_type(0); pit < (pos_type)buffer.paragraphs().size(); ++pit) {
@@ -1119,11 +1130,27 @@ class Intervall {
   int findclosing(int start, int end, char up, char down, int repeat);
   void handleParentheses(int lastpos, bool closingAllowed);
   bool hasTitle;
+  int isOpeningPar(int pos);
   string titleValue;
   void output(ostringstream &os, int lastpos);
   // string show(int lastpos);
 };
 
+int Intervall::isOpeningPar(int pos)
+{
+  if ((pos < 0) || (size_t(pos) >= par.size()))
+    return 0;
+  if (par[pos] != '{')
+    return 0;
+  if (size_t(pos) + 2 >= par.size())
+    return 1;
+  if (par[pos+2] != '}')
+    return 1;
+  if (par[pos+1] == '[' || par[pos+1] == ']')
+    return 3;
+  return 1;
+}
+
 void Intervall::setForDefaultLang(KeyInfo &defLang)
 {
   // Enable the use of first token again
@@ -1536,7 +1563,10 @@ void LatexInfo::buildEntries(bool isPatternString)
         found._dataStart = found._dataEnd;
         found._tokensize = found._dataEnd - found._tokenstart;
         found.parenthesiscount = 0;
+        found.head = interval.par.substr(found._tokenstart, found._tokensize);
       }
+      else
+        continue;
     }
     else {
       if (evaluatingMath) {
@@ -1575,6 +1605,7 @@ void LatexInfo::buildEntries(bool isPatternString)
         found._dataEnd = found._tokenstart + found._tokensize;
         found._dataStart = found._dataEnd;
         found.parenthesiscount = 0;
+        found.head = interval.par.substr(found._tokenstart, found._tokensize);
         evaluatingMath = true;
       }
       else {
@@ -1625,9 +1656,11 @@ void LatexInfo::buildEntries(bool isPatternString)
             found.head = interval.par.substr(found._tokenstart, found._tokensize);
           }
           else {
+            // Swallow possible optional params
             while (interval.par[pos1] == '[') {
               pos1 = interval.findclosing(pos1+1, interval.par.length(), '[', ']')+1;
             }
+            // Swallow also the eventual parameter
             if (interval.par[pos1] == '{') {
               found._dataEnd = interval.findclosing(pos1+1, interval.par.length()) + 1;
             }
@@ -1637,6 +1670,7 @@ void LatexInfo::buildEntries(bool isPatternString)
             found._dataStart = found._dataEnd;
             found._tokensize = count + found._dataEnd - pos;
             found.parenthesiscount = 0;
+            found.head = interval.par.substr(found._tokenstart, found._tokensize);
             found.disabled = true;
           }
         }
@@ -1646,6 +1680,7 @@ void LatexInfo::buildEntries(bool isPatternString)
           found._dataEnd = found._dataStart;
           found._tokensize = count + found._dataEnd - pos;
           found.parenthesiscount = 0;
+          found.head = interval.par.substr(found._tokenstart, found._tokensize);
           found.disabled = true;
         }
       }
@@ -1818,7 +1853,7 @@ void LatexInfo::buildKeys(bool isPatternString)
   // Skip
   // makeKey("enskip|smallskip|medskip|bigskip|vfill", KeyInfo(KeyInfo::isChar, 0, false), isPatternString);
   // Custom space/skip, remove the content (== length value)
-  makeKey("vspace|hspace|mspace", KeyInfo(KeyInfo::noContent, 1, false), isPatternString);
+  makeKey("vspace|vspace*|hspace|hspace*|mspace", KeyInfo(KeyInfo::noContent, 1, false), isPatternString);
   // Found in fr/UserGuide.lyx
   makeKey("og|fg", KeyInfo(KeyInfo::isChar, 0, false), isPatternString);
   // quotes
@@ -1850,7 +1885,7 @@ void LatexInfo::buildKeys(bool isPatternString)
   makeKey("trianglerightpar|hexagonpar|starpar",   KeyInfo(KeyInfo::isStandard, 1, true), isPatternString);
   makeKey("triangleuppar|triangledownpar|droppar", KeyInfo(KeyInfo::isStandard, 1, true), isPatternString);
   makeKey("triangleleftpar|shapepar|dropuppar",    KeyInfo(KeyInfo::isStandard, 1, true), isPatternString);
-  makeKey("hphantom|footnote|shortcut|includegraphics",     KeyInfo(KeyInfo::isStandard, 1, true), isPatternString);
+  makeKey("hphantom|vphantom|footnote|shortcut|include|includegraphics",     KeyInfo(KeyInfo::isStandard, 1, true), isPatternString);
   makeKey("parbox", KeyInfo(KeyInfo::doRemove, 1, true), isPatternString);
   // like ('tiny{}' or '\tiny ' ... )
   makeKey("footnotesize|tiny|scriptsize|small|large|Large|LARGE|huge|Huge", KeyInfo(KeyInfo::isSize, 0, false), isPatternString);
@@ -1985,14 +2020,15 @@ void Intervall::output(ostringstream &os, int lastpos)
 void LatexInfo::processRegion(int start, int region_end)
 {
   while (start < region_end) {          /* Let {[} and {]} survive */
-    if ((interval.par[start] == '{') &&
-        (interval.par[start+1] != ']') &&
-        (interval.par[start+1] != '[')) {
+    int cnt = interval.isOpeningPar(start);
+    if (cnt == 1) {
       // Closing is allowed past the region
       int closing = interval.findclosing(start+1, interval.par.length());
       interval.addIntervall(start, start+1);
       interval.addIntervall(closing, closing+1);
     }
+    else if (cnt == 3)
+      start += 2;
     start = interval.nextNotIgnored(start+1);
   }
 }
@@ -2310,7 +2346,7 @@ int LatexInfo::process(ostringstream &os, KeyInfo &actual )
   }
   // Remove possible empty data
   int dstart = interval.nextNotIgnored(actual._dataStart);
-  while ((dstart < output_end) && (interval.par[dstart] == '{')) {
+  while (interval.isOpeningPar(dstart) == 1) {
     interval.addIntervall(dstart, dstart+1);
     int dend = interval.findclosing(dstart+1, output_end);
     interval.addIntervall(dend, dend+1);
@@ -2542,10 +2578,22 @@ MatchStringAdv::MatchStringAdv(lyx::Buffer & buf, FindAndReplaceOptions const &
                        ++close_wildcards;
                }
                if (!opt.ignoreformat) {
-                       // Remove extra '\}' at end
-                       while ( regex_replace(par_as_string, par_as_string, "(.*)\\\\}$", "$1")) {
-                               open_braces++;
+                       // Remove extra '\}' at end if not part of \{\.\}
+                       size_t lng = par_as_string.size();
+                       while(lng > 2) {
+                               if (par_as_string.substr(lng-2, 2).compare("\\}") == 0) {
+                                       if (lng >= 6) {
+                                               if (par_as_string.substr(lng-6,3).compare("\\{\\") == 0)
+                                                       break;
+                                       }
+                                       lng -= 2;
+                                       open_braces++;
+                               }
+                               else
+                                       break;
                        }
+                       if (lng < par_as_string.size())
+                               par_as_string = par_as_string.substr(0,lng);
                        /*
                        // save '\.'
                        regex_replace(par_as_string, par_as_string, "\\\\\\.", "_xxbdotxx_");
@@ -2641,18 +2689,23 @@ static int computeSize(string s, int len)
        return count;
 }
 
-int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) const
+MatchResult MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) const
 {
+       MatchResult mres;
+
        if (at_begin &&
                (opt.restr == FindAndReplaceOptions::R_ONLY_MATHS && !cur.inMathed()) )
-               return 0;
+               return mres;
 
        docstring docstr = stringifyFromForSearch(opt, cur, len);
        string str = normalize(docstr, true);
        if (!opt.ignoreformat) {
                str = correctlanguagesetting(str, false, !opt.ignoreformat);
        }
-       if (str.empty()) return(-1);
+       if (str.empty()) {
+               mres.match_len = -1;
+               return mres;
+       }
        LYXERR(Debug::FIND, "Matching against     '" << lyx::to_utf8(docstr) << "'");
        LYXERR(Debug::FIND, "After normalization: '" << str << "'");
 
@@ -2669,21 +2722,21 @@ int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) con
                }
                sregex_iterator re_it(str.begin(), str.end(), *p_regexp, flags);
                if (re_it == sregex_iterator())
-                       return 0;
+                       return mres;
                match_results<string::const_iterator> const & m = *re_it;
 
                if (0) { // Kornel Benko: DO NOT CHECKK
                        // Check braces on the segment that matched the entire regexp expression,
                        // plus the last subexpression, if a (.*?) was inserted in the constructor.
                        if (!braces_match(m[0].first, m[0].second, open_braces))
-                               return 0;
+                               return mres;
                }
 
                // Check braces on segments that matched all (.*?) subexpressions,
                // except the last "padding" one inserted by lyx.
                for (size_t i = 1; i < m.size() - 1; ++i)
                        if (!braces_match(m[i].first, m[i].second, open_braces))
-                               return 0;
+                               return mres;
 
                // Exclude from the returned match length any length
                // due to close wildcards added at end of regexp
@@ -2716,7 +2769,10 @@ int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) con
                        result -= leadingsize;
                else
                        result = 0;
-               return computeSize(str.substr(pos+leadingsize,result), result);
+               mres.match_len = computeSize(str.substr(pos+leadingsize,result), result);
+               mres.match2end = str.size() - pos - leadingsize;
+               mres.pos = pos+leadingsize;
+               return mres;
        }
 
        // else !use_regexp: but all code paths above return
@@ -2729,28 +2785,39 @@ int MatchStringAdv::findAux(DocIterator const & cur, int len, bool at_begin) con
        if (at_begin) {
                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();
+               if (str.substr(0, par_as_string.size()) == par_as_string) {
+                       mres.match_len = par_as_string.size();
+                       mres.match2end = str.size();
+                       mres.pos = 0;
+                       return mres;
+               }
        } else {
                size_t pos = str.find(par_as_string_nolead);
-               if (pos != string::npos)
-                       return par_as_string.size();
+               if (pos != string::npos) {
+                       mres.match_len = par_as_string.size();
+                       mres.match2end = str.size() - pos;
+                       mres.pos = pos;
+                       return mres;
+               }
        }
-       return 0;
+       return mres;
 }
 
 
-int MatchStringAdv::operator()(DocIterator const & cur, int len, bool at_begin) const
+MatchResult MatchStringAdv::operator()(DocIterator const & cur, int len, bool at_begin) const
 {
-       int res = findAux(cur, len, at_begin);
+       MatchResult mres = findAux(cur, len, at_begin);
+       int res = mres.match_len;
        LYXERR(Debug::FIND,
               "res=" << res << ", at_begin=" << at_begin
               << ", matchword=" << opt.matchword
               << ", inTexted=" << cur.inTexted());
        if (res == 0 || !at_begin || !opt.matchword || !cur.inTexted())
-               return res;
-        if ((len > 0) && (res < len))
-          return 0;
+               return mres;
+        if ((len > 0) && (res < len)) {
+         mres.match_len = 0;
+          return mres;
+       }
        Paragraph const & par = cur.paragraph();
        bool ws_left = (cur.pos() > 0)
                ? par.isWordSeparator(cur.pos() - 1)
@@ -2766,12 +2833,15 @@ int MatchStringAdv::operator()(DocIterator const & cur, int len, bool at_begin)
        if (ws_left && ws_right) {
           // Check for word separators inside the found 'word'
           for (int i = 0; i < len; i++) {
-            if (par.isWordSeparator(cur.pos() + i))
-              return 0;
+            if (par.isWordSeparator(cur.pos() + i)) {
+             mres.match_len = 0;
+              return mres;
+           }
           }
-          return res;
+          return mres;
         }
-       return 0;
+       mres.match_len = 0;
+       return mres;
 }
 
 
@@ -2847,14 +2917,15 @@ docstring stringifyFromCursor(DocIterator const & cur, int len)
                OutputParams runparams(&cur.buffer()->params().encoding());
                runparams.nice = true;
                runparams.flavor = OutputParams::LATEX;
-               runparams.linelen = 100000; //lyxrc.plaintext_linelen;
+               runparams.linelen = 10000; //lyxrc.plaintext_linelen;
                // No side effect of file copying and image conversion
                runparams.dryrun = true;
                LYXERR(Debug::FIND, "Stringifying with cur: "
                       << cur << ", from pos: " << cur.pos() << ", end: " << end);
-               return par.asString(cur.pos(), end,
+               docstring result = par.asString(cur.pos(), end,
                        AS_STR_INSETS | AS_STR_SKIPDELETE | AS_STR_PLAINTEXT,
                        &runparams);
+               return result;
        } else if (cur.inMathed()) {
                CursorSlice cs = cur.top();
                MathData md = cs.cell();
@@ -2963,9 +3034,9 @@ int findAdvFinalize(DocIterator & cur, MatchStringAdv const & match)
                d = cur.depth();
                old_cur = cur;
                cur.forwardPos();
-       } while (cur && cur.depth() > d && match(cur) > 0);
+       } while (cur && cur.depth() > d && match(cur).match_len > 0);
        cur = old_cur;
-       int max_match = match(cur);     /* match valid only if not searching whole words */
+       int max_match = match(cur).match_len;     /* match valid only if not searching whole words */
        if (max_match <= 0) return 0;
        LYXERR(Debug::FIND, "Ok");
 
@@ -2975,17 +3046,17 @@ int findAdvFinalize(DocIterator & cur, MatchStringAdv const & match)
          return 0;
        if (match.opt.matchword) {
           LYXERR(Debug::FIND, "verifying unmatch with len = " << len);
-          while (cur.pos() + len <= cur.lastpos() && match(cur, len) <= 0) {
+          while (cur.pos() + len <= cur.lastpos() && match(cur, len).match_len <= 0) {
             ++len;
             LYXERR(Debug::FIND, "verifying unmatch with len = " << len);
           }
           // Length of matched text (different from len param)
-          int old_match = match(cur, len);
+          int old_match = match(cur, len).match_len;
           if (old_match < 0)
             old_match = 0;
           int new_match;
           // Greedy behaviour while matching regexps
-          while ((new_match = match(cur, len + 1)) > old_match) {
+          while ((new_match = match(cur, len + 1).match_len) > old_match) {
             ++len;
             old_match = new_match;
             LYXERR(Debug::FIND, "verifying   match with len = " << len);
@@ -2998,7 +3069,7 @@ int findAdvFinalize(DocIterator & cur, MatchStringAdv const & match)
          int maxl = cur.lastpos() - cur.pos();
          // Greedy behaviour while matching regexps
          while (maxl > minl) {
-           int actual_match = match(cur, len);
+           int actual_match = match(cur, len).match_len;
            if (actual_match >= max_match) {
              // actual_match > max_match _can_ happen,
              // if the search area splits
@@ -3029,7 +3100,7 @@ int findAdvFinalize(DocIterator & cur, MatchStringAdv const & match)
             }
             if (cur.pos() != old_cur.pos()) {
               // OK, forwarded 1 pos in actual inset
-              actual_match = match(cur, len-1);
+              actual_match = match(cur, len-1).match_len;
               if (actual_match == max_match) {
                 // Ha, got it! The shorter selection has the same match length
                 len--;
@@ -3043,7 +3114,7 @@ int findAdvFinalize(DocIterator & cur, MatchStringAdv const & match)
             }
             else {
               LYXERR0("cur.pos() == old_cur.pos(), this should never happen");
-              actual_match = match(cur, len);
+              actual_match = match(cur, len).match_len;
               if (actual_match == max_match)
                 old_cur = cur;
             }
@@ -3060,16 +3131,60 @@ int findForwardAdv(DocIterator & cur, MatchStringAdv & match)
                return 0;
        while (!theApp()->longOperationCancelled() && cur) {
                LYXERR(Debug::FIND, "findForwardAdv() cur: " << cur);
-               int match_len = match(cur, -1, false);
+               MatchResult mres = match(cur, -1, false);
+               int match_len = mres.match_len;
                LYXERR(Debug::FIND, "match_len: " << match_len);
+               if ((mres.pos > 10000) || (mres.match2end > 10000) || (match_len > 10000)) {
+                       LYXERR0("BIG LENGTHS: " << mres.pos << ", " << match_len << ", " << mres.match2end);
+                       match_len = 0;
+               }
                if (match_len > 0) {
+                       // Try to find the begin of searched string
+                       int increment = mres.pos/2;
+                       while (mres.pos > 5 && (increment > 5)) {
+                               DocIterator old_cur = cur;
+                               for (int i = 0; i < increment && cur; cur.forwardPos(), i++) {
+                                       /*
+                                       while (cur && cur.depth() != old_cur.depth())
+                                               cur.forwardPos();
+                                               */
+                               }
+                               if (! cur) {
+                                       cur = old_cur;
+                                       increment /= 2;
+                               }
+                               else {
+                                       MatchResult mres2 = match(cur, -1, false);
+                                       if ((mres2.match2end < mres.match2end) ||
+                                         (mres2.match_len < mres.match_len)) {
+                                               cur = old_cur;
+                                               increment /= 2;
+                                       }
+                                       else {
+                                               mres = mres2;
+                                               increment -= 2;
+                                               if (increment > mres.pos/2)
+                                                       increment = mres.pos/2;
+                                       }
+                               }
+                       }
                        int match_len_zero_count = 0;
-                       for (; !theApp()->longOperationCancelled() && cur; cur.forwardPos()) {
+                       for (int i = 0; !theApp()->longOperationCancelled() && cur; cur.forwardPos()) {
+                               if (i++ > 10) {
+                                       int remaining_len = match(cur, -1, false).match_len;
+                                       if (remaining_len <= 0) {
+                                               // Apparently the searched string is not in the remaining part
+                                               break;
+                                       }
+                                       else {
+                                               i = 0;
+                                       }
+                               }
                                LYXERR(Debug::FIND, "Advancing cur: " << cur);
-                               int match_len3 = match(cur, 1);
+                               int match_len3 = match(cur, 1).match_len;
                                if (match_len3 < 0)
                                        continue;
-                               int match_len2 = match(cur);
+                               int match_len2 = match(cur).match_len;
                                LYXERR(Debug::FIND, "match_len2: " << match_len2);
                                if (match_len2 > 0) {
                                        // Sometimes in finalize we understand it wasn't a match
@@ -3121,7 +3236,7 @@ int findMostBackwards(DocIterator & cur, MatchStringAdv const & match)
                LYXERR(Debug::FIND, "findMostBackwards(): cur=" << cur);
                DocIterator new_cur = cur;
                new_cur.backwardPos();
-               if (new_cur == cur || &new_cur.inset() != &inset || !match(new_cur))
+               if (new_cur == cur || &new_cur.inset() != &inset || !match(new_cur).match_len)
                        break;
                int new_len = findAdvFinalize(new_cur, match);
                if (new_len == len)
@@ -3147,7 +3262,7 @@ int findBackwardsAdv(DocIterator & cur, MatchStringAdv & match)
        bool pit_changed = false;
        do {
                cur.pos() = 0;
-               bool found_match = match(cur, -1, false);
+               bool found_match = (match(cur, -1, false).match_len > 0);
 
                if (found_match) {
                        if (pit_changed)
@@ -3157,7 +3272,7 @@ int findBackwardsAdv(DocIterator & cur, MatchStringAdv & match)
                        LYXERR(Debug::FIND, "findBackAdv2: cur: " << cur);
                        DocIterator cur_prev_iter;
                        do {
-                               found_match = match(cur);
+                               found_match = (match(cur).match_len > 0);
                                LYXERR(Debug::FIND, "findBackAdv3: found_match="
                                       << found_match << ", cur: " << cur);
                                if (found_match)
@@ -3287,7 +3402,7 @@ static void findAdvReplace(BufferView * bv, FindAndReplaceOptions const & opt, M
                return;
        LASSERT(sel_len > 0, return);
 
-       if (!matchAdv(sel_beg, sel_len))
+       if (!matchAdv(sel_beg, sel_len).match_len)
                return;
 
        // Build a copy of the replace buffer, adapted to the KeepCase option