changeset 2407:783a74c60a5e

obshistory: add a graph option on the debugobshistory command Add a graph option (--graph) to the debugobshistory. The output is like the 'hg log -G' output. The option is activated by default but can be deactivated with '--no-graph' option. There are various issue with the current implementation (multiple cycles handling, N² complexity) but this can be fixed later.
author Pierre-Yves David <pierre-yves.david@octobus.net>
date Thu, 18 May 2017 11:29:27 +0200
parents 31255706b591
children 0af6bb0bfdc3
files hgext3rd/evolve/__init__.py hgext3rd/evolve/obshistory.py tests/test-evolve-obshistory.t
diffstat 3 files changed, 467 insertions(+), 268 deletions(-) [+]
line wrap: on
line diff
--- a/hgext3rd/evolve/__init__.py	Thu May 18 11:29:23 2017 +0200
+++ b/hgext3rd/evolve/__init__.py	Thu May 18 11:29:27 2017 +0200
@@ -3264,12 +3264,16 @@
 
 @eh.command(
     '^debugobshistory',
-    [] + commands.formatteropts,
+    [('G', 'graph', True, _("show the revision DAG")),
+    ] + commands.formatteropts,
     _('hg debugobshistory [OPTION]... [REV]'))
 def cmdobshistory(ui, repo, *revs, **opts):
     revs = scmutil.revrange(repo, revs)
+
+    if opts['graph']:
+        return obshistory._debugobshistorygraph(ui, repo, revs, opts)
+
     fm = ui.formatter('debugobshistory', opts)
-
     revs.reverse()
     obshistory._debugobshistorysingle(fm, repo, revs)
 
--- a/hgext3rd/evolve/obshistory.py	Thu May 18 11:29:23 2017 +0200
+++ b/hgext3rd/evolve/obshistory.py	Thu May 18 11:29:27 2017 +0200
@@ -9,8 +9,197 @@
 
 from mercurial import (
     node as nodemod,
+    cmdutil,
+    graphmod,
+    error
 )
 
