[MERGE] binary search for 'date:' revision

[Guillaume Pinot]

Guillaume Pinot <guillaume.pinot at tremplin-utc.net> writes:

> "Olaf Conradi" <oohlaf at gmail.com> writes:
> 
> > On 28/04/06, Guillaume Pinot <guillaume.pinot at tremplin-utc.net> wrote:
> > 
> > > I've changed the linear search for 'date:' revision to a binary
> > > search. It speedup commands like "bzr log -r date:yesterday" a
> > > lot.
> > >
> > > http://wwwlinux.utc.fr/~pinotgui/hack/bzr.dev.gp.binsearch/
> > 
> > Looks good, I like it (I also made a binsearch version, but using
> > bisect is better)
> > 
> > +1 if you add a NEWS entry
> 
> NEWS entry added.

I relanch this thread.

This patch speedup a lot revision date (5 min for bzr log -r
date:yesterday on bzr.dev, imediate with this patch).

I try to keep this branch mergable with bzr.dev. It's not up to date
merged, but it must merge without conflict.

What it the rule for the "+1" things?

Because it seems to be the desired way, here is the relevant patch
from the branch. (bzr diff -r -5..-2)

Thanks.

=== modified file 'a/NEWS'
--- a/NEWS      
+++ b/NEWS      
@@ -97,6 +97,8 @@
 
     * Hitting CTRL-C while doing an SFTP push will no longer cause
       stale locks
       to be left in the SFTP repository. (Robert Collins, Martin
       Pool).
+
+    * Speedup improvement for 'date:'-revision search. (Guillaume Pinot).
 
   CHANGES:
 

=== modified file 'a/bzrlib/revisionspec.py'
--- a/bzrlib/revisionspec.py    
+++ b/bzrlib/revisionspec.py    
@@ -17,6 +17,7 @@
 
 import datetime
 import re
+import bisect
 from bzrlib.errors import BzrError, NoSuchRevision, NoCommits
 
 _marker = []
@@ -248,6 +249,18 @@
 SPEC_TYPES.append(RevisionSpec_tag)
 
 
+class RevisionSpec_revs:
+    def __init__(self, revs, branch):
+        self.revs = revs
+        self.branch = branch
+    def __getitem__(self, index):
+        r = self.branch.repository.get_revision(self.revs[index])
+        # TODO: Handle timezone.
+        return datetime.datetime.fromtimestamp(r.timestamp)
+    def __len__(self):
+        return len(self.revs)
+
+
 class RevisionSpec_date(RevisionSpec):
     prefix = 'date:'
     _date_re = re.compile(
@@ -295,14 +308,12 @@
 
             dt = datetime.datetime(year=year, month=month, day=day,
                     hour=hour, minute=minute, second=second)
-        first = dt
-        for i in range(len(revs)):
-            r = branch.repository.get_revision(revs[i])
-            # TODO: Handle timezone.
-            dt = datetime.datetime.fromtimestamp(r.timestamp)
-            if first <= dt:
-                return RevisionInfo(branch, i+1)
-        return RevisionInfo(branch, None)
+
+        rev = bisect.bisect(RevisionSpec_revs(revs, branch), dt)
+        if rev == len(revs):
+            return RevisionInfo(branch, None)
+        else:
+            return RevisionInfo(branch, rev + 1)
 
 SPEC_TYPES.append(RevisionSpec_date)
 

=== modified file 'a/bzrlib/tests/test_revisionnamespaces.py'
--- a/bzrlib/tests/test_revisionnamespaces.py   
+++ b/bzrlib/tests/test_revisionnamespaces.py   
@@ -54,6 +54,8 @@
                           (1, 'a at r-0-1'))
         self.assertEquals(RevisionSpec('before:date:today').in_history(b),
                           (1, 'a at r-0-1'))
+        self.assertRaises(NoSuchRevision,
+                          RevisionSpec('date:tomorrow').in_history, b)
 
         self.assertEquals(RevisionSpec('last:1').in_history(b),
                           (3, 'a at r-0-3'))