← 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: Canonical.com Patch Queue Manager
  • Date: 2008-03-13 23:45:11 UTC
  • mfrom: (3272.1.1 ianc-integration)
  • Revision ID: pqm@pqm.ubuntu.com-20080313234511-fkj5oa8gm3nrfcro
(Neil Martinsen-Burrell) Explain version-info --custom in the User
        Guide

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1
 
# Copyright (C) 2007-2011 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,
19
19
    graph as _mod_graph,
 
20
    symbol_versioning,
20
21
    tests,
21
22
    )
22
23
from bzrlib.revision import NULL_REVISION
164
165
# Complex shortcut
165
166
# This has a failure mode in that a shortcut will find some nodes in common,
166
167
# but the common searcher won't have time to find that one branch is actually
167
 
# 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
168
169
# walking off the graph. Specifically, node G should be considered common, but
169
170
# is likely to be seen by M long before the common searcher finds it.
170
171
#
180
181
#     |\
181
182
#     e f
182
183
#     | |\
183
 
#     | g h
184
 
#     |/| |
185
 
#     i j |
 
184
#     i | h
 
185
#     |\| |
 
186
#     | g |
 
187
#     | | |
 
188
#     | j |
186
189
#     | | |
187
190
#     | k |
188
191
#     | | |
189
192
#     | l |
190
193
#     |/|/
191
194
#     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']}
196
 
 
197
 
# NULL_REVISION
198
 
#     |
199
 
#     a
200
 
#     |
201
 
#     b
202
 
#     |
203
 
#     c
204
 
#     |
205
 
#     d
206
 
#     |\
207
 
#     e |
208
 
#     | |
209
 
#     f |
210
 
#     | |
211
 
#     g h
212
 
#     | |\
213
 
#     i | j
214
 
#     |\| |
215
 
#     | k |
216
 
#     | | |
217
 
#     | l |
218
 
#     | | |
219
 
#     | m |
220
 
#     | | |
221
 
#     | n |
222
 
#     | | |
223
 
#     | o |
224
 
#     | | |
225
 
#     | p |
226
 
#     | | |
227
 
#     | q |
228
 
#     | | |
229
 
#     | r |
230
 
#     | | |
231
 
#     | s |
232
 
#     | | |
233
 
#     |/|/
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'],
 
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'],
240
202
                    }
241
203
 
242
 
# Graph where different walkers will race to find the common and uncommon
243
 
# nodes.
244
 
#
245
 
# NULL_REVISION
246
 
#     |
247
 
#     a
248
 
#     |
249
 
#     b
250
 
#     |
251
 
#     c
252
 
#     |
253
 
#     d
254
 
#     |\
255
 
#     e k
256
 
#     | |
257
 
#     f-+-p
258
 
#     | | |
259
 
#     | l |
260
 
#     | | |
261
 
#     | m |
262
 
#     | |\|
263
 
#     g n q
264
 
#     |\| |
265
 
#     h o |
266
 
#     |/| |
267
 
#     i r |
268
 
#     | | |
269
 
#     | s |
270
 
#     | | |
271
 
#     | t |
272
 
#     | | |
273
 
#     | u |
274
 
#     | | |
275
 
#     | v |
276
 
#     | | |
277
 
#     | w |
278
 
#     | | |
279
 
#     | x |
280
 
#     | |\|
281
 
#     | y z
282
 
#     |/
283
 
#     j
284
 
#
285
 
# x is found to be common right away, but is the start of a long series of
286
 
# common commits.
287
 
# o is actually common, but the i-j shortcut makes it look like it is actually
288
 
# unique to j at first, you have to traverse all of x->o to find it.
289
 
# q,m gives the walker from j a common point to stop searching, as does p,f.
290
 
# k-n exists so that the second pass still has nodes that are worth searching,
291
 
# rather than instantly cancelling the extra walker.
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']}
298
 
 
299
 
 
300
 
# A graph with multiple nodes unique to one side.
301
 
#
302
 
# NULL_REVISION
303
 
#     |
304
 
#     a
305
 
#     |
306
 
#     b
307
 
#     |
308
 
#     c
309
 
#     |
310
 
#     d
311
 
#     |\
312
 
#     e f
313
 
#     |\ \
314
 
#     g h i
315
 
#     |\ \ \
316
 
#     j k l m
317
 
#     | |/ x|
318
 
#     | n o p
319
 
#     | |/  |
320
 
#     | q   |
321
 
#     | |   |
322
 
#     | r   |
323
 
#     | |   |
324
 
#     | s   |
325
 
#     | |   |
326
 
#     | t   |
327
 
#     | |   |
328
 
#     | u   |
329
 
#     | |   |
330
 
#     | v   |
331
 
#     | |   |
332
 
#     | w   |
333
 
#     | |   |
334
 
#     | x   |
335
 
#     |/ \ /
336
 
#     y   z
337
 
#
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']}
345
 
 
346
 
 
347
204
# Shortcut with extra root
348
205
# We have a long history shortcut, and an extra root, which is why we can't
349
206
# stop searchers based on seeing NULL_REVISION
381
238
            'f':[NULL_REVISION]}
382
239
 
383
240
 
384
 
# A graph that contains a ghost
385
 
#  NULL_REVISION
386
 
#       |
387
 
#       f
388
 
#       |
389
 
#       e   g
390
 
#      / \ /
391
 
#     b   d
392
 
#     | \ |
393
 
#     a   c
394
 
 
395
 
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
396
 
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
397
 
 
398
 
# A graph that shows we can shortcut finding revnos when reaching them from the
399
 
# side.
400
 
#  NULL_REVISION
401
 
#       |
402
 
#       a
403
 
#       |
404
 
#       b
405
 
#       |
406
 
#       c
407
 
#       |
408
 
#       d
409
 
