diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -228,12 +228,18 @@ def matchpats(repo, pats=[], opts={}, gl
         pats = util.expand_glob(pats or [])
     m = match.match(repo.root, repo.getcwd(), pats, opts.get('include'),
                     opts.get('exclude'), default)
+    def badfn(f, msg):
+        repo.ui.warn("%s: %s\n" % (m.rel(f), msg))
+        return False
+    m.bad = badfn
     return m.files(), m, m.anypats()
 
 def walk(repo, pats=[], opts={}, node=None, badmatch=None, globbed=False,
          default='relpath'):
     dummy, m, dummy = matchpats(repo, pats, opts, globbed, default)
-    for src, fn in repo.walk(node, m, badmatch):
+    if badmatch:
+        m.bad = badmatch
+    for src, fn in repo.walk(node, m):
         yield src, fn, m.rel(fn), m.exact(fn)
 
 def findrenames(repo, added=None, removed=None, threshold=0.5):
diff --git a/mercurial/commands.py b/mercurial/commands.py
--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -32,7 +32,7 @@ def add(ui, repo, *pats, **opts):
     exacts = {}
     names = []
     for src, abs, rel, exact in cmdutil.walk(repo, pats, opts,
-                                             badmatch=util.always):
+                                             badmatch=lambda x,y: True):
         if exact:
             if ui.verbose:
                 ui.status(_('adding %s\n') % rel)
@@ -1696,7 +1696,7 @@ def locate(ui, repo, *pats, **opts):
 
     ret = 1
     for src, abs, rel, exact in cmdutil.walk(repo, pats, opts, node=node,
-                                             badmatch=util.always,
+                                             badmatch=lambda x,y: True,
                                              default='relglob'):
         if src == 'b':
             continue
diff --git a/mercurial/dirstate.py b/mercurial/dirstate.py
--- a/mercurial/dirstate.py
+++ b/mercurial/dirstate.py
@@ -416,14 +416,13 @@ class dirstate(object):
                 return True
         return False
 
-    def walk(self, match, badmatch):
+    def walk(self, match):
         # filter out the stat
-        for src, f, st in self.statwalk(match.files(), match,
-                                        badmatch=badmatch):
+        for src, f, st in self.statwalk(match.files(), match, badfn=match.bad):
             yield src, f
 
     def statwalk(self, files, match, unknown=True,
-                 ignored=False, badmatch=None, directories=False):
+                 ignored=False, badfn=None, directories=False):
         '''
         walk recursively through the directory tree, finding all files
         matched by the match function
@@ -433,11 +432,16 @@ class dirstate(object):
         'f' the file was found in the directory tree
         'd' the file is a directory of the tree
         'm' the file was only in the dirstate and not in the tree
-        'b' file was not found and matched badmatch
+        'b' file was not found and did not match badfn
 
         and st is the stat result if the file was found in the directory.
         '''
 
+        def fwarn(f, msg):
+            self._ui.warn('%s: %s\n' % (self.pathto(ff), msg))
+            return False
+        badfn = badfn or fwarn
+
         # walk all files by default
         if not files:
             files = ['.']
@@ -536,10 +540,9 @@ class dirstate(object):
                         found = True
                         break
                 if not found:
-                    if inst.errno != errno.ENOENT or not badmatch:
-                        self._ui.warn('%s: %s\n' %
-                                      (self.pathto(ff), inst.strerror))
-                    elif badmatch and badmatch(ff) and imatch(nf):
+                    if inst.errno != errno.ENOENT:
+                        fwarn(ff, inst.strerror)
+                    elif badfn(ff, inst.strerror) and imatch(nf):
                         yield 'b', ff, None
                 continue
             if s_isdir(st.st_mode):
diff --git a/mercurial/localrepo.py b/mercurial/localrepo.py
--- a/mercurial/localrepo.py
+++ b/mercurial/localrepo.py
@@ -931,7 +931,7 @@ class localrepository(repo.repository):
                 self.dirstate.invalidate()
             del tr, lock, wlock
 
-    def walk(self, node, match, badmatch):
+    def walk(self, node, match):
         '''
         walk recursively through the directory tree or a given
         changeset, finding all files matched by the match
@@ -963,14 +963,11 @@ class localrepository(repo.repository):
             ffiles = fdict.keys()
             ffiles.sort()
             for fn in ffiles:
-                if badmatch and badmatch(fn):
-                    if match(fn):
-                        yield 'b', fn
-                else:
-                    self.ui.warn(_('%s: No such file in rev %s\n')
-                                 % (self.pathto(fn), short(node)))
+                if match.bad(fn, 'No such file in rev ' + short(node)) \
+                        and match(fn):
+                    yield 'b', fn
         else:
-            for src, fn in self.dirstate.walk(match, badmatch):
+            for src, fn in self.dirstate.walk(match):
                 yield src, fn
 
     def status(self, node1=None, node2=None, files=[], match=util.always,
diff --git a/mercurial/match.py b/mercurial/match.py
--- a/mercurial/match.py
+++ b/mercurial/match.py
@@ -7,9 +7,8 @@ class match(object):
         self._cwd = cwd
         self._include = include
         self._exclude = exclude
-        f, mf, ap = util.matcher(self._root, self._cwd, self._patterns,
-                                 self._include, self._exclude, self.src(),
-                                 default)
+        f, mf, ap = util.matcher(root, cwd, patterns, include, exclude,
+                                 self.src(), default)
         self._files = f
         self._fmap = dict.fromkeys(f)
         self._matchfn = mf