commit: trade O(n^2) file checks for O(n^2) dir checks
authorMatt Mackall <mpm@selenic.com>
Mon, 01 Jun 2009 22:13:08 -0500
changeset 8710 bcb6e5bebd93
parent 8709 b9e0ddb04c5c
child 8711 1b95c6f13155
commit: trade O(n^2) file checks for O(n^2) dir checks
mercurial/localrepo.py
--- a/mercurial/localrepo.py	Mon Jun 01 21:51:00 2009 -0500
+++ b/mercurial/localrepo.py	Mon Jun 01 22:13:08 2009 -0500
@@ -808,17 +808,19 @@
 
             # make sure all explicit patterns are matched
             if not force and match.files():
-                files = sorted(changes[0] + changes[1] + changes[2])
+                matched = set(changes[0] + changes[1] + changes[2])
 
                 for f in match.files():
-                    if f == '.' or f in files: # matched
+                    if f == '.' or f in matched: # matched
                         continue
                     if f in changes[3]: # missing
                         fail(f, _('file not found!'))
                     if f in vdirs: # visited directory
                         d = f + '/'
-                        i = bisect.bisect(files, d)
-                        if i >= len(files) or not files[i].startswith(d):
+                        for mf in matched:
+                            if mf.startswith(d):
+                                break
+                        else:
                             fail(f, _("no match under directory!"))
                     elif f not in self.dirstate:
                         fail(f, _("file not tracked!"))