[PATCH 3 of 3] cmdutil: implemented new lazy increasingwindows

[Lucas Moscovicz]

# HG changeset patch
# User Lucas Moscovicz <lmoscovicz at fb.com>
# Date 1392330432 28800
#      Thu Feb 13 14:27:12 2014 -0800
# Node ID dbb13949e05d8c576672ea0a49a978048c77ddf7
# Parent  01e0d36c542521cea4569185506909c47df3d129
cmdutil: implemented new lazy increasingwindows

Now log can work in a lazy way and get results as soon as they are processed.

Performance Benchmarking:

$ time hg log -l1 -qr "branch(default)"
0:9117c6561b0b

real  0m2.303s
user  0m2.252s
sys 0m0.048s

$ time ./hg log -l1 -qr "branch(default)"
0:9117c6561b0b

real  0m0.238s
user  0m0.199s
sys 0m0.037s

diff --git a/mercurial/cmdutil.py b/mercurial/cmdutil.py
--- a/mercurial/cmdutil.py
+++ b/mercurial/cmdutil.py
@@ -995,19 +995,11 @@
 
     raise util.Abort(_("revision matching date not found"))
 
-def increasingwindows(start, end, windowsize=8, sizelimit=512):
-    if start < end:
-        while start < end:
-            yield start, min(windowsize, end - start)
-            start += windowsize
-            if windowsize < sizelimit:
-                windowsize *= 2
-    else:
-        while start > end:
-            yield start, min(windowsize, start - end - 1)
-            start -= windowsize
-            if windowsize < sizelimit:
-                windowsize *= 2
+def increasingwindows(windowsize=8, sizelimit=512):
+    while True:
+        yield windowsize
+        if windowsize < sizelimit:
+            windowsize *= 2
 
 class FileWalkError(Exception):
     pass
@@ -1140,7 +1132,6 @@
     slowpath = match.anypats() or (match.files() and opts.get('removed'))
     fncache = {}
     change = repo.changectx
-    revs = revset.baseset(revs)
 
     # First step is to fill wanted, the set of revisions that we want to yield.
     # When it does not induce extra cost, we also fill fncache for revisions in
@@ -1149,7 +1140,7 @@
 
     if not slowpath and not match.files():
         # No files, no patterns.  Display all revs.
-        wanted = set(revs)
+        wanted = revs
 
     if not slowpath and match.files():
         # We only have to read through the filelog to find wanted revisions
@@ -1251,14 +1242,7 @@
         stop = min(revs[0], revs[-1])
         for x in xrange(rev, stop - 1, -1):
             if ff.match(x):
-                wanted.discard(x)
-
-    # Choose a small initial window if we will probably only visit a
-    # few commits.
-    limit = loglimit(opts)
-    windowsize = 8
-    if limit:
-        windowsize = min(limit, windowsize)
+                wanted = wanted - [x]
 
     # Now that wanted is correctly initialized, we can iterate over the
     # revision range, yielding only revisions in wanted.
@@ -1271,8 +1255,18 @@
             def want(rev):
                 return rev in wanted
 
-        for i, window in increasingwindows(0, len(revs), windowsize):
-            nrevs = [rev for rev in revs[i:i + window] if want(rev)]
+        it = iter(revs)
+        stopiteration = False
+        for windowsize in increasingwindows():
+            nrevs = []
+            for i in xrange(windowsize):
+                try:
+                    rev = it.next()
+                    if want(rev):
+                        nrevs.append(rev)
+                except (StopIteration):
+                    stopiteration = True
+                    break
             for rev in sorted(nrevs):
                 fns = fncache.get(rev)
                 ctx = change(rev)
@@ -1285,6 +1279,10 @@
                 prepare(ctx, fns)
             for rev in nrevs:
                 yield change(rev)
+
+            if stopiteration:
+                break
+
     return iterate()
 
 def _makegraphfilematcher(repo, pats, followfirst):