changeset 2411:bd937b7ce7d2

debugobshistory: handle multiple cycles

We previously handled up to one cycle only. This is now fixed.

--- a/hgext3rd/evolve/obshistory.py	Thu May 18 14:49:02 2017 +0200
+++ b/hgext3rd/evolve/obshistory.py	Thu May 18 14:58:22 2017 +0200
@@ -84,7 +84,7 @@
     path_set = set(path)
     stack = [iter(graph)]
     while stack:
-        for v in stack[-1]:
+        for v in sorted(stack[-1]):
             if v in path_set:
                 path_set.remove(o)
                 return path_set
@@ -108,17 +108,6 @@
     # 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()
 
@@ -135,12 +124,28 @@
         # already shown
         validcandidates = filter(isvalidcandidate, candidates)
 
-        # Check for cycles
-        assert validcandidates
+        # 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
+            repo.ui.debug('obs-cycle detected, forcing display of %s\n'
+                          % nodemod.short(breaknode))
+            validcandidates = [breaknode]
+
+        # Display all valid candidates
         for cand in sorted(validcandidates):
             # Remove candidate from candidates set
             candidates.remove(cand)
+            # And remove it from nodesucc in case of future cycle detected
+            try:
+                del nodesucc[cand]
+            except KeyError:
+                pass
+
             shown.add(cand)
 
             # Add the right changectx class

--- a/tests/test-evolve-obshistory.t	Thu May 18 14:49:02 2017 +0200
+++ b/tests/test-evolve-obshistory.t	Thu May 18 14:58:22 2017 +0200
@@ -1315,3 +1315,133 @@
   |    rewritten by test (*20*) as a8df460dbbfe (glob)
   |
 
+Test with multiple cyles
+========================
+
+Test setup
+----------
+
+  $ hg init $TESTTMP/multiple-cycle
+  $ cd $TESTTMP/multiple-cycle
+  $ mkcommit ROOT
+  $ mkcommit A
+  $ mkcommit B
+  $ mkcommit C
+  $ mkcommit D
+  $ mkcommit E
+  $ mkcommit F
+  $ hg log -G
+  @  changeset:   6:d9f908fde1a1
+  |  tag:         tip
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     F
+  |
+  o  changeset:   5:0da815c333f6
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     E
+  |
+  o  changeset:   4:868d2e0eb19c
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     D
+  |
+  o  changeset:   3:a8df460dbbfe
+  |  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 first cycle
+  $ hg prune -s "desc(B)" "desc(A)"
+  1 changesets pruned
+  5 new unstable changesets
+  $ hg prune -s "desc(C)" "desc(B)"
+  1 changesets pruned
+  $ hg prune --split -s "desc(A)" -s "desc(D)" "desc(C)"
+  1 changesets pruned
+And create a second one
+  $ hg prune -s "desc(E)" "desc(D)"
+  1 changesets pruned
+  $ hg prune -s "desc(F)" "desc(E)"
+  1 changesets pruned
+  $ hg prune -s "desc(D)" "desc(F)"
+  0 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  working directory now at 868d2e0eb19c
+  1 changesets pruned
+  $ hg log --hidden -G
+  x  changeset:   6:d9f908fde1a1
+  |  tag:         tip
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     F
+  |
+  x  changeset:   5:0da815c333f6
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     E
+  |
+  @  changeset:   4:868d2e0eb19c
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  summary:     D
+  |
+  x  changeset:   3:a8df460dbbfe
+  |  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
+  |
+  x  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 "desc(D)" --hidden
+  x  0da815c333f6 (5) E
+  |    rewritten by test (*20*) as d9f908fde1a1 (glob)
+  |
+  @    868d2e0eb19c (4) D
+  |\     rewritten by test (*20*) as 0da815c333f6 (glob)
+  | |
+  | x  d9f908fde1a1 (6) F
+  | |    rewritten by test (*20*) as 868d2e0eb19c (glob)
+  | |
+  +---x  2a34000d3544 (1) A
+  | |      rewritten by test (*20*) as c473644ee0e9 (glob)
+  | |
+  x |  a8df460dbbfe (3) C
+  | |    rewritten by test (*20*) as 2a34000d3544, 868d2e0eb19c (glob)
+  | |
+  x |  c473644ee0e9 (2) B
+  | |    rewritten by test (*20*) as a8df460dbbfe (glob)
+  | |