#       |
410
 
#       e
411
 
#      / \
412
 
#     f   g
413
 
#     |
414
 
#     h
415
 
#     |
416
 
#     i
417
 
 
418
 
with_tail = {'a':[NULL_REVISION], 'b':['a'], 'c':['b'], 'd':['c'], 'e':['d'],
419
 
             'f':['e'], 'g':['e'], 'h':['f'], 'i':['h']}
420
 
 
421
 
 
422
241
class InstrumentedParentsProvider(object):
423
242
 
424
243
    def __init__(self, parents_provider):
425
244
        self.calls = []
426
245
        self._real_parents_provider = parents_provider
427
 
        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
428
 
        if get_cached is not None:
429
 
            # Only expose the underlying 'get_cached_parent_map' function if
430
 
            # the wrapped provider has it.
431
 
            self.get_cached_parent_map = self._get_cached_parent_map
432
246
 
433
247
    def get_parent_map(self, nodes):
434
248
        self.calls.extend(nodes)
435
249
        return self._real_parents_provider.get_parent_map(nodes)
436
250
 
437
 
    def _get_cached_parent_map(self, nodes):
438
 
        self.calls.append(('cached', sorted(nodes)))
439
 
        return self._real_parents_provider.get_cached_parent_map(nodes)
440
 
 
441
 
 
442
 
class SharedInstrumentedParentsProvider(object):
443
 
 
444
 
    def __init__(self, parents_provider, calls, info):
445
 
        self.calls = calls
446
 
        self.info = info
447
 
        self._real_parents_provider = parents_provider
448
 
        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
449
 
        if get_cached is not None:
450
 
            # Only expose the underlying 'get_cached_parent_map' function if
451
 
            # the wrapped provider has it.
452
 
            self.get_cached_parent_map = self._get_cached_parent_map
453
 
 
454
 
    def get_parent_map(self, nodes):
455
 
        self.calls.append((self.info, sorted(nodes)))
456
 
        return self._real_parents_provider.get_parent_map(nodes)
457
 
 
458
 
    def _get_cached_parent_map(self, nodes):
459
 
        self.calls.append((self.info, 'cached', sorted(nodes)))
460
 
        return self._real_parents_provider.get_cached_parent_map(nodes)
461
 
 
462
 
 
463
 
class TestGraphBase(tests.TestCase):
464
 
 
465
 
    def make_graph(self, ancestors):
466
 
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
467
 
 
468
 
    def make_breaking_graph(self, ancestors, break_on):
469
 
        """Make a Graph that raises an exception if we hit a node."""
470
 
        g = self.make_graph(ancestors)
471
 
        orig_parent_map = g.get_parent_map
472
 
        def get_parent_map(keys):
473
 
            bad_keys = set(keys).intersection(break_on)
474
 
            if bad_keys:
475
 
                self.fail('key(s) %s was accessed' % (sorted(bad_keys),))
476
 
            return orig_parent_map(keys)
477
 
        g.get_parent_map = get_parent_map
478
 
        return g
479
 
 
480
251
 
481
252
class TestGraph(TestCaseWithMemoryTransport):
482
253
 
554
325
        graph = self.make_graph(history_shortcut)
555
326
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
556
327
 
557
 
    def test_lefthand_distance_smoke(self):
558
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
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)
562
 
 
563
 
    def test_lefthand_distance_ghosts(self):
564
 
        """A simple does it work test for graph.lefthand_distance(keys)."""
565
 
        nodes = {'nonghost':[NULL_REVISION], 'toghost':['ghost']}
566
 
        graph = self.make_graph(nodes)
567
 
        distance_graph = graph.find_lefthand_distances(['nonghost', 'toghost'])
568
 
        self.assertEqual({'nonghost': 1, 'toghost': -1}, distance_graph)
569
 
 
570
328
    def test_recursive_unique_lca(self):
571
329
        """Test finding a unique least common ancestor.
572
330
 
583
341
                         graph.find_unique_lca('rev2a', 'rev2b',
584
342
                         count_steps=True))
585
343
 
586
 
    def assertRemoveDescendants(self, expected, graph, revisions):
587
 
        parents = graph.get_parent_map(revisions)
588
 
        self.assertEqual(expected,
589
 
                         graph._remove_simple_descendants(revisions, parents))
590
 
 
591
 
    def test__remove_simple_descendants(self):
592
 
        graph = self.make_graph(ancestry_1)
593
 
        self.assertRemoveDescendants(set(['rev1']), graph,
594
 
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
595
 
 
596
 
    def test__remove_simple_descendants_disjoint(self):
597
 
        graph = self.make_graph(ancestry_1)
598
 
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
599
 
            set(['rev1', 'rev3']))
600
 
 
601
 
    def test__remove_simple_descendants_chain(self):
602
 
        graph = self.make_graph(ancestry_1)
603
 
        self.assertRemoveDescendants(set(['rev1']), graph,
604
 
            set(['rev1', 'rev2a', 'rev3']))
605
 
 
606
 
    def test__remove_simple_descendants_siblings(self):
607
 
        graph = self.make_graph(ancestry_1)
608
 
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
609
 
            set(['rev2a', 'rev2b', 'rev3']))
610
 
 
611
344
    def test_unique_lca_criss_cross(self):
612
345
        """Ensure we don't pick non-unique lcas in a criss-cross"""
613
346
        graph = self.make_graph(criss_cross)
678
411
 
679
412
    def test_graph_difference_extended_history(self):
680
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'))
681
417
        self.assertEqual((set(['e']), set(['f'])),
682
418
                         graph.find_difference('e', 'f'))
683
419
        self.assertEqual((set(['f']), set(['e'])),
690
426
 
691
427
    def test_graph_difference_complex_shortcut(self):
692
428
        graph = self.make_graph(complex_shortcut)
693
 
        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'])),
694
433
                         graph.find_difference('m', 'n'))
