/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/tests/test_graph.py

  • Committer: Jelmer Vernooij
  • Date: 2017-05-30 22:17:31 UTC
  • mto: This revision was merged to the branch mainline in revision 6642.
  • Revision ID: jelmer@jelmer.uk-20170530221731-k3djl8mbldt2gmoi
Fix doc generation with sphinx.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/tests/test_graph.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007-2011 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
 
from bzrlib import (
 
17
from .. import (
18
18
    errors,
19
19
    graph as _mod_graph,
20
 
    symbol_versioning,
21
20
    tests,
22
21
    )
23
 
from bzrlib.revision import NULL_REVISION
24
 
from bzrlib.tests import TestCaseWithMemoryTransport
25
 
from bzrlib.symbol_versioning import deprecated_in
 
22
from ..revision import NULL_REVISION
 
23
from . import TestCaseWithMemoryTransport
26
24
 
27
25
 
28
26
# Ancestry 1:
426
424
    def __init__(self, parents_provider):
427
425
        self.calls = []
428
426
        self._real_parents_provider = parents_provider
 
427
        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
 
428
        if get_cached is not None:
 
429
            # Only expose the underlying 'get_cached_parent_map' function if
 
430
            # the wrapped provider has it.
 
431
            self.get_cached_parent_map = self._get_cached_parent_map
429
432
 
430
433
    def get_parent_map(self, nodes):
431
434
        self.calls.extend(nodes)
432
435
        return self._real_parents_provider.get_parent_map(nodes)
433
436
 
 
437
    def _get_cached_parent_map(self, nodes):
 
438
        self.calls.append(('cached', sorted(nodes)))
 
439
        return self._real_parents_provider.get_cached_parent_map(nodes)
 
440
 
 
441
 
 
442
class SharedInstrumentedParentsProvider(object):
 
443
 
 
444
    def __init__(self, parents_provider, calls, info):
 
445
        self.calls = calls
 
446
        self.info = info
 
447
        self._real_parents_provider = parents_provider
 
448
        get_cached = getattr(parents_provider, 'get_cached_parent_map', None)
 
449
        if get_cached is not None:
 
450
            # Only expose the underlying 'get_cached_parent_map' function if
 
451
            # the wrapped provider has it.
 
452
            self.get_cached_parent_map = self._get_cached_parent_map
 
453
 
 
454
    def get_parent_map(self, nodes):
 
455
        self.calls.append((self.info, sorted(nodes)))
 
456
        return self._real_parents_provider.get_parent_map(nodes)
 
457
 
 
458
    def _get_cached_parent_map(self, nodes):
 
459
        self.calls.append((self.info, 'cached', sorted(nodes)))
 
460
        return self._real_parents_provider.get_cached_parent_map(nodes)
 
461
 
434
462
 
435
463
class TestGraphBase(tests.TestCase):
436
464
 
500
528
        """
501
529
        graph = self.make_graph(ancestry_1)
502
530
        self.assertRaises(errors.InvalidRevisionId, graph.find_lca, None)
503
 
        self.assertEqual(set([NULL_REVISION]),
 
531
        self.assertEqual({NULL_REVISION},
504
532
                         graph.find_lca(NULL_REVISION, NULL_REVISION))
505
 
        self.assertEqual(set([NULL_REVISION]),
 
533
        self.assertEqual({NULL_REVISION},
506
534
                         graph.find_lca(NULL_REVISION, 'rev1'))
507
 
        self.assertEqual(set(['rev1']), graph.find_lca('rev1', 'rev1'))
508
 
        self.assertEqual(set(['rev1']), graph.find_lca('rev2a', 'rev2b'))
 
535
        self.assertEqual({'rev1'}, graph.find_lca('rev1', 'rev1'))
 
536
        self.assertEqual({'rev1'}, graph.find_lca('rev2a', 'rev2b'))
509
537
 
510
538
    def test_no_unique_lca(self):
511
539
        """Test error when one revision is not in the graph"""
516
544
    def test_lca_criss_cross(self):
517
545
        """Test least-common-ancestor after a criss-cross merge."""
518
546
        graph = self.make_graph(criss_cross)
519
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
547
        self.assertEqual({'rev2a', 'rev2b'},
520
548
                         graph.find_lca('rev3a', 'rev3b'))
521
 
        self.assertEqual(set(['rev2b']),
 
549
        self.assertEqual({'rev2b'},
522
550
                         graph.find_lca('rev3a', 'rev3b', 'rev2b'))
523
551
 
524
552
    def test_lca_shortcut(self):
525
553
        """Test least-common ancestor on this history shortcut"""
526
554
        graph = self.make_graph(history_shortcut)
527
 
        self.assertEqual(set(['rev2b']), graph.find_lca('rev3a', 'rev3b'))
 
555
        self.assertEqual({'rev2b'}, graph.find_lca('rev3a', 'rev3b'))
528
556
 
529
557
    def test_lefthand_distance_smoke(self):
530
558
        """A simple does it work test for graph.lefthand_distance(keys)."""
562
590
 
563
591
    def test__remove_simple_descendants(self):
564
592
        graph = self.make_graph(ancestry_1)
565
 
        self.assertRemoveDescendants(set(['rev1']), graph,
566
 
            set(['rev1', 'rev2a', 'rev2b', 'rev3', 'rev4']))
 
593
        self.assertRemoveDescendants({'rev1'}, graph,
 
594
            {'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'})
567
595
 
568
596
    def test__remove_simple_descendants_disjoint(self):
569
597
        graph = self.make_graph(ancestry_1)
570
 
        self.assertRemoveDescendants(set(['rev1', 'rev3']), graph,
571
 
            set(['rev1', 'rev3']))
 
598
        self.assertRemoveDescendants({'rev1', 'rev3'}, graph,
 
599
            {'rev1', 'rev3'})
572
600
 
573
601
    def test__remove_simple_descendants_chain(self):
574
602
        graph = self.make_graph(ancestry_1)
575
 
        self.assertRemoveDescendants(set(['rev1']), graph,
576
 
            set(['rev1', 'rev2a', 'rev3']))
 
603
        self.assertRemoveDescendants({'rev1'}, graph,
 
604
            {'rev1', 'rev2a', 'rev3'})
577
605
 
578
606
    def test__remove_simple_descendants_siblings(self):
579
607
        graph = self.make_graph(ancestry_1)
580
 
        self.assertRemoveDescendants(set(['rev2a', 'rev2b']), graph,
581
 
            set(['rev2a', 'rev2b', 'rev3']))
 
608
        self.assertRemoveDescendants({'rev2a', 'rev2b'}, graph,
 
609
            {'rev2a', 'rev2b', 'rev3'})
582
610
 
583
611
    def test_unique_lca_criss_cross(self):
584
612
        """Ensure we don't pick non-unique lcas in a criss-cross"""
624
652
    def test_graph_difference(self):
625
653
        graph = self.make_graph(ancestry_1)
626
654
        self.assertEqual((set(), set()), graph.find_difference('rev1', 'rev1'))
627
 
        self.assertEqual((set(), set(['rev1'])),
 
655
        self.assertEqual((set(), {'rev1'}),
628
656
                         graph.find_difference(NULL_REVISION, 'rev1'))
629
 
        self.assertEqual((set(['rev1']), set()),
 
657
        self.assertEqual(({'rev1'}, set()),
630
658
                         graph.find_difference('rev1', NULL_REVISION))
631
 
        self.assertEqual((set(['rev2a', 'rev3']), set(['rev2b'])),
 
659
        self.assertEqual(({'rev2a', 'rev3'}, {'rev2b'}),
632
660
                         graph.find_difference('rev3', 'rev2b'))
633
 
        self.assertEqual((set(['rev4', 'rev3', 'rev2a']), set()),
 
661
        self.assertEqual(({'rev4', 'rev3', 'rev2a'}, set()),
634
662
                         graph.find_difference('rev4', 'rev2b'))
635
663
 
636
664
    def test_graph_difference_separate_ancestry(self):
637
665
        graph = self.make_graph(ancestry_2)
638
 
        self.assertEqual((set(['rev1a']), set(['rev1b'])),
 
666
        self.assertEqual(({'rev1a'}, {'rev1b'}),
639
667
                         graph.find_difference('rev1a', 'rev1b'))
640
 
        self.assertEqual((set(['rev1a', 'rev2a', 'rev3a', 'rev4a']),
641
 
                          set(['rev1b'])),
 
668
        self.assertEqual(({'rev1a', 'rev2a', 'rev3a', 'rev4a'},
 
669
                          {'rev1b'}),
642
670
                         graph.find_difference('rev4a', 'rev1b'))
643
671
 
644
672
    def test_graph_difference_criss_cross(self):
645
673
        graph = self.make_graph(criss_cross)
646
 
        self.assertEqual((set(['rev3a']), set(['rev3b'])),
 
674
        self.assertEqual(({'rev3a'}, {'rev3b'}),
647
675
                         graph.find_difference('rev3a', 'rev3b'))
648
 
        self.assertEqual((set([]), set(['rev3b', 'rev2b'])),
 
676
        self.assertEqual((set([]), {'rev3b', 'rev2b'}),
649
677
                         graph.find_difference('rev2a', 'rev3b'))
650
678
 
651
679
    def test_graph_difference_extended_history(self):
652
680
        graph = self.make_graph(extended_history_shortcut)
653
 
        self.assertEqual((set(['e']), set(['f'])),
 
681
        self.assertEqual(({'e'}, {'f'}),
654
682
                         graph.find_difference('e', 'f'))
655
 
        self.assertEqual((set(['f']), set(['e'])),
 
683
        self.assertEqual(({'f'}, {'e'}),
656
684
                         graph.find_difference('f', 'e'))
657
685
 
658
686
    def test_graph_difference_double_shortcut(self):
659
687
        graph = self.make_graph(double_shortcut)
660
 
        self.assertEqual((set(['d', 'f']), set(['e', 'g'])),
 
688
        self.assertEqual(({'d', 'f'}, {'e', 'g'}),
661
689
                         graph.find_difference('f', 'g'))
662
690
 
663
691
    def test_graph_difference_complex_shortcut(self):
664
692
        graph = self.make_graph(complex_shortcut)
665
 
        self.assertEqual((set(['m', 'i', 'e']), set(['n', 'h'])),
 
693
        self.assertEqual(({'m', 'i', 'e'}, {'n', 'h'}),
666
694
                         graph.find_difference('m', 'n'))
667
695
 
668
696
    def test_graph_difference_complex_shortcut2(self):
669
697
        graph = self.make_graph(complex_shortcut2)
670
 
        self.assertEqual((set(['t']), set(['j', 'u'])),
 
698
        self.assertEqual(({'t'}, {'j', 'u'}),
671
699
                         graph.find_difference('t', 'u'))
672
700
 
673
701
    def test_graph_difference_shortcut_extra_root(self):
674
702
        graph = self.make_graph(shortcut_extra_root)
675
 
        self.assertEqual((set(['e']), set(['f', 'g'])),
 
703
        self.assertEqual(({'e'}, {'f', 'g'}),
676
704
                         graph.find_difference('e', 'f'))
677
705
 
678
 
 
679
 
    def test_stacked_parents_provider(self):
680
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
681
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
682
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
683
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
684
 
                         stacked.get_parent_map(['rev1', 'rev2']))
685
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
686
 
                         stacked.get_parent_map(['rev2', 'rev1']))
687
 
        self.assertEqual({'rev2':['rev3']},
688
 
                         stacked.get_parent_map(['rev2', 'rev2']))
689
 
        self.assertEqual({'rev1':['rev4']},
690
 
                         stacked.get_parent_map(['rev1', 'rev1']))
691
 
    
692
 
    def test_stacked_parents_provider_overlapping(self):
693
 
        # rev2 is availible in both providers.
694
 
        # 1
695
 
        # |
696
 
        # 2
697
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
698
 
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
699
 
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
700
 
        self.assertEqual({'rev2': ['rev1']},
701
 
                         stacked.get_parent_map(['rev2']))
702
 
 
703
 
    def test__stacked_parents_provider_deprecated(self):
704
 
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
705
 
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
706
 
        stacked = self.applyDeprecated(deprecated_in((1, 16, 0)),
707
 
                    _mod_graph._StackedParentsProvider, [parents1, parents2])
708
 
        self.assertEqual({'rev1':['rev4'], 'rev2':['rev3']},
709
 
                         stacked.get_parent_map(['rev1', 'rev2']))
710
 
        self.assertEqual({'rev2':['rev3'], 'rev1':['rev4']},
711
 
                         stacked.get_parent_map(['rev2', 'rev1']))
712
 
        self.assertEqual({'rev2':['rev3']},
713
 
                         stacked.get_parent_map(['rev2', 'rev2']))
714
 
        self.assertEqual({'rev1':['rev4']},
715
 
                         stacked.get_parent_map(['rev1', 'rev1']))
716
 
 
717
706
    def test_iter_topo_order(self):
718
707
        graph = self.make_graph(ancestry_1)
719
708
        args = ['rev2a', 'rev3', 'rev1']
802
791
        #      c
803
792
        graph = self.make_graph({'c': ['b', 'd'], 'd': ['e'], 'b': ['a'],
804
793
                                 'a': [NULL_REVISION], 'e': [NULL_REVISION]})
805
 
        self.assertEqual(set(['c']), graph.heads(['a', 'c', 'e']))
 
794
        self.assertEqual({'c'}, graph.heads(['a', 'c', 'e']))
806
795
 
807
796
    def test_heads_null(self):
808
797
        graph = self.make_graph(ancestry_1)
809
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
810
 
        self.assertEqual(set(['rev1']), graph.heads(['null:', 'rev1']))
811
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1', 'null:']))
812
 
        self.assertEqual(set(['rev1']), graph.heads(set(['rev1', 'null:'])))
813
 
        self.assertEqual(set(['rev1']), graph.heads(('rev1', 'null:')))
 
798
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
799
        self.assertEqual({'rev1'}, graph.heads(['null:', 'rev1']))
 
800
        self.assertEqual({'rev1'}, graph.heads(['rev1', 'null:']))
 
801
        self.assertEqual({'rev1'}, graph.heads({'rev1', 'null:'}))
 
802
        self.assertEqual({'rev1'}, graph.heads(('rev1', 'null:')))
814
803
 
815
804
    def test_heads_one(self):
816
805
        # A single node will always be a head
817
806
        graph = self.make_graph(ancestry_1)
818
 
        self.assertEqual(set(['null:']), graph.heads(['null:']))
819
 
        self.assertEqual(set(['rev1']), graph.heads(['rev1']))
820
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev2a']))
821
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev2b']))
822
 
        self.assertEqual(set(['rev3']), graph.heads(['rev3']))
823
 
        self.assertEqual(set(['rev4']), graph.heads(['rev4']))
 
807
        self.assertEqual({'null:'}, graph.heads(['null:']))
 
808
        self.assertEqual({'rev1'}, graph.heads(['rev1']))
 
809
        self.assertEqual({'rev2a'}, graph.heads(['rev2a']))
 
810
        self.assertEqual({'rev2b'}, graph.heads(['rev2b']))
 
811
        self.assertEqual({'rev3'}, graph.heads(['rev3']))
 
812
        self.assertEqual({'rev4'}, graph.heads(['rev4']))
824
813
 
825
814
    def test_heads_single(self):
826
815
        graph = self.make_graph(ancestry_1)
827
 
        self.assertEqual(set(['rev4']), graph.heads(['null:', 'rev4']))
828
 
        self.assertEqual(set(['rev2a']), graph.heads(['rev1', 'rev2a']))
829
 
        self.assertEqual(set(['rev2b']), graph.heads(['rev1', 'rev2b']))
830
 
        self.assertEqual(set(['rev3']), graph.heads(['rev1', 'rev3']))
831
 
        self.assertEqual(set(['rev4']), graph.heads(['rev1', 'rev4']))
832
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2a', 'rev4']))
833
 
        self.assertEqual(set(['rev4']), graph.heads(['rev2b', 'rev4']))
834
 
        self.assertEqual(set(['rev4']), graph.heads(['rev3', 'rev4']))
 
816
        self.assertEqual({'rev4'}, graph.heads(['null:', 'rev4']))
 
817
        self.assertEqual({'rev2a'}, graph.heads(['rev1', 'rev2a']))
 
818
        self.assertEqual({'rev2b'}, graph.heads(['rev1', 'rev2b']))
 
819
        self.assertEqual({'rev3'}, graph.heads(['rev1', 'rev3']))
 
820
        self.assertEqual({'rev4'}, graph.heads(['rev1', 'rev4']))
 
821
        self.assertEqual({'rev4'}, graph.heads(['rev2a', 'rev4']))
 
822
        self.assertEqual({'rev4'}, graph.heads(['rev2b', 'rev4']))
 
823
        self.assertEqual({'rev4'}, graph.heads(['rev3', 'rev4']))
835
824
 
836
825
    def test_heads_two_heads(self):
837
826
        graph = self.make_graph(ancestry_1)
838
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
827
        self.assertEqual({'rev2a', 'rev2b'},
839
828
                         graph.heads(['rev2a', 'rev2b']))
840
 
        self.assertEqual(set(['rev3', 'rev2b']),
 
829
        self.assertEqual({'rev3', 'rev2b'},
841
830
                         graph.heads(['rev3', 'rev2b']))
842
831
 
843
832
    def test_heads_criss_cross(self):
844
833
        graph = self.make_graph(criss_cross)
845
 
        self.assertEqual(set(['rev2a']),
 
834
        self.assertEqual({'rev2a'},
846
835
                         graph.heads(['rev2a', 'rev1']))
847
 
        self.assertEqual(set(['rev2b']),
 
836
        self.assertEqual({'rev2b'},
848
837
                         graph.heads(['rev2b', 'rev1']))
849
 
        self.assertEqual(set(['rev3a']),
 
838
        self.assertEqual({'rev3a'},
850
839
                         graph.heads(['rev3a', 'rev1']))
851
 
        self.assertEqual(set(['rev3b']),
 
840
        self.assertEqual({'rev3b'},
852
841
                         graph.heads(['rev3b', 'rev1']))
853
 
        self.assertEqual(set(['rev2a', 'rev2b']),
 
842
        self.assertEqual({'rev2a', 'rev2b'},
854
843
                         graph.heads(['rev2a', 'rev2b']))
855
 
        self.assertEqual(set(['rev3a']),
 
844
        self.assertEqual({'rev3a'},
856
845
                         graph.heads(['rev3a', 'rev2a']))
857
 
        self.assertEqual(set(['rev3a']),
 
846
        self.assertEqual({'rev3a'},
858
847
                         graph.heads(['rev3a', 'rev2b']))
859
 
        self.assertEqual(set(['rev3a']),
 
848
        self.assertEqual({'rev3a'},
860
849
                         graph.heads(['rev3a', 'rev2a', 'rev2b']))
861
 
        self.assertEqual(set(['rev3b']),
 
850
        self.assertEqual({'rev3b'},
862
851
                         graph.heads(['rev3b', 'rev2a']))
863
 
        self.assertEqual(set(['rev3b']),
 
852
        self.assertEqual({'rev3b'},
864
853
                         graph.heads(['rev3b', 'rev2b']))
865
 
        self.assertEqual(set(['rev3b']),
 
854
        self.assertEqual({'rev3b'},
866
855
                         graph.heads(['rev3b', 'rev2a', 'rev2b']))
867
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
856
        self.assertEqual({'rev3a', 'rev3b'},
868
857
                         graph.heads(['rev3a', 'rev3b']))
869
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
858
        self.assertEqual({'rev3a', 'rev3b'},
870
859
                         graph.heads(['rev3a', 'rev3b', 'rev2a', 'rev2b']))
871
860
 
872
861
    def test_heads_shortcut(self):
873
862
        graph = self.make_graph(history_shortcut)
874
863
 
875
 
        self.assertEqual(set(['rev2a', 'rev2b', 'rev2c']),
 
864
        self.assertEqual({'rev2a', 'rev2b', 'rev2c'},
876
865
                         graph.heads(['rev2a', 'rev2b', 'rev2c']))
877
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
866
        self.assertEqual({'rev3a', 'rev3b'},
878
867
                         graph.heads(['rev3a', 'rev3b']))
879
 
        self.assertEqual(set(['rev3a', 'rev3b']),
 
868
        self.assertEqual({'rev3a', 'rev3b'},
880
869
                         graph.heads(['rev2a', 'rev3a', 'rev3b']))
881
 
        self.assertEqual(set(['rev2a', 'rev3b']),
 
870
        self.assertEqual({'rev2a', 'rev3b'},
882
871
                         graph.heads(['rev2a', 'rev3b']))
883
 
        self.assertEqual(set(['rev2c', 'rev3a']),
 
872
        self.assertEqual({'rev2c', 'rev3a'},
884
873
                         graph.heads(['rev2c', 'rev3a']))
885
874
 
886
875
    def _run_heads_break_deeper(self, graph_dict, search):
909
898
            'right':['common'],
910
899
            'common':['deeper'],
911
900
        }
912
 
        self.assertEqual(set(['left', 'right']),
 
901
        self.assertEqual({'left', 'right'},
913
902
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
914
903
 
915
904
    def test_heads_limits_search_assymetric(self):
921
910
            'common':['aftercommon'],
922
911
            'aftercommon':['deeper'],
923
912
        }
924
 
        self.assertEqual(set(['left', 'right']),
 
913
        self.assertEqual({'left', 'right'},
925
914
            self._run_heads_break_deeper(graph_dict, ['left', 'right']))
926
915
 
927
916
    def test_heads_limits_search_common_search_must_continue(self):
934
923
            'common1':['common2'],
935
924
            'common2':['deeper'],
936
925
        }
937
 
        self.assertEqual(set(['h1', 'h2']),
 
926
        self.assertEqual({'h1', 'h2'},
938
927
            self._run_heads_break_deeper(graph_dict, ['h1', 'h2']))
939
928
 
940
929
    def test_breadth_first_search_start_ghosts(self):
941
930
        graph = self.make_graph({})
942
931
        # with_ghosts reports the ghosts
943
932
        search = graph._make_breadth_first_searcher(['a-ghost'])
944
 
        self.assertEqual((set(), set(['a-ghost'])), search.next_with_ghosts())
 
933
        self.assertEqual((set(), {'a-ghost'}), search.next_with_ghosts())
945
934
        self.assertRaises(StopIteration, search.next_with_ghosts)
946
935
        # next includes them
947
936
        search = graph._make_breadth_first_searcher(['a-ghost'])
948
 
        self.assertEqual(set(['a-ghost']), search.next())
949
 
        self.assertRaises(StopIteration, search.next)
 
937
        self.assertEqual({'a-ghost'}, next(search))
 
938
        self.assertRaises(StopIteration, next, search)
950
939
 
951
940
    def test_breadth_first_search_deep_ghosts(self):
952
941
        graph = self.make_graph({
956
945
            })
957
946
        # with_ghosts reports the ghosts
958
947
        search = graph._make_breadth_first_searcher(['head'])
959
 
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
960
 
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
961
 
        self.assertEqual((set(['child']), set(['ghost'])),
 
948
        self.assertEqual(({'head'}, set()), search.next_with_ghosts())
 
949
        self.assertEqual(({'present'}, set()), search.next_with_ghosts())
 
950
        self.assertEqual(({'child'}, {'ghost'}),
962
951
            search.next_with_ghosts())
963
952
        self.assertRaises(StopIteration, search.next_with_ghosts)
964
953
        # next includes them
965
954
        search = graph._make_breadth_first_searcher(['head'])
966
 
        self.assertEqual(set(['head']), search.next())
967
 
        self.assertEqual(set(['present']), search.next())
968
 
        self.assertEqual(set(['child', 'ghost']),
969
 
            search.next())
970
 
        self.assertRaises(StopIteration, search.next)
 
955
        self.assertEqual({'head'}, next(search))
 
956
        self.assertEqual({'present'}, next(search))
 
957
        self.assertEqual({'child', 'ghost'},
 
958
            next(search))
 
959
        self.assertRaises(StopIteration, next, search)
971
960
 
972
961
    def test_breadth_first_search_change_next_to_next_with_ghosts(self):
973
962
        # To make the API robust, we allow calling both next() and
979
968
            })
980
969
        # start with next_with_ghosts
981
970
        search = graph._make_breadth_first_searcher(['head'])
982
 
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
983
 
        self.assertEqual(set(['present']), search.next())
984
 
        self.assertEqual((set(['child']), set(['ghost'])),
 
971
        self.assertEqual(({'head'}, set()), search.next_with_ghosts())
 
972
        self.assertEqual({'present'}, next(search))
 
973
        self.assertEqual(({'child'}, {'ghost'}),
985
974
            search.next_with_ghosts())
986
 
        self.assertRaises(StopIteration, search.next)
 
975
        self.assertRaises(StopIteration, next, search)
987
976
        # start with next
988
977
        search = graph._make_breadth_first_searcher(['head'])
989
 
        self.assertEqual(set(['head']), search.next())
990
 
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
991
 
        self.assertEqual(set(['child', 'ghost']),
992
 
            search.next())
 
978
        self.assertEqual({'head'}, next(search))
 
979
        self.assertEqual(({'present'}, set()), search.next_with_ghosts())
 
980
        self.assertEqual({'child', 'ghost'},
 
981
            next(search))
993
982
        self.assertRaises(StopIteration, search.next_with_ghosts)
994
983
 
995
984
    def test_breadth_first_change_search(self):
1001
990
            'other_2':[],
1002
991
            })
1003
992
        search = graph._make_breadth_first_searcher(['head'])
1004
 
        self.assertEqual((set(['head']), set()), search.next_with_ghosts())
1005
 
        self.assertEqual((set(['present']), set()), search.next_with_ghosts())
1006
 
        self.assertEqual(set(['present']),
 
993
        self.assertEqual(({'head'}, set()), search.next_with_ghosts())
 
994
        self.assertEqual(({'present'}, set()), search.next_with_ghosts())
 
995
        self.assertEqual({'present'},
1007
996
            search.stop_searching_any(['present']))
1008
 
        self.assertEqual((set(['other']), set(['other_ghost'])),
 
997
        self.assertEqual(({'other'}, {'other_ghost'}),
1009
998
            search.start_searching(['other', 'other_ghost']))
1010
 
        self.assertEqual((set(['other_2']), set()), search.next_with_ghosts())
 
999
        self.assertEqual(({'other_2'}, set()), search.next_with_ghosts())
1011
1000
        self.assertRaises(StopIteration, search.next_with_ghosts)
1012
1001
        # next includes them
1013
1002
        search = graph._make_breadth_first_searcher(['head'])
1014
 
        self.assertEqual(set(['head']), search.next())
1015
 
        self.assertEqual(set(['present']), search.next())
1016
 
        self.assertEqual(set(['present']),
 
1003
        self.assertEqual({'head'}, next(search))
 
1004
        self.assertEqual({'present'}, next(search))
 
1005
        self.assertEqual({'present'},
1017
1006
            search.stop_searching_any(['present']))
1018
1007
        search.start_searching(['other', 'other_ghost'])
1019
 
        self.assertEqual(set(['other_2']), search.next())
1020
 
        self.assertRaises(StopIteration, search.next)
 
1008
        self.assertEqual({'other_2'}, next(search))
 
1009
        self.assertRaises(StopIteration, next, search)
1021
1010
 
1022
1011
    def assertSeenAndResult(self, instructions, search, next):
1023
1012
        """Check the results of .seen and get_result() for a seach.
1040
1029
                search.start_searching(starts)
1041
1030
            if stops is not None:
1042
1031
                search.stop_searching_any(stops)
1043
 
            result = search.get_result()
1044
 
            self.assertEqual(recipe, result.get_recipe())
1045
 
            self.assertEqual(set(included_keys), result.get_keys())
 
1032
            state = search.get_state()
 
1033
            self.assertEqual(set(included_keys), state[2])
1046
1034
            self.assertEqual(seen, search.seen)
1047
1035
 
1048
1036
    def test_breadth_first_get_result_excludes_current_pending(self):
1053
1041
            })
1054
1042
        search = graph._make_breadth_first_searcher(['head'])
1055
1043
        # At the start, nothing has been seen, to its all excluded:
1056
 
        result = search.get_result()
1057
 
        self.assertEqual(('search', set(['head']), set(['head']), 0),
1058
 
            result.get_recipe())
1059
 
        self.assertEqual(set(), result.get_keys())
 
1044
        state = search.get_state()
 
1045
        self.assertEqual(({'head'}, {'head'}, set()),
 
1046
            state)
1060
1047
        self.assertEqual(set(), search.seen)
1061
1048
        # using next:
1062
1049
        expected = [
1063
 
            (set(['head']), (set(['head']), set(['child']), 1),
 
1050
            ({'head'}, ({'head'}, {'child'}, 1),
1064
1051
             ['head'], None, None),
1065
 
            (set(['head', 'child']), (set(['head']), set([NULL_REVISION]), 2),
 
1052
            ({'head', 'child'}, ({'head'}, {NULL_REVISION}, 2),
1066
1053
             ['head', 'child'], None, None),
1067
 
            (set(['head', 'child', NULL_REVISION]), (set(['head']), set(), 3),
 
1054
            ({'head', 'child', NULL_REVISION}, ({'head'}, set(), 3),
1068
1055
             ['head', 'child', NULL_REVISION], None, None),
1069
1056
            ]
1070
 
        self.assertSeenAndResult(expected, search, search.next)
 
1057
        self.assertSeenAndResult(expected, search, search.__next__)
1071
1058
        # using next_with_ghosts:
1072
1059
        search = graph._make_breadth_first_searcher(['head'])
1073
1060
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1085
1072
        # Starting with nothing and adding a search works:
1086
1073
        search.start_searching(['head'])
1087
1074
        # head has been seen:
1088
 
        result = search.get_result()
1089
 
        self.assertEqual(('search', set(['head']), set(['child']), 1),
1090
 
            result.get_recipe())
1091
 
        self.assertEqual(set(['head']), result.get_keys())
1092
 
        self.assertEqual(set(['head']), search.seen)
 
1075
        state = search.get_state()
 
1076
        self.assertEqual(({'head'}, {'child'}, {'head'}),
 
1077
            state)
 
1078
        self.assertEqual({'head'}, search.seen)
1093
1079
        # using next:
1094
1080
        expected = [
1095
1081
            # stop at child, and start a new search at otherhead:
1096
1082
            # - otherhead counts as seen immediately when start_searching is
1097
1083
            # called.
1098
 
            (set(['head', 'child', 'otherhead']),
1099
 
             (set(['head', 'otherhead']), set(['child', 'otherchild']), 2),
 
1084
            ({'head', 'child', 'otherhead'},
 
1085
             ({'head', 'otherhead'}, {'child', 'otherchild'}, 2),
1100
1086
             ['head', 'otherhead'], ['otherhead'], ['child']),
1101
 
            (set(['head', 'child', 'otherhead', 'otherchild']),
1102
 
             (set(['head', 'otherhead']), set(['child', 'excluded']), 3),
 
1087
            ({'head', 'child', 'otherhead', 'otherchild'},
 
1088
             ({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1103
1089
             ['head', 'otherhead', 'otherchild'], None, None),
1104
1090
            # stop searching excluded now
1105
 
            (set(['head', 'child', 'otherhead', 'otherchild', 'excluded']),
1106
 
             (set(['head', 'otherhead']), set(['child', 'excluded']), 3),
 
1091
            ({'head', 'child', 'otherhead', 'otherchild', 'excluded'},
 
1092
             ({'head', 'otherhead'}, {'child', 'excluded'}, 3),
1107
1093
             ['head', 'otherhead', 'otherchild'], None, ['excluded']),
1108
1094
            ]
1109
 
        self.assertSeenAndResult(expected, search, search.next)
 
1095
        self.assertSeenAndResult(expected, search, search.__next__)
1110
1096
        # using next_with_ghosts:
1111
1097
        search = graph._make_breadth_first_searcher([])
1112
1098
        search.start_searching(['head'])
1123
1109
        search = graph._make_breadth_first_searcher(['head'])
1124
1110
        expected = [
1125
1111
            # NULL_REVISION and ghost1 have not been returned
1126
 
            (set(['head']),
1127
 
             (set(['head']), set(['child', NULL_REVISION, 'ghost1']), 1),
 
1112
            ({'head'},
 
1113
             ({'head'}, {'child', NULL_REVISION, 'ghost1'}, 1),
1128
1114
             ['head'], None, [NULL_REVISION, 'ghost1']),
1129
1115
            # ghost1 has been returned, NULL_REVISION is to be returned in the
1130
1116
            # next iteration.
1131
 
            (set(['head', 'child', 'ghost1']),
1132
 
             (set(['head']), set(['ghost1', NULL_REVISION]), 2),
 
1117
            ({'head', 'child', 'ghost1'},
 
1118
             ({'head'}, {'ghost1', NULL_REVISION}, 2),
1133
1119
             ['head', 'child'], None, [NULL_REVISION, 'ghost1']),
1134
1120
            ]
1135
 
        self.assertSeenAndResult(expected, search, search.next)
 
1121
        self.assertSeenAndResult(expected, search, search.__next__)
1136
1122
        # using next_with_ghosts:
1137
1123
        search = graph._make_breadth_first_searcher(['head'])
1138
1124
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1149
1135
            })
1150
1136
        search = graph._make_breadth_first_searcher(['head'])
1151
1137
        expected = [
1152
 
            (set(['head']), (set(['head']), set(['middle']), 1),
 
1138
            ({'head'}, ({'head'}, {'middle'}, 1),
1153
1139
             ['head'], None, None),
1154
 
            (set(['head', 'middle']), (set(['head']), set(['child']), 2),
 
1140
            ({'head', 'middle'}, ({'head'}, {'child'}, 2),
1155
1141
             ['head', 'middle'], None, None),
1156
1142
            # 'middle' came from the previous iteration, but we don't stop
1157
1143
            # searching it until *after* advancing the searcher.
1158
 
            (set(['head', 'middle', 'child']),
1159
 
             (set(['head']), set(['middle', 'child']), 1),
 
1144
            ({'head', 'middle', 'child'},
 
1145
             ({'head'}, {'middle', 'child'}, 1),
1160
1146
             ['head'], None, ['middle', 'child']),
1161
1147
            ]
1162
 
        self.assertSeenAndResult(expected, search, search.next)
 
1148
        self.assertSeenAndResult(expected, search, search.__next__)
1163
1149
        # using next_with_ghosts:
1164
1150
        search = graph._make_breadth_first_searcher(['head'])
1165
1151
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1173
1159
        search = graph._make_breadth_first_searcher(['head'])
1174
1160
        # using next:
1175
1161
        expected = [
1176
 
            (set(['head']),
1177
 
             (set(['head']), set(['ghost', 'child']), 1),
 
1162
            ({'head'},
 
1163
             ({'head'}, {'ghost', 'child'}, 1),
1178
1164
             ['head'], None, None),
1179
 
            (set(['head', 'child', 'ghost']),
1180
 
             (set(['head']), set([NULL_REVISION, 'ghost']), 2),
 
1165
            ({'head', 'child', 'ghost'},
 
1166
             ({'head'}, {NULL_REVISION, 'ghost'}, 2),
1181
1167
             ['head', 'child'], None, None),
1182
1168
            ]
1183
 
        self.assertSeenAndResult(expected, search, search.next)
 
1169
        self.assertSeenAndResult(expected, search, search.__next__)
1184
1170
        # using next_with_ghosts:
1185
1171
        search = graph._make_breadth_first_searcher(['head'])
1186
1172
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1194
1180
        search = graph._make_breadth_first_searcher(['head'])
1195
1181
        # using next:
1196
1182
        expected = [
1197
 
            (set(['head', 'ghost']),
1198
 
             (set(['head', 'ghost']), set(['child', 'ghost']), 1),
 
1183
            ({'head', 'ghost'},
 
1184
             ({'head', 'ghost'}, {'child', 'ghost'}, 1),
1199
1185
             ['head'], ['ghost'], None),
1200
 
            (set(['head', 'child', 'ghost']),
1201
 
             (set(['head', 'ghost']), set([NULL_REVISION, 'ghost']), 2),
 
1186
            ({'head', 'child', 'ghost'},
 
1187
             ({'head', 'ghost'}, {NULL_REVISION, 'ghost'}, 2),
1202
1188
             ['head', 'child'], None, None),
1203
1189
            ]
1204
 
        self.assertSeenAndResult(expected, search, search.next)
 
1190
        self.assertSeenAndResult(expected, search, search.__next__)
1205
1191
        # using next_with_ghosts:
1206
1192
        search = graph._make_breadth_first_searcher(['head'])
1207
1193
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1214
1200
        search = graph._make_breadth_first_searcher(['head'])
1215
1201
        # using next:
1216
1202
        expected = [
1217
 
            (set(['head']),
1218
 
             (set(['head']), set([NULL_REVISION]), 1),
 
1203
            ({'head'},
 
1204
             ({'head'}, {NULL_REVISION}, 1),
1219
1205
             ['head'], None, None),
1220
 
            (set(['head', NULL_REVISION]),
1221
 
             (set(['head']), set([]), 2),
 
1206
            ({'head', NULL_REVISION},
 
1207
             ({'head'}, set([]), 2),
1222
1208
             ['head', NULL_REVISION], None, None),
1223
1209
            ]
1224
 
        self.assertSeenAndResult(expected, search, search.next)
 
1210
        self.assertSeenAndResult(expected, search, search.__next__)
1225
1211
        # using next_with_ghosts:
1226
1212
        search = graph._make_breadth_first_searcher(['head'])
1227
1213
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1235
1221
        search = graph._make_breadth_first_searcher(['head'])
1236
1222
        # using next:
1237
1223
        expected = [
1238
 
            (set(['head']),
1239
 
             (set(['head']), set([NULL_REVISION]), 1),
 
1224
            ({'head'},
 
1225
             ({'head'}, {NULL_REVISION}, 1),
1240
1226
             ['head'], None, None),
1241
 
            (set(['head', 'ghost', NULL_REVISION]),
1242
 
             (set(['head', 'ghost']), set(['ghost']), 2),
 
1227
            ({'head', 'ghost', NULL_REVISION},
 
1228
             ({'head', 'ghost'}, {'ghost'}, 2),
1243
1229
             ['head', NULL_REVISION], ['ghost'], None),
1244
1230
            ]
1245
 
        self.assertSeenAndResult(expected, search, search.next)
1246
 
        self.assertRaises(StopIteration, search.next)
1247
 
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1248
 
        result = search.get_result()
1249
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1250
 
            result.get_recipe())
1251
 
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
1231
        self.assertSeenAndResult(expected, search, search.__next__)
 
1232
        self.assertRaises(StopIteration, next, search)
 
1233
        self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
 
1234
        state = search.get_state()
 
1235
        self.assertEqual(
 
1236
            ({'ghost', 'head'}, {'ghost'},
 
1237
                {'head', NULL_REVISION}),
 
1238
            state)
1252
1239
        # using next_with_ghosts:
1253
1240
        search = graph._make_breadth_first_searcher(['head'])
1254
1241
        self.assertSeenAndResult(expected, search, search.next_with_ghosts)
1255
 
        self.assertRaises(StopIteration, search.next)
1256
 
        self.assertEqual(set(['head', 'ghost', NULL_REVISION]), search.seen)
1257
 
        result = search.get_result()
1258
 
        self.assertEqual(('search', set(['ghost', 'head']), set(['ghost']), 2),
1259
 
            result.get_recipe())
1260
 
        self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
1242
        self.assertRaises(StopIteration, next, search)
 
1243
        self.assertEqual({'head', 'ghost', NULL_REVISION}, search.seen)
 
1244
        state = search.get_state()
 
1245
        self.assertEqual(
 
1246
            ({'ghost', 'head'}, {'ghost'},
 
1247
                {'head', NULL_REVISION}),
 
1248
            state)
1261
1249
 
1262
1250
 
1263
1251
class TestFindUniqueAncestors(TestGraphBase):
1424
1412
        self.assertMergeOrder(['rev3', 'rev1'], graph, 'rev4', ['rev1', 'rev3'])
1425
1413
 
1426
1414
 
 
1415
class TestFindDescendants(TestGraphBase):
 
1416
 
 
1417
    def test_find_descendants_rev1_rev3(self):
 
1418
        graph = self.make_graph(ancestry_1)
 
1419
        descendants = graph.find_descendants('rev1', 'rev3')
 
1420
        self.assertEqual({'rev1', 'rev2a', 'rev3'}, descendants)
 
1421
 
 
1422
    def test_find_descendants_rev1_rev4(self):
 
1423
        graph = self.make_graph(ancestry_1)
 
1424
        descendants = graph.find_descendants('rev1', 'rev4')
 
1425
        self.assertEqual({'rev1', 'rev2a', 'rev2b', 'rev3', 'rev4'},
 
1426
                         descendants)
 
1427
 
 
1428
    def test_find_descendants_rev2a_rev4(self):
 
1429
        graph = self.make_graph(ancestry_1)
 
1430
        descendants = graph.find_descendants('rev2a', 'rev4')
 
1431
        self.assertEqual({'rev2a', 'rev3', 'rev4'}, descendants)
 
1432
 
 
1433
class TestFindLefthandMerger(TestGraphBase):
 
1434
 
 
1435
    def check_merger(self, result, ancestry, merged, tip):
 
1436
        graph = self.make_graph(ancestry)
 
1437
        self.assertEqual(result, graph.find_lefthand_merger(merged, tip))
 
1438
 
 
1439
    def test_find_lefthand_merger_rev2b(self):
 
1440
        self.check_merger('rev4', ancestry_1, 'rev2b', 'rev4')
 
1441
 
 
1442
    def test_find_lefthand_merger_rev2a(self):
 
1443
        self.check_merger('rev2a', ancestry_1, 'rev2a', 'rev4')
 
1444
 
 
1445
    def test_find_lefthand_merger_rev4(self):
 
1446
        self.check_merger(None, ancestry_1, 'rev4', 'rev2a')
 
1447
 
 
1448
    def test_find_lefthand_merger_f(self):
 
1449
        self.check_merger('i', complex_shortcut, 'f', 'm')
 
1450
 
 
1451
    def test_find_lefthand_merger_g(self):
 
1452
        self.check_merger('i', complex_shortcut, 'g', 'm')
 
1453
 
 
1454
    def test_find_lefthand_merger_h(self):
 
1455
        self.check_merger('n', complex_shortcut, 'h', 'n')
 
1456
 
 
1457
 
 
1458
class TestGetChildMap(TestGraphBase):
 
1459
 
 
1460
    def test_get_child_map(self):
 
1461
        graph = self.make_graph(ancestry_1)
 
1462
        child_map = graph.get_child_map(['rev4', 'rev3', 'rev2a', 'rev2b'])
 
1463
        self.assertEqual({'rev1': ['rev2a', 'rev2b'],
 
1464
                          'rev2a': ['rev3'],
 
1465
                          'rev2b': ['rev4'],
 
1466
                          'rev3': ['rev4']},
 
1467
                          child_map)
 
1468
 
 
1469
 
1427
1470
class TestCachingParentsProvider(tests.TestCase):
1428
1471
    """These tests run with:
1429
1472
 
1434
1477
 
1435
1478
    def setUp(self):
1436
1479
        super(TestCachingParentsProvider, self).setUp()
1437
 
        dict_pp = _mod_graph.DictParentsProvider({'a':('b',)})
 
1480
        dict_pp = _mod_graph.DictParentsProvider({'a': ('b',)})
1438
1481
        self.inst_pp = InstrumentedParentsProvider(dict_pp)
1439
1482
        self.caching_pp = _mod_graph.CachingParentsProvider(self.inst_pp)
1440
1483
 
1477
1520
        self.caching_pp.note_missing_key('b')
1478
1521
        self.assertEqual({}, self.caching_pp.get_parent_map(['b']))
1479
1522
        self.assertEqual([], self.inst_pp.calls)
1480
 
        self.assertEqual(set(['b']), self.caching_pp.missing_keys)
 
1523
        self.assertEqual({'b'}, self.caching_pp.missing_keys)
 
1524
 
 
1525
    def test_get_cached_parent_map(self):
 
1526
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['a']))
 
1527
        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']))
1481
1532
 
1482
1533
 
1483
1534
class TestCachingParentsProviderExtras(tests.TestCaseWithTransport):
1543
1594
                         self.caching_pp.get_parent_map(['rev2']))
1544
1595
        self.assertEqual(['rev3'], self.inst_pp.calls)
1545
1596
 
 
1597
    def test_extras_using_cached(self):
 
1598
        self.assertEqual({}, self.caching_pp.get_cached_parent_map(['rev3']))
 
1599
        self.assertEqual({}, self.caching_pp.get_parent_map(['rev3']))
 
1600
        self.assertEqual({'rev2': ['rev1']},
 
1601
                         self.caching_pp.get_cached_parent_map(['rev2']))
 
1602
        self.assertEqual(['rev3'], self.inst_pp.calls)
 
1603
 
 
1604
 
1546
1605
 
1547
1606
class TestCollapseLinearRegions(tests.TestCase):
1548
1607
 
1599
1658
        self.assertEqual(['D'], sorted(graph_thunk.heads(['D', 'C'])))
1600
1659
        self.assertEqual(['B', 'C'], sorted(graph_thunk.heads(['B', 'C'])))
1601
1660
 
1602
 
 
1603
 
class TestPendingAncestryResultGetKeys(TestCaseWithMemoryTransport):
1604
 
    """Tests for bzrlib.graph.PendingAncestryResult."""
1605
 
 
1606
 
    def test_get_keys(self):
1607
 
        builder = self.make_branch_builder('b')
1608
 
        builder.start_series()
1609
 
        builder.build_snapshot('rev-1', None, [
1610
 
            ('add', ('', 'root-id', 'directory', ''))])
1611
 
        builder.build_snapshot('rev-2', ['rev-1'], [])
1612
 
        builder.finish_series()
1613
 
        repo = builder.get_branch().repository
1614
 
        repo.lock_read()
1615
 
        self.addCleanup(repo.unlock)
1616
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1617
 
        self.assertEqual(set(['rev-1', 'rev-2']), set(result.get_keys()))
1618
 
 
1619
 
    def test_get_keys_excludes_ghosts(self):
1620
 
        builder = self.make_branch_builder('b')
1621
 
        builder.start_series()
1622
 
        builder.build_snapshot('rev-1', None, [
1623
 
            ('add', ('', 'root-id', 'directory', ''))])
1624
 
        builder.build_snapshot('rev-2', ['rev-1', 'ghost'], [])
1625
 
        builder.finish_series()
1626
 
        repo = builder.get_branch().repository
1627
 
        repo.lock_read()
1628
 
        self.addCleanup(repo.unlock)
1629
 
        result = _mod_graph.PendingAncestryResult(['rev-2'], repo)
1630
 
        self.assertEqual(sorted(['rev-1', 'rev-2']), sorted(result.get_keys()))
1631
 
 
1632
 
    def test_get_keys_excludes_null(self):
1633
 
        # Make a 'graph' with an iter_ancestry that returns NULL_REVISION
1634
 
        # somewhere other than the last element, which can happen in real
1635
 
        # ancestries.
1636
 
        class StubGraph(object):
1637
 
            def iter_ancestry(self, keys):
1638
 
                return [(NULL_REVISION, ()), ('foo', (NULL_REVISION,))]
1639
 
        result = _mod_graph.PendingAncestryResult(['rev-3'], None)
1640
 
        result_keys = result._get_keys(StubGraph())
1641
 
        # Only the non-null keys from the ancestry appear.
1642
 
        self.assertEqual(set(['foo']), set(result_keys))
1643
 
 
1644
 
 
1645
 
class TestPendingAncestryResultRefine(TestGraphBase):
1646
 
 
1647
 
    def test_refine(self):
1648
 
        # Used when pulling from a stacked repository, so test some revisions
1649
 
        # being satisfied from the stacking branch.
1650
 
        g = self.make_graph(
1651
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1652
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1653
 
        result = _mod_graph.PendingAncestryResult(['tip', 'tag'], None)
1654
 
        result = result.refine(set(['tip']), set(['mid']))
1655
 
        self.assertEqual(set(['mid', 'tag']), result.heads)
1656
 
        result = result.refine(set(['mid', 'tag', 'base']),
1657
 
            set([NULL_REVISION]))
1658
 
        self.assertEqual(set([NULL_REVISION]), result.heads)
1659
 
        self.assertTrue(result.is_empty())
1660
 
 
1661
 
 
1662
 
class TestSearchResultRefine(TestGraphBase):
1663
 
 
1664
 
    def test_refine(self):
1665
 
        # Used when pulling from a stacked repository, so test some revisions
1666
 
        # being satisfied from the stacking branch.
1667
 
        g = self.make_graph(
1668
 
            {"tip":["mid"], "mid":["base"], "tag":["base"],
1669
 
             "base":[NULL_REVISION], NULL_REVISION:[]})
1670
 
        result = _mod_graph.SearchResult(set(['tip', 'tag']),
1671
 
            set([NULL_REVISION]), 4, set(['tip', 'mid', 'tag', 'base']))
1672
 
        result = result.refine(set(['tip']), set(['mid']))
1673
 
        recipe = result.get_recipe()
1674
 
        # We should be starting from tag (original head) and mid (seen ref)
1675
 
        self.assertEqual(set(['mid', 'tag']), recipe[1])
1676
 
        # We should be stopping at NULL (original stop) and tip (seen head)
1677
 
        self.assertEqual(set([NULL_REVISION, 'tip']), recipe[2])
1678
 
        self.assertEqual(3, recipe[3])
1679
 
        result = result.refine(set(['mid', 'tag', 'base']),
1680
 
            set([NULL_REVISION]))
1681
 
        recipe = result.get_recipe()
1682
 
        # We should be starting from nothing (NULL was known as a cut point)
1683
 
        self.assertEqual(set([]), recipe[1])
1684
 
        # We should be stopping at NULL (original stop) and tip (seen head) and
1685
 
        # tag (seen head) and mid(seen mid-point head). We could come back and
1686
 
        # define this as not including mid, for minimal results, but it is
1687
 
        # still 'correct' to include mid, and simpler/easier.
1688
 
        self.assertEqual(set([NULL_REVISION, 'tip', 'tag', 'mid']), recipe[2])
1689
 
        self.assertEqual(0, recipe[3])
1690
 
        self.assertTrue(result.is_empty())
 
1661
    def test_add_node(self):
 
1662
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1663
        g = _mod_graph.KnownGraph(d)
 
1664
        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'])))
 
1668
 
 
1669
    def test_merge_sort(self):
 
1670
        d = {('C',):[('A',)], ('B',): [('A',)], ('A',): []}
 
1671
        g = _mod_graph.KnownGraph(d)
 
1672
        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')])
 
1677
 
 
1678
 
 
1679
class TestStackedParentsProvider(tests.TestCase):
 
1680
 
 
1681
    def setUp(self):
 
1682
        super(TestStackedParentsProvider, self).setUp()
 
1683
        self.calls = []
 
1684
 
 
1685
    def get_shared_provider(self, info, ancestry, has_cached):
 
1686
        pp = _mod_graph.DictParentsProvider(ancestry)
 
1687
        if has_cached:
 
1688
            pp.get_cached_parent_map = pp.get_parent_map
 
1689
        return SharedInstrumentedParentsProvider(pp, self.calls, info)
 
1690
 
 
1691
    def test_stacked_parents_provider(self):
 
1692
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev3']})
 
1693
        parents2 = _mod_graph.DictParentsProvider({'rev1': ['rev4']})
 
1694
        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']))
 
1703
 
 
1704
    def test_stacked_parents_provider_overlapping(self):
 
1705
        # rev2 is availible in both providers.
 
1706
        # 1
 
1707
        # |
 
1708
        # 2
 
1709
        parents1 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
1710
        parents2 = _mod_graph.DictParentsProvider({'rev2': ['rev1']})
 
1711
        stacked = _mod_graph.StackedParentsProvider([parents1, parents2])
 
1712
        self.assertEqual({'rev2': ['rev1']},
 
1713
                         stacked.get_parent_map(['rev2']))
 
1714
 
 
1715
    def test_handles_no_get_cached_parent_map(self):
 
1716
        # this shows that we both handle when a provider doesn't implement
 
1717
        # get_cached_parent_map
 
1718
        pp1 = self.get_shared_provider('pp1', {'rev2': ('rev1',)},
 
1719
                                       has_cached=False)
 
1720
        pp2 = self.get_shared_provider('pp2', {'rev2': ('rev1',)},
 
1721
                                       has_cached=True)
 
1722
        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)
 
1726
 
 
1727
    def test_query_order(self):
 
1728
        # We should call get_cached_parent_map on all providers before we call
 
1729
        # get_parent_map. Further, we should track what entries we have found,
 
1730
        # 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)
 
1734
        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']),
 
1738
                          # No call to pp2, because it doesn't have cached
 
1739
                          ('pp3', 'cached', ['b', 'c', 'd']),
 
1740
                          ('pp1', ['c', 'd']),
 
1741
                          ('pp2', ['c', 'd']),
 
1742
                          ('pp3', ['d']),
 
1743
                         ], self.calls)