Merge lp:~gz/bzr-grep/no_match_fast_path into lp:bzr-grep

[Martin Packman]

Optimisation, avoids splitting the text into a list of lines and testing each one for a match. There are actually a couple of cases where we have avoid this anyway, as explained in the comments, and currently always fall back to splitting into lines after a match is found.

Timings of most interest here will be a big tree with only a few files hit by the pattern.

[Parth Malwankar (parthm)]

This is a really neat optimization. Thanks.
The hot cache numbers for emacs tree working tree search go from 2.39-2.42s to 0.93-0.96s for a pattern thats not found. One we merge in the prerequisite branch we can merge this in. Please add a NEWS entry.

review: Approve

[lp:~gz/bzr-grep/no_match_fast_path]

158. By Martin Packman on 2010-06-07

Fix previously untested bug with regexp and line numbers introduced by optimisation

159. By Martin Packman on 2010-06-07

Scale back no-match fast path to avoid some behaviour changes with line endings

[Martin Packman (gz)]

Even with the current checks, this branch changes some corner-cases with line-endings. The existing behaviour isn't all that great, but should really decide on what we want the plugin to do and make it consistent.

I've removed a little of the code for the moment, so the first match will happen twice, but the basic speedup should be the same, and the landing risk should be lower.

[lp:~gz/bzr-grep/no_match_fast_path]

160. By Martin Packman on 2010-06-07

Add NEWS entry for no match fast path change

=== modified file 'NEWS'
--- NEWS	2010-05-23 07:59:31 +0000
+++ NEWS	2010-06-07 19:36:31 +0000
@@ -1,3 +1,9 @@
+bzr-grep 0.4.0-dev
+==================================
+* Added fast path for no match that avoids splitting the file text into
+  seperate lines and testing each one, by checking the entire text for a
+  possible match initially. (Martin [gz])
+
 bzr-grep 0.3.0-final - 23-May-2010
 ==================================
 * Support for --color option (POSIX only). (Parth Malwankar, #571694)

=== modified file '__init__.py'
--- __init__.py	2010-06-07 19:36:31 +0000
+++ __init__.py	2010-06-07 19:36:31 +0000
@@ -198,9 +198,9 @@
             pattern = re.escape(pattern)
 
         patternc = None
-        re_flags = 0
+        re_flags = re.MULTILINE
         if ignore_case:
-            re_flags = re.IGNORECASE
+            re_flags |= re.IGNORECASE
 
         if not fixed_string:
             patternc = grep.compile_pattern(pattern, re_flags)

=== modified file 'grep.py'
--- grep.py	2010-06-07 19:36:31 +0000
+++ grep.py	2010-06-07 19:36:31 +0000
@@ -14,6 +14,9 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
+import os
+import sys
+
 from bzrlib.lazy_import import lazy_import
 lazy_import(globals(), """
 from fnmatch import fnmatch
@@ -469,38 +472,75 @@
     writeline = opts.outputter.get_writer(path, revno, cache_id)
 
     if opts.files_with_matches or opts.files_without_match:
-        # While printing files with matches we only have two case
-        # print file name or print file name with revno.
-        found = False
         if opts.fixed_string:
-            for line in file_text.splitlines():
-                if pattern in line:
-                    found = True
-                    break
+            if sys.platform > (2, 5):
+                found = pattern in file_text
+            else:
+                for line in file_text.splitlines():
+                    if pattern in line:
+                        found = True
+                        break
+                else:
+                    found = False
         else:
             search = opts.patternc.search
-            for line in file_text.splitlines():
-                if search(line):
-                    found = True
-                    break
+            if "$" not in pattern:
+                found = search(file_text) is not None
+            else:
+                for line in file_text.splitlines():
+                    if search(line):
+                        found = True
+                        break
+                else:
+                    found = False
         if (opts.files_with_matches and found) or \
                 (opts.files_without_match and not found):
             writeline()
     elif opts.fixed_string:
+        # Fast path for no match, search through the entire file at once rather
+        # than a line at a time. However, we don't want this without Python 2.5
+        # as the quick string search algorithm wasn't implemented till then:
+        # <http://effbot.org/zone/stringlib.htm>
+        if sys.version_info > (2, 5):
+            i = file_text.find(pattern)
+            if i == -1:
+                return
+            b = file_text.rfind("\n", 0, i) + 1
+            if opts.line_number:
+                start = file_text.count("\n", 0, b) + 1
+            file_text = file_text[b:]
+        else:
+            start = 1
         if opts.line_number:
             for index, line in enumerate(file_text.splitlines()):
                 if pattern in line:
-                    writeline(lineno=index+1, line=line)
+                    writeline(lineno=index+start, line=line)
         else:
             for line in file_text.splitlines():
                 if pattern in line:
                     writeline(line=line)
     else:
+        # Fast path on no match, the re module avoids bad behaviour in most
+        # standard cases, but perhaps could try and detect backtracking
+        # patterns here and avoid whole text search in those cases
         search = opts.patternc.search
+        if "$" not in pattern:
+            # GZ 2010-06-05: Grr, re.MULTILINE can't save us when searching
+            #                through revisions as bazaar returns binary mode
+            #                and trailing \r breaks $ as line ending match
+            m = search(file_text)
+            if m is None:
+                return
+            b = file_text.rfind("\n", 0, m.start()) + 1
+            if opts.line_number:
+                start = file_text.count("\n", 0, b) + 1
+            file_text = file_text[b:]
+        else:
+            start = 1
         if opts.line_number:
             for index, line in enumerate(file_text.splitlines()):
                 if search(line):
-                    writeline(lineno=index+1, line=line)
+                    writeline(lineno=index+start, line=line)
         else:
             for line in file_text.splitlines():
                 if search(line):

=== modified file 'test_grep.py'
--- test_grep.py	2010-06-07 19:36:31 +0000
+++ test_grep.py	2010-06-07 19:36:31 +0000
@@ -1082,6 +1082,9 @@
             '-n', 'line1', 'file0.txt'])
         self.assertContainsRe(out, "file0.txt~.:1:line1", flags=TestGrep._reflags)
 
+        out, err = self.run_bzr(['grep', '-n', 'line[0-9]', 'file0.txt'])
+        self.assertContainsRe(out, "file0.txt:3:line3", flags=TestGrep._reflags)
+
     def test_wtree_with_line_number(self):
         """(wtree) Search for pattern with --line-number.
         """
@@ -1099,6 +1102,9 @@
         out, err = self.run_bzr(['grep', '-n', '[hjkl]ine1', 'file0.txt'])
         self.assertContainsRe(out, "file0.txt:1:line1", flags=TestGrep._reflags)
 
+        out, err = self.run_bzr(['grep', '-n', 'line[0-9]', 'file0.txt'])
+        self.assertContainsRe(out, "file0.txt:3:line3", flags=TestGrep._reflags)
+
     def test_revno_basic_history_grep_file(self):
         """Search for pattern in specific revision number in a file.
         """