match: remove unnecessary optimization where visitdir() returns 'all'

Match's visitdir() was prematurely optimized to return 'all' in some cases, so
that the caller would not have to call it for directories within the current
directory. This change makes the visitdir system less flexible for future
changes, such as making visitdir consider the match's include and exclude
patterns.

As a demonstration of this optimization not actually improving performance,
I ran 'hg files -r . media' on the Mozilla repository, stored as treemanifest
revlogs.

With best of ten tries, the command took 1.07s both with and without the
optimization, even though the optimization reduced the calls from visitdir()
from 987 to 51.

mercurial/manifest.py

@@ -1,961 +1,947 b''
 # manifest.py - manifest revision class for mercurial
 #
 # Copyright 2005-2007 Matt Mackall <[e-mail]>
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 from i18n import _
 import mdiff, parsers, error, revlog, util
 import array, struct
 import os
 
 propertycache = util.propertycache
 
 def _parsev1(data):
     # This method does a little bit of excessive-looking
     # precondition checking. This is so that the behavior of this
     # class exactly matches its C counterpart to try and help
     # prevent surprise breakage for anyone that develops against
     # the pure version.
     if data and data[-1] != '\n':
         raise ValueError('Manifest did not end in a newline.')
     prev = None
     for l in data.splitlines():
         if prev is not None and prev > l:
             raise ValueError('Manifest lines not in sorted order.')
         prev = l
         f, n = l.split('\0')
         if len(n) > 40:
             yield f, revlog.bin(n[:40]), n[40:]
         else:
             yield f, revlog.bin(n), ''
 
 def _parsev2(data):
     metadataend = data.find('\n')
     # Just ignore metadata for now
     pos = metadataend + 1
     prevf = ''
     while pos < len(data):
         end = data.find('\n', pos + 1) # +1 to skip stem length byte
         if end == -1:
             raise ValueError('Manifest ended with incomplete file entry.')
         stemlen = ord(data[pos])
         items = data[pos + 1:end].split('\0')
         f = prevf[:stemlen] + items[0]
         if prevf > f:
             raise ValueError('Manifest entries not in sorted order.')
         fl = items[1]
         # Just ignore metadata (items[2:] for now)
         n = data[end + 1:end + 21]
         yield f, n, fl
         pos = end + 22
         prevf = f
 
 def _parse(data):
     """Generates (path, node, flags) tuples from a manifest text"""
     if data.startswith('\0'):
         return iter(_parsev2(data))
     else:
         return iter(_parsev1(data))
 
 def _text(it, usemanifestv2):
     """Given an iterator over (path, node, flags) tuples, returns a manifest
     text"""
     if usemanifestv2:
         return _textv2(it)
     else:
         return _textv1(it)
 
 def _textv1(it):
     files = []
     lines = []
     _hex = revlog.hex
     for f, n, fl in it:
         files.append(f)
         # if this is changed to support newlines in filenames,
         # be sure to check the templates/ dir again (especially *-raw.tmpl)
         lines.append("%s\0%s%s\n" % (f, _hex(n), fl))
 
     _checkforbidden(files)
     return ''.join(lines)
 
 def _textv2(it):
     files = []
     lines = ['\0\n']
     prevf = ''
     for f, n, fl in it:
         files.append(f)
         stem = os.path.commonprefix([prevf, f])
         stemlen = min(len(stem), 255)
         lines.append("%c%s\0%s\n%s\n" % (stemlen, f[stemlen:], fl, n))
         prevf = f
     _checkforbidden(files)
     return ''.join(lines)
 
 class _lazymanifest(dict):
     """This is the pure implementation of lazymanifest.
 
     It has not been optimized *at all* and is not lazy.
     """
 
     def __init__(self, data):
         dict.__init__(self)
         for f, n, fl in _parse(data):
             self[f] = n, fl
 
     def __setitem__(self, k, v):
         node, flag = v
         assert node is not None
         if len(node) > 21:
             node = node[:21] # match c implementation behavior
         dict.__setitem__(self, k, (node, flag))
 
     def __iter__(self):
         return iter(sorted(dict.keys(self)))
 
     def iterkeys(self):
         return iter(sorted(dict.keys(self)))
 
     def iterentries(self):
         return ((f, e[0], e[1]) for f, e in sorted(self.iteritems()))
 
     def copy(self):
         c = _lazymanifest('')
         c.update(self)
         return c
 
     def diff(self, m2, clean=False):
         '''Finds changes between the current manifest and m2.'''
         diff = {}
 
         for fn, e1 in self.iteritems():
             if fn not in m2:
                 diff[fn] = e1, (None, '')
             else:
                 e2 = m2[fn]
                 if e1 != e2:
                     diff[fn] = e1, e2
                 elif clean:
                     diff[fn] = None
 
         for fn, e2 in m2.iteritems():
             if fn not in self:
                 diff[fn] = (None, ''), e2
 
         return diff
 
     def filtercopy(self, filterfn):
         c = _lazymanifest('')
         for f, n, fl in self.iterentries():
             if filterfn(f):
                 c[f] = n, fl
         return c
 
     def text(self):
         """Get the full data of this manifest as a bytestring."""
         return _textv1(self.iterentries())
 
 try:
     _lazymanifest = parsers.lazymanifest
 except AttributeError:
     pass
 
 class manifestdict(object):
     def __init__(self, data=''):
         if data.startswith('\0'):
             #_lazymanifest can not parse v2
             self._lm = _lazymanifest('')
             for f, n, fl in _parsev2(data):
                 self._lm[f] = n, fl
         else:
             self._lm = _lazymanifest(data)
 
     def __getitem__(self, key):
         return self._lm[key][0]
 
     def find(self, key):
         return self._lm[key]
 
     def __len__(self):
         return len(self._lm)
 
     def __setitem__(self, key, node):
         self._lm[key] = node, self.flags(key, '')
 
     def __contains__(self, key):
         return key in self._lm
 
     def __delitem__(self, key):
         del self._lm[key]
 
     def __iter__(self):
         return self._lm.__iter__()
 
     def iterkeys(self):
         return self._lm.iterkeys()
 
     def keys(self):
         return list(self.iterkeys())
 
     def filesnotin(self, m2):
         '''Set of files in this manifest that are not in the other'''
         files = set(self)
         files.difference_update(m2)
         return files
 
     @propertycache
     def _dirs(self):
         return util.dirs(self)
 
     def dirs(self):
         return self._dirs
 
     def hasdir(self, dir):
         return dir in self._dirs
 
     def _filesfastpath(self, match):
         '''Checks whether we can correctly and quickly iterate over matcher
         files instead of over manifest files.'''
         files = match.files()
         return (len(files) < 100 and (match.isexact() or
             (not match.anypats() and all(fn in self for fn in files))))
 
     def walk(self, match):
         '''Generates matching file names.
 
         Equivalent to manifest.matches(match).iterkeys(), but without creating
         an entirely new manifest.
 
         It also reports nonexistent files by marking them bad with match.bad().
         '''
         if match.always():
             for f in iter(self):
                 yield f
             return
 
         fset = set(match.files())
 
         # avoid the entire walk if we're only looking for specific files
         if self._filesfastpath(match):
             for fn in sorted(fset):
                 yield fn
             return
 
         for fn in self:
             if fn in fset:
                 # specified pattern is the exact name
                 fset.remove(fn)
             if match(fn):
                 yield fn
 
         # for dirstate.walk, files=['.'] means "walk the whole tree".
         # follow that here, too
         fset.discard('.')
 
         for fn in sorted(fset):
             if not self.hasdir(fn):
                 match.bad(fn, None)
 
     def matches(self, match):
         '''generate a new manifest filtered by the match argument'''
         if match.always():
             return self.copy()
 
         if self._filesfastpath(match):
             m = manifestdict()
             lm = self._lm
             for fn in match.files():
                 if fn in lm:
                     m._lm[fn] = lm[fn]
             return m
 
         m = manifestdict()
         m._lm = self._lm.filtercopy(match)
         return m
 
     def diff(self, m2, clean=False):
         '''Finds changes between the current manifest and m2.
 
         Args:
           m2: the manifest to which this manifest should be compared.
           clean: if true, include files unchanged between these manifests
                  with a None value in the returned dictionary.
 
         The result is returned as a dict with filename as key and
         values of the form ((n1,fl1),(n2,fl2)), where n1/n2 is the
         nodeid in the current/other manifest and fl1/fl2 is the flag
         in the current/other manifest. Where the file does not exist,
         the nodeid will be None and the flags will be the empty
         string.
         '''
         return self._lm.diff(m2._lm, clean)
 
     def setflag(self, key, flag):
         self._lm[key] = self[key], flag
 
     def get(self, key, default=None):
         try:
             return self._lm[key][0]
         except KeyError:
             return default
 
     def flags(self, key, default=''):
         try:
             return self._lm[key][1]
         except KeyError:
             return default
 
     def copy(self):
         c = manifestdict()
         c._lm = self._lm.copy()
         return c
 
     def iteritems(self):
         return (x[:2] for x in self._lm.iterentries())
 
     def text(self, usemanifestv2=False):
         if usemanifestv2:
             return _textv2(self._lm.iterentries())
         else:
             # use (probably) native version for v1
             return self._lm.text()
 
     def fastdelta(self, base, changes):
         """Given a base manifest text as an array.array and a list of changes
         relative to that text, compute a delta that can be used by revlog.
         """
         delta = []
         dstart = None
         dend = None
         dline = [""]
         start = 0
         # zero copy representation of base as a buffer
         addbuf = util.buffer(base)
 
         # start with a readonly loop that finds the offset of
         # each line and creates the deltas
         for f, todelete in changes:
             # bs will either be the index of the item or the insert point
             start, end = _msearch(addbuf, f, start)
             if not todelete:
                 h, fl = self._lm[f]
                 l = "%s\0%s%s\n" % (f, revlog.hex(h), fl)
             else:
                 if start == end:
                     # item we want to delete was not found, error out
                     raise AssertionError(
                             _("failed to remove %s from manifest") % f)
                 l = ""
             if dstart is not None and dstart <= start and dend >= start:
                 if dend < end:
                     dend = end
                 if l:
                     dline.append(l)
             else:
                 if dstart is not None:
                     delta.append([dstart, dend, "".join(dline)])
                 dstart = start
                 dend = end
                 dline = [l]
 
         if dstart is not None:
             delta.append([dstart, dend, "".join(dline)])
         # apply the delta to the base, and get a delta for addrevision
         deltatext, arraytext = _addlistdelta(base, delta)
         return arraytext, deltatext
 
 def _msearch(m, s, lo=0, hi=None):
     '''return a tuple (start, end) that says where to find s within m.
 
     If the string is found m[start:end] are the line containing
     that string.  If start == end the string was not found and
     they indicate the proper sorted insertion point.
 
     m should be a buffer or a string
     s is a string'''
     def advance(i, c):
         while i < lenm and m[i] != c:
             i += 1
         return i
     if not s:
         return (lo, lo)
     lenm = len(m)
     if not hi:
         hi = lenm
     while lo < hi:
         mid = (lo + hi) // 2
         start = mid
         while start > 0 and m[start - 1] != '\n':
             start -= 1
         end = advance(start, '\0')
         if m[start:end] < s:
             # we know that after the null there are 40 bytes of sha1
             # this translates to the bisect lo = mid + 1
             lo = advance(end + 40, '\n') + 1
         else:
             # this translates to the bisect hi = mid
             hi = start
     end = advance(lo, '\0')
     found = m[lo:end]
     if s == found:
         # we know that after the null there are 40 bytes of sha1
         end = advance(end + 40, '\n')
         return (lo, end + 1)
     else:
         return (lo, lo)
 
 def _checkforbidden(l):
     """Check filenames for illegal characters."""
     for f in l:
         if '\n' in f or '\r' in f:
             raise error.RevlogError(
                 _("'\\n' and '\\r' disallowed in filenames: %r") % f)
 
 
 # apply the changes collected during the bisect loop to our addlist
 # return a delta suitable for addrevision
 def _addlistdelta(addlist, x):
     # for large addlist arrays, building a new array is cheaper
     # than repeatedly modifying the existing one
     currentposition = 0
     newaddlist = array.array('c')
 
     for start, end, content in x:
         newaddlist += addlist[currentposition:start]
         if content:
             newaddlist += array.array('c', content)
 
         currentposition = end
 
     newaddlist += addlist[currentposition:]
 
     deltatext = "".join(struct.pack(">lll", start, end, len(content))
                    + content for start, end, content in x)
     return deltatext, newaddlist
 
 def _splittopdir(f):
     if '/' in f:
         dir, subpath = f.split('/', 1)
         return dir + '/', subpath
     else:
         return '', f
 
 class treemanifest(object):
     def __init__(self, dir='', text=''):
         self._dir = dir
         self._node = revlog.nullid
         self._dirs = {}
         # Using _lazymanifest here is a little slower than plain old dicts
         self._files = {}
         self._flags = {}
         def readsubtree(subdir, subm):
             raise AssertionError('treemanifest constructor only accepts '
                                  'flat manifests')
         self.parse(text, readsubtree)
 
     def _subpath(self, path):
         return self._dir + path
 
     def __len__(self):
         size = len(self._files)
         for m in self._dirs.values():
             size += m.__len__()
         return size
 
     def _isempty(self):
         return (not self._files and (not self._dirs or
                 all(m._isempty() for m in self._dirs.values())))
 
     def __str__(self):
         return ('<treemanifest dir=%s, node=%s>' %
                 (self._dir, revlog.hex(self._node)))
 
     def dir(self):
         '''The directory that this tree manifest represents, including a
         trailing '/'. Empty string for the repo root directory.'''
         return self._dir
 
     def node(self):
         '''This node of this instance. nullid for unsaved instances. Should
         be updated when the instance is read or written from a revlog.
         '''
         return self._node
 
     def setnode(self, node):
         self._node = node
 
     def iteritems(self):
         for p, n in sorted(self._dirs.items() + self._files.items()):
             if p in self._files:
                 yield self._subpath(p), n
             else:
                 for f, sn in n.iteritems():
                     yield f, sn
 
     def iterkeys(self):
         for p in sorted(self._dirs.keys() + self._files.keys()):
             if p in self._files:
                 yield self._subpath(p)
             else:
                 for f in self._dirs[p].iterkeys():
                     yield f
 
     def keys(self):
         return list(self.iterkeys())
 
     def __iter__(self):
         return self.iterkeys()
 
     def __contains__(self, f):
         if f is None:
             return False
         dir, subpath = _splittopdir(f)
         if dir:
             if dir not in self._dirs:
                 return False
             return self._dirs[dir].__contains__(subpath)
         else:
             return f in self._files
 
     def get(self, f, default=None):
         dir, subpath = _splittopdir(f)
         if dir:
             if dir not in self._dirs:
                 return default
             return self._dirs[dir].get(subpath, default)
         else:
             return self._files.get(f, default)
 
     def __getitem__(self, f):
         dir, subpath = _splittopdir(f)
         if dir:
             return self._dirs[dir].__getitem__(subpath)
         else:
             return self._files[f]
 
     def flags(self, f):
         dir, subpath = _splittopdir(f)
         if dir:
             if dir not in self._dirs:
                 return ''
             return self._dirs[dir].flags(subpath)
         else:
             if f in self._dirs:
                 return ''
             return self._flags.get(f, '')
 
     def find(self, f):
         dir, subpath = _splittopdir(f)
         if dir:
             return self._dirs[dir].find(subpath)
         else:
             return self._files[f], self._flags.get(f, '')
 
     def __delitem__(self, f):
         dir, subpath = _splittopdir(f)
         if dir:
             self._dirs[dir].__delitem__(subpath)
             # If the directory is now empty, remove it
             if self._dirs[dir]._isempty():
                 del self._dirs[dir]
         else:
             del self._files[f]
             if f in self._flags:
                 del self._flags[f]
 
     def __setitem__(self, f, n):
         assert n is not None
         dir, subpath = _splittopdir(f)
         if dir:
             if dir not in self._dirs:
                 self._dirs[dir] = treemanifest(self._subpath(dir))
             self._dirs[dir].__setitem__(subpath, n)
         else:
             self._files[f] = n[:21] # to match manifestdict's behavior
 
     def setflag(self, f, flags):
         """Set the flags (symlink, executable) for path f."""
         assert 'd' not in flags
         dir, subpath = _splittopdir(f)
         if dir:
             if dir not in self._dirs:
                 self._dirs[dir] = treemanifest(self._subpath(dir))
             self._dirs[dir].setflag(subpath, flags)
         else:
             self._flags[f] = flags
 
     def copy(self):
         copy = treemanifest(self._dir)
         copy._node = self._node
         for d in self._dirs:
             copy._dirs[d] = self._dirs[d].copy()
         copy._files = dict.copy(self._files)
         copy._flags = dict.copy(self._flags)
         return copy
 
     def filesnotin(self, m2):
         '''Set of files in this manifest that are not in the other'''
         files = set()
         def _filesnotin(t1, t2):
             for d, m1 in t1._dirs.iteritems():
                 if d in t2._dirs:
                     m2 = t2._dirs[d]
                     _filesnotin(m1, m2)
                 else:
                     files.update(m1.iterkeys())
 
             for fn in t1._files.iterkeys():
                 if fn not in t2._files:
                     files.add(t1._subpath(fn))
 
         _filesnotin(self, m2)
         return files
 
     @propertycache
     def _alldirs(self):
         return util.dirs(self)
 
     def dirs(self):
         return self._alldirs
 
     def hasdir(self, dir):
         topdir, subdir = _splittopdir(dir)
         if topdir:
             if topdir in self._dirs:
                 return self._dirs[topdir].hasdir(subdir)
             return False
         return (dir + '/') in self._dirs
 
     def walk(self, match):
         '''Generates matching file names.
 
         Equivalent to manifest.matches(match).iterkeys(), but without creating
         an entirely new manifest.
 
         It also reports nonexistent files by marking them bad with match.bad().
         '''
         if match.always():
             for f in iter(self):
                 yield f
             return
 
         fset = set(match.files())
 
         for fn in self._walk(match):
             if fn in fset:
                 # specified pattern is the exact name
                 fset.remove(fn)
             yield fn
 
         # for dirstate.walk, files=['.'] means "walk the whole tree".
         # follow that here, too
         fset.discard('.')
 
         for fn in sorted(fset):
             if not self.hasdir(fn):
                 match.bad(fn, None)
 
