[PATCH] obsolete: add detection of divergent sets for a given node

[Kostia Balytskyi]

# HG changeset patch
# User Kostia Balytskyi <ikostia at fb.com>
# Date 1458512982 25200
#      Sun Mar 20 15:29:42 2016 -0700
# Node ID 93524966df1be6573e06373c804a9cfbbfa2ea21
# Parent  c776481f8adab3e1c69be977bb621d82bacc397d
obsolete: add detection of divergent sets for a given node

Originally, this was implemented in evolve extensions, but Pierre-Yves
expressed a wish for this to be moved to core in order for the potential
reuse.

Once this is accepted, I will change evolve --list implementation to use this.

Please see function's docstring for details on what it returns.

diff --git a/mercurial/obsolete.py b/mercurial/obsolete.py
--- a/mercurial/obsolete.py
+++ b/mercurial/obsolete.py
@@ -1280,3 +1280,37 @@ def isenabled(repo, option):
                            "if other obsolete options are enabled"))
 
     return option in result
+
+def divergentsets(repo, node):
+    """Compute sets of commits divergent with a given one
+
+    Returns a list of 2-element tuples, like this:
+    [(set1, com_prec1), (set2, com_prec2), ...]
+    where set1 is a set of ctx objects divergent with a given node
+    and com_prec1 is a common precursor between node and set1.
+
+    Please note, that set1 is a full successor for com_prec1 (e.g.
+    at some point some successor of com_prec1 was split into multiple
+    commits).
+    """
+    cache = {}
+    succsets = {}
+    base = {}
+    for n in obsolete.allprecursors(repo.obsstore, [node]):
+        if n == node:
+            # a node can't be a base for divergence with itself
+            continue
+        nsuccsets = obsolete.successorssets(repo, n, cache)
+        for nsuccset in nsuccsets:
+            if node in nsuccset:
+                # we are only interested in *other* successor sets
+                continue
+            if tuple(nsuccset) in base:
+                # we already know the latest base for this divergency
+                continue
+            base[tuple(nsuccset)] = n
+    divergence = []
+    for divset, b in base.iteritems():
+        divergence.append((divset, b))
+
+    return divergence