annotate tests/test-ancestor.py @ 24385:885a573fa619

patch.pathtransform: prepend prefix even if strip is 0 Silly oversight by me.
author Siddharth Agarwal <sid0@fb.com>
date Wed, 18 Mar 2015 20:59:06 -0700
parents f710644e1ce9
children 4056fdf71aff
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
19504
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
1 from mercurial import ancestor, commands, hg, ui, util
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
2 from mercurial.node import nullrev
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
3 import binascii, getopt, math, os, random, sys, time
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
4
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
5 def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
6 '''nodes: total number of nodes in the graph
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
7 rootprob: probability that a new node (not 0) will be a root
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
8 mergeprob: probability that, excluding a root a node will be a merge
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
9 prevprob: probability that p1 will be the previous node
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
10
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
11 return value is a graph represented as an adjacency list.
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
12 '''
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
13 graph = [None] * nodes
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
14 for i in xrange(nodes):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
15 if i == 0 or rng.random() < rootprob:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
16 graph[i] = [nullrev]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
17 elif i == 1:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
18 graph[i] = [0]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
19 elif rng.random() < mergeprob:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
20 if i == 2 or rng.random() < prevprob:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
21 # p1 is prev
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
22 p1 = i - 1
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
23 else:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
24 p1 = rng.randrange(i - 1)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
25 p2 = rng.choice(range(0, p1) + range(p1 + 1, i))
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
26 graph[i] = [p1, p2]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
27 elif rng.random() < prevprob:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
28 graph[i] = [i - 1]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
29 else:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
30 graph[i] = [rng.randrange(i - 1)]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
31
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
32 return graph
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
33
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
34 def buildancestorsets(graph):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
35 ancs = [None] * len(graph)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
36 for i in xrange(len(graph)):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
37 ancs[i] = set([i])
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
38 if graph[i] == [nullrev]:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
39 continue
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
40 for p in graph[i]:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
41 ancs[i].update(ancs[p])
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
42 return ancs
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
43
23335
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
44 class naiveincrementalmissingancestors(object):
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
45 def __init__(self, ancs, bases):
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
46 self.ancs = ancs
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
47 self.bases = set(bases)
23341
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
48 def addbases(self, newbases):
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
49 self.bases.update(newbases)
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
50 def removeancestorsfrom(self, revs):
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
51 for base in self.bases:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
52 if base != nullrev:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
53 revs.difference_update(self.ancs[base])
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
54 revs.discard(nullrev)
23335
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
55 def missingancestors(self, revs):
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
56 res = set()
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
57 for rev in revs:
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
58 if rev != nullrev:
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
59 res.update(self.ancs[rev])
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
60 for base in self.bases:
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
61 if base != nullrev:
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
62 res.difference_update(self.ancs[base])
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
63 return sorted(res)
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
64
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
65 def test_missingancestors(seed, rng):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
66 # empirically observed to take around 1 second
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
67 graphcount = 100
23336
4178ad511edf test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents: 23335
diff changeset
68 testcount = 10
4178ad511edf test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents: 23335
diff changeset
69 inccount = 10
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
70 nerrs = [0]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
71 # the default mu and sigma give us a nice distribution of mostly
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
72 # single-digit counts (including 0) with some higher ones
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
73 def lognormrandom(mu, sigma):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
74 return int(math.floor(rng.lognormvariate(mu, sigma)))
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
75
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
76 def samplerevs(nodes, mu=1.1, sigma=0.8):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
77 count = min(lognormrandom(mu, sigma), len(nodes))
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
78 return rng.sample(nodes, count)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
79
23336
4178ad511edf test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents: 23335
diff changeset
80 def err(seed, graph, bases, seq, output, expected):
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
81 if nerrs[0] == 0:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
82 print >> sys.stderr, 'seed:', hex(seed)[:-1]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
83 if gerrs[0] == 0:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
84 print >> sys.stderr, 'graph:', graph
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
85 print >> sys.stderr, '* bases:', bases
23336
4178ad511edf test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents: 23335
diff changeset
86 print >> sys.stderr, '* seq: ', seq
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
87 print >> sys.stderr, '* output: ', output
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
88 print >> sys.stderr, '* expected:', expected
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
89 nerrs[0] += 1
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
90 gerrs[0] += 1
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
91
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
92 for g in xrange(graphcount):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
93 graph = buildgraph(rng)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
94 ancs = buildancestorsets(graph)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
95 gerrs = [0]
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
96 for _ in xrange(testcount):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
97 # start from nullrev to include it as a possibility
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
98 graphnodes = range(nullrev, len(graph))
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
99 bases = samplerevs(graphnodes)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
100
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
101 # fast algorithm
23334
59e6e5dd3605 ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents: 23331
diff changeset
102 inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases)
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
103 # reference slow algorithm
23335
3f28e8cb3066 test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents: 23334
diff changeset
104 naiveinc = naiveincrementalmissingancestors(ancs, bases)
23336
4178ad511edf test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents: 23335
diff changeset
105 seq = []
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
106 revs = []
23336
4178ad511edf test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents: 23335
diff changeset
107 for _ in xrange(inccount):
23341
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
108 if rng.random() < 0.2:
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
109 newbases = samplerevs(graphnodes)
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
110 seq.append(('addbases', newbases))
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
111 inc.addbases(newbases)
bcc3012f8477 ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents: 23336
diff changeset
112 naiveinc.addbases(newbases)
23342
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
113 if rng.random() < 0.4:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
114 # larger set so that there are more revs to remove from
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
115 revs = samplerevs(graphnodes, mu=1.5)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
116 seq.append(('removeancestorsfrom', revs))
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
117 hrevs = set(revs)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
118 rrevs = set(revs)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
119 inc.removeancestorsfrom(hrevs)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
120 naiveinc.removeancestorsfrom(rrevs)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
121 if hrevs != rrevs:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
122 err(seed, graph, bases, seq, sorted(hrevs),
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
123 sorted(rrevs))
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
124 else:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
125 revs = samplerevs(graphnodes)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
126 seq.append(('missingancestors', revs))
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
127 h = inc.missingancestors(revs)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
128 r = naiveinc.missingancestors(revs)
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
129 if h != r:
f710644e1ce9 ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents: 23341
diff changeset
130 err(seed, graph, bases, seq, h, r)
18079
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
131
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
132 # graph is a dict of child->parent adjacency lists for this graph:
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
133 # o 13
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
134 # |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
135 # | o 12
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
136 # | |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
137 # | | o 11
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
138 # | | |\
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
139 # | | | | o 10
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
140 # | | | | |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
141 # | o---+ | 9
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
142 # | | | | |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
143 # o | | | | 8
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
144 # / / / /
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
145 # | | o | 7
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
146 # | | | |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
147 # o---+ | 6
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
148 # / / /
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
149 # | | o 5
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
150 # | |/
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
151 # | o 4
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
152 # | |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
153 # o | 3
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
154 # | |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
155 # | o 2
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
156 # |/
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
157 # o 1
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
158 # |
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
159 # o 0
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
160
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
161 graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4],
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
162 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9],
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
163 13: [8]}
b3ba69692f8a ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff changeset
164
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
165 def genlazyancestors(revs, stoprev=0, inclusive=False):
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
166 print ("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" %
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
167 (revs, stoprev, inclusive))
23328
3a7d9c0c57a5 ancestor.lazyancestors: take parentrevs function rather than changelog
Siddharth Agarwal <sid0@fb.com>
parents: 22355
diff changeset
168 return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev,
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
169 inclusive=inclusive)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
170
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
171 def printlazyancestors(s, l):
23329
c6cd4b8b76f8 test-ancestor: test iteration for lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23328
diff changeset
172 print 'membership: %r' % [n for n in l if n in s]
c6cd4b8b76f8 test-ancestor: test iteration for lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23328
diff changeset
173 print 'iteration: %r' % list(s)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
174
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
175 def test_lazyancestors():
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
176 # Empty revs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
177 s = genlazyancestors([])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
178 printlazyancestors(s, [3, 0, -1])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
179
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
180 # Standard example
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
181 s = genlazyancestors([11, 13])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
182 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
183
22355
731b2a90983b test-ancestor: add a test for `ancestor` with ancestry within the initset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21024
diff changeset
184 # Standard with ancestry in the initial set (1 is ancestor of 3)
731b2a90983b test-ancestor: add a test for `ancestor` with ancestry within the initset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21024
diff changeset
185 s = genlazyancestors([1, 3])
731b2a90983b test-ancestor: add a test for `ancestor` with ancestry within the initset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21024
diff changeset
186 printlazyancestors(s, [1, -1, 0])
731b2a90983b test-ancestor: add a test for `ancestor` with ancestry within the initset
Pierre-Yves David <pierre-yves.david@fb.com>
parents: 21024
diff changeset
187
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
188 # Including revs
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
189 s = genlazyancestors([11, 13], inclusive=True)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
190 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
191
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
192 # Test with stoprev
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
193 s = genlazyancestors([11, 13], stoprev=6)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
194 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
195 s = genlazyancestors([11, 13], stoprev=6, inclusive=True)
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
196 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0])
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
197
19504
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
198
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
199 # The C gca algorithm requires a real repo. These are textual descriptions of
21024
7731a2281cf0 spelling: fixes from spell checker
Mads Kiilerich <madski@unity3d.com>
parents: 19504
diff changeset
200 # DAGs that have been known to be problematic.
19504
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
201 dagtests = [
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
202 '+2*2*2/*3/2',
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
203 '+3*3/*2*2/*4*4/*4/2*4/2*2',
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
204 ]
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
205 def test_gca():
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
206 u = ui.ui()
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
207 for i, dag in enumerate(dagtests):
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
208 repo = hg.repository(u, 'gca%d' % i, create=1)
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
209 cl = repo.changelog
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
210 if not util.safehasattr(cl.index, 'ancestors'):
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
211 # C version not available
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
212 return
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
213
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
214 commands.debugbuilddag(u, repo, dag)
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
215 # Compare the results of the Python and C versions. This does not
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
216 # include choosing a winner when more than one gca exists -- we make
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
217 # sure both return exactly the same set of gcas.
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
218 for a in cl:
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
219 for b in cl:
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
220 cgcas = sorted(cl.index.ancestors(a, b))
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
221 pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b))
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
222 if cgcas != pygcas:
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
223 print "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b)
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
224 print " C returned: %s" % cgcas
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
225 print " Python returned: %s" % pygcas
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
226
23330
37c3731d8a58 test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents: 23329
diff changeset
227 def main():
23331
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
228 seed = None
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
229 opts, args = getopt.getopt(sys.argv[1:], 's:', ['seed='])
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
230 for o, a in opts:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
231 if o in ('-s', '--seed'):
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
232 seed = long(a, base=0) # accepts base 10 or 16 strings
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
233
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
234 if seed is None:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
235 try:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
236 seed = long(binascii.hexlify(os.urandom(16)), 16)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
237 except AttributeError:
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
238 seed = long(time.time() * 1000)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
239
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
240 rng = random.Random(seed)
3b1b8f25443e test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents: 23330
diff changeset
241 test_missingancestors(seed, rng)
18091
f7f8159caad3 ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents: 18079
diff changeset
242 test_lazyancestors()
19504
2fa303619b4d ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents: 18091
diff changeset
243 test_gca()
23330
37c3731d8a58 test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents: 23329
diff changeset
244
37c3731d8a58 test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents: 23329
diff changeset
245 if __name__ == '__main__':
37c3731d8a58 test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents: 23329
diff changeset
246 main()