-    def _walk(self, match, alldirs=False):
-        '''Recursively generates matching file names for walk().
-
-        Will visit all subdirectories if alldirs is True, otherwise it will
-        only visit subdirectories for which match.visitdir is True.'''
-
-        if not alldirs:
-            # substring to strip trailing slash
-            visit = match.visitdir(self._dir[:-1] or '.')
-            if not visit:
+    def _walk(self, match):
+        '''Recursively generates matching file names for walk().'''
+        if not match.visitdir(self._dir[:-1] or '.'):
                 return
-            alldirs = (visit == 'all')
 
         # yield this dir's files and walk its submanifests
         for p in sorted(self._dirs.keys() + self._files.keys()):
             if p in self._files:
                 fullp = self._subpath(p)
                 if match(fullp):
                     yield fullp
             else:
-                for f in self._dirs[p]._walk(match, alldirs):
+                for f in self._dirs[p]._walk(match):
                     yield f
 
     def matches(self, match):
         '''generate a new manifest filtered by the match argument'''
         if match.always():
             return self.copy()
 
         return self._matches(match)
 
-    def _matches(self, match, alldirs=False):
+    def _matches(self, match):
         '''recursively generate a new manifest filtered by the match argument.
-
-        Will visit all subdirectories if alldirs is True, otherwise it will
-        only visit subdirectories for which match.visitdir is True.'''
-
+        '''
         ret = treemanifest(self._dir)
-        if not alldirs:
-            # substring to strip trailing slash
-            visit = match.visitdir(self._dir[:-1] or '.')
-            if not visit:
+
+        if not match.visitdir(self._dir[:-1] or '.'):
                 return ret
-            alldirs = (visit == 'all')
 
         for fn in self._files:
             fullp = self._subpath(fn)
             if not match(fullp):
                 continue
             ret._files[fn] = self._files[fn]
             if fn in self._flags:
                 ret._flags[fn] = self._flags[fn]
 
         for dir, subm in self._dirs.iteritems():
-            m = subm._matches(match, alldirs)
+            m = subm._matches(match)
             if not m._isempty():
                 ret._dirs[dir] = m
 
         return ret
 
     def diff(self, m2, clean=False):
         '''Finds changes between the current manifest and m2.
 
         Args:
           m2: the manifest to which this manifest should be compared.
           clean: if true, include files unchanged between these manifests
                  with a None value in the returned dictionary.
 
         The result is returned as a dict with filename as key and
         values of the form ((n1,fl1),(n2,fl2)), where n1/n2 is the
         nodeid in the current/other manifest and fl1/fl2 is the flag
         in the current/other manifest. Where the file does not exist,
         the nodeid will be None and the flags will be the empty
         string.
         '''
         result = {}
         emptytree = treemanifest()
         def _diff(t1, t2):
             for d, m1 in t1._dirs.iteritems():
                 m2 = t2._dirs.get(d, emptytree)
                 _diff(m1, m2)
 
             for d, m2 in t2._dirs.iteritems():
                 if d not in t1._dirs:
                     _diff(emptytree, m2)
 
             for fn, n1 in t1._files.iteritems():
                 fl1 = t1._flags.get(fn, '')
                 n2 = t2._files.get(fn, None)
                 fl2 = t2._flags.get(fn, '')
                 if n1 != n2 or fl1 != fl2:
                     result[t1._subpath(fn)] = ((n1, fl1), (n2, fl2))
                 elif clean:
                     result[t1._subpath(fn)] = None
 
             for fn, n2 in t2._files.iteritems():
                 if fn not in t1._files:
                     fl2 = t2._flags.get(fn, '')
                     result[t2._subpath(fn)] = ((None, ''), (n2, fl2))
 
         _diff(self, m2)
         return result
 
     def parse(self, text, readsubtree):
         for f, n, fl in _parse(text):
             if fl == 'd':
                 f = f + '/'
                 self._dirs[f] = readsubtree(self._subpath(f), n)
             else:
                 # Use __setitem__ and setflag rather than assigning directly
                 # to _files and _flags, thereby letting us parse flat manifests
                 # as well as tree manifests.
                 self[f] = n
                 if fl:
                     self.setflag(f, fl)
 
     def text(self, usemanifestv2=False):
         """Get the full data of this manifest as a bytestring."""
         flags = self.flags
         return _text(((f, self[f], flags(f)) for f in self.keys()),
                      usemanifestv2)
 
     def dirtext(self, usemanifestv2=False):
         """Get the full data of this directory as a bytestring. Make sure that
         any submanifests have been written first, so their nodeids are correct.
         """
         flags = self.flags
         dirs = [(d[:-1], self._dirs[d]._node, 'd') for d in self._dirs]
         files = [(f, self._files[f], flags(f)) for f in self._files]
         return _text(sorted(dirs + files), usemanifestv2)
 
     def writesubtrees(self, m1, m2, writesubtree):
         emptytree = treemanifest()
         for d, subm in self._dirs.iteritems():
             subp1 = m1._dirs.get(d, emptytree)._node
             subp2 = m2._dirs.get(d, emptytree)._node
             if subp1 == revlog.nullid:
                 subp1, subp2 = subp2, subp1
             writesubtree(subm, subp1, subp2)
 
 class manifest(revlog.revlog):
     def __init__(self, opener, dir='', dirlogcache=None):
         '''The 'dir' and 'dirlogcache' arguments are for internal use by
         manifest.manifest only. External users should create a root manifest
         log with manifest.manifest(opener) and call dirlog() on it.
         '''
         # During normal operations, we expect to deal with not more than four
         # revs at a time (such as during commit --amend). When rebasing large
         # stacks of commits, the number can go up, hence the config knob below.
         cachesize = 4
         usetreemanifest = False
         usemanifestv2 = False
         opts = getattr(opener, 'options', None)
         if opts is not None:
             cachesize = opts.get('manifestcachesize', cachesize)
             usetreemanifest = opts.get('treemanifest', usetreemanifest)
             usemanifestv2 = opts.get('manifestv2', usemanifestv2)
         self._mancache = util.lrucachedict(cachesize)
         self._treeinmem = usetreemanifest
         self._treeondisk = usetreemanifest
         self._usemanifestv2 = usemanifestv2
         indexfile = "00manifest.i"
         if dir:
             assert self._treeondisk
             if not dir.endswith('/'):
                 dir = dir + '/'
             indexfile = "meta/" + dir + "00manifest.i"
         revlog.revlog.__init__(self, opener, indexfile)
         self._dir = dir
         # The dirlogcache is kept on the root manifest log
         if dir:
             self._dirlogcache = dirlogcache
         else:
             self._dirlogcache = {'': self}
 
     def _newmanifest(self, data=''):
         if self._treeinmem:
             return treemanifest(self._dir, data)
         return manifestdict(data)
 
     def dirlog(self, dir):
         assert self._treeondisk
         if dir not in self._dirlogcache:
             self._dirlogcache[dir] = manifest(self.opener, dir,
                                               self._dirlogcache)
         return self._dirlogcache[dir]
 
     def _slowreaddelta(self, node):
         r0 = self.deltaparent(self.rev(node))
         m0 = self.read(self.node(r0))
         m1 = self.read(node)
         md = self._newmanifest()
         for f, ((n0, fl0), (n1, fl1)) in m0.diff(m1).iteritems():
             if n1:
                 md[f] = n1
                 if fl1:
                     md.setflag(f, fl1)
         return md
 
     def readdelta(self, node):
         if self._usemanifestv2 or self._treeondisk:
             return self._slowreaddelta(node)
         r = self.rev(node)
         d = mdiff.patchtext(self.revdiff(self.deltaparent(r), r))
         return self._newmanifest(d)
 
     def readfast(self, node):
         '''use the faster of readdelta or read
 
         This will return a manifest which is either only the files
         added/modified relative to p1, or all files in the
         manifest. Which one is returned depends on the codepath used
         to retrieve the data.
         '''
         r = self.rev(node)
         deltaparent = self.deltaparent(r)
         if deltaparent != revlog.nullrev and deltaparent in self.parentrevs(r):
             return self.readdelta(node)
         return self.read(node)
 
     def read(self, node):
         if node == revlog.nullid:
             return self._newmanifest() # don't upset local cache
         if node in self._mancache:
             return self._mancache[node][0]
         text = self.revision(node)
         if self._treeondisk:
             def readsubtree(dir, subm):
                 return self.dirlog(dir).read(subm)
             m = self._newmanifest()
             m.parse(text, readsubtree)
             m.setnode(node)
             arraytext = None
         else:
             m = self._newmanifest(text)
             arraytext = array.array('c', text)
         self._mancache[node] = (m, arraytext)
         return m
 
     def find(self, node, f):
         '''look up entry for a single file efficiently.
         return (node, flags) pair if found, (None, None) if not.'''
         m = self.read(node)
         try:
             return m.find(f)
         except KeyError:
             return None, None
 
     def add(self, m, transaction, link, p1, p2, added, removed):
         if (p1 in self._mancache and not self._treeinmem
             and not self._usemanifestv2):
             # If our first parent is in the manifest cache, we can
             # compute a delta here using properties we know about the
             # manifest up-front, which may save time later for the
             # revlog layer.
 
             _checkforbidden(added)
             # combine the changed lists into one list for sorting
             work = [(x, False) for x in added]
             work.extend((x, True) for x in removed)
             # this could use heapq.merge() (from Python 2.6+) or equivalent
             # since the lists are already sorted
             work.sort()
 
             arraytext, deltatext = m.fastdelta(self._mancache[p1][1], work)
             cachedelta = self.rev(p1), deltatext
             text = util.buffer(arraytext)
             n = self.addrevision(text, transaction, link, p1, p2, cachedelta)
         else:
             # The first parent manifest isn't already loaded, so we'll
             # just encode a fulltext of the manifest and pass that
             # through to the revlog layer, and let it handle the delta
             # process.
             if self._treeondisk:
                 m1 = self.read(p1)
                 m2 = self.read(p2)
                 n = self._addtree(m, transaction, link, m1, m2)
                 arraytext = None
             else:
                 text = m.text(self._usemanifestv2)
                 n = self.addrevision(text, transaction, link, p1, p2)
                 arraytext = array.array('c', text)
 
         self._mancache[n] = (m, arraytext)
 
         return n
 
     def _addtree(self, m, transaction, link, m1, m2):
         def writesubtree(subm, subp1, subp2):
             sublog = self.dirlog(subm.dir())
             sublog.add(subm, transaction, link, subp1, subp2, None, None)
         m.writesubtrees(m1, m2, writesubtree)
         text = m.dirtext(self._usemanifestv2)
         # If the manifest is unchanged compared to one parent,
         # don't write a new revision
         if text == m1.dirtext(self._usemanifestv2):
             n = m1.node()
         elif text == m2.dirtext(self._usemanifestv2):
             n = m2.node()
         else:
             n = self.addrevision(text, transaction, link, m1.node(), m2.node())
         # Save nodeid so parent manifest can calculate its nodeid
         m.setnode(n)
         return n

mercurial/match.py

@@ -1,546 +1,542 b''
 # match.py - filename matching
 #
 #  Copyright 2008, 2009 Matt Mackall <[e-mail]> and others
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
 import re
 import util, pathutil
 from i18n import _
 
 propertycache = util.propertycache
 
 def _rematcher(regex):
     '''compile the regexp with the best available regexp engine and return a
     matcher function'''
     m = util.re.compile(regex)
     try:
         # slightly faster, provided by facebook's re2 bindings
         return m.test_match
     except AttributeError:
         return m.match
 
 def _expandsets(kindpats, ctx, listsubrepos):
     '''Returns the kindpats list with the 'set' patterns expanded.'''
     fset = set()
     other = []
 
     for kind, pat in kindpats:
         if kind == 'set':
             if not ctx:
                 raise util.Abort("fileset expression with no context")
             s = ctx.getfileset(pat)
             fset.update(s)
 
             if listsubrepos:
                 for subpath in ctx.substate:
                     s = ctx.sub(subpath).getfileset(pat)
                     fset.update(subpath + '/' + f for f in s)
 
             continue
         other.append((kind, pat))
     return fset, other
 
 def _kindpatsalwaysmatch(kindpats):
     """"Checks whether the kindspats match everything, as e.g.
     'relpath:.' does.
     """
     for kind, pat in kindpats:
         if pat != '' or kind not in ['relpath', 'glob']:
             return False
     return True
 
 class match(object):
     def __init__(self, root, cwd, patterns, include=[], exclude=[],
                  default='glob', exact=False, auditor=None, ctx=None,
                  listsubrepos=False):
         """build an object to match a set of file patterns
 
         arguments:
         root - the canonical root of the tree you're matching against
         cwd - the current working directory, if relevant
         patterns - patterns to find
         include - patterns to include (unless they are excluded)
         exclude - patterns to exclude (even if they are included)
         default - if a pattern in patterns has no explicit type, assume this one
         exact - patterns are actually filenames (include/exclude still apply)
 
         a pattern is one of:
         'glob:<glob>' - a glob relative to cwd
         're:<regexp>' - a regular expression
         'path:<path>' - a path relative to repository root
         'relglob:<glob>' - an unrooted glob (*.c matches C files in all dirs)
         'relpath:<path>' - a path relative to cwd
         'relre:<regexp>' - a regexp that needn't match the start of a name
         'set:<fileset>' - a fileset expression
         '<something>' - a pattern of the specified default type
         """
 
         self._root = root
         self._cwd = cwd
         self._files = [] # exact files and roots of patterns
         self._anypats = bool(include or exclude)
         self._always = False
         self._pathrestricted = bool(include or exclude or patterns)
 
         matchfns = []
         if include:
             kindpats = self._normalize(include, 'glob', root, cwd, auditor)
             self.includepat, im = _buildmatch(ctx, kindpats, '(?:/|$)',
                                               listsubrepos)
             matchfns.append(im)
         if exclude:
             kindpats = self._normalize(exclude, 'glob', root, cwd, auditor)
             self.excludepat, em = _buildmatch(ctx, kindpats, '(?:/|$)',
                                               listsubrepos)
             matchfns.append(lambda f: not em(f))
         if exact:
             if isinstance(patterns, list):
                 self._files = patterns
             else:
                 self._files = list(patterns)
             matchfns.append(self.exact)
         elif patterns:
             kindpats = self._normalize(patterns, default, root, cwd, auditor)
             if not _kindpatsalwaysmatch(kindpats):
                 self._files = _roots(kindpats)
                 self._anypats = self._anypats or _anypats(kindpats)
                 self.patternspat, pm = _buildmatch(ctx, kindpats, '$',
                                                    listsubrepos)
                 matchfns.append(pm)
 
         if not matchfns:
             m = util.always
             self._always = True
         elif len(matchfns) == 1:
             m = matchfns[0]
         else:
             def m(f):
                 for matchfn in matchfns:
                     if not matchfn(f):
                         return False
                 return True
 
         self.matchfn = m
         self._fmap = set(self._files)
 
     def __call__(self, fn):
         return self.matchfn(fn)
     def __iter__(self):
         for f in self._files:
             yield f
 
     # Callbacks related to how the matcher is used by dirstate.walk.
     # Subscribers to these events must monkeypatch the matcher object.
     def bad(self, f, msg):
         '''Callback from dirstate.walk for each explicit file that can't be
         found/accessed, with an error message.'''
         pass
 
     # If an explicitdir is set, it will be called when an explicitly listed
     # directory is visited.
     explicitdir = None
 
     # If an traversedir is set, it will be called when a directory discovered
     # by recursive traversal is visited.
     traversedir = None
 
     def abs(self, f):
         '''Convert a repo path back to path that is relative to the root of the
         matcher.'''
         return f
 
     def rel(self, f):
         '''Convert repo path back to path that is relative to cwd of matcher.'''
         return util.pathto(self._root, self._cwd, f)
 
     def uipath(self, f):
         '''Convert repo path to a display path.  If patterns or -I/-X were used
         to create this matcher, the display path will be relative to cwd.
         Otherwise it is relative to the root of the repo.'''
         return (self._pathrestricted and self.rel(f)) or self.abs(f)
 
     def files(self):
         '''Explicitly listed files or patterns or roots:
         if no patterns or .always(): empty list,
         if exact: list exact files,
         if not .anypats(): list all files and dirs,
         else: optimal roots'''
         return self._files
 
     @propertycache
     def _dirs(self):
         return set(util.dirs(self._fmap)) | set(['.'])
 
     def visitdir(self, dir):
-        '''Helps while traversing a directory tree. Returns the string 'all' if
-        the given directory and all subdirectories should be visited. Otherwise
-        returns True or False indicating whether the given directory should be
-        visited. If 'all' is returned, calling this method on a subdirectory
-        gives an undefined result.'''
-        if not self._fmap or self.exact(dir):
-            return 'all'
-        return dir in self._dirs
+        return (not self._fmap or '.' in self._fmap or
+                dir in self._fmap or dir in self._dirs or
+                any(parentdir in self._fmap
+                    for parentdir in util.finddirs(dir)))
 
     def exact(self, f):
         '''Returns True if f is in .files().'''
         return f in self._fmap
 
     def anypats(self):
         '''Matcher uses patterns or include/exclude.'''
         return self._anypats
 
     def always(self):
         '''Matcher will match everything and .files() will be empty
         - optimization might be possible and necessary.'''
         return self._always
 
     def ispartial(self):
         '''True if the matcher won't always match.
 
         Although it's just the inverse of _always in this implementation,
         an extenion such as narrowhg might make it return something
         slightly different.'''
         return not self._always
 
     def isexact(self):
         return self.matchfn == self.exact
 
     def _normalize(self, patterns, default, root, cwd, auditor):
         '''Convert 'kind:pat' from the patterns list to tuples with kind and
         normalized and rooted patterns and with listfiles expanded.'''
         kindpats = []
         for kind, pat in [_patsplit(p, default) for p in patterns]:
             if kind in ('glob', 'relpath'):
                 pat = pathutil.canonpath(root, cwd, pat, auditor)
             elif kind in ('relglob', 'path'):
                 pat = util.normpath(pat)
             elif kind in ('listfile', 'listfile0'):
                 try:
                     files = util.readfile(pat)
                     if kind == 'listfile0':
                         files = files.split('\0')
                     else:
                         files = files.splitlines()
                     files = [f for f in files if f]
                 except EnvironmentError:
                     raise util.Abort(_("unable to read file list (%s)") % pat)
                 kindpats += self._normalize(files, default, root, cwd, auditor)
                 continue
             # else: re or relre - which cannot be normalized
             kindpats.append((kind, pat))
         return kindpats
 
 def exact(root, cwd, files):
     return match(root, cwd, files, exact=True)
 
 def always(root, cwd):
     return match(root, cwd, [])
 
 class narrowmatcher(match):
     """Adapt a matcher to work on a subdirectory only.
 
     The paths are remapped to remove/insert the path as needed:
 
     >>> m1 = match('root', '', ['a.txt', 'sub/b.txt'])
     >>> m2 = narrowmatcher('sub', m1)
     >>> bool(m2('a.txt'))
     False
     >>> bool(m2('b.txt'))
     True
     >>> bool(m2.matchfn('a.txt'))
     False
     >>> bool(m2.matchfn('b.txt'))
     True
     >>> m2.files()
     ['b.txt']
     >>> m2.exact('b.txt')
     True
     >>> util.pconvert(m2.rel('b.txt'))
     'sub/b.txt'
     >>> def bad(f, msg):
     ...     print "%s: %s" % (f, msg)
     >>> m1.bad = bad
     >>> m2.bad('x.txt', 'No such file')
     sub/x.txt: No such file
     >>> m2.abs('c.txt')
     'sub/c.txt'
     """
 
     def __init__(self, path, matcher):
         self._root = matcher._root
         self._cwd = matcher._cwd
         self._path = path
         self._matcher = matcher
         self._always = matcher._always
         self._pathrestricted = matcher._pathrestricted
 
         self._files = [f[len(path) + 1:] for f in matcher._files
                        if f.startswith(path + "/")]
         self._anypats = matcher._anypats
         self.matchfn = lambda fn: matcher.matchfn(self._path + "/" + fn)
         self._fmap = set(self._files)
 
     def abs(self, f):
         return self._matcher.abs(self._path + "/" + f)
 
     def bad(self, f, msg):
         self._matcher.bad(self._path + "/" + f, msg)
 
     def rel(self, f):
         return self._matcher.rel(self._path + "/" + f)
 
 class icasefsmatcher(match):
     """A matcher for wdir on case insensitive filesystems, which normalizes the
     given patterns to the case in the filesystem.
     """
 
     def __init__(self, root, cwd, patterns, include, exclude, default, auditor,
                  ctx, listsubrepos=False):
         init = super(icasefsmatcher, self).__init__
         self._dsnormalize = ctx.repo().dirstate.normalize
 
         init(root, cwd, patterns, include, exclude, default, auditor=auditor,
              ctx=ctx, listsubrepos=listsubrepos)
 
         # m.exact(file) must be based off of the actual user input, otherwise
         # inexact case matches are treated as exact, and not noted without -v.
         if self._files:
             self._fmap = set(_roots(self._kp))
 
     def _normalize(self, patterns, default, root, cwd, auditor):
         self._kp = super(icasefsmatcher, self)._normalize(patterns, default,
                                                           root, cwd, auditor)
         kindpats = []
         for kind, pats in self._kp:
             if kind not in ('re', 'relre'):  # regex can't be normalized
                 pats = self._dsnormalize(pats)
             kindpats.append((kind, pats))
         return kindpats
 
 def patkind(pattern, default=None):
     '''If pattern is 'kind:pat' with a known kind, return kind.'''
     return _patsplit(pattern, default)[0]
 
 def _patsplit(pattern, default):
     """Split a string into the optional pattern kind prefix and the actual
     pattern."""
     if ':' in pattern:
         kind, pat = pattern.split(':', 1)
         if kind in ('re', 'glob', 'path', 'relglob', 'relpath', 'relre',
                     'listfile', 'listfile0', 'set'):
             return kind, pat
     return default, pattern
 
 def _globre(pat):
     r'''Convert an extended glob string to a regexp string.
 
     >>> print _globre(r'?')
     .
     >>> print _globre(r'*')
     [^/]*
     >>> print _globre(r'**')
     .*
     >>> print _globre(r'**/a')
     (?:.*/)?a
     >>> print _globre(r'a/**/b')
     a\/(?:.*/)?b
     >>> print _globre(r'[a*?!^][^b][!c]')
     [a*?!^][\^b][^c]
     >>> print _globre(r'{a,b}')
     (?:a|b)
     >>> print _globre(r'.\*\?')
     \.\*\?
     '''
     i, n = 0, len(pat)
     res = ''
     group = 0
     escape = util.re.escape
     def peek():
         return i < n and pat[i]
     while i < n:
         c = pat[i]
         i += 1
         if c not in '*?[{},\\':
             res += escape(c)
         elif c == '*':
             if peek() == '*':
                 i += 1
                 if peek() == '/':
                     i += 1
                     res += '(?:.*/)?'
                 else:
                     res += '.*'
             else:
                 res += '[^/]*'
         elif c == '?':
             res += '.'
         elif c == '[':
             j = i
             if j < n and pat[j] in '!]':
                 j += 1
             while j < n and pat[j] != ']':
                 j += 1
             if j >= n:
                 res += '\\['
             else:
                 stuff = pat[i:j].replace('\\','\\\\')
                 i = j + 1
                 if stuff[0] == '!':
                     stuff = '^' + stuff[1:]
                 elif stuff[0] == '^':
                     stuff = '\\' + stuff
                 res = '%s[%s]' % (res, stuff)
         elif c == '{':
             group += 1
             res += '(?:'
         elif c == '}' and group:
             res += ')'
             group -= 1
         elif c == ',' and group:
             res += '|'
         elif c == '\\':
             p = peek()
             if p:
                 i += 1
                 res += escape(p)
             else:
                 res += escape(c)
         else:
             res += escape(c)
     return res
 
 def _regex(kind, pat, globsuffix):
     '''Convert a (normalized) pattern of any kind into a regular expression.
     globsuffix is appended to the regexp of globs.'''
     if not pat:
         return ''
     if kind == 're':
         return pat
     if kind == 'path':
         return '^' + util.re.escape(pat) + '(?:/|$)'
     if kind == 'relglob':
         return '(?:|.*/)' + _globre(pat) + globsuffix
     if kind == 'relpath':
         return util.re.escape(pat) + '(?:/|$)'
     if kind == 'relre':
         if pat.startswith('^'):
             return pat
         return '.*' + pat
     return _globre(pat) + globsuffix
 
 def _buildmatch(ctx, kindpats, globsuffix, listsubrepos):
     '''Return regexp string and a matcher function for kindpats.
     globsuffix is appended to the regexp of globs.'''
     fset, kindpats = _expandsets(kindpats, ctx, listsubrepos)
     if not kindpats:
         return "", fset.__contains__
 
     regex, mf = _buildregexmatch(kindpats, globsuffix)
     if fset:
         return regex, lambda f: f in fset or mf(f)
     return regex, mf
 
 def _buildregexmatch(kindpats, globsuffix):
     """Build a match function from a list of kinds and kindpats,
     return regexp string and a matcher function."""
     try:
         regex = '(?:%s)' % '|'.join([_regex(k, p, globsuffix)
                                      for (k, p) in kindpats])
         if len(regex) > 20000:
             raise OverflowError
         return regex, _rematcher(regex)
     except OverflowError:
         # We're using a Python with a tiny regex engine and we
         # made it explode, so we'll divide the pattern list in two
         # until it works
         l = len(kindpats)
         if l < 2:
             raise
         regexa, a = _buildregexmatch(kindpats[:l//2], globsuffix)
         regexb, b = _buildregexmatch(kindpats[l//2:], globsuffix)
         return regex, lambda s: a(s) or b(s)
     except re.error:
         for k, p in kindpats:
             try:
                 _rematcher('(?:%s)' % _regex(k, p, globsuffix))
             except re.error:
                 raise util.Abort(_("invalid pattern (%s): %s") % (k, p))
         raise util.Abort(_("invalid pattern"))
 
 def _roots(kindpats):
     '''return roots and exact explicitly listed files from patterns
 
     >>> _roots([('glob', 'g/*'), ('glob', 'g'), ('glob', 'g*')])
     ['g', 'g', '.']
     >>> _roots([('relpath', 'r'), ('path', 'p/p'), ('path', '')])
     ['r', 'p/p', '.']
     >>> _roots([('relglob', 'rg*'), ('re', 're/'), ('relre', 'rr')])
     ['.', '.', '.']
     '''
     r = []
     for kind, pat in kindpats:
         if kind == 'glob': # find the non-glob prefix
             root = []
             for p in pat.split('/'):
                 if '[' in p or '{' in p or '*' in p or '?' in p:
                     break
                 root.append(p)
             r.append('/'.join(root) or '.')
         elif kind in ('relpath', 'path'):
             r.append(pat or '.')
         else: # relglob, re, relre
             r.append('.')
     return r
 
 def _anypats(kindpats):
     for kind, pat in kindpats:
         if kind in ('glob', 're', 'relglob', 'relre', 'set'):
             return True
 
 _commentre = None
 
 def readpatternfile(filepath, warn):
     '''parse a pattern file, returning a list of
     patterns. These patterns should be given to compile()
     to be validated and converted into a match function.'''
     syntaxes = {'re': 'relre:', 'regexp': 'relre:', 'glob': 'relglob:'}
     syntax = 'relre:'
     patterns = []
 
     fp = open(filepath)
     for line in fp:
         if "#" in line:
             global _commentre
             if not _commentre:
                 _commentre = re.compile(r'((^|[^\\])(\\\\)*)#.*')
             # remove comments prefixed by an even number of escapes
             line = _commentre.sub(r'\1', line)
             # fixup properly escaped comments that survived the above
             line = line.replace("\\#", "#")
         line = line.rstrip()
         if not line:
             continue
 
         if line.startswith('syntax:'):
             s = line[7:].strip()
             try:
                 syntax = syntaxes[s]
             except KeyError:
                 warn(_("%s: ignoring invalid syntax '%s'\n") % (filepath, s))
             continue
 
         linesyntax = syntax
         for s, rels in syntaxes.iteritems():
             if line.startswith(rels):
                 linesyntax = rels
                 line = line[len(rels):]
                 break
             elif line.startswith(s+':'):
                 linesyntax = rels
                 line = line[len(s) + 1:]
                 break
         patterns.append(linesyntax + line)
     fp.close()
     return patterns