591
593
def test__remove_simple_descendants(self):
592
594
graph = self.make_graph(ancestry_1)
593
self.assertRemoveDescendants({'rev1'}, graph,
594
{'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'})
595
self.assertRemoveDescendants({b'rev1'}, graph,
596
{b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'})
596
598
def test__remove_simple_descendants_disjoint(self):
597
599
graph = self.make_graph(ancestry_1)
598
self.assertRemoveDescendants({'rev1', 'rev3'}, graph,
600
self.assertRemoveDescendants({b'rev1', b'rev3'}, graph,
601
603
def test__remove_simple_descendants_chain(self):
602
604
graph = self.make_graph(ancestry_1)
603
self.assertRemoveDescendants({'rev1'}, graph,
604
{'rev1', 'rev2a', 'rev3'})
605
self.assertRemoveDescendants({b'rev1'}, graph,
606
{b'rev1', b'rev2a', b'rev3'})
606
608
def test__remove_simple_descendants_siblings(self):
607
609
graph = self.make_graph(ancestry_1)
608
self.assertRemoveDescendants({'rev2a', 'rev2b'}, graph,
609
{'rev2a', 'rev2b', 'rev3'})
610
self.assertRemoveDescendants({b'rev2a', b'rev2b'}, graph,
611
{b'rev2a', b'rev2b', b'rev3'})
611
613
def test_unique_lca_criss_cross(self):
612
614
"""Ensure we don't pick non-unique lcas in a criss-cross"""
613
615
graph = self.make_graph(criss_cross)
614
self.assertEqual('rev1', graph.find_unique_lca('rev3a', 'rev3b'))
615
lca, steps = graph.find_unique_lca('rev3a', 'rev3b', count_steps=True)
616
self.assertEqual('rev1', lca)
616
self.assertEqual(b'rev1', graph.find_unique_lca(b'rev3a', b'rev3b'))
617
lca, steps = graph.find_unique_lca(
618
b'rev3a', b'rev3b', count_steps=True)
619
self.assertEqual(b'rev1', lca)
617
620
self.assertEqual(2, steps)
619
622
def test_unique_lca_null_revision(self):
620
623
"""Ensure we pick NULL_REVISION when necessary"""
621
624
graph = self.make_graph(criss_cross2)
622
self.assertEqual('rev1b', graph.find_unique_lca('rev2a', 'rev1b'))
625
self.assertEqual(b'rev1b', graph.find_unique_lca(b'rev2a', b'rev1b'))
623
626
self.assertEqual(NULL_REVISION,
624
graph.find_unique_lca('rev2a', 'rev2b'))
627
graph.find_unique_lca(b'rev2a', b'rev2b'))
626
629
def test_unique_lca_null_revision2(self):
627
630
"""Ensure we pick NULL_REVISION when necessary"""
628
631
graph = self.make_graph(ancestry_2)
629
632
self.assertEqual(NULL_REVISION,
630
graph.find_unique_lca('rev4a', 'rev1b'))
633
graph.find_unique_lca(b'rev4a', b'rev1b'))
632
635
def test_lca_double_shortcut(self):
633
636
graph = self.make_graph(double_shortcut)
634
self.assertEqual('c', graph.find_unique_lca('f', 'g'))
637
self.assertEqual(b'c', graph.find_unique_lca(b'f', b'g'))
636
639
def test_common_ancestor_two_repos(self):
637
640
"""Ensure we do unique_lca using data from two repos"""
648
651
graph = mainline_tree.branch.repository.get_graph(
649
652
feature_tree.branch.repository)
650
self.assertEqual('rev2b', graph.find_unique_lca('rev2a', 'rev3b'))
653
self.assertEqual(b'rev2b', graph.find_unique_lca(b'rev2a', b'rev3b'))
652
655
def test_graph_difference(self):
653
656
graph = self.make_graph(ancestry_1)
654
self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
655
self.assertEqual((set(), {'rev1'}),
656
graph.find_difference(NULL_REVISION, 'rev1'))
657
self.assertEqual(({'rev1'}, set()),
658
graph.find_difference('rev1', NULL_REVISION))
659
self.assertEqual(({'rev2a', 'rev3'}, {'rev2b'}),
660
graph.find_difference('rev3', 'rev2b'))
661
self.assertEqual(({'rev4', 'rev3', 'rev2a'}, set()),
662
graph.find_difference('rev4', 'rev2b'))
658
(set(), set()), graph.find_difference(b'rev1', b'rev1'))
659
self.assertEqual((set(), {b'rev1'}),
660
graph.find_difference(NULL_REVISION, b'rev1'))
661
self.assertEqual(({b'rev1'}, set()),
662
graph.find_difference(b'rev1', NULL_REVISION))
663
self.assertEqual(({b'rev2a', b'rev3'}, {b'rev2b'}),
664
graph.find_difference(b'rev3', b'rev2b'))
665
self.assertEqual(({b'rev4', b'rev3', b'rev2a'}, set()),
666
graph.find_difference(b'rev4', b'rev2b'))
664
668
def test_graph_difference_separate_ancestry(self):
665
669
graph = self.make_graph(ancestry_2)
666
self.assertEqual(({'rev1a'}, {'rev1b'}),
667
graph.find_difference('rev1a', 'rev1b'))
668
self.assertEqual(({'rev1a', 'rev2a', 'rev3a', 'rev4a'},
670
graph.find_difference('rev4a', 'rev1b'))
670
self.assertEqual(({b'rev1a'}, {b'rev1b'}),
671
graph.find_difference(b'rev1a', b'rev1b'))
672
self.assertEqual(({b'rev1a', b'rev2a', b'rev3a', b'rev4a'},
674
graph.find_difference(b'rev4a', b'rev1b'))
672
676
def test_graph_difference_criss_cross(self):
673
677
graph = self.make_graph(criss_cross)
674
self.assertEqual(({'rev3a'}, {'rev3b'}),
675
graph.find_difference('rev3a', 'rev3b'))
676
self.assertEqual((set([]), {'rev3b', 'rev2b'}),
677
graph.find_difference('rev2a', 'rev3b'))
678
self.assertEqual(({b'rev3a'}, {b'rev3b'}),
679
graph.find_difference(b'rev3a', b'rev3b'))
680
self.assertEqual((set([]), {b'rev3b', b'rev2b'}),
681
graph.find_difference(b'rev2a', b'rev3b'))
679
683
def test_graph_difference_extended_history(self):
680
684
graph = self.make_graph(extended_history_shortcut)
681
self.assertEqual(({'e'}, {'f'}),
682
graph.find_difference('e', 'f'))
683
self.assertEqual(({'f'}, {'e'}),
684
graph.find_difference('f', 'e'))
685
self.assertEqual(({b'e'}, {b'f'}),
686
graph.find_difference(b'e', b'f'))
687
self.assertEqual(({b'f'}, {b'e'}),
688
graph.find_difference(b'f', b'e'))
686
690
def test_graph_difference_double_shortcut(self):
687
691
graph = self.make_graph(double_shortcut)
688
self.assertEqual(({'d', 'f'}, {'e', 'g'}),
689
graph.find_difference('f', 'g'))
692
self.assertEqual(({b'd', b'f'}, {b'e', b'g'}),
693
graph.find_difference(b'f', b'g'))
691
695
def test_graph_difference_complex_shortcut(self):
692
696
graph = self.make_graph(complex_shortcut)
693
self.assertEqual(({'m', 'i', 'e'}, {'n', 'h'}),
694
graph.find_difference('m', 'n'))
697
self.assertEqual(({b'm', b'i', b'e'}, {b'n', b'h'}),
698
graph.find_difference(b'm', b'n'))
696
700
def test_graph_difference_complex_shortcut2(self):
697
701
graph = self.make_graph(complex_shortcut2)
698
self.assertEqual(({'t'}, {'j', 'u'}),
699
graph.find_difference('t', 'u'))
702
self.assertEqual(({b't'}, {b'j', b'u'}),
703
graph.find_difference(b't', b'u'))
701
705
def test_graph_difference_shortcut_extra_root(self):
702
706
graph = self.make_graph(shortcut_extra_root)
703
self.assertEqual(({'e'}, {'f', 'g'}),
704
graph.find_difference('e', 'f'))
707
self.assertEqual(({b'e'}, {b'f', b'g'}),
708
graph.find_difference(b'e', b'f'))
706
710
def test_iter_topo_order(self):
707
711
graph = self.make_graph(ancestry_1)
708
args = ['rev2a', 'rev3', 'rev1']
712
args = [b'rev2a', b'rev3', b'rev1']
709
713
topo_args = list(graph.iter_topo_order(args))
710
714
self.assertEqual(set(args), set(topo_args))
711
self.assertTrue(topo_args.index('rev2a') > topo_args.index('rev1'))
712
self.assertTrue(topo_args.index('rev2a') < topo_args.index('rev3'))
715
self.assertTrue(topo_args.index(b'rev2a') > topo_args.index(b'rev1'))
716
self.assertTrue(topo_args.index(b'rev2a') < topo_args.index(b'rev3'))
714
718
def test_is_ancestor(self):
715
719
graph = self.make_graph(ancestry_1)
716
self.assertEqual(True, graph.is_ancestor('null:', 'null:'))
717
self.assertEqual(True, graph.is_ancestor('null:', 'rev1'))
718
self.assertEqual(False, graph.is_ancestor('rev1', 'null:'))
719
self.assertEqual(True, graph.is_ancestor('null:', 'rev4'))
720
self.assertEqual(False, graph.is_ancestor('rev4', 'null:'))
721
self.assertEqual(False, graph.is_ancestor('rev4', 'rev2b'))
722
self.assertEqual(True, graph.is_ancestor('rev2b', 'rev4'))
723
self.assertEqual(False, graph.is_ancestor('rev2b', 'rev3'))
724
self.assertEqual(False, graph.is_ancestor('rev3', 'rev2b'))
720
self.assertEqual(True, graph.is_ancestor(b'null:', b'null:'))
721
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev1'))
722
self.assertEqual(False, graph.is_ancestor(b'rev1', b'null:'))
723
self.assertEqual(True, graph.is_ancestor(b'null:', b'rev4'))
724
self.assertEqual(False, graph.is_ancestor(b'rev4', b'null:'))
725
self.assertEqual(False, graph.is_ancestor(b'rev4', b'rev2b'))
726
self.assertEqual(True, graph.is_ancestor(b'rev2b', b'rev4'))
727
self.assertEqual(False, graph.is_ancestor(b'rev2b', b'rev3'))
728
self.assertEqual(False, graph.is_ancestor(b'rev3', b'rev2b'))
725
729
instrumented_provider = InstrumentedParentsProvider(graph)
726
730
instrumented_graph = _mod_graph.Graph(instrumented_provider)
727
instrumented_graph.is_ancestor('rev2a', 'rev2b')
728
self.assertTrue('null:' not in instrumented_provider.calls)
731
instrumented_graph.is_ancestor(b'rev2a', b'rev2b')
732
self.assertTrue(b'null:' not in instrumented_provider.calls)
730
734
def test_is_between(self):
731
735
graph = self.make_graph(ancestry_1)
732
self.assertEqual(True, graph.is_between('null:', 'null:', 'null:'))
733
self.assertEqual(True, graph.is_between('rev1', 'null:', 'rev1'))
734
self.assertEqual(True, graph.is_between('rev1', 'rev1', 'rev4'))
735
self.assertEqual(True, graph.is_between('rev4', 'rev1', 'rev4'))
736
self.assertEqual(True, graph.is_between('rev3', 'rev1', 'rev4'))
737
self.assertEqual(False, graph.is_between('rev4', 'rev1', 'rev3'))
738
self.assertEqual(False, graph.is_between('rev1', 'rev2a', 'rev4'))
739
self.assertEqual(False, graph.is_between('null:', 'rev1', 'rev4'))
736
self.assertEqual(True, graph.is_between(b'null:', b'null:', b'null:'))
737
self.assertEqual(True, graph.is_between(b'rev1', b'null:', b'rev1'))
738
self.assertEqual(True, graph.is_between(b'rev1', b'rev1', b'rev4'))
739
self.assertEqual(True, graph.is_between(b'rev4', b'rev1', b'rev4'))
740
self.assertEqual(True, graph.is_between(b'rev3', b'rev1', b'rev4'))
741
self.assertEqual(False, graph.is_between(b'rev4', b'rev1', b'rev3'))
742
self.assertEqual(False, graph.is_between(b'rev1', b'rev2a', b'rev4'))
743
self.assertEqual(False, graph.is_between(b'null:', b'rev1', b'rev4'))
741
745
def test_is_ancestor_boundary(self):
742
746
"""Ensure that we avoid searching the whole graph.
792
graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
793
'a': [NULL_REVISION], 'e': [NULL_REVISION]})
794
self.assertEqual({'c'}, graph.heads(['a', 'c', 'e']))
796
graph = self.make_graph({b'c': [b'b', b'd'], b'd': [b'e'], b'b': [b'a'],
797
b'a': [NULL_REVISION], b'e': [NULL_REVISION]})
798
self.assertEqual({b'c'}, graph.heads([b'a', b'c', b'e']))
796
800
def test_heads_null(self):
797
801
graph = self.make_graph(ancestry_1)
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:')))
802
self.assertEqual({b'null:'}, graph.heads([b'null:']))
803
self.assertEqual({b'rev1'}, graph.heads([b'null:', b'rev1']))
804
self.assertEqual({b'rev1'}, graph.heads([b'rev1', b'null:']))
805
self.assertEqual({b'rev1'}, graph.heads({b'rev1', b'null:'}))
806
self.assertEqual({b'rev1'}, graph.heads((b'rev1', b'null:')))
804
808
def test_heads_one(self):
805
809
# A single node will always be a head
806
810
graph = self.make_graph(ancestry_1)
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']))
811
self.assertEqual({b'null:'}, graph.heads([b'null:']))
812
self.assertEqual({b'rev1'}, graph.heads([b'rev1']))
813
self.assertEqual({b'rev2a'}, graph.heads([b'rev2a']))
814
self.assertEqual({b'rev2b'}, graph.heads([b'rev2b']))
815
self.assertEqual({b'rev3'}, graph.heads([b'rev3']))
816
self.assertEqual({b'rev4'}, graph.heads([b'rev4']))
814
818
def test_heads_single(self):
815
819
graph = self.make_graph(ancestry_1)
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']))
820
self.assertEqual({b'rev4'}, graph.heads([b'null:', b'rev4']))
821
self.assertEqual({b'rev2a'}, graph.heads([b'rev1', b'rev2a']))
822
self.assertEqual({b'rev2b'}, graph.heads([b'rev1', b'rev2b']))
823
self.assertEqual({b'rev3'}, graph.heads([b'rev1', b'rev3']))
824
self.assertEqual({b'rev4'}, graph.heads([b'rev1', b'rev4']))
825
self.assertEqual({b'rev4'}, graph.heads([b'rev2a', b'rev4']))
826
self.assertEqual({b'rev4'}, graph.heads([b'rev2b', b'rev4']))
827
self.assertEqual({b'rev4'}, graph.heads([b'rev3', b'rev4']))
825
829
def test_heads_two_heads(self):
826
830
graph = self.make_graph(ancestry_1)
827
self.assertEqual({'rev2a', 'rev2b'},
828
graph.heads(['rev2a', 'rev2b']))
829
self.assertEqual({'rev3', 'rev2b'},
830
graph.heads(['rev3', 'rev2b']))
831
self.assertEqual({b'rev2a', b'rev2b'},
832
graph.heads([b'rev2a', b'rev2b']))
833
self.assertEqual({b'rev3', b'rev2b'},
834
graph.heads([b'rev3', b'rev2b']))
832
836
def test_heads_criss_cross(self):
833
837
graph = self.make_graph(criss_cross)
834
self.assertEqual({'rev2a'},
835
graph.heads(['rev2a', 'rev1']))
836
self.assertEqual({'rev2b'},
837
graph.heads(['rev2b', 'rev1']))
838
self.assertEqual({'rev3a'},
839
graph.heads(['rev3a', 'rev1']))
840
self.assertEqual({'rev3b'},
841
graph.heads(['rev3b', 'rev1']))
842
self.assertEqual({'rev2a', 'rev2b'},
843
graph.heads(['rev2a', 'rev2b']))
844
self.assertEqual({'rev3a'},
845
graph.heads(['rev3a', 'rev2a']))
846
self.assertEqual({'rev3a'},
847
graph.heads(['rev3a', 'rev2b']))
848
self.assertEqual({'rev3a'},
849
graph.heads(['rev3a', 'rev2a', 'rev2b']))
850
self.assertEqual({'rev3b'},
851
graph.heads(['rev3b', 'rev2a']))
852
self.assertEqual({'rev3b'},
853
graph.heads(['rev3b', 'rev2b']))
854
self.assertEqual({'rev3b'},
855
graph.heads(['rev3b', 'rev2a', 'rev2b']))
856
self.assertEqual({'rev3a', 'rev3b'},
857
graph.heads(['rev3a', 'rev3b']))
858
self.assertEqual({'rev3a', 'rev3b'},
859
graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
838
self.assertEqual({b'rev2a'},
839
graph.heads([b'rev2a', b'rev1']))
840
self.assertEqual({b'rev2b'},
841
graph.heads([b'rev2b', b'rev1']))
842
self.assertEqual({b'rev3a'},
843
graph.heads([b'rev3a', b'rev1']))
844
self.assertEqual({b'rev3b'},
845
graph.heads([b'rev3b', b'rev1']))
846
self.assertEqual({b'rev2a', b'rev2b'},
847
graph.heads([b'rev2a', b'rev2b']))
848
self.assertEqual({b'rev3a'},
849
graph.heads([b'rev3a', b'rev2a']))
850
self.assertEqual({b'rev3a'},
851
graph.heads([b'rev3a', b'rev2b']))
852
self.assertEqual({b'rev3a'},
853
graph.heads([b'rev3a', b'rev2a', b'rev2b']))
854
self.assertEqual({b'rev3b'},
855
graph.heads([b'rev3b', b'rev2a']))
856
self.assertEqual({b'rev3b'},
857
graph.heads([b'rev3b', b'rev2b']))
858
self.assertEqual({b'rev3b'},
859
graph.heads([b'rev3b', b'rev2a', b'rev2b']))
860
self.assertEqual({b'rev3a', b'rev3b'},
861
graph.heads([b'rev3a', b'rev3b']))
862
self.assertEqual({b'rev3a', b'rev3b'},
863
graph.heads([b'rev3a', b'rev3b', b'rev2a', b'rev2b']))
861
865
def test_heads_shortcut(self):
862
866
graph = self.make_graph(history_shortcut)
864
self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
865
graph.heads(['rev2a', 'rev2b', 'rev2c']))
866
self.assertEqual({'rev3a', 'rev3b'},
867
graph.heads(['rev3a', 'rev3b']))
868
self.assertEqual({'rev3a', 'rev3b'},
869
graph.heads(['rev2a', 'rev3a', 'rev3b']))
870
self.assertEqual({'rev2a', 'rev3b'},
871
graph.heads(['rev2a', 'rev3b']))
872
self.assertEqual({'rev2c', 'rev3a'},
873
graph.heads(['rev2c', 'rev3a']))
868
self.assertEqual({b'rev2a', b'rev2b', b'rev2c'},
869
graph.heads([b'rev2a', b'rev2b', b'rev2c']))
870
self.assertEqual({b'rev3a', b'rev3b'},
871
graph.heads([b'rev3a', b'rev3b']))
872
self.assertEqual({b'rev3a', b'rev3b'},
873
graph.heads([b'rev2a', b'rev3a', b'rev3b']))
874
self.assertEqual({b'rev2a', b'rev3b'},
875
graph.heads([b'rev2a', b'rev3b']))
876
self.assertEqual({b'rev2c', b'rev3a'},
877
graph.heads([b'rev2c', b'rev3a']))
875
879
def _run_heads_break_deeper(self, graph_dict, search):
876
880
"""Run heads on a graph-as-a-dict.
878
If the search asks for the parents of 'deeper' the test will fail.
882
If the search asks for the parents of b'deeper' the test will fail.
880
884
class stub(object):
882
887
def get_parent_map(keys):
886
891
self.fail('key deeper was accessed')
887
892
result[key] = graph_dict[key]
894
899
def test_heads_limits_search(self):
895
900
# test that a heads query does not search all of history
899
'common': ['deeper'],
902
b'left': [b'common'],
903
b'right': [b'common'],
904
b'common': [b'deeper'],
901
self.assertEqual({'left', 'right'},
902
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
906
self.assertEqual({b'left', b'right'},
907
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
904
909
def test_heads_limits_search_assymetric(self):
905
910
# test that a heads query does not search all of history
908
'midleft': ['common'],
910
'common': ['aftercommon'],
911
'aftercommon': ['deeper'],
912
b'left': [b'midleft'],
913
b'midleft': [b'common'],
914
b'right': [b'common'],
915
b'common': [b'aftercommon'],
916
b'aftercommon': [b'deeper'],
913
self.assertEqual({'left', 'right'},
914
self._run_heads_break_deeper(graph_dict, ['left', 'right']))
918
self.assertEqual({b'left', b'right'},
919
self._run_heads_break_deeper(graph_dict, [b'left', b'right']))
916
921
def test_heads_limits_search_common_search_must_continue(self):
917
922
# test that common nodes are still queried, preventing
918
923
# all-the-way-to-origin behaviour in the following graph:
920
'h1': ['shortcut', 'common1'],
922
'shortcut': ['common2'],
923
'common1': ['common2'],
924
'common2': ['deeper'],
925
b'h1': [b'shortcut', b'common1'],
927
b'shortcut': [b'common2'],
928
b'common1': [b'common2'],
929
b'common2': [b'deeper'],
926
self.assertEqual({'h1', 'h2'},
927
self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
931
self.assertEqual({b'h1', b'h2'},
932
self._run_heads_break_deeper(graph_dict, [b'h1', b'h2']))
929
934
def test_breadth_first_search_start_ghosts(self):
930
935
graph = self.make_graph({})
931
936
# with_ghosts reports the ghosts
932
search = graph._make_breadth_first_searcher(['a-ghost'])
933
self.assertEqual((set(), {'a-ghost'}), search.next_with_ghosts())
937
search = graph._make_breadth_first_searcher([b'a-ghost'])
938
self.assertEqual((set(), {b'a-ghost'}), search.next_with_ghosts())
934
939
self.assertRaises(StopIteration, search.next_with_ghosts)
935
940
# next includes them
936
search = graph._make_breadth_first_searcher(['a-ghost'])
937
self.assertEqual({'a-ghost'}, next(search))
941
search = graph._make_breadth_first_searcher([b'a-ghost'])
942
self.assertEqual({b'a-ghost'}, next(search))
938
943
self.assertRaises(StopIteration, next, search)
940
945
def test_breadth_first_search_deep_ghosts(self):
941
946
graph = self.make_graph({
943
'present': ['child', 'ghost'],
947
b'head': [b'present'],
948
b'present': [b'child', b'ghost'],
946
951
# with_ghosts reports the ghosts
947
search = graph._make_breadth_first_searcher(['head'])
948
self.assertEqual(({'head'}, set()), search.next_with_ghosts())
949
self.assertEqual(({'present'}, set()), search.next_with_ghosts())
950
self.assertEqual(({'child'}, {'ghost'}),
951
search.next_with_ghosts())
952
search = graph._make_breadth_first_searcher([b'head'])
953
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
954
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
955
self.assertEqual(({b'child'}, {b'ghost'}),
956
search.next_with_ghosts())
952
957
self.assertRaises(StopIteration, search.next_with_ghosts)
953
958
# next includes them
954
search = graph._make_breadth_first_searcher(['head'])
955
self.assertEqual({'head'}, next(search))
956
self.assertEqual({'present'}, next(search))
957
self.assertEqual({'child', 'ghost'},
959
search = graph._make_breadth_first_searcher([b'head'])
960
self.assertEqual({b'head'}, next(search))
961
self.assertEqual({b'present'}, next(search))
962
self.assertEqual({b'child', b'ghost'},
959
964
self.assertRaises(StopIteration, next, search)
961
966
def test_breadth_first_search_change_next_to_next_with_ghosts(self):
962
967
# To make the API robust, we allow calling both next() and
963
968
# next_with_ghosts() on the same searcher.
964
969
graph = self.make_graph({
966
'present': ['child', 'ghost'],
970
b'head': [b'present'],
971
b'present': [b'child', b'ghost'],
969
974
# start with next_with_ghosts
970
search = graph._make_breadth_first_searcher(['head'])
971
self.assertEqual(({'head'}, set()), search.next_with_ghosts())
972
self.assertEqual({'present'}, next(search))
973
self.assertEqual(({'child'}, {'ghost'}),
974
search.next_with_ghosts())
975
search = graph._make_breadth_first_searcher([b'head'])
976
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
977
self.assertEqual({b'present'}, next(search))
978
self.assertEqual(({b'child'}, {b'ghost'}),
979
search.next_with_ghosts())
975
980
self.assertRaises(StopIteration, next, search)
976
981
# start with next
977
search = graph._make_breadth_first_searcher(['head'])
978
self.assertEqual({'head'}, next(search))
979
self.assertEqual(({'present'}, set()), search.next_with_ghosts())
980
self.assertEqual({'child', 'ghost'},
982
search = graph._make_breadth_first_searcher([b'head'])
983
self.assertEqual({b'head'}, next(search))
984
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
985
self.assertEqual({b'child', b'ghost'},
982
987
self.assertRaises(StopIteration, search.next_with_ghosts)
984
989
def test_breadth_first_change_search(self):
985
990
# Changing the search should work with both next and next_with_ghosts.
986
991
graph = self.make_graph({
988
'present': ['stopped'],
989
'other': ['other_2'],
992
b'head': [b'present'],
993
b'present': [b'stopped'],
994
b'other': [b'other_2'],
992
search = graph._make_breadth_first_searcher(['head'])
993
self.assertEqual(({'head'}, set()), search.next_with_ghosts())
994
self.assertEqual(({'present'}, set()), search.next_with_ghosts())
995
self.assertEqual({'present'},
996
search.stop_searching_any(['present']))
997
self.assertEqual(({'other'}, {'other_ghost'}),
998
search.start_searching(['other', 'other_ghost']))
999
self.assertEqual(({'other_2'}, set()), search.next_with_ghosts())
997
search = graph._make_breadth_first_searcher([b'head'])
998
self.assertEqual(({b'head'}, set()), search.next_with_ghosts())
999
self.assertEqual(({b'present'}, set()), search.next_with_ghosts())
1000
self.assertEqual({b'present'},
1001
search.stop_searching_any([b'present']))
1002
self.assertEqual(({b'other'}, {b'other_ghost'}),
1003
search.start_searching([b'other', b'other_ghost']))
1004
self.assertEqual(({b'other_2'}, set()), search.next_with_ghosts())
1000
1005
self.assertRaises(StopIteration, search.next_with_ghosts)
1001
1006
# next includes them
1002
search = graph._make_breadth_first_searcher(['head'])
1003
self.assertEqual({'head'}, next(search))
1004
self.assertEqual({'present'}, next(search))
1005
self.assertEqual({'present'},
1006
search.stop_searching_any(['present']))
1007
search.start_searching(['other', 'other_ghost'])
1008
self.assertEqual({'other_2'}, next(search))
1007
search = graph._make_breadth_first_searcher([b'head'])
1008
self.assertEqual({b'head'}, next(search))
1009
self.assertEqual({b'present'}, next(search))
1010
self.assertEqual({b'present'},
1011
search.stop_searching_any([b'present']))
1012
search.start_searching([b'other', b'other_ghost'])
1013
self.assertEqual({b'other_2'}, next(search))
1009
1014
self.assertRaises(StopIteration, next, search)
1011
1016
def assertSeenAndResult(self, instructions, search, next):
1036
1041
def test_breadth_first_get_result_excludes_current_pending(self):
1037
1042
graph = self.make_graph({
1039
'child': [NULL_REVISION],
1043
b'head': [b'child'],
1044
b'child': [NULL_REVISION],
1040
1045
NULL_REVISION: [],
1042
search = graph._make_breadth_first_searcher(['head'])
1047
search = graph._make_breadth_first_searcher([b'head'])
1043
1048
# At the start, nothing has been seen, to its all excluded:
1044
1049
state = search.get_state()
1045
self.assertEqual(({'head'}, {'head'}, set()),
1050
self.assertEqual(({b'head'}, {b'head'}, set()),
1047
1052
self.assertEqual(set(), search.seen)
1050
({'head'}, ({'head'}, {'child'}, 1),
1051
['head'], None, None),
1052
({'head', 'child'}, ({'head'}, {NULL_REVISION}, 2),
1053
['head', 'child'], None, None),
1054
({'head', 'child', NULL_REVISION}, ({'head'}, set(), 3),
1055
['head', 'child', NULL_REVISION], None, None),
1055
({b'head'}, ({b'head'}, {b'child'}, 1),
1056
[b'head'], None, None),
1057
({b'head', b'child'}, ({b'head'}, {NULL_REVISION}, 2),
1058
[b'head', b'child'], None, None),
1059
({b'head', b'child', NULL_REVISION}, ({b'head'}, set(), 3),
1060
[b'head', b'child', NULL_REVISION], None, None),
1057
1062
self.assertSeenAndResult(expected, search, search.__next__)
1058
1063
# using next_with_ghosts:
1059
search = graph._make_breadth_first_searcher(['head'])
1064
search = graph._make_breadth_first_searcher([b'head'])
1060
1065
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1062
1067
def test_breadth_first_get_result_starts_stops(self):
1063
1068
graph = self.make_graph({
1065
'child':[NULL_REVISION],
1066
'otherhead':['otherchild'],
1067
'otherchild':['excluded'],
1068
'excluded':[NULL_REVISION],
1069
b'head': [b'child'],
1070
b'child': [NULL_REVISION],
1071
b'otherhead': [b'otherchild'],
1072
b'otherchild': [b'excluded'],
1073
b'excluded': [NULL_REVISION],
1071
1076
search = graph._make_breadth_first_searcher([])
1072
1077
# Starting with nothing and adding a search works:
1073
search.start_searching(['head'])
1078
search.start_searching([b'head'])
1074
1079
# head has been seen:
1075
1080
state = search.get_state()
1076
self.assertEqual(({'head'}, {'child'}, {'head'}),
1078
self.assertEqual({'head'}, search.seen)
1081
self.assertEqual(({b'head'}, {b'child'}, {b'head'}),
1083
self.assertEqual({b'head'}, search.seen)
1081
1086
# stop at child, and start a new search at otherhead:
1082
1087
# - otherhead counts as seen immediately when start_searching is
1084
({'head', 'child', 'otherhead'},
1085
({'head', 'otherhead'}, {'child', 'otherchild'}, 2),
1086
['head', 'otherhead'], ['otherhead'], ['child']),
1087
({'head', 'child', 'otherhead', 'otherchild'},
1088
({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1089
['head', 'otherhead', 'otherchild'], None, None),
1089
({b'head', b'child', b'otherhead'},
1090
({b'head', b'otherhead'}, {b'child', b'otherchild'}, 2),
1091
[b'head', b'otherhead'], [b'otherhead'], [b'child']),
1092
({b'head', b'child', b'otherhead', b'otherchild'},
1093
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1094
[b'head', b'otherhead', b'otherchild'], None, None),
1090
1095
# stop searching excluded now
1091
({'head', 'child', 'otherhead', 'otherchild', 'excluded'},
1092
({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1093
['head', 'otherhead', 'otherchild'], None, ['excluded']),
1096
({b'head', b'child', b'otherhead', b'otherchild', b'excluded'},
1097
({b'head', b'otherhead'}, {b'child', b'excluded'}, 3),
1098
[b'head', b'otherhead', b'otherchild'], None, [b'excluded']),
1095
1100
self.assertSeenAndResult(expected, search, search.__next__)
1096
1101
# using next_with_ghosts:
1097
1102
search = graph._make_breadth_first_searcher([])
1098
search.start_searching(['head'])
1103
search.start_searching([b'head'])
1099
1104
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1101
1106
def test_breadth_first_stop_searching_not_queried(self):
1102
# A client should be able to say 'stop node X' even if X has not been
1107
# A client should be able to say b'stop node X' even if X has not been
1103
1108
# returned to the client.
1104
1109
graph = self.make_graph({
1105
'head': ['child', 'ghost1'],
1106
'child': [NULL_REVISION],
1110
b'head': [b'child', b'ghost1'],
1111
b'child': [NULL_REVISION],
1107
1112
NULL_REVISION: [],
1109
search = graph._make_breadth_first_searcher(['head'])
1114
search = graph._make_breadth_first_searcher([b'head'])
1111
1116
# NULL_REVISION and ghost1 have not been returned
1113
({'head'}, {'child', NULL_REVISION, 'ghost1'}, 1),
1114
['head'], None, [NULL_REVISION, 'ghost1']),
1118
({b'head'}, {b'child', NULL_REVISION, b'ghost1'}, 1),
1119
[b'head'], None, [NULL_REVISION, b'ghost1']),
1115
1120
# ghost1 has been returned, NULL_REVISION is to be returned in the
1116
1121
# next iteration.
1117
({'head', 'child', 'ghost1'},
1118
({'head'}, {'ghost1', NULL_REVISION}, 2),
1119
['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1122
({b'head', b'child', b'ghost1'},
1123
({b'head'}, {b'ghost1', NULL_REVISION}, 2),
1124
[b'head', b'child'], None, [NULL_REVISION, b'ghost1']),
1121
1126
self.assertSeenAndResult(expected, search, search.__next__)
1122
1127
# using next_with_ghosts:
1123
search = graph._make_breadth_first_searcher(['head'])
1128
search = graph._make_breadth_first_searcher([b'head'])
1124
1129
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1126
1131
def test_breadth_first_stop_searching_late(self):
1127
# A client should be able to say 'stop node X' and have it excluded
1132
# A client should be able to say b'stop node X' and have it excluded
1128
1133
# from the result even if X was seen in an older iteration of the
1130
1135
graph = self.make_graph({
1132
'middle': ['child'],
1133
'child': [NULL_REVISION],
1136
b'head': [b'middle'],
1137
b'middle': [b'child'],
1138
b'child': [NULL_REVISION],
1134
1139
NULL_REVISION: [],
1136
search = graph._make_breadth_first_searcher(['head'])
1141
search = graph._make_breadth_first_searcher([b'head'])
1138
({'head'}, ({'head'}, {'middle'}, 1),
1139
['head'], None, None),
1140
({'head', 'middle'}, ({'head'}, {'child'}, 2),
1141
['head', 'middle'], None, None),
1142
# 'middle' came from the previous iteration, but we don't stop
1143
({b'head'}, ({b'head'}, {b'middle'}, 1),
1144
[b'head'], None, None),
1145
({b'head', b'middle'}, ({b'head'}, {b'child'}, 2),
1146
[b'head', b'middle'], None, None),
1147
# b'middle' came from the previous iteration, but we don't stop
1143
1148
# searching it until *after* advancing the searcher.
1144
({'head', 'middle', 'child'},
1145
({'head'}, {'middle', 'child'}, 1),
1146
['head'], None, ['middle', 'child']),
1149
({b'head', b'middle', b'child'},
1150
({b'head'}, {b'middle', b'child'}, 1),
1151
[b'head'], None, [b'middle', b'child']),
1148
1153
self.assertSeenAndResult(expected, search, search.__next__)
1149
1154
# using next_with_ghosts:
1150
search = graph._make_breadth_first_searcher(['head'])
1155
search = graph._make_breadth_first_searcher([b'head'])
1151
1156
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1153
1158
def test_breadth_first_get_result_ghosts_are_excluded(self):
1154
1159
graph = self.make_graph({
1155
'head': ['child', 'ghost'],
1156
'child': [NULL_REVISION],
1160
b'head': [b'child', b'ghost'],
1161
b'child': [NULL_REVISION],
1157
1162
NULL_REVISION: [],
1159
search = graph._make_breadth_first_searcher(['head'])
1164
search = graph._make_breadth_first_searcher([b'head'])
1163
({'head'}, {'ghost', 'child'}, 1),
1164
['head'], None, None),
1165
({'head', 'child', 'ghost'},
1166
({'head'}, {NULL_REVISION, 'ghost'}, 2),
1167
['head', 'child'], None, None),
1168
({b'head'}, {b'ghost', b'child'}, 1),
1169
[b'head'], None, None),
1170
({b'head', b'child', b'ghost'},
1171
({b'head'}, {NULL_REVISION, b'ghost'}, 2),
1172
[b'head', b'child'], None, None),
1169
1174
self.assertSeenAndResult(expected, search, search.__next__)
1170
1175
# using next_with_ghosts:
1171
search = graph._make_breadth_first_searcher(['head'])
1176
search = graph._make_breadth_first_searcher([b'head'])
1172
1177
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1174
1179
def test_breadth_first_get_result_starting_a_ghost_ghost_is_excluded(self):
1175
1180
graph = self.make_graph({
1177
'child': [NULL_REVISION],
1181
b'head': [b'child'],
1182
b'child': [NULL_REVISION],
1178
1183
NULL_REVISION: [],
1180
search = graph._make_breadth_first_searcher(['head'])
1185
search = graph._make_breadth_first_searcher([b'head'])
1184
({'head', 'ghost'}, {'child', 'ghost'}, 1),
1185
['head'], ['ghost'], None),
1186
({'head', 'child', 'ghost'},
1187
({'head', 'ghost'}, {NULL_REVISION, 'ghost'}, 2),
1188
['head', 'child'], None, None),
1188
({b'head', b'ghost'},
1189
({b'head', b'ghost'}, {b'child', b'ghost'}, 1),
1190
[b'head'], [b'ghost'], None),
1191
({b'head', b'child', b'ghost'},
1192
({b'head', b'ghost'}, {NULL_REVISION, b'ghost'}, 2),
1193
[b'head', b'child'], None, None),
1190
1195
self.assertSeenAndResult(expected, search, search.__next__)
1191
1196
# using next_with_ghosts:
1192
search = graph._make_breadth_first_searcher(['head'])
1197
search = graph._make_breadth_first_searcher([b'head'])
1193
1198
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1195
1200
def test_breadth_first_revision_count_includes_NULL_REVISION(self):
1196
1201
graph = self.make_graph({
1197
'head': [NULL_REVISION],
1202
b'head': [NULL_REVISION],
1198
1203
NULL_REVISION: [],
1200
search = graph._make_breadth_first_searcher(['head'])
1205
search = graph._make_breadth_first_searcher([b'head'])
1204
({'head'}, {NULL_REVISION}, 1),
1205
['head'], None, None),
1206
({'head', NULL_REVISION},
1207
({'head'}, set([]), 2),
1208
['head', NULL_REVISION], None, None),
1209
({b'head'}, {NULL_REVISION}, 1),
1210
[b'head'], None, None),
1211
({b'head', NULL_REVISION},
1212
({b'head'}, set([]), 2),
1213
[b'head', NULL_REVISION], None, None),
1210
1215
self.assertSeenAndResult(expected, search, search.__next__)
1211
1216
# using next_with_ghosts:
1212
search = graph._make_breadth_first_searcher(['head'])
1217
search = graph._make_breadth_first_searcher([b'head'])
1213
1218
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1215
1220
def test_breadth_first_search_get_result_after_StopIteration(self):
1216
1221
# StopIteration should not invalid anything..
1217
1222
graph = self.make_graph({
1218
'head': [NULL_REVISION],
1223
b'head': [NULL_REVISION],
1219
1224
NULL_REVISION: [],
1221
search = graph._make_breadth_first_searcher(['head'])
1226
search = graph._make_breadth_first_searcher([b'head'])
1225
({'head'}, {NULL_REVISION}, 1),
1226
['head'], None, None),
1227
({'head', 'ghost', NULL_REVISION},
1228
({'head', 'ghost'}, {'ghost'}, 2),
1229
['head', NULL_REVISION], ['ghost'], None),
1230
({b'head'}, {NULL_REVISION}, 1),
1231
[b'head'], None, None),
1232
({b'head', b'ghost', NULL_REVISION},
1233
({b'head', b'ghost'}, {b'ghost'}, 2),
1234
[b'head', NULL_REVISION], [b'ghost'], None),
1231
1236
self.assertSeenAndResult(expected, search, search.__next__)
1232
1237
self.assertRaises(StopIteration, next, search)
1233
self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
1238
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1234
1239
state = search.get_state()
1235
1240
self.assertEqual(
1236
({'ghost', 'head'}, {'ghost'},
1237
{'head', NULL_REVISION}),
1241
({b'ghost', b'head'}, {b'ghost'},
1242
{b'head', NULL_REVISION}),
1239
1244
# using next_with_ghosts:
1240
search = graph._make_breadth_first_searcher(['head'])
1245
search = graph._make_breadth_first_searcher([b'head'])
1241
1246
self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1242
1247
self.assertRaises(StopIteration, next, search)
1243
self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
1248
self.assertEqual({b'head', b'ghost', NULL_REVISION}, search.seen)
1244
1249
state = search.get_state()
1245
1250
self.assertEqual(
1246
({'ghost', 'head'}, {'ghost'},
1247
{'head', NULL_REVISION}),
1251
({b'ghost', b'head'}, {b'ghost'},
1252
{b'head', NULL_REVISION}),
1257
1262
def test_empty_set(self):
1258
1263
graph = self.make_graph(ancestry_1)
1259
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
1260
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
1261
self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
1264
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev1'])
1265
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev2b'])
1266
self.assertFindUniqueAncestors(graph, [], b'rev3', [b'rev1', b'rev3'])
1263
1268
def test_single_node(self):
1264
1269
graph = self.make_graph(ancestry_1)
1265
self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
1266
self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
1267
self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
1270
self.assertFindUniqueAncestors(graph, [b'rev2a'], b'rev2a', [b'rev1'])
1271
self.assertFindUniqueAncestors(graph, [b'rev2b'], b'rev2b', [b'rev1'])
1272
self.assertFindUniqueAncestors(graph, [b'rev3'], b'rev3', [b'rev2a'])
1269
1274
def test_minimal_ancestry(self):
1270
1275
graph = self.make_breaking_graph(extended_history_shortcut,
1271
[NULL_REVISION, 'a', 'b'])
1272
self.assertFindUniqueAncestors(graph, ['e'], 'e', ['d'])
1276
[NULL_REVISION, b'a', b'b'])
1277
self.assertFindUniqueAncestors(graph, [b'e'], b'e', [b'd'])
1274
1279
graph = self.make_breaking_graph(extended_history_shortcut,
1276
self.assertFindUniqueAncestors(graph, ['f'], 'f', ['a', 'd'])
1281
self.assertFindUniqueAncestors(graph, [b'f'], b'f', [b'a', b'd'])
1278
1283
graph = self.make_breaking_graph(complex_shortcut,
1280
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['i'])
1281
self.assertFindUniqueAncestors(graph, ['e', 'g', 'i'], 'i', ['h'])
1282
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['g'])
1283
self.assertFindUniqueAncestors(graph, ['h'], 'h', ['j'])
1285
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'i'])
1286
self.assertFindUniqueAncestors(graph, [b'e', b'g', b'i'], b'i', [b'h'])
1287
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'g'])
1288
self.assertFindUniqueAncestors(graph, [b'h'], b'h', [b'j'])
1285
1290
def test_in_ancestry(self):
1286
1291
graph = self.make_graph(ancestry_1)
1287
self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
1288
self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
1292
self.assertFindUniqueAncestors(graph, [], b'rev1', [b'rev3'])
1293
self.assertFindUniqueAncestors(graph, [], b'rev2b', [b'rev4'])
1290
1295
def test_multiple_revisions(self):
1291
1296
graph = self.make_graph(ancestry_1)
1292
1297
self.assertFindUniqueAncestors(graph,
1293
['rev4'], 'rev4', ['rev3', 'rev2b'])
1298
[b'rev4'], b'rev4', [b'rev3', b'rev2b'])
1294
1299
self.assertFindUniqueAncestors(graph,
1295
['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
1300
[b'rev2a', b'rev3', b'rev4'], b'rev4', [b'rev2b'])
1297
1302
def test_complex_shortcut(self):
1298
1303
graph = self.make_graph(complex_shortcut)
1299
1304
self.assertFindUniqueAncestors(graph,
1300
['h', 'n'], 'n', ['m'])
1305
[b'h', b'n'], b'n', [b'm'])
1301
1306
self.assertFindUniqueAncestors(graph,
1302
['e', 'i', 'm'], 'm', ['n'])
1307
[b'e', b'i', b'm'], b'm', [b'n'])
1304
1309
def test_complex_shortcut2(self):
1305
1310
graph = self.make_graph(complex_shortcut2)
1306
1311
self.assertFindUniqueAncestors(graph,
1307
['j', 'u'], 'u', ['t'])
1312
[b'j', b'u'], b'u', [b't'])
1308
1313
self.assertFindUniqueAncestors(graph,
1314
[b't'], b't', [b'u'])
1311
1316
def test_multiple_interesting_unique(self):
1312
1317
graph = self.make_graph(multiple_interesting_unique)
1313
1318
self.assertFindUniqueAncestors(graph,
1314
['j', 'y'], 'y', ['z'])
1319
[b'j', b'y'], b'y', [b'z'])
1315
1320
self.assertFindUniqueAncestors(graph,
1316
['p', 'z'], 'z', ['y'])
1321
[b'p', b'z'], b'z', [b'y'])
1318
1323
def test_racing_shortcuts(self):
1319
1324
graph = self.make_graph(racing_shortcuts)
1320
1325
self.assertFindUniqueAncestors(graph,
1321
['p', 'q', 'z'], 'z', ['y'])
1326
[b'p', b'q', b'z'], b'z', [b'y'])
1322
1327
self.assertFindUniqueAncestors(graph,
1323
['h', 'i', 'j', 'y'], 'j', ['z'])
1328
[b'h', b'i', b'j', b'y'], b'j', [b'z'])
1326
1331
class TestGraphFindDistanceToNull(TestGraphBase):
1334
1339
def test_nothing_known(self):
1335
1340
graph = self.make_graph(ancestry_1)
1336
1341
self.assertFindDistance(0, graph, NULL_REVISION, [])
1337
self.assertFindDistance(1, graph, 'rev1', [])
1338
self.assertFindDistance(2, graph, 'rev2a', [])
1339
self.assertFindDistance(2, graph, 'rev2b', [])
1340
self.assertFindDistance(3, graph, 'rev3', [])
1341
self.assertFindDistance(4, graph, 'rev4', [])
1342
self.assertFindDistance(1, graph, b'rev1', [])
1343
self.assertFindDistance(2, graph, b'rev2a', [])
1344
self.assertFindDistance(2, graph, b'rev2b', [])
1345
self.assertFindDistance(3, graph, b'rev3', [])
1346
self.assertFindDistance(4, graph, b'rev4', [])
1343
1348
def test_rev_is_ghost(self):
1344
1349
graph = self.make_graph(ancestry_1)
1345
1350
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1346
graph.find_distance_to_null, 'rev_missing', [])
1347
self.assertEqual('rev_missing', e.revision_id)
1348
self.assertEqual('rev_missing', e.ghost_revision_id)
1351
graph.find_distance_to_null, b'rev_missing', [])
1352
self.assertEqual(b'rev_missing', e.revision_id)
1353
self.assertEqual(b'rev_missing', e.ghost_revision_id)
1350
1355
def test_ancestor_is_ghost(self):
1351
graph = self.make_graph({'rev':['parent']})
1356
graph = self.make_graph({b'rev': [b'parent']})
1352
1357
e = self.assertRaises(errors.GhostRevisionsHaveNoRevno,
1353
graph.find_distance_to_null, 'rev', [])
1354
self.assertEqual('rev', e.revision_id)
1355
self.assertEqual('parent', e.ghost_revision_id)
1358
graph.find_distance_to_null, b'rev', [])
1359
self.assertEqual(b'rev', e.revision_id)
1360
self.assertEqual(b'parent', e.ghost_revision_id)
1357
1362
def test_known_in_ancestry(self):
1358
1363
graph = self.make_graph(ancestry_1)
1359
self.assertFindDistance(2, graph, 'rev2a', [('rev1', 1)])
1360
self.assertFindDistance(3, graph, 'rev3', [('rev2a', 2)])
1364
self.assertFindDistance(2, graph, b'rev2a', [(b'rev1', 1)])
1365
self.assertFindDistance(3, graph, b'rev3', [(b'rev2a', 2)])
1362
1367
def test_known_in_ancestry_limits(self):
1363
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1364
self.assertFindDistance(4, graph, 'rev4', [('rev3', 3)])
1368
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1369
self.assertFindDistance(4, graph, b'rev4', [(b'rev3', 3)])
1366
1371
def test_target_is_ancestor(self):
1367
1372
graph = self.make_graph(ancestry_1)
1368
self.assertFindDistance(2, graph, 'rev2a', [('rev3', 3)])
1373
self.assertFindDistance(2, graph, b'rev2a', [(b'rev3', 3)])
1370
1375
def test_target_is_ancestor_limits(self):
1371
1376
"""We shouldn't search all history if we run into ourselves"""
1372
graph = self.make_breaking_graph(ancestry_1, ['rev1'])
1373
self.assertFindDistance(3, graph, 'rev3', [('rev4', 4)])
1377
graph = self.make_breaking_graph(ancestry_1, [b'rev1'])
1378
self.assertFindDistance(3, graph, b'rev3', [(b'rev4', 4)])
1375
1380
def test_target_parallel_to_known_limits(self):
1376
1381
# Even though the known revision isn't part of the other ancestry, they
1377
1382
# eventually converge
1378
graph = self.make_breaking_graph(with_tail, ['a'])
1379
self.assertFindDistance(6, graph, 'f', [('g', 6)])
1380
self.assertFindDistance(7, graph, 'h', [('g', 6)])
1381
self.assertFindDistance(8, graph, 'i', [('g', 6)])
1382
self.assertFindDistance(6, graph, 'g', [('i', 8)])
1383
graph = self.make_breaking_graph(with_tail, [b'a'])
1384
self.assertFindDistance(6, graph, b'f', [(b'g', 6)])
1385
self.assertFindDistance(7, graph, b'h', [(b'g', 6)])
1386
self.assertFindDistance(8, graph, b'i', [(b'g', 6)])
1387
self.assertFindDistance(6, graph, b'g', [(b'i', 8)])
1385
1390
class TestFindMergeOrder(TestGraphBase):
1390
1395
def test_parents(self):
1391
1396
graph = self.make_graph(ancestry_1)
1392
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1394
self.assertMergeOrder(['rev3', 'rev2b'], graph, 'rev4',
1397
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1398
[b'rev3', b'rev2b'])
1399
self.assertMergeOrder([b'rev3', b'rev2b'], graph, b'rev4',
1400
[b'rev2b', b'rev3'])
1397
1402
def test_ancestors(self):
1398
1403
graph = self.make_graph(ancestry_1)
1399
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1401
self.assertMergeOrder(['rev1', 'rev2b'], graph, 'rev4',
1404
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1405
[b'rev1', b'rev2b'])
1406
self.assertMergeOrder([b'rev1', b'rev2b'], graph, b'rev4',
1407
[b'rev2b', b'rev1'])
1404
1409
def test_shortcut_one_ancestor(self):
1405
1410
# When we have enough info, we can stop searching
1406
graph = self.make_breaking_graph(ancestry_1, ['rev3', 'rev2b', 'rev4'])
1411
graph = self.make_breaking_graph(
1412
ancestry_1, [b'rev3', b'rev2b', b'rev4'])
1407
1413
# Single ancestors shortcut right away
1408
self.assertMergeOrder(['rev3'], graph, 'rev4', ['rev3'])
1414
self.assertMergeOrder([b'rev3'], graph, b'rev4', [b'rev3'])
1410
1416
def test_shortcut_after_one_ancestor(self):
1411
graph = self.make_breaking_graph(ancestry_1, ['rev2a', 'rev2b'])
1412
self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1417
graph = self.make_breaking_graph(ancestry_1, [b'rev2a', b'rev2b'])
1418
self.assertMergeOrder([b'rev3', b'rev1'], graph,
1419
b'rev4', [b'rev1', b'rev3'])
1415
1422
class TestFindDescendants(TestGraphBase):
1417
1424
def test_find_descendants_rev1_rev3(self):
1418
1425
graph = self.make_graph(ancestry_1)
1419
descendants = graph.find_descendants('rev1', 'rev3')
1420
self.assertEqual({'rev1', 'rev2a', 'rev3'}, descendants)
1426
descendants = graph.find_descendants(b'rev1', b'rev3')
1427
self.assertEqual({b'rev1', b'rev2a', b'rev3'}, descendants)
1422
1429
def test_find_descendants_rev1_rev4(self):
1423
1430
graph = self.make_graph(ancestry_1)
1424
descendants = graph.find_descendants('rev1', 'rev4')
1425
self.assertEqual({'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'},
1431
descendants = graph.find_descendants(b'rev1', b'rev4')
1432
self.assertEqual({b'rev1', b'rev2a', b'rev2b', b'rev3', b'rev4'},
1428
1435
def test_find_descendants_rev2a_rev4(self):
1429
1436
graph = self.make_graph(ancestry_1)
1430
descendants = graph.find_descendants('rev2a', 'rev4')
1431
self.assertEqual({'rev2a', 'rev3', 'rev4'}, descendants)
1437
descendants = graph.find_descendants(b'rev2a', b'rev4')
1438
self.assertEqual({b'rev2a', b'rev3', b'rev4'}, descendants)
1433
1441
class TestFindLefthandMerger(TestGraphBase):
1478
1486
def setUp(self):
1479
1487
super(TestCachingParentsProvider, self).setUp()
1480
dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1488
dict_pp = _mod_graph.DictParentsProvider({b'a': (b'b',)})
1481
1489
self.inst_pp = InstrumentedParentsProvider(dict_pp)
1482
1490
self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1484
1492
def test_get_parent_map(self):
1485
1493
"""Requesting the same revision should be returned from cache"""
1486
1494
self.assertEqual({}, self.caching_pp._cache)
1487
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1488
self.assertEqual(['a'], self.inst_pp.calls)
1489
self.assertEqual({'a':('b',)}, self.caching_pp.get_parent_map(['a']))
1496
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1497
self.assertEqual([b'a'], self.inst_pp.calls)
1499
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1490
1500
# No new call, as it should have been returned from the cache
1491
self.assertEqual(['a'], self.inst_pp.calls)
1492
self.assertEqual({'a':('b',)}, self.caching_pp._cache)
1501
self.assertEqual([b'a'], self.inst_pp.calls)
1502
self.assertEqual({b'a': (b'b',)}, self.caching_pp._cache)
1494
1504
def test_get_parent_map_not_present(self):
1495
1505
"""The cache should also track when a revision doesn't exist"""
1496
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1497
self.assertEqual(['b'], self.inst_pp.calls)
1498
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1506
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1507
self.assertEqual([b'b'], self.inst_pp.calls)
1508
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1500
self.assertEqual(['b'], self.inst_pp.calls)
1510
self.assertEqual([b'b'], self.inst_pp.calls)
1502
1512
def test_get_parent_map_mixed(self):
1503
1513
"""Anything that can be returned from cache, should be"""
1504
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1505
self.assertEqual(['b'], self.inst_pp.calls)
1506
self.assertEqual({'a':('b',)},
1507
self.caching_pp.get_parent_map(['a', 'b']))
1508
self.assertEqual(['b', 'a'], self.inst_pp.calls)
1514
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1515
self.assertEqual([b'b'], self.inst_pp.calls)
1516
self.assertEqual({b'a': (b'b',)},
1517
self.caching_pp.get_parent_map([b'a', b'b']))
1518
self.assertEqual([b'b', b'a'], self.inst_pp.calls)
1510
1520
def test_get_parent_map_repeated(self):
1511
1521
"""Asking for the same parent 2x will only forward 1 request."""
1512
self.assertEqual({'a':('b',)},
1513
self.caching_pp.get_parent_map(['b', 'a', 'b']))
1522
self.assertEqual({b'a': (b'b',)},
1523
self.caching_pp.get_parent_map([b'b', b'a', b'b']))
1514
1524
# Use sorted because we don't care about the order, just that each is
1515
1525
# only present 1 time.
1516
self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
1526
self.assertEqual([b'a', b'b'], sorted(self.inst_pp.calls))
1518
1528
def test_note_missing_key(self):
1519
1529
"""After noting that a key is missing it is cached."""
1520
self.caching_pp.note_missing_key('b')
1521
self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1530
self.caching_pp.note_missing_key(b'b')
1531
self.assertEqual({}, self.caching_pp.get_parent_map([b'b']))
1522
1532
self.assertEqual([], self.inst_pp.calls)
1523
self.assertEqual({'b'}, self.caching_pp.missing_keys)
1533
self.assertEqual({b'b'}, self.caching_pp.missing_keys)
1525
1535
def test_get_cached_parent_map(self):
1526
self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
1536
self.assertEqual({}, self.caching_pp.get_cached_parent_map([b'a']))
1527
1537
self.assertEqual([], self.inst_pp.calls)
1528
self.assertEqual({'a': ('b',)}, self.caching_pp.get_parent_map(['a']))
1529
self.assertEqual(['a'], self.inst_pp.calls)
1530
self.assertEqual({'a': ('b',)},
1531
self.caching_pp.get_cached_parent_map(['a']))
1539
{b'a': (b'b',)}, self.caching_pp.get_parent_map([b'a']))
1540
self.assertEqual([b'a'], self.inst_pp.calls)
1541
self.assertEqual({b'a': (b'b',)},
1542
self.caching_pp.get_cached_parent_map([b'a']))
1534
1545
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1652
d = {('D',): [('B',), ('C',)], ('C',):[('A',)],
1653
('B',): [('A',)], ('A',): []}
1663
d = {(b'D',): [(b'B',), (b'C',)], (b'C',): [(b'A',)],
1664
(b'B',): [(b'A',)], (b'A',): []}
1654
1665
g = _mod_graph.Graph(_mod_graph.DictParentsProvider(d))
1655
1666
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1656
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'A'])))
1657
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'B'])))
1658
self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1659
self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1667
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'A'])))
1668
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'B'])))
1669
self.assertEqual([b'D'], sorted(graph_thunk.heads([b'D', b'C'])))
1670
self.assertEqual([b'B', b'C'], sorted(graph_thunk.heads([b'B', b'C'])))
1661
1672
def test_add_node(self):
1662
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1673
d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1663
1674
g = _mod_graph.KnownGraph(d)
1664
1675
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1665
graph_thunk.add_node("D", ["A", "C"])
1666
self.assertEqual(['B', 'D'],
1667
sorted(graph_thunk.heads(['D', 'B', 'A'])))
1676
graph_thunk.add_node(b"D", [b"A", b"C"])
1677
self.assertEqual([b'B', b'D'],
1678
sorted(graph_thunk.heads([b'D', b'B', b'A'])))
1669
1680
def test_merge_sort(self):
1670
d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
1681
d = {(b'C',): [(b'A',)], (b'B',): [(b'A',)], (b'A',): []}
1671
1682
g = _mod_graph.KnownGraph(d)
1672
1683
graph_thunk = _mod_graph.GraphThunkIdsToKeys(g)
1673
graph_thunk.add_node("D", ["A", "C"])
1674
self.assertEqual([('C', 0, (2,), False), ('A', 0, (1,), True)],
1675
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1676
for n in graph_thunk.merge_sort('C')])
1684
graph_thunk.add_node(b"D", [b"A", b"C"])
1685
self.assertEqual([(b'C', 0, (2,), False), (b'A', 0, (1,), True)],
1686
[(n.key, n.merge_depth, n.revno, n.end_of_merge)
1687
for n in graph_thunk.merge_sort(b'C')])
1679
1690
class TestStackedParentsProvider(tests.TestCase):
1689
1700
return SharedInstrumentedParentsProvider(pp, self.calls, info)
1691
1702
def test_stacked_parents_provider(self):
1692
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
1693
parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
1703
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev3']})
1704
parents2 = _mod_graph.DictParentsProvider({b'rev1': [b'rev4']})
1694
1705
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1695
self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
1696
stacked.get_parent_map(['rev1', 'rev2']))
1697
self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
1698
stacked.get_parent_map(['rev2', 'rev1']))
1699
self.assertEqual({'rev2':['rev3']},
1700
stacked.get_parent_map(['rev2', 'rev2']))
1701
self.assertEqual({'rev1':['rev4']},
1702
stacked.get_parent_map(['rev1', 'rev1']))
1706
self.assertEqual({b'rev1': [b'rev4'], b'rev2': [b'rev3']},
1707
stacked.get_parent_map([b'rev1', b'rev2']))
1708
self.assertEqual({b'rev2': [b'rev3'], b'rev1': [b'rev4']},
1709
stacked.get_parent_map([b'rev2', b'rev1']))
1710
self.assertEqual({b'rev2': [b'rev3']},
1711
stacked.get_parent_map([b'rev2', b'rev2']))
1712
self.assertEqual({b'rev1': [b'rev4']},
1713
stacked.get_parent_map([b'rev1', b'rev1']))
1704
1715
def test_stacked_parents_provider_overlapping(self):
1705
1716
# rev2 is availible in both providers.
1709
parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1710
parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
1720
parents1 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1721
parents2 = _mod_graph.DictParentsProvider({b'rev2': [b'rev1']})
1711
1722
stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
1712
self.assertEqual({'rev2': ['rev1']},
1713
stacked.get_parent_map(['rev2']))
1723
self.assertEqual({b'rev2': [b'rev1']},
1724
stacked.get_parent_map([b'rev2']))
1715
1726
def test_handles_no_get_cached_parent_map(self):
1716
1727
# this shows that we both handle when a provider doesn't implement
1717
1728
# get_cached_parent_map
1718
pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
1729
pp1 = self.get_shared_provider(b'pp1', {b'rev2': (b'rev1',)},
1719
1730
has_cached=False)
1720
pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
1731
pp2 = self.get_shared_provider(b'pp2', {b'rev2': (b'rev1',)},
1721
1732
has_cached=True)
1722
1733
stacked = _mod_graph.StackedParentsProvider([pp1, pp2])
1723
self.assertEqual({'rev2': ('rev1',)}, stacked.get_parent_map(['rev2']))
1724
# No call on 'pp1' because it doesn't provide get_cached_parent_map
1725
self.assertEqual([('pp2', 'cached', ['rev2'])], self.calls)
1734
self.assertEqual({b'rev2': (b'rev1',)},
1735
stacked.get_parent_map([b'rev2']))
1736
# No call on b'pp1' because it doesn't provide get_cached_parent_map
1737
self.assertEqual([(b'pp2', 'cached', [b'rev2'])], self.calls)
1727
1739
def test_query_order(self):
1728
1740
# We should call get_cached_parent_map on all providers before we call
1729
1741
# get_parent_map. Further, we should track what entries we have found,
1730
1742
# and not re-try them.
1731
pp1 = self.get_shared_provider('pp1', {'a': ()}, has_cached=True)
1732
pp2 = self.get_shared_provider('pp2', {'c': ('b',)}, has_cached=False)
1733
pp3 = self.get_shared_provider('pp3', {'b': ('a',)}, has_cached=True)
1743
pp1 = self.get_shared_provider(b'pp1', {b'a': ()}, has_cached=True)
1744
pp2 = self.get_shared_provider(
1745
b'pp2', {b'c': (b'b',)}, has_cached=False)
1746
pp3 = self.get_shared_provider(
1747
b'pp3', {b'b': (b'a',)}, has_cached=True)
1734
1748
stacked = _mod_graph.StackedParentsProvider([pp1, pp2, pp3])
1735
self.assertEqual({'a': (), 'b': ('a',), 'c': ('b',)},
1736
stacked.get_parent_map(['a', 'b', 'c', 'd']))
1737
self.assertEqual([('pp1', 'cached', ['a', 'b', 'c', 'd']),
1749
self.assertEqual({b'a': (), b'b': (b'a',), b'c': (b'b',)},
1750
stacked.get_parent_map([b'a', b'b', b'c', b'd']))
1751
self.assertEqual([(b'pp1', 'cached', [b'a', b'b', b'c', b'd']),
1738
1752
# No call to pp2, because it doesn't have cached
1739
('pp3', 'cached', ['b', 'c', 'd']),
1740
('pp1', ['c', 'd']),
1741
('pp2', ['c', 'd']),
1753
(b'pp3', 'cached', [b'b', b'c', b'd']),
1754
(b'pp1', [b'c', b'd']),
1755
(b'pp2', [b'c', b'd']),
added
removed
breezy/tests/test_graph.py
