changeset 2087:0c2371542687

depth: update depth to code to reuse ancestors depth

Computing the depth of all N revs is no longer 'O(N**2)'

--- a/hgext3rd/evolve/obsdiscovery.py	Sat Mar 11 09:08:20 2017 -0800
+++ b/hgext3rd/evolve/obsdiscovery.py	Sat Mar 11 10:26:30 2017 -0800
@@ -485,6 +485,9 @@
     n = repo.changelog.node
     s = node.short
     revs = scmutil.revrange(repo, opts['rev'])
+    # prewarm depth cache
+    for r in repo.revs("::%ld", revs):
+        utility.depth(repo, r)
     toproceed = [_range(repo, r, 0, ) for r in revs]
     ranges = set(toproceed)
     while toproceed:
@@ -548,7 +551,7 @@
     @util.propertycache
     def _revs(self):
         r = _stablesort(self._repo, [self.head])[self.index:]
-        assert len(r) == len(self), (self.head, self.index)
+        assert len(r) == len(self), (self.head, self.index, len(r), len(self))
         return r
 
     def _slicesat(self, globalindex):

--- a/hgext3rd/evolve/utility.py	Sat Mar 11 09:08:20 2017 -0800
+++ b/hgext3rd/evolve/utility.py	Sat Mar 11 10:26:30 2017 -0800
@@ -32,7 +32,23 @@
         elif p2 == node.nullrev:
             revdepth = depth(repo, p1) + 1
         else:
-            # XXX we should just find the common ancestors
-            revdepth = len(list(cl.ancestors([rev], inclusive=True)))
+            ancs = cl.commonancestorsheads(cl.node(p1), cl.node(p2))
+            depth_p1 = depth(repo, p1)
+            depth_p2 = depth(repo, p2)
+            if not ancs:
+                revdepth = depth_p1 + depth_p2 + 1
+            elif len(ancs) == 1:
+                anc = cl.rev(ancs[0])
+                revdepth = depth_anc = depth(repo, anc)
+                revdepth += depth_p1 - depth_anc
+                revdepth += depth_p2 - depth_anc
+                revdepth += 1
+            else:
+                # multiple ancestors, we pick the highest and search all missing bits
+                anc = max(cl.rev(a) for a in ancs)
+                revdepth = depth(repo, anc)
+                revdepth += len(repo.revs('only(%d, %d)', rev, anc))
         _depthcache[n] = revdepth
+    # actual_depth = len(list(cl.ancestors([rev], inclusive=True)))
+    # assert revdepth == actual_depth, (rev, revdepth, actual_depth)
     return revdepth