290
409
self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
291
410
graph.find_difference('rev2a', 'rev3b'))
412
def test_graph_difference_extended_history(self):
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'))
417
self.assertEqual((set(['e']), set(['f'])),
418
graph.find_difference('e', 'f'))
419
self.assertEqual((set(['f']), set(['e'])),
420
graph.find_difference('f', 'e'))
422
def test_graph_difference_double_shortcut(self):
423
graph = self.make_graph(double_shortcut)
424
self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
425
graph.find_difference('f', 'g'))
427
def test_graph_difference_complex_shortcut(self):
428
graph = self.make_graph(complex_shortcut)
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'])),
433
graph.find_difference('m', 'n'))
435
def test_graph_difference_shortcut_extra_root(self):
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'))
440
self.assertEqual((set(['e']), set(['f', 'g'])),
441
graph.find_difference('e', 'f'))
293
443
def test_stacked_parents_provider(self):
295
444
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
296
445
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
297
446
stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
298
self.assertEqual([['rev4',], ['rev3']],
299
stacked.get_parents(['rev1', 'rev2']))
300
self.assertEqual([['rev3',], ['rev4']],
301
stacked.get_parents(['rev2', 'rev1']))
302
self.assertEqual([['rev3',], ['rev3']],
303
stacked.get_parents(['rev2', 'rev2']))
304
self.assertEqual([['rev4',], ['rev4']],
305
stacked.get_parents(['rev1', 'rev1']))
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']))
307
456
def test_iter_topo_order(self):
308
457
graph = self.make_graph(ancestry_1)
497
646
self.assertEqual(set(['h1', 'h2']),
498
647
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
649
def test_breadth_first_search_start_ghosts(self):
650
graph = self.make_graph({})
651
# with_ghosts reports the ghosts
652
search = graph._make_breadth_first_searcher(['a-ghost'])
653
self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
654
self.assertRaises(StopIteration, search.next_with_ghosts)
656
search = graph._make_breadth_first_searcher(['a-ghost'])
657
self.assertEqual(set(['a-ghost']), search.next())
658
self.assertRaises(StopIteration, search.next)
660
def test_breadth_first_search_deep_ghosts(self):
661
graph = self.make_graph({
663
'present':['child', 'ghost'],
666
# with_ghosts reports the ghosts
667
search = graph._make_breadth_first_searcher(['head'])
668
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
669
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
670
self.assertEqual((set(['child']), set(['ghost'])),
671
search.next_with_ghosts())
672
self.assertRaises(StopIteration, search.next_with_ghosts)
674
search = graph._make_breadth_first_searcher(['head'])
675
self.assertEqual(set(['head']), search.next())
676
self.assertEqual(set(['present']), search.next())
677
self.assertEqual(set(['child', 'ghost']),
679
self.assertRaises(StopIteration, search.next)
681
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
682
# To make the API robust, we allow calling both next() and
683
# next_with_ghosts() on the same searcher.
684
graph = self.make_graph({
686
'present':['child', 'ghost'],
689
# start with next_with_ghosts
690
search = graph._make_breadth_first_searcher(['head'])
691
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
692
self.assertEqual(set(['present']), search.next())
693
self.assertEqual((set(['child']), set(['ghost'])),
694
search.next_with_ghosts())
695
self.assertRaises(StopIteration, search.next)
697
search = graph._make_breadth_first_searcher(['head'])
698
self.assertEqual(set(['head']), search.next())
699
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
700
self.assertEqual(set(['child', 'ghost']),
702
self.assertRaises(StopIteration, search.next_with_ghosts)
704
def test_breadth_first_change_search(self):
705
# Changing the search should work with both next and next_with_ghosts.
706
graph = self.make_graph({
708
'present':['stopped'],
712
search = graph._make_breadth_first_searcher(['head'])
713
self.assertEqual((set(['head']), set()), search.next_with_ghosts())
714
self.assertEqual((set(['present']), set()), search.next_with_ghosts())
715
self.assertEqual(set(['present']),
716
search.stop_searching_any(['present']))
717
self.assertEqual((set(['other']), set(['other_ghost'])),
718
search.start_searching(['other', 'other_ghost']))
719
self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
720
self.assertRaises(StopIteration, search.next_with_ghosts)
722
search = graph._make_breadth_first_searcher(['head'])
723
self.assertEqual(set(['head']), search.next())
724
self.assertEqual(set(['present']), search.next())
725
self.assertEqual(set(['present']),
726
search.stop_searching_any(['present']))
727
search.start_searching(['other', 'other_ghost'])
728
self.assertEqual(set(['other_2']), search.next())
729
self.assertRaises(StopIteration, search.next)
731
def assertSeenAndResult(self, instructions, search, next):
732
"""Check the results of .seen and get_result() for a seach.
734
:param instructions: A list of tuples:
735
(seen, recipe, included_keys, starts, stops).
736
seen, recipe and included_keys are results to check on the search
737
and the searches get_result(). starts and stops are parameters to
738
pass to start_searching and stop_searching_any during each
739
iteration, if they are not None.
740
:param search: The search to use.
741
:param next: A callable to advance the search.
743
for seen, recipe, included_keys, starts, stops in instructions:
745
if starts is not None:
746
search.start_searching(starts)
747
if stops is not None:
748
search.stop_searching_any(stops)
749
result = search.get_result()
750
self.assertEqual(recipe, result.get_recipe())
751
self.assertEqual(set(included_keys), result.get_keys())
752
self.assertEqual(seen, search.seen)
754
def test_breadth_first_get_result_excludes_current_pending(self):
755
graph = self.make_graph({
757
'child':[NULL_REVISION],
760
search = graph._make_breadth_first_searcher(['head'])
761
# At the start, nothing has been seen, to its all excluded:
762
result = search.get_result()
763
self.assertEqual((set(['head']), set(['head']), 0),
765
self.assertEqual(set(), result.get_keys())
766
self.assertEqual(set(), search.seen)
769
(set(['head']), (set(['head']), set(['child']), 1),
770
['head'], None, None),
771
(set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
772
['head', 'child'], None, None),
773
(set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
774
['head', 'child', NULL_REVISION], None, None),
776
self.assertSeenAndResult(expected, search, search.next)
777
# using next_with_ghosts:
778
search = graph._make_breadth_first_searcher(['head'])
779
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
781
def test_breadth_first_get_result_starts_stops(self):
782
graph = self.make_graph({
784
'child':[NULL_REVISION],
785
'otherhead':['otherchild'],
786
'otherchild':['excluded'],
787
'excluded':[NULL_REVISION],
790
search = graph._make_breadth_first_searcher([])
791
# Starting with nothing and adding a search works:
792
search.start_searching(['head'])
793
# head has been seen:
794
result = search.get_result()
795
self.assertEqual((set(['head']), set(['child']), 1),
797
self.assertEqual(set(['head']), result.get_keys())
798
self.assertEqual(set(['head']), search.seen)
801
# stop at child, and start a new search at otherhead:
802
# - otherhead counts as seen immediately when start_searching is
804
(set(['head', 'child', 'otherhead']),
805
(set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
806
['head', 'otherhead'], ['otherhead'], ['child']),
807
(set(['head', 'child', 'otherhead', 'otherchild']),
808
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
809
['head', 'otherhead', 'otherchild'], None, None),
810
# stop searching excluded now
811
(set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
812
(set(['head', 'otherhead']), set(['child', 'excluded']), 3),
813
['head', 'otherhead', 'otherchild'], None, ['excluded']),
815
self.assertSeenAndResult(expected, search, search.next)
816
# using next_with_ghosts:
817
search = graph._make_breadth_first_searcher([])
818
search.start_searching(['head'])
819
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
821
def test_breadth_first_stop_searching_not_queried(self):
822
# A client should be able to say 'stop node X' even if X has not been
823
# returned to the client.
824
graph = self.make_graph({
825
'head':['child', 'ghost1'],
826
'child':[NULL_REVISION],
829
search = graph._make_breadth_first_searcher(['head'])
831
# NULL_REVISION and ghost1 have not been returned
832
(set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
833
['head'], None, [NULL_REVISION, 'ghost1']),
834
# ghost1 has been returned, NULL_REVISION is to be returned in the
836
(set(['head', 'child', 'ghost1']),
837
(set(['head']), set(['ghost1', NULL_REVISION]), 2),
838
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
840
self.assertSeenAndResult(expected, search, search.next)
841
# using next_with_ghosts:
842
search = graph._make_breadth_first_searcher(['head'])
843
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
845
def test_breadth_first_get_result_ghosts_are_excluded(self):
846
graph = self.make_graph({
847
'head':['child', 'ghost'],
848
'child':[NULL_REVISION],
851
search = graph._make_breadth_first_searcher(['head'])
855
(set(['head']), set(['ghost', 'child']), 1),
856
['head'], None, None),
857
(set(['head', 'child', 'ghost']),
858
(set(['head']), set([NULL_REVISION, 'ghost']), 2),
859
['head', 'child'], None, None),
861
self.assertSeenAndResult(expected, search, search.next)
862
# using next_with_ghosts:
863
search = graph._make_breadth_first_searcher(['head'])
864
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
866
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
867
graph = self.make_graph({
869
'child':[NULL_REVISION],
872
search = graph._make_breadth_first_searcher(['head'])
875
(set(['head', 'ghost']),
876
(set(['head', 'ghost']), set(['child', 'ghost']), 1),
877
['head'], ['ghost'], None),
878
(set(['head', 'child', 'ghost']),
879
(set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
880
['head', 'child'], None, None),
882
self.assertSeenAndResult(expected, search, search.next)
883
# using next_with_ghosts:
884
search = graph._make_breadth_first_searcher(['head'])
885
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
887
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
888
graph = self.make_graph({
889
'head':[NULL_REVISION],
892
search = graph._make_breadth_first_searcher(['head'])
896
(set(['head']), set([NULL_REVISION]), 1),
897
['head'], None, None),
898
(set(['head', NULL_REVISION]),
899
(set(['head']), set([]), 2),
900
['head', NULL_REVISION], None, None),
902
self.assertSeenAndResult(expected, search, search.next)
903
# using next_with_ghosts:
904
search = graph._make_breadth_first_searcher(['head'])
905
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
907
def test_breadth_first_search_get_result_after_StopIteration(self):
908
# StopIteration should not invalid anything..
909
graph = self.make_graph({
910
'head':[NULL_REVISION],
913
search = graph._make_breadth_first_searcher(['head'])
917
(set(['head']), set([NULL_REVISION]), 1),
918
['head'], None, None),
919
(set(['head', 'ghost', NULL_REVISION]),
920
(set(['head', 'ghost']), set(['ghost']), 2),
921
['head', NULL_REVISION], ['ghost'], None),
923
self.assertSeenAndResult(expected, search, search.next)
924
self.assertRaises(StopIteration, search.next)
925
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
926
result = search.get_result()
927
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
929
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
930
# using next_with_ghosts:
931
search = graph._make_breadth_first_searcher(['head'])
932
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
933
self.assertRaises(StopIteration, search.next)
934
self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
935
result = search.get_result()
936
self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
938
self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
941
class TestCachingParentsProvider(tests.TestCase):
944
super(TestCachingParentsProvider, self).setUp()
945
dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
946
self.inst_pp = InstrumentedParentsProvider(dict_pp)
947
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
949
def test_get_parent_map(self):
950
"""Requesting the same revision should be returned from cache"""
951
self.assertEqual({}, self.caching_pp._cache)
952
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
953
self.assertEqual(['a'], self.inst_pp.calls)
954
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
955
# No new call, as it should have been returned from the cache
956
self.assertEqual(['a'], self.inst_pp.calls)
957
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
959
def test_get_parent_map_not_present(self):
960
"""The cache should also track when a revision doesn't exist"""
961
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
962
self.assertEqual(['b'], self.inst_pp.calls)
963
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
965
self.assertEqual(['b'], self.inst_pp.calls)
966
self.assertEqual({'b':None}, self.caching_pp._cache)
968
def test_get_parent_map_mixed(self):
969
"""Anything that can be returned from cache, should be"""
970
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
971
self.assertEqual(['b'], self.inst_pp.calls)
972
self.assertEqual({'a':('b',)},
973
self.caching_pp.get_parent_map(['a', 'b']))
974
self.assertEqual(['b', 'a'], self.inst_pp.calls)
976
def test_get_parent_map_repeated(self):
977
"""Asking for the same parent 2x will only forward 1 request."""
978
self.assertEqual({'a':('b',)},
979
self.caching_pp.get_parent_map(['b', 'a', 'b']))
980
# Use sorted because we don't care about the order, just that each is
981
# only present 1 time.
982
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
added
removed
bzrlib/tests/test_graph.py
