Mercurial > hg
annotate tests/test-ancestor.py @ 46858:85e3a630cad9
revlog: move the details of revlog "v2" index inside revlog.utils.constants
the revlog module is quite large and this kind of format information would handy
for other module. So let us start to gather this information about the format in
a more appropriate place.
We update various reference to this information to use the new "source of truth"
in the process.
Differential Revision: https://phab.mercurial-scm.org/D10305
author | Pierre-Yves David <pierre-yves.david@octobus.net> |
---|---|
date | Mon, 05 Apr 2021 12:21:12 +0200 |
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() |