# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@ens-lyon.org>
# Date 1490960811 -7200
# Node ID 7ec214ea5d670ac20e30faabaaff9589f1d55b78
# Parent  5b33df335b6c16818c9a1444af852ce4f52eabfc
checkheahds: switch algorithm to use pushed markers instead

We now checks if markers involved in the push are relevant to nodes in the
branch we try to replace. The approach is simpler and more robust.

A test showing the limitation of the previous approach is added.

diff -r 5b33df335b6c -r 7ec214ea5d67 hgext3rd/evolve/checkheads.py
--- a/hgext3rd/evolve/checkheads.py	Fri Mar 31 13:47:14 2017 +0200
+++ b/hgext3rd/evolve/checkheads.py	Fri Mar 31 13:46:51 2017 +0200
@@ -5,12 +5,13 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
+import functools
+
 from mercurial import (
     discovery,
     error,
     extensions,
     node as nodemod,
-    obsolete,
     phases,
     util,
 )
@@ -190,28 +191,24 @@
     # remove future heads which are actually obsoleted by another
     # pushed element:
     #
-    # XXX as above, There are several cases this code does not handle
-    # XXX properly. some below:
+    # known issue
     #
     # * We "silently" skip processing on all changeset unknown locally
     #
     # * if <nh> is public on the remote, it won't be affected by obsolete
     #     marker and a new is created
-    #
-    # * if a successors is pruned, but the prune marker will not be exchanged,
-    #   we currently badely detect the situation.
-    #
-    # These two cases will be easy to handle for known changeset but
-    # much more tricky for unsynced changes.
     repo = pushop.repo
     unfi = repo.unfiltered()
-    cl = unfi.changelog
+    tonode = unfi.changelog.node
+    public = phases.public
+    getphase = unfi._phasecache.phase
+    ispublic = (lambda r: getphase(unfi, r) == public)
+    hasoutmarker = functools.partial(pushingmarkerfor, unfi.obsstore, futurecommon)
     newhs = set()
     discarded = set()
     # I leave the print in the code because they are so handy at debugging
     # and I keep getting back to this piece of code.
     #
-    # from mercurial.node import short
     localcandidate = set()
     unknownheads = set()
     for h in candidate:
@@ -223,86 +220,57 @@
         return unknownheads | set(candidate), set()
     while localcandidate:
         nh = localcandidate.pop()
-        # print 'newhead:', short(nh)
-        currentbranch = unfi.revs('only(%n, (%ln+%ln))',
-                                  nh, localcandidate, newhs)
-        if nh in futurecommon:
-            # The heads will still be alive in the future set
-            # print ' >> head is common'
+        # run this check early to skip the revset on the whole branch
+        if (nh in futurecommon
+                or unfi[nh].phase() <= public):
             newhs.add(nh)
             continue
-        stack = [nh]
-        seen = set(stack)
-        while stack:
-            current = stack.pop()
-            # print ' current:', short(current)
-            if current in futurecommon:
-                if cl.rev(current) not in currentbranch:
-                    # we reach the bottom of the branch, do not go further
-                    # print '  > futurecommon'
-                    continue
-            # XXX we do not know the phase on the remote side
-            if unfi[current].phase() <= phases.public:
-                # public changeset cannot be rewritten. This head will remain.
-                newhs.add(nh)
-                break
-            # We check is the changeset will disappear on push. It happens when
-            #
-            # * the changeset is pruned,
-            # * the changeset is superceed by a one in future common set.
-            #
-            # XXX note: maybe we can just check is the changeset is affected by a
-            # markers relevant to the 'push-set' but that. It might be simpler
-
-            # XXX we need some "stop at" argument to 'successorssets' to
-            # XXX prevent iterating too far. But pushing obsolete changeset
-            # XXX will requires --force anyway.
-            sucsets = obsolete.successorssets(unfi, current)
-            # print '  =', short(current), [tuple(short(s) for s in ss) for ss in sucsets]
-            if sucsets == []: # pruned
-                # XXX possibly, the prune markers is further away and rooted on
-                # some changeset we do not push
+        # XXX there is a corner case if there is a merge in the branch. we
+        # might end up with -more- heads.  However, these heads are not "added"
+        # by the push, but more by the "removal" on the remote so I think is a
+        # okay to ignore them,
+        branchrevs = unfi.revs('only(%n, (%ln+%ln))',
+                               nh, localcandidate, newhs)
+        branchnodes = [tonode(r) for r in branchrevs]
 
