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

Submitter Siddharth Agarwal Nov. 16, 2014, 9:17 a.m. <58d5580ad38482f1613e.1416129437@devbig136.prn2.facebook.com> mbox | patch /patch/6761/ Accepted f710644e1ce99a9f422b5a3a7b53d3dae2af36eb show

Siddharth Agarwal - Nov. 16, 2014, 9:17 a.m.
```# HG changeset patch
# User Siddharth Agarwal <sid0@fb.com>
# Date 1416022830 28800
#      Fri Nov 14 19:40:30 2014 -0800
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.
```

## Patch

```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
+        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
+            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)
self.bases.update(newbases)
+    def removeancestorsfrom(self, revs):
+        for base in self.bases:
+            if base != nullrev:
+                revs.difference_update(self.ancs[base])
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)
-                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

```