← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Matthew Revell
  • Date: 2008-03-05 14:11:35 UTC
  • mto: This revision was merged to the branch mainline in revision 3263.
  • Revision ID: matthew.revell@canonical.com-20080305141135-96jf8j24b9crru6v
Added an admin-guide directory to doc/en and outlined headings for the admin guide in index.txt

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2007 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
from bzrlib import (
18
18
    errors,
22
22
    )
23
23
from bzrlib.revision import NULL_REVISION
24
24
from bzrlib.tests import TestCaseWithMemoryTransport
25
 
from bzrlib.symbol_versioning import deprecated_in
26
25
 
27
26
 
28
27
# Ancestry 1:
166
165
# Complex shortcut
167
166
# This has a failure mode in that a shortcut will find some nodes in common,
168
167
# but the common searcher won't have time to find that one branch is actually
169
 
# in common. The extra nodes at the beginning are because we want to avoid
 
168
# in common. The extra nodes at the top are because we want to avoid
170
169
# walking off the graph. Specifically, node G should be considered common, but
171
170
# is likely to be seen by M long before the common searcher finds it.
172
171
#
182
181
#     |\
183
182
#     e f
184
183
#     | |\
185
 
#     | g h
186
 
#     |/| |
187
 
#     i j |
 
184
#     i | h
 
185
#     |\| |
 
186
#     | g |
 
187
#     | | |
 
188
#     | j |
188
189
#     | | |
189
190
#     | k |
190
191
#     | | |
191
192
#     | l |
192
193
#     |/|/
193
194
#     m n
194
 
complex_shortcut = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
195
 
                    'e':['d'], 'f':['d'], 'g':['f'], 'h':['f'],
196
 
                    'i':['e', 'g'], 'j':['g'], 'k':['j'],
197
 
                    'l':['k'], 'm':['i', 'l'], 'n':['l', 'h']}
198
 
 
199
 
# NULL_REVISION
200
 
#     |
201
 
#     a
202
 
#     |
203
 
#     b
204
 
#     |
205
 
#     c
206
 
#     |
207
 
#     d
208
 
#     |\
209
 
#     e |
210
 
#     | |
211
 
#     f |
212
 
#     | |
213
 
#     g h
214
 
#     | |\
215
 
#     i | j
216
 
#     |\| |
217
 
#     | k |
218
 
#     | | |
219
 
#     | l |
220
 
#     | | |
221
 
#     | m |
222
 
#     | | |
223
 
#     | n |
224
 
#     | | |
225
 
#     | o |
226
 
#     | | |
227
 
#     | p |
228
 
#     | | |
229
 
#     | q |
230
 
#     | | |
231
 
#     | r |
232
 
#     | | |
233
 
#     | s |
234
 
#     | | |
235
 
#     |/|/
236
 
#     t u
237
 
complex_shortcut2 = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
238
 
                    'e':['d'], 'f':['e'], 'g':['f'], 'h':['d'], 'i':['g'],
239
 
                    'j':['h'], 'k':['h', 'i'], 'l':['k'], 'm':['l'], 'n':['m'],
240
 
                    'o':['n'], 'p':['o'], 'q':['p'], 'r':['q'], 's':['r'],
241
 
                    't':['i', 's'], 'u':['s', 'j'],
 
195
complex_shortcut = {'d':[NULL_REVISION],
 
196
                    'x':['d'], 'y':['x'],
 
197
                    'e':['y'], 'f':['d'], 'g':['f', 'i'], 'h':['f'],
 
198
                    'i':['e'], 'j':['g'], 'k':['j'],
 
199
                    'l':['k'], 'm':['i', 's'], 'n':['s', 'h'],
 
200
                    'o':['l'], 'p':['o'], 'q':['p'],
 
201
                    'r':['q'], 's':['r'],
242
202
                    }
243
203
 
244
 
# Graph where different walkers will race to find the common and uncommon
245
 
# nodes.
246
 
#
247
 
# NULL_REVISION
248
 
#     |
249
 
#     a
250
 
#     |
251
 
#     b
252
 
#     |
253
 
#     c
254
 
#     |
255
 
#     d
256
 
#     |\
257
 
#     e k
258
 
#     | |
259
 
#     f-+-p
260
 
#     | | |
261
 
#     | l |
262
 
#     | | |
263
 
#     | m |
264
 
#     | |\|
265
 
#     g n q
266
 
#     |\| |
267
 
#     h o |
268
 
#     |/| |
269
 
#     i r |
270
 
#     | | |
271
 
#     | s |
272
 
#     | | |
273
 
#     | t |
274
 
