Merge lp:~whitley/bzr/ignore-exception into lp:bzr

[John Whitley]

[John Whitley (whitley)]

This is an implementation of ignore exceptions, using a syntax borrowed from git that prefixes ignores with an exclamation point '!'. Per discussion on the list, I've also extended this with a syntax ('!!' patterns) to allow ignores be specified under excepted paths. NEWS, help, and internal comments in this branch should have been updated w.r.t. this addition.

bug: https://bugs.launchpad.net/bzr/+bug/428031

[Martin Pool (mbp)]

That is a nice feature and the patch looks reasonable. I saw there was a thread about benchmarking it to check there was no performance regression - is that verified now?

In the shell examples, you might need to take into account that in some shells doublequotes don't escape !. You might be safer with \!.

Can you please execute the contributor agreement <http://www.canonical.com/contributors>?

[John A Meinel (jameinel)]

The code looks good. I think the only thing we are waiting on is
1) Running some perf tests of 'bzr status' on a fairly large tree and/or initial import.

  a) Create a 50k tree
      run bzr init
      time bzr add
  b) For all files, touch f + '.o'
     time bzr st

2) Contributor agreement.

...
115 -
116 - if not pattern.startswith('RE:'):
117 + if not (pattern.startswith('RE:') or pattern.startswith('!RE:')):

^- What about pattern.startswith('!!RE:') ?

...
204 + patterns = [ u'*', u'!./local', u'!./local/**/*', u'!RE:\.z.*',u'!!./.zcompdump' ]
^- our style guide would have this written as:
204 + patterns = [u'*', u'!./local', u'!./local/**/*', u'!RE:\.z.*', u'!!./.zcompdump']
                      ^ ^ ^
Though you probably also need to watch out for >80 chars (just wrap to the next line as needed). You may also want to add a !!RE: pattern to catch the above issue.

same here:
215 + patterns = [ u'static/**/*.html', u'!static/**/versionable.html']

review: Approve

[John Whitley (whitley)]

John A Meinel <email address hidden> wrote ..
> Review [...]

Thanks for the review and comments. I'll have the contributor agreement, perf results, and John's suggested changes (plus a few more tests related to same) in ASAP. I've been a bit time-crunched recently but should be able to button this up soon.

[John Whitley (whitley)]

Performance notes:

without exceptions in .bzrignore, on the ignore exception working tree:
>> bzrtime "call([sys.executable, '../bzr.dev/bzr', 'st'], stdout=PIPE)"
10 loops, best of 3: 286 msec per loop
>> bzrtime "call([sys.executable, '../ignore-exception/bzr', 'st'], stdout=PIPE)"
10 loops, best of 3: 289 msec per loop

with '!' and '!!' patterns on the same working tree:
>> bzrtime "call([sys.executable, '../bzr.dev/bzr', 'st'], stdout=PIPE)"
10 loops, best of 3: 291 msec per loop
>> bzrtime "call([sys.executable, '../ignore-exception/bzr', 'st'], stdout=PIPE)"
10 loops, best of 3: 297 msec per loop

For the above tests, this was added to the tree's .bzrignore:
!./build/temp.macosx-10.6-i386-2.6
!wombat~
!foobar$$
!RE:nada.*nada
!!./build/temp.macosx-10.6-i386-2.6/bzrlib/diff-delta.o
!!./doc/en/admin-guide/index-plain.html
!!nadabadanada

On my (large, deep) home directory, with ignore exclusion patterns:
>> python -m timeit -s "from subprocess import call, PIPE" "call([sys.executable, 'src/bzr/bzr.dev/bzr', 'st'], stdout=PIPE)"
10 loops, best of 3: 278 msec per loop
>> python -m timeit -s "from subprocess import call, PIPE" "call([sys.executable, 'src/bzr/ignore-exception/bzr', 'st'], stdout=PIPE)"
10 loops, best of 3: 283 msec per loop

54k file tree test (many copies of exported emacs HEAD tree):
>> time ~/src/ignore-exception/bzr add
bzr add 9.13s user 1.16s system 67% cpu 15.266 total

