← Back to branch summary

~ubuntu-branches/ubuntu/hardy/bzr/hardy-proposed

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: Bazaar Package Importer
  • Author(s): Adeodato Simó
  • Date: 2008-02-14 13:32:37 UTC
  • mfrom: (1.1.37 upstream)
  • Revision ID: james.westby@ubuntu.com-20080214133237-1dcmf4z41a6hg1i7
Tags: 1.2~rc1-1
First release candidate of the upcoming 1.2 release.

(NB: 1.1 final was never packaged because there were no code changes
between 1.1~rc1 and 1.1 itself.)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
244
244
        self.calls = []
245
245
        self._real_parents_provider = parents_provider
246
246
 
247
 
    def get_parents(self, nodes):
248
 
        self.calls.extend(nodes)
249
 
        return self._real_parents_provider.get_parents(nodes)
250
 
 
251
247
    def get_parent_map(self, nodes):
252
248
        self.calls.extend(nodes)
253
249
        return self._real_parents_provider.get_parent_map(nodes)
256
252
class TestGraph(TestCaseWithMemoryTransport):
257
253
 
258
254
    def make_graph(self, ancestors):
259
 
        # XXX: This seems valid, is there a reason to actually create a
260
 
        # repository and put things in it?
261
255
        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
262
 
        tree = self.prepare_memory_tree('.')
263
 
        self.build_ancestry(tree, ancestors)
264
 
        self.addCleanup(tree.unlock)
265
 
        return tree.branch.repository.get_graph()
266
256
 
267
257
    def prepare_memory_tree(self, location):
268
258
        tree = self.make_branch_and_memory_tree(location)
450
440
        self.assertEqual((set(['e']), set(['f', 'g'])),
451
441
                         graph.find_difference('e', 'f'))
452
442
 
453
 
    def test_stacked_parents_provider_get_parents(self):
454
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
455
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
456
 
        stacked = _mod_graph._StackedParentsProvider([parents1, parents2])
457
 
        self.assertEqual([['rev4',], ['rev3']],
458
 
             self.applyDeprecated(symbol_versioning.one_one,
459
 
                                  stacked.get_parents, ['rev1', 'rev2']))
460
 
        self.assertEqual([['rev3',], ['rev4']],
461
 
             self.applyDeprecated(symbol_versioning.one_one,
462
 
                                  stacked.get_parents, ['rev2', 'rev1']))
463
 
        self.assertEqual([['rev3',], ['rev3']],
464
 
             self.applyDeprecated(symbol_versioning.one_one,
465
 
                         stacked.get_parents, ['rev2', 'rev2']))
466
 
        self.assertEqual([['rev4',], ['rev4']],
467
 
             self.applyDeprecated(symbol_versioning.one_one,
468
 
                         stacked.get_parents, ['rev1', 'rev1']))
469
 
 
470
443
    def test_stacked_parents_provider(self):
471
444
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
472
445
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
626
599
        """
627
600
        class stub(object):
628
601
            pass
629
 
        def get_parents(keys):
630
 
            result = []
631
 
            for key in keys:
632
 
                if key == 'deeper':
633
 
                    self.fail('key deeper was accessed')
634
 
                result.append(graph_dict[key])
635
 
            return result
636
602
        def get_parent_map(keys):
637
603
            result = {}
638
604
            for key in keys:
641
607
                result[key] = graph_dict[key]
642
608
            return result
643
609
        an_obj = stub()
644
 
        an_obj.get_parents = get_parents
645
610
        an_obj.get_parent_map = get_parent_map
646
611
        graph = _mod_graph.Graph(an_obj)
647
612
        return graph.heads(search)
681
646
        self.assertEqual(set(['h1', 'h2']),
682
647
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
683
648
 
 
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)
 
655
        # next includes them
 
656
        search = graph._make_breadth_first_searcher(['a-ghost'])
 
657
        self.assertEqual(set(['a-ghost']), search.next())
 
658
        self.assertRaises(StopIteration, search.next)
 
659
 
 
660
    def test_breadth_first_search_deep_ghosts(self):
 
661
        graph = self.make_graph({
 
662
            'head':['present'],
 
663
            'present':['child', 'ghost'],
 
664
            'child':[],
 
665
            })
 
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)
 
673
        # next includes them
 
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']),
 
678
            search.next())
 
679
        self.assertRaises(StopIteration, search.next)
 
680
 
 
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({
 
685
            'head':['present'],
 
686
            'present':['child', 'ghost'],
 
687
            'child':[],
 
688
            })
 
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)
 
696
        # start with 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']),
 
701
            search.next())
 
702
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
703
 
 
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({
 
707
            'head':['present'],
 
708
            'present':['stopped'],
 
709
            'other':['other_2'],
 
710
            'other_2':[],
 
711
            })
 
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)
 
721
        # next includes them
 
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)
 
730
 
 
731
    def assertSeenAndResult(self, instructions, search, next):
 
732
        """Check the results of .seen and get_result() for a seach.
 