#     | | |
275
 
#     | u |
276
 
#     | | |
277
 
#     | v |
278
 
#     | | |
279
 
#     | w |
280
 
#     | | |
281
 
#     | x |
282
 
#     | |\|
283
 
#     | y z
284
 
#     |/
285
 
#     j
286
 
#
287
 
# x is found to be common right away, but is the start of a long series of
288
 
# common commits.
289
 
# o is actually common, but the i-j shortcut makes it look like it is actually
290
 
# unique to j at first, you have to traverse all of x->o to find it.
291
 
# q,m gives the walker from j a common point to stop searching, as does p,f.
292
 
# k-n exists so that the second pass still has nodes that are worth searching,
293
 
# rather than instantly cancelling the extra walker.
294
 
 
295
 
racing_shortcuts = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'],
296
 
    'e':['d'], 'f':['e'], 'g':['f'], 'h':['g'], 'i':['h', 'o'], 'j':['i', 'y'],
297
 
    'k':['d'], 'l':['k'], 'm':['l'], 'n':['m'], 'o':['n', 'g'], 'p':['f'],
298
 
    'q':['p', 'm'], 'r':['o'], 's':['r'], 't':['s'], 'u':['t'], 'v':['u'],
299
 
    'w':['v'], 'x':['w'], 'y':['x'], 'z':['x', 'q']}
300
 
 
301
 
 
302
 
# A graph with multiple nodes unique to one side.
303
 
#
304
 
# NULL_REVISION
305
 
#     |
306
 
#     a
307
 
#     |
308
 
#     b
309
 
#     |
310
 
#     c
311
 
#     |
312
 
#     d
313
 
#     |\
314
 
#     e f
315
 
#     |\ \
316
 
#     g h i
317
 
#     |\ \ \
318
 
#     j k l m
319
 
#     | |/ x|
320
 
#     | n o p
321
 
#     | |/  |
322
 
#     | q   |
323
 
#     | |   |
324
 
#     | r   |
325
 
#     | |   |
326
 
#     | s   |
327
 
#     | |   |
328
 
#     | t   |
329
 
#     | |   |
330
 
#     | u   |
331
 
#     | |   |
332
 
#     | v   |
333
 
#     | |   |
334
 
#     | w   |
335
 
#     | |   |
336
 
#     | x   |
337
 
#     |/ \ /
338
 
#     y   z
339
 
#
340
 
 
341
 
multiple_interesting_unique = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'],
342
 
    'd':['c'], 'e':['d'], 'f':['d'], 'g':['e'], 'h':['e'], 'i':['f'],
343
 
    'j':['g'], 'k':['g'], 'l':['h'], 'm':['i'], 'n':['k', 'l'],
344
 
    'o':['m'], 'p':['m', 'l'], 'q':['n', 'o'], 'r':['q'], 's':['r'],
345
 
    't':['s'], 'u':['t'], 'v':['u'], 'w':['v'], 'x':['w'],
346
 
    'y':['j', 'x'], 'z':['x', 'p']}
347
 
 
348
 
 
349
204
# Shortcut with extra root
350
205
# We have a long history shortcut, and an extra root, which is why we can't
351
206
# stop searchers based on seeing NULL_REVISION
383
238
            'f':[NULL_REVISION]}
384
239
 
385
240
 
386
 
# A graph that contains a ghost
387
 
#  NULL_REVISION
388
 
#       |
389
 
#       f
390
 
#       |
391
 
#       e   g
392
 
#      / \ /
393
 
#     b   d
394
 
#     | \ |
395
 
#     a   c
396
 
 
397
 
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
398
 
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
399
 
 
400
 
# A graph that shows we can shortcut finding revnos when reaching them from the
401
 
# side.
402
 
#  NULL_REVISION
403
 
#       |
404
 
#       a
405
 
#       |
406
 
#       b
407
 
#       |
408
 
#       c
409
 
#       |
410
 
#       d
411
 
#       |
412
 
#       e
413
 
#      / \
414
 
#     f   g
415
 
#     |
416
 
#     h
417
 
#     |
418
 
#     i
419
 
 
420
 
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
421
 
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
422
 
 
423
 
 
424
241
class InstrumentedParentsProvider(object):
425
242
 
426
243
    def __init__(self, parents_provider):
432
249
        return self._real_parents_provider.get_parent_map(nodes)
433
250
 
434
251
 
435
 
class TestGraphBase(tests.TestCase):
436
 
 
437
 
    def make_graph(self, ancestors):
438
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
439
 
 
440
 
    def make_breaking_graph(self, ancestors, break_on):
