Comments
Patch
@@ -6,7 +6,7 @@
# GNU General Public License version 2 or any later version.
import re
-import parser, util, error, discovery, hbisect, phases
+import parser, util, error, discovery, hbisect, phases, heapq
import node
import match as matchmod
from i18n import _
@@ -19,14 +19,23 @@
"""Like revlog.ancestors(), but supports followfirst."""
cut = followfirst and 1 or None
cl = repo.changelog
- visit = util.deque(revs)
+
+ # Implementation to be changed in later patches based on revs order.
+ h = list(revs)
+ for i in xrange(len(h)):
+ h[i] = -h[i]
+ heapq.heapify(h)
seen = set([node.nullrev])
- while visit:
- for parent in cl.parentrevs(visit.popleft())[:cut]:
- if parent not in seen:
- visit.append(parent)
- seen.add(parent)
- yield parent
+ def iterate():
+ while h:
+ current = -heapq.heappop(h)
+ if current not in seen:
+ seen.add(current)
+ yield current
+ for parent in cl.parentrevs(current)[:cut]:
+ heapq.heappush(h, -parent)
+
+ return descgeneratorset(iterate())
def _revdescendants(repo, revs, followfirst):
"""Like revlog.descendants() but supports followfirst."""
@@ -309,7 +318,7 @@
repo.changelog.filteredrevs), x)
if not args:
return baseset([])
- s = set(_revancestors(repo, args, followfirst)) | set(args)
+ s = _revancestors(repo, args, followfirst)
return subset.filter(lambda r: r in s)
def ancestors(repo, subset, x):
@@ -765,7 +774,7 @@
else:
return baseset([])
else:
- s = set(_revancestors(repo, [c.rev()], followfirst)) | set([c.rev()])
+ s = _revancestors(repo, baseset([c.rev()]), followfirst)
return baseset([r for r in subset if r in s])