695
434
 
696
 
    def test_graph_difference_complex_shortcut2(self):
697
 
        graph = self.make_graph(complex_shortcut2)
698
 
        self.assertEqual((set(['t']), set(['j', 'u'])),
699
 
                         graph.find_difference('t', 'u'))
700
 
 
701
435
    def test_graph_difference_shortcut_extra_root(self):
702
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'))
703
440
        self.assertEqual((set(['e']), set(['f', 'g'])),
704
441
                         graph.find_difference('e', 'f'))
705
442
 
 
443
    def test_stacked_parents_provider(self):
 
444
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
445
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
446
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
 
447
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
 
448
                         stacked.get_parent_map(['rev1', 'rev2']))
 
449
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
 
450
                         stacked.get_parent_map(['rev2', 'rev1']))
 
451
        self.assertEqual({'rev2':['rev3']},
 
452
                         stacked.get_parent_map(['rev2', 'rev2']))
 
453
        self.assertEqual({'rev1':['rev4']},
 
454
                         stacked.get_parent_map(['rev1', 'rev1']))
 
455
 
706
456
    def test_iter_topo_order(self):
707
457
        graph = self.make_graph(ancestry_1)
708
458
        args = ['rev2a', 'rev3', 'rev1']
727
477
        instrumented_graph.is_ancestor('rev2a', 'rev2b')
728
478
        self.assertTrue('null:' not in instrumented_provider.calls)
729
479
 
730
 
    def test_is_between(self):
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'))
740
 
 
741
480
    def test_is_ancestor_boundary(self):
742
481
        """Ensure that we avoid searching the whole graph.
743
 
 
 
482
        
744
483
        This requires searching through b as a common ancestor, so we
745
484
        can identify that e is common.
746
485
        """
750
489
        self.assertFalse(graph.is_ancestor('a', 'c'))
751
490
        self.assertTrue('null:' not in instrumented_provider.calls)
752
491
 
753
 
    def test_iter_ancestry(self):
754
 
        nodes = boundary.copy()
755
 
        nodes[NULL_REVISION] = ()
756
 
        graph = self.make_graph(nodes)
757
 
        expected = nodes.copy()
758
 
        expected.pop('a') # 'a' is not in the ancestry of 'c', all the
759
 
                          # other nodes are
760
 
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
761
 
        self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
762
 
 
763
 
    def test_iter_ancestry_with_ghost(self):
764
 
        graph = self.make_graph(with_ghost)
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'])))
771
 
 
772
492
    def test_filter_candidate_lca(self):
773
493
        """Test filter_candidate_lca for a corner case
774
494
 
874
594
 
875
595
    def _run_heads_break_deeper(self, graph_dict, search):
876
596
        """Run heads on a graph-as-a-dict.
877
 
 
 
597
        
878
598
        If the search asks for the parents of 'deeper' the test will fail.
879
599
        """
880
600
        class stub(object):
1021
741
        :param next: A callable to advance the search.
1022
742
        """
1023
743
        for seen, recipe, included_keys, starts, stops in instructions:
1024
 
            # Adjust for recipe contract changes that don't vary for all the
1025
 
            # current tests.
1026
 
            recipe = ('search',) + recipe
1027
744
            next()
1028
745
            if starts is not None:
1029
746
                search.start_searching(starts)
1043
760
        search = graph._make_breadth_first_searcher(['head'])
1044
761
        # At the start, nothing has been seen, to its all excluded:
1045
762
        result = search.get_result()
1046
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
 
763
        self.assertEqual((set(['head']), set(['head']), 0),
1047
764
            result.get_recipe())
1048
765
        self.assertEqual(set(), result.get_keys())
1049
766
        self.assertEqual(set(), search.seen)
1075
792
        search.start_searching(['head'])
1076
793
        # head has been seen:
1077
794
        result = search.get_result()
1078
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
 
795
        self.assertEqual((set(['head']), set(['child']), 1),
1079
796
            result.get_recipe())
1080
797
        self.assertEqual(set(['head']), result.get_keys())
1081
798
        self.assertEqual(set(['head']), search.seen)
1112
829
        search = graph._make_breadth_first_searcher(['head'])
1113
830
        expected = [
1114
831
            # NULL_REVISION and ghost1 have not been returned
1115
 
            (set(['head']),
1116
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
832
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
1117
833
             ['head'], None, [NULL_REVISION, 'ghost1']),
1118
834
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1119
835
            # next iteration.
1126
842
        search = graph._make_breadth_first_searcher(['head'])
1127
843
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1128
844
 
1129
 
    def test_breadth_first_stop_searching_late(self):
1130
 
        # A client should be able to say 'stop node X' and have it excluded
1131
 
        # from the result even if X was seen in an older iteration of the
1132
 
        # search.
1133
 
        graph = self.make_graph({
1134
 
            'head':['middle'],
1135
 
            'middle':['child'],
1136
 
            'child':[NULL_REVISION],
1137
 
            NULL_REVISION:[],
1138
 
            })
1139
 
        search = graph._make_breadth_first_searcher(['head'])
1140
 
        expected = [
1141
 
            (set(['head']), (set(['head']), set(['middle']), 1),
1142
 
             ['head'], None, None),
1143
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
1144
 
             ['head', 'middle'], None, None),
1145
 
            # 'middle' came from the previous iteration, but we don't stop
1146
 
            # searching it until *after* advancing the searcher.
1147
 
            (set(['head', 'middle', 'child']),
1148
 
             (set(['head']), set(['middle', 'child']), 1),
1149
 
             ['head'], None, ['middle', 'child']),
1150
 
            ]
1151
 
        self.assertSeenAndResult(expected, search, search.next)
