test-ancestor.py
275 lines
| 8.7 KiB
| text/x-python
|
PythonLexer
/ tests / test-ancestor.py
|
r28723 | from __future__ import absolute_import, print_function | ||
|
r27280 | |||
import binascii | ||||
import getopt | ||||
import math | ||||
import os | ||||
import random | ||||
import sys | ||||
import time | ||||
|
r23331 | from mercurial.node import nullrev | ||
|
r27280 | from mercurial import ( | ||
ancestor, | ||||
|
r30402 | debugcommands, | ||
|
r27280 | hg, | ||
|
r32861 | pycompat, | ||
|
r28774 | ui as uimod, | ||
|
r27280 | util, | ||
) | ||||
|
r23331 | |||
|
r32861 | if pycompat.ispy3: | ||
long = int | ||||
xrange = range | ||||
|
r23331 | def buildgraph(rng, nodes=100, rootprob=0.05, mergeprob=0.2, prevprob=0.7): | ||
'''nodes: total number of nodes in the graph | ||||
rootprob: probability that a new node (not 0) will be a root | ||||
mergeprob: probability that, excluding a root a node will be a merge | ||||
prevprob: probability that p1 will be the previous node | ||||
return value is a graph represented as an adjacency list. | ||||
''' | ||||
graph = [None] * nodes | ||||
for i in xrange(nodes): | ||||
if i == 0 or rng.random() < rootprob: | ||||
graph[i] = [nullrev] | ||||
elif i == 1: | ||||
graph[i] = [0] | ||||
elif rng.random() < mergeprob: | ||||
if i == 2 or rng.random() < prevprob: | ||||
# p1 is prev | ||||
p1 = i - 1 | ||||
else: | ||||
p1 = rng.randrange(i - 1) | ||||
|
r32893 | p2 = rng.choice(list(range(0, p1)) + list(range(p1 + 1, i))) | ||
|
r23331 | graph[i] = [p1, p2] | ||
elif rng.random() < prevprob: | ||||
graph[i] = [i - 1] | ||||
else: | ||||
graph[i] = [rng.randrange(i - 1)] | ||||
return graph | ||||
def buildancestorsets(graph): | ||||
ancs = [None] * len(graph) | ||||
for i in xrange(len(graph)): | ||||
|
r32291 | ancs[i] = {i} | ||
|
r23331 | if graph[i] == [nullrev]: | ||
continue | ||||
for p in graph[i]: | ||||
ancs[i].update(ancs[p]) | ||||
return ancs | ||||
|
r23335 | class naiveincrementalmissingancestors(object): | ||
def __init__(self, ancs, bases): | ||||
self.ancs = ancs | ||||
self.bases = set(bases) | ||||
|
r23341 | def addbases(self, newbases): | ||
self.bases.update(newbases) | ||||
|
r23342 | def removeancestorsfrom(self, revs): | ||
for base in self.bases: | ||||
if base != nullrev: | ||||
revs.difference_update(self.ancs[base]) | ||||
revs.discard(nullrev) | ||||
|
r23335 | def missingancestors(self, revs): | ||
res = set() | ||||
for rev in revs: | ||||
if rev != nullrev: | ||||
res.update(self.ancs[rev]) | ||||
for base in self.bases: | ||||
if base != nullrev: | ||||
res.difference_update(self.ancs[base]) | ||||
return sorted(res) | ||||
|
r23331 | |||
def test_missingancestors(seed, rng): | ||||
# empirically observed to take around 1 second | ||||
graphcount = 100 | ||||
|
r23336 | testcount = 10 | ||
inccount = 10 | ||||
|
r23331 | nerrs = [0] | ||
# the default mu and sigma give us a nice distribution of mostly | ||||
# single-digit counts (including 0) with some higher ones | ||||
def lognormrandom(mu, sigma): | ||||
return int(math.floor(rng.lognormvariate(mu, sigma))) | ||||
def samplerevs(nodes, mu=1.1, sigma=0.8): | ||||
count = min(lognormrandom(mu, sigma), len(nodes)) | ||||
return rng.sample(nodes, count) | ||||
|
r23336 | def err(seed, graph, bases, seq, output, expected): | ||
|
r23331 | if nerrs[0] == 0: | ||
|
r28723 | print('seed:', hex(seed)[:-1], file=sys.stderr) | ||
|
r23331 | if gerrs[0] == 0: | ||
|
r28723 | print('graph:', graph, file=sys.stderr) | ||
print('* bases:', bases, file=sys.stderr) | ||||
print('* seq: ', seq, file=sys.stderr) | ||||
print('* output: ', output, file=sys.stderr) | ||||
print('* expected:', expected, file=sys.stderr) | ||||
|
r23331 | nerrs[0] += 1 | ||
gerrs[0] += 1 | ||||
for g in xrange(graphcount): | ||||
graph = buildgraph(rng) | ||||
ancs = buildancestorsets(graph) | ||||
gerrs = [0] | ||||
for _ in xrange(testcount): | ||||
# start from nullrev to include it as a possibility | ||||
graphnodes = range(nullrev, len(graph)) | ||||
bases = samplerevs(graphnodes) | ||||
# fast algorithm | ||||
|
r23334 | inc = ancestor.incrementalmissingancestors(graph.__getitem__, bases) | ||
|
r23331 | # reference slow algorithm | ||
|
r23335 | naiveinc = naiveincrementalmissingancestors(ancs, bases) | ||
|
r23336 | seq = [] | ||
|
r23342 | revs = [] | ||
|
r23336 | for _ in xrange(inccount): | ||
|
r23341 | if rng.random() < 0.2: | ||
newbases = samplerevs(graphnodes) | ||||
seq.append(('addbases', newbases)) | ||||
inc.addbases(newbases) | ||||
naiveinc.addbases(newbases) | ||||
|
r23342 | if rng.random() < 0.4: | ||
# larger set so that there are more revs to remove from | ||||
revs = samplerevs(graphnodes, mu=1.5) | ||||
seq.append(('removeancestorsfrom', revs)) | ||||
hrevs = set(revs) | ||||
rrevs = set(revs) | ||||
inc.removeancestorsfrom(hrevs) | ||||
naiveinc.removeancestorsfrom(rrevs) | ||||
if hrevs != rrevs: | ||||
err(seed, graph, bases, seq, sorted(hrevs), | ||||
sorted(rrevs)) | ||||
else: | ||||
revs = samplerevs(graphnodes) | ||||
seq.append(('missingancestors', revs)) | ||||
h = inc.missingancestors(revs) | ||||
r = naiveinc.missingancestors(revs) | ||||
if h != r: | ||||
err(seed, graph, bases, seq, h, r) | ||||
|
r18079 | |||
# graph is a dict of child->parent adjacency lists for this graph: | ||||
# o 13 | ||||
# | | ||||
# | o 12 | ||||
# | | | ||||
# | | o 11 | ||||
# | | |\ | ||||
# | | | | o 10 | ||||
# | | | | | | ||||
# | o---+ | 9 | ||||
# | | | | | | ||||
# o | | | | 8 | ||||
# / / / / | ||||
# | | o | 7 | ||||
# | | | | | ||||
# o---+ | 6 | ||||
# / / / | ||||
# | | o 5 | ||||
# | |/ | ||||
# | o 4 | ||||
# | | | ||||
# o | 3 | ||||
# | | | ||||
# | o 2 | ||||
# |/ | ||||
# o 1 | ||||
# | | ||||
# o 0 | ||||
graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], | ||||
7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | ||||
13: [8]} | ||||
|
r18091 | def genlazyancestors(revs, stoprev=0, inclusive=False): | ||
|
r28723 | print(("%% lazy ancestor set for %s, stoprev = %s, inclusive = %s" % | ||
(revs, stoprev, inclusive))) | ||||
|
r23328 | return ancestor.lazyancestors(graph.get, revs, stoprev=stoprev, | ||
|
r18091 | inclusive=inclusive) | ||
def printlazyancestors(s, l): | ||||
|
r28723 | print('membership: %r' % [n for n in l if n in s]) | ||
print('iteration: %r' % list(s)) | ||||
|
r18091 | |||
def test_lazyancestors(): | ||||
# Empty revs | ||||
s = genlazyancestors([]) | ||||
printlazyancestors(s, [3, 0, -1]) | ||||
# Standard example | ||||
s = genlazyancestors([11, 13]) | ||||
printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | ||||
|
r22355 | # Standard with ancestry in the initial set (1 is ancestor of 3) | ||
s = genlazyancestors([1, 3]) | ||||
printlazyancestors(s, [1, -1, 0]) | ||||
|
r18091 | # Including revs | ||
s = genlazyancestors([11, 13], inclusive=True) | ||||
printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | ||||
# Test with stoprev | ||||
s = genlazyancestors([11, 13], stoprev=6) | ||||
printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | ||||
s = genlazyancestors([11, 13], stoprev=6, inclusive=True) | ||||
printlazyancestors(s, [11, 13, 7, 9, 8, 3, 6, 4, 1, -1, 0]) | ||||
|
r19504 | |||
# The C gca algorithm requires a real repo. These are textual descriptions of | ||||
|
r33475 | # DAGs that have been known to be problematic, and, optionally, known pairs | ||
# of revisions and their expected ancestor list. | ||||
|
r19504 | dagtests = [ | ||
|
r36644 | (b'+2*2*2/*3/2', {}), | ||
(b'+3*3/*2*2/*4*4/*4/2*4/2*2', {}), | ||||
(b'+2*2*/2*4*/4*/3*2/4', {(6, 7): [3, 5]}), | ||||
|
r19504 | ] | ||
def test_gca(): | ||||
|
r30559 | u = uimod.ui.load() | ||
|
r33475 | for i, (dag, tests) in enumerate(dagtests): | ||
|
r32894 | repo = hg.repository(u, b'gca%d' % i, create=1) | ||
|
r19504 | cl = repo.changelog | ||
if not util.safehasattr(cl.index, 'ancestors'): | ||||
# C version not available | ||||
return | ||||
|
r30402 | debugcommands.debugbuilddag(u, repo, dag) | ||
|
r19504 | # Compare the results of the Python and C versions. This does not | ||
# include choosing a winner when more than one gca exists -- we make | ||||
# sure both return exactly the same set of gcas. | ||||
|
r33475 | # Also compare against expected results, if available. | ||
|
r19504 | for a in cl: | ||
for b in cl: | ||||
cgcas = sorted(cl.index.ancestors(a, b)) | ||||
pygcas = sorted(ancestor.ancestors(cl.parentrevs, a, b)) | ||||
|
r33475 | expected = None | ||
if (a, b) in tests: | ||||
expected = tests[(a, b)] | ||||
if cgcas != pygcas or (expected and cgcas != expected): | ||||
|
r28723 | print("test_gca: for dag %s, gcas for %d, %d:" | ||
% (dag, a, b)) | ||||
print(" C returned: %s" % cgcas) | ||||
print(" Python returned: %s" % pygcas) | ||||
|
r33475 | if expected: | ||
print(" expected: %s" % expected) | ||||
|
r19504 | |||
|
r23330 | def main(): | ||
|
r23331 | seed = None | ||
opts, args = getopt.getopt(sys.argv[1:], 's:', ['seed=']) | ||||
for o, a in opts: | ||||
if o in ('-s', '--seed'): | ||||
seed = long(a, base=0) # accepts base 10 or 16 strings | ||||
if seed is None: | ||||
try: | ||||
seed = long(binascii.hexlify(os.urandom(16)), 16) | ||||
except AttributeError: | ||||
seed = long(time.time() * 1000) | ||||
rng = random.Random(seed) | ||||
test_missingancestors(seed, rng) | ||||
|
r18091 | test_lazyancestors() | ||
|
r19504 | test_gca() | ||
|
r23330 | |||
if __name__ == '__main__': | ||||
main() | ||||