← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test__known_graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-09-02 18:07:58 UTC
  • mfrom: (4634.6.15 2.0)
  • Revision ID: pqm@pqm.ubuntu.com-20090902180758-uuuxc8dd62vq67i8
(jam) Merge 2.0 4649 into bzr.dev

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test__known_graph.py
768
768
                },
769
769
                'E',
770
770
                [])
 
771
 
 
772
 
 
773
class TestKnownGraphStableReverseTopoSort(TestCaseWithKnownGraph):
 
774
    """Test the sort order returned by gc_sort."""
 
775
 
 
776
    def assertSorted(self, expected, parent_map):
 
777
        graph = self.make_known_graph(parent_map)
 
778
        value = graph.gc_sort()
 
779
        if expected != value:
 
780
            self.assertEqualDiff(pprint.pformat(expected),
 
781
                                 pprint.pformat(value))
 
782
 
 
783
    def test_empty(self):
 
784
        self.assertSorted([], {})
 
785
 
 
786
    def test_single(self):
 
787
        self.assertSorted(['a'], {'a':()})
 
788
        self.assertSorted([('a',)], {('a',):()})
 
789
        self.assertSorted([('F', 'a')], {('F', 'a'):()})
 
790
 
 
791
    def test_linear(self):
 
792
        self.assertSorted(['c', 'b', 'a'], {'a':(), 'b':('a',), 'c':('b',)})
 
793
        self.assertSorted([('c',), ('b',), ('a',)],
 
794
                          {('a',):(), ('b',): (('a',),), ('c',): (('b',),)})
 
795
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a')],
 
796
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
797
                           ('F', 'c'): (('F', 'b'),)})
 
798
 
 
799
    def test_mixed_ancestries(self):
 
800
        # Each prefix should be sorted separately
 
801
        self.assertSorted([('F', 'c'), ('F', 'b'), ('F', 'a'),
 
802
                           ('G', 'c'), ('G', 'b'), ('G', 'a'),
 
803
                           ('Q', 'c'), ('Q', 'b'), ('Q', 'a'),
 
804
                          ],
 
805
                          {('F', 'a'):(), ('F', 'b'): (('F', 'a'),),
 
806
                           ('F', 'c'): (('F', 'b'),),
 
807
                           ('G', 'a'):(), ('G', 'b'): (('G', 'a'),),
 
808
                           ('G', 'c'): (('G', 'b'),),
 
809
                           ('Q', 'a'):(), ('Q', 'b'): (('Q', 'a'),),
 
810
                           ('Q', 'c'): (('Q', 'b'),),
 
811
                          })
 
812
 
 
813
    def test_stable_sorting(self):
 
814
        # the sort order should be stable even when extra nodes are added
 
815
        self.assertSorted(['b', 'c', 'a'],
 
816
                          {'a':(), 'b':('a',), 'c':('a',)})
 
817
        self.assertSorted(['b', 'c', 'd', 'a'],
 
818
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
819
        self.assertSorted(['b', 'c', 'd', 'a'],
 
820
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',)})
 
821
        self.assertSorted(['Z', 'b', 'c', 'd', 'a'],
 
822
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
823
                           'Z':('a',)})
 
824
        self.assertSorted(['e', 'b', 'c', 'f', 'Z', 'd', 'a'],
 
825
                          {'a':(), 'b':('a',), 'c':('a',), 'd':('a',),
 
826
                           'Z':('a',),
 
827
                           'e':('b', 'c', 'd'),
 
828
                           'f':('d', 'Z'),
 
829
                           })
 
830
 
 
831
    def test_skip_ghost(self):
 
832
        self.assertSorted(['b', 'c', 'a'],
 
833
                          {'a':(), 'b':('a', 'ghost'), 'c':('a',)})
 
834
 
 
835
    def test_skip_mainline_ghost(self):
 
836
        self.assertSorted(['b', 'c', 'a'],
 
837
                          {'a':(), 'b':('ghost', 'a'), 'c':('a',)})