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('foo', [], TEXT_1)
70
self.assertTrue('foo' in k)
78
class StoreText(TestBase):
79
"""Store and retrieve a simple text."""
82
idx = k.add('text0', [], TEXT_0)
83
self.assertEqual(k.get(idx), TEXT_0)
84
self.assertEqual(idx, 0)
87
class AnnotateOne(TestBase):
90
k.add('text0', [], TEXT_0)
91
self.assertEqual(k.annotate(0),
95
class StoreTwo(TestBase):
99
idx = k.add('text0', [], TEXT_0)
100
self.assertEqual(idx, 0)
102
idx = k.add('text1', [], TEXT_1)
103
self.assertEqual(idx, 1)
105
self.assertEqual(k.get(0), TEXT_0)
106
self.assertEqual(k.get(1), TEXT_1)
109
class AddWithGivenSha(TestBase):
111
"""Add with caller-supplied SHA-1"""
115
k.add('text0', [], [t], sha1=sha_string(t))
118
class GetSha1(TestBase):
119
def test_get_sha1(self):
121
k.add('text0', [], 'text0')
122
self.assertEqual('34dc0e430c642a26c3dd1c2beb7a8b4f4445eb79',
124
self.assertRaises(errors.RevisionNotPresent,
126
self.assertRaises(errors.RevisionNotPresent,
130
class InvalidAdd(TestBase):
131
"""Try to use invalid version number during add."""
135
self.assertRaises(IndexError,
142
class RepeatedAdd(TestBase):
143
"""Add the same version twice; harmless."""
146
idx = k.add('text0', [], TEXT_0)
147
idx2 = k.add('text0', [], TEXT_0)
148
self.assertEqual(idx, idx2)
151
class InvalidRepeatedAdd(TestBase):
154
idx = k.add('text0', [], TEXT_0)
155
self.assertRaises(errors.RevisionAlreadyPresent,
159
['not the same text'])
160
self.assertRaises(errors.RevisionAlreadyPresent,
163
[12], # not the right parents
167
class InsertLines(TestBase):
168
"""Store a revision that adds one line to the original.
170
Look at the annotations to make sure that the first line is matched
171
and not stored repeatedly."""
175
k.add('text0', [], ['line 1'])
176
k.add('text1', [0], ['line 1', 'line 2'])
178
self.assertEqual(k.annotate(0),
181
self.assertEqual(k.get(1),
185
self.assertEqual(k.annotate(1),
189
k.add('text2', [0], ['line 1', 'diverged line'])
191
self.assertEqual(k.annotate(2),
193
(2, 'diverged line')])
195
text3 = ['line 1', 'middle line', 'line 2']
200
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
202
self.log("k._weave=" + pformat(k._weave))
204
self.assertEqual(k.annotate(3),
209
# now multiple insertions at different places
212
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
214
self.assertEqual(k.annotate(4),
223
class DeleteLines(TestBase):
224
"""Deletion of lines from existing text.
226
Try various texts all based on a common ancestor."""
230
base_text = ['one', 'two', 'three', 'four']
232
k.add('text0', [], base_text)
234
texts = [['one', 'two', 'three'],
235
['two', 'three', 'four'],
237
['one', 'two', 'three', 'four'],
242
ver = k.add('text%d' % i,
246
self.log('final weave:')
247
self.log('k._weave=' + pformat(k._weave))
249
for i in range(len(texts)):
250
self.assertEqual(k.get(i+1),
254
class SuicideDelete(TestBase):
255
"""Invalid weave which tries to add and delete simultaneously."""
261
k._weave = [('{', 0),
268
################################### SKIPPED
269
# Weave.get doesn't trap this anymore
272
self.assertRaises(WeaveFormatError,
277
class CannedDelete(TestBase):
278
"""Unpack canned weave with deleted lines."""
285
k._weave = [('{', 0),
288
'line to be deleted',
293
k._sha1s = [sha_string('first lineline to be deletedlast line')
294
, sha_string('first linelast line')]
296
self.assertEqual(k.get(0),
298
'line to be deleted',
302
self.assertEqual(k.get(1),
308
class CannedReplacement(TestBase):
309
"""Unpack canned weave with deleted lines."""
313
k._parents = [frozenset(),
316
k._weave = [('{', 0),
319
'line to be deleted',
327
k._sha1s = [sha_string('first lineline to be deletedlast line')
328
, sha_string('first linereplacement linelast line')]
330
self.assertEqual(k.get(0),
332
'line to be deleted',
336
self.assertEqual(k.get(1),
343
class BadWeave(TestBase):
344
"""Test that we trap an insert which should not occur."""
348
k._parents = [frozenset(),
350
k._weave = ['bad line',
354
' added in version 1',
363
################################### SKIPPED
364
# Weave.get doesn't trap this anymore
368
self.assertRaises(WeaveFormatError,
373
class BadInsert(TestBase):
374
"""Test that we trap an insert which should not occur."""
378
k._parents = [frozenset(),
383
k._weave = [('{', 0),
386
' added in version 1',
394
# this is not currently enforced by get
395
return ##########################################
397
self.assertRaises(WeaveFormatError,
401
self.assertRaises(WeaveFormatError,
406
class InsertNested(TestBase):
407
"""Insertion with nested instructions."""
411
k._parents = [frozenset(),
416
k._weave = [('{', 0),
419
' added in version 1',
428
k._sha1s = [sha_string('foo {}')
429
, sha_string('foo { added in version 1 also from v1}')
430
, sha_string('foo { added in v2}')
431
, sha_string('foo { added in version 1 added in v2 also from v1}')
434
self.assertEqual(k.get(0),
438
self.assertEqual(k.get(1),
440
' added in version 1',
444
self.assertEqual(k.get(2),
449
self.assertEqual(k.get(3),
451
' added in version 1',
457
class DeleteLines2(TestBase):
458
"""Test recording revisions that delete lines.
460
This relies on the weave having a way to represent lines knocked
461
out by a later revision."""
465
k.add('text0', [], ["line the first",
470
self.assertEqual(len(k.get(0)), 4)
472
k.add('text1', [0], ["line the first",
475
self.assertEqual(k.get(1),
479
self.assertEqual(k.annotate(1),
480
[(0, "line the first"),
484
class IncludeVersions(TestBase):
485
"""Check texts that are stored across multiple revisions.
487
Here we manually create a weave with particular encoding and make
488
sure it unpacks properly.
490
Text 0 includes nothing; text 1 includes text 0 and adds some
497
k._parents = [frozenset(), frozenset([0])]
498
k._weave = [('{', 0),
505
k._sha1s = [sha_string('first line')
506
, sha_string('first linesecond line')]
508
self.assertEqual(k.get(1),
512
self.assertEqual(k.get(0),
516
class DivergedIncludes(TestBase):
517
"""Weave with two diverged texts based on version 0.
520
# FIXME make the weave, dont poke at it.
523
k._names = ['0', '1', '2']
524
k._parents = [frozenset(),
528
k._weave = [('{', 0),
535
"alternative second line",
539
k._sha1s = [sha_string('first line')
540
, sha_string('first linesecond line')
541
, sha_string('first linealternative second line')]
543
self.assertEqual(k.get(0),
546
self.assertEqual(k.get(1),
550
self.assertEqual(k.get(2),
552
"alternative second line"])
554
self.assertEqual(list(k.inclusions([2])),
558
class ReplaceLine(TestBase):
562
text0 = ['cheddar', 'stilton', 'gruyere']
563
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
565
k.add('text0', [], text0)
566
k.add('text1', [0], text1)
568
self.log('k._weave=' + pformat(k._weave))
570
self.assertEqual(k.get(0), text0)
571
self.assertEqual(k.get(1), text1)
574
class Merge(TestBase):
575
"""Storage of versions that merge diverged parents"""
580
['header', '', 'line from 1'],
581
['header', '', 'line from 2', 'more from 2'],
582
['header', '', 'line from 1', 'fixup line', 'line from 2'],
585
k.add('text0', [], texts[0])
586
k.add('text1', [0], texts[1])
587
k.add('text2', [0], texts[2])
588
k.add('merge', [0, 1, 2], texts[3])
590
for i, t in enumerate(texts):
591
self.assertEqual(k.get(i), t)
593
self.assertEqual(k.annotate(3),
601
self.assertEqual(list(k.inclusions([3])),
602
['text0', 'text1', 'text2', 'merge'])
604
self.log('k._weave=' + pformat(k._weave))
606
self.check_read_write(k)
609
class Conflicts(TestBase):
610
"""Test detection of conflicting regions during a merge.
612
A base version is inserted, then two descendents try to
613
insert different lines in the same place. These should be
614
reported as a possible conflict and forwarded to the user."""
619
k.add([], ['aaa', 'bbb'])
620
k.add([0], ['aaa', '111', 'bbb'])
621
k.add([1], ['aaa', '222', 'bbb'])
623
merged = k.merge([1, 2])
625
self.assertEquals([[['aaa']],
630
class NonConflict(TestBase):
631
"""Two descendants insert compatible changes.
633
No conflict should be reported."""
638
k.add([], ['aaa', 'bbb'])
639
k.add([0], ['111', 'aaa', 'ccc', 'bbb'])
640
k.add([1], ['aaa', 'ccc', 'bbb', '222'])
643
class Khayyam(TestBase):
644
"""Test changes to multi-line texts, and read/write"""
646
def test_multi_line_merge(self):
648
"""A Book of Verses underneath the Bough,
649
A Jug of Wine, a Loaf of Bread, -- and Thou
650
Beside me singing in the Wilderness --
651
Oh, Wilderness were Paradise enow!""",
653
"""A Book of Verses underneath the Bough,
654
A Jug of Wine, a Loaf of Bread, -- and Thou
655
Beside me singing in the Wilderness --
656
Oh, Wilderness were Paradise now!""",
658
"""A Book of poems underneath the tree,
659
A Jug of Wine, a Loaf of Bread,
661
Beside me singing in the Wilderness --
662
Oh, Wilderness were Paradise now!
666
"""A Book of Verses underneath the Bough,
667
A Jug of Wine, a Loaf of Bread,
669
Beside me singing in the Wilderness --
670
Oh, Wilderness were Paradise now!""",
672
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
678
ver = k.add('text%d' % i,
683
self.log("k._weave=" + pformat(k._weave))
685
for i, t in enumerate(texts):
686
self.assertEqual(k.get(i), t)
688
self.check_read_write(k)
691
class MergeCases(TestBase):
692
def doMerge(self, base, a, b, mp):
693
from cStringIO import StringIO
694
from textwrap import dedent
700
w.add('text0', [], map(addcrlf, base))
701
w.add('text1', [0], map(addcrlf, a))
702
w.add('text2', [0], map(addcrlf, b))
704
self.log('weave is:')
707
self.log(tmpf.getvalue())
709
self.log('merge plan:')
710
p = list(w.plan_merge(1, 2))
711
for state, line in p:
713
self.log('%12s | %s' % (state, line[:-1]))
717
mt.writelines(w.weave_merge(p))
719
self.log(mt.getvalue())
721
mp = map(addcrlf, mp)
722
self.assertEqual(mt.readlines(), mp)
725
def testOneInsert(self):
731
def testSeparateInserts(self):
732
self.doMerge(['aaa', 'bbb', 'ccc'],
733
['aaa', 'xxx', 'bbb', 'ccc'],
734
['aaa', 'bbb', 'yyy', 'ccc'],
735
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
737
def testSameInsert(self):
738
self.doMerge(['aaa', 'bbb', 'ccc'],
739
['aaa', 'xxx', 'bbb', 'ccc'],
740
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
741
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
743
def testOverlappedInsert(self):
744
self.doMerge(['aaa', 'bbb'],
745
['aaa', 'xxx', 'yyy', 'bbb'],
746
['aaa', 'xxx', 'bbb'],
747
['aaa', '<<<<<<< ', 'xxx', 'yyy', '=======', 'xxx',
750
# really it ought to reduce this to
751
# ['aaa', 'xxx', 'yyy', 'bbb']
754
def testClashReplace(self):
755
self.doMerge(['aaa'],
758
['<<<<<<< ', 'xxx', '=======', 'yyy', 'zzz',
761
def testNonClashInsert(self):
762
self.doMerge(['aaa'],
765
['<<<<<<< ', 'xxx', 'aaa', '=======', 'yyy', 'zzz',
768
self.doMerge(['aaa'],
774
def testDeleteAndModify(self):
775
"""Clashing delete and modification.
777
If one side modifies a region and the other deletes it then
778
there should be a conflict with one side blank.
781
#######################################
782
# skippd, not working yet
785
self.doMerge(['aaa', 'bbb', 'ccc'],
786
['aaa', 'ddd', 'ccc'],
788
['<<<<<<<< ', 'aaa', '=======', '>>>>>>> ', 'ccc'])
791
class JoinWeavesTests(TestBase):
793
super(JoinWeavesTests, self).setUp()
794
self.weave1 = Weave()
795
self.lines1 = ['hello\n']
796
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
797
self.weave1.add('v1', [], self.lines1)
798
self.weave1.add('v2', [0], ['hello\n', 'world\n'])
799
self.weave1.add('v3', [1], self.lines3)
801
def test_join_empty(self):
802
"""Join two empty weaves."""
803
eq = self.assertEqual
807
eq(w1.numversions(), 0)
809
def test_join_empty_to_nonempty(self):
810
"""Join empty weave onto nonempty."""
811
self.weave1.join(Weave())
812
self.assertEqual(len(self.weave1), 3)
814
def test_join_unrelated(self):
815
"""Join two weaves with no history in common."""
817
wb.add('b1', [], ['line from b\n'])
820
eq = self.assertEqual
822
eq(sorted(list(w1.iter_names())),
823
['b1', 'v1', 'v2', 'v3'])
825
def test_join_related(self):
826
wa = self.weave1.copy()
827
wb = self.weave1.copy()
828
wa.add('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
829
wb.add('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
830
eq = self.assertEquals
835
eq(wa.get_lines('b1'),
836
['hello\n', 'pale blue\n', 'world\n'])
838
def test_join_parent_disagreement(self):
839
#join reconciles differening parents into a union.
842
wa.add('v1', [], ['hello\n'])
844
wb.add('v1', ['v0'], ['hello\n'])
846
self.assertEqual(['v0'], wa.get_parents('v1'))
848
def test_join_text_disagreement(self):
849
"""Cannot join weaves with different texts for a version."""
852
wa.add('v1', [], ['hello\n'])
853
wb.add('v1', [], ['not\n', 'hello\n'])
854
self.assertRaises(WeaveError,
857
def test_join_unordered(self):
858
"""Join weaves where indexes differ.
860
The source weave contains a different version at index 0."""
861
wa = self.weave1.copy()
863
wb.add('x1', [], ['line from x1\n'])
864
wb.add('v1', [], ['hello\n'])
865
wb.add('v2', ['v1'], ['hello\n', 'world\n'])
867
eq = self.assertEquals
868
eq(sorted(wa.iter_names()), ['v1', 'v2', 'v3', 'x1',])
869
eq(wa.get_text('x1'), 'line from x1\n')
871
def test_written_detection(self):
872
# Test detection of weave file corruption.
874
# Make sure that we can detect if a weave file has
875
# been corrupted. This doesn't test all forms of corruption,
876
# but it at least helps verify the data you get, is what you want.
877
from cStringIO import StringIO
880
w.add('v1', [], ['hello\n'])
881
w.add('v2', ['v1'], ['hello\n', 'there\n'])
886
# Because we are corrupting, we need to make sure we have the exact text
887
self.assertEquals('# 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',
893
# Change a single letter
894
tmpf = StringIO('# bzr weave file v5\n'
895
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
896
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
897
'w\n{ 0\n. hello\n}\n{ 1\n. There\n}\nW\n')
901
self.assertEqual('hello\n', w.get_text('v1'))
902
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
903
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
904
self.assertRaises(errors.WeaveInvalidChecksum, list, w.get_iter('v2'))
905
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
907
# Change the sha checksum
908
tmpf = StringIO('# bzr weave file v5\n'
909
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
910
'i 0\n1 f0f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
911
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n')
915
self.assertEqual('hello\n', w.get_text('v1'))
916
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
917
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
918
self.assertRaises(errors.WeaveInvalidChecksum, list, w.get_iter('v2'))
919
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
922
class InstrumentedWeave(Weave):
923
"""Keep track of how many times functions are called."""
925
def __init__(self, weave_name=None):
926
self._extract_count = 0
927
Weave.__init__(self, weave_name=weave_name)
929
def _extract(self, versions):
930
self._extract_count += 1
931
return Weave._extract(self, versions)
934
class JoinOptimization(TestCase):
935
"""Test that Weave.join() doesn't extract all texts, only what must be done."""
938
w1 = InstrumentedWeave()
939
w2 = InstrumentedWeave()
942
txt1 = ['a\n', 'b\n']
943
txt2 = ['a\n', 'c\n']
944
txt3 = ['a\n', 'b\n', 'c\n']
946
w1.add('txt0', [], txt0) # extract 1a
947
w2.add('txt0', [], txt0) # extract 1b
948
w1.add('txt1', [0], txt1)# extract 2a
949
w2.add('txt2', [0], txt2)# extract 2b
950
w1.join(w2) # extract 3a to add txt2
951
w2.join(w1) # extract 3b to add txt1
953
w1.add('txt3', [1, 2], txt3) # extract 4a
954
w2.add('txt3', [1, 2], txt3) # extract 4b
955
# These secretly have inverted parents
957
# This should not have to do any extractions
958
w1.join(w2) # NO extract, texts already present with same parents
959
w2.join(w1) # NO extract, texts already present with same parents
961
self.assertEqual(4, w1._extract_count)
962
self.assertEqual(4, w2._extract_count)
964
def test_double_parent(self):
965
# It should not be considered illegal to add
966
# a revision with the same parent twice
967
w1 = InstrumentedWeave()
968
w2 = InstrumentedWeave()
971
txt1 = ['a\n', 'b\n']
972
txt2 = ['a\n', 'c\n']
973
txt3 = ['a\n', 'b\n', 'c\n']
975
w1.add('txt0', [], txt0)
976
w2.add('txt0', [], txt0)
977
w1.add('txt1', [0], txt1)
978
w2.add('txt1', [0,0], txt1)
979
# Same text, effectively the same, because the
980
# parent is only repeated
981
w1.join(w2) # extract 3a to add txt2
982
w2.join(w1) # extract 3b to add txt1
985
class MismatchedTexts(TestCase):
986
"""Test that merging two weaves with different texts fails."""
988
def test_reweave(self):
992
w1.add('txt0', [], ['a\n'])
993
w2.add('txt0', [], ['a\n'])
994
w1.add('txt1', [0], ['a\n', 'b\n'])
995
w2.add('txt1', [0], ['a\n', 'c\n'])
997
self.assertRaises(errors.WeaveTextDiffers, w1.reweave, w2)
1000
class TestNeedsRweave(TestCase):
1001
"""Internal corner cases for when reweave is needed."""
1003
def test_compatible_parents(self):
1005
my_parents = set([1, 2, 3])
1007
self.assertTrue(w1._compatible_parents(my_parents, set([3])))
1009
self.assertTrue(w1._compatible_parents(my_parents, set(my_parents)))
1010
# same empty corner case
1011
self.assertTrue(w1._compatible_parents(set(), set()))
1012
# other cannot contain stuff my_parents does not
1013
self.assertFalse(w1._compatible_parents(set(), set([1])))
1014
self.assertFalse(w1._compatible_parents(my_parents, set([1, 2, 3, 4])))
1015
self.assertFalse(w1._compatible_parents(my_parents, set([4])))
added
removed
bzrlib/tests/test_weave.py