+class obsmarker_printer(cmdutil.changeset_printer):
+    """show (available) information about a node
+
+    We display the node, description (if available) and various information
+    about obsolescence markers affecting it"""
+
+    def show(self, ctx, copies=None, matchfn=None, **props):
+        if self.buffered:
+            self.ui.pushbuffer(labeled=True)
+
+            changenode = ctx.node()
+
+            fm = self.ui.formatter('debugobshistory', props)
+            _debugobshistorydisplaynode(fm, self.repo, changenode)
+
+            succs = self.repo.obsstore.successors.get(changenode, ())
+
+            markerfm = fm.nested("debugobshistory.markers")
+            for successor in sorted(succs):
+                _debugobshistorydisplaymarker(markerfm, self.repo, successor)
+            markerfm.end()
+
+            markerfm.plain('\n')
+
+            self.hunk[ctx.node()] = self.ui.popbuffer()
+        else:
+            ### graph output is buffered only
+            msg = 'cannot be used outside of the graphlog (yet)'
+            raise error.ProgrammingError(msg)
+
+    def flush(self, ctx):
+        ''' changeset_printer has some logic around buffering data
+        in self.headers that we don't use
+        '''
+        pass
+
+class missingchangectx(object):
+    ''' a minimal object mimicking changectx for change contexts
+    references by obs markers but not available locally '''
+
+    def __init__(self, repo, nodeid):
+        self._repo = repo
+        self._node = nodeid
+
+    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]
+    path_set = set(path)
+    stack = [iter(graph)]
+    while stack:
+        for v in stack[-1]:
+            if v in path_set:
+                path_set.remove(o)
+                return path_set
+            elif v not in visited:
+                visited.add(v)
+                path.append(v)
+                path_set.add(v)
+                stack.append(iter(graph.get(v, ())))
+                break
+        else:
+            path_set.remove(path.pop())
+            stack.pop()
+    return False
+
+def _obshistorywalker(repo, revs):
+    """ Directly inspired by graphmod.dagwalker,
+    walk the obs marker tree and yield
+    (id, CHANGESET, ctx, [parentinfo]) tuples
+    """
+
+    # Get the list of nodes and links between them
+    candidates, nodesucc, nodeprec = _obshistorywalker_links(repo, revs)
+
+    # If we have a cycle
+    cycle = cyclic(nodesucc)
+    # XXX We might have multiple cycles
+    if cycle:
+        # Break the cycle
+        breaknode = sorted(cycle)[0]
+        # By removing one of the node in the cycle successors
+        del nodesucc[breaknode]
+        repo.ui.debug('obs-cycle detected, breaking at %s\n'
+                      % nodemod.short(breaknode))
+
+    # Shown, set of nodes presents in items
+    shown = set()
+
+    def isvalidcandidate(candidate):
+        """ Function to filter candidates, check the candidate succ are
+        in shown set
+        """
+        return nodesucc.get(candidate, set()).issubset(shown)
+
+    # While we have some nodes to show
+    while candidates:
+
+        # Filter out candidates, returns only nodes with all their successors
+        # already shown
+        validcandidates = filter(isvalidcandidate, candidates)
+
+        # Check for cycles
+        assert validcandidates
+
+        for cand in sorted(validcandidates):
+            # Remove candidate from candidates set
+            candidates.remove(cand)
+            shown.add(cand)
+
+            # Add the right changectx class
+            if cand in repo:
+                changectx = repo[cand]
+            else:
+                changectx = missingchangectx(repo, cand)
+
+            childrens = [(graphmod.PARENT, x) for x in nodeprec.get(cand, ())]
+            yield (cand, 'M', changectx, childrens)
+
+def _obshistorywalker_links(repo, revs):
+    """ Iterate the obs history tree starting from revs, traversing
+    each revision precursors recursively.
+    Return a tuple of:
+    - The list of node crossed
+    - The dictionnary of each node successors, values are a set
+    - The dictionnary of each node precursors, values are a list
+    """
+    precursors = repo.obsstore.precursors
+    nodec = repo.changelog.node
+
+    # Parents, set of parents nodes seen during walking the graph for node
+    nodesucc = dict()
+    # Childrens
+    nodeprec = dict()
+
+    nodes = [nodec(r) for r in revs]
+    seen = set(nodes)
+
+    # Iterate on each node
+    while nodes:
+        node = nodes.pop()
+
+        precs = precursors.get(node, ())
+
+        nodeprec[node] = []
+
+        for prec in sorted(precs):
+            precnode = prec[0]
+
+            # Mark node as prec successor
+            nodesucc.setdefault(precnode, set()).add(node)
+
+            # Mark precnode as node precursor
+            nodeprec[node].append(precnode)
+
+            # Add prec for future processing if not node already processed
+            if precnode not in seen:
+                seen.add(precnode)
+                nodes.append(precnode)
+
+    return sorted(seen), nodesucc, nodeprec
+
+def _debugobshistorygraph(ui, repo, revs, opts):
+    displayer = obsmarker_printer(ui, repo.unfiltered(), None, opts, buffered=True)
+    edges = graphmod.asciiedges
+    cmdutil.displaygraph(ui, repo, _obshistorywalker(repo.unfiltered(), revs), displayer, edges)
+
 def _debugobshistorysingle(fm, repo, revs):
     """ Display the obsolescence history for a single revision
     """
--- a/tests/test-evolve-obshistory.t	Thu May 18 11:29:23 2017 +0200
+++ b/tests/test-evolve-obshistory.t	Thu May 18 11:29:27 2017 +0200
@@ -54,10 +54,12 @@
 Actual test
 -----------
   $ hg debugobshistory 4ae3a4151de9