1152
 
        # using next_with_ghosts:
1153
 
        search = graph._make_breadth_first_searcher(['head'])
1154
 
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1155
 
 
1156
845
    def test_breadth_first_get_result_ghosts_are_excluded(self):
1157
846
        graph = self.make_graph({
1158
847
            'head':['child', 'ghost'],
1235
924
        self.assertRaises(StopIteration, search.next)
1236
925
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1237
926
        result = search.get_result()
1238
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
927
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1239
928
            result.get_recipe())
1240
929
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1241
930
        # using next_with_ghosts:
1244
933
        self.assertRaises(StopIteration, search.next)
1245
934
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1246
935
        result = search.get_result()
1247
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
 
936
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
1248
937
            result.get_recipe())
1249
938
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
1250
939
 
1251
940
 
1252
 
class TestFindUniqueAncestors(TestGraphBase):
1253
 
 
1254
 
    def assertFindUniqueAncestors(self, graph, expected, node, common):
1255
 
        actual = graph.find_unique_ancestors(node, common)
1256
 
        self.assertEqual(expected, sorted(actual))
1257
 
 
1258
 
    def test_empty_set(self):
1259
 
        graph = self.make_graph(ancestry_1)
1260
 
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1261
 
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1262
 
        self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1263
 
 
1264
 
    def test_single_node(self):
1265
 
        graph = self.make_graph(ancestry_1)
1266
 
        self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1267
 
        self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1268
 
        self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1269
 
 
1270
 
    def test_minimal_ancestry(self):
1271
 
        graph = self.make_breaking_graph(extended_history_shortcut,
1272
 
                                         [NULL_REVISION, 'a', 'b'])
1273
 
        self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1274
 
 
1275
 
        graph = self.make_breaking_graph(extended_history_shortcut,
1276
 
                                         ['b'])
1277
 
        self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1278
 
 
1279
 
        graph = self.make_breaking_graph(complex_shortcut,
1280
 
                                         ['a', 'b'])
1281
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1282
 
        self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1283
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1284
 
        self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1285
 
 
1286
 
    def test_in_ancestry(self):
1287
 
        graph = self.make_graph(ancestry_1)
1288
 
        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1289
 
        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1290
 
 
1291
 
    def test_multiple_revisions(self):
1292
 
        graph = self.make_graph(ancestry_1)
1293
 
        self.assertFindUniqueAncestors(graph,
1294
 
            ['rev4'], 'rev4', ['rev3', 'rev2b'])
1295
 
        self.assertFindUniqueAncestors(graph,
1296
 
            ['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1297
 
 
1298
 
    def test_complex_shortcut(self):
1299
 
        graph = self.make_graph(complex_shortcut)
1300
 
        self.assertFindUniqueAncestors(graph,
1301
 
            ['h', 'n'], 'n', ['m'])
1302
 
        self.assertFindUniqueAncestors(graph,
1303
 
            ['e', 'i', 'm'], 'm', ['n'])
1304
 
 
1305
 
    def test_complex_shortcut2(self):
1306
 
        graph = self.make_graph(complex_shortcut2)
1307
 
        self.assertFindUniqueAncestors(graph,
1308
 
            ['j', 'u'], 'u', ['t'])
1309
 
        self.assertFindUniqueAncestors(graph,
1310
 
            ['t'], 't', ['u'])
1311
 
 
1312
 
    def test_multiple_interesting_unique(self):
1313
 
        graph = self.make_graph(multiple_interesting_unique)
1314
 
        self.assertFindUniqueAncestors(graph,
1315
 
            ['j', 'y'], 'y', ['z'])
1316
 
        self.assertFindUniqueAncestors(graph,
1317
 
            ['p', 'z'], 'z', ['y'])
1318
 
 
1319
 
    def test_racing_shortcuts(self):
1320
 
        graph = self.make_graph(racing_shortcuts)
1321
 
        self.assertFindUniqueAncestors(graph,
1322
 
            ['p', 'q', 'z'], 'z', ['y'])
1323
 
        self.assertFindUniqueAncestors(graph,
1324
 
            ['h', 'i', 'j', 'y'], 'j', ['z'])
1325
 
 
1326
 
 
1327
 
class TestGraphFindDistanceToNull(TestGraphBase):
1328
 
    """Test an api that should be able to compute a revno"""
1329
 
 
1330
 
    def assertFindDistance(self, revno, graph, target_id, known_ids):
1331
 
        """Assert the output of Graph.find_distance_to_null()"""
1332
 
        actual = graph.find_distance_to_null(target_id, known_ids)
1333
 
        self.assertEqual(revno, actual)
1334
 
 
1335
 
    def test_nothing_known(self):
1336
 
        graph = self.make_graph(ancestry_1)
1337
 
        self.assertFindDistance(0, graph, NULL_REVISION, [])
1338
 
        self.assertFindDistance(1, graph, 'rev1', [])
1339
 
        self.assertFindDistance(2, graph, 'rev2a', [])
1340
 
        self.assertFindDistance(2, graph, 'rev2b', [])
1341
 
        self.assertFindDistance(3, graph, 'rev3', [])
1342
 
        self.assertFindDistance(4, graph, 'rev4', [])
1343
 
 
1344
 
    def test_rev_is_ghost(self):
1345
 
        graph = self.make_graph(ancestry_1)
1346
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1347
 
                              graph.find_distance_to_null, 'rev_missing', [])
1348
 
        self.assertEqual('rev_missing', e.revision_id)
1349
 
        self.assertEqual('rev_missing', e.ghost_revision_id)
1350
 
 
1351
 
    def test_ancestor_is_ghost(self):
1352
 
        graph = self.make_graph({'rev':['parent']})
1353
 
        e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1354
 
                              graph.find_distance_to_null, 'rev', [])
