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