-  4ae3a4151de9 (3) A1
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as 4ae3a4151de9 (glob)
-  $ hg debugobshistory 4ae3a4151de9 -Tjson | python -m json.tool
+  @  4ae3a4151de9 (3) A1
+  |
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as 4ae3a4151de9 (glob)
+  
+  $ hg debugobshistory 4ae3a4151de9 --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [],
@@ -85,9 +87,10 @@
       }
   ]
   $ hg debugobshistory --hidden 471f378eab4c
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as 4ae3a4151de9 (glob)
-  $ hg debugobshistory --hidden 471f378eab4c -Tjson | python -m json.tool
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as 4ae3a4151de9 (glob)
+  
+  $ hg debugobshistory --hidden 471f378eab4c --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [
@@ -171,9 +174,10 @@
 -----------
 
   $ hg debugobshistory 'desc(B0)' --hidden
-  0dec01379d3b (2) B0
-    pruned by test (*20*) (glob)
-  $ hg debugobshistory 'desc(B0)' --hidden -Tjson | python -m json.tool
+  x  0dec01379d3b (2) B0
+       pruned by test (*20*) (glob)
+  
+  $ hg debugobshistory 'desc(B0)' --hidden --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [
@@ -192,8 +196,9 @@
       }
   ]
   $ hg debugobshistory 'desc(A0)'
-  471f378eab4c (1) A0
-  $ hg debugobshistory 'desc(A0)' -Tjson | python -m json.tool
+  @  471f378eab4c (1) A0
+  
+  $ hg debugobshistory 'desc(A0)' --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [],
@@ -300,10 +305,12 @@
 Actual test
 -----------
 
+Check that debugobshistory on splitted commit show both targets
   $ hg debugobshistory 471597cad322 --hidden
-  471597cad322 (1) A0
-    rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
-  $ hg debugobshistory 471597cad322 --hidden -Tjson | python -m json.tool
+  x  471597cad322 (1) A0
+       rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
+  
+  $ hg debugobshistory 471597cad322 --hidden --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [
@@ -325,70 +332,32 @@
           "debugobshistory.shortdescription": "A0"
       }
   ]
+Check that debugobshistory on the first successor after split show
+the revision plus the splitted one
   $ hg debugobshistory 337fec4d2edc
-  337fec4d2edc (2) A0
-  471597cad322 (1) A0
-    rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
-  $ hg debugobshistory 337fec4d2edc -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [],
-          "debugobshistory.node": "337fec4d2edc",
-          "debugobshistory.rev": 2,
-          "debugobshistory.shortdescription": "A0"
-      },
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "337fec4d2edc",
-                      "f257fde29c7a"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "471597cad322",
-          "debugobshistory.rev": 1,
-          "debugobshistory.shortdescription": "A0"
-      }
-  ]
+  o  337fec4d2edc (2) A0
+  |
+  x  471597cad322 (1) A0
+       rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
+  
+Check that debugobshistory on the second successor after split show
+the revision plus the splitted one
   $ hg debugobshistory f257fde29c7a
-  f257fde29c7a (3) A0
-  471597cad322 (1) A0
-    rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
-  $ hg debugobshistory f257fde29c7a -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [],
-          "debugobshistory.node": "f257fde29c7a",
-          "debugobshistory.rev": 3,
-          "debugobshistory.shortdescription": "A0"
-      },
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "337fec4d2edc",
-                      "f257fde29c7a"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "471597cad322",
-          "debugobshistory.rev": 1,
-          "debugobshistory.shortdescription": "A0"
-      }
-  ]
+  @  f257fde29c7a (3) A0
+  |
+  x  471597cad322 (1) A0
+       rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
+  
+Check that debugobshistory on both successors after split show
+a coherent graph
+  $ hg debugobshistory 'f257fde29c7a+337fec4d2edc'
+  o  337fec4d2edc (2) A0
+  |
+  | @  f257fde29c7a (3) A0
+  |/
+  x  471597cad322 (1) A0
+       rewritten by test (*20*) as 337fec4d2edc, f257fde29c7a (glob)
+  
   $ hg update 471597cad322
   abort: hidden revision '471597cad322'!
   (use --hidden to access hidden revisions; successors: 337fec4d2edc, f257fde29c7a)
