test-ancestor: use random testing for missing ancestors

We're going to make changes to the missing ancestor algorithm, and random
testing will give us much more confidence than a fixed set of tests.

tests/test-ancestor.py

@@ -1,141 +1,211 b''
 from mercurial import ancestor, commands, hg, ui, util
+from mercurial.node import nullrev
+import binascii, getopt, math, os, random, sys, time
+
+def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7):
+    '''nodes: total number of nodes in the graph
+    rootprob: probability that a new node (not 0) will be a root
+    mergeprob: probability that, excluding a root a node will be a merge
+    prevprob: probability that p1 will be the previous node
+
+    return value is a graph represented as an adjacency list.
+    '''
+    graph = [None] * nodes
+    for i in xrange(nodes):
+        if i == 0 or rng.random() < rootprob:
+            graph[i] = [nullrev]
+        elif i == 1:
+            graph[i] = [0]
+        elif rng.random() < mergeprob:
+            if i == 2 or rng.random() < prevprob:
+                # p1 is prev
+                p1 = i - 1
+            else:
+                p1 = rng.randrange(i - 1)
+            p2 = rng.choice(range(0, p1) + range(p1 + 1, i))
+            graph[i] = [p1, p2]
+        elif rng.random() < prevprob:
+            graph[i] = [i - 1]
+        else:
+            graph[i] = [rng.randrange(i - 1)]
+
+    return graph
+
+def buildancestorsets(graph):
+    ancs = [None] * len(graph)
+    for i in xrange(len(graph)):
+        ancs[i] = set([i])
+        if graph[i] == [nullrev]:
+            continue
+        for p in graph[i]:
+            ancs[i].update(ancs[p])
+    return ancs
+
+def naivemissingancestors(ancs, revs, bases):
+    res = set()
+    for rev in revs:
+        if rev != nullrev:
+            res.update(ancs[rev])
+    for base in bases:
+        if base != nullrev:
+            res.difference_update(ancs[base])
+    return sorted(res)
+
+def test_missingancestors(seed, rng):
+    # empirically observed to take around 1 second
+    graphcount = 100
+    testcount = 100
+    nerrs = [0]
+    # the default mu and sigma give us a nice distribution of mostly
+    # single-digit counts (including 0) with some higher ones
+    def lognormrandom(mu, sigma):
+        return int(math.floor(rng.lognormvariate(mu, sigma)))
+
+    def samplerevs(nodes, mu=1.1, sigma=0.8):
+        count = min(lognormrandom(mu, sigma), len(nodes))
+        return rng.sample(nodes, count)
+
+    def err(seed, graph, bases, revs, output, expected):
+        if nerrs[0] == 0:
+            print >> sys.stderr, 'seed:', hex(seed)[:-1]
+        if gerrs[0] == 0:
+            print >> sys.stderr, 'graph:', graph
+        print >> sys.stderr, '* bases:', bases
+        print >> sys.stderr, '* revs: ', revs
+        print >> sys.stderr, '*  output:  ', output
+        print >> sys.stderr, '*  expected:', expected
+        nerrs[0] += 1
+        gerrs[0] += 1
+
+    for g in xrange(graphcount):
+        graph = buildgraph(rng)
+        ancs = buildancestorsets(graph)
+        gerrs = [0]
+        for _ in xrange(testcount):
+            # start from nullrev to include it as a possibility
+            graphnodes = range(nullrev, len(graph))
+            bases = samplerevs(graphnodes)
+            revs = samplerevs(graphnodes)
+
+            # fast algorithm
+            h = ancestor.missingancestors(revs, bases, graph.__getitem__)
+            # reference slow algorithm
+            r = naivemissingancestors(ancs, revs, bases)
+            if h != r:
+                err(seed, graph, bases, revs, h, r)
 
 # graph is a dict of child->parent adjacency lists for this graph:
 # o  13
 # |
 # | o  12
 # | |
 # | | o    11
 # | | |\
 # | | | | o  10
 # | | | | |
 # | o---+ |  9
 # | | | | |
 # o | | | |  8
 #  / / / /
 # | | o |  7
 # | | | |
 # o---+ |  6
 #  / / /
 # | | o  5
 # | |/
 # | o  4
 # | |
 # o |  3
 # | |
 # | o  2
 # |/
 # o  1
 # |
 # o  0
 
 graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4],
          7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9],
          13: [8]}