-                # print '  - pruned'
-                # XXX if current is unknown, we should request a pull
-                if current in unfi:
-                    for p in unfi[current].parents():
-                        pnode = p.node()
-                        if pnode not in seen:
-                            seen.add(pnode)
-                            stack.append(pnode)
-                continue
-            for ss in sucsets:
-                if ss == (current,): # changeset is alive
-                    # print '  < alive'
-                    newhs.add(nh)
-                    break
-                for suc in ss:
-                    # XXX we should do something special for split
-                    # split -> 1 < len(ss)
-                    if suc in futurecommon:
-                        # print '  - superceeded (%s)' % (current in repo)
-                        if current in unfi:
-                            for p in unfi[current].parents():
-                                pnode = p.node()
-                                if pnode not in seen:
-                                    seen.add(pnode)
-                                    stack.append(pnode)
-                        # XXX if current is unknown, we should request a pull
-                        break
-                else:
-                    continue
-                break # propagate the break
-            else:
-                for ss in sucsets:
-                    for suc in ss:
-                        if suc != nh and suc in futurecommon:
-                            discarded.add(nh)
-                            break
-                    else:
-                        continue
-                    break # propagate the break
-                else:
-                    newhs.add(nh)
+        # The branch will still exist on the remote if
+        # * any part of it is public,
+        # * any part of it is considered part of the result by previous logic,
+        # * if we have no markers to push to obsolete it.
+        if (any(ispublic(r) for r in branchrevs)
+                or any(n in futurecommon for n in branchnodes)
+                or any(not hasoutmarker(n) for n in branchnodes)):
+            newhs.add(nh)
+        else:
+            discarded.add(nh)
     newhs |= unknownheads
     return newhs, discarded
