# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 1243912388 18000
# Node ID bcb6e5bebd93162ce3059167ad5322932063746a
# Parent  b9e0ddb04c5cdf7a128aa4d9947832cc22030a14
commit: trade O(n^2) file checks for O(n^2) dir checks

diff -r b9e0ddb04c5c -r bcb6e5bebd93 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!"))