-pfunc = graph.get
-
-def runmissingancestors(revs, bases):
-    print "%% ancestors of %s and not of %s" % (revs, bases)
-    print ancestor.missingancestors(revs, bases, pfunc)
-
-def test_missingancestors():
-    # Empty revs
-    runmissingancestors([], [1])
-    runmissingancestors([], [])
-
-    # If bases is empty, it's the same as if it were [nullrev]
-    runmissingancestors([12], [])
-
-    # Trivial case: revs == bases
-    runmissingancestors([0], [0])
-    runmissingancestors([4, 5, 6], [6, 5, 4])
-
-    # With nullrev
-    runmissingancestors([-1], [12])
-    runmissingancestors([12], [-1])
-
-    # 9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an
-    # ancestor of 12 but not of 7.
-    runmissingancestors([12], [9])
-    runmissingancestors([9], [12])
-    runmissingancestors([12, 9], [7])
-    runmissingancestors([7, 6], [12])
-
-    # More complex cases
-    runmissingancestors([10], [11, 12])
-    runmissingancestors([11], [10])
-    runmissingancestors([11], [10, 12])
-    runmissingancestors([12], [10])
-    runmissingancestors([12], [11])
-    runmissingancestors([10, 11, 12], [13])
-    runmissingancestors([13], [10, 11, 12])
 
 def genlazyancestors(revs, stoprev=0, inclusive=False):
     print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
            (revs, stoprev, inclusive))
     return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev,
                                   inclusive=inclusive)
 
 def printlazyancestors(s, l):
     print 'membership: %r' % [n for n in l if n in s]
     print 'iteration:  %r' % list(s)
 
 def test_lazyancestors():
     # Empty revs
     s = genlazyancestors([])
     printlazyancestors(s, [3, 0, -1])
 
     # Standard example
     s = genlazyancestors([11, 13])
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
     # Standard with ancestry in the initial set (1 is ancestor of 3)
     s = genlazyancestors([1, 3])
     printlazyancestors(s, [1, -1, 0])
 
     # Including revs
     s = genlazyancestors([11, 13], inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
     # Test with stoprev
     s = genlazyancestors([11, 13], stoprev=6)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
     s = genlazyancestors([11, 13], stoprev=6, inclusive=True)
     printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
 
 
 # The C gca algorithm requires a real repo. These are textual descriptions of
 # DAGs that have been known to be problematic.
 dagtests = [
     '+2*2*2/*3/2',
     '+3*3/*2*2/*4*4/*4/2*4/2*2',
 ]
 def test_gca():
     u = ui.ui()
     for i, dag in enumerate(dagtests):
         repo = hg.repository(u, 'gca%d' % i, create=1)
         cl = repo.changelog
         if not util.safehasattr(cl.index, 'ancestors'):
             # C version not available
             return
 
         commands.debugbuilddag(u, repo, dag)
         # Compare the results of the Python and C versions. This does not
         # include choosing a winner when more than one gca exists -- we make
         # sure both return exactly the same set of gcas.
         for a in cl:
             for b in cl:
                 cgcas = sorted(cl.index.ancestors(a, b))
                 pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b))
                 if cgcas != pygcas:
                     print "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b)
                     print "  C returned:      %s" % cgcas
                     print "  Python returned: %s" % pygcas
 
 def main():
-    test_missingancestors()
+    seed = None
+    opts, args = getopt.getopt(sys.argv[1:], 's:', ['seed='])
+    for o, a in opts:
+        if o in ('-s', '--seed'):
+            seed = long(a, base=0) # accepts base 10 or 16 strings
+
+    if seed is None:
+        try:
+            seed = long(binascii.hexlify(os.urandom(16)), 16)
+        except AttributeError:
+            seed = long(time.time() * 1000)
+
+    rng = random.Random(seed)
+    test_missingancestors(seed, rng)
     test_lazyancestors()
     test_gca()
 
 if __name__ == '__main__':
     main()

tests/test-ancestor.py.out

@@ -1,54 +1,18 b''
-% ancestors of [] and not of [1]
-[]
-% ancestors of [] and not of []
-[]
-% ancestors of [12] and not of []
-[0, 1, 2, 4, 6, 7, 9, 12]
-% ancestors of [0] and not of [0]
-[]
-% ancestors of [4, 5, 6] and not of [6, 5, 4]
-[]
-% ancestors of [-1] and not of [12]
-[]
-% ancestors of [12] and not of [-1]
-[0, 1, 2, 4, 6, 7, 9, 12]
-% ancestors of [12] and not of [9]
-[12]
-% ancestors of [9] and not of [12]
-[]
-% ancestors of [12, 9] and not of [7]
-[6, 9, 12]
-% ancestors of [7, 6] and not of [12]
-[]
-% ancestors of [10] and not of [11, 12]
-[5, 10]
-% ancestors of [11] and not of [10]
-[3, 7, 11]
-% ancestors of [11] and not of [10, 12]
-[3, 11]
-% ancestors of [12] and not of [10]
-[6, 7, 9, 12]
-% ancestors of [12] and not of [11]
-[6, 9, 12]
-% ancestors of [10, 11, 12] and not of [13]
-[0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12]
-% ancestors of [13] and not of [10, 11, 12]
-[8, 13]
 % lazy ancestor set for [], stoprev = 0, inclusive = False
 membership: []
 iteration:  []
 % lazy ancestor set for [11, 13], stoprev = 0, inclusive = False
 membership: [7, 8, 3, 4, 1, 0]
 iteration:  [3, 7, 8, 1, 4, 0, 2]
 % lazy ancestor set for [1, 3], stoprev = 0, inclusive = False
 membership: [1, 0]
 iteration:  [0, 1]
 % lazy ancestor set for [11, 13], stoprev = 0, inclusive = True
 membership: [11, 13, 7, 8, 3, 4, 1, 0]
 iteration:  [11, 13, 3, 7, 8, 1, 4, 0, 2]
 % lazy ancestor set for [11, 13], stoprev = 6, inclusive = False
 membership: [7, 8]
 iteration:  [7, 8]
 % lazy ancestor set for [11, 13], stoprev = 6, inclusive = True
 membership: [11, 13, 7, 8]
 iteration:  [11, 13, 7, 8]