[PATCH 1 of 8] obsutil: move 'successorssets' to the new modules
Pierre-Yves David
pierre-yves.david at ens-lyon.org
Tue Jun 27 08:56:44 UTC 2017
# HG changeset patch
# User Pierre-Yves David <pierre-yves.david at octobus.net>
# Date 1498518181 -7200
# Tue Jun 27 01:03:01 2017 +0200
# Node ID 40df51910c27ae6dc8db6e24fb6542d17982d8e4
# Parent a49ab7f5e7e765a94a1dfab2ee3b1da695789eb6
# EXP-Topic obsutil
# Available At https://www.mercurial-scm.org/repo/users/marmoute/mercurial/
# hg pull https://www.mercurial-scm.org/repo/users/marmoute/mercurial/ -r 40df51910c27
obsutil: move 'successorssets' to the new modules
We have a new 'obsutil' module now. We move this high level utility there to bring
'obsolete.py' back to a more reasonable size.
diff --git a/mercurial/debugcommands.py b/mercurial/debugcommands.py
--- a/mercurial/debugcommands.py
+++ b/mercurial/debugcommands.py
@@ -47,6 +47,7 @@ from . import (
lock as lockmod,
merge as mergemod,
obsolete,
+ obsutil,
phases,
policy,
pvec,
@@ -2084,7 +2085,7 @@ def debugsuccessorssets(ui, repo, *revs)
for rev in scmutil.revrange(repo, revs):
ctx = repo[rev]
ui.write('%s\n'% ctx2str(ctx))
- for succsset in obsolete.successorssets(repo, ctx.node(), cache):
+ for succsset in obsutil.successorssets(repo, ctx.node(), cache):
if succsset:
ui.write(' ')
ui.write(node2str(succsset[0]))
diff --git a/mercurial/destutil.py b/mercurial/destutil.py
--- a/mercurial/destutil.py
+++ b/mercurial/destutil.py
@@ -11,7 +11,7 @@ from .i18n import _
from . import (
bookmarks,
error,
- obsolete,
+ obsutil,
scmutil,
)
@@ -24,7 +24,7 @@ def _destupdateobs(repo, clean):
if p1.obsolete() and not p1.children():
# allow updating to successors
- successors = obsolete.successorssets(repo, p1.node())
+ successors = obsutil.successorssets(repo, p1.node())
# behavior of certain cases is as follows,
#
diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -76,6 +76,7 @@ from .i18n import _
from . import (
error,
node,
+ obsutil,
phases,
policy,
util,
@@ -1062,211 +1063,10 @@ def foreground(repo, nodes):
foreground = set(repo.set('%ln::', known))
return set(c.node() for c in foreground)
-
def successorssets(repo, initialnode, cache=None):
- """Return set of all latest successors of initial nodes
-
- The successors set of a changeset A are the group of revisions that succeed
- A. It succeeds A as a consistent whole, each revision being only a partial
- replacement. The successors set contains non-obsolete changesets only.
-
- This function returns the full list of successor sets which is why it
- returns a list of tuples and not just a single tuple. Each tuple is a valid
- successors set. Note that (A,) may be a valid successors set for changeset A
- (see below).
-
- In most cases, a changeset A will have a single element (e.g. the changeset
- A is replaced by A') in its successors set. Though, it is also common for a
- changeset A to have no elements in its successor set (e.g. the changeset
- has been pruned). Therefore, the returned list of successors sets will be
- [(A',)] or [], respectively.
-
- When a changeset A is split into A' and B', however, it will result in a
- successors set containing more than a single element, i.e. [(A',B')].
- Divergent changesets will result in multiple successors sets, i.e. [(A',),
- (A'')].
-
- If a changeset A is not obsolete, then it will conceptually have no
- successors set. To distinguish this from a pruned changeset, the successor
- set will contain itself only, i.e. [(A,)].
-
- Finally, successors unknown locally are considered to be pruned (obsoleted
- without any successors).
-
- The optional `cache` parameter is a dictionary that may contain precomputed
- successors sets. It is meant to reuse the computation of a previous call to
- `successorssets` when multiple calls are made at the same time. The cache
- dictionary is updated in place. The caller is responsible for its life
- span. Code that makes multiple calls to `successorssets` *must* use this
- cache mechanism or suffer terrible performance.
- """
-
- succmarkers = repo.obsstore.successors
-
- # Stack of nodes we search successors sets for
- toproceed = [initialnode]
- # set version of above list for fast loop detection
- # element added to "toproceed" must be added here
- stackedset = set(toproceed)
- if cache is None:
- cache = {}
-
- # This while loop is the flattened version of a recursive search for
- # successors sets
- #
- # def successorssets(x):
- # successors = directsuccessors(x)
- # ss = [[]]
- # for succ in directsuccessors(x):
- # # product as in itertools cartesian product
- # ss = product(ss, successorssets(succ))
- # return ss
- #
- # But we can not use plain recursive calls here:
- # - that would blow the python call stack
- # - obsolescence markers may have cycles, we need to handle them.
- #
- # The `toproceed` list act as our call stack. Every node we search
- # successors set for are stacked there.
- #
- # The `stackedset` is set version of this stack used to check if a node is
- # already stacked. This check is used to detect cycles and prevent infinite
- # loop.
- #
- # successors set of all nodes are stored in the `cache` dictionary.
- #
- # After this while loop ends we use the cache to return the successors sets
- # for the node requested by the caller.
- while toproceed:
- # Every iteration tries to compute the successors sets of the topmost
- # node of the stack: CURRENT.
- #
- # There are four possible outcomes:
- #
- # 1) We already know the successors sets of CURRENT:
- # -> mission accomplished, pop it from the stack.
- # 2) Node is not obsolete:
- # -> the node is its own successors sets. Add it to the cache.
- # 3) We do not know successors set of direct successors of CURRENT:
- # -> We add those successors to the stack.
- # 4) We know successors sets of all direct successors of CURRENT:
- # -> We can compute CURRENT successors set and add it to the
- # cache.
- #
- current = toproceed[-1]
- if current in cache:
- # case (1): We already know the successors sets
- stackedset.remove(toproceed.pop())
- elif current not in succmarkers:
- # case (2): The node is not obsolete.
- if current in repo:
- # We have a valid last successors.
- cache[current] = [(current,)]
- else:
- # Final obsolete version is unknown locally.
- # Do not count that as a valid successors
- cache[current] = []
- else:
- # cases (3) and (4)
- #
- # We proceed in two phases. Phase 1 aims to distinguish case (3)
- # from case (4):
- #
- # For each direct successors of CURRENT, we check whether its
- # successors sets are known. If they are not, we stack the
- # unknown node and proceed to the next iteration of the while
- # loop. (case 3)
- #
- # During this step, we may detect obsolescence cycles: a node
- # with unknown successors sets but already in the call stack.
- # In such a situation, we arbitrary set the successors sets of
- # the node to nothing (node pruned) to break the cycle.
- #
- # If no break was encountered we proceed to phase 2.
- #
- # Phase 2 computes successors sets of CURRENT (case 4); see details
- # in phase 2 itself.
- #
- # Note the two levels of iteration in each phase.
- # - The first one handles obsolescence markers using CURRENT as
- # precursor (successors markers of CURRENT).
- #
- # Having multiple entry here means divergence.
- #
- # - The second one handles successors defined in each marker.
- #
- # Having none means pruned node, multiple successors means split,
- # single successors are standard replacement.
- #
- for mark in sorted(succmarkers[current]):
- for suc in mark[1]:
- if suc not in cache:
- if suc in stackedset:
- # cycle breaking
- cache[suc] = []
- else:
- # case (3) If we have not computed successors sets
- # of one of those successors we add it to the
- # `toproceed` stack and stop all work for this
- # iteration.
- toproceed.append(suc)
- stackedset.add(suc)
- break
- else:
- continue
- break
- else:
- # case (4): we know all successors sets of all direct
- # successors
- #
- # Successors set contributed by each marker depends on the
- # successors sets of all its "successors" node.
- #
- # Each different marker is a divergence in the obsolescence
- # history. It contributes successors sets distinct from other
- # markers.
- #
- # Within a marker, a successor may have divergent successors
- # sets. In such a case, the marker will contribute multiple
- # divergent successors sets. If multiple successors have
- # divergent successors sets, a Cartesian product is used.
- #
- # At the end we post-process successors sets to remove
- # duplicated entry and successors set that are strict subset of
- # another one.
- succssets = []
- for mark in sorted(succmarkers[current]):
- # successors sets contributed by this marker
- markss = [[]]
- for suc in mark[1]:
- # cardinal product with previous successors
- productresult = []
- for prefix in markss:
- for suffix in cache[suc]:
- newss = list(prefix)
- for part in suffix:
- # do not duplicated entry in successors set
- # first entry wins.
- if part not in newss:
- newss.append(part)
- productresult.append(newss)
- markss = productresult
- succssets.extend(markss)
- # remove duplicated and subset
- seen = []
- final = []
- candidate = sorted(((set(s), s) for s in succssets if s),
- key=lambda x: len(x[1]), reverse=True)
- for setversion, listversion in candidate:
- for seenset in seen:
- if setversion.issubset(seenset):
- break
- else:
- final.append(listversion)
- seen.append(setversion)
- final.reverse() # put small successors set first
- cache[current] = final
- return cache[initialnode]
+ movemsg = 'obsolete.successorssets moved to obsutil.successorssets'
+ repo.ui.deprecwarn(movemsg, '4.3')
+ return obsutil.successorssets(repo, initialnode, cache=cache)
# mapping of 'set-name' -> <function to compute this set>
cachefuncs = {}
@@ -1385,7 +1185,7 @@ def _computedivergentset(repo):
continue # emergency cycle hanging prevention
seen.add(prec)
if prec not in newermap:
- successorssets(repo, prec, newermap)
+ obsutil.successorssets(repo, prec, newermap)
newer = [n for n in newermap[prec] if n]
if len(newer) > 1:
divergent.add(ctx.rev())
diff --git a/mercurial/obsutil.py b/mercurial/obsutil.py
--- a/mercurial/obsutil.py
+++ b/mercurial/obsutil.py
@@ -34,3 +34,208 @@ def closestpredecessors(repo, nodeid):
yield precnodeid
else:
stack.append(precnodeid)
+
+def successorssets(repo, initialnode, cache=None):
+ """Return set of all latest successors of initial nodes
+
+ The successors set of a changeset A are the group of revisions that succeed
+ A. It succeeds A as a consistent whole, each revision being only a partial
+ replacement. The successors set contains non-obsolete changesets only.
+
+ This function returns the full list of successor sets which is why it
+ returns a list of tuples and not just a single tuple. Each tuple is a valid
+ successors set. Note that (A,) may be a valid successors set for changeset A
+ (see below).
+
+ In most cases, a changeset A will have a single element (e.g. the changeset
+ A is replaced by A') in its successors set. Though, it is also common for a
+ changeset A to have no elements in its successor set (e.g. the changeset
+ has been pruned). Therefore, the returned list of successors sets will be
+ [(A',)] or [], respectively.
+
+ When a changeset A is split into A' and B', however, it will result in a
+ successors set containing more than a single element, i.e. [(A',B')].
+ Divergent changesets will result in multiple successors sets, i.e. [(A',),
+ (A'')].
+
+ If a changeset A is not obsolete, then it will conceptually have no
+ successors set. To distinguish this from a pruned changeset, the successor
+ set will contain itself only, i.e. [(A,)].
+
+ Finally, successors unknown locally are considered to be pruned (obsoleted
+ without any successors).
+
+ The optional `cache` parameter is a dictionary that may contain precomputed
+ successors sets. It is meant to reuse the computation of a previous call to
+ `successorssets` when multiple calls are made at the same time. The cache
+ dictionary is updated in place. The caller is responsible for its life
+ span. Code that makes multiple calls to `successorssets` *must* use this
+ cache mechanism or suffer terrible performance.
+ """
+
+ succmarkers = repo.obsstore.successors
+
+ # Stack of nodes we search successors sets for
+ toproceed = [initialnode]
+ # set version of above list for fast loop detection
+ # element added to "toproceed" must be added here
+ stackedset = set(toproceed)
+ if cache is None:
+ cache = {}
+
+ # This while loop is the flattened version of a recursive search for
+ # successors sets
+ #
+ # def successorssets(x):
+ # successors = directsuccessors(x)
+ # ss = [[]]
+ # for succ in directsuccessors(x):
+ # # product as in itertools cartesian product
+ # ss = product(ss, successorssets(succ))
+ # return ss
+ #
+ # But we can not use plain recursive calls here:
+ # - that would blow the python call stack
+ # - obsolescence markers may have cycles, we need to handle them.
+ #
+ # The `toproceed` list act as our call stack. Every node we search
+ # successors set for are stacked there.
+ #
+ # The `stackedset` is set version of this stack used to check if a node is
+ # already stacked. This check is used to detect cycles and prevent infinite
+ # loop.
+ #
+ # successors set of all nodes are stored in the `cache` dictionary.
+ #
+ # After this while loop ends we use the cache to return the successors sets
+ # for the node requested by the caller.
+ while toproceed:
+ # Every iteration tries to compute the successors sets of the topmost
+ # node of the stack: CURRENT.
+ #
+ # There are four possible outcomes:
+ #
+ # 1) We already know the successors sets of CURRENT:
+ # -> mission accomplished, pop it from the stack.
+ # 2) Node is not obsolete:
+ # -> the node is its own successors sets. Add it to the cache.
+ # 3) We do not know successors set of direct successors of CURRENT:
+ # -> We add those successors to the stack.
+ # 4) We know successors sets of all direct successors of CURRENT:
+ # -> We can compute CURRENT successors set and add it to the
+ # cache.
+ #
+ current = toproceed[-1]
+ if current in cache:
+ # case (1): We already know the successors sets
+ stackedset.remove(toproceed.pop())
+ elif current not in succmarkers:
+ # case (2): The node is not obsolete.
+ if current in repo:
+ # We have a valid last successors.
+ cache[current] = [(current,)]
+ else:
+ # Final obsolete version is unknown locally.
+ # Do not count that as a valid successors
+ cache[current] = []
+ else:
+ # cases (3) and (4)
+ #
+ # We proceed in two phases. Phase 1 aims to distinguish case (3)
+ # from case (4):
+ #
+ # For each direct successors of CURRENT, we check whether its
+ # successors sets are known. If they are not, we stack the
+ # unknown node and proceed to the next iteration of the while
+ # loop. (case 3)
+ #
+ # During this step, we may detect obsolescence cycles: a node
+ # with unknown successors sets but already in the call stack.
+ # In such a situation, we arbitrary set the successors sets of
+ # the node to nothing (node pruned) to break the cycle.
+ #
+ # If no break was encountered we proceed to phase 2.
+ #
+ # Phase 2 computes successors sets of CURRENT (case 4); see details
+ # in phase 2 itself.
+ #
+ # Note the two levels of iteration in each phase.
+ # - The first one handles obsolescence markers using CURRENT as
+ # precursor (successors markers of CURRENT).
+ #
+ # Having multiple entry here means divergence.
+ #
+ # - The second one handles successors defined in each marker.
+ #
+ # Having none means pruned node, multiple successors means split,
+ # single successors are standard replacement.
+ #
+ for mark in sorted(succmarkers[current]):
+ for suc in mark[1]:
+ if suc not in cache:
+ if suc in stackedset:
+ # cycle breaking
+ cache[suc] = []
+ else:
+ # case (3) If we have not computed successors sets
+ # of one of those successors we add it to the
+ # `toproceed` stack and stop all work for this
+ # iteration.
+ toproceed.append(suc)
+ stackedset.add(suc)
+ break
+ else:
+ continue
+ break
+ else:
+ # case (4): we know all successors sets of all direct
+ # successors
+ #
+ # Successors set contributed by each marker depends on the
+ # successors sets of all its "successors" node.
+ #
+ # Each different marker is a divergence in the obsolescence
+ # history. It contributes successors sets distinct from other
+ # markers.
+ #
+ # Within a marker, a successor may have divergent successors
+ # sets. In such a case, the marker will contribute multiple
+ # divergent successors sets. If multiple successors have
+ # divergent successors sets, a Cartesian product is used.
+ #
+ # At the end we post-process successors sets to remove
+ # duplicated entry and successors set that are strict subset of
+ # another one.
+ succssets = []
+ for mark in sorted(succmarkers[current]):
+ # successors sets contributed by this marker
+ markss = [[]]
+ for suc in mark[1]:
+ # cardinal product with previous successors
+ productresult = []
+ for prefix in markss:
+ for suffix in cache[suc]:
+ newss = list(prefix)
+ for part in suffix:
+ # do not duplicated entry in successors set
+ # first entry wins.
+ if part not in newss:
+ newss.append(part)
+ productresult.append(newss)
+ markss = productresult
+ succssets.extend(markss)
+ # remove duplicated and subset
+ seen = []
+ final = []
+ candidate = sorted(((set(s), s) for s in succssets if s),
+ key=lambda x: len(x[1]), reverse=True)
+ for setversion, listversion in candidate:
+ for seenset in seen:
+ if setversion.issubset(seenset):
+ break
+ else:
+ final.append(listversion)
+ seen.append(setversion)
+ final.reverse() # put small successors set first
+ cache[current] = final
+ return cache[initialnode]
More information about the Mercurial-devel
mailing list