← 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-15 02:01:29 UTC
  • mfrom: (3177.3.3 breadth-first-ghosts)
  • Revision ID: pqm@pqm.ubuntu.com-20080115020129-jl22ugxkca1rox94
(robertc) Add next_with_ghosts to the api on breadth-first-searchers.
        (Robert Collins)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
652
652
        self.assertEqual(set(['h1', 'h2']),
653
653
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
654
654
 
 
655
    def test_breadth_first_search_start_ghosts(self):
 
656
        parent_graph = {}
 
657
        parents_provider = InstrumentedParentsProvider(
 
658
            _mod_graph.DictParentsProvider(parent_graph))
 
659
        graph = _mod_graph.Graph(parents_provider)
 
660
        # with_ghosts reports the ghosts
 
661
        search = graph._make_breadth_first_searcher(['a-ghost'])
 
662
        self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
 
663
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
664
        # next includes them
 
665
        search = graph._make_breadth_first_searcher(['a-ghost'])
 
666
        self.assertEqual(set(['a-ghost']), search.next())
 
667
        self.assertRaises(StopIteration, search.next)
 
668
 
 
669
    def test_breadth_first_search_deep_ghosts(self):
 
670
        parent_graph = {
 
671
            'head':['present'],
 
672
            'present':['child', 'ghost'],
 
673
            'child':[],
 
674
            }
 
675
        parents_provider = InstrumentedParentsProvider(
 
676
            _mod_graph.DictParentsProvider(parent_graph))
 
677
        graph = _mod_graph.Graph(parents_provider)
 
678
        # with_ghosts reports the ghosts
 
679
        search = graph._make_breadth_first_searcher(['head'])
 
680
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
 
681
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
 
682
        self.assertEqual((set(['child']), set(['ghost'])),
 
683
            search.next_with_ghosts())
 
684
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
685
        # next includes them
 
686
        search = graph._make_breadth_first_searcher(['head'])
 
687
        self.assertEqual(set(['head']), search.next())
 
688
        self.assertEqual(set(['present']), search.next())
 
689
        self.assertEqual(set(['child', 'ghost']),
 
690
            search.next())
 
691
        self.assertRaises(StopIteration, search.next)
 
692
 
 
693
    def test_breadth_first_search_change_next_to_next_with_ghosts(self):
 
694
        # To make the API robust, we allow calling both next() and
 
695
        # next_with_ghosts() on the same searcher.
 
696
        parent_graph = {
 
697
            'head':['present'],
 
698
            'present':['child', 'ghost'],
 
699
            'child':[],
 
700
            }
 
701
        parents_provider = InstrumentedParentsProvider(
 
702
            _mod_graph.DictParentsProvider(parent_graph))
 
703
        graph = _mod_graph.Graph(parents_provider)
 
704
        # start with next_with_ghosts
 
705
        search = graph._make_breadth_first_searcher(['head'])
 
706
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
 
707
        self.assertEqual(set(['present']), search.next())
 
708
        self.assertEqual((set(['child']), set(['ghost'])),
 
709
            search.next_with_ghosts())
 
710
        self.assertRaises(StopIteration, search.next)
 
711
        # start with next
 
712
        search = graph._make_breadth_first_searcher(['head'])
 
713
        self.assertEqual(set(['head']), search.next())
 
714
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
 
715
        self.assertEqual(set(['child', 'ghost']),
 
716
            search.next())
 
717
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
718
 
 
719
    def test_breadth_first_change_search(self):
 
720
        # Changing the search should work with both next and next_with_ghosts.
 
721
        parent_graph = {
 
722
            'head':['present'],
 
723
            'present':['stopped'],
 
724
            'other':['other_2'],
 
725
            'other_2':[],
 
726
            }
 
727
        parents_provider = InstrumentedParentsProvider(
 
728
            _mod_graph.DictParentsProvider(parent_graph))
 
729
        graph = _mod_graph.Graph(parents_provider)
 
730
        search = graph._make_breadth_first_searcher(['head'])
 
731
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
 
732
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
 
733
        self.assertEqual(set(['present']),
 
734
            search.stop_searching_any(['present']))
 
735
        self.assertEqual((set(['other']), set(['other_ghost'])),
 
736
            search.start_searching(['other', 'other_ghost']))
 
737
        self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
 
738
        self.assertRaises(StopIteration, search.next_with_ghosts)
 
739
        # next includes them
 
740
        search = graph._make_breadth_first_searcher(['head'])
 
741
        self.assertEqual(set(['head']), search.next())
 
742
        self.assertEqual(set(['present']), search.next())
 
743
        self.assertEqual(set(['present']),
 
744
            search.stop_searching_any(['present']))
 
745
        search.start_searching(['other', 'other_ghost'])
 
746
        self.assertEqual(set(['other_2']), search.next())
 
747
        self.assertRaises(StopIteration, search.next)
 
748
 
655
749
 
656
750
class TestCachingParentsProvider(tests.TestCase):
657
751