(One cache warming run elided from each set below)
>> time ~/src/bzr/bzr.dev/bzr --no-plugins status
~/src/bzr/bzr.dev/bzr --no-plugins st 4.78s user 2.99s system 80% cpu 9.609 total
~/src/bzr/bzr.dev/bzr --no-plugins st 4.80s user 3.01s system 79% cpu 9.893 total
~/src/bzr/bzr.dev/bzr --no-plugins st 4.78s user 3.00s system 79% cpu 9.785 total

>> time ~/src/bzr/ignore-exception/bzr --no-plugins status
~/src/bzr/ignore-exception/bzr --no-plugins st 4.88s user 3.02s system 75% cpu 10.479 total
~/src/bzr/ignore-exception/bzr --no-plugins st 4.88s user 3.02s system 73% cpu 10.765 total
~/src/bzr/ignore-exception/bzr --no-plugins st 4.88s user 3.05s system 73% cpu 10.830 total

With ignore exceptions above added to .bzrignore:
>> time ~/src/bzr/bzr.dev/bzr --no-plugins status
~/src/bzr/bzr.dev/bzr --no-plugins st 4.81s user 3.03s system 78% cpu 9.939 total
~/src/bzr/bzr.dev/bzr --no-plugins st 4.81s user 3.03s system 79% cpu 9.898 total
~/src/bzr/bzr.dev/bzr --no-plugins st 4.81s user 3.01s system 80% cpu 9.672 total

>> time ~/src/bzr/ignore-exception/bzr --no-plugins status
~/src/bzr/ignore-exception/bzr --no-plugins st 5.22s user 3.05s system 76% cpu 10.767 total
~/src/bzr/ignore-exception/bzr --no-plugins st 5.21s user 3.01s system 77% cpu 10.642 total
~/src/bzr/ignore-exception/bzr --no-plugins st 5.22s user 3.03s system 75% cpu 10.971 total

The big-tree timings are potentially concerning. It appears that the implementation change incurs a roughly 9.5% hit to bzr status. Adding exception patterns doesn't really change the picture.

If that's too great then my the next step would be a reimplementation of ExcludingGlobster to use the same regex strategy as Globster, but order the pattern types by priority ('!!', '!', then normal pat...

[John Whitley (whitley)]

The fix, added tests, and PEP 8 cleanup per John's review have been pushed to this branch.

[John A Meinel (jameinel)]

So a 10% hit is a bit of a shame, but not terrible. I also notice that there isn't a huge impact when you actually add the exceptions. Which tells me that it is just the extra calls to Globster.match() (with nothing to match) that are causing the problem.

Looking at the code, Globster.match() should be iterating over self._regex_patterns and not finding anything so then returning pretty quickly.

Do you care to try an evil hack?
=== modified file 'bzrlib/globbing.py'
--- bzrlib/globbing.py 2010-01-11 16:44:02 +0000
+++ bzrlib/globbing.py 2010-01-14 15:12:34 +0000
@@ -215,6 +215,7 @@
                 return patterns[match.lastindex -1]
         return None

+
 class ExceptionGlobster(object):
     """A Globster that supports exception patterns.

@@ -235,9 +236,18 @@
                 ignores[1].append(p[1:])
             else:
                 ignores[0].append(p)
+ self.match = self._match_with_exceptions
+ if not ignores[1]:
+ # If there are no exclusions, then forced inclusions don't need
+ # higher priority
+ ignores[0].extend(ignores[2])
+ del ignores[2][:]
         self._ignores = [Globster(i) for i in ignores]
+ if not ignores[1]:
+ # We don't need any fancy logic, there are only straight 'includes'
+ self.match = self._ignores[0].match

- def match(self, filename):
+ def _match_with_exceptions(self, filename):
         """Searches for a pattern that matches the given filename.

         :return A matching pattern or None if there is no matching pattern.
@@ -249,6 +259,7 @@
             return None
         else:
             return self._ignores[0].match(filename)