@@ -552,9 +521,10 @@
 -----------
 
   $ hg debugobshistory de7290d8b885 --hidden
-  de7290d8b885 (1) A0
-    rewritten by test (*20*) as 1ae8bc733a14, 337fec4d2edc, c7f044602e9b, f257fde29c7a (glob)
-  $ hg debugobshistory de7290d8b885 --hidden -Tjson | python -m json.tool
+  x  de7290d8b885 (1) A0
+       rewritten by test (*20*) as 1ae8bc733a14, 337fec4d2edc, c7f044602e9b, f257fde29c7a (glob)
+  
+  $ hg debugobshistory de7290d8b885 --hidden --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [
@@ -579,10 +549,12 @@
       }
   ]
   $ hg debugobshistory c7f044602e9b
-  c7f044602e9b (5) A0
-  de7290d8b885 (1) A0
-    rewritten by test (*20*) as 1ae8bc733a14, 337fec4d2edc, c7f044602e9b, f257fde29c7a (glob)
-  $ hg debugobshistory c7f044602e9b -Tjson | python -m json.tool
+  @  c7f044602e9b (5) A0
+  |
+  x  de7290d8b885 (1) A0
+       rewritten by test (*20*) as 1ae8bc733a14, 337fec4d2edc, c7f044602e9b, f257fde29c7a (glob)
+  
+  $ hg debugobshistory c7f044602e9b --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [],
@@ -612,13 +584,19 @@
           "debugobshistory.shortdescription": "A0"
       }
   ]
-  $ hg debugobshistory 2:5
-  337fec4d2edc (2) A0
-  de7290d8b885 (1) A0
-    rewritten by test (*20*) as 1ae8bc733a14, 337fec4d2edc, c7f044602e9b, f257fde29c7a (glob)
-  f257fde29c7a (3) A0
-  1ae8bc733a14 (4) A0
-  c7f044602e9b (5) A0
+Check that debugobshistory on all heads show a coherent graph
+  $ hg debugobshistory 2::5
+  o  1ae8bc733a14 (4) A0
+  |
+  | o  337fec4d2edc (2) A0
+  |/
+  | @  c7f044602e9b (5) A0
+  |/
+  | o  f257fde29c7a (3) A0
+  |/
+  x  de7290d8b885 (1) A0
+       rewritten by test (*20*) as 1ae8bc733a14, 337fec4d2edc, c7f044602e9b, f257fde29c7a (glob)
+  
   $ hg update de7290d8b885
   abort: hidden revision 'de7290d8b885'!
   (use --hidden to access hidden revisions; successors: 337fec4d2edc, f257fde29c7a and 2 more)
@@ -685,61 +663,30 @@
  Actual test
  -----------
 
+Check that debugobshistory on the first folded revision show only
+the revision with the target
   $ hg debugobshistory --hidden 471f378eab4c
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  $ hg debugobshistory --hidden 471f378eab4c -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "eb5a0daa2192"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "471f378eab4c",
-          "debugobshistory.rev": 1,
-          "debugobshistory.shortdescription": "A0"
-      }
-  ]
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as eb5a0daa2192 (glob)
+  
+Check that debugobshistory on the second folded revision show only
+the revision with the target
   $ hg debugobshistory --hidden 0dec01379d3b
-  0dec01379d3b (2) B0
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  $ hg debugobshistory --hidden 0dec01379d3b -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "eb5a0daa2192"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "0dec01379d3b",
-          "debugobshistory.rev": 2,
-          "debugobshistory.shortdescription": "B0"
-      }
-  ]
+  x  0dec01379d3b (2) B0
+       rewritten by test (*20*) as eb5a0daa2192 (glob)
+  
+Check that debugobshistory on the successor revision show a coherent
+graph
   $ hg debugobshistory eb5a0daa2192
