--- a/doc/hg.1.txt
+++ b/doc/hg.1.txt
@@ -33,7 +33,8 @@ COMMAND ELEMENTS
 ----------------
 
 files ...::
-    indicates one or more filename or relative path filenames
+    indicates one or more filename or relative path filenames; see
+    "FILE NAME PATTERNS" for information on pattern matching
 
 path::
     indicates a path on the local machine
@@ -51,11 +52,14 @@ repository path::
 COMMANDS
 --------
 
-add [files ...]::
+add [options] [files ...]::
     Schedule files to be version controlled and added to the repository.
     
     The files will be added to the repository at the next commit.
 
+    If no names are given, add all files in the current directory and
+    its subdirectory.
+
 addremove::
     Add all new files and remove all missing files from the repository.
     
@@ -183,14 +187,10 @@ import [-p <n> -b <base> -q] <patches>::
 init::
     Initialize a new repository in the current directory.
 
-locate [options] [patterns]::
-    Print all files under Mercurial control whose basenames match the
+locate [options] [files]::
+    Print all files under Mercurial control whose names match the
     given patterns.
 
-    Patterns are shell-style globs.  To restrict searches to specific
-    directories, use the "-i <pat>" option.  To eliminate particular
-    directories from searching, use the "-x <pat>" option.
-
     This command searches the current directory and its
     subdirectories.  To search an entire repository, move to the root
     of the repository.
@@ -207,9 +207,9 @@ locate [options] [patterns]::
 
     -0, --print0         end filenames with NUL, for use with xargs
     -f, --fullpath       print complete paths from the filesystem root
-    -i, --include <pat>  include directories matching the given globs
+    -I, --include <pat>  include directories matching the given patterns
     -r, --rev <rev>      search the repository as it stood at rev
-    -x, --exclude <pat>  exclude directories matching the given globs
+    -X, --exclude <pat>  exclude directories matching the given patterns
 
 log [-r revision ...] [-p] [file]::
     Print the revision history of the specified file or the entire project.
@@ -398,6 +398,52 @@ verify::
     the changelog, manifest, and tracked files, as well as the
     integrity of their crosslinks and indices.
 
+FILE NAME PATTERNS
+------------------
+
+    Mercurial accepts several notations for identifying one or more
+    file at a time.
+
+    By default, Mercurial treats file names as shell-style extended
+    glob patterns.
+
+    Alternate pattern notations must be specified explicitly.
+
+    To use a plain path name without any pattern matching, start a
+    name with "path:".  These path names must match completely, from
+    the root of the current repository.
+
+    To use an extended glob, start a name with "glob:".  Globs are
+    rooted at the current directory; a glob such as "*.c" will match
+    files ending in ".c" in the current directory only.
+
+    The supported glob syntax extensions are "**" to match any string
+    across path separators, and "{a,b}" to mean "a or b".
+
+    To use a Perl/Python regular expression, start a name with "re:".
+    Regexp pattern matching is anchored at the root of the repository.
+
+    Plain examples:
+
+    path:foo/bar   a name bar in a directory named foo in the root of
+                   the repository
+    path:path:name a file or directory named "path:name"
+
+    Glob examples:
+
+    glob:*.c       any name ending in ".c" in the current directory
+    *.c            any name ending in ".c" in the current directory
+    **.c           any name ending in ".c" in the current directory, or
+                   any subdirectory
+    foo/*.c        any name ending in ".c" in the directory foo
+    foo/**.c       any name ending in ".c" in the directory foo, or any
+                   subdirectory
+
+    Regexp examples:
+
+    re:.*\.c$      any name ending in ".c", anywhere in the repsitory
+
+
 SPECIFYING SINGLE REVISIONS
 ---------------------------
 

--- a/mercurial/commands.py
+++ b/mercurial/commands.py
@@ -36,6 +36,39 @@ def relpath(repo, args):
                 for x in args]
     return args
 
+def matchpats(ui, cwd, pats = [], opts = {}):
+    head = ''
+    if opts.get('rootless'): head = '(?:.*/|)'
+    def reify(name, tail):
+        if name.startswith('re:'):
+            return name[3:]
+        elif name.startswith('glob:'):
+            return head + util.globre(name[5:], '', tail)
+        elif name.startswith('path:'):
+            return '^' + re.escape(name[5:]) + '$'
+        return head + util.globre(name, '', tail)
+    cwdsep = cwd + os.sep
+    def under(fn):
+        if not cwd or fn.startswith(cwdsep): return True
+    def matchfn(pats, tail, ifempty = util.always):
+        if not pats: return ifempty
+        pat = '(?:%s)' % '|'.join([reify(p, tail) for p in pats])
+        if cwd: pat = re.escape(cwd + os.sep) + pat
+        ui.debug('regexp: %s\n' % pat)
+        return re.compile(pat).match
+    patmatch = matchfn(pats, '$')
+    incmatch = matchfn(opts.get('include'), '(?:/|$)', under)
+    excmatch = matchfn(opts.get('exclude'), '(?:/|$)', util.never)
+    return lambda fn: (incmatch(fn) and not excmatch(fn) and
+                       (fn.endswith('/') or patmatch(fn)))
+
+def walk(repo, pats, opts):
+    cwd = repo.getcwd()
+    if cwd: c = len(cwd) + 1
+    for fn in repo.walk(match = matchpats(repo.ui, cwd, pats, opts)):
+        if cwd: yield fn, fn[c:]
+        else: yield fn, fn
+
 revrangesep = ':'
 
 def revrange(ui, repo, revs, revlog=None):