441
 
        """Make a Graph that raises an exception if we hit a node."""
442
 
        g = self.make_graph(ancestors)
443
 
        orig_parent_map = g.get_parent_map
444
 
        def get_parent_map(keys):
445
 
            bad_keys = set(keys).intersection(break_on)
446
 
            if bad_keys:
447
 
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
448
 
            return orig_parent_map(keys)
449
 
        g.get_parent_map = get_parent_map
450
 
        return g
451
 
 
452
 
 
453
252
class TestGraph(TestCaseWithMemoryTransport):
454
253
 
455
254
    def make_graph(self, ancestors):
526
325
        graph = self.make_graph(history_shortcut)
527
326
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
528
327
 
529
 
    def test_lefthand_distance_smoke(self):
530
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
531
 
        graph = self.make_graph(history_shortcut)
532
 
        distance_graph = graph.find_lefthand_distances(['rev3b', 'rev2a'])
533
 
        self.assertEqual({'rev2a': 2, 'rev3b': 3}, distance_graph)
534
 
 
535
 
    def test_lefthand_distance_ghosts(self):
536
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
537
 
        nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
538
 
        graph = self.make_graph(nodes)
539
 
        distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
540
 
        self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
541
 
 
542
328
    def test_recursive_unique_lca(self):
543
329
        """Test finding a unique least common ancestor.
544
330
 
555
341
                         graph.find_unique_lca('rev2a', 'rev2b',
556
342
                         count_steps=True))
557
343
 
558
 
    def assertRemoveDescendants(self, expected, graph, revisions):
559
 
        parents = graph.get_parent_map(revisions)
560
 
        self.assertEqual(expected,
561
 
                         graph._remove_simple_descendants(revisions, parents))
562
 
 
563
 
    def test__remove_simple_descendants(self):
564
 
        graph = self.make_graph(ancestry_1)
565
 
        self.assertRemoveDescendants(set(['rev1']), graph,
566
 
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
567
 
 
568
 
    def test__remove_simple_descendants_disjoint(self):
569
 
        graph = self.make_graph(ancestry_1)
570
 
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
571
 
            set(['rev1', 'rev3']))
572
 
 
573
 
    def test__remove_simple_descendants_chain(self):
574
 
        graph = self.make_graph(ancestry_1)
575
 
        self.assertRemoveDescendants(set(['rev1']), graph,
576
 
            set(['rev1', 'rev2a', 'rev3']))
577
 
 
578
 
    def test__remove_simple_descendants_siblings(self):
579
 
        graph = self.make_graph(ancestry_1)
580
 
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
581
 
            set(['rev2a', 'rev2b', 'rev3']))
582
 
 
583
344
    def test_unique_lca_criss_cross(self):
584
345
        """Ensure we don't pick non-unique lcas in a criss-cross"""
585
346
        graph = self.make_graph(criss_cross)
650
411
 
651
412
    def test_graph_difference_extended_history(self):
652
413
        graph = self.make_graph(extended_history_shortcut)
 
414
        self.expectFailure('find_difference cannot handle shortcuts',
 
415
            self.assertEqual, (set(['e']), set(['f'])),
 
416
                graph.find_difference('e', 'f'))
653
417
        self.assertEqual((set(['e']), set(['f'])),
654
418
                         graph.find_difference('e', 'f'))
655
419
        self.assertEqual((set(['f']), set(['e'])),
662
426
 
663
427
    def test_graph_difference_complex_shortcut(self):
664
428
        graph = self.make_graph(complex_shortcut)
665
 
        self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
 
429
        self.expectFailure('find_difference cannot handle shortcuts',
 
430
            self.assertEqual, (set(['m']), set(['h', 'n'])),
 
431
                graph.find_difference('m', 'n'))
 
432
        self.assertEqual((set(['m']), set(['h', 'n'])),
666
433
                         graph.find_difference('m', 'n'))
667
434
 
668
 
    def test_graph_difference_complex_shortcut2(self):
669
 
        graph = self.make_graph(complex_shortcut2)
670
 
        self.assertEqual((set(['t']), set(['j', 'u'])),
671
 
                         graph.find_difference('t', 'u'))
672
 
 
673
435
    def test_graph_difference_shortcut_extra_root(self):
674
436
        graph = self.make_graph(shortcut_extra_root)
 
437
        self.expectFailure('find_difference cannot handle shortcuts',
 
438
            self.assertEqual, (set(['e']), set(['f', 'g'])),
 
439
                graph.find_difference('e', 'f'))
675
440
        self.assertEqual((set(['e']), set(['f', 'g'])),
676
441
                         graph.find_difference('e', 'f'))
677
442
 
678
 
 
679
443
    def test_stacked_parents_provider(self):
680
444
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
681
445
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
682
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
683
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
684
 
                         stacked.get_parent_map(['rev1', 'rev2']))