+
+def pushingmarkerfor(obsstore, pushset, node):
+    """True if some markers are to be pushed for node
+
+    We cannot just look in to the pushed obsmarkers from the pushop because
+    discover might have filtered relevant markers. In addition listing all
+    markers relevant to all changeset in the pushed set would be too expensive.
+
+    The is probably some cache opportunity in this function. but it would
+    requires a two dimentions stack.
+    """
+    successorsmarkers = obsstore.successors
+    stack = [node]
+    seen = set(stack)
+    while stack:
+        current = stack.pop()
+        if current in pushset:
+            return True
+        markers = successorsmarkers.get(current, ())
+        # markers fields = ('prec', 'succs', 'flag', 'meta', 'date', 'parents')
+        for m in markers:
+            nexts = m[1] # successors
+            if not nexts: # this is a prune marker
+                nexts = m[5] # parents
+            for n in nexts:
+                if n not in seen:
+                    seen.add(n)
+                    stack.append(n)
+    return False
diff -r 5b33df335b6c -r 7ec214ea5d67 tests/test-checkheads-unpushed-D6.t
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-checkheads-unpushed-D6.t	Fri Mar 31 13:46:51 2017 +0200
@@ -0,0 +1,78 @@
+====================================
+Testing head checking code: Case D-6
+====================================
+
+Mercurial checks for the introduction of multiple heads on push. Evolution
+comes into play to detect if existing heads on the server are being replaced by
+some of the new heads we push.
+
+This test file is part of a series of tests checking this behavior.
+
+Category D: remote head is "obs-affected" locally, but result is not part of the push.
+TestCase 6: single changesets, superseeded then pruned (on a new changeset unpushed) changeset
+
+This is a partial push variation of B6
+
+.. old-state:
+..
+.. * 1 changeset branch
+..
+.. new-state:
+..
+.. * old branch is rewritten onto another one,
+.. * the new version is then pruned.
+..
+.. expected-result:
+..
+.. * push denied
+..
+.. graph-summary:
+..
+..   A ø⇠⊗ A'
+..     | |
+.. C ◔ | ◔ B
+..    \|/
+..     ●
+
+  $ . $TESTDIR/testlib/checkheads-util.sh
+
+Test setup
+----------
+
+  $ setuprepos
+  creating basic server and client repo
+  updating to branch default
+  2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ cd client
+  $ hg up 0
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ mkcommit B0
+  created new head
+  $ mkcommit A1
+  $ hg up '0'
+  0 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  $ mkcommit C0
+  created new head
+  $ hg debugobsolete `getid "desc(A0)"` `getid "desc(A1)"`
+  $ hg debugobsolete --record-parents `getid "desc(A1)"`
+  $ hg log -G --hidden
+  @  0f88766e02d6 (draft): C0
+  |
+  | x  ba93660aff8d (draft): A1
+  | |
+  | o  74ff5441d343 (draft): B0
+  |/
+  | x  8aaa48160adc (draft): A0
+  |/
+  o  1e4be0697311 (public): root
+  
+
+Actual testing
+--------------
+
+  $ hg push --rev 'desc(C0)'
+  pushing to $TESTTMP/server
+  searching for changes
+  abort: push creates new remote head 0f88766e02d6!
+  (merge or see 'hg help push' for details about pushing new heads)
+  [255]
diff -r 5b33df335b6c -r 7ec214ea5d67 tests/test-checkheads-unpushed-D7.t
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-checkheads-unpushed-D7.t	Fri Mar 31 13:46:51 2017 +0200
@@ -0,0 +1,92 @@
+====================================
+Testing head checking code: Case D-7
+====================================
+
+Mercurial checks for the introduction of multiple heads on push. Evolution
+comes into play to detect if existing heads on the server are being replaced by
+some of the new heads we push.
+
+This test file is part of a series of tests checking this behavior.
+
+Category D: remote head is "obs-affected" locally, but result is not part of the push.
+TestCase 7: single changesets, superseeded multiple time then pruned (on a new changeset unpushed) changeset
+
+This is a partial push variation of B6
+
+.. old-state:
+..
+.. * 1 changeset branch
+..
+.. new-state:
+..
+.. * old branch is rewritten onto another one,
+.. * The rewriting it again rewritten on the root
+.. * the new version is then pruned.
+..
+.. expected-result:
+..
+.. * push allowed
+..
+.. graph-summary:
+..
+..       A'
+..   A ø⇠ø⇠⊗ A''
+..     | | |
+.. C ◔ | ◔ | B
+..    \|/ /
+..     | /
+..     |/
+..     |
+..     ●
+
+  $ . $TESTDIR/testlib/checkheads-util.sh
+
+Test setup
+----------
+
+  $ setuprepos
+  creating basic server and client repo
+  updating to branch default
+  2 files updated, 0 files merged, 0 files removed, 0 files unresolved
+  $ cd client
+  $ hg up 0
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ mkcommit B0
+  created new head
+  $ mkcommit A1
+  $ hg up '0'
+  0 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  $ mkcommit A2
+  created new head
+  $ hg up '0'
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ mkcommit C0
+  created new head
+  $ hg debugobsolete `getid "desc(A0)"` `getid "desc(A1)"`
+  $ hg debugobsolete `getid "desc(A1)"` `getid "desc(A2)"`
+  $ hg debugobsolete --record-parents `getid "desc(A2)"`
+  $ hg log -G --hidden
+  @  0f88766e02d6 (draft): C0
+  |
+  | x  c1f8d089020f (draft): A2
+  |/
+  | x  ba93660aff8d (draft): A1
+  | |
+  | o  74ff5441d343 (draft): B0
+  |/
+  | x  8aaa48160adc (draft): A0
+  |/
+  o  1e4be0697311 (public): root
+  
+
+Actual testing
+--------------
+
+  $ hg push --rev 'desc(C0)'
+  pushing to $TESTTMP/server
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)
+  3 new obsolescence markers