← 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-01-14 01:40:02 UTC
  • mfrom: (3177.1.1 ianc-integration)
  • Revision ID: pqm@pqm.ubuntu.com-20080114014002-pz5tya37urp1n3fk
Fix typos of Firefox and OpenOffice.org in docs (Matt Nordhoff)

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
 
 
257
241
class InstrumentedParentsProvider(object):
258
242
 
259
243
    def __init__(self, parents_provider):
268
252
class TestGraph(TestCaseWithMemoryTransport):
269
253
 
270
254
    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?
271
257
        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()
272
262
 
273
263
    def prepare_memory_tree(self, location):
274
264
        tree = self.make_branch_and_memory_tree(location)
505
495
        self.assertFalse(graph.is_ancestor('a', 'c'))
506
496
        self.assertTrue('null:' not in instrumented_provider.calls)
507
497
 
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
 
 
527
498
    def test_filter_candidate_lca(self):
528
499
        """Test filter_candidate_lca for a corner case
529
500
 
681
652
        self.assertEqual(set(['h1', 'h2']),
682
653
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
683
654
 
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
 
 
975
655
 
976
656
class TestCachingParentsProvider(tests.TestCase):
977
657