685
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
686
 
                         stacked.get_parent_map(['rev2', 'rev1']))
687
 
        self.assertEqual({'rev2':['rev3']},
688
 
                         stacked.get_parent_map(['rev2', 'rev2']))
689
 
        self.assertEqual({'rev1':['rev4']},
690
 
                         stacked.get_parent_map(['rev1', 'rev1']))
691
 
    
692
 
    def test_stacked_parents_provider_overlapping(self):
693
 
        # rev2 is availible in both providers.
694
 
        # 1
695
 
        # |
696
 
        # 2
697
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
699
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
700
 
        self.assertEqual({'rev2': ['rev1']},
701
 
                         stacked.get_parent_map(['rev2']))
702
 
 
703
 
    def test__stacked_parents_provider_deprecated(self):
704
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
705
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
706
 
        stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
707
 
                    _mod_graph._StackedParentsProvider, [parents1, parents2])
 
446
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
708
447
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
709
448
                         stacked.get_parent_map(['rev1', 'rev2']))
710
449
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
738
477
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
739
478
        self.assertTrue('null:' not in instrumented_provider.calls)
740
479
 
741
 
    def test_is_between(self):
742
 
        graph = self.make_graph(ancestry_1)
743
 
        self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
744
 
        self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
745
 
        self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
746
 
        self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
747
 
        self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
748
 
        self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
749
 
        self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
750
 
        self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
751
 
 
752
480
    def test_is_ancestor_boundary(self):
753
481
        """Ensure that we avoid searching the whole graph.
754
 
 
 
482
        
755
483
        This requires searching through b as a common ancestor, so we
756
484
        can identify that e is common.
757
485
        """
761
489
        self.assertFalse(graph.is_ancestor('a', 'c'))
762
490
        self.assertTrue('null:' not in instrumented_provider.calls)
763
491
 
764
 
    def test_iter_ancestry(self):
765
 
        nodes = boundary.copy()
766
 
        nodes[NULL_REVISION] = ()
767
 
        graph = self.make_graph(nodes)
768
 
        expected = nodes.copy()
769
 
        expected.pop('a') # 'a' is not in the ancestry of 'c', all the
770
 
                          # other nodes are
771
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
772
 
        self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
773
 
 
774
 
    def test_iter_ancestry_with_ghost(self):
775
 
        graph = self.make_graph(with_ghost)
776
 
        expected = with_ghost.copy()
777
 
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
778
 
        expected['g'] = None
779
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
780
 
        expected.pop('a')
781
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
782
 
 
783
492
    def test_filter_candidate_lca(self):
784
493
        """Test filter_candidate_lca for a corner case
785
494
 
885
594
 
886
595
    def _run_heads_break_deeper(self, graph_dict, search):
887
596
        """Run heads on a graph-as-a-dict.
888
 
 
 
597
        
889
598
        If the search asks for the parents of 'deeper' the test will fail.
890
599
        """
891
600
        class stub(object):
1032
741
        :param next: A callable to advance the search.
1033
742
        """
1034
743
        for seen, recipe, included_keys, starts, stops in instructions:
1035
 
            # Adjust for recipe contract changes that don't vary for all the
1036
 
            # current tests.
1037
 
            recipe = ('search',) + recipe
1038
744
            next()
1039
745
            if starts is not None:
1040
746
                search.start_searching(starts)
1054
760
        search = graph._make_breadth_first_searcher(['head'])
1055
761
        # At the start, nothing has been seen, to its all excluded:
1056
762
        result = search.get_result()
1057
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
 
763
        self.assertEqual((set(['head']), set(['head']), 0),
1058
764
            result.get_recipe())
1059
765
        self.assertEqual(set(), result.get_keys())
1060
766
        self.assertEqual(set(), search.seen)
1086
792
        search.start_searching(['head'])
1087
793
        # head has been seen:
1088
794
        result = search.get_result()
1089
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
 
795
        self.assertEqual((set(['head']), set(['child']), 1),
1090
796
            result.get_recipe())
1091
797
        self.assertEqual(set(['head']), result.get_keys())
1092
798
        self.assertEqual(set(['head']), search.seen)
1123
829
        search = graph._make_breadth_first_searcher(['head'])
