--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mercurial/dagop.py Sun Oct 16 18:03:24 2016 +0900
@@ -0,0 +1,339 @@
+# dagop.py - graph ancestry and topology algorithm for revset
+#
+# Copyright 2010 Matt Mackall <mpm@selenic.com>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+from __future__ import absolute_import
+
+import heapq
+
+from . import (
+ error,
+ node,
+ smartset,
+)
+
+baseset = smartset.baseset
+generatorset = smartset.generatorset
+
+def revancestors(repo, revs, followfirst):
+ """Like revlog.ancestors(), but supports followfirst."""
+ if followfirst:
+ cut = 1
+ else:
+ cut = None
+ cl = repo.changelog
+
+ def iterate():
+ revs.sort(reverse=True)
+ irevs = iter(revs)
+ h = []
+
+ inputrev = next(irevs, None)
+ if inputrev is not None:
+ heapq.heappush(h, -inputrev)
+
+ seen = set()
+ while h:
+ current = -heapq.heappop(h)
+ if current == inputrev:
+ inputrev = next(irevs, None)
+ if inputrev is not None:
+ heapq.heappush(h, -inputrev)
+ if current not in seen:
+ seen.add(current)
+ yield current
+ try:
+ for parent in cl.parentrevs(current)[:cut]:
+ if parent != node.nullrev:
+ heapq.heappush(h, -parent)
+ except error.WdirUnsupported:
+ for parent in repo[current].parents()[:cut]:
+ if parent.rev() != node.nullrev:
+ heapq.heappush(h, -parent.rev())
+
+ return generatorset(iterate(), iterasc=False)
+
+def revdescendants(repo, revs, followfirst):
+ """Like revlog.descendants() but supports followfirst."""
+ if followfirst:
+ cut = 1
+ else:
+ cut = None
+
+ def iterate():
+ cl = repo.changelog
+ # XXX this should be 'parentset.min()' assuming 'parentset' is a
+ # smartset (and if it is not, it should.)
+ first = min(revs)
+ nullrev = node.nullrev
+ if first == nullrev:
+ # Are there nodes with a null first parent and a non-null
+ # second one? Maybe. Do we care? Probably not.
+ for i in cl:
+ yield i
+ else:
+ seen = set(revs)
+ for i in cl.revs(first + 1):
+ for x in cl.parentrevs(i)[:cut]:
+ if x != nullrev and x in seen:
+ seen.add(i)
+ yield i
+ break
+
+ return generatorset(iterate(), iterasc=True)
+
+def _reachablerootspure(repo, minroot, roots, heads, includepath):
+ """return (heads(::<roots> and ::<heads>))
+
+ If includepath is True, return (<roots>::<heads>)."""
+ if not roots:
+ return []
+ parentrevs = repo.changelog.parentrevs
+ roots = set(roots)
+ visit = list(heads)
+ reachable = set()
+ seen = {}
+ # prefetch all the things! (because python is slow)
+ reached = reachable.add
+ dovisit = visit.append
+ nextvisit = visit.pop
+ # open-code the post-order traversal due to the tiny size of
+ # sys.getrecursionlimit()
+ while visit:
+ rev = nextvisit()
+ if rev in roots:
+ reached(rev)
+ if not includepath:
+ continue
+ parents = parentrevs(rev)
+ seen[rev] = parents
+ for parent in parents:
+ if parent >= minroot and parent not in seen:
+ dovisit(parent)
+ if not reachable:
+ return baseset()
+ if not includepath:
+ return reachable
+ for rev in sorted(seen):
+ for parent in seen[rev]:
+ if parent in reachable:
+ reached(rev)
+ return reachable
+
+def reachableroots(repo, roots, heads, includepath=False):
+ """return (heads(::<roots> and ::<heads>))
+
+ If includepath is True, return (<roots>::<heads>)."""
+ if not roots:
+ return baseset()
+ minroot = roots.min()
+ roots = list(roots)
+ heads = list(heads)
+ try:
+ revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
+ except AttributeError:
+ revs = _reachablerootspure(repo, minroot, roots, heads, includepath)
+ revs = baseset(revs)
+ revs.sort()
+ return revs
+
+def toposort(revs, parentsfunc, firstbranch=()):
+ """Yield revisions from heads to roots one (topo) branch at a time.
+
+ This function aims to be used by a graph generator that wishes to minimize
+ the number of parallel branches and their interleaving.
+
+ Example iteration order (numbers show the "true" order in a changelog):
+
+ o 4
+ |
+ o 1
+ |
+ | o 3
+ | |
+ | o 2
+ |/
+ o 0
+
+ Note that the ancestors of merges are understood by the current
+ algorithm to be on the same branch. This means no reordering will
+ occur behind a merge.
+ """
+
+ ### Quick summary of the algorithm
+ #
+ # This function is based around a "retention" principle. We keep revisions
+ # in memory until we are ready to emit a whole branch that immediately
+ # "merges" into an existing one. This reduces the number of parallel
+ # branches with interleaved revisions.
+ #
+ # During iteration revs are split into two groups:
+ # A) revision already emitted
+ # B) revision in "retention". They are stored as different subgroups.
+ #
+ # for each REV, we do the following logic:
+ #
+ # 1) if REV is a parent of (A), we will emit it. If there is a
+ # retention group ((B) above) that is blocked on REV being
+ # available, we emit all the revisions out of that retention
+ # group first.
+ #
+ # 2) else, we'll search for a subgroup in (B) awaiting for REV to be
+ # available, if such subgroup exist, we add REV to it and the subgroup is
+ # now awaiting for REV.parents() to be available.
+ #
+ # 3) finally if no such group existed in (B), we create a new subgroup.
+ #
+ #
+ # To bootstrap the algorithm, we emit the tipmost revision (which
+ # puts it in group (A) from above).
+
+ revs.sort(reverse=True)
+
+ # Set of parents of revision that have been emitted. They can be considered
+ # unblocked as the graph generator is already aware of them so there is no
+ # need to delay the revisions that reference them.
+ #
+ # If someone wants to prioritize a branch over the others, pre-filling this
+ # set will force all other branches to wait until this branch is ready to be
+ # emitted.
+ unblocked = set(firstbranch)
+
+ # list of groups waiting to be displayed, each group is defined by:
+ #
+ # (revs: lists of revs waiting to be displayed,
+ # blocked: set of that cannot be displayed before those in 'revs')
+ #
+ # The second value ('blocked') correspond to parents of any revision in the
+ # group ('revs') that is not itself contained in the group. The main idea
+ # of this algorithm is to delay as much as possible the emission of any
+ # revision. This means waiting for the moment we are about to display
+ # these parents to display the revs in a group.
+ #
+ # This first implementation is smart until it encounters a merge: it will
+ # emit revs as soon as any parent is about to be emitted and can grow an
+ # arbitrary number of revs in 'blocked'. In practice this mean we properly
+ # retains new branches but gives up on any special ordering for ancestors
+ # of merges. The implementation can be improved to handle this better.
+ #
+ # The first subgroup is special. It corresponds to all the revision that
+ # were already emitted. The 'revs' lists is expected to be empty and the
+ # 'blocked' set contains the parents revisions of already emitted revision.
+ #
+ # You could pre-seed the <parents> set of groups[0] to a specific
+ # changesets to select what the first emitted branch should be.
+ groups = [([], unblocked)]
+ pendingheap = []
+ pendingset = set()
+
+ heapq.heapify(pendingheap)
+ heappop = heapq.heappop
+ heappush = heapq.heappush
+ for currentrev in revs:
+ # Heap works with smallest element, we want highest so we invert
+ if currentrev not in pendingset:
+ heappush(pendingheap, -currentrev)
+ pendingset.add(currentrev)
+ # iterates on pending rev until after the current rev have been
+ # processed.
+ rev = None
+ while rev != currentrev:
+ rev = -heappop(pendingheap)
+ pendingset.remove(rev)
+
+ # Seek for a subgroup blocked, waiting for the current revision.
+ matching = [i for i, g in enumerate(groups) if rev in g[1]]
+
+ if matching:
+ # The main idea is to gather together all sets that are blocked
+ # on the same revision.
+ #
+ # Groups are merged when a common blocking ancestor is
+ # observed. For example, given two groups:
+ #
+ # revs [5, 4] waiting for 1
+ # revs [3, 2] waiting for 1
+ #
+ # These two groups will be merged when we process
+ # 1. In theory, we could have merged the groups when
+ # we added 2 to the group it is now in (we could have
+ # noticed the groups were both blocked on 1 then), but
+ # the way it works now makes the algorithm simpler.
+ #
+ # We also always keep the oldest subgroup first. We can
+ # probably improve the behavior by having the longest set
+ # first. That way, graph algorithms could minimise the length
+ # of parallel lines their drawing. This is currently not done.
+ targetidx = matching.pop(0)
+ trevs, tparents = groups[targetidx]
+ for i in matching:
+ gr = groups[i]
+ trevs.extend(gr[0])
+ tparents |= gr[1]
+ # delete all merged subgroups (except the one we kept)
+ # (starting from the last subgroup for performance and
+ # sanity reasons)
+ for i in reversed(matching):
+ del groups[i]
+ else:
+ # This is a new head. We create a new subgroup for it.
+ targetidx = len(groups)
+ groups.append(([], {rev}))
+
+ gr = groups[targetidx]
+
+ # We now add the current nodes to this subgroups. This is done
+ # after the subgroup merging because all elements from a subgroup
+ # that relied on this rev must precede it.
+ #
+ # we also update the <parents> set to include the parents of the
+ # new nodes.
+ if rev == currentrev: # only display stuff in rev
+ gr[0].append(rev)
+ gr[1].remove(rev)
+ parents = [p for p in parentsfunc(rev) if p > node.nullrev]
+ gr[1].update(parents)
+ for p in parents:
+ if p not in pendingset:
+ pendingset.add(p)
+ heappush(pendingheap, -p)
+
+ # Look for a subgroup to display
+ #
+ # When unblocked is empty (if clause), we were not waiting for any
+ # revisions during the first iteration (if no priority was given) or
+ # if we emitted a whole disconnected set of the graph (reached a
+ # root). In that case we arbitrarily take the oldest known
+ # subgroup. The heuristic could probably be better.
+ #
+ # Otherwise (elif clause) if the subgroup is blocked on
+ # a revision we just emitted, we can safely emit it as
+ # well.
+ if not unblocked:
+ if len(groups) > 1: # display other subset
+ targetidx = 1
+ gr = groups[1]
+ elif not gr[1] & unblocked:
+ gr = None
+
+ if gr is not None:
+ # update the set of awaited revisions with the one from the
+ # subgroup
+ unblocked |= gr[1]
+ # output all revisions in the subgroup
+ for r in gr[0]:
+ yield r
+ # delete the subgroup that you just output
+ # unless it is groups[0] in which case you just empty it.
+ if targetidx:
+ del groups[targetidx]
+ else:
+ gr[0][:] = []
+ # Check if we have some subgroup waiting for revisions we are not going to
+ # iterate over
+ for g in groups:
+ for r in g[0]:
+ yield r
--- a/mercurial/revset.py Thu Jun 15 17:14:53 2017 -0700
+++ b/mercurial/revset.py Sun Oct 16 18:03:24 2016 +0900
@@ -7,11 +7,11 @@
from __future__ import absolute_import
-import heapq
import re
from .i18n import _
from . import (
+ dagop,
destutil,
encoding,
error,
@@ -49,128 +49,6 @@
spanset = smartset.spanset
fullreposet = smartset.fullreposet
-def _revancestors(repo, revs, followfirst):
- """Like revlog.ancestors(), but supports followfirst."""
- if followfirst:
- cut = 1
- else:
- cut = None
- cl = repo.changelog
-
- def iterate():
- revs.sort(reverse=True)
- irevs = iter(revs)
- h = []
-
- inputrev = next(irevs, None)
- if inputrev is not None:
- heapq.heappush(h, -inputrev)
-
- seen = set()
- while h:
- current = -heapq.heappop(h)
- if current == inputrev:
- inputrev = next(irevs, None)
- if inputrev is not None:
- heapq.heappush(h, -inputrev)
- if current not in seen:
- seen.add(current)
- yield current
- try:
- for parent in cl.parentrevs(current)[:cut]:
- if parent != node.nullrev:
- heapq.heappush(h, -parent)
- except error.WdirUnsupported:
- for parent in repo[current].parents()[:cut]:
- if parent.rev() != node.nullrev:
- heapq.heappush(h, -parent.rev())
-
- return generatorset(iterate(), iterasc=False)
-
-def _revdescendants(repo, revs, followfirst):
- """Like revlog.descendants() but supports followfirst."""
- if followfirst:
- cut = 1
- else:
- cut = None
-
- def iterate():
- cl = repo.changelog
- # XXX this should be 'parentset.min()' assuming 'parentset' is a
- # smartset (and if it is not, it should.)
- first = min(revs)
- nullrev = node.nullrev
- if first == nullrev:
- # Are there nodes with a null first parent and a non-null
- # second one? Maybe. Do we care? Probably not.
- for i in cl:
- yield i
- else:
- seen = set(revs)
- for i in cl.revs(first + 1):
- for x in cl.parentrevs(i)[:cut]:
- if x != nullrev and x in seen:
- seen.add(i)
- yield i
- break
-
- return generatorset(iterate(), iterasc=True)
-
-def _reachablerootspure(repo, minroot, roots, heads, includepath):
- """return (heads(::<roots> and ::<heads>))
-
- If includepath is True, return (<roots>::<heads>)."""
- if not roots:
- return []
- parentrevs = repo.changelog.parentrevs
- roots = set(roots)
- visit = list(heads)
- reachable = set()
- seen = {}
- # prefetch all the things! (because python is slow)
- reached = reachable.add
- dovisit = visit.append
- nextvisit = visit.pop
- # open-code the post-order traversal due to the tiny size of
- # sys.getrecursionlimit()
- while visit:
- rev = nextvisit()
- if rev in roots:
- reached(rev)
- if not includepath:
- continue
- parents = parentrevs(rev)
- seen[rev] = parents
- for parent in parents:
- if parent >= minroot and parent not in seen:
- dovisit(parent)
- if not reachable:
- return baseset()
- if not includepath:
- return reachable
- for rev in sorted(seen):
- for parent in seen[rev]:
- if parent in reachable:
- reached(rev)
- return reachable
-
-def reachableroots(repo, roots, heads, includepath=False):
- """return (heads(::<roots> and ::<heads>))
-
- If includepath is True, return (<roots>::<heads>)."""
- if not roots:
- return baseset()
- minroot = roots.min()
- roots = list(roots)
- heads = list(heads)
- try:
- revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
- except AttributeError:
- revs = _reachablerootspure(repo, minroot, roots, heads, includepath)
- revs = baseset(revs)
- revs.sort()
- return revs
-
# helpers
def getset(repo, subset, x):
@@ -242,8 +120,8 @@
def dagrange(repo, subset, x, y, order):
r = fullreposet(repo)
- xs = reachableroots(repo, getset(repo, r, x), getset(repo, r, y),
- includepath=True)
+ xs = dagop.reachableroots(repo, getset(repo, r, x), getset(repo, r, y),
+ includepath=True)
return subset & xs
def andset(repo, subset, x, y, order):
@@ -364,7 +242,7 @@
heads = getset(repo, fullreposet(repo), x)
if not heads:
return baseset()
- s = _revancestors(repo, heads, followfirst)
+ s = dagop.revancestors(repo, heads, followfirst)
return subset & s
@predicate('ancestors(set)', safe=True)
@@ -697,7 +575,7 @@
roots = getset(repo, fullreposet(repo), x)
if not roots:
return baseset()
- s = _revdescendants(repo, roots, followfirst)
+ s = dagop.revdescendants(repo, roots, followfirst)
# Both sets need to be ascending in order to lazily return the union
# in the correct order.
@@ -916,7 +794,7 @@
# include the revision responsible for the most recent version
s.add(fctx.introrev())
else:
- s = _revancestors(repo, baseset([c.rev()]), followfirst)
+ s = dagop.revancestors(repo, baseset([c.rev()]), followfirst)
return subset & s
@@ -1355,7 +1233,7 @@
if not include:
return baseset()
- descendants = set(_revdescendants(repo, include, False))
+ descendants = set(dagop.revdescendants(repo, include, False))
exclude = [rev for rev in cl.headrevs()
if not rev in descendants and not rev in include]
else:
@@ -1857,7 +1735,8 @@
firstbranch = ()
if 'topo.firstbranch' in opts:
firstbranch = getset(repo, subset, opts['topo.firstbranch'])
- revs = baseset(_toposort(revs, repo.changelog.parentrevs, firstbranch),
+ revs = baseset(dagop.toposort(revs, repo.changelog.parentrevs,
+ firstbranch),
istopo=True)
if keyflags[0][1]:
revs.reverse()
@@ -1869,204 +1748,6 @@
ctxs.sort(key=_sortkeyfuncs[k], reverse=reverse)
return baseset([c.rev() for c in ctxs])
-def _toposort(revs, parentsfunc, firstbranch=()):
- """Yield revisions from heads to roots one (topo) branch at a time.
-
- This function aims to be used by a graph generator that wishes to minimize
- the number of parallel branches and their interleaving.
-
- Example iteration order (numbers show the "true" order in a changelog):
-
- o 4
- |
- o 1
- |
- | o 3
- | |
- | o 2
- |/
- o 0
-
- Note that the ancestors of merges are understood by the current
- algorithm to be on the same branch. This means no reordering will
- occur behind a merge.
- """
-
- ### Quick summary of the algorithm
- #
- # This function is based around a "retention" principle. We keep revisions
- # in memory until we are ready to emit a whole branch that immediately
- # "merges" into an existing one. This reduces the number of parallel
- # branches with interleaved revisions.
- #
- # During iteration revs are split into two groups:
- # A) revision already emitted
- # B) revision in "retention". They are stored as different subgroups.
- #
- # for each REV, we do the following logic:
- #
- # 1) if REV is a parent of (A), we will emit it. If there is a
- # retention group ((B) above) that is blocked on REV being
- # available, we emit all the revisions out of that retention
- # group first.
- #
- # 2) else, we'll search for a subgroup in (B) awaiting for REV to be
- # available, if such subgroup exist, we add REV to it and the subgroup is
- # now awaiting for REV.parents() to be available.
- #
- # 3) finally if no such group existed in (B), we create a new subgroup.
- #
- #
- # To bootstrap the algorithm, we emit the tipmost revision (which
- # puts it in group (A) from above).
-
- revs.sort(reverse=True)
-
- # Set of parents of revision that have been emitted. They can be considered
- # unblocked as the graph generator is already aware of them so there is no
- # need to delay the revisions that reference them.
- #
- # If someone wants to prioritize a branch over the others, pre-filling this
- # set will force all other branches to wait until this branch is ready to be
- # emitted.
- unblocked = set(firstbranch)
-
- # list of groups waiting to be displayed, each group is defined by:
- #
- # (revs: lists of revs waiting to be displayed,
- # blocked: set of that cannot be displayed before those in 'revs')
- #
- # The second value ('blocked') correspond to parents of any revision in the
- # group ('revs') that is not itself contained in the group. The main idea
- # of this algorithm is to delay as much as possible the emission of any
- # revision. This means waiting for the moment we are about to display
- # these parents to display the revs in a group.
- #
- # This first implementation is smart until it encounters a merge: it will
- # emit revs as soon as any parent is about to be emitted and can grow an
- # arbitrary number of revs in 'blocked'. In practice this mean we properly
- # retains new branches but gives up on any special ordering for ancestors
- # of merges. The implementation can be improved to handle this better.
- #
- # The first subgroup is special. It corresponds to all the revision that
- # were already emitted. The 'revs' lists is expected to be empty and the
- # 'blocked' set contains the parents revisions of already emitted revision.
- #
- # You could pre-seed the <parents> set of groups[0] to a specific
- # changesets to select what the first emitted branch should be.
- groups = [([], unblocked)]
- pendingheap = []
- pendingset = set()
-
- heapq.heapify(pendingheap)
- heappop = heapq.heappop
- heappush = heapq.heappush
- for currentrev in revs:
- # Heap works with smallest element, we want highest so we invert
- if currentrev not in pendingset:
- heappush(pendingheap, -currentrev)
- pendingset.add(currentrev)
- # iterates on pending rev until after the current rev have been
- # processed.
- rev = None
- while rev != currentrev:
- rev = -heappop(pendingheap)
- pendingset.remove(rev)
-
- # Seek for a subgroup blocked, waiting for the current revision.
- matching = [i for i, g in enumerate(groups) if rev in g[1]]
-
- if matching:
- # The main idea is to gather together all sets that are blocked
- # on the same revision.
- #
- # Groups are merged when a common blocking ancestor is
- # observed. For example, given two groups:
- #
- # revs [5, 4] waiting for 1
- # revs [3, 2] waiting for 1
- #
- # These two groups will be merged when we process
- # 1. In theory, we could have merged the groups when
- # we added 2 to the group it is now in (we could have
- # noticed the groups were both blocked on 1 then), but
- # the way it works now makes the algorithm simpler.
- #
- # We also always keep the oldest subgroup first. We can
- # probably improve the behavior by having the longest set
- # first. That way, graph algorithms could minimise the length
- # of parallel lines their drawing. This is currently not done.
- targetidx = matching.pop(0)
- trevs, tparents = groups[targetidx]
- for i in matching:
- gr = groups[i]
- trevs.extend(gr[0])
- tparents |= gr[1]
- # delete all merged subgroups (except the one we kept)
- # (starting from the last subgroup for performance and
- # sanity reasons)
- for i in reversed(matching):
- del groups[i]
- else:
- # This is a new head. We create a new subgroup for it.
- targetidx = len(groups)
- groups.append(([], {rev}))
-
- gr = groups[targetidx]
-
- # We now add the current nodes to this subgroups. This is done
- # after the subgroup merging because all elements from a subgroup
- # that relied on this rev must precede it.
- #
- # we also update the <parents> set to include the parents of the
- # new nodes.
- if rev == currentrev: # only display stuff in rev
- gr[0].append(rev)
- gr[1].remove(rev)
- parents = [p for p in parentsfunc(rev) if p > node.nullrev]
- gr[1].update(parents)
- for p in parents:
- if p not in pendingset:
- pendingset.add(p)
- heappush(pendingheap, -p)
-
- # Look for a subgroup to display
- #
- # When unblocked is empty (if clause), we were not waiting for any
- # revisions during the first iteration (if no priority was given) or
- # if we emitted a whole disconnected set of the graph (reached a
- # root). In that case we arbitrarily take the oldest known
- # subgroup. The heuristic could probably be better.
- #
- # Otherwise (elif clause) if the subgroup is blocked on
- # a revision we just emitted, we can safely emit it as
- # well.
- if not unblocked:
- if len(groups) > 1: # display other subset
- targetidx = 1
- gr = groups[1]
- elif not gr[1] & unblocked:
- gr = None
-
- if gr is not None:
- # update the set of awaited revisions with the one from the
- # subgroup
- unblocked |= gr[1]
- # output all revisions in the subgroup
- for r in gr[0]:
- yield r
- # delete the subgroup that you just output
- # unless it is groups[0] in which case you just empty it.
- if targetidx:
- del groups[targetidx]
- else:
- gr[0][:] = []
- # Check if we have some subgroup waiting for revisions we are not going to
- # iterate over
- for g in groups:
- for r in g[0]:
- yield r
-
@predicate('subrepo([pattern])')
def subrepo(repo, subset, x):
"""Changesets that add, modify or remove the given subrepo. If no subrepo