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)