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