obsolete: add a function to compute "exclusive-markers" for a set of nodes

This set will be used to select the obsmarkers to be stripped alongside the
stripped changesets. See the function docstring for details.

More advanced testing is introduced in the next changesets to keep this one
simpler. That extra testing provides more example.

mercurial/debugcommands.py

@@ -1313,6 +1313,8 b' def debugnamecomplete(ui, repo, *args):'
          ('', 'record-parents', False,
           _('record parent information for the precursor')),
          ('r', 'rev', [], _('display markers relevant to REV')),
+         ('', 'exclusive', False, _('restrict display to markers only '
+                                    'relevant to REV')),
          ('', 'index', False, _('display index of the marker')),
          ('', 'delete', [], _('delete markers specified by indices')),
         ] + cmdutil.commitopts2 + cmdutil.formatteropts,
@@ -1391,7 +1393,8 b' def debugobsolete(ui, repo, precursor=No'
         if opts['rev']:
             revs = scmutil.revrange(repo, opts['rev'])
             nodes = [repo[r].node() for r in revs]
-            markers = list(obsolete.getmarkers(repo, nodes=nodes))
+            markers = list(obsolete.getmarkers(repo, nodes=nodes,
+                                               exclusive=opts['exclusive']))
             markers.sort(key=lambda x: x._data)
         else:
             markers = obsolete.getmarkers(repo)

mercurial/obsolete.py

@@ -737,6 +737,129 b' class obsstore(object):'
             seennodes |= pendingnodes
         return seenmarkers
 
