/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Andrew Bennetts
  • Date: 2008-03-27 06:10:18 UTC
  • mfrom: (3309 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3320.
  • Revision ID: andrew.bennetts@canonical.com-20080327061018-dxztpxyv6yoeg3am
Merge from bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
238
238
            'f':[NULL_REVISION]}
239
239
 
240
240
 
 
241
# A graph that contains a ghost
 
242
#  NULL_REVISION
 
243
#       |
 
244
#       f
 
245
#       |
 
246
#       e   g
 
247
#      / \ /
 
248
#     b   d
 
249
#     | \ |
 
250
#     a   c
 
251
 
 
252
with_ghost = {'a': ['b'], 'c': ['b', 'd'], 'b':['e'], 'd':['e', 'g'],
 
253
              'e': ['f'], 'f':[NULL_REVISION], NULL_REVISION:()}
 
254
 
 
255
 
 
256
 
241
257
class InstrumentedParentsProvider(object):
242
258
 
243
259
    def __init__(self, parents_provider):
252
268
class TestGraph(TestCaseWithMemoryTransport):
253
269
 
254
270
    def make_graph(self, ancestors):
255
 
        # XXX: This seems valid, is there a reason to actually create a
256
 
        # repository and put things in it?
257
271
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
258
 
        tree = self.prepare_memory_tree('.')
259
 
        self.build_ancestry(tree, ancestors)
260
 
        self.addCleanup(tree.unlock)
261
 
        return tree.branch.repository.get_graph()
262
272
 
263
273
    def prepare_memory_tree(self, location):
264
274
        tree = self.make_branch_and_memory_tree(location)
495
505
        self.assertFalse(graph.is_ancestor('a', 'c'))
496
506
        self.assertTrue('null:' not in instrumented_provider.calls)
497
507
 
 
508
    def test_iter_ancestry(self):
 
509
        nodes = boundary.copy()
 
510
        nodes[NULL_REVISION] = ()
 
511
        graph = self.make_graph(nodes)
 
512
        expected = nodes.copy()
 
513
        expected.pop('a') # 'a' is not in the ancestry of 'c', all the
 
514
                          # other nodes are
 
515
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
 
516
        self.assertEqual(nodes, dict(graph.iter_ancestry(['a', 'c'])))
 
517
 
 
518
    def test_iter_ancestry_with_ghost(self):
 
519
        graph = self.make_graph(with_ghost)
 
520
        expected = with_ghost.copy()
 
521
        # 'a' is not in the ancestry of 'c', and 'g' is a ghost
 
522
        expected['g'] = None
 
523
        self.assertEqual(expected, dict(graph.iter_ancestry(['a', 'c'])))
 
524
        expected.pop('a') 
 
525
        self.assertEqual(expected, dict(graph.iter_ancestry(['c'])))
 
526
 
498
527
    def test_filter_candidate_lca(self):