@@ -288,9 +321,17 @@ def help_(ui, cmd=None):
 
 # Commands start here, listed alphabetically
 
-def add(ui, repo, file1, *files):
+def add(ui, repo, *pats, **opts):
     '''add the specified files on the next commit'''
-    repo.add(relpath(repo, (file1,) + files))
+    names = []
+    q = dict(zip(pats, pats))
+    for abs, rel in walk(repo, pats, opts):
+        if rel in q or abs in q:
+            names.append(abs)
+        elif repo.dirstate.state(abs) == '?':
+            ui.status('adding %s\n' % rel)
+            names.append(abs)
+    repo.add(names)
 
 def addremove(ui, repo, *files):
     """add all new files, delete all missing files"""
@@ -669,46 +710,15 @@ def init(ui, source=None):
 
 def locate(ui, repo, *pats, **opts):
     """locate files matching specific patterns"""
-    if [p for p in pats if os.sep in p]:
-        ui.warn("error: patterns may not contain '%s'\n" % os.sep)
-        ui.warn("use '-i <dir>' instead\n")
-        sys.exit(1)
-    def compile(pats, head='^', tail=os.sep, on_empty=True):
-        if not pats:
-            class c:
-                def match(self, x):
-                    return on_empty
-            return c()
-        fnpats = [fnmatch.translate(os.path.normpath(os.path.normcase(p)))[:-1]
-                  for p in pats]
-        regexp = r'%s(?:%s)%s' % (head, '|'.join(fnpats), tail)
-        return re.compile(regexp)
-    exclude = compile(opts['exclude'], on_empty=False)
-    include = compile(opts['include'])
-    pat = compile(pats, head='', tail='$')
-    end = opts['print0'] and '\0' or '\n'
-    if opts['rev']:
-        node = repo.manifest.lookup(opts['rev'])
-    else:
-        node = repo.manifest.tip()
-    manifest = repo.manifest.read(node)
-    cwd = repo.getcwd()
-    cwd_plus = cwd and (cwd + os.sep)
-    found = []
-    for f in manifest:
-        f = os.path.normcase(f)
-        if exclude.match(f) or not(include.match(f) and
-                                   f.startswith(cwd_plus) and
-                                   pat.match(os.path.basename(f))):
-            continue
+    if opts['print0']: end = '\0'
+    else: end = '\n'
+    opts['rootless'] = True
+    for abs, rel in walk(repo, pats, opts):
+        if repo.dirstate.state(abs) == '?': continue
         if opts['fullpath']:
-            f = os.path.join(repo.root, f)
-        elif cwd:
-            f = f[len(cwd_plus):]
-        found.append(f)
-    found.sort()
-    for f in found:
-        ui.write(f, end)
+            ui.write(os.path.join(repo.root, abs), end)
+        else:
+            ui.write(rel, end)
 
 def log(ui, repo, f=None, **opts):
     """show the revision history of the repository or a single file"""