-  eb5a0daa2192 (3) C0
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  0dec01379d3b (2) B0
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  $ hg debugobshistory eb5a0daa2192 -Tjson | python -m json.tool
+  @    eb5a0daa2192 (3) C0
+  |\
+  x |  0dec01379d3b (2) B0
+   /     rewritten by test (*20*) as eb5a0daa2192 (glob)
+  |
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as eb5a0daa2192 (glob)
+  
+  $ hg debugobshistory eb5a0daa2192 --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [],
@@ -867,11 +814,13 @@
 Actual test
 -----------
 
+Check that debugobshistory on the divergent revision show both destinations
   $ hg debugobshistory --hidden 471f378eab4c
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as 65b757b745b9 (glob)
-    rewritten by test (*20*) as fdf9bde5129a (glob)
-  $ hg debugobshistory --hidden 471f378eab4c -Tjson | python -m json.tool
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as 65b757b745b9 (glob)
+       rewritten by test (*20*) as fdf9bde5129a (glob)
+  
+  $ hg debugobshistory --hidden 471f378eab4c --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [
@@ -903,55 +852,36 @@
           "debugobshistory.shortdescription": "A0"
       }
   ]
+Check that debugobshistory on the first diverged revision show the revision
+and the diverent one
   $ hg debugobshistory fdf9bde5129a
-  fdf9bde5129a (2) A1
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as 65b757b745b9 (glob)
-    rewritten by test (*20*) as fdf9bde5129a (glob)
-  $ hg debugobshistory fdf9bde5129a -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [],
-          "debugobshistory.node": "fdf9bde5129a",
-          "debugobshistory.rev": 2,
-          "debugobshistory.shortdescription": "A1"
-      },
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "65b757b745b9"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              },
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "fdf9bde5129a"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "471f378eab4c",
-          "debugobshistory.rev": 1,
-          "debugobshistory.shortdescription": "A0"
-      }
-  ]
+  o  fdf9bde5129a (2) A1
+  |
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as 65b757b745b9 (glob)
+       rewritten by test (*20*) as fdf9bde5129a (glob)
+  
+Check that debugobshistory on the second diverged revision show the revision
+and the diverent one
   $ hg debugobshistory 65b757b745b9
-  65b757b745b9 (3) A2
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as 65b757b745b9 (glob)
-    rewritten by test (*20*) as fdf9bde5129a (glob)
-  $ hg debugobshistory 65b757b745b9 -Tjson | python -m json.tool
+  @  65b757b745b9 (3) A2
+  |
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as 65b757b745b9 (glob)
+       rewritten by test (*20*) as fdf9bde5129a (glob)
+  
+Check that debugobshistory on the both diverged revision show a coherent
+graph
+  $ hg debugobshistory '65b757b745b9+fdf9bde5129a'
+  @  65b757b745b9 (3) A2
+  |
+  | o  fdf9bde5129a (2) A1
+  |/
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as 65b757b745b9 (glob)
+       rewritten by test (*20*) as fdf9bde5129a (glob)
+  
+  $ hg debugobshistory '65b757b745b9+fdf9bde5129a' --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [],
@@ -987,6 +917,12 @@
           "debugobshistory.node": "471f378eab4c",
           "debugobshistory.rev": 1,
           "debugobshistory.shortdescription": "A0"
+      },
+      {
+          "debugobshistory.markers": [],
+          "debugobshistory.node": "fdf9bde5129a",
+          "debugobshistory.rev": 2,
+          "debugobshistory.shortdescription": "A1"
       }
   ]
   $ hg update 471f378eab4c
@@ -1068,63 +1004,20 @@
  Actual test
  -----------
 
