--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -40,16 +40,30 @@ def relpath(repo, args):
     return args
 
 def matchpats(cwd, pats = [], opts = {}, head = ''):
-    return util.matcher(cwd, pats, opts.get('include'),
+    return util.matcher(cwd, pats or ['.'], opts.get('include'),
                         opts.get('exclude'), head)
 
+def pathto(n1, n2):
+    '''return the relative path from one place to another'''
+    if not n1: return n2
+    a, b = n1.split(os.sep), n2.split(os.sep)
+    a.reverse(), b.reverse()
+    while a and b and a[-1] == b[-1]:
+        a.pop(), b.pop()
+    b.reverse()
+    return os.sep.join((['..'] * len(a)) + b)
+
+def makewalk(repo, pats, opts, head = ''):
+    cwd = repo.getcwd()
+    files, matchfn = matchpats(cwd, pats, opts, head)
+    def walk():
+        for src, fn in repo.walk(files = files, match = matchfn):
+            yield src, fn, pathto(cwd, fn)
+    return files, matchfn, walk()
+
 def walk(repo, pats, opts, head = ''):
-    cwd = repo.getcwd()
-    c = 0
-    if cwd: c = len(cwd) + 1
-    files, matchfn = matchpats(cwd, pats, opts, head)
-    for src, fn in repo.walk(files = files, match = matchfn):
-        yield src, fn, fn[c:]
+    files, matchfn, results = makewalk(repo, pats, opts, head)
+    for r in results: yield r
 
 revrangesep = ':'
 
@@ -145,11 +159,11 @@ def make_file(repo, r, pat, node=None,
     return open(make_filename(repo, r, pat, node, total, seqno, revwidth),
                 mode)
 
-def dodiff(fp, ui, repo, files=None, node1=None, node2=None):
+def dodiff(fp, ui, repo, files=None, node1=None, node2=None, match=util.always):
     def date(c):
         return time.asctime(time.gmtime(float(c[2].split(' ')[0])))
 
-    (c, a, d, u) = repo.changes(node1, node2, files)
+    (c, a, d, u) = repo.changes(node1, node2, files, match = match)
     if files:
         c, a, d = map(lambda x: filterfiles(files, x), (c, a, d))
 
@@ -565,6 +579,11 @@ def debugindexdot(ui, file_):
             ui.write("\t%d -> %d\n" % (r.rev(e[5]), i))
     ui.write("}\n")
 
+def debugwalk(ui, repo, *pats, **opts):
+    items = list(walk(repo, pats, opts))
+    fmt = '%%s  %%-%ds  %%s' % max([len(abs) for (src, abs, rel) in items])
+    for i in items: print fmt % i
+
 def diff(ui, repo, *pats, **opts):
     """diff working directory (or selected files)"""
     revs = []
@@ -575,9 +594,10 @@ def diff(ui, repo, *pats, **opts):
         raise Abort("too many revisions to diff")
 
     files = []
-    for src, abs, rel in walk(repo, pats, opts):
+    roots, match, results = makewalk(repo, pats, opts)
+    for src, abs, rel in results:
         files.append(abs)
-    dodiff(sys.stdout, ui, repo, files, *revs)
+    dodiff(sys.stdout, ui, repo, files, *revs, **{'match': match})
 
 def doexport(ui, repo, changeset, seqno, total, revwidth, opts):
     node = repo.lookup(changeset)
@@ -1015,9 +1035,10 @@ def status(ui, repo, *pats, **opts):
     R = removed
     ? = not tracked'''
 
-    files, matchfn = matchpats(repo.getcwd(), pats, opts)
-    (c, a, d, u) = repo.changes(files = files, match = matchfn)
-    (c, a, d, u) = map(lambda x: relfilter(repo, x), (c, a, d, u))
+    cwd = repo.getcwd()
+    files, matchfn = matchpats(cwd, pats, opts)
+    (c, a, d, u) = [[pathto(cwd, x) for x in n]
+                    for n in repo.changes(files=files, match=matchfn)]
 
     for f in c:
         ui.write("M ", f, "\n")
@@ -1160,6 +1181,10 @@ table = {
     "debugstate": (debugstate, [], 'debugstate'),
     "debugindex": (debugindex, [], 'debugindex FILE'),
     "debugindexdot": (debugindexdot, [], 'debugindexdot FILE'),
+    "debugwalk": (debugwalk,
+                  [('I', 'include', [], 'include path in search'),
+                   ('X', 'exclude', [], 'exclude path from search')],
+                  'debugwalk [OPTIONS]... [FILE]...'),
     "^diff":
         (diff,
          [('r', 'rev', [], 'revision'),

--- a/mercurial/hg.py
+++ b/mercurial/hg.py
@@ -440,32 +440,43 @@ class dirstate:
         dc = self.map.copy()
         # walk all files by default
         if not files: files = [self.root]
+        known = {'.hg': 1}
+        def seen(fn):
+            if fn in known: return True
+            known[fn] = 1
         def traverse():
             for f in util.unique(files):
                 f = os.path.join(self.root, f)
                 if os.path.isdir(f):
                     for dir, subdirs, fl in os.walk(f):
                         d = dir[len(self.root) + 1:]
-                        if d == '.hg':
+                        nd = os.path.normpath(d)
+                        if seen(nd):
                             subdirs[:] = []
                             continue
                         for sd in subdirs:
-                            ds = os.path.join(d, sd +'/')
+                            ds = os.path.join(nd, sd +'/')
                             if self.ignore(ds) or not match(ds):
                                 subdirs.remove(sd)
+                        subdirs.sort()
+                        fl.sort()
                         for fn in fl:
                             fn = util.pconvert(os.path.join(d, fn))
                             yield 'f', fn
                 else:
                     yield 'f', f[len(self.root) + 1:]
 
-            for k in dc.keys():
+            ks = dc.keys()
+            ks.sort()
+            for k in ks:
                 yield 'm', k
 
         # yield only files that match: all in dirstate, others only if
         # not in .hgignore
 
         for src, fn in util.unique(traverse()):
+            fn = os.path.normpath(fn)
+            if seen(fn): continue
             if fn in dc:
                 del dc[fn]
             elif self.ignore(fn):
@@ -868,7 +879,7 @@ class localrepository:
     def walk(self, node = None, files = [], match = util.always):
         if node:
             for fn in self.manifest.read(self.changelog.read(node)[0]):
-                yield 'm', fn
+                if match(fn): yield 'm', fn
         else:
             for src, fn in self.dirstate.walk(files, match):
                 yield src, fn

--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -69,24 +69,27 @@ def globre(pat, head = '^', tail = '$'):
 _globchars = {'[': 1, '{': 1, '*': 1, '?': 1}
 
 def matcher(cwd, names, inc, exc, head = ''):
-    def patlike(name):
+    def patkind(name):
         for prefix in 're:', 'glob:', 'path:':
-            if name.startswith(prefix): return True
+            if name.startswith(prefix): return name.split(':', 1)
         for c in name:
-            if c in _globchars: return True
+            if c in _globchars: return 'glob', name
+        return 'relpath', name
+
+    cwdsep = cwd + os.sep
 
     def regex(name, tail):
         '''convert a pattern into a regular expression'''
-        if name.startswith('re:'):
-            return name[3:]
-        elif name.startswith('path:'):
-            return '^' + re.escape(name[5:]) + '$'
-        elif name.startswith('glob:'):
-            return head + globre(name[5:], '', tail)
+        kind, name = patkind(name)
+        if kind == 're':
+            return name
+        elif kind == 'path':
+            return '^' + re.escape(name) + '$'
+        if cwd: name = os.path.join(cwdsep, name)
+        name = os.path.normpath(name)
+        if name == '.': name = '**'
         return head + globre(name, '', tail)
 
-    cwdsep = cwd + os.sep
-
     def under(fn):
         """check if fn is under our cwd"""
         return not cwd or fn.startswith(cwdsep)
@@ -95,22 +98,28 @@ def matcher(cwd, names, inc, exc, head =
         """build a matching function from a set of patterns"""
         if pats:
             pat = '(?:%s)' % '|'.join([regex(p, tail) for p in pats])
-            if cwd:
-                pat = re.escape(cwdsep) + pat
             return re.compile(pat).match
 
-    pats = filter(patlike, names)
-    files = [n for n in names if not patlike(n)]
-    if pats: plain = []
-    elif cwd: plain = [cwdsep + f for f in files]
-    else: plain = files
+    def globprefix(pat):
+        '''return the non-glob prefix of a path, e.g. foo/* -> foo'''
+        root = []
+        for p in pat.split(os.sep):
+            if patkind(p)[0] == 'glob': break
+            root.append(p)
+        return os.sep.join(root)
+
+    patkinds = map(patkind, names)
+    pats = [name for (kind, name) in patkinds if kind != 'relpath']
+    files = [name for (kind, name) in patkinds if kind == 'relpath']
+    roots = filter(None, map(globprefix, pats)) + files
+    if cwd: roots = [cwdsep + r for r in roots]
         
-    patmatch = matchfn(pats, '$')
-    filematch = matchfn(files, '(?:/|$)')
-    incmatch = matchfn(inc, '(?:/|$)') or under
+    patmatch = matchfn(pats, '$') or always
+    filematch = matchfn(files, '(?:/|$)') or always
+    incmatch = matchfn(inc, '(?:/|$)') or always
     excmatch = matchfn(exc, '(?:/|$)') or (lambda fn: False)
 
-    return plain, lambda fn: (incmatch(fn) and not excmatch(fn) and
+    return roots, lambda fn: (incmatch(fn) and not excmatch(fn) and
                               (fn.endswith('/') or
                                (not pats and not files) or
                                (pats and patmatch(fn)) or

--- a/tests/test-merge5.out
+++ b/tests/test-merge5.out
@@ -9,4 +9,4 @@ removing b
 this update spans a branch affecting the following files:
  b
 aborting update spanning branches!
-(use update -m to perform a branch merge)
+(use update -m to merge across branches or -C to lose changes)