1124
830
        expected = [
1125
831
            # NULL_REVISION and ghost1 have not been returned
1126
 
            (set(['head']),
1127
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
832
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1128
833
             ['head'], None, [NULL_REVISION, 'ghost1']),
1129
834
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1130
835
            # next iteration.
1137
842
        search = graph._make_breadth_first_searcher(['head'])
1138
843
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1139
844
 
1140
 
    def test_breadth_first_stop_searching_late(self):
1141
 
        # A client should be able to say 'stop node X' and have it excluded
1142
 
        # from the result even if X was seen in an older iteration of the
1143
 
        # search.
1144
 
        graph = self.make_graph({
1145
 
            'head':['middle'],
1146
 
            'middle':['child'],
1147
 
            'child':[NULL_REVISION],
1148
 
            NULL_REVISION:[],
1149
 
            })
1150
 
        search = graph._make_breadth_first_searcher(['head'])
1151
 
        expected = [
1152
 
            (set(['head']), (set(['head']), set(['middle']), 1),
1153
 
             ['head'], None, None),
1154
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
1155
 
             ['head', 'middle'], None, None),
1156
 
            # 'middle' came from the previous iteration, but we don't stop
1157
 
            # searching it until *after* advancing the searcher.
1158
 
            (set(['head', 'middle', 'child']),
1159
 
             (set(['head']), set(['middle', 'child']), 1),
1160
 
             ['head'], None, ['middle', 'child']),
1161
 
            ]
1162
 
        self.assertSeenAndResult(expected, search, search.next)
1163
 
        # using next_with_ghosts:
1164
 
        search = graph._make_breadth_first_searcher(['head'])
1165
 
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1166
 
 
1167
845
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1168
846
        graph = self.make_graph({
1169
847
            'head':['child', 'ghost'],
1246
924
        self.assertRaises(StopIteration, search.next)
1247
925
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
926
        result = search.get_result()
1249
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
927
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1250
928
            result.get_recipe())
1251
929
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1252
930
        # using next_with_ghosts:
1255
933
        self.assertRaises(StopIteration, search.next)
1256
934
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
935
        result = search.get_result()
1258
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
936
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1259
937
            result.get_recipe())
1260
938
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1261
939
 
1262
940
 
1263
 
class TestFindUniqueAncestors(TestGraphBase):
1264
 
 
1265
 
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1266
 
        actual = graph.find_unique_ancestors(node, common)
1267
 
        self.assertEqual(expected, sorted(actual))
1268
 
 
1269
 
    def test_empty_set(self):
1270
 
        graph = self.make_graph(ancestry_1)
1271
 
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1272
 
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1273
 
        self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1274
 
 
1275
 
    def test_single_node(self):
1276
 
        graph = self.make_graph(ancestry_1)
1277
 
        self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1278
 
        self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1279
 
        self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1280
 
 
1281
 
    def test_minimal_ancestry(self):
1282
 
        graph = self.make_breaking_graph(extended_history_shortcut,
1283
 
                                         [NULL_REVISION, 'a', 'b'])
1284
 
        self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1285
 
 
1286
 
        graph = self.make_breaking_graph(extended_history_shortcut,
1287
 
                                         ['b'])
1288
 
        self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1289
 
 
1290
 
        graph = self.make_breaking_graph(complex_shortcut,
1291
 
                                         ['a', 'b'])
1292
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1293
 
        self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1294
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1295
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1296
 
 
1297
 
    def test_in_ancestry(self):
1298
 
        graph = self.make_graph(ancestry_1)
1299
 
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1300
 
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1301
 
 
1302
 
    def test_multiple_revisions(self):
1303
 
        graph = self.make_graph(ancestry_1)
1304
 
        self.assertFindUniqueAncestors(graph,
1305
 
            ['rev4'], 'rev4', ['rev3', 'rev2b'])
