diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -150,6 +150,10 @@ class incrementalmissingancestors(object
         '''whether the common set has any non-trivial bases'''
         return self.bases and self.bases != set([nullrev])
 
+    def addbases(self, newbases):
+        '''grow the ancestor set by adding new bases'''
+        self.bases.update(newbases)
+
     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
@@ -45,6 +45,8 @@ class naiveincrementalmissingancestors(o
     def __init__(self, ancs, bases):
         self.ancs = ancs
         self.bases = set(bases)
+    def addbases(self, newbases):
+        self.bases.update(newbases)
     def missingancestors(self, revs):
         res = set()
         for rev in revs:
@@ -97,6 +99,11 @@ def test_missingancestors(seed, rng):
             naiveinc = naiveincrementalmissingancestors(ancs, bases)
             seq = []
             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)