« back to all changes in this revision
Viewing changes to bzrlib/tests/test_merge.py
- browse files at revision 3015.4.21
- compare with another revision
- compare with revision 45
- download diff
- download tarball
- view history from revision 3015.4.21
- Committer: Andrew Bennetts
- Date: 2008-07-28 06:53:44 UTC
- mfrom: (3581 +trunk)
- mto: This revision was merged to the branch mainline in revision 3583.
- Revision ID: andrew.bennetts@canonical.com-20080728065344-ocndjoycs903q6fz
Merge bzr.dev.
- files added:
- bzrlib/_walkdirs_win32.h
- files modified:
- .bzrignore
added
removed
bzrlib/tests/test_merge.py
478
478
def add_version(self, key, parents, text):
479
479
self.vf.add_lines(key, parents, [c+'\n' for c in text])
480
480
481
def add_rev(self, prefix, revision_id, parents, text):
482
self.add_version((prefix, revision_id), [(prefix, p) for p in parents],
483
text)
484
481
485
def add_uncommitted_version(self, key, parents, text):
482
486
self.plan_merge_vf.add_lines(key, parents,
483
487
[c+'\n' for c in text])
484
488
485
489
def setup_plan_merge(self):
486
self.add_version(('root', 'A'), [], 'abc')
487
self.add_version(('root', 'B'), [('root', 'A')], 'acehg')
488
self.add_version(('root', 'C'), [('root', 'A')], 'fabg')
490
self.add_rev('root', 'A', [], 'abc')
491
self.add_rev('root', 'B', ['A'], 'acehg')
492
self.add_rev('root', 'C', ['A'], 'fabg')
489
493
return _PlanMerge('B', 'C', self.plan_merge_vf, ('root',))
490
494
491
495
def setup_plan_merge_uncommitted(self):
500
504
plan._get_matching_blocks('B', 'C')),
501
505
([1, 2, 3], [0, 2]))
502
506
503
def test_find_new(self):
504
plan = self.setup_plan_merge()
505
self.assertEqual(set([2, 3, 4]), plan._find_new('B'))
506
self.assertEqual(set([0, 3]), plan._find_new('C'))
507
508
def test_find_new2(self):
509
self.add_version(('root', 'A'), [], 'abc')
510
self.add_version(('root', 'B'), [('root', 'A')], 'abcde')
511
self.add_version(('root', 'C'), [('root', 'A')], 'abcefg')
512
self.add_version(('root', 'D'),
513
[('root', 'A'), ('root', 'B'), ('root', 'C')], 'abcdegh')
514
my_plan = _PlanMerge('B', 'D', self.plan_merge_vf, ('root',))
515
self.assertEqual(set([5, 6]), my_plan._find_new('D'))
516
self.assertEqual(set(), my_plan._find_new('A'))
517
518
def test_find_new_no_ancestors(self):
519
self.add_version(('root', 'A'), [], 'abc')
520
self.add_version(('root', 'B'), [], 'xyz')
521
my_plan = _PlanMerge('A', 'B', self.vf, ('root',))
522
self.assertEqual(set([0, 1, 2]), my_plan._find_new('A'))
523
524
507
def test_plan_merge(self):
525
508
self.setup_plan_merge()
526
509
plan = self.plan_merge_vf.plan_merge('B', 'C')
527
510
self.assertEqual([
528
511
('new-b', 'f\n'),
529
512
('unchanged', 'a\n'),
513
('killed-a', 'b\n'),
530
514
('killed-b', 'c\n'),
531
515
('new-a', 'e\n'),
532
516
('new-a', 'h\n'),
533
('killed-a', 'b\n'),
534
('unchanged', 'g\n')],
517
('new-a', 'g\n'),
518
('new-b', 'g\n')],
519
list(plan))
520
521
def test_plan_merge_cherrypick(self):
522
self.add_rev('root', 'A', [], 'abc')
523
self.add_rev('root', 'B', ['A'], 'abcde')
524
self.add_rev('root', 'C', ['A'], 'abcefg')
525
self.add_rev('root', 'D', ['A', 'B', 'C'], 'abcdegh')
526
my_plan = _PlanMerge('B', 'D', self.plan_merge_vf, ('root',))
527
# We shortcut when one text supersedes the other in the per-file graph.
528
# We don't actually need to compare the texts at this point.
529
self.assertEqual([
530
('new-b', 'a\n'),
531
('new-b', 'b\n'),
532
('new-b', 'c\n'),
533
('new-b', 'd\n'),
534
('new-b', 'e\n'),
535
('new-b', 'g\n'),
536
('new-b', 'h\n')],
537
list(my_plan.plan_merge()))
538
539
def test_plan_merge_no_common_ancestor(self):
540
self.add_rev('root', 'A', [], 'abc')
541
self.add_rev('root', 'B', [], 'xyz')
542
my_plan = _PlanMerge('A', 'B', self.plan_merge_vf, ('root',))
543
self.assertEqual([
544
('new-a', 'a\n'),
545
('new-a', 'b\n'),
546
('new-a', 'c\n'),
547
('new-b', 'x\n'),
548
('new-b', 'y\n'),
549
('new-b', 'z\n')],
550
list(my_plan.plan_merge()))
551
552
def test_plan_merge_tail_ancestors(self):
553
# The graph looks like this:
554
# A # Common to all ancestors
555
# / \
556
# B C # Ancestors of E, only common to one side
557
# |\ /|
558
# D E F # D, F are unique to G, H respectively
559
# |/ \| # E is the LCA for G & H, and the unique LCA for
560
# G H # I, J
561
# |\ /|
562
# | X |
563
# |/ \|
564
# I J # criss-cross merge of G, H
565
#
566
# In this situation, a simple pruning of ancestors of E will leave D &
567
# F "dangling", which looks like they introduce lines different from
568
# the ones in E, but in actuality C&B introduced the lines, and they
569
# are already present in E
570
571
# Introduce the base text
572
self.add_rev('root', 'A', [], 'abc')
573
# Introduces a new line B
574
self.add_rev('root', 'B', ['A'], 'aBbc')
575
# Introduces a new line C
576
self.add_rev('root', 'C', ['A'], 'abCc')
577
# Introduce new line D
578
self.add_rev('root', 'D', ['B'], 'DaBbc')
579
# Merges B and C by just incorporating both
580
self.add_rev('root', 'E', ['B', 'C'], 'aBbCc')
581
# Introduce new line F
582
self.add_rev('root', 'F', ['C'], 'abCcF')
583
# Merge D & E by just combining the texts
584
self.add_rev('root', 'G', ['D', 'E'], 'DaBbCc')
585
# Merge F & E by just combining the texts
586
self.add_rev('root', 'H', ['F', 'E'], 'aBbCcF')
587
# Merge G & H by just combining texts
588
self.add_rev('root', 'I', ['G', 'H'], 'DaBbCcF')
589
# Merge G & H but supersede an old line in B
590
self.add_rev('root', 'J', ['H', 'G'], 'DaJbCcF')
591
plan = self.plan_merge_vf.plan_merge('I', 'J')
592
self.assertEqual([
593
('unchanged', 'D\n'),
594
('unchanged', 'a\n'),
595
('killed-b', 'B\n'),
596
('new-b', 'J\n'),
597
('unchanged', 'b\n'),
598
('unchanged', 'C\n'),
599
('unchanged', 'c\n'),
600
('unchanged', 'F\n')],
601
list(plan))
602
603
def test_plan_merge_tail_triple_ancestors(self):
604
# The graph looks like this:
605
# A # Common to all ancestors
606
# / \
607
# B C # Ancestors of E, only common to one side
608
# |\ /|
609
# D E F # D, F are unique to G, H respectively
610
# |/|\| # E is the LCA for G & H, and the unique LCA for
611
# G Q H # I, J
612
# |\ /| # Q is just an extra node which is merged into both
613
# | X | # I and J
614
# |/ \|
615
# I J # criss-cross merge of G, H
616
#
617
# This is the same as the test_plan_merge_tail_ancestors, except we add
618
# a third LCA that doesn't add new lines, but will trigger our more
619
# involved ancestry logic
620
621
self.add_rev('root', 'A', [], 'abc')
622
self.add_rev('root', 'B', ['A'], 'aBbc')
623
self.add_rev('root', 'C', ['A'], 'abCc')
624
self.add_rev('root', 'D', ['B'], 'DaBbc')
625
self.add_rev('root', 'E', ['B', 'C'], 'aBbCc')
626
self.add_rev('root', 'F', ['C'], 'abCcF')
627
self.add_rev('root', 'G', ['D', 'E'], 'DaBbCc')
628
self.add_rev('root', 'H', ['F', 'E'], 'aBbCcF')
629
self.add_rev('root', 'Q', ['E'], 'aBbCc')
630
self.add_rev('root', 'I', ['G', 'Q', 'H'], 'DaBbCcF')
631
# Merge G & H but supersede an old line in B
632
self.add_rev('root', 'J', ['H', 'Q', 'G'], 'DaJbCcF')
633
plan = self.plan_merge_vf.plan_merge('I', 'J')
634
self.assertEqual([
635
('unchanged', 'D\n'),
636
('unchanged', 'a\n'),
637
('killed-b', 'B\n'),
638
('new-b', 'J\n'),
639
('unchanged', 'b\n'),
640
('unchanged', 'C\n'),
641
('unchanged', 'c\n'),
642
('unchanged', 'F\n')],
643
list(plan))
644
645
def test_plan_merge_2_tail_triple_ancestors(self):
646
# The graph looks like this:
647
# A B # 2 tails going back to NULL
648
# |\ /|
649
# D E F # D, is unique to G, F to H
650
# |/|\| # E is the LCA for G & H, and the unique LCA for
651
# G Q H # I, J
652
# |\ /| # Q is just an extra node which is merged into both
653
# | X | # I and J
654
# |/ \|
655
# I J # criss-cross merge of G, H (and Q)
656
#
657
658
# This is meant to test after hitting a 3-way LCA, and multiple tail
659
# ancestors (only have NULL_REVISION in common)
660
661
self.add_rev('root', 'A', [], 'abc')
662
self.add_rev('root', 'B', [], 'def')
663
self.add_rev('root', 'D', ['A'], 'Dabc')
664
self.add_rev('root', 'E', ['A', 'B'], 'abcdef')
665
self.add_rev('root', 'F', ['B'], 'defF')
666
self.add_rev('root', 'G', ['D', 'E'], 'Dabcdef')
667
self.add_rev('root', 'H', ['F', 'E'], 'abcdefF')
668
self.add_rev('root', 'Q', ['E'], 'abcdef')
669
self.add_rev('root', 'I', ['G', 'Q', 'H'], 'DabcdefF')
670
# Merge G & H but supersede an old line in B
671
self.add_rev('root', 'J', ['H', 'Q', 'G'], 'DabcdJfF')
672
plan = self.plan_merge_vf.plan_merge('I', 'J')
673
self.assertEqual([
674
('unchanged', 'D\n'),
675
('unchanged', 'a\n'),
676
('unchanged', 'b\n'),
677
('unchanged', 'c\n'),
678
('unchanged', 'd\n'),
679
('killed-b', 'e\n'),
680
('new-b', 'J\n'),
681
('unchanged', 'f\n'),
682
('unchanged', 'F\n')],
535
683
list(plan))
536
684
537
685
def test_plan_merge_uncommitted_files(self):
540
688
self.assertEqual([
541
689
('new-b', 'f\n'),
542
690
('unchanged', 'a\n'),
691
('killed-a', 'b\n'),
543
692
('killed-b', 'c\n'),
544
693
('new-a', 'e\n'),
545
694
('new-a', 'h\n'),
546
('killed-a', 'b\n'),
695
('new-a', 'g\n'),
696
('new-b', 'g\n')],
697
list(plan))
698
699
def test_plan_merge_insert_order(self):
700
"""Weave merges are sensitive to the order of insertion.
701
702
Specifically for overlapping regions, it effects which region gets put
703
'first'. And when a user resolves an overlapping merge, if they use the
704
same ordering, then the lines match the parents, if they don't only
705
*some* of the lines match.
706
"""
707
self.add_rev('root', 'A', [], 'abcdef')
708
self.add_rev('root', 'B', ['A'], 'abwxcdef')
709
self.add_rev('root', 'C', ['A'], 'abyzcdef')
710
# Merge, and resolve the conflict by adding *both* sets of lines
711
# If we get the ordering wrong, these will look like new lines in D,
712
# rather than carried over from B, C
713
self.add_rev('root', 'D', ['B', 'C'],
714
'abwxyzcdef')
715
# Supersede the lines in B and delete the lines in C, which will
716
# conflict if they are treated as being in D
717
self.add_rev('root', 'E', ['C', 'B'],
718
'abnocdef')
719
# Same thing for the lines in C
720
self.add_rev('root', 'F', ['C'], 'abpqcdef')
721
plan = self.plan_merge_vf.plan_merge('D', 'E')
722
self.assertEqual([
723
('unchanged', 'a\n'),
724
('unchanged', 'b\n'),
725
('killed-b', 'w\n'),
726
('killed-b', 'x\n'),
727
('killed-b', 'y\n'),
728
('killed-b', 'z\n'),
729
('new-b', 'n\n'),
730
('new-b', 'o\n'),
731
('unchanged', 'c\n'),
732
('unchanged', 'd\n'),
733
('unchanged', 'e\n'),
734
('unchanged', 'f\n')],
735
list(plan))
736
plan = self.plan_merge_vf.plan_merge('E', 'D')
737
# Going in the opposite direction shows the effect of the opposite plan
738
self.assertEqual([
739
('unchanged', 'a\n'),
740
('unchanged', 'b\n'),
741
('new-b', 'w\n'),
742
('new-b', 'x\n'),
743
('killed-a', 'y\n'),
744
('killed-a', 'z\n'),
745
('killed-both', 'w\n'),
746
('killed-both', 'x\n'),
747
('new-a', 'n\n'),
748
('new-a', 'o\n'),
749
('unchanged', 'c\n'),
750
('unchanged', 'd\n'),
751
('unchanged', 'e\n'),
752
('unchanged', 'f\n')],
753
list(plan))
754
755
def test_plan_merge_criss_cross(self):
756
# This is specificly trying to trigger problems when using limited
757
# ancestry and weaves. The ancestry graph looks like:
758
# XX unused ancestor, should not show up in the weave
759
# |
760
# A Unique LCA
761
# |\
762
# B \ Introduces a line 'foo'
763
# / \ \
764
# C D E C & D both have 'foo', E has different changes
765
# |\ /| |
766
# | X | |
767
# |/ \|/
768
# F G All of C, D, E are merged into F and G, so they are
769
# all common ancestors.
770
#
771
# The specific issue with weaves:
772
# B introduced a text ('foo') that is present in both C and D.
773
# If we do not include B (because it isn't an ancestor of E), then
774
# the A=>C and A=>D look like both sides independently introduce the
775
# text ('foo'). If F does not modify the text, it would still appear
776
# to have deleted on of the versions from C or D. If G then modifies
777
# 'foo', it should appear as superseding the value in F (since it
778
# came from B), rather than conflict because of the resolution during
779
# C & D.
780
self.add_rev('root', 'XX', [], 'qrs')
781
self.add_rev('root', 'A', ['XX'], 'abcdef')
782
self.add_rev('root', 'B', ['A'], 'axcdef')
783
self.add_rev('root', 'C', ['B'], 'axcdefg')
784
self.add_rev('root', 'D', ['B'], 'haxcdef')
785
self.add_rev('root', 'E', ['A'], 'abcdyf')
786
# Simple combining of all texts
787
self.add_rev('root', 'F', ['C', 'D', 'E'], 'haxcdyfg')
788
# combine and supersede 'x'
789
self.add_rev('root', 'G', ['C', 'D', 'E'], 'hazcdyfg')
790
plan = self.plan_merge_vf.plan_merge('F', 'G')
791
self.assertEqual([
792
('unchanged', 'h\n'),
793
('unchanged', 'a\n'),
794
('killed-base', 'b\n'),
795
('killed-b', 'x\n'),
796
('new-b', 'z\n'),
797
('unchanged', 'c\n'),
798
('unchanged', 'd\n'),
799
('killed-base', 'e\n'),
800
('unchanged', 'y\n'),
801
('unchanged', 'f\n'),
547
802
('unchanged', 'g\n')],
548
803
list(plan))
549
804
805
def assertRemoveExternalReferences(self, filtered_parent_map,
806
child_map, tails, parent_map):
807
"""Assert results for _PlanMerge._remove_external_references."""
808
(act_filtered_parent_map, act_child_map,
809
act_tails) = _PlanMerge._remove_external_references(parent_map)
810
811
# The parent map *should* preserve ordering, but the ordering of
812
# children is not strictly defined
813
# child_map = dict((k, sorted(children))
814
# for k, children in child_map.iteritems())
815
# act_child_map = dict(k, sorted(children)
816
# for k, children in act_child_map.iteritems())
817
self.assertEqual(filtered_parent_map, act_filtered_parent_map)
818
self.assertEqual(child_map, act_child_map)
819
self.assertEqual(sorted(tails), sorted(act_tails))
820
821
def test__remove_external_references(self):
822
# First, nothing to remove
823
self.assertRemoveExternalReferences({3: [2], 2: [1], 1: []},
824
{1: [2], 2: [3], 3: []}, [1], {3: [2], 2: [1], 1: []})
825
# The reverse direction
826
self.assertRemoveExternalReferences({1: [2], 2: [3], 3: []},
827
{3: [2], 2: [1], 1: []}, [3], {1: [2], 2: [3], 3: []})
828
# Extra references
829
self.assertRemoveExternalReferences({3: [2], 2: [1], 1: []},
830
{1: [2], 2: [3], 3: []}, [1], {3: [2, 4], 2: [1, 5], 1: [6]})
831
# Multiple tails
832
self.assertRemoveExternalReferences(
833
{4: [2, 3], 3: [], 2: [1], 1: []},
834
{1: [2], 2: [4], 3: [4], 4: []},
835
[1, 3],
836
{4: [2, 3], 3: [5], 2: [1], 1: [6]})
837
# Multiple children
838
self.assertRemoveExternalReferences(
839
{1: [3], 2: [3, 4], 3: [], 4: []},
840
{1: [], 2: [], 3: [1, 2], 4: [2]},
841
[3, 4],
842
{1: [3], 2: [3, 4], 3: [5], 4: []})
843
844
def assertPruneTails(self, pruned_map, tails, parent_map):
845
child_map = {}
846
for key, parent_keys in parent_map.iteritems():
847
child_map.setdefault(key, [])
848
for pkey in parent_keys:
849
child_map.setdefault(pkey, []).append(key)
850
_PlanMerge._prune_tails(parent_map, child_map, tails)
851
self.assertEqual(pruned_map, parent_map)
852
853
def test__prune_tails(self):
854
# Nothing requested to prune
855
self.assertPruneTails({1: [], 2: [], 3: []}, [],
856
{1: [], 2: [], 3: []})
857
# Prune a single entry
858
self.assertPruneTails({1: [], 3: []}, [2],
859
{1: [], 2: [], 3: []})
860
# Prune a chain
861
self.assertPruneTails({1: []}, [3],
862
{1: [], 2: [3], 3: []})
863
# Prune a chain with a diamond
864
self.assertPruneTails({1: []}, [5],
865
{1: [], 2: [3, 4], 3: [5], 4: [5], 5: []})
866
# Prune a partial chain
867
self.assertPruneTails({1: [6], 6:[]}, [5],
868
{1: [2, 6], 2: [3, 4], 3: [5], 4: [5], 5: [],
869
6: []})
870
# Prune a chain with multiple tips, that pulls out intermediates
871
self.assertPruneTails({1:[3], 3:[]}, [4, 5],
872
{1: [2, 3], 2: [4, 5], 3: [], 4:[], 5:[]})
873
self.assertPruneTails({1:[3], 3:[]}, [5, 4],
874
{1: [2, 3], 2: [4, 5], 3: [], 4:[], 5:[]})
875
550
876
def test_subtract_plans(self):
551
877
old_plan = [
552
878
('unchanged', 'a\n'),
578
904
list(_PlanMerge._subtract_plans(old_plan, new_plan)))
579
905
580
906
def setup_merge_with_base(self):
581
self.add_version(('root', 'COMMON'), [], 'abc')
582
self.add_version(('root', 'THIS'), [('root', 'COMMON')], 'abcd')
583
self.add_version(('root', 'BASE'), [('root', 'COMMON')], 'eabc')
584
self.add_version(('root', 'OTHER'), [('root', 'BASE')], 'eafb')
907
self.add_rev('root', 'COMMON', [], 'abc')
908
self.add_rev('root', 'THIS', ['COMMON'], 'abcd')
909
self.add_rev('root', 'BASE', ['COMMON'], 'eabc')
910
self.add_rev('root', 'OTHER', ['BASE'], 'eafb')
585
911
586
912
def test_plan_merge_with_base(self):
587
913
self.setup_merge_with_base()
657
983
('new-b', 'c\n'),
658
984
], list(plan))
659
985
986
def test_plan_merge_with_delete_and_change(self):
987
self.add_rev('root', 'C', [], 'a')
988
self.add_rev('root', 'A', ['C'], 'b')
989
self.add_rev('root', 'B', ['C'], '')
990
plan = self.plan_merge_vf.plan_merge('A', 'B')
991
self.assertEqual([('killed-both', 'a\n'),
992
('new-a', 'b\n'),
993
], list(plan))
994
995
def test_plan_merge_with_move_and_change(self):
996
self.add_rev('root', 'C', [], 'abcd')
997
self.add_rev('root', 'A', ['C'], 'acbd')
998
self.add_rev('root', 'B', ['C'], 'aBcd')
999
plan = self.plan_merge_vf.plan_merge('A', 'B')
1000
self.assertEqual([('unchanged', 'a\n'),
1001
('new-a', 'c\n'),
1002
('killed-b', 'b\n'),
1003
('new-b', 'B\n'),
1004
('killed-a', 'c\n'),
1005
('unchanged', 'd\n'),
1006
], list(plan))
1007
660
1008
661
1009
class TestMergeImplementation(object):
662
1010
694
1042
self.assertFileEqual('d\na\nb\nc\n', 'this/file1')
695
1043
self.assertFileEqual('d\na\nb\n', 'this/file2')
696
1044
1045
def test_merge_move_and_change(self):
1046
this_tree = self.make_branch_and_tree('this')
1047
this_tree.lock_write()
1048
self.addCleanup(this_tree.unlock)
1049
self.build_tree_contents([
1050
('this/file1', 'line 1\nline 2\nline 3\nline 4\n'),
1051
])
1052
this_tree.add('file1',)
1053
this_tree.commit('Added file')
1054
other_tree = this_tree.bzrdir.sprout('other').open_workingtree()
1055
self.build_tree_contents([
1056
('other/file1', 'line 1\nline 2 to 2.1\nline 3\nline 4\n'),
1057
])
1058
other_tree.commit('Changed 2 to 2.1')
1059
self.build_tree_contents([
1060
('this/file1', 'line 1\nline 3\nline 2\nline 4\n'),
1061
])
1062
this_tree.commit('Swapped 2 & 3')
1063
self.do_merge(this_tree, other_tree)
1064
self.assertFileEqual('line 1\n'
1065
'<<<<<<< TREE\n'
1066
'line 3\n'
1067
'line 2\n'
1068
'=======\n'
1069
'line 2 to 2.1\n'
1070
'line 3\n'
1071
'>>>>>>> MERGE-SOURCE\n'
1072
'line 4\n', 'this/file1')
1073
697
1074
698
1075
class TestMerge3Merge(TestCaseWithTransport, TestMergeImplementation):
699
1076
708
1085
class TestLCAMerge(TestCaseWithTransport, TestMergeImplementation):
709
1086
710
1087
merge_type = _mod_merge.LCAMerger
1088
1089
def test_merge_move_and_change(self):
1090
self.expectFailure("lca merge doesn't conflict for move and change",
1091
super(TestLCAMerge, self).test_merge_move_and_change)
Loggerhead is a web-based interface for Breezy
Version: 2.0.1