To get this branch, use:
bzr branch
http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar
« back to all changes in this revision
Viewing changes to breezy/tests/test_graph.py
- browse files at revision 6973.5.2
- compare with another revision
- compare with revision 5200.2.3
- download diff
- download tarball
- view history from revision 6973.5.2
- Committer: Jelmer Vernooij
- Date: 2018-05-22 02:05:12 UTC
- mto: (6973.12.2 python3-k)
- mto: This revision was merged to the branch mainline in revision 6992.
- Revision ID: jelmer@jelmer.uk-20180522020512-btpj2jchdlehi3en
Add more bees.
- files modified:
- breezy/graph.py
added
removed
breezy/tests/test_graph.py
34
34
# rev3 /
35
35
# | /
36
36
# rev4
37
ancestry_1 = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
38
'rev3': ['rev2a'], 'rev4': ['rev3', 'rev2b']}
37
ancestry_1 = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'],
38
b'rev3': [b'rev2a'], b'rev4': [b'rev3', b'rev2b']}
39
39
40
40
41
41
# Ancestry 2:
49
49
# rev3a
50
50
# |
51
51
# rev4a
52
ancestry_2 = {'rev1a': [NULL_REVISION], 'rev2a': ['rev1a'],
53
'rev1b': [NULL_REVISION], 'rev3a': ['rev2a'], 'rev4a': ['rev3a']}
52
ancestry_2 = {b'rev1a': [NULL_REVISION], b'rev2a': [b'rev1a'],
53
b'rev1b': [NULL_REVISION], b'rev3a': [b'rev2a'], b'rev4a': [b'rev3a']}
54
54
55
55
56
56
# Criss cross ancestry
64
64
# | X |
65
65
# |/ \|
66
66
# rev3a rev3b
67
criss_cross = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'], 'rev2b': ['rev1'],
68
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2a']}
67
criss_cross = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'], b'rev2b': [b'rev1'],
68
b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2a']}
69
69
70
70
71
71
# Criss-cross 2
79
79
# | / \ |
80
80
# |/ \|
81
81
# rev2a rev2b
82
criss_cross2 = {'rev1a': [NULL_REVISION], 'rev1b': [NULL_REVISION],
83
'rev2a': ['rev1a', 'rev1b'], 'rev2b': ['rev1b', 'rev1a']}
82
criss_cross2 = {b'rev1a': [NULL_REVISION], b'rev1b': [NULL_REVISION],
83
b'rev2a': [b'rev1a', b'rev1b'], b'rev2b': [b'rev1b', b'rev1a']}
84
84
85
85
86
86
# Mainline:
92
92
# | rev2b
93
93
# | /
94
94
# rev2a
95
mainline = {'rev1': [NULL_REVISION], 'rev2a': ['rev1', 'rev2b'],
96
'rev2b': ['rev1']}
95
mainline = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1', b'rev2b'],
96
b'rev2b': [b'rev1']}
97
97
98
98
99
99
# feature branch:
105
105
# rev2b
106
106
# |
107
107
# rev3b
108
feature_branch = {'rev1': [NULL_REVISION],
109
'rev2b': ['rev1'], 'rev3b': ['rev2b']}
108
feature_branch = {b'rev1': [NULL_REVISION],
109
b'rev2b': [b'rev1'], b'rev3b': [b'rev2b']}
110
110
111
111
112
112
# History shortcut
117
117
# rev2a rev2b rev2c
118
118
# | / \ /
119
119
# rev3a rev3b
120
history_shortcut = {'rev1': [NULL_REVISION], 'rev2a': ['rev1'],
121
'rev2b': ['rev1'], 'rev2c': ['rev1'],
122
'rev3a': ['rev2a', 'rev2b'], 'rev3b': ['rev2b', 'rev2c']}
120
history_shortcut = {b'rev1': [NULL_REVISION], b'rev2a': [b'rev1'],
121
b'rev2b': [b'rev1'], b'rev2c': [b'rev1'],
122
b'rev3a': [b'rev2a', b'rev2b'], b'rev3b': [b'rev2b', b'rev2c']}
123
123
124
124
# Extended history shortcut
125
125
# NULL_REVISION
133
133
# d |
134
134
# |\|
135
135
# e f
136
extended_history_shortcut = {'a': [NULL_REVISION],
137
'b': ['a'],
138
'c': ['b'],
139
'd': ['c'],
140
'e': ['d'],
141
'f': ['a', 'd'],
136
extended_history_shortcut = {b'a': [NULL_REVISION],
137
b'b': [b'a'],
138
b'c': [b'b'],
139
b'd': [b'c'],
140
b'e': [b'd'],
141
b'f': [b'a', b'd'],
142
142
}
143
143
144
144
# Double shortcut
145
# Both sides will see 'A' first, even though it is actually a decendent of a
145
# Both sides will see b'A' first, even though it is actually a decendent of a
146
146
# different common revision.
147
147
#
148
148
# NULL_REVISION
157
157
# |/ \|
158
158
# f g
159
159
160
double_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
161
'd':['c'], 'e':['c'], 'f':['a', 'd'],
162
'g':['a', 'e']}
160
double_shortcut = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'],
161
b'd':[b'c'], b'e':[b'c'], b'f':[b'a', b'd'],
162
b'g':[b'a', b'e']}
163
163
164
164
# Complex shortcut
165
165
# This has a failure mode in that a shortcut will find some nodes in common,
189
189
# | l |
190
190
# |/|/
191
191
# m n
192
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
193
'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
194
'i':['e', 'g'], 'j':['g'], 'k':['j'],
195
'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
192
complex_shortcut = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'], b'd':[b'c'],
193
b'e':[b'd'], b'f':[b'd'], b'g':[b'f'], b'h':[b'f'],
194
b'i':[b'e', b'g'], b'j':[b'g'], b'k':[b'j'],
195
b'l':[b'k'], b'm':[b'i', b'l'], b'n':[b'l', b'h']}
196
196
197
197
# NULL_REVISION
198
198
# |
232
232
# | | |
233
233
# |/|/
234
234
# t u
235
complex_shortcut2 = {'a': [NULL_REVISION], 'b': ['a'], 'c': ['b'], 'd': ['c'],
236
'e': ['d'], 'f': ['e'], 'g': ['f'], 'h': ['d'], 'i': ['g'],
237
'j': ['h'], 'k': ['h', 'i'], 'l': ['k'], 'm': ['l'], 'n': ['m'],
238
'o': ['n'], 'p': ['o'], 'q': ['p'], 'r': ['q'], 's': ['r'],
239
't': ['i', 's'], 'u': ['s', 'j'],
235
complex_shortcut2 = {b'a': [NULL_REVISION], b'b': [b'a'], b'c': [b'b'], b'd': [b'c'],
236
b'e': [b'd'], b'f': [b'e'], b'g': [b'f'], b'h': [b'd'], b'i': [b'g'],
237
b'j': [b'h'], b'k': [b'h', b'i'], b'l': [b'k'], b'm': [b'l'], b'n': [b'm'],
238
b'o': [b'n'], b'p': [b'o'], b'q': [b'p'], b'r': [b'q'], b's': [b'r'],
239
b't': [b'i', b's'], b'u': [b's', b'j'],
240
240
}
241
241
242
242
# Graph where different walkers will race to find the common and uncommon
290
290
# k-n exists so that the second pass still has nodes that are worth searching,
291
291
# rather than instantly cancelling the extra walker.
292
292
293
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
294
'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
295
'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
296
'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
297
'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
293
racing_shortcuts = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'], b'd':[b'c'],
294
b'e':[b'd'], b'f':[b'e'], b'g':[b'f'], b'h':[b'g'], b'i':[b'h', b'o'], b'j':[b'i', b'y'],
295
b'k':[b'd'], b'l':[b'k'], b'm':[b'l'], b'n':[b'm'], b'o':[b'n', b'g'], b'p':[b'f'],
296
b'q':[b'p', b'm'], b'r':[b'o'], b's':[b'r'], b't':[b's'], b'u':[b't'], b'v':[b'u'],
297
b'w':[b'v'], b'x':[b'w'], b'y':[b'x'], b'z':[b'x', b'q']}
298
298
299
299
300
300
# A graph with multiple nodes unique to one side.
336
336
# y z
337
337
#
338
338
339
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
340
'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
341
'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
342
'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
343
't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
344
'y':['j', 'x'], 'z':['x', 'p']}
339
multiple_interesting_unique = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'],
340
b'd':[b'c'], b'e':[b'd'], b'f':[b'd'], b'g':[b'e'], b'h':[b'e'], b'i':[b'f'],
341
b'j':[b'g'], b'k':[b'g'], b'l':[b'h'], b'm':[b'i'], b'n':[b'k', b'l'],
342
b'o':[b'm'], b'p':[b'm', b'l'], b'q':[b'n', b'o'], b'r':[b'q'], b's':[b'r'],
343
b't':[b's'], b'u':[b't'], b'v':[b'u'], b'w':[b'v'], b'x':[b'w'],
344
b'y':[b'j', b'x'], b'z':[b'x', b'p']}
345
345
346
346
347
347
# Shortcut with extra root
358
358
# d | g
359
359
# |\|/
360
360
# e f
361
shortcut_extra_root = {'a': [NULL_REVISION],
362
'b': ['a'],
363
'c': ['b'],
364
'd': ['c'],
365
'e': ['d'],
366
'f': ['a', 'd', 'g'],
367
'g': [NULL_REVISION],
361
shortcut_extra_root = {b'a': [NULL_REVISION],
362
b'b': [b'a'],
363
b'c': [b'b'],
364
b'd': [b'c'],
365
b'e': [b'd'],
366
b'f': [b'a', b'd', b'g'],
367
b'g': [NULL_REVISION],
368
368
}
369
369
370
370
# NULL_REVISION
377
377
# | \ |
378
378
# a c
379
379
380
boundary = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e'], 'e': ['f'],
381
'f':[NULL_REVISION]}
380
boundary = {b'a': [b'b'], b'c': [b'b', b'd'], b'b':[b'e'], b'd':[b'e'], b'e': [b'f'],
381
b'f':[NULL_REVISION]}
382
382
383
383
384
384
# A graph that contains a ghost
392
392
# | \ |
393
393
# a c
394
394
395
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
396
'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
395
with_ghost = {b'a': [b'b'], b'c': [b'b', b'd'], b'b':[b'e'], b'd':[b'e', b'g'],
396
b'e': [b'f'], b'f':[NULL_REVISION], NULL_REVISION:()}
397
397
398
398
# A graph that shows we can shortcut finding revnos when reaching them from the
399
399
# side.
415
415
# |
416
416
# i
417
417
418
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
419
'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
418
with_tail = {b'a':[NULL_REVISION], b'b':[b'a'], b'c':[b'b'], b'd':[b'c'], b'e':[b'd'],
419
b'f':[b'e'], b'g':[b'e'], b'h':[b'f'], b'i':[b'h']}
420
420
421
421
422
422
class InstrumentedParentsProvider(object):
531
531
self.assertEqual({NULL_REVISION},
532
532
graph.find_lca(NULL_REVISION, NULL_REVISION))
533
533
self.assertEqual({NULL_REVISION},
534
graph.find_lca(NULL_REVISION, 'rev1'))
535
self.assertEqual({'rev1'}, graph.find_lca('rev1', 'rev1'))
536
self.assertEqual({'rev1'}, graph.find_lca('rev2a', 'rev2b'))
534
graph.find_lca(NULL_REVISION, b'rev1'))
535
self.assertEqual({b'rev1'}, graph.find_lca(b'rev1', b'rev1'))
536
self.assertEqual({b'rev1'}, graph.find_lca(b'rev2a', b'rev2b'))
537
537
538
538
def test_no_unique_lca(self):
539
539
"""Test error when one revision is not in the graph"""
540
540
graph = self.make_graph(ancestry_1)
541
541
self.assertRaises(errors.NoCommonAncestor, graph.find_unique_lca,
542
'rev1', '1rev')
542
b'rev1', b'1rev')
543
543
544
544
def test_lca_criss_cross(self):
545
545
"""Test least-common-ancestor after a criss-cross merge."""
546
546
graph = self.make_graph(criss_cross)
547
self.assertEqual({'rev2a', 'rev2b'},
548
graph.find_lca('rev3a', 'rev3b'))
549
self.assertEqual({'rev2b'},
550
graph.find_lca('rev3a', 'rev3b', 'rev2b'))
547
self.assertEqual({b'rev2a', b'rev2b'},
548
graph.find_lca(b'rev3a', b'rev3b'))
549
self.assertEqual({b'rev2b'},
550
graph.find_lca(b'rev3a', b'rev3b', b'rev2b'))
551
551
552
552
def test_lca_shortcut(self):
553
553
"""Test least-common ancestor on this history shortcut"""
554
554
graph = self.make_graph(history_shortcut)
555
self.assertEqual({'rev2b'}, graph.find_lca('rev3a', 'rev3b'))
555
self.assertEqual({b'rev2b'}, graph.find_lca(b'rev3a', b'rev3b'))
556
556
557
557
def test_lefthand_distance_smoke(self):
558
558
"""A simple does it work test for graph.lefthand_distance(keys)."""
559
559
graph = self.make_graph(history_shortcut)
560
distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
561
self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
560
distance_graph = graph.find_lefthand_distances([b'rev3b', b'rev2a'])
561
self.assertEqual({b'rev2a': 2, b'rev3b': 3}, distance_graph)
562
562
563
563
def test_lefthand_distance_ghosts(self):
564
564
"""A simple does it work test for graph.lefthand_distance(keys)."""
565
nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
565
nodes = {b'nonghost': [NULL_REVISION], b'toghost': [b'ghost']}
566
566
graph = self.make_graph(nodes)
567
distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
568
self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
567
distance_graph = graph.find_lefthand_distances([b'nonghost', b'toghost'])
568
self.assertEqual({b'nonghost': 1, b'toghost': -1}, distance_graph)
569
569
570
570
def test_recursive_unique_lca(self):
571
571
"""Test finding a unique least common ancestor.
576
576
self.assertEqual(NULL_REVISION,
577
577
graph.find_unique_lca(NULL_REVISION, NULL_REVISION))
578
578
self.assertEqual(NULL_REVISION,
579
graph.find_unique_lca(NULL_REVISION, 'rev1'))
580
self.assertEqual('rev1', graph.find_unique_lca('rev1', 'rev1'))
581
self.assertEqual('rev1', graph.find_unique_lca('rev2a', 'rev2b'))
582
self.assertEqual(('rev1', 1,),
583
graph.find_unique_lca('rev2a', 'rev2b',
579
graph.find_unique_lca(NULL_REVISION, b'rev1'))
580
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev1', b'rev1'))
581
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev2a', b'rev2b'))
582
self.assertEqual((b'rev1', 1,),
583
graph.find_unique_lca(b'rev2a', b'rev2b',
584
584
count_steps=True))
585
585
586
586
def assertRemoveDescendants(self, expected, graph, revisions):
590
590
591
591
def test__remove_simple_descendants(self):
592
592
graph = self.make_graph(ancestry_1)
593
self.assertRemoveDescendants({'rev1'}, graph,
594
{'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'})
593
self.assertRemoveDescendants({b'rev1'}, graph,
594
{b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'})
595
595
596
596
def test__remove_simple_descendants_disjoint(self):
597
597
graph = self.make_graph(ancestry_1)
598
self.assertRemoveDescendants({'rev1', 'rev3'}, graph,
599
{'rev1', 'rev3'})
598
self.assertRemoveDescendants({b'rev1', b'rev3'}, graph,
599
{b'rev1', b'rev3'})
600
600
601
601
def test__remove_simple_descendants_chain(self):
602
602
graph = self.make_graph(ancestry_1)
603
self.assertRemoveDescendants({'rev1'}, graph,
604
{'rev1', 'rev2a', 'rev3'})
603
self.assertRemoveDescendants({b'rev1'}, graph,
604
{b'rev1', b'rev2a', b'rev3'})
605
605
606
606
def test__remove_simple_descendants_siblings(self):
607
607
graph = self.make_graph(ancestry_1)
608
self.assertRemoveDescendants({'rev2a', 'rev2b'}, graph,
609
{'rev2a', 'rev2b', 'rev3'})
608
self.assertRemoveDescendants({b'rev2a', b'rev2b'}, graph,
609
{b'rev2a', b'rev2b', b'rev3'})
610
610
611
611
def test_unique_lca_criss_cross(self):
612
612
"""Ensure we don't pick non-unique lcas in a criss-cross"""
613
613
graph = self.make_graph(criss_cross)
614
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
615
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
616
self.assertEqual('rev1', lca)
614
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev3a', b'rev3b'))
615
lca, steps = graph.find_unique_lca(b'rev3a', b'rev3b', count_steps=True)
616
self.assertEqual(b'rev1', lca)
617
617
self.assertEqual(2, steps)
618
618
619
619
def test_unique_lca_null_revision(self):
620
620
"""Ensure we pick NULL_REVISION when necessary"""
621
621
graph = self.make_graph(criss_cross2)
622
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
622
self.assertEqual(b'rev1b', graph.find_unique_lca(b'rev2a', b'rev1b'))
623
623
self.assertEqual(NULL_REVISION,
624
graph.find_unique_lca('rev2a', 'rev2b'))
624
graph.find_unique_lca(b'rev2a', b'rev2b'))
625
625
626
626
def test_unique_lca_null_revision2(self):
627
627
"""Ensure we pick NULL_REVISION when necessary"""
628
628
graph = self.make_graph(ancestry_2)
629
629
self.assertEqual(NULL_REVISION,
630
graph.find_unique_lca('rev4a', 'rev1b'))
630
graph.find_unique_lca(b'rev4a', b'rev1b'))
631
631
632
632
def test_lca_double_shortcut(self):
633
633
graph = self.make_graph(double_shortcut)
634
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
634
self.assertEqual(b'c', graph.find_unique_lca(b'f', b'g'))
635
635
636
636
def test_common_ancestor_two_repos(self):
637
637
"""Ensure we do unique_lca using data from two repos"""
647
647
648
648
graph = mainline_tree.branch.repository.get_graph(
649
649
feature_tree.branch.repository)
650
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
650
self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))
651
651
652
652
def test_graph_difference(self):
653
653
graph = self.make_graph(ancestry_1)
654
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
655
self.assertEqual((set(), {'rev1'}),
656
graph.find_difference(NULL_REVISION, 'rev1'))
657
self.assertEqual(({'rev1'}, set()),
658
graph.find_difference('rev1', NULL_REVISION))
659
self.assertEqual(({'rev2a', 'rev3'}, {'rev2b'}),
660
graph.find_difference('rev3', 'rev2b'))
661
self.assertEqual(({'rev4', 'rev3', 'rev2a'}, set()),
662
graph.find_difference('rev4', 'rev2b'))
654
self.assertEqual((set(), set()), graph.find_difference(b'rev1', b'rev1'))
655
self.assertEqual((set(), {b'rev1'}),
656
graph.find_difference(NULL_REVISION, b'rev1'))
657
self.assertEqual(({b'rev1'}, set()),
658
graph.find_difference(b'rev1', NULL_REVISION))
659
self.assertEqual(({b'rev2a', b'rev3'}, {b'rev2b'}),
660
graph.find_difference(b'rev3', b'rev2b'))
661
self.assertEqual(({b'rev4', b'rev3', b'rev2a'}, set()),
662
graph.find_difference(b'rev4', b'rev2b'))
663
663
664
664
def test_graph_difference_separate_ancestry(self):
665
665
graph = self.make_graph(ancestry_2)
666
self.assertEqual(({'rev1a'}, {'rev1b'}),
667
graph.find_difference('rev1a', 'rev1b'))
668
self.assertEqual(({'rev1a', 'rev2a', 'rev3a', 'rev4a'},
669
{'rev1b'}),
670
graph.find_difference('rev4a', 'rev1b'))
666
self.assertEqual(({b'rev1a'}, {b'rev1b'}),
667
graph.find_difference(b'rev1a', b'rev1b'))
668
self.assertEqual(({b'rev1a', b'rev2a', b'rev3a', b'rev4a'},
669
{b'rev1b'}),
670
graph.find_difference(b'rev4a', b'rev1b'))
671
671
672
672
def test_graph_difference_criss_cross(self):
673
673
graph = self.make_graph(criss_cross)
674
self.assertEqual(({'rev3a'}, {'rev3b'}),
675
graph.find_difference('rev3a', 'rev3b'))
676
self.assertEqual((set([]), {'rev3b', 'rev2b'}),
677
graph.find_difference('rev2a', 'rev3b'))
674
self.assertEqual(({b'rev3a'}, {b'rev3b'}),
675
graph.find_difference(b'rev3a', b'rev3b'))
676
self.assertEqual((set([]), {b'rev3b', b'rev2b'}),
677
graph.find_difference(b'rev2a', b'rev3b'))
678
678
679
679
def test_graph_difference_extended_history(self):
680
680
graph = self.make_graph(extended_history_shortcut)
681
self.assertEqual(({'e'}, {'f'}),
682
graph.find_difference('e', 'f'))
683
self.assertEqual(({'f'}, {'e'}),
684
graph.find_difference('f', 'e'))
681
self.assertEqual(({b'e'}, {b'f'}),
682
graph.find_difference(b'e', b'f'))
683
self.assertEqual(({b'f'}, {b'e'}),
684
graph.find_difference(b'f', b'e'))
685
685
686
686
def test_graph_difference_double_shortcut(self):
687
687
graph = self.make_graph(double_shortcut)
688
self.assertEqual(({'d', 'f'}, {'e', 'g'}),
689
graph.find_difference('f', 'g'))
688
self.assertEqual(({b'd', b'f'}, {b'e', b'g'}),
689
graph.find_difference(b'f', b'g'))
690
690
691
691
def test_graph_difference_complex_shortcut(self):
692
692
graph = self.make_graph(complex_shortcut)
693
self.assertEqual(({'m', 'i', 'e'}, {'n', 'h'}),
694
graph.find_difference('m', 'n'))
693
self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}),
694
graph.find_difference(b'm', b'n'))
695
695
696
696
def test_graph_difference_complex_shortcut2(self):
697
697
graph = self.make_graph(complex_shortcut2)
698
self.assertEqual(({'t'}, {'j', 'u'}),
699
graph.find_difference('t', 'u'))
698
self.assertEqual(({b't'}, {b'j', b'u'}),
699
graph.find_difference(b't', b'u'))
700
700
701
701
def test_graph_difference_shortcut_extra_root(self):
702
702
graph = self.make_graph(shortcut_extra_root)
703
self.assertEqual(({'e'}, {'f', 'g'}),
704
graph.find_difference('e', 'f'))
703
self.assertEqual(({b'e'}, {b'f', b'g'}),
704
graph.find_difference(b'e', b'f'))
705
705
706
706
def test_iter_topo_order(self):
707
707
graph = self.make_graph(ancestry_1)
708
args = ['rev2a', 'rev3', 'rev1']
708
args = [b'rev2a', b'rev3', b'rev1']
709
709
topo_args = list(graph.iter_topo_order(args))
710
710
self.assertEqual(set(args), set(topo_args))
711
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
712
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
711
self.assertTrue(topo_args.index(b'rev2a') > topo_args.index(b'rev1'))
712
self.assertTrue(topo_args.index(b'rev2a') < topo_args.index(b'rev3'))
713
713
714
714
def test_is_ancestor(self):
715
715
graph = self.make_graph(ancestry_1)
716
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
717
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
718
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
719
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
720
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
721
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
722
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
723
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
724
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
716
self.assertEqual(True, graph.is_ancestor(b'null:', b'null:'))
717
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev1'))
718
self.assertEqual(False, graph.is_ancestor(b'rev1', b'null:'))
719
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev4'))
720
self.assertEqual(False, graph.is_ancestor(b'rev4', b'null:'))
721
self.assertEqual(False, graph.is_ancestor(b'rev4', b'rev2b'))
722
self.assertEqual(True, graph.is_ancestor(b'rev2b', b'rev4'))
723
self.assertEqual(False, graph.is_ancestor(b'rev2b', b'rev3'))
724
self.assertEqual(False, graph.is_ancestor(b'rev3', b'rev2b'))
725
725
instrumented_provider = InstrumentedParentsProvider(graph)
726
726
instrumented_graph = _mod_graph.Graph(instrumented_provider)
727
instrumented_graph.is_ancestor('rev2a', 'rev2b')
728
self.assertTrue('null:' not in instrumented_provider.calls)
727
instrumented_graph.is_ancestor(b'rev2a', b'rev2b')
728
self.assertTrue(b'null:' not in instrumented_provider.calls)
729
729
730
730
def test_is_between(self):
731
731
graph = self.make_graph(ancestry_1)
732
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
733
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
734
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
735
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
736
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
737
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
738
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
739
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
732
self.assertEqual(True, graph.is_between(b'null:', b'null:', b'null:'))
733
self.assertEqual(True, graph.is_between(b'rev1', b'null:', b'rev1'))
734
self.assertEqual(True, graph.is_between(b'rev1', b'rev1', b'rev4'))
735
self.assertEqual(True, graph.is_between(b'rev4', b'rev1', b'rev4'))
736
self.assertEqual(True, graph.is_between(b'rev3', b'rev1', b'rev4'))
737
self.assertEqual(False, graph.is_between(b'rev4', b'rev1', b'rev3'))
738
self.assertEqual(False, graph.is_between(b'rev1', b'rev2a', b'rev4'))
739
self.assertEqual(False, graph.is_between(b'null:', b'rev1', b'rev4'))
740
740
741
741
def test_is_ancestor_boundary(self):
742
742
"""Ensure that we avoid searching the whole graph.
747
747
graph = self.make_graph(boundary)
748
748
instrumented_provider = InstrumentedParentsProvider(graph)
749
749
graph = _mod_graph.Graph(instrumented_provider)
750
self.assertFalse(graph.is_ancestor('a', 'c'))
751
self.assertTrue('null:' not in instrumented_provider.calls)
750
self.assertFalse(graph.is_ancestor(b'a', b'c'))
751
self.assertTrue(b'null:' not in instrumented_provider.calls)
752
752
753
753
def test_iter_ancestry(self):
754
754
nodes = boundary.copy()
755
755
nodes[NULL_REVISION] = ()
756
756
graph = self.make_graph(nodes)
757
757
expected = nodes.copy()
758
expected.pop('a') # 'a' is not in the ancestry of 'c', all the
758
expected.pop(b'a') # b'a' is not in the ancestry of b'c', all the
759
759
# other nodes are
760
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
761
self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
760
self.assertEqual(expected, dict(graph.iter_ancestry([b'c'])))
761
self.assertEqual(nodes, dict(graph.iter_ancestry([b'a', b'c'])))
762
762
763
763
def test_iter_ancestry_with_ghost(self):
764
764
graph = self.make_graph(with_ghost)
765
765
expected = with_ghost.copy()
766
# 'a' is not in the ancestry of 'c', and 'g' is a ghost
767
expected['g'] = None
768
self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
769
expected.pop('a')
770
self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
766
# b'a' is not in the ancestry of b'c', and b'g' is a ghost
767
expected[b'g'] = None
768
self.assertEqual(expected, dict(graph.iter_ancestry([b'a', b'c'])))
769
expected.pop(b'a')
770
self.assertEqual(expected, dict(graph.iter_ancestry([b'c'])))
771
771
772
772
def test_filter_candidate_lca(self):
773
773
"""Test filter_candidate_lca for a corner case
774
774
775
This tests the case where we encounter the end of iteration for 'e'
776
in the same pass as we discover that 'd' is an ancestor of 'e', and
777
therefore 'e' can't be an lca.
775
This tests the case where we encounter the end of iteration for b'e'
776
in the same pass as we discover that b'd' is an ancestor of b'e', and
777
therefore b'e' can't be an lca.
778
778
779
779
To compensate for different dict orderings on other Python
780
implementations, we mirror 'd' and 'e' with 'b' and 'a'.
780
implementations, we mirror b'd' and b'e' with b'b' and b'a'.
781
781
"""
782
782
# This test is sensitive to the iteration order of dicts. It will
783
# pass incorrectly if 'e' and 'a' sort before 'c'
783
# pass incorrectly if b'e' and b'a' sort before b'c'
784
784
#
785
785
# NULL_REVISION
786
786
# / \
789
789
# b d
790
790
# \ /
791
791
# c
792
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
793
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
794
self.assertEqual({'c'}, graph.heads(['a', 'c', 'e']))
792
graph = self.make_graph({b'c': [b'b', b'd'], b'd': [b'e'], b'b': [b'a'],
793
b'a': [NULL_REVISION], b'e': [NULL_REVISION]})
794
self.assertEqual({b'c'}, graph.heads([b'a', b'c', b'e']))
795
795
796
796
def test_heads_null(self):
797
797
graph = self.make_graph(ancestry_1)
798
self.assertEqual({'null:'}, graph.heads(['null:']))
799
self.assertEqual({'rev1'}, graph.heads(['null:', 'rev1']))
800
self.assertEqual({'rev1'}, graph.heads(['rev1', 'null:']))
801
self.assertEqual({'rev1'}, graph.heads({'rev1', 'null:'}))
802
self.assertEqual({'rev1'}, graph.heads(('rev1', 'null:')))
798
self.assertEqual({b'null:'}, graph.heads([b'null:']))
799
self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1']))
800
self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:']))
801
self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'}))
802
self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:')))
803
803
804
804
def test_heads_one(self):
805
805
# A single node will always be a head
806
806
graph = self.make_graph(ancestry_1)
807
self.assertEqual({'null:'}, graph.heads(['null:']))
808
self.assertEqual({'rev1'}, graph.heads(['rev1']))
809
self.assertEqual({'rev2a'}, graph.heads(['rev2a']))
810
self.assertEqual({'rev2b'}, graph.heads(['rev2b']))
811
self.assertEqual({'rev3'}, graph.heads(['rev3']))
812
self.assertEqual({'rev4'}, graph.heads(['rev4']))
807
self.assertEqual({b'null:'}, graph.heads([b'null:']))
808
self.assertEqual({b'rev1'}, graph.heads([b'rev1']))
809
self.assertEqual({b'rev2a'}, graph.heads([b'rev2a']))
810
self.assertEqual({b'rev2b'}, graph.heads([b'rev2b']))
811
self.assertEqual({b'rev3'}, graph.heads([b'rev3']))
812
self.assertEqual({b'rev4'}, graph.heads([b'rev4']))
813
813
814
814
def test_heads_single(self):
815
815
graph = self.make_graph(ancestry_1)
816
self.assertEqual({'rev4'}, graph.heads(['null:', 'rev4']))
817
self.assertEqual({'rev2a'}, graph.heads(['rev1', 'rev2a']))
818
self.assertEqual({'rev2b'}, graph.heads(['rev1', 'rev2b']))
819
self.assertEqual({'rev3'}, graph.heads(['rev1', 'rev3']))
820
self.assertEqual({'rev4'}, graph.heads(['rev1', 'rev4']))
821
self.assertEqual({'rev4'}, graph.heads(['rev2a', 'rev4']))
822
self.assertEqual({'rev4'}, graph.heads(['rev2b', 'rev4']))
823
self.assertEqual({'rev4'}, graph.heads(['rev3', 'rev4']))
816
self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4']))
817
self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a']))
818
self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b']))
819
self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3']))
820
self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4']))
821
self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4']))
822
self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4']))
823
self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4']))
824
824
825
825
def test_heads_two_heads(self):
826
826
graph = self.make_graph(ancestry_1)
827
self.assertEqual({'rev2a', 'rev2b'},
828
graph.heads(['rev2a', 'rev2b']))
829
self.assertEqual({'rev3', 'rev2b'},
830
graph.heads(['rev3', 'rev2b']))
827
self.assertEqual({b'rev2a', b'rev2b'},
828
graph.heads([b'rev2a', b'rev2b']))
829
self.assertEqual({b'rev3', b'rev2b'},
830
graph.heads([b'rev3', b'rev2b']))
831
831
832
832
def test_heads_criss_cross(self):
833
833
graph = self.make_graph(criss_cross)
834
self.assertEqual({'rev2a'},
835
graph.heads(['rev2a', 'rev1']))
836
self.assertEqual({'rev2b'},
837
graph.heads(['rev2b', 'rev1']))
838
self.assertEqual({'rev3a'},
839
graph.heads(['rev3a', 'rev1']))
840
self.assertEqual({'rev3b'},
841
graph.heads(['rev3b', 'rev1']))
842
self.assertEqual({'rev2a', 'rev2b'},
843
graph.heads(['rev2a', 'rev2b']))
844
self.assertEqual({'rev3a'},
845
graph.heads(['rev3a', 'rev2a']))
846
self.assertEqual({'rev3a'},
847
graph.heads(['rev3a', 'rev2b']))
848
self.assertEqual({'rev3a'},
849
graph.heads(['rev3a', 'rev2a', 'rev2b']))
850
self.assertEqual({'rev3b'},
851
graph.heads(['rev3b', 'rev2a']))
852
self.assertEqual({'rev3b'},
853
graph.heads(['rev3b', 'rev2b']))
854
self.assertEqual({'rev3b'},
855
graph.heads(['rev3b', 'rev2a', 'rev2b']))
856
self.assertEqual({'rev3a', 'rev3b'},
857
graph.heads(['rev3a', 'rev3b']))
858
self.assertEqual({'rev3a', 'rev3b'},
859
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
834
self.assertEqual({b'rev2a'},
835
graph.heads([b'rev2a', b'rev1']))
836
self.assertEqual({b'rev2b'},
837
graph.heads([b'rev2b', b'rev1']))
838
self.assertEqual({b'rev3a'},
839
graph.heads([b'rev3a', b'rev1']))
840
self.assertEqual({b'rev3b'},
841
graph.heads([b'rev3b', b'rev1']))
842
self.assertEqual({b'rev2a', b'rev2b'},
843
graph.heads([b'rev2a', b'rev2b']))
844
self.assertEqual({b'rev3a'},
845
graph.heads([b'rev3a', b'rev2a']))
846
self.assertEqual({b'rev3a'},
847
graph.heads([b'rev3a', b'rev2b']))
848
self.assertEqual({b'rev3a'},
849
graph.heads([b'rev3a', b'rev2a', b'rev2b']))
850
self.assertEqual({b'rev3b'},
851
graph.heads([b'rev3b', b'rev2a']))
852
self.assertEqual({b'rev3b'},
853
graph.heads([b'rev3b', b'rev2b']))
854
self.assertEqual({b'rev3b'},
855
graph.heads([b'rev3b', b'rev2a', b'rev2b']))
856
self.assertEqual({b'rev3a', b'rev3b'},
857
graph.heads([b'rev3a', b'rev3b']))
858
self.assertEqual({b'rev3a', b'rev3b'},
859
graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b']))
860
860
861
861
def test_heads_shortcut(self):
862
862
graph = self.make_graph(history_shortcut)
863
863
864
self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
865
graph.heads(['rev2a', 'rev2b', 'rev2c']))
866
self.assertEqual({'rev3a', 'rev3b'},
867
graph.heads(['rev3a', 'rev3b']))
868
self.assertEqual({'rev3a', 'rev3b'},
869
graph.heads(['rev2a', 'rev3a', 'rev3b']))
870
self.assertEqual({'rev2a', 'rev3b'},
871
graph.heads(['rev2a', 'rev3b']))
872
self.assertEqual({'rev2c', 'rev3a'},
873
graph.heads(['rev2c', 'rev3a']))
864
self.assertEqual({b'rev2a', b'rev2b', b'rev2c'},
865
graph.heads([b'rev2a', b'rev2b', b'rev2c']))
866
self.assertEqual({b'rev3a', b'rev3b'},
867
graph.heads([b'rev3a', b'rev3b']))
868
self.assertEqual({b'rev3a', b'rev3b'},
869
graph.heads([b'rev2a', b'rev3a', b'rev3b']))
870
self.assertEqual({b'rev2a', b'rev3b'},
871
graph.heads([b'rev2a', b'rev3b']))
872
self.assertEqual({b'rev2c', b'rev3a'},
873
graph.heads([b'rev2c', b'rev3a']))
874
874
875
875
def _run_heads_break_deeper(self, graph_dict, search):
876
876
"""Run heads on a graph-as-a-dict.
877
877
878
If the search asks for the parents of 'deeper' the test will fail.
878
If the search asks for the parents of b'deeper' the test will fail.
879
879
"""
880
880
class stub(object):
881
881
pass
882
882
def get_parent_map(keys):
883
883
result = {}
884
884
for key in keys:
885
if key == 'deeper':
885
if key == b'deeper':
886
886
self.fail('key deeper was accessed')
887
887
result[key] = graph_dict[key]
888
888
return result
894
894
def test_heads_limits_search(self):
895
895
# test that a heads query does not search all of history
896
896
graph_dict = {
897
'left': ['common'],
898
'right': ['common'],
899
'common': ['deeper'],
897
b'left': [b'common'],
898
b'right': [b'common'],
899
b'common': [b'deeper'],
900
900
}
901
self.assertEqual({'left', 'right'},
902
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
901
self.assertEqual({b'left', b'right'},
902
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
903
903
904
904
def test_heads_limits_search_assymetric(self):
905
905
# test that a heads query does not search all of history
906
906
graph_dict = {
907
'left': ['midleft'],
908
'midleft': ['common'],
909
'right': ['common'],
910
'common': ['aftercommon'],
911
'aftercommon': ['deeper'],
907
b'left': [b'midleft'],
908
b'midleft': [b'common'],
909
b'right': [b'common'],
910
b'common': [b'aftercommon'],
911
b'aftercommon': [b'deeper'],
912
912
}
913
self.assertEqual({'left', 'right'},
914
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
913
self.assertEqual({b'left', b'right'},
914
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
915
915
916
916
def test_heads_limits_search_common_search_must_continue(self):
917
917
# test that common nodes are still queried, preventing
918
918
# all-the-way-to-origin behaviour in the following graph:
919
919
graph_dict = {
920
'h1': ['shortcut', 'common1'],
921
'h2': ['common1'],
922
'shortcut': ['common2'],
923
'common1': ['common2'],
924
'common2': ['deeper'],
920
b'h1': [b'shortcut', b'common1'],
921
b'h2': [b'common1'],
922
b'shortcut': [b'common2'],
923
b'common1': [b'common2'],
924
b'common2': [b'deeper'],
925
925
}
926
self.assertEqual({'h1', 'h2'},
927
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
926
self.assertEqual({b'h1', b'h2'},
927
self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
928
928
929
929
def test_breadth_first_search_start_ghosts(self):
930
930
graph = self.make_graph({})
931
931
# with_ghosts reports the ghosts
932
search = graph._make_breadth_first_searcher(['a-ghost'])
933
self.assertEqual((set(), {'a-ghost'}), search.next_with_ghosts())
932
search = graph._make_breadth_first_searcher([b'a-ghost'])
933
self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts())
934
934
self.assertRaises(StopIteration, search.next_with_ghosts)
935
935
# next includes them
936
search = graph._make_breadth_first_searcher(['a-ghost'])
937
self.assertEqual({'a-ghost'}, next(search))
936
search = graph._make_breadth_first_searcher([b'a-ghost'])
937
self.assertEqual({b'a-ghost'}, next(search))
938
938
self.assertRaises(StopIteration, next, search)
939
939
940
940
def test_breadth_first_search_deep_ghosts(self):
941
941
graph = self.make_graph({
942
'head': ['present'],
943
'present': ['child', 'ghost'],
944
'child': [],
942
b'head': [b'present'],
943
b'present': [b'child', b'ghost'],
944
b'child': [],
945
945
})
946
946
# with_ghosts reports the ghosts
947
search = graph._make_breadth_first_searcher(['head'])
948
self.assertEqual(({'head'}, set()), search.next_with_ghosts())
949
self.assertEqual(({'present'}, set()), search.next_with_ghosts())
950
self.assertEqual(({'child'}, {'ghost'}),
947
search = graph._make_breadth_first_searcher([b'head'])
948
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
949
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
950
self.assertEqual(({b'child'}, {b'ghost'}),
951
951
search.next_with_ghosts())
952
952
self.assertRaises(StopIteration, search.next_with_ghosts)
953
953
# next includes them
954
search = graph._make_breadth_first_searcher(['head'])
955
self.assertEqual({'head'}, next(search))
956
self.assertEqual({'present'}, next(search))
957
self.assertEqual({'child', 'ghost'},
954
search = graph._make_breadth_first_searcher([b'head'])
955
self.assertEqual({b'head'}, next(search))
956
self.assertEqual({b'present'}, next(search))
957
self.assertEqual({b'child', b'ghost'},
958
958
next(search))
959
959
self.assertRaises(StopIteration, next, search)
960
960
962
962
# To make the API robust, we allow calling both next() and
963
963
# next_with_ghosts() on the same searcher.
964
964
graph = self.make_graph({
965
'head': ['present'],
966
'present': ['child', 'ghost'],
967
'child': [],
965
b'head': [b'present'],
966
b'present': [b'child', b'ghost'],
967
b'child': [],
968
968
})
969
969
# start with next_with_ghosts
970
search = graph._make_breadth_first_searcher(['head'])
971
self.assertEqual(({'head'}, set()), search.next_with_ghosts())
972
self.assertEqual({'present'}, next(search))
973
self.assertEqual(({'child'}, {'ghost'}),
970
search = graph._make_breadth_first_searcher([b'head'])
971
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
972
self.assertEqual({b'present'}, next(search))
973
self.assertEqual(({b'child'}, {b'ghost'}),
974
974
search.next_with_ghosts())
975
975
self.assertRaises(StopIteration, next, search)
976
976
# start with next
977
search = graph._make_breadth_first_searcher(['head'])
978
self.assertEqual({'head'}, next(search))
979
self.assertEqual(({'present'}, set()), search.next_with_ghosts())
980
self.assertEqual({'child', 'ghost'},
977
search = graph._make_breadth_first_searcher([b'head'])
978
self.assertEqual({b'head'}, next(search))
979
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
980
self.assertEqual({b'child', b'ghost'},
981
981
next(search))
982
982
self.assertRaises(StopIteration, search.next_with_ghosts)
983
983
984
984
def test_breadth_first_change_search(self):
985
985
# Changing the search should work with both next and next_with_ghosts.
986
986
graph = self.make_graph({
987
'head': ['present'],
988
'present': ['stopped'],
989
'other': ['other_2'],
990
'other_2': [],
987
b'head': [b'present'],
988
b'present': [b'stopped'],
989
b'other': [b'other_2'],
990
b'other_2': [],
991
991
})
992
search = graph._make_breadth_first_searcher(['head'])
993
self.assertEqual(({'head'}, set()), search.next_with_ghosts())
994
self.assertEqual(({'present'}, set()), search.next_with_ghosts())
995
self.assertEqual({'present'},
996
search.stop_searching_any(['present']))
997
self.assertEqual(({'other'}, {'other_ghost'}),
998
search.start_searching(['other', 'other_ghost']))
999
self.assertEqual(({'other_2'}, set()), search.next_with_ghosts())
992
search = graph._make_breadth_first_searcher([b'head'])
993
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
994
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
995
self.assertEqual({b'present'},
996
search.stop_searching_any([b'present']))
997
self.assertEqual(({b'other'}, {b'other_ghost'}),
998
search.start_searching([b'other', b'other_ghost']))
999
self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts())
1000
1000
self.assertRaises(StopIteration, search.next_with_ghosts)
1001
1001
# next includes them
1002
search = graph._make_breadth_first_searcher(['head'])
1003
self.assertEqual({'head'}, next(search))
1004
self.assertEqual({'present'}, next(search))
1005
self.assertEqual({'present'},
1006
search.stop_searching_any(['present']))
1007
search.start_searching(['other', 'other_ghost'])
1008
self.assertEqual({'other_2'}, next(search))
1002
search = graph._make_breadth_first_searcher([b'head'])
1003
self.assertEqual({b'head'}, next(search))
1004
self.assertEqual({b'present'}, next(search))
1005
self.assertEqual({b'present'},
1006
search.stop_searching_any([b'present']))
1007
search.start_searching([b'other', b'other_ghost'])
1008
self.assertEqual({b'other_2'}, next(search))
1009
1009
self.assertRaises(StopIteration, next, search)
1010
1010
1011
1011
def assertSeenAndResult(self, instructions, search, next):
1035
1035
1036
1036
def test_breadth_first_get_result_excludes_current_pending(self):
1037
1037
graph = self.make_graph({
1038
'head': ['child'],
1039
'child': [NULL_REVISION],
1038
b'head': [b'child'],
1039
b'child': [NULL_REVISION],
1040
1040
NULL_REVISION: [],
1041
1041
})
1042
search = graph._make_breadth_first_searcher(['head'])
1042
search = graph._make_breadth_first_searcher([b'head'])
1043
1043
# At the start, nothing has been seen, to its all excluded:
1044
1044
state = search.get_state()
1045
self.assertEqual(({'head'}, {'head'}, set()),
1045
self.assertEqual(({b'head'}, {b'head'}, set()),
1046
1046
state)
1047
1047
self.assertEqual(set(), search.seen)
1048
1048
# using next:
1049
1049
expected = [
1050
({'head'}, ({'head'}, {'child'}, 1),
1051
['head'], None, None),
1052
({'head', 'child'}, ({'head'}, {NULL_REVISION}, 2),
1053
['head', 'child'], None, None),
1054
({'head', 'child', NULL_REVISION}, ({'head'}, set(), 3),
1055
['head', 'child', NULL_REVISION], None, None),
1050
({b'head'}, ({b'head'}, {b'child'}, 1),
1051
[b'head'], None, None),
1052
({b'head', b'child'}, ({b'head'}, {NULL_REVISION}, 2),
1053
[b'head', b'child'], None, None),
1054
({b'head', b'child', NULL_REVISION}, ({b'head'}, set(), 3),
1055
[b'head', b'child', NULL_REVISION], None, None),
1056
1056
]
1057
1057
self.assertSeenAndResult(expected, search, search.__next__)
1058
1058
# using next_with_ghosts:
1059
search = graph._make_breadth_first_searcher(['head'])
1059
search = graph._make_breadth_first_searcher([b'head'])
1060
1060
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1061
1061
1062
1062
def test_breadth_first_get_result_starts_stops(self):
1063
1063
graph = self.make_graph({
1064
'head':['child'],
1065
'child':[NULL_REVISION],
1066
'otherhead':['otherchild'],
1067
'otherchild':['excluded'],
1068
'excluded':[NULL_REVISION],
1064
b'head':[b'child'],
1065
b'child':[NULL_REVISION],
1066
b'otherhead':[b'otherchild'],
1067
b'otherchild':[b'excluded'],
1068
b'excluded':[NULL_REVISION],
1069
1069
NULL_REVISION:[]
1070
1070
})
1071
1071
search = graph._make_breadth_first_searcher([])
1072
1072
# Starting with nothing and adding a search works:
1073
search.start_searching(['head'])
1073
search.start_searching([b'head'])
1074
1074
# head has been seen:
1075
1075
state = search.get_state()
1076
self.assertEqual(({'head'}, {'child'}, {'head'}),
1076
self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1077
1077
state)
1078
self.assertEqual({'head'}, search.seen)
1078
self.assertEqual({b'head'}, search.seen)
1079
1079
# using next:
1080
1080
expected = [
1081
1081
# stop at child, and start a new search at otherhead:
1082
1082
# - otherhead counts as seen immediately when start_searching is
1083
1083
# called.
1084
({'head', 'child', 'otherhead'},
1085
({'head', 'otherhead'}, {'child', 'otherchild'}, 2),
1086
['head', 'otherhead'], ['otherhead'], ['child']),
1087
({'head', 'child', 'otherhead', 'otherchild'},
1088
({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1089
['head', 'otherhead', 'otherchild'], None, None),
1084
({b'head', b'child', b'otherhead'},
1085
({b'head', b'otherhead'}, {b'child', b'otherchild'}, 2),
1086
[b'head', b'otherhead'], [b'otherhead'], [b'child']),
1087
({b'head', b'child', b'otherhead', b'otherchild'},
1088
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1089
[b'head', b'otherhead', b'otherchild'], None, None),
1090
1090
# stop searching excluded now
1091
({'head', 'child', 'otherhead', 'otherchild', 'excluded'},
1092
({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1093
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1091
({b'head', b'child', b'otherhead', b'otherchild', b'excluded'},
1092
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1093
[b'head', b'otherhead', b'otherchild'], None, [b'excluded']),
1094
1094
]
1095
1095
self.assertSeenAndResult(expected, search, search.__next__)
1096
1096
# using next_with_ghosts:
1097
1097
search = graph._make_breadth_first_searcher([])
1098
search.start_searching(['head'])
1098
search.start_searching([b'head'])
1099
1099
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1100
1100
1101
1101
def test_breadth_first_stop_searching_not_queried(self):
1102
# A client should be able to say 'stop node X' even if X has not been
1102
# A client should be able to say b'stop node X' even if X has not been
1103
1103
# returned to the client.
1104
1104
graph = self.make_graph({
1105
'head': ['child', 'ghost1'],
1106
'child': [NULL_REVISION],
1105
b'head': [b'child', b'ghost1'],
1106
b'child': [NULL_REVISION],
1107
1107
NULL_REVISION: [],
1108
1108
})
1109
search = graph._make_breadth_first_searcher(['head'])
1109
search = graph._make_breadth_first_searcher([b'head'])
1110
1110
expected = [
1111
1111
# NULL_REVISION and ghost1 have not been returned
1112
({'head'},
1113
({'head'}, {'child', NULL_REVISION, 'ghost1'}, 1),
1114
['head'], None, [NULL_REVISION, 'ghost1']),
1112
({b'head'},
1113
({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1),
1114
[b'head'], None, [NULL_REVISION, b'ghost1']),
1115
1115
# ghost1 has been returned, NULL_REVISION is to be returned in the
1116
1116
# next iteration.
1117
({'head', 'child', 'ghost1'},
1118
({'head'}, {'ghost1', NULL_REVISION}, 2),
1119
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1117
({b'head', b'child', b'ghost1'},
1118
({b'head'}, {b'ghost1', NULL_REVISION}, 2),
1119
[b'head', b'child'], None, [NULL_REVISION, b'ghost1']),
1120
1120
]
1121
1121
self.assertSeenAndResult(expected, search, search.__next__)
1122
1122
# using next_with_ghosts:
1123
search = graph._make_breadth_first_searcher(['head'])
1123
search = graph._make_breadth_first_searcher([b'head'])
1124
1124
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1125
1125
1126
1126
def test_breadth_first_stop_searching_late(self):
1127
# A client should be able to say 'stop node X' and have it excluded
1127
# A client should be able to say b'stop node X' and have it excluded
1128
1128
# from the result even if X was seen in an older iteration of the
1129
1129
# search.
1130
1130
graph = self.make_graph({
1131
'head': ['middle'],
1132
'middle': ['child'],
1133
'child': [NULL_REVISION],
1131
b'head': [b'middle'],
1132
b'middle': [b'child'],
1133
b'child': [NULL_REVISION],
1134
1134
NULL_REVISION: [],
1135
1135
})
1136
search = graph._make_breadth_first_searcher(['head'])
1136
search = graph._make_breadth_first_searcher([b'head'])
1137
1137
expected = [
1138
({'head'}, ({'head'}, {'middle'}, 1),
1139
['head'], None, None),
1140
({'head', 'middle'}, ({'head'}, {'child'}, 2),
1141
['head', 'middle'], None, None),
1142
# 'middle' came from the previous iteration, but we don't stop
1138
({b'head'}, ({b'head'}, {b'middle'}, 1),
1139
[b'head'], None, None),
1140
({b'head', b'middle'}, ({b'head'}, {b'child'}, 2),
1141
[b'head', b'middle'], None, None),
1142
# b'middle' came from the previous iteration, but we don't stop
1143
1143
# searching it until *after* advancing the searcher.
1144
({'head', 'middle', 'child'},
1145
({'head'}, {'middle', 'child'}, 1),
1146
['head'], None, ['middle', 'child']),
1144
({b'head', b'middle', b'child'},
1145
({b'head'}, {b'middle', b'child'}, 1),
1146
[b'head'], None, [b'middle', b'child']),
1147
1147
]
1148
1148
self.assertSeenAndResult(expected, search, search.__next__)
1149
1149
# using next_with_ghosts:
1150
search = graph._make_breadth_first_searcher(['head'])
1150
search = graph._make_breadth_first_searcher([b'head'])
1151
1151
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1152
1152
1153
1153
def test_breadth_first_get_result_ghosts_are_excluded(self):
1154
1154
graph = self.make_graph({
1155
'head': ['child', 'ghost'],
1156
'child': [NULL_REVISION],
1155
b'head': [b'child', b'ghost'],
1156
b'child': [NULL_REVISION],
1157
1157
NULL_REVISION: [],
1158
1158
})
1159
search = graph._make_breadth_first_searcher(['head'])
1159
search = graph._make_breadth_first_searcher([b'head'])
1160
1160
# using next:
1161
1161
expected = [
1162
({'head'},
1163
({'head'}, {'ghost', 'child'}, 1),
1164
['head'], None, None),
1165
({'head', 'child', 'ghost'},
1166
({'head'}, {NULL_REVISION, 'ghost'}, 2),
1167
['head', 'child'], None, None),
1162
({b'head'},
1163
({b'head'}, {b'ghost', b'child'}, 1),
1164
[b'head'], None, None),
1165
({b'head', b'child', b'ghost'},
1166
({b'head'}, {NULL_REVISION, b'ghost'}, 2),
1167
[b'head', b'child'], None, None),
1168
1168
]
1169
1169
self.assertSeenAndResult(expected, search, search.__next__)
1170
1170
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1171
search = graph._make_breadth_first_searcher([b'head'])
1172
1172
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1173
1173
1174
1174
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1175
1175
graph = self.make_graph({
1176
'head': ['child'],
1177
'child': [NULL_REVISION],
1176
b'head': [b'child'],
1177
b'child': [NULL_REVISION],
1178
1178
NULL_REVISION: [],
1179
1179
})
1180
search = graph._make_breadth_first_searcher(['head'])
1180
search = graph._make_breadth_first_searcher([b'head'])
1181
1181
# using next:
1182
1182
expected = [
1183
({'head', 'ghost'},
1184
({'head', 'ghost'}, {'child', 'ghost'}, 1),
1185
['head'], ['ghost'], None),
1186
({'head', 'child', 'ghost'},
1187
({'head', 'ghost'}, {NULL_REVISION, 'ghost'}, 2),
1188
['head', 'child'], None, None),
1183
({b'head', b'ghost'},
1184
({b'head', b'ghost'}, {b'child', b'ghost'}, 1),
1185
[b'head'], [b'ghost'], None),
1186
({b'head', b'child', b'ghost'},
1187
({b'head', b'ghost'}, {NULL_REVISION, b'ghost'}, 2),
1188
[b'head', b'child'], None, None),
1189
1189
]
1190
1190
self.assertSeenAndResult(expected, search, search.__next__)
1191
1191
# using next_with_ghosts:
1192
search = graph._make_breadth_first_searcher(['head'])
1192
search = graph._make_breadth_first_searcher([b'head'])
1193
1193
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1194
1194
1195
1195
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1196
1196
graph = self.make_graph({
1197
'head': [NULL_REVISION],
1197
b'head': [NULL_REVISION],
1198
1198
NULL_REVISION: [],
1199
1199
})
1200
search = graph._make_breadth_first_searcher(['head'])
1200
search = graph._make_breadth_first_searcher([b'head'])
1201
1201
# using next:
1202
1202
expected = [
1203
({'head'},
1204
({'head'}, {NULL_REVISION}, 1),
1205
['head'], None, None),
1206
({'head', NULL_REVISION},
1207
({'head'}, set([]), 2),
1208
['head', NULL_REVISION], None, None),
1203
({b'head'},
1204
({b'head'}, {NULL_REVISION}, 1),
1205
[b'head'], None, None),
1206
({b'head', NULL_REVISION},
1207
({b'head'}, set([]), 2),
1208
[b'head', NULL_REVISION], None, None),
1209
1209
]
1210
1210
self.assertSeenAndResult(expected, search, search.__next__)
1211
1211
# using next_with_ghosts:
1212
search = graph._make_breadth_first_searcher(['head'])
1212
search = graph._make_breadth_first_searcher([b'head'])
1213
1213
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1214
1214
1215
1215
def test_breadth_first_search_get_result_after_StopIteration(self):
1216
1216
# StopIteration should not invalid anything..
1217
1217
graph = self.make_graph({
1218
'head': [NULL_REVISION],
1218
b'head': [NULL_REVISION],
1219
1219
NULL_REVISION: [],
1220
1220
})
1221
search = graph._make_breadth_first_searcher(['head'])
1221
search = graph._make_breadth_first_searcher([b'head'])
1222
1222
# using next:
1223
1223
expected = [
1224
({'head'},
1225
({'head'}, {NULL_REVISION}, 1),
1226
['head'], None, None),
1227
({'head', 'ghost', NULL_REVISION},
1228
({'head', 'ghost'}, {'ghost'}, 2),
1229
['head', NULL_REVISION], ['ghost'], None),
1224
({b'head'},
1225
({b'head'}, {NULL_REVISION}, 1),
1226
[b'head'], None, None),
1227
({b'head', b'ghost', NULL_REVISION},
1228
({b'head', b'ghost'}, {b'ghost'}, 2),
1229
[b'head', NULL_REVISION], [b'ghost'], None),
1230
1230
]
1231
1231
self.assertSeenAndResult(expected, search, search.__next__)
1232
1232
self.assertRaises(StopIteration, next, search)
1233
self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
1233
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1234
1234
state = search.get_state()
1235
1235
self.assertEqual(
1236
({'ghost', 'head'}, {'ghost'},
1237
{'head', NULL_REVISION}),
1236
({b'ghost', b'head'}, {b'ghost'},
1237
{b'head', NULL_REVISION}),
1238
1238
state)
1239
1239
# using next_with_ghosts:
1240
search = graph._make_breadth_first_searcher(['head'])
1240
search = graph._make_breadth_first_searcher([b'head'])
1241
1241
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1242
self.assertRaises(StopIteration, next, search)
1243
self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
1243
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1244
1244
state = search.get_state()
1245
1245
self.assertEqual(
1246
({'ghost', 'head'}, {'ghost'},
1247
{'head', NULL_REVISION}),
1246
({b'ghost', b'head'}, {b'ghost'},
1247
{b'head', NULL_REVISION}),
1248
1248
state)
1249
1249
1250
1250
1256
1256
1257
1257
def test_empty_set(self):
1258
1258
graph = self.make_graph(ancestry_1)
1259
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1261
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1259
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev1'])
1260
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev2b'])
1261
self.assertFindUniqueAncestors(graph, [], b'rev3', [b'rev1', b'rev3'])
1262
1262
1263
1263
def test_single_node(self):
1264
1264
graph = self.make_graph(ancestry_1)
1265
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1266
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1267
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1265
self.assertFindUniqueAncestors(graph, [b'rev2a'], b'rev2a', [b'rev1'])
1266
self.assertFindUniqueAncestors(graph, [b'rev2b'], b'rev2b', [b'rev1'])
1267
self.assertFindUniqueAncestors(graph, [b'rev3'], b'rev3', [b'rev2a'])
1268
1268
1269
1269
def test_minimal_ancestry(self):
1270
1270
graph = self.make_breaking_graph(extended_history_shortcut,
1271
[NULL_REVISION, 'a', 'b'])
1272
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1271
[NULL_REVISION, b'a', b'b'])
1272
self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd'])
1273
1273
1274
1274
graph = self.make_breaking_graph(extended_history_shortcut,
1275
['b'])
1276
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1275
[b'b'])
1276
self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd'])
1277
1277
1278
1278
graph = self.make_breaking_graph(complex_shortcut,
1279
['a', 'b'])
1280
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1281
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1282
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1283
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1279
[b'a', b'b'])
1280
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'i'])
1281
self.assertFindUniqueAncestors(graph, [b'e', b'g', b'i'], b'i', [b'h'])
1282
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'g'])
1283
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'j'])
1284
1284
1285
1285
def test_in_ancestry(self):
1286
1286
graph = self.make_graph(ancestry_1)
1287
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1288
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1287
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3'])
1288
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4'])
1289
1289
1290
1290
def test_multiple_revisions(self):
1291
1291
graph = self.make_graph(ancestry_1)
1292
1292
self.assertFindUniqueAncestors(graph,
1293
['rev4'], 'rev4', ['rev3', 'rev2b'])
1293
[b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1294
1294
self.assertFindUniqueAncestors(graph,
1295
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1295
[b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1296
1296
1297
1297
def test_complex_shortcut(self):
1298
1298
graph = self.make_graph(complex_shortcut)
1299
1299
self.assertFindUniqueAncestors(graph,
1300
['h', 'n'], 'n', ['m'])
1300
[b'h', b'n'], b'n', [b'm'])
1301
1301
self.assertFindUniqueAncestors(graph,
1302
['e', 'i', 'm'], 'm', ['n'])
1302
[b'e', b'i', b'm'], b'm', [b'n'])
1303
1303
1304
1304
def test_complex_shortcut2(self):
1305
1305
graph = self.make_graph(complex_shortcut2)
1306
1306
self.assertFindUniqueAncestors(graph,
1307
['j', 'u'], 'u', ['t'])
1307
[b'j', b'u'], b'u', [b't'])
1308
1308
self.assertFindUniqueAncestors(graph,
1309
['t'], 't', ['u'])
1309
[b't'], b't', [b'u'])
1310
1310
1311
1311
def test_multiple_interesting_unique(self):
1312
1312
graph = self.make_graph(multiple_interesting_unique)
1313
1313
self.assertFindUniqueAncestors(graph,
1314
['j', 'y'], 'y', ['z'])
1314
[b'j', b'y'], b'y', [b'z'])
1315
1315
self.assertFindUniqueAncestors(graph,
1316
['p', 'z'], 'z', ['y'])
1316
[b'p', b'z'], b'z', [b'y'])
1317
1317
1318
1318
def test_racing_shortcuts(self):
1319
1319
graph = self.make_graph(racing_shortcuts)
1320
1320
self.assertFindUniqueAncestors(graph,
1321
['p', 'q', 'z'], 'z', ['y'])
1321
[b'p', b'q', b'z'], b'z', [b'y'])
1322
1322
self.assertFindUniqueAncestors(graph,
1323
['h', 'i', 'j', 'y'], 'j', ['z'])
1323
[b'h', b'i', b'j', b'y'], b'j', [b'z'])
1324
1324
1325
1325
1326
1326
class TestGraphFindDistanceToNull(TestGraphBase):
1334
1334
def test_nothing_known(self):
1335
1335
graph = self.make_graph(ancestry_1)
1336
1336
self.assertFindDistance(0, graph, NULL_REVISION, [])
1337
self.assertFindDistance(1, graph, 'rev1', [])
1338
self.assertFindDistance(2, graph, 'rev2a', [])
1339
self.assertFindDistance(2, graph, 'rev2b', [])
1340
self.assertFindDistance(3, graph, 'rev3', [])
1341
self.assertFindDistance(4, graph, 'rev4', [])
1337
self.assertFindDistance(1, graph, b'rev1', [])
1338
self.assertFindDistance(2, graph, b'rev2a', [])
1339
self.assertFindDistance(2, graph, b'rev2b', [])
1340
self.assertFindDistance(3, graph, b'rev3', [])
1341
self.assertFindDistance(4, graph, b'rev4', [])
1342
1342
1343
1343
def test_rev_is_ghost(self):
1344
1344
graph = self.make_graph(ancestry_1)
1345
1345
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1346
graph.find_distance_to_null, 'rev_missing', [])
1347
self.assertEqual('rev_missing', e.revision_id)
1348
self.assertEqual('rev_missing', e.ghost_revision_id)
1346
graph.find_distance_to_null, b'rev_missing', [])
1347
self.assertEqual(b'rev_missing', e.revision_id)
1348
self.assertEqual(b'rev_missing', e.ghost_revision_id)
1349
1349
1350
1350
def test_ancestor_is_ghost(self):
1351
graph = self.make_graph({'rev':['parent']})
1351
graph = self.make_graph({b'rev': [b'parent']})
1352
1352
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1353
graph.find_distance_to_null, 'rev', [])
1354
self.assertEqual('rev', e.revision_id)
1355
self.assertEqual('parent', e.ghost_revision_id)
1353
graph.find_distance_to_null, b'rev', [])
1354
self.assertEqual(b'rev', e.revision_id)
1355
self.assertEqual(b'parent', e.ghost_revision_id)
1356
1356
1357
1357
def test_known_in_ancestry(self):
1358
1358
graph = self.make_graph(ancestry_1)
1359
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1360
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1359
self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)])
1360
self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)])
1361
1361
1362
1362
def test_known_in_ancestry_limits(self):
1363
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1364
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1363
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1364
self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)])
1365
1365
1366
1366
def test_target_is_ancestor(self):
1367
1367
graph = self.make_graph(ancestry_1)
1368
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1368
self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)])
1369
1369
1370
1370
def test_target_is_ancestor_limits(self):
1371
1371
"""We shouldn't search all history if we run into ourselves"""
1372
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1373
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1372
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1373
self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)])
1374
1374
1375
1375
def test_target_parallel_to_known_limits(self):
1376
1376
# Even though the known revision isn't part of the other ancestry, they
1377
1377
# eventually converge
1378
graph = self.make_breaking_graph(with_tail, ['a'])
1379
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1380
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1381
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1382
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1378
graph = self.make_breaking_graph(with_tail, [b'a'])
1379
self.assertFindDistance(6, graph, b'f', [(b'g', 6)])
1380
self.assertFindDistance(7, graph, b'h', [(b'g', 6)])
1381
self.assertFindDistance(8, graph, b'i', [(b'g', 6)])
1382
self.assertFindDistance(6, graph, b'g', [(b'i', 8)])
1383
1383
1384
1384
1385
1385
class TestFindMergeOrder(TestGraphBase):
1389
1389
1390
1390
def test_parents(self):
1391
1391
graph = self.make_graph(ancestry_1)
1392
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1393
['rev3', 'rev2b'])
1394
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1395
['rev2b', 'rev3'])
1392
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1393
[b'rev3', b'rev2b'])
1394
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1395
[b'rev2b', b'rev3'])
1396
1396
1397
1397
def test_ancestors(self):
1398
1398
graph = self.make_graph(ancestry_1)
1399
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1400
['rev1', 'rev2b'])
1401
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1402
['rev2b', 'rev1'])
1399
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1400
[b'rev1', b'rev2b'])
1401
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1402
[b'rev2b', b'rev1'])
1403
1403
1404
1404
def test_shortcut_one_ancestor(self):
1405
1405
# When we have enough info, we can stop searching
1406
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1406
graph = self.make_breaking_graph(ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1407
1407
# Single ancestors shortcut right away
1408
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1408
self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1409
1409
1410
1410
def test_shortcut_after_one_ancestor(self):
1411
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1412
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1411
graph = self.make_breaking_graph(ancestry_1, [b'rev2a', b'rev2b'])
1412
self.assertMergeOrder([b'rev3', b'rev1'], graph, b'rev4', [b'rev1', b'rev3'])
1413
1413
1414
1414
1415
1415
class TestFindDescendants(TestGraphBase):
1416
1416
1417
1417
def test_find_descendants_rev1_rev3(self):
1418
1418
graph = self.make_graph(ancestry_1)
1419
descendants = graph.find_descendants('rev1', 'rev3')
1420
self.assertEqual({'rev1', 'rev2a', 'rev3'}, descendants)
1419
descendants = graph.find_descendants(b'rev1', b'rev3')
1420
self.assertEqual({b'rev1', b'rev2a', b'rev3'}, descendants)
1421
1421
1422
1422
def test_find_descendants_rev1_rev4(self):
1423
1423
graph = self.make_graph(ancestry_1)
1424
descendants = graph.find_descendants('rev1', 'rev4')
1425
self.assertEqual({'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'},
1424
descendants = graph.find_descendants(b'rev1', b'rev4')
1425
self.assertEqual({b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'},
1426
1426
descendants)
1427
1427
1428
1428
def test_find_descendants_rev2a_rev4(self):
1429
1429
graph = self.make_graph(ancestry_1)
1430
descendants = graph.find_descendants('rev2a', 'rev4')
1431
self.assertEqual({'rev2a', 'rev3', 'rev4'}, descendants)
1430
descendants = graph.find_descendants(b'rev2a', b'rev4')
1431
self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants)
1432
1432
1433
1433
class TestFindLefthandMerger(TestGraphBase):
1434
1434
1437
1437
self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1438
1438
1439
1439
def test_find_lefthand_merger_rev2b(self):
1440
self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1440
self.check_merger(b'rev4', ancestry_1, b'rev2b', b'rev4')
1441
1441
1442
1442
def test_find_lefthand_merger_rev2a(self):
1443
self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1443
self.check_merger(b'rev2a', ancestry_1, b'rev2a', b'rev4')
1444
1444
1445
1445
def test_find_lefthand_merger_rev4(self):
1446
self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1446
self.check_merger(None, ancestry_1, b'rev4', b'rev2a')
1447
1447
1448
1448
def test_find_lefthand_merger_f(self):
1449
self.check_merger('i', complex_shortcut, 'f', 'm')
1449
self.check_merger(b'i', complex_shortcut, b'f', b'm')
1450
1450
1451
1451
def test_find_lefthand_merger_g(self):
1452
self.check_merger('i', complex_shortcut, 'g', 'm')
1452
self.check_merger(b'i', complex_shortcut, b'g', b'm')
1453
1453
1454
1454
def test_find_lefthand_merger_h(self):
1455
self.check_merger('n', complex_shortcut, 'h', 'n')
1455
self.check_merger(b'n', complex_shortcut, b'h', b'n')
1456
1456
1457
1457
1458
1458
class TestGetChildMap(TestGraphBase):
1459
1459
1460
1460
def test_get_child_map(self):
1461
1461
graph = self.make_graph(ancestry_1)
1462
child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1463
self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1464
'rev2a': ['rev3'],
1465
'rev2b': ['rev4'],
1466
'rev3': ['rev4']},
1462
child_map = graph.get_child_map([b'rev4', b'rev3', b'rev2a', b'rev2b'])
1463
self.assertEqual({b'rev1': [b'rev2a', b'rev2b'],
1464
b'rev2a': [b'rev3'],
1465
b'rev2b': [b'rev4'],
1466
b'rev3': [b'rev4']},
1467
1467
child_map)
1468
1468
1469
1469
1477
1477
1478
1478
def setUp(self):
1479
1479
super(TestCachingParentsProvider, self).setUp()
1480
dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1480
dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)})
1481
1481
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1482
1482
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1483
1483
1484
1484
def test_get_parent_map(self):
1485
1485
"""Requesting the same revision should be returned from cache"""
1486
1486
self.assertEqual({}, self.caching_pp._cache)
1487
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1488
self.assertEqual(['a'], self.inst_pp.calls)
1489
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1487
self.assertEqual({b'a':(b'b',)}, self.caching_pp.get_parent_map([b'a']))
1488
self.assertEqual([b'a'], self.inst_pp.calls)
1489
self.assertEqual({b'a':(b'b',)}, self.caching_pp.get_parent_map([b'a']))
1490
1490
# No new call, as it should have been returned from the cache
1491
self.assertEqual(['a'], self.inst_pp.calls)
1492
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1491
self.assertEqual([b'a'], self.inst_pp.calls)
1492
self.assertEqual({b'a':(b'b',)}, self.caching_pp._cache)
1493
1493
1494
1494
def test_get_parent_map_not_present(self):
1495
1495
"""The cache should also track when a revision doesn't exist"""
1496
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1497
self.assertEqual(['b'], self.inst_pp.calls)
1498
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1496
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1497
self.assertEqual([b'b'], self.inst_pp.calls)
1498
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1499
1499
# No new calls
1500
self.assertEqual(['b'], self.inst_pp.calls)
1500
self.assertEqual([b'b'], self.inst_pp.calls)
1501
1501
1502
1502
def test_get_parent_map_mixed(self):
1503
1503
"""Anything that can be returned from cache, should be"""
1504
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1505
self.assertEqual(['b'], self.inst_pp.calls)
1506
self.assertEqual({'a':('b',)},
1507
self.caching_pp.get_parent_map(['a', 'b']))
1508
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1504
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1505
self.assertEqual([b'b'], self.inst_pp.calls)
1506
self.assertEqual({b'a':(b'b',)},
1507
self.caching_pp.get_parent_map([b'a', b'b']))
1508
self.assertEqual([b'b', b'a'], self.inst_pp.calls)
1509
1509
1510
1510
def test_get_parent_map_repeated(self):
1511
1511
"""Asking for the same parent 2x will only forward 1 request."""
1512
self.assertEqual({'a':('b',)},
1513
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1512
self.assertEqual({b'a':(b'b',)},
1513
self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1514
1514
# Use sorted because we don't care about the order, just that each is
1515
1515
# only present 1 time.
1516
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1516
self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls))
1517
1517
1518
1518
def test_note_missing_key(self):
1519
1519
"""After noting that a key is missing it is cached."""
1520
self.caching_pp.note_missing_key('b')
1521
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1520
self.caching_pp.note_missing_key(b'b')
1521
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1522
1522
self.assertEqual([], self.inst_pp.calls)
1523
self.assertEqual({'b'}, self.caching_pp.missing_keys)
1523
self.assertEqual({b'b'}, self.caching_pp.missing_keys)
1524
1524
1525
1525
def test_get_cached_parent_map(self):
1526
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1526
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a']))
1527
1527
self.assertEqual([], self.inst_pp.calls)
1528
self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1529
self.assertEqual(['a'], self.inst_pp.calls)
1530
self.assertEqual({'a': ('b',)},
1531
self.caching_pp.get_cached_parent_map(['a']))
1528
self.assertEqual({b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1529
self.assertEqual([b'a'], self.inst_pp.calls)
1530
self.assertEqual({b'a': (b'b',)},
1531
self.caching_pp.get_cached_parent_map([b'a']))
1532
1532
1533
1533
1534
1534
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1539
1539
class ExtraParentsProvider(object):
1540
1540
1541
1541
def get_parent_map(self, keys):
1542
return {'rev1': [], 'rev2': ['rev1',]}
1542
return {b'rev1': [], b'rev2': [b'rev1',]}
1543
1543
1544
1544
self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1545
1545
self.caching_pp = _mod_graph.CachingParentsProvider(
1547
1547
1548
1548
def test_uncached(self):
1549
1549
self.caching_pp.disable_cache()
1550
self.assertEqual({'rev1': []},
1551
self.caching_pp.get_parent_map(['rev1']))
1552
self.assertEqual(['rev1'], self.inst_pp.calls)
1550
self.assertEqual({b'rev1': []},
1551
self.caching_pp.get_parent_map([b'rev1']))
1552
self.assertEqual([b'rev1'], self.inst_pp.calls)
1553
1553
self.assertIs(None, self.caching_pp._cache)
1554
1554
1555
1555
def test_cache_initially_empty(self):
1556
1556
self.assertEqual({}, self.caching_pp._cache)
1557
1557
1558
1558
def test_cached(self):
1559
self.assertEqual({'rev1': []},
1560
self.caching_pp.get_parent_map(['rev1']))
1561
self.assertEqual(['rev1'], self.inst_pp.calls)
1562
self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1559
self.assertEqual({b'rev1': []},
1560
self.caching_pp.get_parent_map([b'rev1']))
1561
self.assertEqual([b'rev1'], self.inst_pp.calls)
1562
self.assertEqual({b'rev1': [], b'rev2': [b'rev1']},
1563
1563
self.caching_pp._cache)
1564
self.assertEqual({'rev1': []},
1565
self.caching_pp.get_parent_map(['rev1']))
1566
self.assertEqual(['rev1'], self.inst_pp.calls)
1564
self.assertEqual({b'rev1': []},
1565
self.caching_pp.get_parent_map([b'rev1']))
1566
self.assertEqual([b'rev1'], self.inst_pp.calls)
1567
1567
1568
1568
def test_disable_cache_clears_cache(self):
1569
1569
# Put something in the cache
1570
self.caching_pp.get_parent_map(['rev1'])
1570
self.caching_pp.get_parent_map([b'rev1'])
1571
1571
self.assertEqual(2, len(self.caching_pp._cache))
1572
1572
self.caching_pp.disable_cache()
1573
1573
self.assertIs(None, self.caching_pp._cache)
1577
1577
self.assertEqual('Cache enabled when already enabled.', str(e))
1578
1578
1579
1579
def test_cache_misses(self):
1580
self.caching_pp.get_parent_map(['rev3'])
1581
self.caching_pp.get_parent_map(['rev3'])
1582
self.assertEqual(['rev3'], self.inst_pp.calls)
1580
self.caching_pp.get_parent_map([b'rev3'])
1581
self.caching_pp.get_parent_map([b'rev3'])
1582
self.assertEqual([b'rev3'], self.inst_pp.calls)
1583
1583
1584
1584
def test_no_cache_misses(self):
1585
1585
self.caching_pp.disable_cache()
1586
1586
self.caching_pp.enable_cache(cache_misses=False)
1587
self.caching_pp.get_parent_map(['rev3'])
1588
self.caching_pp.get_parent_map(['rev3'])
1589
self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1587
self.caching_pp.get_parent_map([b'rev3'])
1588
self.caching_pp.get_parent_map([b'rev3'])
1589
self.assertEqual([b'rev3', b'rev3'], self.inst_pp.calls)
1590
1590
1591
1591
def test_cache_extras(self):
1592
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1593
self.assertEqual({'rev2': ['rev1']},
1594
self.caching_pp.get_parent_map(['rev2']))
1595
self.assertEqual(['rev3'], self.inst_pp.calls)
1592
self.assertEqual({}, self.caching_pp.get_parent_map([b'rev3']))
1593
self.assertEqual({b'rev2': [b'rev1']},
1594
self.caching_pp.get_parent_map([b'rev2']))
1595
self.assertEqual([b'rev3'], self.inst_pp.calls)
1596
1596
1597
1597
def test_extras_using_cached(self):
1598
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
1599
self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1600
self.assertEqual({'rev2': ['rev1']},
1601
self.caching_pp.get_cached_parent_map(['rev2']))
1602
self.assertEqual(['rev3'], self.inst_pp.calls)
1598
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'rev3']))
1599
self.assertEqual({}, self.caching_pp.get_parent_map([b'rev3']))
1600
self.assertEqual({b'rev2': [b'rev1']},
1601
self.caching_pp.get_cached_parent_map([b'rev2']))
1602
self.assertEqual([b'rev3'], self.inst_pp.calls)
1603
1603
1604
1604
1605
1605
1649
1649
# B C
1650
1650
# |/
1651
1651
# D
1652
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1653
('B',): [('A',)], ('A',): []}
1652
d = {(b'D',): [(b'B',), (b'C',)], (b'C',):[(b'A',)],
1653
(b'B',): [(b'A',)], (b'A',): []}
1654
1654
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1655
1655
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1656
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1657
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1658
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1659
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1656
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'A'])))
1657
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'B'])))
1658
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'C'])))
1659
self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C'])))
1660
1660
1661
1661
def test_add_node(self):
1662
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1662
d = {(b'C',):[(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1663
1663
g = _mod_graph.KnownGraph(d)
1664
1664
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1665
graph_thunk.add_node("D", ["A", "C"])
1666
self.assertEqual(['B', 'D'],
1667
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1665
graph_thunk.add_node(b"D", [b"A", b"C"])
1666
self.assertEqual([b'B', b'D'],
1667
sorted(graph_thunk.heads([b'D', b'B', b'A'])))
1668
1668
1669
1669
def test_merge_sort(self):
1670
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1670
d = {(b'C',):[(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1671
1671
g = _mod_graph.KnownGraph(d)
1672
1672
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1673
graph_thunk.add_node("D", ["A", "C"])
1674
self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1673
graph_thunk.add_node(b"D", [b"A", b"C"])
1674
self.assertEqual([(b'C', 0, (2,), False), (b'A', 0, (1,), True)],
1675
1675
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1676
for n in graph_thunk.merge_sort('C')])
1676
for n in graph_thunk.merge_sort(b'C')])
1677
1677
1678
1678
1679
1679
class TestStackedParentsProvider(tests.TestCase):
1689
1689
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1690
1690
1691
1691
def test_stacked_parents_provider(self):
1692
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1693
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1692
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']})
1693
parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']})
1694
1694
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1695
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1696
stacked.get_parent_map(['rev1', 'rev2']))
1697
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1698
stacked.get_parent_map(['rev2', 'rev1']))
1699
self.assertEqual({'rev2':['rev3']},
1700
stacked.get_parent_map(['rev2', 'rev2']))
1701
self.assertEqual({'rev1':['rev4']},
1702
stacked.get_parent_map(['rev1', 'rev1']))
1695
self.assertEqual({b'rev1':[b'rev4'], b'rev2':[b'rev3']},
1696
stacked.get_parent_map([b'rev1', b'rev2']))
1697
self.assertEqual({b'rev2':[b'rev3'], b'rev1':[b'rev4']},
1698
stacked.get_parent_map([b'rev2', b'rev1']))
1699
self.assertEqual({b'rev2':[b'rev3']},
1700
stacked.get_parent_map([b'rev2', b'rev2']))
1701
self.assertEqual({b'rev1':[b'rev4']},
1702
stacked.get_parent_map([b'rev1', b'rev1']))
1703
1703
1704
1704
def test_stacked_parents_provider_overlapping(self):
1705
1705
# rev2 is availible in both providers.
1706
1706
# 1
1707
1707
# |
1708
1708
# 2
1709
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1710
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1709
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1710
parents2 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1711
1711
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1712
self.assertEqual({'rev2': ['rev1']},
1713
stacked.get_parent_map(['rev2']))
1712
self.assertEqual({b'rev2': [b'rev1']},
1713
stacked.get_parent_map([b'rev2']))
1714
1714
1715
1715
def test_handles_no_get_cached_parent_map(self):
1716
1716
# this shows that we both handle when a provider doesn't implement
1717
1717
# get_cached_parent_map
1718
pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1718
pp1 = self.get_shared_provider(b'pp1', {b'rev2': (b'rev1',)},
1719
1719
has_cached=False)
1720
pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1720
pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)},
1721
1721
has_cached=True)
1722
1722
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1723
self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1724
# No call on 'pp1' because it doesn't provide get_cached_parent_map
1725
self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1723
self.assertEqual({b'rev2': (b'rev1',)}, stacked.get_parent_map([b'rev2']))
1724
# No call on b'pp1' because it doesn't provide get_cached_parent_map
1725
self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls)
1726
1726
1727
1727
def test_query_order(self):
1728
1728
# We should call get_cached_parent_map on all providers before we call
1729
1729
# get_parent_map. Further, we should track what entries we have found,
1730
1730
# and not re-try them.
1731
pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1732
pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1733
pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1731
pp1 = self.get_shared_provider(b'pp1', {b'a': ()}, has_cached=True)
1732
pp2 = self.get_shared_provider(b'pp2', {b'c': (b'b',)}, has_cached=False)
1733
pp3 = self.get_shared_provider(b'pp3', {b'b': (b'a',)}, has_cached=True)
1734
1734
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1735
self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1736
stacked.get_parent_map(['a', 'b', 'c', 'd']))
1737
self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1735
self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)},
1736
stacked.get_parent_map([b'a', b'b', b'c', b'd']))
1737
self.assertEqual([(b'pp1', 'cached', [b'a', b'b', b'c', b'd']),
1738
1738
# No call to pp2, because it doesn't have cached
1739
('pp3', 'cached', ['b', 'c', 'd']),
1740
('pp1', ['c', 'd']),
1741
('pp2', ['c', 'd']),
1742
('pp3', ['d']),
1739
(b'pp3', 'cached', [b'b', b'c', b'd']),
1740
(b'pp1', [b'c', b'd']),
1741
(b'pp2', [b'c', b'd']),
1742
(b'pp3', [b'd']),
1743
1743
], self.calls)
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0