+def _filterprunes(markers):
+    """return a set with no prune markers"""
+    return set(m for m in markers if m[1])
+
+def exclusivemarkers(repo, nodes):
+    """set of markers relevant to "nodes" but no other locally-known nodes
+
+    This function compute the set of markers "exclusive" to a locally-known
+    node. This means we walk the markers starting from <nodes> until we reach a
+    locally-known precursors outside of <nodes>. Element of <nodes> with
+    locally-known successors outside of <nodes> are ignored (since their
+    precursors markers are also relevant to these successors).
+
+    For example:
+
+        # (A0 rewritten as A1)
+        #
+        # A0 <-1- A1 # Marker "1" is exclusive to A1
+
+        or
+
+        # (A0 rewritten as AX; AX rewritten as A1; AX is unkown locally)
+        #
+        # <-1- A0 <-2- AX <-3- A1 # Marker "2,3" are exclusive to A1
+
+        or
+
+        # (A0 has unknown precursors, A0 rewritten as A1 and A2 (divergence))
+        #
+        #          <-2- A1 # Marker "2" is exclusive to A0,A1
+        #        /
+        # <-1- A0
+        #        \
+        #         <-3- A2 # Marker "3" is exclusive to A0,A2
+        #
+        # in addition:
+        #
+        #  Markers "2,3" are exclusive to A1,A2
+        #  Markers "1,2,3" are exclusive to A0,A1,A2
+
+    An example usage is strip. When stripping a changeset, we also want to
+    strip the markers exclusive to this changeset. Otherwise we would have
+    "dangling"" obsolescence markers from its precursors: Obsolescence markers
+    marking a node as obsolete without any successors available locally.
+
+    As for relevant markers, the prune markers for children will be followed.
+    Of course, they will only be followed if the pruned children is
+    locally-known. Since the prune markers are relevant to the pruned node.
+    However, while prune markers are considered relevant to the parent of the
+    pruned changesets, prune markers for locally-known changeset (with no
+    successors) are considered exclusive to the pruned nodes. This allows
+    to strip the prune markers (with the rest of the exclusive chain) alongside
+    the pruned changesets.
+    """
+    # running on a filtered repository would be dangerous as markers could be
+    # reported as exclusive when they are relevant for other filtered nodes.
+    unfi = repo.unfiltered()
+
+    # shortcut to various useful item
+    nm = unfi.changelog.nodemap
+    precursorsmarkers = unfi.obsstore.precursors
+    successormarkers = unfi.obsstore.successors
+    childrenmarkers = unfi.obsstore.children
+
+    # exclusive markers (return of the function)
+    exclmarkers = set()
+    # we need fast membership testing
+    nodes = set(nodes)
+    # looking for head in the obshistory
+    #
+    # XXX we are ignoring all issues in regard with cycle for now.
+    stack = [n for n in nodes if not _filterprunes(successormarkers.get(n, ()))]
+    stack.sort()
+    # nodes already stacked
+    seennodes = set(stack)
+    while stack:
+        current = stack.pop()
+        # fetch precursors markers
+        markers = list(precursorsmarkers.get(current, ()))
+        # extend the list with prune markers
+        for mark in successormarkers.get(current, ()):
+            if not mark[1]:
+                markers.append(mark)
+        # and markers from children (looking for prune)
+        for mark in childrenmarkers.get(current, ()):
+            if not mark[1]:
+                markers.append(mark)
+        # traverse the markers
+        for mark in markers:
+            if mark in exclmarkers:
+                # markers already selected
+                continue
+
+            # If the markers is about the current node, select it
+            #
+            # (this delay the addition of markers from children)
+            if mark[1] or mark[0] == current:
+                exclmarkers.add(mark)
+
+            # should we keep traversing through the precursors?
+            prec = mark[0]
+
+            # nodes in the stack or already processed
+            if prec in seennodes:
+                continue
+
+            # is this a locally known node ?
+            known = prec in nm
+            # if locally-known and not in the <nodes> set the traversal
+            # stop here.
+            if known and prec not in nodes:
+                continue
+
+            # do not keep going if there are unselected markers pointing to this
+            # nodes. If we end up traversing these unselected markers later the
+            # node will be taken care of at that point.
+            precmarkers = _filterprunes(successormarkers.get(prec))
+            if precmarkers.issubset(exclmarkers):
+                seennodes.add(prec)
+                stack.append(prec)
+
+    return exclmarkers
+
 def commonversion(versions):
     """Return the newest version listed in both versions and our local formats.
 
@@ -804,13 +927,15 b' def pushmarker(repo, key, old, new):'
     finally:
         lock.release()
 
-def getmarkers(repo, nodes=None):
+def getmarkers(repo, nodes=None, exclusive=False):
     """returns markers known in a repository
 
     If <nodes> is specified, only markers "relevant" to those nodes are are
     returned"""
     if nodes is None:
         rawmarkers = repo.obsstore
+    elif exclusive:
+        rawmarkers = exclusivemarkers(repo, nodes)
     else:
         rawmarkers = repo.obsstore.relevantmarkers(nodes)
 

tests/test-completion.t

@@ -272,7 +272,7 b' Show all commands + options'
   debuglocks: force-lock, force-wlock
   debugmergestate: 
   debugnamecomplete: 
-  debugobsolete: flags, record-parents, rev, index, delete, date, user, template
+  debugobsolete: flags, record-parents, rev, exclusive, index, delete, date, user, template
   debugpathcomplete: full, normal, added, removed
   debugpickmergetool: rev, changedelete, include, exclude, tool
   debugpushkey: 

tests/test-obsolete.t

@@ -267,6 +267,42 b' We need to create a clone of 5 and add a'
   o  0:1f0dee641bb7 (public) [ ] add a
   
 
+Basic exclusive testing
+
+  $ hg log -G --hidden
+  @  6:6f9641995072 (draft) [tip ] add n3w_3_c
+  |
+  | x  5:5601fb93a350 (draft *obsolete*) [ ] add new_3_c
+  |/
+  | x  4:ca819180edb9 (draft *obsolete*) [ ] add new_2_c
+  |/
+  | x  3:cdbce2fbb163 (draft *obsolete*) [ ] add new_c
+  |/
+  | o  2:245bde4270cd (public) [ ] add original_c
+  |/
+  o  1:7c3bad9141dc (public) [ ] add b
+  |
+  o  0:1f0dee641bb7 (public) [ ] add a
+  
+  $ hg debugobsolete --rev 6f9641995072
+  1337133713371337133713371337133713371337 5601fb93a350734d935195fee37f4054c529ff39 0 (Thu Jan 01 00:22:19 1970 +0000) {'user': 'test'}
+  245bde4270cd1072a27757984f9cda8ba26f08ca cdbce2fbb16313928851e97e0d85413f3f7eb77f C (Thu Jan 01 00:00:01 1970 -0002) {'user': 'test'}
+  5601fb93a350734d935195fee37f4054c529ff39 6f96419950729f3671185b847352890f074f7557 1 (Thu Jan 01 00:22:18 1970 +0000) {'user': 'test'}
+  ca819180edb99ed25ceafb3e9584ac287e240b00 1337133713371337133713371337133713371337 0 (Thu Jan 01 00:22:18 1970 +0000) {'user': 'test'}
+  cdbce2fbb16313928851e97e0d85413f3f7eb77f ca819180edb99ed25ceafb3e9584ac287e240b00 0 (Thu Jan 01 00:22:17 1970 +0000) {'user': 'test'}
+  $ hg debugobsolete --rev 6f9641995072 --exclusive
+  5601fb93a350734d935195fee37f4054c529ff39 6f96419950729f3671185b847352890f074f7557 1 (Thu Jan 01 00:22:18 1970 +0000) {'user': 'test'}
+  $ hg debugobsolete --rev 5601fb93a350 --hidden
+  1337133713371337133713371337133713371337 5601fb93a350734d935195fee37f4054c529ff39 0 (Thu Jan 01 00:22:19 1970 +0000) {'user': 'test'}
+  245bde4270cd1072a27757984f9cda8ba26f08ca cdbce2fbb16313928851e97e0d85413f3f7eb77f C (Thu Jan 01 00:00:01 1970 -0002) {'user': 'test'}
+  ca819180edb99ed25ceafb3e9584ac287e240b00 1337133713371337133713371337133713371337 0 (Thu Jan 01 00:22:18 1970 +0000) {'user': 'test'}
+  cdbce2fbb16313928851e97e0d85413f3f7eb77f ca819180edb99ed25ceafb3e9584ac287e240b00 0 (Thu Jan 01 00:22:17 1970 +0000) {'user': 'test'}
+  $ hg debugobsolete --rev 5601fb93a350 --hidden --exclusive
+  $ hg debugobsolete --rev 5601fb93a350+6f9641995072 --hidden --exclusive
+  1337133713371337133713371337133713371337 5601fb93a350734d935195fee37f4054c529ff39 0 (Thu Jan 01 00:22:19 1970 +0000) {'user': 'test'}
+  5601fb93a350734d935195fee37f4054c529ff39 6f96419950729f3671185b847352890f074f7557 1 (Thu Jan 01 00:22:18 1970 +0000) {'user': 'test'}
+  ca819180edb99ed25ceafb3e9584ac287e240b00 1337133713371337133713371337133713371337 0 (Thu Jan 01 00:22:18 1970 +0000) {'user': 'test'}
+
   $ cd ..
 
 Revision 0 is hidden