Mercurial > hg
annotate tests/test-ancestor.py @ 48946:642e31cb55f0
py3: use class X: instead of class X(object):
The inheritance from object is implied in Python 3. So this should
be equivalent.
This change was generated via an automated search and replace. So there
may have been some accidental changes.
Differential Revision: https://phab.mercurial-scm.org/D12352
author | Gregory Szorc <gregory.szorc@gmail.com> |
---|---|
date | Mon, 21 Feb 2022 13:08:28 -0700 |
parents | 6000f5b25c9b |
children | 56f98406831b |
rev | line source |
---|---|
27280
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
1 import binascii |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
2 import getopt |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
3 import math |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
4 import os |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
5 import random |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
6 import sys |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
7 import time |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
8 |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
9 from mercurial.node import nullrev |
27280
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
10 from mercurial import ( |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
11 ancestor, |
30402
945f8229b30d
debugcommands: move debugbuilddag
Gregory Szorc <gregory.szorc@gmail.com>
parents:
28774
diff
changeset
|
12 debugcommands, |
27280
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
13 hg, |
32861
20d70df64e93
py3: alias long to int and xrange to range in test-ancestor.py on Python 3
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32291
diff
changeset
|
14 pycompat, |
28774
21a507f9a6cd
tests: alias ui as uimod in test-ancestor
Yuya Nishihara <yuya@tcha.org>
parents:
28723
diff
changeset
|
15 ui as uimod, |
27280
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
16 util, |
4056fdf71aff
tests/test-ancestor: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents:
23342
diff
changeset
|
17 ) |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
18 |
32861
20d70df64e93
py3: alias long to int and xrange to range in test-ancestor.py on Python 3
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32291
diff
changeset
|
19 if pycompat.ispy3: |
20d70df64e93
py3: alias long to int and xrange to range in test-ancestor.py on Python 3
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32291
diff
changeset
|
20 long = int |
20d70df64e93
py3: alias long to int and xrange to range in test-ancestor.py on Python 3
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32291
diff
changeset
|
21 xrange = range |
20d70df64e93
py3: alias long to int and xrange to range in test-ancestor.py on Python 3
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32291
diff
changeset
|
22 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
23 |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
24 def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7): |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
25 """nodes: total number of nodes in the graph |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
26 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
|
27 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
|
28 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
|
29 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
30 return value is a graph represented as an adjacency list. |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
31 """ |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
32 graph = [None] * nodes |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
33 for i in xrange(nodes): |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
34 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
|
35 graph[i] = [nullrev] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
36 elif i == 1: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
37 graph[i] = [0] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
38 elif rng.random() < mergeprob: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
39 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
|
40 # p1 is prev |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
41 p1 = i - 1 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
42 else: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
43 p1 = rng.randrange(i - 1) |
32893
a8dfa35a4130
py3: pass range() into list() to get one explicitly
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32861
diff
changeset
|
44 p2 = rng.choice(list(range(0, p1)) + list(range(p1 + 1, i))) |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
45 graph[i] = [p1, p2] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
46 elif rng.random() < prevprob: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
47 graph[i] = [i - 1] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
48 else: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
49 graph[i] = [rng.randrange(i - 1)] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
50 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
51 return graph |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
52 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
53 |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
54 def buildancestorsets(graph): |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
55 ancs = [None] * len(graph) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
56 for i in xrange(len(graph)): |
32291
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
30559
diff
changeset
|
57 ancs[i] = {i} |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
58 if graph[i] == [nullrev]: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
59 continue |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
60 for p in graph[i]: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
61 ancs[i].update(ancs[p]) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
62 return ancs |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
63 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
64 |
48946
642e31cb55f0
py3: use class X: instead of class X(object):
Gregory Szorc <gregory.szorc@gmail.com>
parents:
48875
diff
changeset
|
65 class naiveincrementalmissingancestors: |
23335
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
66 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
|
67 self.ancs = ancs |
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
68 self.bases = set(bases) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
69 |
23341
bcc3012f8477
ancestor: add a way to add to bases of a missing ancestor object
Siddharth Agarwal <sid0@fb.com>
parents:
23336
diff
changeset
|
70 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
|
71 self.bases.update(newbases) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
72 |
23342
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
73 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
|
74 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
|
75 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
|
76 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
|
77 revs.discard(nullrev) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
78 |
23335
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
79 def missingancestors(self, revs): |
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
80 res = set() |
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
81 for rev in revs: |
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
82 if rev != nullrev: |
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
83 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
|
84 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
|
85 if base != nullrev: |
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
86 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
|
87 return sorted(res) |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
88 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
89 |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
90 def test_missingancestors(seed, rng): |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
91 # 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
|
92 graphcount = 100 |
23336
4178ad511edf
test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents:
23335
diff
changeset
|
93 testcount = 10 |
4178ad511edf
test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents:
23335
diff
changeset
|
94 inccount = 10 |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
95 nerrs = [0] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
96 # 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
|
97 # 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
|
98 def lognormrandom(mu, sigma): |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
99 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
|
100 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
101 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
|
102 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
|
103 return rng.sample(nodes, count) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
104 |
23336
4178ad511edf
test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents:
23335
diff
changeset
|
105 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
|
106 if nerrs[0] == 0: |
28723
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
107 print('seed:', hex(seed)[:-1], file=sys.stderr) |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
108 if gerrs[0] == 0: |
28723
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
109 print('graph:', graph, file=sys.stderr) |
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
110 print('* bases:', bases, file=sys.stderr) |
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
111 print('* seq: ', seq, file=sys.stderr) |
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
112 print('* output: ', output, file=sys.stderr) |
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
113 print('* expected:', expected, file=sys.stderr) |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
114 nerrs[0] += 1 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
115 gerrs[0] += 1 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
116 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
117 for g in xrange(graphcount): |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
118 graph = buildgraph(rng) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
119 ancs = buildancestorsets(graph) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
120 gerrs = [0] |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
121 for _ in xrange(testcount): |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
122 # 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
|
123 graphnodes = range(nullrev, len(graph)) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
124 bases = samplerevs(graphnodes) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
125 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
126 # fast algorithm |
23334
59e6e5dd3605
ancestor.missingancestors: turn into a state-keeping class
Siddharth Agarwal <sid0@fb.com>
parents:
23331
diff
changeset
|
127 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
|
128 # reference slow algorithm |
23335
3f28e8cb3066
test-ancestor: move naive missing ancestor algorithm into a class
Siddharth Agarwal <sid0@fb.com>
parents:
23334
diff
changeset
|
129 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
|
130 seq = [] |
4178ad511edf
test-ancestor: add support for multiple tests against one incremental object
Siddharth Agarwal <sid0@fb.com>
parents:
23335
diff
changeset
|
131 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
|
132 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
|
133 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
|
134 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
|
135 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
|
136 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
|
137 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
|
138 # 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
|
139 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
|
140 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
|
141 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
|
142 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
|
143 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
|
144 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
|
145 if hrevs != rrevs: |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
146 err( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
147 seed, |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
148 graph, |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
149 bases, |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
150 seq, |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
151 sorted(hrevs), |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
152 sorted(rrevs), |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
153 ) |
23342
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
154 else: |
f710644e1ce9
ancestor: add a way to remove ancestors of bases from a given set
Siddharth Agarwal <sid0@fb.com>
parents:
23341
diff
changeset
|
155 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
|
156 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
|
157 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
|
158 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
|
159 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
|
160 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
|
161 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
162 |
18079
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
163 # 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
|
164 # o 13 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
165 # | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
166 # | o 12 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
167 # | | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
168 # | | o 11 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
169 # | | |\ |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
170 # | | | | o 10 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
171 # | | | | | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
172 # | o---+ | 9 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
173 # | | | | | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
174 # o | | | | 8 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
175 # / / / / |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
176 # | | o | 7 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
177 # | | | | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
178 # o---+ | 6 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
179 # / / / |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
180 # | | o 5 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
181 # | |/ |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
182 # | o 4 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
183 # | | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
184 # o | 3 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
185 # | | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
186 # | o 2 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
187 # |/ |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
188 # o 1 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
189 # | |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
190 # o 0 |
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
191 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
192 graph = { |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
193 0: [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
194 1: [0, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
195 2: [1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
196 3: [1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
197 4: [2, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
198 5: [4, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
199 6: [4, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
200 7: [4, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
201 8: [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
202 9: [6, 7], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
203 10: [5, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
204 11: [3, 7], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
205 12: [9, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
206 13: [8, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
207 } |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
208 |
18079
b3ba69692f8a
ancestor: move missingancestors doctest out into a separate file
Siddharth Agarwal <sid0@fb.com>
parents:
diff
changeset
|
209 |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
210 def test_missingancestors_explicit(): |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
211 """A few explicit cases, easier to check for catching errors in refactors. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
212 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
213 The bigger graph at the end has been produced by the random generator |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
214 above, and we have some evidence that the other tests don't cover it. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
215 """ |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
216 for i, (bases, revs) in enumerate( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
217 ( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
218 ({1, 2, 3, 4, 7}, set(xrange(10))), |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
219 ({10}, set({11, 12, 13, 14})), |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
220 ({7}, set({1, 2, 3, 4, 5})), |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
221 ) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
222 ): |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
223 print("%% removeancestorsfrom(), example %d" % (i + 1)) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
224 missanc = ancestor.incrementalmissingancestors(graph.get, bases) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
225 missanc.removeancestorsfrom(revs) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
226 print("remaining (sorted): %s" % sorted(list(revs))) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
227 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
228 for i, (bases, revs) in enumerate( |
45942
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
229 ( |
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
230 ({10}, {11}), |
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
231 ({11}, {10}), |
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
232 ({7}, {9, 11}), |
89a2afe31e82
formating: upgrade to black 20.8b1
Augie Fackler <raf@durin42.com>
parents:
43076
diff
changeset
|
233 ) |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
234 ): |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
235 print("%% missingancestors(), example %d" % (i + 1)) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
236 missanc = ancestor.incrementalmissingancestors(graph.get, bases) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
237 print("return %s" % missanc.missingancestors(revs)) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
238 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
239 print("% removeancestorsfrom(), bigger graph") |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
240 vecgraph = [ |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
241 [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
242 [0, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
243 [1, 0], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
244 [2, 1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
245 [3, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
246 [4, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
247 [5, 1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
248 [2, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
249 [7, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
250 [8, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
251 [9, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
252 [10, 1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
253 [3, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
254 [12, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
255 [13, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
256 [14, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
257 [4, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
258 [16, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
259 [17, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
260 [18, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
261 [19, 11], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
262 [20, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
263 [21, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
264 [22, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
265 [23, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
266 [2, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
267 [3, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
268 [26, 24], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
269 [27, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
270 [28, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
271 [12, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
272 [1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
273 [1, 9], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
274 [32, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
275 [33, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
276 [34, 31], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
277 [35, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
278 [36, 26], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
279 [37, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
280 [38, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
281 [39, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
282 [40, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
283 [41, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
284 [42, 26], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
285 [0, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
286 [44, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
287 [45, 4], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
288 [40, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
289 [47, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
290 [36, 0], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
291 [49, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
292 [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
293 [51, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
294 [52, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
295 [53, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
296 [14, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
297 [55, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
298 [15, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
299 [23, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
300 [58, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
301 [59, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
302 [2, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
303 [61, 59], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
304 [62, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
305 [63, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
306 [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
307 [65, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
308 [66, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
309 [67, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
310 [68, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
311 [37, 28], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
312 [69, 25], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
313 [71, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
314 [72, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
315 [50, 2], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
316 [74, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
317 [12, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
318 [18, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
319 [77, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
320 [78, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
321 [79, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
322 [43, 33], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
323 [81, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
324 [82, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
325 [83, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
326 [84, 45], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
327 [85, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
328 [86, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
329 [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
330 [88, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
331 [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
332 [76, 83], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
333 [44, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
334 [92, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
335 [93, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
336 [9, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
337 [95, 67], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
338 [96, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
339 [97, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
340 [-1, -1], |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
341 ] |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
342 problem_rev = 28 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
343 problem_base = 70 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
344 # problem_rev is a parent of problem_base, but a faulty implementation |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
345 # could forget to remove it. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
346 bases = {60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6} |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
347 if problem_rev not in vecgraph[problem_base] or problem_base not in bases: |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
348 print("Conditions have changed") |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
349 missanc = ancestor.incrementalmissingancestors(vecgraph.__getitem__, bases) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
350 revs = {4, 12, 41, 28, 68, 38, 1, 30, 56, 44} |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
351 missanc.removeancestorsfrom(revs) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
352 if 28 in revs: |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
353 print("Failed!") |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
354 else: |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
355 print("Ok") |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
356 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
357 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
358 def genlazyancestors(revs, stoprev=0, inclusive=False): |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
359 print( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
360 ( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
361 "%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
362 % (revs, stoprev, inclusive) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
363 ) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
364 ) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
365 return ancestor.lazyancestors( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
366 graph.get, revs, stoprev=stoprev, inclusive=inclusive |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
367 ) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
368 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
369 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
370 def printlazyancestors(s, l): |
28723
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
371 print('membership: %r' % [n for n in l if n in s]) |
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
372 print('iteration: %r' % list(s)) |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
373 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
374 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
375 def test_lazyancestors(): |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
376 # Empty revs |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
377 s = genlazyancestors([]) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
378 printlazyancestors(s, [3, 0, -1]) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
379 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
380 # Standard example |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
381 s = genlazyancestors([11, 13]) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
382 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
|
383 |
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
|
384 # 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
|
385 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
|
386 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
|
387 |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
388 # Including revs |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
389 s = genlazyancestors([11, 13], inclusive=True) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
390 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
|
391 |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
392 # Test with stoprev |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
393 s = genlazyancestors([11, 13], stoprev=6) |
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
394 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
|
395 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
|
396 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
|
397 |
39475
431068d7e9db
ancestor: add test showing inconsistency between __iter__ and __contains__
Yuya Nishihara <yuya@tcha.org>
parents:
36626
diff
changeset
|
398 # Test with stoprev >= min(initrevs) |
431068d7e9db
ancestor: add test showing inconsistency between __iter__ and __contains__
Yuya Nishihara <yuya@tcha.org>
parents:
36626
diff
changeset
|
399 s = genlazyancestors([11, 13], stoprev=11, inclusive=True) |
431068d7e9db
ancestor: add test showing inconsistency between __iter__ and __contains__
Yuya Nishihara <yuya@tcha.org>
parents:
36626
diff
changeset
|
400 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
431068d7e9db
ancestor: add test showing inconsistency between __iter__ and __contains__
Yuya Nishihara <yuya@tcha.org>
parents:
36626
diff
changeset
|
401 s = genlazyancestors([11, 13], stoprev=12, inclusive=True) |
431068d7e9db
ancestor: add test showing inconsistency between __iter__ and __contains__
Yuya Nishihara <yuya@tcha.org>
parents:
36626
diff
changeset
|
402 printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
403 |
39536
bdb177923291
ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents:
39535
diff
changeset
|
404 # Contiguous chains: 5->4, 2->1 (where 1 is in seen set), 1->0 |
bdb177923291
ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents:
39535
diff
changeset
|
405 s = genlazyancestors([10, 1], inclusive=True) |
bdb177923291
ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents:
39535
diff
changeset
|
406 printlazyancestors(s, [2, 10, 4, 5, -1, 0, 1]) |
bdb177923291
ancestor: optimize _lazyancestorsiter() for contiguous chains
Yuya Nishihara <yuya@tcha.org>
parents:
39535
diff
changeset
|
407 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
408 |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
409 # The C gca algorithm requires a real repo. These are textual descriptions of |
33475
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
410 # DAGs that have been known to be problematic, and, optionally, known pairs |
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
411 # of revisions and their expected ancestor list. |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
412 dagtests = [ |
36626
6754d0c5e1b5
py3: make test-ancestors.py pass on Python 3 with C extensions
Yuya Nishihara <yuya@tcha.org>
parents:
33475
diff
changeset
|
413 (b'+2*2*2/*3/2', {}), |
6754d0c5e1b5
py3: make test-ancestors.py pass on Python 3 with C extensions
Yuya Nishihara <yuya@tcha.org>
parents:
33475
diff
changeset
|
414 (b'+3*3/*2*2/*4*4/*4/2*4/2*2', {}), |
6754d0c5e1b5
py3: make test-ancestors.py pass on Python 3 with C extensions
Yuya Nishihara <yuya@tcha.org>
parents:
33475
diff
changeset
|
415 (b'+2*2*/2*4*/4*/3*2/4', {(6, 7): [3, 5]}), |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
416 ] |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
417 |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
418 |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
419 def test_gca(): |
30559
d83ca854fa21
ui: factor out ui.load() to create a ui without loading configs (API)
Yuya Nishihara <yuya@tcha.org>
parents:
30402
diff
changeset
|
420 u = uimod.ui.load() |
33475
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
421 for i, (dag, tests) in enumerate(dagtests): |
32894
ec9ed269edc3
py3: pass the path in hg.repository() as bytes
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32893
diff
changeset
|
422 repo = hg.repository(u, b'gca%d' % i, create=1) |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
423 cl = repo.changelog |
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
424 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
|
425 # C version not available |
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
426 return |
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
427 |
30402
945f8229b30d
debugcommands: move debugbuilddag
Gregory Szorc <gregory.szorc@gmail.com>
parents:
28774
diff
changeset
|
428 debugcommands.debugbuilddag(u, repo, dag) |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
429 # 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
|
430 # 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
|
431 # sure both return exactly the same set of gcas. |
33475
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
432 # Also compare against expected results, if available. |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
433 for a in cl: |
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
434 for b in cl: |
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
435 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
|
436 pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b)) |
33475
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
437 expected = None |
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
438 if (a, b) in tests: |
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
439 expected = tests[(a, b)] |
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
440 if cgcas != pygcas or (expected and cgcas != expected): |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
441 print( |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
442 "test_gca: for dag %s, gcas for %d, %d:" % (dag, a, b) |
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
443 ) |
28723
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
444 print(" C returned: %s" % cgcas) |
18e738038d78
py3: use print_function in test-ancestor.py
Robert Stanca <robert.stanca7@gmail.com>
parents:
27280
diff
changeset
|
445 print(" Python returned: %s" % pygcas) |
33475
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
446 if expected: |
f501322512b6
parsers: fix invariant bug in find_deepest (issue5623)
Sune Foldager <cryo@cyanite.org>
parents:
32894
diff
changeset
|
447 print(" expected: %s" % expected) |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
448 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
449 |
23330
37c3731d8a58
test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents:
23329
diff
changeset
|
450 def main(): |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
451 seed = None |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
452 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
|
453 for o, a in opts: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
454 if o in ('-s', '--seed'): |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
455 seed = long(a, base=0) # accepts base 10 or 16 strings |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
456 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
457 if seed is None: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
458 try: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
459 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
|
460 except AttributeError: |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
461 seed = long(time.time() * 1000) |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
462 |
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
463 rng = random.Random(seed) |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
39536
diff
changeset
|
464 test_missingancestors_explicit() |
23331
3b1b8f25443e
test-ancestor: use random testing for missing ancestors
Siddharth Agarwal <sid0@fb.com>
parents:
23330
diff
changeset
|
465 test_missingancestors(seed, rng) |
18091
f7f8159caad3
ancestor: add lazy membership testing to lazyancestors
Siddharth Agarwal <sid0@fb.com>
parents:
18079
diff
changeset
|
466 test_lazyancestors() |
19504
2fa303619b4d
ancestor.deepest: ignore ninteresting while building result (issue3984)
Siddharth Agarwal <sid0@fb.com>
parents:
18091
diff
changeset
|
467 test_gca() |
23330
37c3731d8a58
test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents:
23329
diff
changeset
|
468 |
43076
2372284d9457
formatting: blacken the codebase
Augie Fackler <augie@google.com>
parents:
41365
diff
changeset
|
469 |
23330
37c3731d8a58
test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents:
23329
diff
changeset
|
470 if __name__ == '__main__': |
37c3731d8a58
test-ancestor: define a main function
Siddharth Agarwal <sid0@fb.com>
parents:
23329
diff
changeset
|
471 main() |