1355
 
        self.assertEqual('rev', e.revision_id)
1356
 
        self.assertEqual('parent', e.ghost_revision_id)
1357
 
 
1358
 
    def test_known_in_ancestry(self):
1359
 
        graph = self.make_graph(ancestry_1)
1360
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1361
 
        self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1362
 
 
1363
 
    def test_known_in_ancestry_limits(self):
1364
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1365
 
        self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1366
 
 
1367
 
    def test_target_is_ancestor(self):
1368
 
        graph = self.make_graph(ancestry_1)
1369
 
        self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1370
 
 
1371
 
    def test_target_is_ancestor_limits(self):
1372
 
        """We shouldn't search all history if we run into ourselves"""
1373
 
        graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1374
 
        self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1375
 
 
1376
 
    def test_target_parallel_to_known_limits(self):
1377
 
        # Even though the known revision isn't part of the other ancestry, they
1378
 
        # eventually converge
1379
 
        graph = self.make_breaking_graph(with_tail, ['a'])
1380
 
        self.assertFindDistance(6, graph, 'f', [('g', 6)])
1381
 
        self.assertFindDistance(7, graph, 'h', [('g', 6)])
1382
 
        self.assertFindDistance(8, graph, 'i', [('g', 6)])
1383
 
        self.assertFindDistance(6, graph, 'g', [('i', 8)])
1384
 
 
1385
 
 
1386
 
class TestFindMergeOrder(TestGraphBase):
1387
 
 
1388
 
    def assertMergeOrder(self, expected, graph, tip, base_revisions):
1389
 
        self.assertEqual(expected, graph.find_merge_order(tip, base_revisions))
1390
 
 
1391
 
    def test_parents(self):
1392
 
        graph = self.make_graph(ancestry_1)
1393
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1394
 
                                                        ['rev3', 'rev2b'])
1395
 
        self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1396
 
                                                        ['rev2b', 'rev3'])
1397
 
 
1398
 
    def test_ancestors(self):
1399
 
        graph = self.make_graph(ancestry_1)
1400
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1401
 
                                                        ['rev1', 'rev2b'])
1402
 
        self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1403
 
                                                        ['rev2b', 'rev1'])
1404
 
 
1405
 
    def test_shortcut_one_ancestor(self):
1406
 
        # When we have enough info, we can stop searching
1407
 
        graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1408
 
        # Single ancestors shortcut right away
1409
 
        self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1410
 
 
1411
 
    def test_shortcut_after_one_ancestor(self):
1412
 
        graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1413
 
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1414
 
 
1415
 
 
1416
 
class TestFindDescendants(TestGraphBase):
1417
 
 
1418
 
    def test_find_descendants_rev1_rev3(self):
1419
 
        graph = self.make_graph(ancestry_1)
1420
 
        descendants = graph.find_descendants('rev1', 'rev3')
1421
 
        self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
1422
 
 
1423
 
    def test_find_descendants_rev1_rev4(self):
1424
 
        graph = self.make_graph(ancestry_1)
1425
 
        descendants = graph.find_descendants('rev1', 'rev4')
1426
 
        self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
1427
 
                         descendants)
1428
 
 
1429
 
    def test_find_descendants_rev2a_rev4(self):
1430
 
        graph = self.make_graph(ancestry_1)
1431
 
        descendants = graph.find_descendants('rev2a', 'rev4')
1432
 
        self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
1433
 
 
1434
 
class TestFindLefthandMerger(TestGraphBase):
1435
 
 
1436
 
    def check_merger(self, result, ancestry, merged, tip):
1437
 
        graph = self.make_graph(ancestry)
1438
 
        self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
1439
 
 
1440
 
    def test_find_lefthand_merger_rev2b(self):
1441
 
        self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
1442
 
 
1443
 
    def test_find_lefthand_merger_rev2a(self):
1444
 
        self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
1445
 
 
1446
 
    def test_find_lefthand_merger_rev4(self):
1447
 
        self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
1448
 
 
1449
 
    def test_find_lefthand_merger_f(self):
1450
 
        self.check_merger('i', complex_shortcut, 'f', 'm')
1451
 
 
1452
 
    def test_find_lefthand_merger_g(self):
1453
 
        self.check_merger('i', complex_shortcut, 'g', 'm')
1454
 
 
1455
 
    def test_find_lefthand_merger_h(self):
1456
 
        self.check_merger('n', complex_shortcut, 'h', 'n')
1457
 
 
1458
 
 
1459
 
class TestGetChildMap(TestGraphBase):
1460
 
 
1461
 
    def test_get_child_map(self):
1462
 
        graph = self.make_graph(ancestry_1)
1463
 
        child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
1464
 
        self.assertEqual({'rev1': ['rev2a', 'rev2b'],
1465
 
                          'rev2a': ['rev3'],
1466
 
                          'rev2b': ['rev4'],
1467
 
                          'rev3': ['rev4']},
1468
 
                          child_map)
1469
 
 
1470
 
 
1471
941
class TestCachingParentsProvider(tests.TestCase):
1472
 
    """These tests run with:
1473
 
 
1474
 
    self.inst_pp, a recording parents provider with a graph of a->b, and b is a
1475
 
    ghost.
1476
 
    self.caching_pp, a CachingParentsProvider layered on inst_pp.
1477
 
    """
1478
942
 
1479
943
    def setUp(self):
1480
944
        super(TestCachingParentsProvider, self).setUp()
1481
 
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
 
945
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
1482
946
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1483
947
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1484
948
 
1499
963
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1500
964
        # No new calls
1501
965
        self.assertEqual(['b'], self.inst_pp.calls)
 
966
        self.assertEqual({'b':None}, self.caching_pp._cache)
1502
967
 
1503
968
    def test_get_parent_map_mixed(self):