1306
 
        self.assertFindUniqueAncestors(graph,
1307
 
            ['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1308
 
 
1309
 
    def test_complex_shortcut(self):
1310
 
        graph = self.make_graph(complex_shortcut)
1311
 
        self.assertFindUniqueAncestors(graph,
1312
 
            ['h', 'n'], 'n', ['m'])
1313
 
        self.assertFindUniqueAncestors(graph,
1314
 
            ['e', 'i', 'm'], 'm', ['n'])
1315
 
 
1316
 
    def test_complex_shortcut2(self):
1317
 
        graph = self.make_graph(complex_shortcut2)
1318
 
        self.assertFindUniqueAncestors(graph,
1319
 
            ['j', 'u'], 'u', ['t'])
1320
 
        self.assertFindUniqueAncestors(graph,
1321
 
            ['t'], 't', ['u'])
1322
 
 
1323
 
    def test_multiple_interesting_unique(self):
1324
 
        graph = self.make_graph(multiple_interesting_unique)
1325
 
        self.assertFindUniqueAncestors(graph,
1326
 
            ['j', 'y'], 'y', ['z'])
1327
 
        self.assertFindUniqueAncestors(graph,
1328
 
            ['p', 'z'], 'z', ['y'])
1329
 
 
1330
 
    def test_racing_shortcuts(self):
1331
 
        graph = self.make_graph(racing_shortcuts)
1332
 
        self.assertFindUniqueAncestors(graph,
1333
 
            ['p', 'q', 'z'], 'z', ['y'])
1334
 
        self.assertFindUniqueAncestors(graph,
1335
 
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1336
 
 
1337
 
 
1338
 
class TestGraphFindDistanceToNull(TestGraphBase):
1339
 
    """Test an api that should be able to compute a revno"""
1340
 
 
1341
 
    def assertFindDistance(self, revno, graph, target_id, known_ids):
1342
 
        """Assert the output of Graph.find_distance_to_null()"""
1343
 
        actual = graph.find_distance_to_null(target_id, known_ids)
1344
 
        self.assertEqual(revno, actual)
1345
 
 
1346
 
    def test_nothing_known(self):
1347
 
        graph = self.make_graph(ancestry_1)
1348
 
        self.assertFindDistance(0, graph, NULL_REVISION, [])
1349
 
        self.assertFindDistance(1, graph, 'rev1', [])
1350
 
        self.assertFindDistance(2, graph, 'rev2a', [])
1351
 
        self.assertFindDistance(2, graph, 'rev2b', [])
1352
 
        self.assertFindDistance(3, graph, 'rev3', [])
1353
 
        self.assertFindDistance(4, graph, 'rev4', [])
1354
 
 
1355
 
    def test_rev_is_ghost(self):
1356
 
        graph = self.make_graph(ancestry_1)
1357
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1358
 
                              graph.find_distance_to_null, 'rev_missing', [])
1359
 
        self.assertEqual('rev_missing', e.revision_id)
1360
 
        self.assertEqual('rev_missing', e.ghost_revision_id)
1361
 
 
1362
 
    def test_ancestor_is_ghost(self):
1363
 
        graph = self.make_graph({'rev':['parent']})
1364
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1365
 
                              graph.find_distance_to_null, 'rev', [])
1366
 
        self.assertEqual('rev', e.revision_id)
1367
 
        self.assertEqual('parent', e.ghost_revision_id)
1368
 
 
1369
 
    def test_known_in_ancestry(self):
1370
 
        graph = self.make_graph(ancestry_1)
1371
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1372
 
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1373
 
 
1374
 
    def test_known_in_ancestry_limits(self):
1375
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1376
 
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1377
 
 
1378
 
    def test_target_is_ancestor(self):
1379
 
        graph = self.make_graph(ancestry_1)
1380
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1381
 
 
1382
 
    def test_target_is_ancestor_limits(self):
1383
 
        """We shouldn't search all history if we run into ourselves"""
1384
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1385
 
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1386
 
 
1387
 
    def test_target_parallel_to_known_limits(self):
1388
 
        # Even though the known revision isn't part of the other ancestry, they
1389
 
        # eventually converge
1390
 
        graph = self.make_breaking_graph(with_tail, ['a'])
1391
 
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
1392
 
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
1393
 
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
1394
 
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1395
 
 
1396
 
 
1397
 
class TestFindMergeOrder(TestGraphBase):
1398
 
 
1399
 
    def assertMergeOrder(self, expected, graph, tip, base_revisions):
1400
 
        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1401
 
 
1402
 
    def test_parents(self):
1403
 
        graph = self.make_graph(ancestry_1)
1404
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1405
 
                                                        ['rev3', 'rev2b'])
1406
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1407
 
                                                        ['rev2b', 'rev3'])
1408
 
 
1409
 
    def test_ancestors(self):
1410
 
        graph = self.make_graph(ancestry_1)
1411
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1412
 
                                                        ['rev1', 'rev2b'])
1413
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1414
 
                                                        ['rev2b', 'rev1'])
1415
 
 
1416
 
    def test_shortcut_one_ancestor(self):
1417
 
        # When we have enough info, we can stop searching
1418
 
        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1419
 
        # Single ancestors shortcut right away
1420
 
        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1421
 
 
1422
 
    def test_shortcut_after_one_ancestor(self):
1423
 
        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1424
 
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1425
 
 
1426
 
 
1427
941
class TestCachingParentsProvider(tests.TestCase):
1428
 
    """These tests run with:
1429
 
 
1430
 
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1431
 
    ghost.
1432
 
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
1433
 
    """
