# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 1408492990 25200
# Node ID 8c69262df82dfe118695466bc89a29de348c9233
# Parent  e5adb6935239bf24e71e0280d6081731280dd738
obsstore: add relevantmarkers method

We add a ``relevantmarkers`` method to fetch all markers that seem relevant to a
set of nodes. See function documentation about how this set is computed. This
will let us exchange only the markers that seem "relevant" to the set of
changesets related to a push or a pull.

The approach used to define "relevant" has been successfully tested in evolve
for 6 months.

diff -r e5adb6935239 -r 8c69262df82d mercurial/obsolete.py
--- a/mercurial/obsolete.py	Tue Aug 19 16:53:53 2014 -0700
+++ b/mercurial/obsolete.py	Tue Aug 19 17:03:10 2014 -0700
@@ -385,6 +385,34 @@
         if node.nullid in self.precursors:
             raise util.Abort(_('bad obsolescence marker detected: '
                                'invalid successors nullid'))
+    def relevantmarkers(self, nodes):
+        """return a set of all obsolescence markers relevant to a set of nodes.
+
+        "relevant" to a set of nodes mean:
+
+        - marker that use this changeset as successor
+        - prune marker of direct children on this changeset
+        - recursive application of the two rules on precursors of these markers
+
+        It is a set so you cannot rely on order."""
+
+        pendingnodes = set(nodes)
+        seenmarkers = set()
+        seennodes = set(pendingnodes)
+        precursorsmarkers = self.precursors
+        children = self.children
+        while pendingnodes:
+            direct = set()
+            for current in pendingnodes:
+                direct.update(precursorsmarkers.get(current, ()))
+                pruned = [m for m in children.get(current, ()) if not m[1]]
+                direct.update(pruned)
+            direct -= seenmarkers
+            pendingnodes = set([m[0] for m in direct])
+            seenmarkers |= direct
+            pendingnodes -= seennodes
+            seennodes |= pendingnodes
+        return seenmarkers
 
 def _encodemarkers(markers, addheader=False):
     # Kept separate from flushmarkers(), it will be reused for