-  $ hg debugobshistory --hidden 471f378eab4c
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  $ hg debugobshistory --hidden 471f378eab4c -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "eb5a0daa2192"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "471f378eab4c",
-          "debugobshistory.rev": 1,
-          "debugobshistory.shortdescription": "A0"
-      }
-  ]
-  $ hg debugobshistory --hidden 0dec01379d3b
-  0dec01379d3b (2) B0
-    rewritten by test (*20*) as b7ea6d14e664 (glob)
-  $ hg debugobshistory --hidden 0dec01379d3b -Tjson | python -m json.tool
-  [
-      {
-          "debugobshistory.markers": [
-              {
-                  "debugobshistory.marker_date": [
-                      *, (glob)
-                      0 (glob)
-                  ],
-                  "debugobshistory.marker_user": "test",
-                  "debugobshistory.succnodes": [
-                      "b7ea6d14e664"
-                  ],
-                  "debugobshistory.verb": "rewritten"
-              }
-          ],
-          "debugobshistory.node": "0dec01379d3b",
-          "debugobshistory.rev": 2,
-          "debugobshistory.shortdescription": "B0"
-      }
-  ]
+Check that debugobshistory on head show a coherent graph
   $ hg debugobshistory eb5a0daa2192
-  eb5a0daa2192 (4) C0
-  b7ea6d14e664 (3) B1
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  0dec01379d3b (2) B0
-    rewritten by test (*20*) as b7ea6d14e664 (glob)
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as eb5a0daa2192 (glob)
-  $ hg debugobshistory eb5a0daa2192 -Tjson | python -m json.tool
+  @    eb5a0daa2192 (4) C0
+  |\
+  x |  471f378eab4c (1) A0
+   /     rewritten by test (*20*) as eb5a0daa2192 (glob)
+  |
+  x  b7ea6d14e664 (3) B1
+  |    rewritten by test (*20*) as eb5a0daa2192 (glob)
+  |
+  x  0dec01379d3b (2) B0
+       rewritten by test (*20*) as b7ea6d14e664 (glob)
+  
+  $ hg debugobshistory eb5a0daa2192 --no-graph -Tjson | python -m json.tool
   [
       {
           "debugobshistory.markers": [],
@@ -1277,11 +1170,14 @@
  -----------
 
   $ hg debugobshistory 7a230b46bf61
-  7a230b46bf61 (3) A2
-  fdf9bde5129a (2) A1
-    rewritten by test (*20*) as 7a230b46bf61 (glob)
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as fdf9bde5129a (glob)
+  @  7a230b46bf61 (3) A2
+  |
+  x  fdf9bde5129a (2) A1
+  |    rewritten by test (*20*) as 7a230b46bf61 (glob)
+  |
+  x  471f378eab4c (1) A0
+       rewritten by test (*20*) as fdf9bde5129a (glob)
+  
   $ cd $TESTTMP/local-remote-markers-2
   $ hg pull
   pulling from $TESTTMP/local-remote-markers-1
@@ -1294,15 +1190,125 @@
   (run 'hg heads' to see heads, 'hg merge' to merge)
   working directory parent is obsolete! (471f378eab4c)
   (use 'hg evolve' to update to its successor: 7a230b46bf61)
-  $ hg debugobshistory 7a230b46bf61 --traceback
-  7a230b46bf61 (2) A2
-  fdf9bde5129a
-    rewritten by test (*20*) as 7a230b46bf61 (glob)
-  471f378eab4c (1) A0
-    rewritten by test (*20*) as fdf9bde5129a (glob)
+Check that debugobshistory works with markers pointing to missing local
+changectx
+  $ hg debugobshistory 7a230b46bf61
+  o  7a230b46bf61 (2) A2
+  |
+  x  fdf9bde5129a
+  |    rewritten by test (*20*) as 7a230b46bf61 (glob)
+  |
+  @  471f378eab4c (1) A0
+       rewritten by test (*20*) as fdf9bde5129a (glob)
+  
   $ hg debugobshistory 7a230b46bf61 --color=debug
-  [evolve.node|7a230b46bf61] [evolve.rev|(2)] [evolve.short_description|A2]
-  [evolve.node evolve.missing_change_ctx|fdf9bde5129a]
-    [evolve.verb|rewritten] by [evolve.user|test] [evolve.date|(*20*)] as [evolve.node|7a230b46bf61] (glob)
-  [evolve.node|471f378eab4c] [evolve.rev|(1)] [evolve.short_description|A0]
-    [evolve.verb|rewritten] by [evolve.user|test] [evolve.date|(*20*)] as [evolve.node|fdf9bde5129a] (glob)
+  o  [evolve.node|7a230b46bf61] [evolve.rev|(2)] [evolve.short_description|A2]
+  |
+  x  [evolve.node evolve.missing_change_ctx|fdf9bde5129a]
+  |    [evolve.verb|rewritten] by [evolve.user|test] [evolve.date|(*20*)] as [evolve.node|7a230b46bf61] (glob)
+  |
+  @  [evolve.node|471f378eab4c] [evolve.rev|(1)] [evolve.short_description|A0]
+       [evolve.verb|rewritten] by [evolve.user|test] [evolve.date|(*20*)] as [evolve.node|fdf9bde5129a] (glob)
+  
+
+Test with cycle
+===============
+
+Test setup
+----------
+
+  $ hg init $TESTTMP/cycle
+  $ cd $TESTTMP/cycle
+  $ mkcommit ROOT
+  $ mkcommit A
+  $ mkcommit B
+  $ mkcommit C
+  $ hg log -G
+  @  changeset:   3:a8df460dbbfe
+  |  tag:         tip
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     C
+  |
+  o  changeset:   2:c473644ee0e9
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     B
+  |
+  o  changeset:   1:2a34000d3544
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     A
+  |
+  o  changeset:   0:ea207398892e
+     user:        test
+     date:        Thu Jan 01 00:00:00 1970 +0000
+     summary:     ROOT
+  
+Create a cycle
+  $ hg prune -s 2 1
+  1 changesets pruned
+  2 new unstable changesets
+  $ hg prune -s 3 2
+  1 changesets pruned
+  $ hg prune -s 1 3
+  0 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  working directory now at 2a34000d3544
+  1 changesets pruned
+  $ hg log --hidden -G
+  x  changeset:   3:a8df460dbbfe
+  |  tag:         tip
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     C
+  |
+  x  changeset:   2:c473644ee0e9
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     B
+  |
+  @  changeset:   1:2a34000d3544
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     A
+  |
+  o  changeset:   0:ea207398892e
+     user:        test
+     date:        Thu Jan 01 00:00:00 1970 +0000
+     summary:     ROOT
+  
+Actual test
+-----------
+
+Check that debugobshistory never crash on a cycle
+
+  $ hg debugobshistory 1 --hidden
+  @  2a34000d3544 (1) A
+  |    rewritten by test (*20*) as c473644ee0e9 (glob)
+  |
+  x  a8df460dbbfe (3) C
+  |    rewritten by test (*20*) as 2a34000d3544 (glob)
+  |
+  x  c473644ee0e9 (2) B
+  |    rewritten by test (*20*) as a8df460dbbfe (glob)
+  |
+  $ hg debugobshistory 2 --hidden
+  @  2a34000d3544 (1) A
+  |    rewritten by test (*20*) as c473644ee0e9 (glob)
+  |
+  x  a8df460dbbfe (3) C
+  |    rewritten by test (*20*) as 2a34000d3544 (glob)
+  |
+  x  c473644ee0e9 (2) B
+  |    rewritten by test (*20*) as a8df460dbbfe (glob)
+  |
+  $ hg debugobshistory 3 --hidden
+  @  2a34000d3544 (1) A
+  |    rewritten by test (*20*) as c473644ee0e9 (glob)
+  |
+  x  a8df460dbbfe (3) C
+  |    rewritten by test (*20*) as 2a34000d3544 (glob)
+  |
+  x  c473644ee0e9 (2) B
+  |    rewritten by test (*20*) as a8df460dbbfe (glob)
+  |