/breezy/unstable

To get this branch, use:
bzr branch https://code.breezy-vcs.org/breezy/unstable

« back to all changes in this revision

Viewing changes to breezy/tests/test_graph.py

  • Committer: Jelmer Vernooij
  • Date: 2017-05-24 01:39:33 UTC
  • mfrom: (3815.3776.6)
  • Revision ID: jelmer@jelmer.uk-20170524013933-ir4y4tqtrsiz2ka2
New upstream snapshot.

Show diffs side-by-side

added added

removed removed

Lines of Context:
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
from bzrlib import (
 
17
from .. import (
18
18
    errors,
19
19
    graph as _mod_graph,
20
20
    tests,
21
21
    )
22
 
from bzrlib.revision import NULL_REVISION
23
 
from bzrlib.tests import TestCaseWithMemoryTransport
 
22
from ..revision import NULL_REVISION
 
23
from . import TestCaseWithMemoryTransport
24
24
 
25
25
 
26
26
# Ancestry 1:
528
528
        """
529
529
        graph = self.make_graph(ancestry_1)
530
530
        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
531
 
        self.assertEqual(set([NULL_REVISION]),
 
531
        self.assertEqual({NULL_REVISION},
532
532
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
533
 
        self.assertEqual(set([NULL_REVISION]),
 
533
        self.assertEqual({NULL_REVISION},
534
534
                         graph.find_lca(NULL_REVISION, 'rev1'))
535
 
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
536
 
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
535
        self.assertEqual({'rev1'}, graph.find_lca('rev1', 'rev1'))
 
536
        self.assertEqual({'rev1'}, graph.find_lca('rev2a', 'rev2b'))
537
537
 
538
538
    def test_no_unique_lca(self):
539
539
        """Test error when one revision is not in the graph"""
544
544
    def test_lca_criss_cross(self):
545
545
        """Test least-common-ancestor after a criss-cross merge."""
546
546
        graph = self.make_graph(criss_cross)
547
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
547
        self.assertEqual({'rev2a', 'rev2b'},
548
548
                         graph.find_lca('rev3a', 'rev3b'))
549
 
        self.assertEqual(set(['rev2b']),
 
549
        self.assertEqual({'rev2b'},
550
550
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
551
551
 
552
552
    def test_lca_shortcut(self):
553
553
        """Test least-common ancestor on this history shortcut"""
554
554
        graph = self.make_graph(history_shortcut)
555
 
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
555
        self.assertEqual({'rev2b'}, graph.find_lca('rev3a', 'rev3b'))
556
556
 
557
557
    def test_lefthand_distance_smoke(self):
558
558
        """A simple does it work test for graph.lefthand_distance(keys)."""
590
590
 
591
591
    def test__remove_simple_descendants(self):
592
592
        graph = self.make_graph(ancestry_1)
593
 
        self.assertRemoveDescendants(set(['rev1']), graph,
594
 
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
 
593
        self.assertRemoveDescendants({'rev1'}, graph,
 
594
            {'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'})
595
595
 
596
596
    def test__remove_simple_descendants_disjoint(self):
597
597
        graph = self.make_graph(ancestry_1)
598
 
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
599
 
            set(['rev1', 'rev3']))
 
598
        self.assertRemoveDescendants({'rev1', 'rev3'}, graph,
 
599
            {'rev1', 'rev3'})
600
600
 
601
601
    def test__remove_simple_descendants_chain(self):
602
602
        graph = self.make_graph(ancestry_1)
603
 
        self.assertRemoveDescendants(set(['rev1']), graph,
604
 
            set(['rev1', 'rev2a', 'rev3']))
 
603
        self.assertRemoveDescendants({'rev1'}, graph,
 
604
            {'rev1', 'rev2a', 'rev3'})
605
605
 
606
606
    def test__remove_simple_descendants_siblings(self):
607
607
        graph = self.make_graph(ancestry_1)
608
 
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
609
 
            set(['rev2a', 'rev2b', 'rev3']))
 
608
        self.assertRemoveDescendants({'rev2a', 'rev2b'}, graph,
 
609
            {'rev2a', 'rev2b', 'rev3'})
610
610
 
611
611
    def test_unique_lca_criss_cross(self):
612
612
        """Ensure we don't pick non-unique lcas in a criss-cross"""
652
652
    def test_graph_difference(self):
653
653
        graph = self.make_graph(ancestry_1)
654
654
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
655
 
        self.assertEqual((set(), set(['rev1'])),
 
655
        self.assertEqual((set(), {'rev1'}),
656
656
                         graph.find_difference(NULL_REVISION, 'rev1'))
657
 
        self.assertEqual((set(['rev1']), set()),
 
657
        self.assertEqual(({'rev1'}, set()),
658
658
                         graph.find_difference('rev1', NULL_REVISION))
659
 
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
659
        self.assertEqual(({'rev2a', 'rev3'}, {'rev2b'}),
660
660
                         graph.find_difference('rev3', 'rev2b'))
661
 
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
661
        self.assertEqual(({'rev4', 'rev3', 'rev2a'}, set()),
662
662
                         graph.find_difference('rev4', 'rev2b'))
663
663
 
664
664
    def test_graph_difference_separate_ancestry(self):
665
665
        graph = self.make_graph(ancestry_2)
666
 
        self.assertEqual((set(['rev1a']), set(['rev1b'])),
 
666
        self.assertEqual(({'rev1a'}, {'rev1b'}),
667
667
                         graph.find_difference('rev1a', 'rev1b'))
668
 
        self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
669
 
                          set(['rev1b'])),
 
668
        self.assertEqual(({'rev1a', 'rev2a', 'rev3a', 'rev4a'},
 
669
                          {'rev1b'}),
670
670
                         graph.find_difference('rev4a', 'rev1b'))
671
671
 
672
672
    def test_graph_difference_criss_cross(self):
673
673
        graph = self.make_graph(criss_cross)
674
 
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
674
        self.assertEqual(({'rev3a'}, {'rev3b'}),
675
675
                         graph.find_difference('rev3a', 'rev3b'))
676
 
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
676
        self.assertEqual((set([]), {'rev3b', 'rev2b'}),
677
677
                         graph.find_difference('rev2a', 'rev3b'))
678
678
 
679
679
    def test_graph_difference_extended_history(self):
680
680
        graph = self.make_graph(extended_history_shortcut)
681
 
        self.assertEqual((set(['e']), set(['f'])),
 
681
        self.assertEqual(({'e'}, {'f'}),
682
682
                         graph.find_difference('e', 'f'))
683
 
        self.assertEqual((set(['f']), set(['e'])),
 
683
        self.assertEqual(({'f'}, {'e'}),
684
684
                         graph.find_difference('f', 'e'))
685
685
 
686
686
    def test_graph_difference_double_shortcut(self):
687
687
        graph = self.make_graph(double_shortcut)
688
 
        self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
 
688
        self.assertEqual(({'d', 'f'}, {'e', 'g'}),
689
689
                         graph.find_difference('f', 'g'))
690
690
 
691
691
    def test_graph_difference_complex_shortcut(self):
692
692
        graph = self.make_graph(complex_shortcut)
693
 
        self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
 
693
        self.assertEqual(({'m', 'i', 'e'}, {'n', 'h'}),
694
694
                         graph.find_difference('m', 'n'))
695
695
 
696
696
    def test_graph_difference_complex_shortcut2(self):
697
697
        graph = self.make_graph(complex_shortcut2)
698
 
        self.assertEqual((set(['t']), set(['j', 'u'])),
 
698
        self.assertEqual(({'t'}, {'j', 'u'}),
699
699
                         graph.find_difference('t', 'u'))
700
700
 
701
701
    def test_graph_difference_shortcut_extra_root(self):
702
702
        graph = self.make_graph(shortcut_extra_root)
703
 
        self.assertEqual((set(['e']), set(['f', 'g'])),
 
703
        self.assertEqual(({'e'}, {'f', 'g'}),
704
704
                         graph.find_difference('e', 'f'))
705
705
 
706
706
    def test_iter_topo_order(self):
791
791
        #      c
792
792
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
793
793
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
794
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
 
794
        self.assertEqual({'c'}, graph.heads(['a', 'c', 'e']))
795
795
 
796
796
    def test_heads_null(self):
797
797
        graph = self.make_graph(ancestry_1)
798
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
799
 
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
800
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
801
 
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
802
 
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
798
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
799
        self.assertEqual({'rev1'}, graph.heads(['null:', 'rev1']))
 
800
        self.assertEqual({'rev1'}, graph.heads(['rev1', 'null:']))
 
801
        self.assertEqual({'rev1'}, graph.heads({'rev1', 'null:'}))
 
802
        self.assertEqual({'rev1'}, graph.heads(('rev1', 'null:')))
803
803
 
804
804
    def test_heads_one(self):
805
805
        # A single node will always be a head
806
806
        graph = self.make_graph(ancestry_1)
807
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
808
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
809
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
810
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
811
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
812
 
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
807
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
808
        self.assertEqual({'rev1'}, graph.heads(['rev1']))
 
809
        self.assertEqual({'rev2a'}, graph.heads(['rev2a']))
 
810
        self.assertEqual({'rev2b'}, graph.heads(['rev2b']))
 
811
        self.assertEqual({'rev3'}, graph.heads(['rev3']))
 
812
        self.assertEqual({'rev4'}, graph.heads(['rev4']))
813
813
 
814
814
    def test_heads_single(self):
815
815
        graph = self.make_graph(ancestry_1)
816
 
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
817
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
818
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
819
 
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
820
 
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
821
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
822
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
823
 
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
816
        self.assertEqual({'rev4'}, graph.heads(['null:', 'rev4']))
 
817
        self.assertEqual({'rev2a'}, graph.heads(['rev1', 'rev2a']))
 
818
        self.assertEqual({'rev2b'}, graph.heads(['rev1', 'rev2b']))
 
819
        self.assertEqual({'rev3'}, graph.heads(['rev1', 'rev3']))
 
820
        self.assertEqual({'rev4'}, graph.heads(['rev1', 'rev4']))
 
821
        self.assertEqual({'rev4'}, graph.heads(['rev2a', 'rev4']))
 
822
        self.assertEqual({'rev4'}, graph.heads(['rev2b', 'rev4']))
 
823
        self.assertEqual({'rev4'}, graph.heads(['rev3', 'rev4']))
824
824
 
825
825
    def test_heads_two_heads(self):
826
826
        graph = self.make_graph(ancestry_1)
827
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
827
        self.assertEqual({'rev2a', 'rev2b'},
828
828
                         graph.heads(['rev2a', 'rev2b']))
829
 
        self.assertEqual(set(['rev3', 'rev2b']),
 
829
        self.assertEqual({'rev3', 'rev2b'},
830
830
                         graph.heads(['rev3', 'rev2b']))
831
831
 
832
832
    def test_heads_criss_cross(self):
833
833
        graph = self.make_graph(criss_cross)
834
 
        self.assertEqual(set(['rev2a']),
 
834
        self.assertEqual({'rev2a'},
835
835
                         graph.heads(['rev2a', 'rev1']))
836
 
        self.assertEqual(set(['rev2b']),
 
836
        self.assertEqual({'rev2b'},
837
837
                         graph.heads(['rev2b', 'rev1']))
838
 
        self.assertEqual(set(['rev3a']),
 
838
        self.assertEqual({'rev3a'},
839
839
                         graph.heads(['rev3a', 'rev1']))
840
 
        self.assertEqual(set(['rev3b']),
 
840
        self.assertEqual({'rev3b'},
841
841
                         graph.heads(['rev3b', 'rev1']))
842
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
842
        self.assertEqual({'rev2a', 'rev2b'},
843
843
                         graph.heads(['rev2a', 'rev2b']))
844
 
        self.assertEqual(set(['rev3a']),
 
844
        self.assertEqual({'rev3a'},
845
845
                         graph.heads(['rev3a', 'rev2a']))
846
 
        self.assertEqual(set(['rev3a']),
 
846
        self.assertEqual({'rev3a'},
847
847
                         graph.heads(['rev3a', 'rev2b']))
848
 
        self.assertEqual(set(['rev3a']),
 
848
        self.assertEqual({'rev3a'},
849
849
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
850
 
        self.assertEqual(set(['rev3b']),
 
850
        self.assertEqual({'rev3b'},
851
851
                         graph.heads(['rev3b', 'rev2a']))
852
 
        self.assertEqual(set(['rev3b']),
 
852
        self.assertEqual({'rev3b'},
853
853
                         graph.heads(['rev3b', 'rev2b']))
854
 
        self.assertEqual(set(['rev3b']),
 
854
        self.assertEqual({'rev3b'},
855
855
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
856
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
856
        self.assertEqual({'rev3a', 'rev3b'},
857
857
                         graph.heads(['rev3a', 'rev3b']))
858
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
858
        self.assertEqual({'rev3a', 'rev3b'},
859
859
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
860
860
 
861
861
    def test_heads_shortcut(self):
862
862
        graph = self.make_graph(history_shortcut)
863
863
 
864
 
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
864
        self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
865
865
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
866
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
866
        self.assertEqual({'rev3a', 'rev3b'},
867
867
                         graph.heads(['rev3a', 'rev3b']))
868
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
868
        self.assertEqual({'rev3a', 'rev3b'},
869
869
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
870
 
        self.assertEqual(set(['rev2a', 'rev3b']),
 
870
        self.assertEqual({'rev2a', 'rev3b'},
871
871
                         graph.heads(['rev2a', 'rev3b']))
872
 
        self.assertEqual(set(['rev2c', 'rev3a']),
 
872
        self.assertEqual({'rev2c', 'rev3a'},
873
873
                         graph.heads(['rev2c', 'rev3a']))
874
874
 
875
875
    def _run_heads_break_deeper(self, graph_dict, search):
898
898
            'right':['common'],
899
899
            'common':['deeper'],
900
900
        }
901
 
        self.assertEqual(set(['left', 'right']),
 
901
        self.assertEqual({'left', 'right'},
902
902
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
903
903
 
904
904
    def test_heads_limits_search_assymetric(self):
910
910
            'common':['aftercommon'],
911
911
            'aftercommon':['deeper'],
912
912
        }
913
 
        self.assertEqual(set(['left', 'right']),
 
913
        self.assertEqual({'left', 'right'},
914
914
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
915
915
 
916
916
    def test_heads_limits_search_common_search_must_continue(self):
923
923
            'common1':['common2'],
924
924
            'common2':['deeper'],
925
925
        }
926
 
        self.assertEqual(set(['h1', 'h2']),
 
926
        self.assertEqual({'h1', 'h2'},
927
927
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
928
928
 
929
929
    def test_breadth_first_search_start_ghosts(self):
930
930
        graph = self.make_graph({})
931
931
        # with_ghosts reports the ghosts
932
932
        search = graph._make_breadth_first_searcher(['a-ghost'])
933
 
        self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
 
933
        self.assertEqual((set(), {'a-ghost'}), search.next_with_ghosts())
934
934
        self.assertRaises(StopIteration, search.next_with_ghosts)
935
935
        # next includes them
936
936
        search = graph._make_breadth_first_searcher(['a-ghost'])
937
 
        self.assertEqual(set(['a-ghost']), search.next())
 
937
        self.assertEqual({'a-ghost'}, search.next())
938
938
        self.assertRaises(StopIteration, search.next)
939
939
 
940
940
    def test_breadth_first_search_deep_ghosts(self):
945
945
            })
946
946
        # with_ghosts reports the ghosts
947
947
        search = graph._make_breadth_first_searcher(['head'])
948
 
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
949
 
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
950
 
        self.assertEqual((set(['child']), set(['ghost'])),
 
948
        self.assertEqual(({'head'}, set()), search.next_with_ghosts())
 
949
        self.assertEqual(({'present'}, set()), search.next_with_ghosts())
 
950
        self.assertEqual(({'child'}, {'ghost'}),
951
951
            search.next_with_ghosts())
952
952
        self.assertRaises(StopIteration, search.next_with_ghosts)
953
953
        # next includes them
954
954
        search = graph._make_breadth_first_searcher(['head'])
955
 
        self.assertEqual(set(['head']), search.next())
956
 
        self.assertEqual(set(['present']), search.next())
957
 
        self.assertEqual(set(['child', 'ghost']),
 
955
        self.assertEqual({'head'}, search.next())
 
956
        self.assertEqual({'present'}, search.next())
 
957
        self.assertEqual({'child', 'ghost'},
958
958
            search.next())
959
959
        self.assertRaises(StopIteration, search.next)
960
960
 
968
968
            })
969
969
        # start with next_with_ghosts
970
970
        search = graph._make_breadth_first_searcher(['head'])
971
 
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
972
 
        self.assertEqual(set(['present']), search.next())
973
 
        self.assertEqual((set(['child']), set(['ghost'])),
 
971
        self.assertEqual(({'head'}, set()), search.next_with_ghosts())
 
972
        self.assertEqual({'present'}, search.next())
 
973
        self.assertEqual(({'child'}, {'ghost'}),
974
974
            search.next_with_ghosts())
975
975
        self.assertRaises(StopIteration, search.next)
976
976
        # start with next
977
977
        search = graph._make_breadth_first_searcher(['head'])
978
 
        self.assertEqual(set(['head']), search.next())
979
 
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
980
 
        self.assertEqual(set(['child', 'ghost']),
 
978
        self.assertEqual({'head'}, search.next())
 
979
        self.assertEqual(({'present'}, set()), search.next_with_ghosts())
 
980
        self.assertEqual({'child', 'ghost'},
981
981
            search.next())
982
982
        self.assertRaises(StopIteration, search.next_with_ghosts)
983
983
 
990
990
            'other_2':[],
991
991
            })
992
992
        search = graph._make_breadth_first_searcher(['head'])
993
 
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
994
 
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
995
 
        self.assertEqual(set(['present']),
 
993
        self.assertEqual(({'head'}, set()), search.next_with_ghosts())
 
994
        self.assertEqual(({'present'}, set()), search.next_with_ghosts())
 
995
        self.assertEqual({'present'},
996
996
            search.stop_searching_any(['present']))
997
 
        self.assertEqual((set(['other']), set(['other_ghost'])),
 
997
        self.assertEqual(({'other'}, {'other_ghost'}),
998
998
            search.start_searching(['other', 'other_ghost']))
999
 
        self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
 
999
        self.assertEqual(({'other_2'}, set()), search.next_with_ghosts())
1000
1000
        self.assertRaises(StopIteration, search.next_with_ghosts)
1001
1001
        # next includes them
1002
1002
        search = graph._make_breadth_first_searcher(['head'])
1003
 
        self.assertEqual(set(['head']), search.next())
1004
 
        self.assertEqual(set(['present']), search.next())
1005
 
        self.assertEqual(set(['present']),
 
1003
        self.assertEqual({'head'}, search.next())
 
1004
        self.assertEqual({'present'}, search.next())
 
1005
        self.assertEqual({'present'},
1006
1006
            search.stop_searching_any(['present']))
1007
1007
        search.start_searching(['other', 'other_ghost'])
1008
 
        self.assertEqual(set(['other_2']), search.next())
 
1008
        self.assertEqual({'other_2'}, search.next())
1009
1009
        self.assertRaises(StopIteration, search.next)
1010
1010
 
1011
1011
    def assertSeenAndResult(self, instructions, search, next):
1042
1042
        search = graph._make_breadth_first_searcher(['head'])
1043
1043
        # At the start, nothing has been seen, to its all excluded:
1044
1044
        state = search.get_state()
1045
 
        self.assertEqual((set(['head']), set(['head']), set()),
 
1045
        self.assertEqual(({'head'}, {'head'}, set()),
1046
1046
            state)
1047
1047
        self.assertEqual(set(), search.seen)
1048
1048
        # using next:
1049
1049
        expected = [
1050
 
            (set(['head']), (set(['head']), set(['child']), 1),
 
1050
            ({'head'}, ({'head'}, {'child'}, 1),
1051
1051
             ['head'], None, None),
1052
 
            (set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
 
1052
            ({'head', 'child'}, ({'head'}, {NULL_REVISION}, 2),
1053
1053
             ['head', 'child'], None, None),
1054
 
            (set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
 
1054
            ({'head', 'child', NULL_REVISION}, ({'head'}, set(), 3),
1055
1055
             ['head', 'child', NULL_REVISION], None, None),
1056
1056
            ]
1057
1057
        self.assertSeenAndResult(expected, search, search.next)
1073
1073
        search.start_searching(['head'])
1074
1074
        # head has been seen:
1075
1075
        state = search.get_state()
1076
 
        self.assertEqual((set(['head']), set(['child']), set(['head'])),
 
1076
        self.assertEqual(({'head'}, {'child'}, {'head'}),
1077
1077
            state)
1078
 
        self.assertEqual(set(['head']), search.seen)
 
1078
        self.assertEqual({'head'}, search.seen)
1079
1079
        # using next:
1080
1080
        expected = [
1081
1081
            # stop at child, and start a new search at otherhead:
1082
1082
            # - otherhead counts as seen immediately when start_searching is
1083
1083
            # called.
1084
 
            (set(['head', 'child', 'otherhead']),
1085
 
             (set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
 
1084
            ({'head', 'child', 'otherhead'},
 
1085
             ({'head', 'otherhead'}, {'child', 'otherchild'}, 2),
1086
1086
             ['head', 'otherhead'], ['otherhead'], ['child']),
1087
 
            (set(['head', 'child', 'otherhead', 'otherchild']),
1088
 
             (set(['head', 'otherhead']), set(['child', 'excluded']), 3),
 
1087
            ({'head', 'child', 'otherhead', 'otherchild'},
 
1088
             ({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1089
1089
             ['head', 'otherhead', 'otherchild'], None, None),
1090
1090
            # stop searching excluded now
1091
 
            (set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1092
 
             (set(['head', 'otherhead']), set(['child', 'excluded']), 3),
 
1091
            ({'head', 'child', 'otherhead', 'otherchild', 'excluded'},
 
1092
             ({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1093
1093
             ['head', 'otherhead', 'otherchild'], None, ['excluded']),
1094
1094
            ]
1095
1095
        self.assertSeenAndResult(expected, search, search.next)
1109
1109
        search = graph._make_breadth_first_searcher(['head'])
1110
1110
        expected = [
1111
1111
            # NULL_REVISION and ghost1 have not been returned
1112
 
            (set(['head']),
1113
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
1112
            ({'head'},
 
1113
             ({'head'}, {'child', NULL_REVISION, 'ghost1'}, 1),
1114
1114
             ['head'], None, [NULL_REVISION, 'ghost1']),
1115
1115
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1116
1116
            # next iteration.
1117
 
            (set(['head', 'child', 'ghost1']),
1118
 
             (set(['head']), set(['ghost1', NULL_REVISION]), 2),
 
1117
            ({'head', 'child', 'ghost1'},
 
1118
             ({'head'}, {'ghost1', NULL_REVISION}, 2),
1119
1119
             ['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1120
1120
            ]
1121
1121
        self.assertSeenAndResult(expected, search, search.next)
1135
1135
            })
1136
1136
        search = graph._make_breadth_first_searcher(['head'])
1137
1137
        expected = [
1138
 
            (set(['head']), (set(['head']), set(['middle']), 1),
 
1138
            ({'head'}, ({'head'}, {'middle'}, 1),
1139
1139
             ['head'], None, None),
1140
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
 
1140
            ({'head', 'middle'}, ({'head'}, {'child'}, 2),
1141
1141
             ['head', 'middle'], None, None),
1142
1142
            # 'middle' came from the previous iteration, but we don't stop
1143
1143
            # searching it until *after* advancing the searcher.
1144
 
            (set(['head', 'middle', 'child']),
1145
 
             (set(['head']), set(['middle', 'child']), 1),
 
1144
            ({'head', 'middle', 'child'},
 
1145
             ({'head'}, {'middle', 'child'}, 1),
1146
1146
             ['head'], None, ['middle', 'child']),
1147
1147
            ]
1148
1148
        self.assertSeenAndResult(expected, search, search.next)
1159
1159
        search = graph._make_breadth_first_searcher(['head'])
1160
1160
        # using next:
1161
1161
        expected = [
1162
 
            (set(['head']),
1163
 
             (set(['head']), set(['ghost', 'child']), 1),
 
1162
            ({'head'},
 
1163
             ({'head'}, {'ghost', 'child'}, 1),
1164
1164
             ['head'], None, None),
1165
 
            (set(['head', 'child', 'ghost']),
1166
 
             (set(['head']), set([NULL_REVISION, 'ghost']), 2),
 
1165
            ({'head', 'child', 'ghost'},
 
1166
             ({'head'}, {NULL_REVISION, 'ghost'}, 2),
1167
1167
             ['head', 'child'], None, None),
1168
1168
            ]
1169
1169
        self.assertSeenAndResult(expected, search, search.next)
1180
1180
        search = graph._make_breadth_first_searcher(['head'])
1181
1181
        # using next:
1182
1182
        expected = [
1183
 
            (set(['head', 'ghost']),
1184
 
             (set(['head', 'ghost']), set(['child', 'ghost']), 1),
 
1183
            ({'head', 'ghost'},
 
1184
             ({'head', 'ghost'}, {'child', 'ghost'}, 1),
1185
1185
             ['head'], ['ghost'], None),
1186
 
            (set(['head', 'child', 'ghost']),
1187
 
             (set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
 
1186
            ({'head', 'child', 'ghost'},
 
1187
             ({'head', 'ghost'}, {NULL_REVISION, 'ghost'}, 2),
1188
1188
             ['head', 'child'], None, None),
1189
1189
            ]
1190
1190
        self.assertSeenAndResult(expected, search, search.next)
1200
1200
        search = graph._make_breadth_first_searcher(['head'])
1201
1201
        # using next:
1202
1202
        expected = [
1203
 
            (set(['head']),
1204
 
             (set(['head']), set([NULL_REVISION]), 1),
 
1203
            ({'head'},
 
1204
             ({'head'}, {NULL_REVISION}, 1),
1205
1205
             ['head'], None, None),
1206
 
            (set(['head', NULL_REVISION]),
1207
 
             (set(['head']), set([]), 2),
 
1206
            ({'head', NULL_REVISION},
 
1207
             ({'head'}, set([]), 2),
1208
1208
             ['head', NULL_REVISION], None, None),
1209
1209
            ]
1210
1210
        self.assertSeenAndResult(expected, search, search.next)
1221
1221
        search = graph._make_breadth_first_searcher(['head'])
1222
1222
        # using next:
1223
1223
        expected = [
1224
 
            (set(['head']),
1225
 
             (set(['head']), set([NULL_REVISION]), 1),
 
1224
            ({'head'},
 
1225
             ({'head'}, {NULL_REVISION}, 1),
1226
1226
             ['head'], None, None),
1227
 
            (set(['head', 'ghost', NULL_REVISION]),
1228
 
             (set(['head', 'ghost']), set(['ghost']), 2),
 
1227
            ({'head', 'ghost', NULL_REVISION},
 
1228
             ({'head', 'ghost'}, {'ghost'}, 2),
1229
1229
             ['head', NULL_REVISION], ['ghost'], None),
1230
1230
            ]
1231
1231
        self.assertSeenAndResult(expected, search, search.next)
1232
1232
        self.assertRaises(StopIteration, search.next)
1233
 
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
 
1233
        self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
1234
1234
        state = search.get_state()
1235
1235
        self.assertEqual(
1236
 
            (set(['ghost', 'head']), set(['ghost']),
1237
 
                set(['head', NULL_REVISION])),
 
1236
            ({'ghost', 'head'}, {'ghost'},
 
1237
                {'head', NULL_REVISION}),
1238
1238
            state)
1239
1239
        # using next_with_ghosts:
1240
1240
        search = graph._make_breadth_first_searcher(['head'])
1241
1241
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1242
        self.assertRaises(StopIteration, search.next)
1243
 
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
 
1243
        self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
1244
1244
        state = search.get_state()
1245
1245
        self.assertEqual(
1246
 
            (set(['ghost', 'head']), set(['ghost']),
1247
 
                set(['head', NULL_REVISION])),
 
1246
            ({'ghost', 'head'}, {'ghost'},
 
1247
                {'head', NULL_REVISION}),
1248
1248
            state)
1249
1249
 
1250
1250
 
1417
1417
    def test_find_descendants_rev1_rev3(self):
1418
1418
        graph = self.make_graph(ancestry_1)
1419
1419
        descendants = graph.find_descendants('rev1', 'rev3')
1420
 
        self.assertEqual(set(['rev1', 'rev2a', 'rev3']), descendants)
 
1420
        self.assertEqual({'rev1', 'rev2a', 'rev3'}, descendants)
1421
1421
 
1422
1422
    def test_find_descendants_rev1_rev4(self):
1423
1423
        graph = self.make_graph(ancestry_1)
1424
1424
        descendants = graph.find_descendants('rev1', 'rev4')
1425
 
        self.assertEqual(set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']),
 
1425
        self.assertEqual({'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'},
1426
1426
                         descendants)
1427
1427
 
1428
1428
    def test_find_descendants_rev2a_rev4(self):
1429
1429
        graph = self.make_graph(ancestry_1)
1430
1430
        descendants = graph.find_descendants('rev2a', 'rev4')
1431
 
        self.assertEqual(set(['rev2a', 'rev3', 'rev4']), descendants)
 
1431
        self.assertEqual({'rev2a', 'rev3', 'rev4'}, descendants)
1432
1432
 
1433
1433
class TestFindLefthandMerger(TestGraphBase):
1434
1434
 
1520
1520
        self.caching_pp.note_missing_key('b')
1521
1521
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1522
1522
        self.assertEqual([], self.inst_pp.calls)
1523
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
 
1523
        self.assertEqual({'b'}, self.caching_pp.missing_keys)
1524
1524
 
1525
1525
    def test_get_cached_parent_map(self):
1526
1526
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))