# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1474537311 -32400
# Node ID c9144396099b0c40e3b39779d1ed55abcd1e7de3
# Parent  2cb05e6043be13002efcd1de7d2d426ee3b495d0
dagop: use heap to compute max rev in filectxancestors()

diff -r 2cb05e6043be -r c9144396099b mercurial/dagop.py
--- a/mercurial/dagop.py	Sun Oct 22 18:57:42 2017 +0900
+++ b/mercurial/dagop.py	Thu Sep 22 18:41:51 2016 +0900
@@ -82,10 +82,12 @@
     Yields (rev, {fctx, ...}) pairs in descending order.
     """
     visit = {}
+    visitheap = []
     def addvisit(fctx):
         rev = fctx.rev()
         if rev not in visit:
             visit[rev] = set()
+            heapq.heappush(visitheap, -rev)  # max heap
         visit[rev].add(fctx)
 
     if followfirst:
@@ -96,12 +98,13 @@
     for c in fctxs:
         addvisit(c)
     while visit:
-        currev = max(visit)
+        currev = -heapq.heappop(visitheap)
         curfctxs = visit.pop(currev)
         yield currev, curfctxs
         for c in curfctxs:
             for parent in c.parents()[:cut]:
                 addvisit(parent)
+    assert not visitheap
 
 def filerevancestors(fctxs, followfirst=False):
     """Like filectx.ancestors(), but can walk from multiple files/revisions,