D5537: obsutil: add a simplified obshistorywalker() (PoC)

[av6 (Anton Shestakov)]

av6 created this revision.
Herald added subscribers: mercurial-devel, mjpieters.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  This code is taken from evolve extension, namely from obslog command
  implementation, and somewhat simplified to be easier to review.
  
  No tests and no users for now. The next patch will be more interesting.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5537

AFFECTED FILES
  mercurial/obsutil.py

CHANGE DETAILS

diff --git a/mercurial/obsutil.py b/mercurial/obsutil.py
--- a/mercurial/obsutil.py
+++ b/mercurial/obsutil.py
@@ -981,3 +981,156 @@
                            'reason': 'predecessor',
                            'node': nodemod.hex(dset['commonpredecessor'])})
     return result
+
+class missingchangectx(object):
+    ''' a minimal object mimicking changectx for change contexts
+    referenced by obs markers but not available locally '''
+
+    def __init__(self, repo, nodeid):
+        self._repo = repo
+        self._node = nodeid
+
+    def __bytes__(self):
+        return nodemod.short(self.node())
+
+    __str__ = encoding.strmethod(__bytes__)
+
+    def __repr__(self):
+        return r"<%s %s>" % (type(self).__name__, str(self))
+
+    def node(self):
+        return self._node
+
+    def obsolete(self):
+        # If we don't have it locally, it's obsolete
+        return True
+
+def cyclic(graph):
+    """Return True if the directed graph has a cycle.
+    The graph must be represented as a dictionary mapping vertices to
+    iterables of neighbouring vertices. For example:
+
+    >>> cyclic({1: (2,), 2: (3,), 3: (1,)})
+    True
+    >>> cyclic({1: (2,), 2: (3,), 3: (4,)})
+    False
+
+    Taken from: https://codereview.stackexchange.com/a/86067
+
+    """
+    visited = set()
+    o = object()
+    path = [o]
+    pathset = set(path)
+    stack = [iter(graph)]
+    while stack:
+        for v in sorted(stack[-1]):
+            if v in pathset:
+                return True
+            elif v not in visited:
+                visited.add(v)
+                path.append(v)
+                pathset.add(v)
+                stack.append(iter(graph.get(v, ())))
+                break
+        else:
+            pathset.remove(path.pop())
+            stack.pop()
+    return False
+
+def _obshistorylinks(repo, revs):
+    """ Iterate over the obsolescence history tree starting from revs,
+    traversing successors and predecessors of each revision recursively.
+
+    Returns a tuple of::
+
+      - A list of all walked nodes
+      - A dict of successors of each node, values are sets
+      - A dict of predecessors of each node, values are lists
+    """
+    nodes = [repo.changelog.node(r) for r in revs]
+    seen = set(nodes)
+    nodesuccs = dict()
+    nodepreds = dict()
+
+    predecessors = repo.obsstore.predecessors
+    successors = repo.obsstore.successors
+
+    while nodes:
+        node = nodes.pop()
+        nodepreds[node] = []
+
+        for marker in sorted(predecessors.get(node, ())):
+            prednode = marker[0]
+            nodepreds[node].append(prednode)
+            # `node` is a successor of `predecessor`
+            nodesuccs.setdefault(prednode, set()).add(node)
+
+            if prednode not in seen:
+                seen.add(prednode)
+                nodes.append(prednode)
+
+        for marker in successors.get(node, ()):
+            for succnode in marker[1]:
+                if succnode not in seen:
+                    seen.add(succnode)
+                    nodes.append(succnode)
+
+    return sorted(seen), nodesuccs, nodepreds
+
+def obshistorywalker(unfi, revs):
+    """ Walk the obsolescence marker tree and yield tuples in this format::
+
+      (id, CHANGESET, ctx, [predecessorinfo])
+
+    Directly inspired by graphmod.dagwalker.
+    """
+
+    # avoid import cycle
+    # dagop -> patch -> scmutil -> obsutil -> graphmod -> dagop
+    from . import graphmod
+    candidates, nodesucc, nodepred = _obshistorylinks(unfi, revs)
+    shown = set()
+
+    def isvalidcandidate(candidate):
+        """ Function to filter candidates, check the candidate successors are
+        in shown set
+        """
+        return nodesucc.get(candidate, set()).issubset(shown)
+
+    while candidates:
+
+        # Filter out candidates, returns only nodes with all their successors
+        # already shown
+        validcandidates = filter(isvalidcandidate, candidates)
+
+        # If we likely have a cycle
+        if not validcandidates:
+            cycle = cyclic(nodesucc)
+            assert cycle
+
+            # Then choose a random node from the cycle
+            breaknode = sorted(cycle)[0]
+            # And display it by force
+            unfi.ui.debug('obs-cycle detected, forcing display of %s\n'
+                          % nodemod.short(breaknode))
+            validcandidates = [breaknode]
+
+        for candidate in sorted(validcandidates):
+            candidates.remove(candidate)
+            # And remove it from nodesucc in case of future cycle detected
+            try:
+                del nodesucc[candidate]
+            except KeyError:
+                pass
+
+            shown.add(candidate)
+
+            if candidate in unfi:
+                changectx = unfi[candidate]
+            else:
+                changectx = missingchangectx(unfi, candidate)
+
+            predecessors = [(graphmod.PARENT, x)
+                            for x in nodepred.get(candidate, ())]
+            yield (candidate, graphmod.CHANGESET, changectx, predecessors)



To: av6, #hg-reviewers
Cc: mjpieters, mercurial-devel