3
# Copyright (C) 2005 by Canonical Ltd
5
# This program is free software; you can redistribute it and/or modify
6
# it under the terms of the GNU General Public License as published by
7
# the Free Software Foundation; either version 2 of the License, or
8
# (at your option) any later version.
10
# This program is distributed in the hope that it will be useful,
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
# GNU General Public License for more details.
15
# You should have received a copy of the GNU General Public License
16
# along with this program; if not, write to the Free Software
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
# TODO: tests regarding version names
21
# TODO: rbc 20050108 test that join does not leave an inconsistent weave
24
"""test suite for weave algorithm"""
26
from pprint import pformat
28
import bzrlib.errors as errors
29
from bzrlib.weave import Weave, WeaveFormatError, WeaveError, reweave
30
from bzrlib.weavefile import write_weave, read_weave
31
from bzrlib.tests import TestCase
32
from bzrlib.osutils import sha_string
35
# texts for use in testing
36
TEXT_0 = ["Hello world"]
37
TEXT_1 = ["Hello world",
41
class TestBase(TestCase):
42
def check_read_write(self, k):
43
"""Check the weave k can be written & re-read."""
44
from tempfile import TemporaryFile
53
self.log('serialized weave:')
57
self.log('parents: %s' % (k._parents == k2._parents))
58
self.log(' %r' % k._parents)
59
self.log(' %r' % k2._parents)
61
self.fail('read/write check failed')
64
class WeaveContains(TestBase):
65
"""Weave __contains__ operator"""
68
self.assertFalse('foo' in k)
69
k.add_lines('foo', [], TEXT_1)
70
self.assertTrue('foo' in k)
78
class StoreText(TestBase):
79
"""Store and retrieve a simple text."""
82
idx = k.add_lines('text0', [], TEXT_0)
83
self.assertEqual(k.get_lines(idx), TEXT_0)
84
self.assertEqual(idx, 0)
87
class AnnotateOne(TestBase):
90
k.add_lines('text0', [], TEXT_0)
91
self.assertEqual(k.annotate('text0'),
92
[('text0', TEXT_0[0])])
95
class StoreTwo(TestBase):
99
idx = k.add_lines('text0', [], TEXT_0)
100
self.assertEqual(idx, 0)
102
idx = k.add_lines('text1', [], TEXT_1)
103
self.assertEqual(idx, 1)
105
self.assertEqual(k.get_lines(0), TEXT_0)
106
self.assertEqual(k.get_lines(1), TEXT_1)
109
class GetSha1(TestBase):
110
def test_get_sha1(self):
112
k.add_lines('text0', [], 'text0')
113
self.assertEqual('34dc0e430c642a26c3dd1c2beb7a8b4f4445eb79',
115
self.assertRaises(errors.RevisionNotPresent,
117
self.assertRaises(errors.RevisionNotPresent,
121
class InvalidAdd(TestBase):
122
"""Try to use invalid version number during add."""
126
self.assertRaises(errors.RevisionNotPresent,
133
class RepeatedAdd(TestBase):
134
"""Add the same version twice; harmless."""
137
idx = k.add_lines('text0', [], TEXT_0)
138
idx2 = k.add_lines('text0', [], TEXT_0)
139
self.assertEqual(idx, idx2)
142
class InvalidRepeatedAdd(TestBase):
145
k.add_lines('basis', [], TEXT_0)
146
idx = k.add_lines('text0', [], TEXT_0)
147
self.assertRaises(errors.RevisionAlreadyPresent,
151
['not the same text'])
152
self.assertRaises(errors.RevisionAlreadyPresent,
155
['basis'], # not the right parents
159
class InsertLines(TestBase):
160
"""Store a revision that adds one line to the original.
162
Look at the annotations to make sure that the first line is matched
163
and not stored repeatedly."""
167
k.add_lines('text0', [], ['line 1'])
168
k.add_lines('text1', ['text0'], ['line 1', 'line 2'])
170
self.assertEqual(k.annotate('text0'),
171
[('text0', 'line 1')])
173
self.assertEqual(k.get_lines(1),
177
self.assertEqual(k.annotate('text1'),
178
[('text0', 'line 1'),
179
('text1', 'line 2')])
181
k.add_lines('text2', ['text0'], ['line 1', 'diverged line'])
183
self.assertEqual(k.annotate('text2'),
184
[('text0', 'line 1'),
185
('text2', 'diverged line')])
187
text3 = ['line 1', 'middle line', 'line 2']
192
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
194
self.log("k._weave=" + pformat(k._weave))
196
self.assertEqual(k.annotate('text3'),
197
[('text0', 'line 1'),
198
('text3', 'middle line'),
199
('text1', 'line 2')])
201
# now multiple insertions at different places
203
['text0', 'text1', 'text3'],
204
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
206
self.assertEqual(k.annotate('text4'),
207
[('text0', 'line 1'),
209
('text3', 'middle line'),
215
class DeleteLines(TestBase):
216
"""Deletion of lines from existing text.
218
Try various texts all based on a common ancestor."""
222
base_text = ['one', 'two', 'three', 'four']
224
k.add_lines('text0', [], base_text)
226
texts = [['one', 'two', 'three'],
227
['two', 'three', 'four'],
229
['one', 'two', 'three', 'four'],
234
ver = k.add_lines('text%d' % i,
238
self.log('final weave:')
239
self.log('k._weave=' + pformat(k._weave))
241
for i in range(len(texts)):
242
self.assertEqual(k.get_lines(i+1),
246
class SuicideDelete(TestBase):
247
"""Invalid weave which tries to add and delete simultaneously."""
253
k._weave = [('{', 0),
260
################################### SKIPPED
261
# Weave.get doesn't trap this anymore
264
self.assertRaises(WeaveFormatError,
269
class CannedDelete(TestBase):
270
"""Unpack canned weave with deleted lines."""
277
k._weave = [('{', 0),
280
'line to be deleted',
285
k._sha1s = [sha_string('first lineline to be deletedlast line')
286
, sha_string('first linelast line')]
288
self.assertEqual(k.get_lines(0),
290
'line to be deleted',
294
self.assertEqual(k.get_lines(1),
300
class CannedReplacement(TestBase):
301
"""Unpack canned weave with deleted lines."""
305
k._parents = [frozenset(),
308
k._weave = [('{', 0),
311
'line to be deleted',
319
k._sha1s = [sha_string('first lineline to be deletedlast line')
320
, sha_string('first linereplacement linelast line')]
322
self.assertEqual(k.get_lines(0),
324
'line to be deleted',
328
self.assertEqual(k.get_lines(1),
335
class BadWeave(TestBase):
336
"""Test that we trap an insert which should not occur."""
340
k._parents = [frozenset(),
342
k._weave = ['bad line',
346
' added in version 1',
355
################################### SKIPPED
356
# Weave.get doesn't trap this anymore
360
self.assertRaises(WeaveFormatError,
365
class BadInsert(TestBase):
366
"""Test that we trap an insert which should not occur."""
370
k._parents = [frozenset(),
375
k._weave = [('{', 0),
378
' added in version 1',
386
# this is not currently enforced by get
387
return ##########################################
389
self.assertRaises(WeaveFormatError,
393
self.assertRaises(WeaveFormatError,
398
class InsertNested(TestBase):
399
"""Insertion with nested instructions."""
403
k._parents = [frozenset(),
408
k._weave = [('{', 0),
411
' added in version 1',
420
k._sha1s = [sha_string('foo {}')
421
, sha_string('foo { added in version 1 also from v1}')
422
, sha_string('foo { added in v2}')
423
, sha_string('foo { added in version 1 added in v2 also from v1}')
426
self.assertEqual(k.get_lines(0),
430
self.assertEqual(k.get_lines(1),
432
' added in version 1',
436
self.assertEqual(k.get_lines(2),
441
self.assertEqual(k.get_lines(3),
443
' added in version 1',
449
class DeleteLines2(TestBase):
450
"""Test recording revisions that delete lines.
452
This relies on the weave having a way to represent lines knocked
453
out by a later revision."""
457
k.add_lines('text0', [], ["line the first",
462
self.assertEqual(len(k.get_lines(0)), 4)
464
k.add_lines('text1', ['text0'], ["line the first",
467
self.assertEqual(k.get_lines(1),
471
self.assertEqual(k.annotate('text1'),
472
[('text0', "line the first"),
476
class IncludeVersions(TestBase):
477
"""Check texts that are stored across multiple revisions.
479
Here we manually create a weave with particular encoding and make
480
sure it unpacks properly.
482
Text 0 includes nothing; text 1 includes text 0 and adds some
489
k._parents = [frozenset(), frozenset([0])]
490
k._weave = [('{', 0),
497
k._sha1s = [sha_string('first line')
498
, sha_string('first linesecond line')]
500
self.assertEqual(k.get_lines(1),
504
self.assertEqual(k.get_lines(0),
508
class DivergedIncludes(TestBase):
509
"""Weave with two diverged texts based on version 0.
512
# FIXME make the weave, dont poke at it.
515
k._names = ['0', '1', '2']
516
k._name_map = {'0':0, '1':1, '2':2}
517
k._parents = [frozenset(),
521
k._weave = [('{', 0),
528
"alternative second line",
532
k._sha1s = [sha_string('first line')
533
, sha_string('first linesecond line')
534
, sha_string('first linealternative second line')]
536
self.assertEqual(k.get_lines(0),
539
self.assertEqual(k.get_lines(1),
543
self.assertEqual(k.get_lines('2'),
545
"alternative second line"])
547
self.assertEqual(list(k.get_ancestry(['2'])),
551
class ReplaceLine(TestBase):
555
text0 = ['cheddar', 'stilton', 'gruyere']
556
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
558
k.add_lines('text0', [], text0)
559
k.add_lines('text1', ['text0'], text1)
561
self.log('k._weave=' + pformat(k._weave))
563
self.assertEqual(k.get_lines(0), text0)
564
self.assertEqual(k.get_lines(1), text1)
567
class Merge(TestBase):
568
"""Storage of versions that merge diverged parents"""
573
['header', '', 'line from 1'],
574
['header', '', 'line from 2', 'more from 2'],
575
['header', '', 'line from 1', 'fixup line', 'line from 2'],
578
k.add_lines('text0', [], texts[0])
579
k.add_lines('text1', ['text0'], texts[1])
580
k.add_lines('text2', ['text0'], texts[2])
581
k.add_lines('merge', ['text0', 'text1', 'text2'], texts[3])
583
for i, t in enumerate(texts):
584
self.assertEqual(k.get_lines(i), t)
586
self.assertEqual(k.annotate('merge'),
587
[('text0', 'header'),
589
('text1', 'line from 1'),
590
('merge', 'fixup line'),
591
('text2', 'line from 2'),
594
self.assertEqual(list(k.get_ancestry(['merge'])),
595
['text0', 'text1', 'text2', 'merge'])
597
self.log('k._weave=' + pformat(k._weave))
599
self.check_read_write(k)
602
class Conflicts(TestBase):
603
"""Test detection of conflicting regions during a merge.
605
A base version is inserted, then two descendents try to
606
insert different lines in the same place. These should be
607
reported as a possible conflict and forwarded to the user."""
612
k.add_lines([], ['aaa', 'bbb'])
613
k.add_lines([0], ['aaa', '111', 'bbb'])
614
k.add_lines([1], ['aaa', '222', 'bbb'])
616
merged = k.merge([1, 2])
618
self.assertEquals([[['aaa']],
623
class NonConflict(TestBase):
624
"""Two descendants insert compatible changes.
626
No conflict should be reported."""
631
k.add_lines([], ['aaa', 'bbb'])
632
k.add_lines([0], ['111', 'aaa', 'ccc', 'bbb'])
633
k.add_lines([1], ['aaa', 'ccc', 'bbb', '222'])
636
class Khayyam(TestBase):
637
"""Test changes to multi-line texts, and read/write"""
639
def test_multi_line_merge(self):
641
"""A Book of Verses underneath the Bough,
642
A Jug of Wine, a Loaf of Bread, -- and Thou
643
Beside me singing in the Wilderness --
644
Oh, Wilderness were Paradise enow!""",
646
"""A Book of Verses underneath the Bough,
647
A Jug of Wine, a Loaf of Bread, -- and Thou
648
Beside me singing in the Wilderness --
649
Oh, Wilderness were Paradise now!""",
651
"""A Book of poems underneath the tree,
652
A Jug of Wine, a Loaf of Bread,
654
Beside me singing in the Wilderness --
655
Oh, Wilderness were Paradise now!
659
"""A Book of Verses underneath the Bough,
660
A Jug of Wine, a Loaf of Bread,
662
Beside me singing in the Wilderness --
663
Oh, Wilderness were Paradise now!""",
665
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
671
ver = k.add_lines('text%d' % i,
673
parents.add('text%d' % i)
676
self.log("k._weave=" + pformat(k._weave))
678
for i, t in enumerate(texts):
679
self.assertEqual(k.get_lines(i), t)
681
self.check_read_write(k)
684
class MergeCases(TestBase):
685
def doMerge(self, base, a, b, mp):
686
from cStringIO import StringIO
687
from textwrap import dedent
693
w.add_lines('text0', [], map(addcrlf, base))
694
w.add_lines('text1', ['text0'], map(addcrlf, a))
695
w.add_lines('text2', ['text0'], map(addcrlf, b))
697
self.log('weave is:')
700
self.log(tmpf.getvalue())
702
self.log('merge plan:')
703
p = list(w.plan_merge('text1', 'text2'))
704
for state, line in p:
706
self.log('%12s | %s' % (state, line[:-1]))
710
mt.writelines(w.weave_merge(p))
712
self.log(mt.getvalue())
714
mp = map(addcrlf, mp)
715
self.assertEqual(mt.readlines(), mp)
718
def testOneInsert(self):
724
def testSeparateInserts(self):
725
self.doMerge(['aaa', 'bbb', 'ccc'],
726
['aaa', 'xxx', 'bbb', 'ccc'],
727
['aaa', 'bbb', 'yyy', 'ccc'],
728
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
730
def testSameInsert(self):
731
self.doMerge(['aaa', 'bbb', 'ccc'],
732
['aaa', 'xxx', 'bbb', 'ccc'],
733
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
734
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
736
def testOverlappedInsert(self):
737
self.doMerge(['aaa', 'bbb'],
738
['aaa', 'xxx', 'yyy', 'bbb'],
739
['aaa', 'xxx', 'bbb'],
740
['aaa', '<<<<<<< ', 'xxx', 'yyy', '=======', 'xxx',
743
# really it ought to reduce this to
744
# ['aaa', 'xxx', 'yyy', 'bbb']
747
def testClashReplace(self):
748
self.doMerge(['aaa'],
751
['<<<<<<< ', 'xxx', '=======', 'yyy', 'zzz',
754
def testNonClashInsert(self):
755
self.doMerge(['aaa'],
758
['<<<<<<< ', 'xxx', 'aaa', '=======', 'yyy', 'zzz',
761
self.doMerge(['aaa'],
767
def testDeleteAndModify(self):
768
"""Clashing delete and modification.
770
If one side modifies a region and the other deletes it then
771
there should be a conflict with one side blank.
774
#######################################
775
# skippd, not working yet
778
self.doMerge(['aaa', 'bbb', 'ccc'],
779
['aaa', 'ddd', 'ccc'],
781
['<<<<<<<< ', 'aaa', '=======', '>>>>>>> ', 'ccc'])
784
class JoinWeavesTests(TestBase):
786
super(JoinWeavesTests, self).setUp()
787
self.weave1 = Weave()
788
self.lines1 = ['hello\n']
789
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
790
self.weave1.add_lines('v1', [], self.lines1)
791
self.weave1.add_lines('v2', ['v1'], ['hello\n', 'world\n'])
792
self.weave1.add_lines('v3', ['v2'], self.lines3)
794
def test_join_empty(self):
795
"""Join two empty weaves."""
796
eq = self.assertEqual
802
def test_join_empty_to_nonempty(self):
803
"""Join empty weave onto nonempty."""
804
self.weave1.join(Weave())
805
self.assertEqual(len(self.weave1), 3)
807
def test_join_unrelated(self):
808
"""Join two weaves with no history in common."""
810
wb.add_lines('b1', [], ['line from b\n'])
813
eq = self.assertEqual
815
eq(sorted(w1.versions()),
816
['b1', 'v1', 'v2', 'v3'])
818
def test_join_related(self):
819
wa = self.weave1.copy()
820
wb = self.weave1.copy()
821
wa.add_lines('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
822
wb.add_lines('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
823
eq = self.assertEquals
828
eq(wa.get_lines('b1'),
829
['hello\n', 'pale blue\n', 'world\n'])
831
def test_join_parent_disagreement(self):
832
#join reconciles differening parents into a union.
835
wa.add_lines('v1', [], ['hello\n'])
836
wb.add_lines('v0', [], [])
837
wb.add_lines('v1', ['v0'], ['hello\n'])
839
self.assertEqual(['v0'], wa.get_parents('v1'))
841
def test_join_text_disagreement(self):
842
"""Cannot join weaves with different texts for a version."""
845
wa.add_lines('v1', [], ['hello\n'])
846
wb.add_lines('v1', [], ['not\n', 'hello\n'])
847
self.assertRaises(WeaveError,
850
def test_join_unordered(self):
851
"""Join weaves where indexes differ.
853
The source weave contains a different version at index 0."""
854
wa = self.weave1.copy()
856
wb.add_lines('x1', [], ['line from x1\n'])
857
wb.add_lines('v1', [], ['hello\n'])
858
wb.add_lines('v2', ['v1'], ['hello\n', 'world\n'])
860
eq = self.assertEquals
861
eq(sorted(wa.versions()), ['v1', 'v2', 'v3', 'x1',])
862
eq(wa.get_text('x1'), 'line from x1\n')
864
def test_written_detection(self):
865
# Test detection of weave file corruption.
867
# Make sure that we can detect if a weave file has
868
# been corrupted. This doesn't test all forms of corruption,
869
# but it at least helps verify the data you get, is what you want.
870
from cStringIO import StringIO
873
w.add_lines('v1', [], ['hello\n'])
874
w.add_lines('v2', ['v1'], ['hello\n', 'there\n'])
879
# Because we are corrupting, we need to make sure we have the exact text
880
self.assertEquals('# bzr weave file v5\n'
881
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
882
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
883
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n',
886
# Change a single letter
887
tmpf = StringIO('# bzr weave file v5\n'
888
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
889
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
890
'w\n{ 0\n. hello\n}\n{ 1\n. There\n}\nW\n')
894
self.assertEqual('hello\n', w.get_text('v1'))
895
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
896
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
897
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
899
# Change the sha checksum
900
tmpf = StringIO('# bzr weave file v5\n'
901
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
902
'i 0\n1 f0f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
903
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n')
907
self.assertEqual('hello\n', w.get_text('v1'))
908
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
909
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
910
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
913
class InstrumentedWeave(Weave):
914
"""Keep track of how many times functions are called."""
916
def __init__(self, weave_name=None):
917
self._extract_count = 0
918
Weave.__init__(self, weave_name=weave_name)
920
def _extract(self, versions):
921
self._extract_count += 1
922
return Weave._extract(self, versions)
925
class JoinOptimization(TestCase):
926
"""Test that Weave.join() doesn't extract all texts, only what must be done."""
929
w1 = InstrumentedWeave()
930
w2 = InstrumentedWeave()
933
txt1 = ['a\n', 'b\n']
934
txt2 = ['a\n', 'c\n']
935
txt3 = ['a\n', 'b\n', 'c\n']
937
w1.add_lines('txt0', [], txt0) # extract 1a
938
w2.add_lines('txt0', [], txt0) # extract 1b
939
w1.add_lines('txt1', ['txt0'], txt1)# extract 2a
940
w2.add_lines('txt2', ['txt0'], txt2)# extract 2b
941
w1.join(w2) # extract 3a to add txt2
942
w2.join(w1) # extract 3b to add txt1
944
w1.add_lines('txt3', ['txt1', 'txt2'], txt3) # extract 4a
945
w2.add_lines('txt3', ['txt2', 'txt1'], txt3) # extract 4b
946
# These secretly have inverted parents
948
# This should not have to do any extractions
949
w1.join(w2) # NO extract, texts already present with same parents
950
w2.join(w1) # NO extract, texts already present with same parents
952
self.assertEqual(4, w1._extract_count)
953
self.assertEqual(4, w2._extract_count)
955
def test_double_parent(self):
956
# It should not be considered illegal to add
957
# a revision with the same parent twice
958
w1 = InstrumentedWeave()
959
w2 = InstrumentedWeave()
962
txt1 = ['a\n', 'b\n']
963
txt2 = ['a\n', 'c\n']
964
txt3 = ['a\n', 'b\n', 'c\n']
966
w1.add_lines('txt0', [], txt0)
967
w2.add_lines('txt0', [], txt0)
968
w1.add_lines('txt1', ['txt0'], txt1)
969
w2.add_lines('txt1', ['txt0', 'txt0'], txt1)
970
# Same text, effectively the same, because the
971
# parent is only repeated
972
w1.join(w2) # extract 3a to add txt2
973
w2.join(w1) # extract 3b to add txt1
976
class TestNeedsRweave(TestCase):
977
"""Internal corner cases for when reweave is needed."""
979
def test_compatible_parents(self):
981
my_parents = set([1, 2, 3])
983
self.assertTrue(w1._compatible_parents(my_parents, set([3])))
985
self.assertTrue(w1._compatible_parents(my_parents, set(my_parents)))
986
# same empty corner case
987
self.assertTrue(w1._compatible_parents(set(), set()))
988
# other cannot contain stuff my_parents does not
989
self.assertFalse(w1._compatible_parents(set(), set([1])))
990
self.assertFalse(w1._compatible_parents(my_parents, set([1, 2, 3, 4])))
991
self.assertFalse(w1._compatible_parents(my_parents, set([4])))
added
removed
bzrlib/tests/test_weave.py