+

 class _OrderedGlobster(Globster):
     """A Globster that keeps pattern order."""

(note that you can also get away with just defining "def match()" and then overriding it in __init__, but this is slightly more obvious that we may do that.)

[Martin Pool (mbp)]

ok with me too.

review: Approve

[John Whitley (whitley)]

> So a 10% hit is a bit of a shame, but not terrible. I also notice that there
> isn't a huge impact when you actually add the exceptions. Which tells me that
> it is just the extra calls to Globster.match() (with nothing to match) that
> are causing the problem.

Agreed.

> Do you care to try an evil hack?

That's one way, but it still incurs the perf hit when exceptions are in use. To clarify my earlier murmurings, I'm leaning towards an approach where the logical match number can be returned with the results (e.g. by modifying Globster's internals), making ExceptionGlobster a child of the so-modified Globster, and tweaking ExceptionGlobster to 1) assemble the regexes in the correct priority order, 2) preserve range information for the exceptions, and 3) modify match to suit.

In any event, optimizations can be submitted as a subsequent modification.

> (note that you can also get away with just defining "def match()" and then
> overriding it in __init__, but this is slightly more obvious that we may do
> that.)

Ah, nice trick w/ defining match in __init__.

[John A Meinel (jameinel)]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

John Whitley wrote:
>> So a 10% hit is a bit of a shame, but not terrible. I also notice that there
>> isn't a huge impact when you actually add the exceptions. Which tells me that
>> it is just the extra calls to Globster.match() (with nothing to match) that
>> are causing the problem.
>
> Agreed.
>
>> Do you care to try an evil hack?
>
> That's one way, but it still incurs the perf hit when exceptions are in use. To clarify my earlier murmurings, I'm leaning towards an approach where the logical match number can be returned with the results (e.g. by modifying Globster's internals), making ExceptionGlobster a child of the so-modified Globster, and tweaking ExceptionGlobster to 1) assemble the regexes in the correct priority order, 2) preserve range information for the exceptions, and 3) modify match to suit.
>
> In any event, optimizations can be submitted as a subsequent modification.

So one thing I was shooting for is that having the feature won't impact
people who aren't using it. Which my version does. Though I've also
worked out a better way.

It is a recognition that we only need to evaluate the "exception" case
if the ignore case matches. And then we only need the double-exception
case when the exception matches (except we also need to check if it
would fit as a regular ignore.)

I pushed this up as lp:~jameinel/bzr/ignore-exception, and have the diff
here.

Can you test the performance hit?

>
>> (note that you can also get away with just defining "def match()" and then
>> overriding it in __init__, but this is slightly more obvious that we may do
>> that.)
>
> Ah, nice trick w/ defining match in __init__.
>
>

v- This is the diff. Sorry to paste it as a quotation, but otherwise my
mail app wraps the lines.

> === modified file 'bzrlib/globbing.py'
> --- bzrlib/globbing.py 2010-01-11 16:44:02 +0000
> +++ bzrlib/globbing.py 2010-01-15 14:37:12 +0000
> @@ -1,4 +1,4 @@
> -# Copyright (C) 2006, 2008 Canonical Ltd
> +# Copyright (C) 2006-2010 Canonical Ltd
>
> # This program is free software; you can redistribute it and/or modify
> # it under the terms of the GNU General Public License as published by
> @@ -215,6 +215,7 @@
> return patterns[match.lastindex -1]
> return None
>
> +
> class ExceptionGlobster(object):
> """A Globster that supports exception patterns.
>
> @@ -235,6 +236,8 @@
> ignores[1].append(p[1:])
> else:
> ignores[0].append(p)
> + # double-exceptions are also simple ignores
> + ignores[0].extend(ignores[2])
> self._ignores = [Globster(i) for i in ignores]
>
> def match(self, filename):
> @@ -242,13 +245,21 @@
>
> :return A matching pattern or None if there is no matching pattern.
> """
> - double_neg = self._ignores[2].match(filename)
> - if double_neg:
> - return "!!%s" % double_neg
> - elif self._ignores[1].match(filename):
> - return None
> - else:
> - return self._ignores[0].match(filename)
> + m = self._ignores[0].match(filename)
> + if m is None:
> + ...

=== modified file 'NEWS'
--- NEWS	2010-01-11 13:15:01 +0000
+++ NEWS	2010-01-11 18:21:15 +0000
@@ -17,6 +17,13 @@
 New Features
 ************
 
+* New ignore patterns.  Patterns prefixed with '!' are exceptions to 
+  ignore patterns and take precedence over regular ignores.  Such 
+  exceptions are used to specify files that should be versioned which 
+  would otherwise be ignored.  Patterns prefixed with '!!' act as regular 
+  ignore patterns, but have highest precedence, even over the '!' 
+  exception patterns. (John Whitley, #428031)
+
 * Add bug information to log output when available.
   (Neil Martinsen-Burrell, Guillermo Gonzalez, #251729)
 

=== modified file 'bzrlib/builtins.py'
--- bzrlib/builtins.py	2010-01-08 00:05:01 +0000
+++ bzrlib/builtins.py	2010-01-11 18:21:15 +0000
@@ -2602,6 +2602,13 @@
     After adding, editing or deleting that file either indirectly by
     using this command or directly by using an editor, be sure to commit
     it.
+    
+    Patterns prefixed with '!' are exceptions to ignore patterns and take
+    precedence over regular ignores.  Such exceptions are used to specify
+    files that should be versioned which would otherwise be ignored.
+    
+    Patterns prefixed with '!!' act as regular ignore patterns, but have
+    precedence over the '!' exception patterns.
 
     Note: ignore patterns containing shell wildcards must be quoted from
     the shell on Unix.
@@ -2611,10 +2618,14 @@
 
             bzr ignore ./Makefile
 
-        Ignore class files in all directories::
+        Ignore .class files in all directories...::
 
             bzr ignore "*.class"
 
+        ...but do not ignore "special.class"::
+
+            bzr ignore "!special.class"
+
         Ignore .o files under the lib directory::
 
             bzr ignore "lib/**/*.o"
@@ -2626,6 +2637,13 @@
         Ignore everything but the "debian" toplevel directory::
 
             bzr ignore "RE:(?!debian/).*"
+        
+        Ignore everything except the "local" toplevel directory,
+        but always ignore "*~" autosave files, even under local/::
+        
+            bzr ignore "*"
+            bzr ignore "!./local"
+            bzr ignore "!!*~"
     """
 
     _see_also = ['status', 'ignored', 'patterns']

=== modified file 'bzrlib/globbing.py'
--- bzrlib/globbing.py	2009-11-11 21:38:02 +0000
+++ bzrlib/globbing.py	2010-01-11 18:21:15 +0000
@@ -215,6 +215,40 @@
                 return patterns[match.lastindex -1]
         return None
 
+class ExceptionGlobster(object):
+    """A Globster that supports exception patterns.
+    
+    Exceptions are ignore patterns prefixed with '!'.  Exception
+    patterns take precedence over regular patterns and cause a 
+    matching filename to return None from the match() function.  
+    Patterns using a '!!' prefix are highest precedence, and act 
+    as regular ignores. '!!' patterns are useful to establish ignores
+    that apply under paths specified by '!' exception patterns.
+    """
+    
+    def __init__(self,patterns):
+        ignores = [[], [], []]
+        for p in patterns:
+            if p.startswith(u'!!'):
+                ignores[2].append(p[2:])
+            elif p.startswith(u'!'):
+                ignores[1].append(p[1:])
+            else:
+                ignores[0].append(p)
+        self._ignores = [Globster(i) for i in ignores]
+        
+    def match(self, filename):
+        """Searches for a pattern that matches the given filename.
+
+        :return A matching pattern or None if there is no matching pattern.
+        """
+        double_neg = self._ignores[2].match(filename)
+        if double_neg:
+            return "!!%s" % double_neg
+        elif self._ignores[1].match(filename):
+            return None
+        else:
+            return self._ignores[0].match(filename)
 
 class _OrderedGlobster(Globster):
     """A Globster that keeps pattern order."""
@@ -244,8 +278,7 @@
 
     Doesn't normalize regular expressions - they may contain escapes.
     """
-
-    if not pattern.startswith('RE:'):
+    if not (pattern.startswith('RE:') or pattern.startswith('!RE:')):
         pattern = _slashes.sub('/', pattern)
     if len(pattern) > 1:
         pattern = pattern.rstrip('/')

=== modified file 'bzrlib/help_topics/en/patterns.txt'
--- bzrlib/help_topics/en/patterns.txt	2008-06-25 07:17:14 +0000
+++ bzrlib/help_topics/en/patterns.txt	2010-01-11 18:21:15 +0000
@@ -23,3 +23,6 @@
 patterns are identified by a 'RE:' prefix followed by the regular
 expression.  Regular expression patterns may not include named or
 numbered groups.
+
+Ignore patterns may be prefixed with '!', which means that a filename
+matched by that pattern will not be ignored.

=== modified file 'bzrlib/tests/per_workingtree/test_is_ignored.py'
--- bzrlib/tests/per_workingtree/test_is_ignored.py	2009-07-10 07:14:02 +0000
+++ bzrlib/tests/per_workingtree/test_is_ignored.py	2010-01-11 18:21:15 +0000
@@ -31,11 +31,15 @@
             ('.bzrignore', './rootdir\n'
                            'randomfile*\n'
                            '*bar\n'
+                           '!bazbar\n'
                            '?foo\n'
                            '*.~*\n'
                            'dir1/*f1\n'
                            'dir1/?f2\n'
+                           'RE:dir2/.*\.wombat\n'
                            'path/from/ro?t\n'
+                           '**/piffle.py\n'
+                           '!b/piffle.py\n'
                            'unicode\xc2\xb5\n' # u'\xb5'.encode('utf8')
                            'dos\r\n'
                            '\n' # empty line
@@ -58,6 +62,12 @@
         self.assertEqual("path/from/ro?t", tree.is_ignored('path/from/root'))
         self.assertEqual("path/from/ro?t", tree.is_ignored('path/from/roat'))
         self.assertEqual(None, tree.is_ignored('roat'))
+        
+        self.assertEqual('**/piffle.py', tree.is_ignored('piffle.py'))
+        self.assertEqual('**/piffle.py', tree.is_ignored('a/piffle.py'))
+        self.assertEqual(None, tree.is_ignored('b/piffle.py')) # exclusion
+        self.assertEqual('**/piffle.py', tree.is_ignored('foo/bar/piffle.py'))
+        self.assertEqual(None, tree.is_ignored('p/iffle.py'))
 
         self.assertEqual(u'unicode\xb5', tree.is_ignored(u'unicode\xb5'))
         self.assertEqual(u'unicode\xb5', tree.is_ignored(u'subdir/unicode\xb5'))
@@ -72,6 +82,8 @@
         self.assertEqual('*bar', tree.is_ignored(r'foo\nbar'))
         self.assertEqual('*bar', tree.is_ignored('bar'))
         self.assertEqual('*bar', tree.is_ignored('.bar'))
+        
+        self.assertEqual(None, tree.is_ignored('bazbar')) # exclusion
 
         self.assertEqual('?foo', tree.is_ignored('afoo'))
         self.assertEqual('?foo', tree.is_ignored('.foo'))
@@ -84,6 +96,9 @@
 
         self.assertEqual('dir1/?f2', tree.is_ignored('dir1/ff2'))
         self.assertEqual('dir1/?f2', tree.is_ignored('dir1/.f2'))
+        
+        self.assertEqual('RE:dir2/.*\.wombat', tree.is_ignored('dir2/foo.wombat'))
+        self.assertEqual(None, tree.is_ignored('dir2/foo'))
 
         # Blank lines and comments should be ignored
         self.assertEqual(None, tree.is_ignored(''))

=== modified file 'bzrlib/tests/test_globbing.py'
--- bzrlib/tests/test_globbing.py	2009-11-11 21:38:02 +0000
+++ bzrlib/tests/test_globbing.py	2010-01-11 18:21:15 +0000
@@ -17,6 +17,7 @@
 
 from bzrlib.globbing import (
     Globster,
+    ExceptionGlobster,
     _OrderedGlobster,
     normalize_pattern
     )
@@ -307,6 +308,30 @@
             self.assertEqual(patterns[x],globster.match(filename))
         self.assertEqual(None,globster.match('foobar.300'))
 
+class TestExceptionGlobster(TestCase):
+
+    def test_exclusion_patterns(self):
+        """test that exception patterns are not matched"""
+        patterns = [ u'*', u'!./local', u'!./local/**/*', u'!RE:\.z.*',u'!!./.zcompdump' ]
+        globster = ExceptionGlobster(patterns)
+        self.assertEqual(u'*', globster.match('tmp/foo.txt'))
+        self.assertEqual(None, globster.match('local'))
+        self.assertEqual(None, globster.match('local/bin/wombat'))
+        self.assertEqual(None, globster.match('.zshrc'))
+        self.assertEqual(None, globster.match('.zfunctions/fiddle/flam'))
+        self.assertEqual(u'!!./.zcompdump', globster.match('.zcompdump'))
+
+    def test_exclusion_order(self):
+        """test that ordering of exclusion patterns does not matter"""
+        patterns = [ u'static/**/*.html', u'!static/**/versionable.html']
+        globster = ExceptionGlobster(patterns)
+        self.assertEqual(u'static/**/*.html', globster.match('static/foo.html'))
+        self.assertEqual(None, globster.match('static/versionable.html'))
+        self.assertEqual(None, globster.match('static/bar/versionable.html'))
+        globster = ExceptionGlobster(reversed(patterns))
+        self.assertEqual(u'static/**/*.html', globster.match('static/foo.html'))
+        self.assertEqual(None, globster.match('static/versionable.html'))
+        self.assertEqual(None, globster.match('static/bar/versionable.html'))
 
 class TestOrderedGlobster(TestCase):
 

=== modified file 'bzrlib/tests/test_ignores.py'
--- bzrlib/tests/test_ignores.py	2009-03-23 14:59:43 +0000
+++ bzrlib/tests/test_ignores.py	2010-01-11 18:21:15 +0000
@@ -34,6 +34,8 @@
                 '\n' # empty line
                 '#comment\n'
                 ' xx \n' # whitespace
+                '!RE:^\.z.*\n'
+                '!!./.zcompdump\n'
                 ))
         self.assertEqual(set(['./rootdir',
                           'randomfile*',
@@ -41,6 +43,8 @@
                           u'unicode\xb5',
                           'dos',
                           ' xx ',
+                          '!RE:^\.z.*',
+                          '!!./.zcompdump',
                          ]), ignored)
 
     def test_parse_empty(self):

=== modified file 'bzrlib/workingtree.py'
--- bzrlib/workingtree.py	2009-12-22 05:24:50 +0000
+++ bzrlib/workingtree.py	2010-01-11 18:21:15 +0000
@@ -1741,13 +1741,15 @@
         r"""Check whether the filename matches an ignore pattern.
 
         Patterns containing '/' or '\' need to match the whole path;
-        others match against only the last component.
+        others match against only the last component.  Patterns starting
+        with '!' are ignore exceptions.  Exceptions take precedence
+        over regular patterns and cause the filename to not be ignored.
 
         If the file is ignored, returns the pattern which caused it to
         be ignored, otherwise None.  So this can simply be used as a
         boolean if desired."""
         if getattr(self, '_ignoreglobster', None) is None:
-            self._ignoreglobster = globbing.Globster(self.get_ignore_list())
+            self._ignoreglobster = globbing.ExceptionGlobster(self.get_ignore_list())
         return self._ignoreglobster.match(filename)
 
     def kind(self, file_id):