From patchwork Thu Jun 22 15:52:18 2017
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: [5,of,7] dagop: compute depth in revancestors() generator
From: Yuya Nishihara <yuya@tcha.org>
X-Patchwork-Id: 21616
Message-Id: <59abcdd7c59336a5314e.1498146738@mimosa>
To: mercurial-devel@mercurial-scm.org
Date: Fri, 23 Jun 2017 00:52:18 +0900

# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1497712308 -32400
#      Sun Jun 18 00:11:48 2017 +0900
# Node ID 59abcdd7c59336a5314ec9b4b95075874c0d838f
# Parent  3b2bded55cfab4dd13079cbf1d0354c1462d5c18
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

diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -31,30 +31,32 @@ def _genrevancestors(repo, revs, followf
     # 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."""