499
528
        """Test filter_candidate_lca for a corner case
500
529
 
652
681
        self.assertEqual(set(['h1', 'h2']),
653
682
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
654
683
 
 
684
    def test_breadth_first_search_start_ghosts(self):
 
685
        graph = self.make_graph({})
 
686
        # with_ghosts reports the ghosts
 
687
        search = graph._make_breadth_first_searcher(['a-ghost'])
 
688
        self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
 
689
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
690
        # next includes them
 
691
        search = graph._make_breadth_first_searcher(['a-ghost'])
 
692
        self.assertEqual(set(['a-ghost']), search.next())
 
693
        self.assertRaises(StopIteration, search.next)
 
694
 
 
695
    def test_breadth_first_search_deep_ghosts(self):
 
696
        graph = self.make_graph({
 
697
            'head':['present'],
 
698
            'present':['child', 'ghost'],
 
699
            'child':[],
 
700
            })
 
701
        # with_ghosts reports the ghosts
 
702
        search = graph._make_breadth_first_searcher(['head'])
 
703
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
 
704
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
 
705
        self.assertEqual((set(['child']), set(['ghost'])),
 
706
            search.next_with_ghosts())
 
707
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
708
        # next includes them
 
709
        search = graph._make_breadth_first_searcher(['head'])
 
710
        self.assertEqual(set(['head']), search.next())
 
711
        self.assertEqual(set(['present']), search.next())
 
712
        self.assertEqual(set(['child', 'ghost']),
 
713
            search.next())
 
714
        self.assertRaises(StopIteration, search.next)
 
715
 
 
716
    def test_breadth_first_search_change_next_to_next_with_ghosts(self):
 
717
        # To make the API robust, we allow calling both next() and
 
718
        # next_with_ghosts() on the same searcher.
 
719
        graph = self.make_graph({
 
720
            'head':['present'],
 
721
            'present':['child', 'ghost'],
 
722
            'child':[],
 
723
            })
 
724
        # start with next_with_ghosts
 
725
        search = graph._make_breadth_first_searcher(['head'])
 
726
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
 
727
        self.assertEqual(set(['present']), search.next())
 
728
        self.assertEqual((set(['child']), set(['ghost'])),
 
729
            search.next_with_ghosts())
 
730
        self.assertRaises(StopIteration, search.next)
 
731
        # start with next
 
732
        search = graph._make_breadth_first_searcher(['head'])
 
733
        self.assertEqual(set(['head']), search.next())
 
734
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
 
735
        self.assertEqual(set(['child', 'ghost']),
 
736
            search.next())
 
737
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
738
 
 
739
    def test_breadth_first_change_search(self):
 
740
        # Changing the search should work with both next and next_with_ghosts.
 
741
        graph = self.make_graph({
 
742
            'head':['present'],
 
743
            'present':['stopped'],
 
744
            'other':['other_2'],
 
745
            'other_2':[],
 
746
            })
 
747
        search = graph._make_breadth_first_searcher(['head'])
 
748
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
 
749
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
 
750
        self.assertEqual(set(['present']),
 
751
            search.stop_searching_any(['present']))
 
752
        self.assertEqual((set(['other']), set(['other_ghost'])),
 
753
            search.start_searching(['other', 'other_ghost']))
 
754
        self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
 
755
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
756
        # next includes them
 
757
        search = graph._make_breadth_first_searcher(['head'])
 
758
        self.assertEqual(set(['head']), search.next())
 
759
        self.assertEqual(set(['present']), search.next())
 
760
        self.assertEqual(set(['present']),
 
761
            search.stop_searching_any(['present']))
 
762
        search.start_searching(['other', 'other_ghost'])
 
763
        self.assertEqual(set(['other_2']), search.next())
 
764
        self.assertRaises(StopIteration, search.next)
 
765
 
 
766
    def assertSeenAndResult(self, instructions, search, next):
 
767
        """Check the results of .seen and get_result() for a seach.
 
768
 
 
769
        :param instructions: A list of tuples:
 
770
            (seen, recipe, included_keys, starts, stops).
 
771
            seen, recipe and included_keys are results to check on the search
 
772
            and the searches get_result(). starts and stops are parameters to
 
773
            pass to start_searching and stop_searching_any during each
 
774
            iteration, if they are not None.
 
775
        :param search: The search to use.
 
776
        :param next: A callable to advance the search.
 
