checkheads: upgrade the obsolescence postprocessing logic (issue4354)

The previous logic had many shortcoming (eg: looking at the head only, not
handling prune, etc...), the new logic use a more robust approach:

For each head, we check if after the push all changesets exclusive to this heads
will be obsolete. If they are, the branch considered be "replaced".

To check if a changeset will be obsolete, we simply checks:

* the changeset phase

* the existence of a marker relevant to the "pushed set" that affects the
  changesets..

This fixes two major issues of the previous algorithm:

* branch partially rewritten (eg: head but not root) are no longer detected as
  replaced,

* Prune are now properly handled.

(This implementation was introduction in the evolve extension, version 6.0.0.)

This new algorithm has an extended number of tests, a basic one is provided
in this patch. The others will be introduced in their own changeset for clarity.

In addition, we stop trying to process heads unknown locally, we do not have
enough data to take an informed decision so we should stop pretending we do.
This reflect a test that is now update.

tests/test-push-checkheads-pruned-B1.t

@@ -0,0 +1,72 b''
+====================================
+Testing head checking code: Case B-1
+====================================
+
+Mercurial checks for the introduction of new heads on push. Evolution comes
+into play to detect if existing branches on the server are being replaced by
+some of the new one we push.
+
+This case is part of a series of tests checking this behavior.
+
+Category B: simple case involving pruned changesets
+TestCase 1: single pruned changeset
+
+.. old-state:
+..
+.. * 1 changeset branch
+..
+.. new-state:
+..
+.. * old branch is pruned
+.. * 1 new unrelated branch
+..
+.. expected-result:
+..
+.. * push allowed
+..
+.. graph-summary:
+..
+..       ◔ B
+..       |
+..   A ⊗ |
+..     |/
+..     ●
+
+  $ . $TESTDIR/testlib/push-checkheads-util.sh
+
+Test setup
+----------
+
+  $ mkdir B1
+  $ cd B1
+  $ 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
+  $ hg debugobsolete --record-parents `getid "desc(A0)"`
+  $ hg log -G --hidden
+  @  74ff5441d343 (draft): B0
+  |
+  | x  8aaa48160adc (draft): A0
+  |/
+  o  1e4be0697311 (public): root
+  
+
+Actual testing
+--------------
+
+  $ hg push
+  pushing to $TESTTMP/B1/server (glob)
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)
+  1 new obsolescence markers
+
+  $ cd ../..

mercurial/discovery.py

@@ -7,8 +7,11 b''
 
 from __future__ import absolute_import
 
+import functools
+
 from .i18n import _
 from .node import (
+    hex,
     nullid,
     short,
 )
@@ -17,7 +20,6 b' from . import ('
     bookmarks,
     branchmap,
     error,
-    obsolete,
     phases,
     setdiscovery,
     treediscovery,
@@ -413,38 +415,105 b' def checkheads(pushop):'
 def _postprocessobsolete(pushop, futurecommon, candidate_newhs):
     """post process the list of new heads with obsolescence information
 
-    Exists as a subfunction to contain the complexity and allow extensions to
+    Exists as a sub-function to contain the complexity and allow extensions to
     experiment with smarter logic.
+
     Returns (newheads, discarded_heads) tuple
     """
-    # remove future heads which are actually obsoleted by another
-    # pushed element:
+    # known issue
     #
-    # XXX as above, There are several cases this code does not handle
-    # XXX properly
-    #
-    # (1) if <nh> is public, it won't be affected by obsolete marker
-    #     and a new is created
+    # * We "silently" skip processing on all changeset unknown locally
     #
-    # (2) if the new heads have ancestors which are not obsolete and
-    #     not ancestors of any other heads we will have a new head too.
-    #
-    # These two cases will be easy to handle for known changeset but
-    # much more tricky for unsynced changes.
-    #
-    # In addition, this code is confused by prune as it only looks for
-    # successors of the heads (none if pruned) leading to issue4354
+    # * if <nh> is public on the remote, it won't be affected by obsolete
+    #     marker and a new is created
+
+    # define various utilities and containers
     repo = pushop.repo
-    newhs = set()
-    discarded = set()
-    for nh in candidate_newhs:
-        if nh in repo and repo[nh].phase() <= phases.public:
+    unfi = repo.unfiltered()
+    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)
+    successorsmarkers = unfi.obsstore.successors
+    newhs = set() # final set of new heads
+    discarded = set() # new head of fully replaced branch
+
+    localcandidate = set() # candidate heads known locally
+    unknownheads = set() # candidate heads unknown locally
+    for h in candidate_newhs:
+        if h in unfi:
+            localcandidate.add(h)
+        else:
+            if successorsmarkers.get(h) is not None:
+                msg = ('checkheads: remote head unknown locally has'
+                       ' local marker: %s\n')
+                repo.ui.debug(msg % hex(h))
+            unknownheads.add(h)
+
+    # fast path the simple case
+    if len(localcandidate) == 1:
+        return unknownheads | set(candidate_newhs), set()
+
+    # actually process branch replacement
+    while localcandidate:
+        nh = localcandidate.pop()
+        # run this check early to skip the evaluation of the whole branch
+        if (nh in futurecommon
+                or unfi[nh].phase() <= public):
+            newhs.add(nh)
+            continue
+
+        # Get all revs/nodes on the branch exclusive to this head
+        # (already filtered heads are "ignored"))
+        branchrevs = unfi.revs('only(%n, (%ln+%ln))',
+                               nh, localcandidate, newhs)
+        branchnodes = [tonode(r) for r in branchrevs]
+
+        # The branch won't be hidden 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:
-            for suc in obsolete.allsuccessors(repo.obsstore, [nh]):
-                if suc != nh and suc in futurecommon:
-                    discarded.add(nh)
-                    break
-            else:
-                newhs.add(nh)
+            # note: 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,
+            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
+    discovery might have filtered relevant markers. In addition listing all
+    markers relevant to all changesets in the pushed set would be too expensive
+    (O(len(repo)))
+
+    (note: There are cache opportunity in this function. but it would requires
+    a two dimensional 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

tests/test-obsolete-checkheads.t

@@ -254,9 +254,27 b' setup'
   @  b4952fcf48cf (public) add base
   
 
-Push should not complain about new heads.
+We do not have enought data to take the right decision, we should fail
+
+  $ hg push
+  pushing to $TESTTMP/remote (glob)
+  searching for changes
+  remote has heads on branch 'default' that are not known locally: c70b08862e08
+  abort: push creates new remote head 71e3228bffe1!
+  (pull and merge or see 'hg help push' for details about pushing new heads)
+  [255]
 
-  $ hg push --traceback
+Pulling the missing data makes it work
+
+  $ hg pull
+  pulling from $TESTTMP/remote (glob)
+  searching for changes
+  adding changesets
+  adding manifests
+  adding file changes
+  added 1 changesets with 1 changes to 1 files (+1 heads)
+  (run 'hg heads' to see heads)
+  $ hg push
   pushing to $TESTTMP/remote (glob)
   searching for changes
   adding changesets