733
 
 
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.
 
742
        """
 
743
        for seen, recipe, included_keys, starts, stops in instructions:
 
744
            next()
 
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)
 
753
 
 
754
    def test_breadth_first_get_result_excludes_current_pending(self):
 
755
        graph = self.make_graph({
 
756
            'head':['child'],
 
757
            'child':[NULL_REVISION],
 
758
            NULL_REVISION:[],
 
759
            })
 
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),
 
764
            result.get_recipe())
 
765
        self.assertEqual(set(), result.get_keys())
 
766
        self.assertEqual(set(), search.seen)
 
767
        # using next:
 
768
        expected = [
 
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),
 
775
            ]
 
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)
 
780
 
 
781
    def test_breadth_first_get_result_starts_stops(self):
 
782
        graph = self.make_graph({
 
783
            'head':['child'],
 
784
            'child':[NULL_REVISION],
 
785
            'otherhead':['otherchild'],
 
786
            'otherchild':['excluded'],
 
787
            'excluded':[NULL_REVISION],
 
788
            NULL_REVISION:[]
 
789
            })
 
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),
 
796
            result.get_recipe())
 
797
        self.assertEqual(set(['head']), result.get_keys())
 
798
        self.assertEqual(set(['head']), search.seen)
 
799
        # using next:
 
800
        expected = [
 
801
            # stop at child, and start a new search at otherhead:
 
802
            # - otherhead counts as seen immediately when start_searching is
 
803
            # called.
 
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']),
 
814
            ]
 
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)
 
820
 
 
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],
 
827
            NULL_REVISION:[],
 
828
            })
 
829
        search = graph._make_breadth_first_searcher(['head'])
 
830
        expected = [
 
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
 
835
            # next iteration.
 
836
            (set(['head', 'child', 'ghost1']),
 
837
             (set(['head']), set(['ghost1', NULL_REVISION]), 2),
 
838
             ['head', 'child'], None, [NULL_REVISION, 'ghost1']),
 
839
            ]
 
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)
 
844
 
 
845
    def test_breadth_first_get_result_ghosts_are_excluded(self):
 
846
        graph = self.make_graph({
 
847
            'head':['child', 'ghost'],
 
848
            'child':[NULL_REVISION],
 
849
            NULL_REVISION:[],
 
850
            })
 
851
        search = graph._make_breadth_first_searcher(['head'])
 
852
        # using next:
 
853
        expected = [
 
854
            (set(['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),
 
860
            ]
 
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)
 
865
 
 
866
    def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
 
867
        graph = self.make_graph({
 
868
            'head':['child'],
 
869
            'child':[NULL_REVISION],
 
870
            NULL_REVISION:[],
 
871
            })
 
872
        search = graph._make_breadth_first_searcher(['head'])
 
873
        # using next:
 
874
        expected = [
 
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),
 
881
            ]
 
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)
 
886
 
 
887
    def test_breadth_first_revision_count_includes_NULL_REVISION(self):
 
888
        graph = self.make_graph({
 
889
            'head':[NULL_REVISION],
 
890
            NULL_REVISION:[],
 
891
            })
 
892
        search = graph._make_breadth_first_searcher(['head'])
 
893
        # using next:
 
894
        expected = [
 
895
            (set(['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),
 
901
            ]
 
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)
 
906
 
 
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],
 
911
            NULL_REVISION:[],
 
912
            })
 
913
        search = graph._make_breadth_first_searcher(['head'])
 
914
        # using next:
 
915
        expected = [
 
916
            (set(['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),
 
922
            ]
 
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),
 
928
            result.get_recipe())
 
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),
 
937
            result.get_recipe())
 
938
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
939
 
684
940
 
685
941
class TestCachingParentsProvider(tests.TestCase):
686
942
 
690
946
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
691
947
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
692
948
 
693
 
    def test_get_parents(self):
694
 
        """Requesting the same revision should be returned from cache"""
695
 
        self.assertEqual({}, self.caching_pp._cache)
696
 
        self.assertEqual([('b',)],
697
 
            self.applyDeprecated(symbol_versioning.one_one,
698
 
            self.caching_pp.get_parents, ['a']))
699
 
        self.assertEqual(['a'], self.inst_pp.calls)
700
 
        self.assertEqual([('b',)],
701
 
            self.applyDeprecated(symbol_versioning.one_one,
702
 
            self.caching_pp.get_parents, ['a']))
703
 
        # No new call, as it should have been returned from the cache
704
 
        self.assertEqual(['a'], self.inst_pp.calls)
705
 
        self.assertEqual({'a':('b',)}, self.caching_pp._cache)
706
 
 
707
949
    def test_get_parent_map(self):
708
950
        """Requesting the same revision should be returned from cache"""
709
951
        self.assertEqual({}, self.caching_pp._cache)