777
        """
 
778
        for seen, recipe, included_keys, starts, stops in instructions:
 
779
            next()
 
780
            if starts is not None:
 
781
                search.start_searching(starts)
 
782
            if stops is not None:
 
783
                search.stop_searching_any(stops)
 
784
            result = search.get_result()
 
785
            self.assertEqual(recipe, result.get_recipe())
 
786
            self.assertEqual(set(included_keys), result.get_keys())
 
787
            self.assertEqual(seen, search.seen)
 
788
 
 
789
    def test_breadth_first_get_result_excludes_current_pending(self):
 
790
        graph = self.make_graph({
 
791
            'head':['child'],
 
792
            'child':[NULL_REVISION],
 
793
            NULL_REVISION:[],
 
794
            })
 
795
        search = graph._make_breadth_first_searcher(['head'])
 
796
        # At the start, nothing has been seen, to its all excluded:
 
797
        result = search.get_result()
 
798
        self.assertEqual((set(['head']), set(['head']), 0),
 
799
            result.get_recipe())
 
800
        self.assertEqual(set(), result.get_keys())
 
801
        self.assertEqual(set(), search.seen)
 
802
        # using next:
 
803
        expected = [
 
804
            (set(['head']), (set(['head']), set(['child']), 1),
 
805
             ['head'], None, None),
 
806
            (set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
 
807
             ['head', 'child'], None, None),
 
808
            (set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
 
809
             ['head', 'child', NULL_REVISION], None, None),
 
810
            ]
 
811
        self.assertSeenAndResult(expected, search, search.next)
 
812
        # using next_with_ghosts:
 
813
        search = graph._make_breadth_first_searcher(['head'])
 
814
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
815
 
 
816
    def test_breadth_first_get_result_starts_stops(self):
 
817
        graph = self.make_graph({
 
818
            'head':['child'],
 
819
            'child':[NULL_REVISION],
 
820
            'otherhead':['otherchild'],
 
821
            'otherchild':['excluded'],
 
822
            'excluded':[NULL_REVISION],
 
823
            NULL_REVISION:[]
 
824
            })
 
825
        search = graph._make_breadth_first_searcher([])
 
826
        # Starting with nothing and adding a search works:
 
827
        search.start_searching(['head'])
 
828
        # head has been seen:
 
829
        result = search.get_result()
 
830
        self.assertEqual((set(['head']), set(['child']), 1),
 
831
            result.get_recipe())
 
832
        self.assertEqual(set(['head']), result.get_keys())
 
833
        self.assertEqual(set(['head']), search.seen)
 
834
        # using next:
 
835
        expected = [
 
836
            # stop at child, and start a new search at otherhead:
 
837
            # - otherhead counts as seen immediately when start_searching is
 
838
            # called.
 
839
            (set(['head', 'child', 'otherhead']),
 
840
             (set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
 
841
             ['head', 'otherhead'], ['otherhead'], ['child']),
 
842
            (set(['head', 'child', 'otherhead', 'otherchild']),
 
843
             (set(['head', 'otherhead']), set(['child', 'excluded']), 3),
 
844
             ['head', 'otherhead', 'otherchild'], None, None),
 
845
            # stop searching excluded now
 
846
            (set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
 
847
             (set(['head', 'otherhead']), set(['child', 'excluded']), 3),
 
848
             ['head', 'otherhead', 'otherchild'], None, ['excluded']),
 
849
            ]
 
850
        self.assertSeenAndResult(expected, search, search.next)
 
851
        # using next_with_ghosts:
 
852
        search = graph._make_breadth_first_searcher([])
 
853
        search.start_searching(['head'])
 
854
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
855
 
 
856
    def test_breadth_first_stop_searching_not_queried(self):
 
857
        # A client should be able to say 'stop node X' even if X has not been
 
858
        # returned to the client.
 
859
        graph = self.make_graph({
 
860
            'head':['child', 'ghost1'],
 
861
            'child':[NULL_REVISION],
 
862
            NULL_REVISION:[],
 
863
            })
 
864
        search = graph._make_breadth_first_searcher(['head'])
 
865
        expected = [
 
866
            # NULL_REVISION and ghost1 have not been returned
 
867
            (set(['head']), (set(['head']), set(['child', 'ghost1']), 1),
 
868
             ['head'], None, [NULL_REVISION, 'ghost1']),
 
869
            # ghost1 has been returned, NULL_REVISION is to be returned in the
 
870
            # next iteration.
 
871
            (set(['head', 'child', 'ghost1']),
 
872
             (set(['head']), set(['ghost1', NULL_REVISION]), 2),
 
873
             ['head', 'child'], None, [NULL_REVISION, 'ghost1']),
 
874
            ]
 
875
        self.assertSeenAndResult(expected, search, search.next)
 
876
        # using next_with_ghosts:
 
877
        search = graph._make_breadth_first_searcher(['head'])
 
878
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
879
 
 
880
    def test_breadth_first_get_result_ghosts_are_excluded(self):
 
881
        graph = self.make_graph({
 
882
            'head':['child', 'ghost'],
 
883
            'child':[NULL_REVISION],
 
884
            NULL_REVISION:[],
 
885
            })
 
886
        search = graph._make_breadth_first_searcher(['head'])
 
887
        # using next:
 
888
        expected = [
 
889
            (set(['head']),
 
890
             (set(['head']), set(['ghost', 'child']), 1),
 
891
             ['head'], None, None),
 
892
            (set(['head', 'child', 'ghost']),
 
893
             (set(['head']), set([NULL_REVISION, 'ghost']), 2),
 
894
             ['head', 'child'], None, None),
 
895
            ]
 
896
        self.assertSeenAndResult(expected, search, search.next)
 
897
        # using next_with_ghosts:
 
898
        search = graph._make_breadth_first_searcher(['head'])
 
899
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
900
 
 
901
    def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
 
902
        graph = self.make_graph({
 
903
            'head':['child'],
 
904
            'child':[NULL_REVISION],
 
905
            NULL_REVISION:[],
 
906
            })
 
907
        search = graph._make_breadth_first_searcher(['head'])
 
908
        # using next:
 
909
        expected = [
 
910
            (set(['head', 'ghost']),
 
911
             (set(['head', 'ghost']), set(['child', 'ghost']), 1),
 
912
             ['head'], ['ghost'], None),
 
913
            (set(['head', 'child', 'ghost']),
 
914
             (set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
 
915
             ['head', 'child'], None, None),
 
916
            ]
 
917
        self.assertSeenAndResult(expected, search, search.next)
 
918
        # using next_with_ghosts:
 
919
        search = graph._make_breadth_first_searcher(['head'])
 
920
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
921
 
 
922
    def test_breadth_first_revision_count_includes_NULL_REVISION(self):
 
923
        graph = self.make_graph({
 
924
            'head':[NULL_REVISION],
 
925
            NULL_REVISION:[],
 
926
            })
 
927
        search = graph._make_breadth_first_searcher(['head'])
 
928
        # using next:
 
929
        expected = [
 
930
            (set(['head']),
 
931
             (set(['head']), set([NULL_REVISION]), 1),
 
932
             ['head'], None, None),
 
933
            (set(['head', NULL_REVISION]),
 
934
             (set(['head']), set([]), 2),
 
935
             ['head', NULL_REVISION], None, None),
 
936
            ]
 
937
        self.assertSeenAndResult(expected, search, search.next)
 
938
        # using next_with_ghosts:
 
939
        search = graph._make_breadth_first_searcher(['head'])
 
940
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
941
 
 
942
    def test_breadth_first_search_get_result_after_StopIteration(self):
 
943
        # StopIteration should not invalid anything..
 
944
        graph = self.make_graph({
 
945
            'head':[NULL_REVISION],
 
946
            NULL_REVISION:[],
 
947
            })
 
948
        search = graph._make_breadth_first_searcher(['head'])
 
949
        # using next:
 
950
        expected = [
 
951
            (set(['head']),
 
952
             (set(['head']), set([NULL_REVISION]), 1),
 
953
             ['head'], None, None),
 
954
            (set(['head', 'ghost', NULL_REVISION]),
 
955
             (set(['head', 'ghost']), set(['ghost']), 2),
 
956
             ['head', NULL_REVISION], ['ghost'], None),
 
957
            ]
 
958
        self.assertSeenAndResult(expected, search, search.next)
 
959
        self.assertRaises(StopIteration, search.next)
 
960
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
 
961
        result = search.get_result()
 
962
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
963
            result.get_recipe())
 
964
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
965
        # using next_with_ghosts:
 
966
        search = graph._make_breadth_first_searcher(['head'])
 
967
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
 
968
        self.assertRaises(StopIteration, search.next)
 
969
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
 
970
        result = search.get_result()
 
971
        self.assertEqual((set(['ghost', 'head']), set(['ghost']), 2),
 
972
            result.get_recipe())
 
973
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
974
 
655
975
 
656
976
class TestCachingParentsProvider(tests.TestCase):
657
977