1434
942
 
1435
943
    def setUp(self):
1436
944
        super(TestCachingParentsProvider, self).setUp()
1455
963
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1456
964
        # No new calls
1457
965
        self.assertEqual(['b'], self.inst_pp.calls)
 
966
        self.assertEqual({'b':None}, self.caching_pp._cache)
1458
967
 
1459
968
    def test_get_parent_map_mixed(self):
1460
969
        """Anything that can be returned from cache, should be"""
1471
980
        # Use sorted because we don't care about the order, just that each is
1472
981
        # only present 1 time.
1473
982
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1474
 
 
1475
 
    def test_note_missing_key(self):
1476
 
        """After noting that a key is missing it is cached."""
1477
 
        self.caching_pp.note_missing_key('b')
1478
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1479
 
        self.assertEqual([], self.inst_pp.calls)
1480
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1481
 
 
1482
 
 
1483
 
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1484
 
    """Test the behaviour when parents are provided that were not requested."""
1485
 
 
1486
 
    def setUp(self):
1487
 
        super(TestCachingParentsProviderExtras, self).setUp()
1488
 
        class ExtraParentsProvider(object):
1489
 
 
1490
 
            def get_parent_map(self, keys):
1491
 
                return {'rev1': [], 'rev2': ['rev1',]}
1492
 
 
1493
 
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1494
 
        self.caching_pp = _mod_graph.CachingParentsProvider(
1495
 
            get_parent_map=self.inst_pp.get_parent_map)
1496
 
 
1497
 
    def test_uncached(self):
1498
 
        self.caching_pp.disable_cache()
1499
 
        self.assertEqual({'rev1': []},
1500
 
                         self.caching_pp.get_parent_map(['rev1']))
1501
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1502
 
        self.assertIs(None, self.caching_pp._cache)
1503
 
 
1504
 
    def test_cache_initially_empty(self):
1505
 
        self.assertEqual({}, self.caching_pp._cache)
1506
 
 
1507
 
    def test_cached(self):
1508
 
        self.assertEqual({'rev1': []},
1509
 
                         self.caching_pp.get_parent_map(['rev1']))
1510
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1511
 
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1512
 
                         self.caching_pp._cache)
1513
 
        self.assertEqual({'rev1': []},
1514
 
                          self.caching_pp.get_parent_map(['rev1']))
1515
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1516
 
 
1517
 
    def test_disable_cache_clears_cache(self):
1518
 
        # Put something in the cache
1519
 
        self.caching_pp.get_parent_map(['rev1'])
1520
 
        self.assertEqual(2, len(self.caching_pp._cache))
1521
 
        self.caching_pp.disable_cache()
1522
 
        self.assertIs(None, self.caching_pp._cache)
1523
 
 
1524
 
    def test_enable_cache_raises(self):
1525
 
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1526
 
        self.assertEqual('Cache enabled when already enabled.', str(e))
1527
 
 
1528
 
    def test_cache_misses(self):
1529
 
        self.caching_pp.get_parent_map(['rev3'])
1530
 
        self.caching_pp.get_parent_map(['rev3'])
1531
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1532
 
 
1533
 
    def test_no_cache_misses(self):
1534
 
        self.caching_pp.disable_cache()
1535
 
        self.caching_pp.enable_cache(cache_misses=False)
1536
 
        self.caching_pp.get_parent_map(['rev3'])
1537
 
        self.caching_pp.get_parent_map(['rev3'])
1538
 
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1539
 
 
1540
 
    def test_cache_extras(self):
1541
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1542
 
        self.assertEqual({'rev2': ['rev1']},
1543
 
                         self.caching_pp.get_parent_map(['rev2']))
1544
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1545
 
 
1546
 
 
1547
 
class TestCollapseLinearRegions(tests.TestCase):
1548
 
 
1549
 
    def assertCollapsed(self, collapsed, original):
1550
 
        self.assertEqual(collapsed,
1551
 
                         _mod_graph.collapse_linear_regions(original))
1552
 
 
1553
 
    def test_collapse_nothing(self):
1554
 
        d = {1:[2, 3], 2:[], 3:[]}
1555
 
        self.assertCollapsed(d, d)
1556
 
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1557
 
        self.assertCollapsed(d, d)
1558
 
 
1559
 
    def test_collapse_chain(self):
1560
 
        # Any time we have a linear chain, we should be able to collapse
1561
 
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1562
 
        self.assertCollapsed({1:[5], 5:[]}, d)