1504
969
        """Anything that can be returned from cache, should be"""
1515
980
        # Use sorted because we don't care about the order, just that each is
1516
981
        # only present 1 time.
1517
982
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1518
 
 
1519
 
    def test_note_missing_key(self):
1520
 
        """After noting that a key is missing it is cached."""
1521
 
        self.caching_pp.note_missing_key('b')
1522
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1523
 
        self.assertEqual([], self.inst_pp.calls)
1524
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
1525
 
 
1526
 
    def test_get_cached_parent_map(self):
1527
 
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1528
 
        self.assertEqual([], self.inst_pp.calls)
1529
 
        self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1530
 
        self.assertEqual(['a'], self.inst_pp.calls)
1531
 
        self.assertEqual({'a': ('b',)},
1532
 
                         self.caching_pp.get_cached_parent_map(['a']))
1533
 
 
1534
 
 
1535
 
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1536
 
    """Test the behaviour when parents are provided that were not requested."""
1537
 
 
1538
 
    def setUp(self):
1539
 
        super(TestCachingParentsProviderExtras, self).setUp()
1540
 
        class ExtraParentsProvider(object):
1541
 
 
1542
 
            def get_parent_map(self, keys):
1543
 
                return {'rev1': [], 'rev2': ['rev1',]}
1544
 
 
1545
 
        self.inst_pp = InstrumentedParentsProvider(ExtraParentsProvider())
1546
 
        self.caching_pp = _mod_graph.CachingParentsProvider(
1547
 
            get_parent_map=self.inst_pp.get_parent_map)
1548
 
 
1549
 
    def test_uncached(self):
1550
 
        self.caching_pp.disable_cache()
1551
 
        self.assertEqual({'rev1': []},
1552
 
                         self.caching_pp.get_parent_map(['rev1']))
1553
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1554
 
        self.assertIs(None, self.caching_pp._cache)
1555
 
 
1556
 
    def test_cache_initially_empty(self):
1557
 
        self.assertEqual({}, self.caching_pp._cache)
1558
 
 
1559
 
    def test_cached(self):
1560
 
        self.assertEqual({'rev1': []},
1561
 
                         self.caching_pp.get_parent_map(['rev1']))
1562
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1563
 
        self.assertEqual({'rev1': [], 'rev2': ['rev1']},
1564
 
                         self.caching_pp._cache)
1565
 
        self.assertEqual({'rev1': []},
1566
 
                          self.caching_pp.get_parent_map(['rev1']))
1567
 
        self.assertEqual(['rev1'], self.inst_pp.calls)
1568
 
 
1569
 
    def test_disable_cache_clears_cache(self):
1570
 
        # Put something in the cache
1571
 
        self.caching_pp.get_parent_map(['rev1'])
1572
 
        self.assertEqual(2, len(self.caching_pp._cache))
1573
 
        self.caching_pp.disable_cache()
1574
 
        self.assertIs(None, self.caching_pp._cache)
1575
 
 
1576
 
    def test_enable_cache_raises(self):
1577
 
        e = self.assertRaises(AssertionError, self.caching_pp.enable_cache)
1578
 
        self.assertEqual('Cache enabled when already enabled.', str(e))
1579
 
 
1580
 
    def test_cache_misses(self):
1581
 
        self.caching_pp.get_parent_map(['rev3'])
1582
 
        self.caching_pp.get_parent_map(['rev3'])
1583
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1584
 
 
1585
 
    def test_no_cache_misses(self):
1586
 
        self.caching_pp.disable_cache()
1587
 
        self.caching_pp.enable_cache(cache_misses=False)
1588
 
        self.caching_pp.get_parent_map(['rev3'])
1589
 
        self.caching_pp.get_parent_map(['rev3'])
1590
 
        self.assertEqual(['rev3', 'rev3'], self.inst_pp.calls)
1591
 
 
1592
 
    def test_cache_extras(self):
1593
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1594
 
        self.assertEqual({'rev2': ['rev1']},
1595
 
                         self.caching_pp.get_parent_map(['rev2']))
1596
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1597
 
 
1598
 
    def test_extras_using_cached(self):
1599
 
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
1600
 
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
1601
 
        self.assertEqual({'rev2': ['rev1']},
1602
 
                         self.caching_pp.get_cached_parent_map(['rev2']))
1603
 
        self.assertEqual(['rev3'], self.inst_pp.calls)
1604
 
 
1605
 
 
1606
 
 
1607
 
class TestCollapseLinearRegions(tests.TestCase):
1608
 
 
1609
 
    def assertCollapsed(self, collapsed, original):
1610
 
        self.assertEqual(collapsed,
1611
 
                         _mod_graph.collapse_linear_regions(original))
1612
 
 
1613
 
    def test_collapse_nothing(self):
1614
 
        d = {1:[2, 3], 2:[], 3:[]}
1615
 
        self.assertCollapsed(d, d)
1616
 
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
1617
 
        self.assertCollapsed(d, d)
1618
 
 
1619
 
    def test_collapse_chain(self):
1620
 
        # Any time we have a linear chain, we should be able to collapse
1621
 
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
1622
 
        self.assertCollapsed({1:[5], 5:[]}, d)
1623
 
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
1624
 
        self.assertCollapsed({5:[1], 1:[]}, d)
1625
 
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
1626
 
        self.assertCollapsed({5:[2], 2:[]}, d)
1627
 
 
1628
 
    def test_collapse_with_multiple_children(self):
1629
 
        #    7
1630
 
        #    |
1631
 
        #    6
1632
 
        #   / \
1633
 
        #  4   5
1634
 
        #  |   |
1635
 
        #  2   3
1636
 
        #   \ /
1637
 
        #    1
1638
 
        #
1639
 
        # 4 and 5 cannot be removed because 6 has 2 children