@@ -1087,7 +1097,10 @@ def verify(ui, repo):
 # Command options and aliases are listed here, alphabetically
 
 table = {
-    "^add": (add, [], "hg add [files]"),
+    "^add": (add,
+             [('I', 'include', [], 'include path in search'),
+              ('X', 'exclude', [], 'exclude path from search')],
+             "hg add [options] [files]"),
     "addremove": (addremove, [], "hg addremove [files]"),
     "^annotate":
         (annotate,
@@ -1139,9 +1152,9 @@ table = {
         (locate,
          [('0', 'print0', None, 'end records with NUL'),
           ('f', 'fullpath', None, 'print complete paths'),
-          ('i', 'include', [], 'include path in search'),
+          ('I', 'include', [], 'include path in search'),
           ('r', 'rev', '', 'revision'),
-          ('x', 'exclude', [], 'exclude path from search')],
+          ('X', 'exclude', [], 'exclude path from search')],
          'hg locate [options] [files]'),
     "^log|history":
         (log,

--- a/mercurial/hg.py
+++ b/mercurial/hg.py
@@ -13,9 +13,6 @@ demandload(globals(), "re lock urllib ur
 demandload(globals(), "tempfile httprangereader bdiff")
 demandload(globals(), "bisect select")
 
-def always(fn):
-    return True
-
 class filelog(revlog):
     def __init__(self, opener, path):
         revlog.__init__(self, opener,
@@ -416,7 +413,7 @@ class dirstate:
             st.write(e + f)
         self.dirty = 0
 
-    def walk(self, files = None, match = always):
+    def walk(self, files = None, match = util.always):
         self.read()
         dc = self.map.copy()
         # walk all files by default
@@ -454,7 +451,7 @@ class dirstate:
             if match(fn):
                 yield fn
 
-    def changes(self, files = None, match = always):
+    def changes(self, files = None, match = util.always):
         self.read()
         dc = self.map.copy()
         lookup, changed, added, unknown = [], [], [], []
@@ -840,12 +837,16 @@ class localrepository:
         if not self.hook("commit", node=hex(n)):
             return 1
 
-    def walk(self, rev = None, files = [], match = always):
-        if rev is None: fns = self.dirstate.walk(files, match)
-        else: fns = filter(match, self.manifest.read(rev))
+    def walk(self, node = None, files = [], match = util.always):
+        if node:
+            change = self.changelog.read(node)
+            fns = filter(match, self.manifest.read(change[0]))
+        else:
+            fns = self.dirstate.walk(files, match)
         for fn in fns: yield fn
 
-    def changes(self, node1 = None, node2 = None, files = [], match = always):
+    def changes(self, node1 = None, node2 = None, files = [],
+                match = util.always):
         mf2, u = None, []
 
         def fcmp(fn, mf):
@@ -922,7 +923,7 @@ class localrepository:
                 self.ui.warn("%s does not exist!\n" % f)
             elif not os.path.isfile(p):
                 self.ui.warn("%s not added: mercurial only supports files currently\n" % f)
-            elif self.dirstate.state(f) == 'n':
+            elif self.dirstate.state(f) in 'an':
                 self.ui.warn("%s already tracked!\n" % f)
             else:
                 self.dirstate.update([f], "a")

--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -6,6 +6,8 @@
 # of the GNU General Public License, incorporated herein by reference.
 
 import os, errno
+from demandload import *
+demandload(globals(), "re")
 
 def unique(g):
     seen = {}
@@ -29,6 +31,54 @@ def explain_exit(code):
         return "stopped by signal %d" % val, val
     raise ValueError("invalid exit code")
 
+def always(fn): return True
+def never(fn): return False
+
+def globre(pat, head = '^', tail = '$'):
+    "convert a glob pattern into a regexp"
+    i, n = 0, len(pat)
+    res = ''
+    group = False
+    def peek(): return i < n and pat[i]
+    while i < n:
+        c = pat[i]
+        i = i+1
+        if c == '*':
+            if peek() == '*':
+                i += 1
+                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 = True
+            res += '(?:'
+        elif c == '}' and group:
+            res += ')'
+            group = False
+        elif c == ',' and group:
+            res += '|'
+        else:
+            res += re.escape(c)
+    return head + res + tail
+
 def system(cmd, errprefix=None):
     """execute a shell command that must succeed"""
     rc = os.system(cmd)