dagop: compute depth in revancestors() generator
authorYuya Nishihara <yuya@tcha.org>
Sun, 18 Jun 2017 00:11:48 +0900
changeset 33017 92d0945a15e0
parent 33016 d3d36bcdf036
child 33018 272a44cac57e
dagop: compute depth in revancestors() generator Surprisingly, this makes revset benchmark slightly faster. I don't know why, but it appears that wrapping -inputrev by tuple is the key. So I decided to just enable depth computation by default. # reverse(ancestors(tip)) using hg repo 1) 0.081051 2) 0.075408
mercurial/dagop.py
--- a/mercurial/dagop.py	Sun Jun 18 08:59:09 2017 +0900
+++ b/mercurial/dagop.py	Sun Jun 18 00:11:48 2017 +0900
@@ -31,30 +31,32 @@
     # without fully computing the input revs
     revs.sort(reverse=True)
     irevs = iter(revs)
-    pendingheap = []
+    pendingheap = []  # [(-rev, depth), ...] (i.e. lower depth first)
 
     inputrev = next(irevs, None)
     if inputrev is not None:
-        heapq.heappush(pendingheap, -inputrev)
+        heapq.heappush(pendingheap, (-inputrev, 0))
 
     lastrev = None
     while pendingheap:
-        currev = -heapq.heappop(pendingheap)
+        currev, curdepth = heapq.heappop(pendingheap)
+        currev = -currev
         if currev == inputrev:
             inputrev = next(irevs, None)
             if inputrev is not None:
-                heapq.heappush(pendingheap, -inputrev)
+                heapq.heappush(pendingheap, (-inputrev, 0))
         if currev != lastrev:
             lastrev = currev
             yield currev
+            pdepth = curdepth + 1
             try:
                 for prev in cl.parentrevs(currev)[:cut]:
                     if prev != node.nullrev:
-                        heapq.heappush(pendingheap, -prev)
+                        heapq.heappush(pendingheap, (-prev, pdepth))
             except error.WdirUnsupported:
                 for pctx in repo[currev].parents()[:cut]:
                     if pctx.rev() != node.nullrev:
-                        heapq.heappush(pendingheap, -pctx.rev())
+                        heapq.heappush(pendingheap, (-pctx.rev(), pdepth))
 
 def revancestors(repo, revs, followfirst):
     """Like revlog.ancestors(), but supports followfirst."""