1640
 
        # 2 and 3 cannot be removed because 1 has 2 parents
1641
 
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
1642
 
        self.assertCollapsed(d, d)
1643
 
 
1644
 
 
1645
 
class TestGraphThunkIdsToKeys(tests.TestCase):
1646
 
 
1647
 
    def test_heads(self):
1648
 
        # A
1649
 
        # |\
1650
 
        # B C
1651
 
        # |/
1652
 
        # D
1653
 
        d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1654
 
             ('B',): [('A',)], ('A',): []}
1655
 
        g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1656
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1657
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1658
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1659
 
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1660
 
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1661
 
 
1662
 
    def test_add_node(self):
1663
 
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1664
 
        g = _mod_graph.KnownGraph(d)
1665
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1666
 
        graph_thunk.add_node("D", ["A", "C"])
1667
 
        self.assertEqual(['B', 'D'],
1668
 
            sorted(graph_thunk.heads(['D', 'B', 'A'])))
1669
 
 
1670
 
    def test_merge_sort(self):
1671
 
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1672
 
        g = _mod_graph.KnownGraph(d)
1673
 
        graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1674
 
        graph_thunk.add_node("D", ["A", "C"])
1675
 
        self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1676
 
            [(n.key, n.merge_depth, n.revno, n.end_of_merge)
1677
 
                 for n in graph_thunk.merge_sort('C')])
1678
 
 
1679
 
 
1680
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1681
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1682
 
 
1683
 
    def test_get_keys(self):
1684
 
        builder = self.make_branch_builder('b')
1685
 
        builder.start_series()
1686
 
        builder.build_snapshot('rev-1', None, [
1687
 
            ('add', ('', 'root-id', 'directory', ''))])
1688
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1689
 
        builder.finish_series()
1690
 
        repo = builder.get_branch().repository
1691
 
        repo.lock_read()
1692
 
        self.addCleanup(repo.unlock)
1693
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1694
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1695
 
 
1696
 
    def test_get_keys_excludes_ghosts(self):
1697
 
        builder = self.make_branch_builder('b')
1698
 
        builder.start_series()
1699
 
        builder.build_snapshot('rev-1', None, [
1700
 
            ('add', ('', 'root-id', 'directory', ''))])
1701
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1702
 
        builder.finish_series()
1703
 
        repo = builder.get_branch().repository
1704
 
        repo.lock_read()
1705
 
        self.addCleanup(repo.unlock)
1706
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1707
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1708
 
 
1709
 
    def test_get_keys_excludes_null(self):
1710
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1711
 
        # somewhere other than the last element, which can happen in real
1712
 
        # ancestries.
1713
 
        class StubGraph(object):
1714
 
            def iter_ancestry(self, keys):
1715
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1716
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1717
 
        result_keys = result._get_keys(StubGraph())
1718
 
        # Only the non-null keys from the ancestry appear.
1719
 
        self.assertEqual(set(['foo']), set(result_keys))
1720
 
 
1721
 
 
1722
 
class TestPendingAncestryResultRefine(TestGraphBase):
1723
 
 
1724
 
    def test_refine(self):
1725
 
        # Used when pulling from a stacked repository, so test some revisions
1726
 
        # being satisfied from the stacking branch.
1727
 
        g = self.make_graph(
1728
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1729
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1730
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1731
 
        result = result.refine(set(['tip']), set(['mid']))
1732
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1733
 
        result = result.refine(set(['mid', 'tag', 'base']),
1734
 
            set([NULL_REVISION]))
1735
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1736
 
        self.assertTrue(result.is_empty())
1737
 
 
1738
 
 
1739
 
class TestSearchResultRefine(TestGraphBase):
1740
 
 
1741
 
    def test_refine(self):
1742
 
        # Used when pulling from a stacked repository, so test some revisions
1743
 
        # being satisfied from the stacking branch.
1744
 
        g = self.make_graph(
1745
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1746
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1747
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1748
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1749
 
        result = result.refine(set(['tip']), set(['mid']))
1750
 
        recipe = result.get_recipe()
1751
 
        # We should be starting from tag (original head) and mid (seen ref)
1752
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1753
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1754
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1755
 
        self.assertEqual(3, recipe[3])
1756
 
        result = result.refine(set(['mid', 'tag', 'base']),
1757
 
            set([NULL_REVISION]))
1758
 
        recipe = result.get_recipe()
1759
 
        # We should be starting from nothing (NULL was known as a cut point)
1760
 
        self.assertEqual(set([]), recipe[1])
1761
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1762
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1763
 
        # define this as not including mid, for minimal results, but it is
1764
 
        # still 'correct' to include mid, and simpler/easier.
1765
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1766
 
        self.assertEqual(0, recipe[3])
1767
 
        self.assertTrue(result.is_empty())
1768
 
 
1769
 
 
1770
 
class TestSearchResultFromParentMap(TestGraphBase):
1771
 
 
1772
 
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
1773
 
                           missing_keys=()):
1774
 
        (start, stop, count) = _mod_graph.search_result_from_parent_map(
1775
 
            parent_map, missing_keys)
1776
 
        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
1777
 
                         (sorted(start), sorted(stop), count))
1778
 
 
1779
 
    def test_no_parents(self):
1780
 
        self.assertSearchResult([], [], 0, {})
1781
 
        self.assertSearchResult([], [], 0, None)
1782
 
 
1783
 
    def test_ancestry_1(self):
1784
 
        self.assertSearchResult(['rev4'], [NULL_REVISION], len(ancestry_1),
1785
 
                                ancestry_1)
1786
 
 
1787
 
    def test_ancestry_2(self):
1788
 
        self.assertSearchResult(['rev1b', 'rev4a'], [NULL_REVISION],
1789
 
                                len(ancestry_2), ancestry_2)
