[PATCH 15 of 16] ancestor: add a way to remove ancestors of bases from a given set

[Siddharth Agarwal]

# HG changeset patch
# User Siddharth Agarwal <sid0 at fb.com>
# Date 1416022830 28800
#      Fri Nov 14 19:40:30 2014 -0800
# Node ID 58d5580ad38482f1613ee8d639dd5ca849f61476
# Parent  336b35538d436cffe1a3aadea25f75b83b24f134
ancestor: add a way to remove ancestors of bases from a given set

This and missingancestors can share state, which will turn out to be perfect
for set discovery.

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -154,6 +154,32 @@
         '''grow the ancestor set by adding new bases'''
         self.bases.update(newbases)
 
+    def removeancestorsfrom(self, revs):
+        '''remove all ancestors of bases from the set revs (in place)'''
+        bases = self.bases
+        pfunc = self.pfunc
+        revs.difference_update(bases)
+        # nullrev is always an ancestor
+        revs.discard(nullrev)
+        if not revs:
+            return
+        # anything in revs > start is definitely not an ancestor of bases
+        # revs <= start needs to be investigated
+        start = max(bases)
+        keepcount = sum(1 for r in revs if r > start)
+        if len(revs) == keepcount:
+            # no revs to consider
+            return
+
+        for curr in xrange(start, min(revs) - 1, -1):
+            if curr not in bases:
+                continue
+            revs.discard(curr)
+            bases.update(pfunc(curr))
+            if len(revs) == keepcount:
+                # no more potential revs to discard
+                break
+
     def missingancestors(self, revs):
         '''return all the ancestors of revs that are not ancestors of self.bases
 
diff --git a/tests/test-ancestor.py b/tests/test-ancestor.py
--- a/tests/test-ancestor.py
+++ b/tests/test-ancestor.py
@@ -47,6 +47,11 @@
         self.bases = set(bases)
     def addbases(self, newbases):
         self.bases.update(newbases)
+    def removeancestorsfrom(self, revs):
+        for base in self.bases:
+            if base != nullrev:
+                revs.difference_update(self.ancs[base])
+        revs.discard(nullrev)
     def missingancestors(self, revs):
         res = set()
         for rev in revs:
@@ -98,18 +103,31 @@
             # reference slow algorithm
             naiveinc = naiveincrementalmissingancestors(ancs, bases)
             seq = []
+            revs = []
             for _ in xrange(inccount):
                 if rng.random() < 0.2:
                     newbases = samplerevs(graphnodes)
                     seq.append(('addbases', newbases))
                     inc.addbases(newbases)
                     naiveinc.addbases(newbases)
-                revs = samplerevs(graphnodes)
-                seq.append(('missingancestors', revs))
-                h = inc.missingancestors(revs)
-                r = naiveinc.missingancestors(revs)
-                if h != r:
-                    err(seed, graph, bases, seq, h, r)
+                if rng.random() < 0.4:
+                    # larger set so that there are more revs to remove from
+                    revs = samplerevs(graphnodes, mu=1.5)
+                    seq.append(('removeancestorsfrom', revs))
+                    hrevs = set(revs)
+                    rrevs = set(revs)
+                    inc.removeancestorsfrom(hrevs)
+                    naiveinc.removeancestorsfrom(rrevs)
+                    if hrevs != rrevs:
+                        err(seed, graph, bases, seq, sorted(hrevs),
+                            sorted(rrevs))
+                else:
+                    revs = samplerevs(graphnodes)
+                    seq.append(('missingancestors', revs))
+                    h = inc.missingancestors(revs)
+                    r = naiveinc.missingancestors(revs)
+                    if h != r:
+                        err(seed, graph, bases, seq, h, r)
 
 # graph is a dict of child->parent adjacency lists for this graph:
 # o  13