1563
 
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1564
 
        self.assertCollapsed({5:[1], 1:[]}, d)
1565
 
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1566
 
        self.assertCollapsed({5:[2], 2:[]}, d)
1567
 
 
1568
 
    def test_collapse_with_multiple_children(self):
1569
 
        #    7
1570
 
        #    |
1571
 
        #    6
1572
 
        #   / \
1573
 
        #  4   5
1574
 
        #  |   |
1575
 
        #  2   3
1576
 
        #   \ /
1577
 
        #    1
1578
 
        #
1579
 
        # 4 and 5 cannot be removed because 6 has 2 children
1580
 
        # 2 and 3 cannot be removed because 1 has 2 parents
1581
 
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1582
 
        self.assertCollapsed(d, d)
1583
 
 
1584
 
 
1585
 
class TestGraphThunkIdsToKeys(tests.TestCase):
1586
 
 
1587
 
    def test_heads(self):
1588
 
        # A
1589
 
        # |\
1590
 
        # B C
1591
 
        # |/
1592
 
        # D
1593
 
        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1594
 
             ('B',): [('A',)], ('A',): []}
1595
 
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1596
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1597
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1598
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1599
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1600
 
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1601
 
 
1602
 
 
1603
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1604
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1605
 
 
1606
 
    def test_get_keys(self):
1607
 
        builder = self.make_branch_builder('b')
1608
 
        builder.start_series()
1609
 
        builder.build_snapshot('rev-1', None, [
1610
 
            ('add', ('', 'root-id', 'directory', ''))])
1611
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1612
 
        builder.finish_series()
1613
 
        repo = builder.get_branch().repository
1614
 
        repo.lock_read()
1615
 
        self.addCleanup(repo.unlock)
1616
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1617
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1618
 
 
1619
 
    def test_get_keys_excludes_ghosts(self):
1620
 
        builder = self.make_branch_builder('b')
1621
 
        builder.start_series()
1622
 
        builder.build_snapshot('rev-1', None, [
1623
 
            ('add', ('', 'root-id', 'directory', ''))])
1624
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1625
 
        builder.finish_series()
1626
 
        repo = builder.get_branch().repository
1627
 
        repo.lock_read()
1628
 
        self.addCleanup(repo.unlock)
1629
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1630
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1631
 
 
1632
 
    def test_get_keys_excludes_null(self):
1633
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1634
 
        # somewhere other than the last element, which can happen in real
1635
 
        # ancestries.
1636
 
        class StubGraph(object):
1637
 
            def iter_ancestry(self, keys):
1638
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1639
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1640
 
        result_keys = result._get_keys(StubGraph())
1641
 
        # Only the non-null keys from the ancestry appear.
1642
 
        self.assertEqual(set(['foo']), set(result_keys))
1643
 
 
1644
 
 
1645
 
class TestPendingAncestryResultRefine(TestGraphBase):
1646
 
 
1647
 
    def test_refine(self):
1648
 
        # Used when pulling from a stacked repository, so test some revisions
1649
 
        # being satisfied from the stacking branch.
1650
 
        g = self.make_graph(
1651
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1652
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1653
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1654
 
        result = result.refine(set(['tip']), set(['mid']))
1655
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1656
 
        result = result.refine(set(['mid', 'tag', 'base']),
1657
 
            set([NULL_REVISION]))
1658
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1659
 
        self.assertTrue(result.is_empty())
1660
 
 
1661
 
 
1662
 
class TestSearchResultRefine(TestGraphBase):
1663
 
 
1664
 
    def test_refine(self):
1665
 
        # Used when pulling from a stacked repository, so test some revisions
1666
 
        # being satisfied from the stacking branch.
1667
 
        g = self.make_graph(
1668
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1669
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1670
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1671
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1672
 
        result = result.refine(set(['tip']), set(['mid']))
1673
 
        recipe = result.get_recipe()
1674
 
        # We should be starting from tag (original head) and mid (seen ref)
1675
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1676
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1677
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1678
 
        self.assertEqual(3, recipe[3])
1679
 
        result = result.refine(set(['mid', 'tag', 'base']),
1680
 
            set([NULL_REVISION]))
1681
 
        recipe = result.get_recipe()
1682
 
        # We should be starting from nothing (NULL was known as a cut point)
1683
 
        self.assertEqual(set([]), recipe[1])
1684
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1685
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1686
 
        # define this as not including mid, for minimal results, but it is
1687
 
        # still 'correct' to include mid, and simpler/easier.
1688
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1689
 
        self.assertEqual(0, recipe[3])
1690
 
        self.assertTrue(result.is_empty())