1790
 
        self.assertSearchResult(['rev1b', 'rev4a'], [],
1791
 
                                len(ancestry_2)+1, ancestry_2,
1792
 
                                missing_keys=[NULL_REVISION])
1793
 
 
1794
 
    def test_partial_search(self):
1795
 
        parent_map = dict((k,extended_history_shortcut[k])
1796
 
                          for k in ['e', 'f'])
1797
 
        self.assertSearchResult(['e', 'f'], ['d', 'a'], 2,
1798
 
                                parent_map)
1799
 
        parent_map.update((k,extended_history_shortcut[k])
1800
 
                          for k in ['d', 'a'])
1801
 
        self.assertSearchResult(['e', 'f'], ['c', NULL_REVISION], 4,
1802
 
                                parent_map)
1803
 
        parent_map['c'] = extended_history_shortcut['c']
1804
 
        self.assertSearchResult(['e', 'f'], ['b'], 6,
1805
 
                                parent_map, missing_keys=[NULL_REVISION])
1806
 
        parent_map['b'] = extended_history_shortcut['b']
1807
 
        self.assertSearchResult(['e', 'f'], [], 7,
1808
 
                                parent_map, missing_keys=[NULL_REVISION])
1809
 
 
1810
 
 
1811
 
class TestLimitedSearchResultFromParentMap(TestGraphBase):
1812
 
 
1813
 
    def assertSearchResult(self, start_keys, stop_keys, key_count, parent_map,
1814
 
                           missing_keys, tip_keys, depth):
1815
 
        (start, stop, count) = _mod_graph.limited_search_result_from_parent_map(
1816
 
            parent_map, missing_keys, tip_keys, depth)
1817
 
        self.assertEqual((sorted(start_keys), sorted(stop_keys), key_count),
1818
 
                         (sorted(start), sorted(stop), count))
1819
 
 
1820
 
    def test_empty_ancestry(self):
1821
 
        self.assertSearchResult([], [], 0, {}, (), ['tip-rev-id'], 10)
1822
 
 
1823
 
    def test_ancestry_1(self):
1824
 
        self.assertSearchResult(['rev4'], ['rev1'], 4,
1825
 
                                ancestry_1, (), ['rev1'], 10)
1826
 
        self.assertSearchResult(['rev2a', 'rev2b'], ['rev1'], 2,
1827
 
                                ancestry_1, (), ['rev1'], 1)
1828
 
 
1829
 
 
1830
 
    def test_multiple_heads(self):
1831
 
        self.assertSearchResult(['e', 'f'], ['a'], 5,
1832
 
                                extended_history_shortcut, (), ['a'], 10)
1833
 
        # Note that even though we only take 1 step back, we find 'f', which
1834
 
        # means the described search will still find d and c.
1835
 
        self.assertSearchResult(['f'], ['a'], 4,
1836
 
                                extended_history_shortcut, (), ['a'], 1)
1837
 
        self.assertSearchResult(['f'], ['a'], 4,
1838
 
                                extended_history_shortcut, (), ['a'], 2)
1839
 
 
1840
 
 
1841
 
class TestStackedParentsProvider(tests.TestCase):
1842
 
 
1843
 
    def setUp(self):
1844
 
        super(TestStackedParentsProvider, self).setUp()
1845
 
        self.calls = []
1846
 
 
1847
 
    def get_shared_provider(self, info, ancestry, has_cached):
1848
 
        pp = _mod_graph.DictParentsProvider(ancestry)
1849
 
        if has_cached:
1850
 
            pp.get_cached_parent_map = pp.get_parent_map
1851
 
        return SharedInstrumentedParentsProvider(pp, self.calls, info)
1852
 
 
1853
 
    def test_stacked_parents_provider(self):
1854
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1855
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1856
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1857
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1858
 
                         stacked.get_parent_map(['rev1', 'rev2']))
1859
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1860
 
                         stacked.get_parent_map(['rev2', 'rev1']))
1861
 
        self.assertEqual({'rev2':['rev3']},
1862
 
                         stacked.get_parent_map(['rev2', 'rev2']))
1863
 
        self.assertEqual({'rev1':['rev4']},
1864
 
                         stacked.get_parent_map(['rev1', 'rev1']))
1865
 
 
1866
 
    def test_stacked_parents_provider_overlapping(self):
1867
 
        # rev2 is availible in both providers.
1868
 
        # 1
1869
 
        # |
1870
 
        # 2
1871
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1872
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1873
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1874
 
        self.assertEqual({'rev2': ['rev1']},
1875
 
                         stacked.get_parent_map(['rev2']))
1876
 
 
1877
 
    def test_handles_no_get_cached_parent_map(self):
1878
 
        # this shows that we both handle when a provider doesn't implement
1879
 
        # get_cached_parent_map
1880
 
        pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1881
 
                                       has_cached=False)
1882
 
        pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1883
 
                                       has_cached=True)
1884
 
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1885
 
        self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1886
 
        # No call on 'pp1' because it doesn't provide get_cached_parent_map
1887
 
        self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1888
 
 
1889
 
    def test_query_order(self):
1890
 
        # We should call get_cached_parent_map on all providers before we call
1891
 
        # get_parent_map. Further, we should track what entries we have found,
1892
 
        # and not re-try them.
1893
 
        pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1894
 
        pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1895
 
        pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1896
 
        stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1897
 
        self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1898
 
                         stacked.get_parent_map(['a', 'b', 'c', 'd']))
1899
 
        self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1900
 
                          # No call to pp2, because it doesn't have cached
1901
 
                          ('pp3', 'cached', ['b', 'c', 'd']),
1902
 
                          ('pp1', ['c', 'd']),
1903
 
                          ('pp2', ['c', 'd']),
1904
 
                          ('pp3', ['d']),
1905
 
                         ], self.calls)