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.

mercurial/debugcommands.py

@@ -47,6 +47,7 from . import (
     lock as lockmod,
     merge as mergemod,
     obsolete,
+    obsutil,
     phases,
     policy,
     pvec,
@@ -2110,7 +2111,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]))

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,
         #

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 = {}
@@ -1391,7 +1191,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())

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]