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."""
81
def test_storing_text(self):
83
idx = k.add_lines('text0', [], TEXT_0)
84
self.assertEqual(k.get_lines(idx), TEXT_0)
85
self.assertEqual(idx, 0)
88
class AnnotateOne(TestBase):
91
k.add_lines('text0', [], TEXT_0)
92
self.assertEqual(k.annotate('text0'),
93
[('text0', TEXT_0[0])])
96
class StoreTwo(TestBase):
100
idx = k.add_lines('text0', [], TEXT_0)
101
self.assertEqual(idx, 0)
103
idx = k.add_lines('text1', [], TEXT_1)
104
self.assertEqual(idx, 1)
106
self.assertEqual(k.get_lines(0), TEXT_0)
107
self.assertEqual(k.get_lines(1), TEXT_1)
110
class GetSha1(TestBase):
111
def test_get_sha1(self):
113
k.add_lines('text0', [], 'text0')
114
self.assertEqual('34dc0e430c642a26c3dd1c2beb7a8b4f4445eb79',
116
self.assertRaises(errors.RevisionNotPresent,
118
self.assertRaises(errors.RevisionNotPresent,
122
class InvalidAdd(TestBase):
123
"""Try to use invalid version number during add."""
127
self.assertRaises(errors.RevisionNotPresent,
134
class RepeatedAdd(TestBase):
135
"""Add the same version twice; harmless."""
138
idx = k.add_lines('text0', [], TEXT_0)
139
idx2 = k.add_lines('text0', [], TEXT_0)
140
self.assertEqual(idx, idx2)
143
class InvalidRepeatedAdd(TestBase):
146
k.add_lines('basis', [], TEXT_0)
147
idx = k.add_lines('text0', [], TEXT_0)
148
self.assertRaises(errors.RevisionAlreadyPresent,
152
['not the same text'])
153
self.assertRaises(errors.RevisionAlreadyPresent,
156
['basis'], # not the right parents
160
class InsertLines(TestBase):
161
"""Store a revision that adds one line to the original.
163
Look at the annotations to make sure that the first line is matched
164
and not stored repeatedly."""
168
k.add_lines('text0', [], ['line 1'])
169
k.add_lines('text1', ['text0'], ['line 1', 'line 2'])
171
self.assertEqual(k.annotate('text0'),
172
[('text0', 'line 1')])
174
self.assertEqual(k.get_lines(1),
178
self.assertEqual(k.annotate('text1'),
179
[('text0', 'line 1'),
180
('text1', 'line 2')])
182
k.add_lines('text2', ['text0'], ['line 1', 'diverged line'])
184
self.assertEqual(k.annotate('text2'),
185
[('text0', 'line 1'),
186
('text2', 'diverged line')])
188
text3 = ['line 1', 'middle line', 'line 2']
193
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
195
self.log("k._weave=" + pformat(k._weave))
197
self.assertEqual(k.annotate('text3'),
198
[('text0', 'line 1'),
199
('text3', 'middle line'),
200
('text1', 'line 2')])
202
# now multiple insertions at different places
204
['text0', 'text1', 'text3'],
205
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
207
self.assertEqual(k.annotate('text4'),
208
[('text0', 'line 1'),
210
('text3', 'middle line'),
216
class DeleteLines(TestBase):
217
"""Deletion of lines from existing text.
219
Try various texts all based on a common ancestor."""
223
base_text = ['one', 'two', 'three', 'four']
225
k.add_lines('text0', [], base_text)
227
texts = [['one', 'two', 'three'],
228
['two', 'three', 'four'],
230
['one', 'two', 'three', 'four'],
235
ver = k.add_lines('text%d' % i,
239
self.log('final weave:')
240
self.log('k._weave=' + pformat(k._weave))
242
for i in range(len(texts)):
243
self.assertEqual(k.get_lines(i+1),
247
class SuicideDelete(TestBase):
248
"""Invalid weave which tries to add and delete simultaneously."""
254
k._weave = [('{', 0),
261
################################### SKIPPED
262
# Weave.get doesn't trap this anymore
265
self.assertRaises(WeaveFormatError,
270
class CannedDelete(TestBase):
271
"""Unpack canned weave with deleted lines."""
278
k._weave = [('{', 0),
281
'line to be deleted',
286
k._sha1s = [sha_string('first lineline to be deletedlast line')
287
, sha_string('first linelast line')]
289
self.assertEqual(k.get_lines(0),
291
'line to be deleted',
295
self.assertEqual(k.get_lines(1),
301
class CannedReplacement(TestBase):
302
"""Unpack canned weave with deleted lines."""
306
k._parents = [frozenset(),
309
k._weave = [('{', 0),
312
'line to be deleted',
320
k._sha1s = [sha_string('first lineline to be deletedlast line')
321
, sha_string('first linereplacement linelast line')]
323
self.assertEqual(k.get_lines(0),
325
'line to be deleted',
329
self.assertEqual(k.get_lines(1),
336
class BadWeave(TestBase):
337
"""Test that we trap an insert which should not occur."""
341
k._parents = [frozenset(),
343
k._weave = ['bad line',
347
' added in version 1',
356
################################### SKIPPED
357
# Weave.get doesn't trap this anymore
361
self.assertRaises(WeaveFormatError,
366
class BadInsert(TestBase):
367
"""Test that we trap an insert which should not occur."""
371
k._parents = [frozenset(),
376
k._weave = [('{', 0),
379
' added in version 1',
387
# this is not currently enforced by get
388
return ##########################################
390
self.assertRaises(WeaveFormatError,
394
self.assertRaises(WeaveFormatError,
399
class InsertNested(TestBase):
400
"""Insertion with nested instructions."""
404
k._parents = [frozenset(),
409
k._weave = [('{', 0),
412
' added in version 1',
421
k._sha1s = [sha_string('foo {}')
422
, sha_string('foo { added in version 1 also from v1}')
423
, sha_string('foo { added in v2}')
424
, sha_string('foo { added in version 1 added in v2 also from v1}')
427
self.assertEqual(k.get_lines(0),
431
self.assertEqual(k.get_lines(1),
433
' added in version 1',
437
self.assertEqual(k.get_lines(2),
442
self.assertEqual(k.get_lines(3),
444
' added in version 1',
450
class DeleteLines2(TestBase):
451
"""Test recording revisions that delete lines.
453
This relies on the weave having a way to represent lines knocked
454
out by a later revision."""
458
k.add_lines('text0', [], ["line the first",
463
self.assertEqual(len(k.get_lines(0)), 4)
465
k.add_lines('text1', ['text0'], ["line the first",
468
self.assertEqual(k.get_lines(1),
472
self.assertEqual(k.annotate('text1'),
473
[('text0', "line the first"),
477
class IncludeVersions(TestBase):
478
"""Check texts that are stored across multiple revisions.
480
Here we manually create a weave with particular encoding and make
481
sure it unpacks properly.
483
Text 0 includes nothing; text 1 includes text 0 and adds some
490
k._parents = [frozenset(), frozenset([0])]
491
k._weave = [('{', 0),
498
k._sha1s = [sha_string('first line')
499
, sha_string('first linesecond line')]
501
self.assertEqual(k.get_lines(1),
505
self.assertEqual(k.get_lines(0),
509
class DivergedIncludes(TestBase):
510
"""Weave with two diverged texts based on version 0.
513
# FIXME make the weave, dont poke at it.
516
k._names = ['0', '1', '2']
517
k._name_map = {'0':0, '1':1, '2':2}
518
k._parents = [frozenset(),
522
k._weave = [('{', 0),
529
"alternative second line",
533
k._sha1s = [sha_string('first line')
534
, sha_string('first linesecond line')
535
, sha_string('first linealternative second line')]
537
self.assertEqual(k.get_lines(0),
540
self.assertEqual(k.get_lines(1),
544
self.assertEqual(k.get_lines('2'),
546
"alternative second line"])
548
self.assertEqual(list(k.get_ancestry(['2'])),
552
class ReplaceLine(TestBase):
556
text0 = ['cheddar', 'stilton', 'gruyere']
557
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
559
k.add_lines('text0', [], text0)
560
k.add_lines('text1', ['text0'], text1)
562
self.log('k._weave=' + pformat(k._weave))
564
self.assertEqual(k.get_lines(0), text0)
565
self.assertEqual(k.get_lines(1), text1)
568
class Merge(TestBase):
569
"""Storage of versions that merge diverged parents"""
574
['header', '', 'line from 1'],
575
['header', '', 'line from 2', 'more from 2'],
576
['header', '', 'line from 1', 'fixup line', 'line from 2'],
579
k.add_lines('text0', [], texts[0])
580
k.add_lines('text1', ['text0'], texts[1])
581
k.add_lines('text2', ['text0'], texts[2])
582
k.add_lines('merge', ['text0', 'text1', 'text2'], texts[3])
584
for i, t in enumerate(texts):
585
self.assertEqual(k.get_lines(i), t)
587
self.assertEqual(k.annotate('merge'),
588
[('text0', 'header'),
590
('text1', 'line from 1'),
591
('merge', 'fixup line'),
592
('text2', 'line from 2'),
595
self.assertEqual(list(k.get_ancestry(['merge'])),
596
['text0', 'text1', 'text2', 'merge'])
598
self.log('k._weave=' + pformat(k._weave))
600
self.check_read_write(k)
603
class Conflicts(TestBase):
604
"""Test detection of conflicting regions during a merge.
606
A base version is inserted, then two descendents try to
607
insert different lines in the same place. These should be
608
reported as a possible conflict and forwarded to the user."""
613
k.add_lines([], ['aaa', 'bbb'])
614
k.add_lines([0], ['aaa', '111', 'bbb'])
615
k.add_lines([1], ['aaa', '222', 'bbb'])
617
merged = k.merge([1, 2])
619
self.assertEquals([[['aaa']],
624
class NonConflict(TestBase):
625
"""Two descendants insert compatible changes.
627
No conflict should be reported."""
632
k.add_lines([], ['aaa', 'bbb'])
633
k.add_lines([0], ['111', 'aaa', 'ccc', 'bbb'])
634
k.add_lines([1], ['aaa', 'ccc', 'bbb', '222'])
637
class Khayyam(TestBase):
638
"""Test changes to multi-line texts, and read/write"""
640
def test_multi_line_merge(self):
642
"""A Book of Verses underneath the Bough,
643
A Jug of Wine, a Loaf of Bread, -- and Thou
644
Beside me singing in the Wilderness --
645
Oh, Wilderness were Paradise enow!""",
647
"""A Book of Verses underneath the Bough,
648
A Jug of Wine, a Loaf of Bread, -- and Thou
649
Beside me singing in the Wilderness --
650
Oh, Wilderness were Paradise now!""",
652
"""A Book of poems underneath the tree,
653
A Jug of Wine, a Loaf of Bread,
655
Beside me singing in the Wilderness --
656
Oh, Wilderness were Paradise now!
660
"""A Book of Verses underneath the Bough,
661
A Jug of Wine, a Loaf of Bread,
663
Beside me singing in the Wilderness --
664
Oh, Wilderness were Paradise now!""",
666
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
672
ver = k.add_lines('text%d' % i,
674
parents.add('text%d' % i)
677
self.log("k._weave=" + pformat(k._weave))
679
for i, t in enumerate(texts):
680
self.assertEqual(k.get_lines(i), t)
682
self.check_read_write(k)
685
class MergeCases(TestBase):
686
def doMerge(self, base, a, b, mp):
687
from cStringIO import StringIO
688
from textwrap import dedent
694
w.add_lines('text0', [], map(addcrlf, base))
695
w.add_lines('text1', ['text0'], map(addcrlf, a))
696
w.add_lines('text2', ['text0'], map(addcrlf, b))
698
self.log('weave is:')
701
self.log(tmpf.getvalue())
703
self.log('merge plan:')
704
p = list(w.plan_merge('text1', 'text2'))
705
for state, line in p:
707
self.log('%12s | %s' % (state, line[:-1]))
711
mt.writelines(w.weave_merge(p))
713
self.log(mt.getvalue())
715
mp = map(addcrlf, mp)
716
self.assertEqual(mt.readlines(), mp)
719
def testOneInsert(self):
725
def testSeparateInserts(self):
726
self.doMerge(['aaa', 'bbb', 'ccc'],
727
['aaa', 'xxx', 'bbb', 'ccc'],
728
['aaa', 'bbb', 'yyy', 'ccc'],
729
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
731
def testSameInsert(self):
732
self.doMerge(['aaa', 'bbb', 'ccc'],
733
['aaa', 'xxx', 'bbb', 'ccc'],
734
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
735
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
737
def testOverlappedInsert(self):
738
self.doMerge(['aaa', 'bbb'],
739
['aaa', 'xxx', 'yyy', 'bbb'],
740
['aaa', 'xxx', 'bbb'],
741
['aaa', '<<<<<<< ', 'xxx', 'yyy', '=======', 'xxx',
744
# really it ought to reduce this to
745
# ['aaa', 'xxx', 'yyy', 'bbb']
748
def testClashReplace(self):
749
self.doMerge(['aaa'],
752
['<<<<<<< ', 'xxx', '=======', 'yyy', 'zzz',
755
def testNonClashInsert(self):
756
self.doMerge(['aaa'],
759
['<<<<<<< ', 'xxx', 'aaa', '=======', 'yyy', 'zzz',
762
self.doMerge(['aaa'],
768
def testDeleteAndModify(self):
769
"""Clashing delete and modification.
771
If one side modifies a region and the other deletes it then
772
there should be a conflict with one side blank.
775
#######################################
776
# skippd, not working yet
779
self.doMerge(['aaa', 'bbb', 'ccc'],
780
['aaa', 'ddd', 'ccc'],
782
['<<<<<<<< ', 'aaa', '=======', '>>>>>>> ', 'ccc'])
785
class JoinWeavesTests(TestBase):
787
super(JoinWeavesTests, self).setUp()
788
self.weave1 = Weave()
789
self.lines1 = ['hello\n']
790
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
791
self.weave1.add_lines('v1', [], self.lines1)
792
self.weave1.add_lines('v2', ['v1'], ['hello\n', 'world\n'])
793
self.weave1.add_lines('v3', ['v2'], self.lines3)
795
def test_join_empty(self):
796
"""Join two empty weaves."""
797
eq = self.assertEqual
803
def test_join_empty_to_nonempty(self):
804
"""Join empty weave onto nonempty."""
805
self.weave1.join(Weave())
806
self.assertEqual(len(self.weave1), 3)
808
def test_join_unrelated(self):
809
"""Join two weaves with no history in common."""
811
wb.add_lines('b1', [], ['line from b\n'])
814
eq = self.assertEqual
816
eq(sorted(w1.versions()),
817
['b1', 'v1', 'v2', 'v3'])
819
def test_join_related(self):
820
wa = self.weave1.copy()
821
wb = self.weave1.copy()
822
wa.add_lines('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
823
wb.add_lines('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
824
eq = self.assertEquals
829
eq(wa.get_lines('b1'),
830
['hello\n', 'pale blue\n', 'world\n'])
832
def test_join_parent_disagreement(self):
833
#join reconciles differening parents into a union.
836
wa.add_lines('v1', [], ['hello\n'])
837
wb.add_lines('v0', [], [])
838
wb.add_lines('v1', ['v0'], ['hello\n'])
840
self.assertEqual(['v0'], wa.get_parents('v1'))
842
def test_join_text_disagreement(self):
843
"""Cannot join weaves with different texts for a version."""
846
wa.add_lines('v1', [], ['hello\n'])
847
wb.add_lines('v1', [], ['not\n', 'hello\n'])
848
self.assertRaises(WeaveError,
851
def test_join_unordered(self):
852
"""Join weaves where indexes differ.
854
The source weave contains a different version at index 0."""
855
wa = self.weave1.copy()
857
wb.add_lines('x1', [], ['line from x1\n'])
858
wb.add_lines('v1', [], ['hello\n'])
859
wb.add_lines('v2', ['v1'], ['hello\n', 'world\n'])
861
eq = self.assertEquals
862
eq(sorted(wa.versions()), ['v1', 'v2', 'v3', 'x1',])
863
eq(wa.get_text('x1'), 'line from x1\n')
865
def test_written_detection(self):
866
# Test detection of weave file corruption.
868
# Make sure that we can detect if a weave file has
869
# been corrupted. This doesn't test all forms of corruption,
870
# but it at least helps verify the data you get, is what you want.
871
from cStringIO import StringIO
874
w.add_lines('v1', [], ['hello\n'])
875
w.add_lines('v2', ['v1'], ['hello\n', 'there\n'])
880
# Because we are corrupting, we need to make sure we have the exact text
881
self.assertEquals('# bzr weave file v5\n'
882
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
883
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
884
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n',
887
# Change a single letter
888
tmpf = StringIO('# bzr weave file v5\n'
889
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
890
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
891
'w\n{ 0\n. hello\n}\n{ 1\n. There\n}\nW\n')
895
self.assertEqual('hello\n', w.get_text('v1'))
896
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
897
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
898
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
900
# Change the sha checksum
901
tmpf = StringIO('# bzr weave file v5\n'
902
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
903
'i 0\n1 f0f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
904
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n')
908
self.assertEqual('hello\n', w.get_text('v1'))
909
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
910
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
911
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
914
class InstrumentedWeave(Weave):
915
"""Keep track of how many times functions are called."""
917
def __init__(self, weave_name=None):
918
self._extract_count = 0
919
Weave.__init__(self, weave_name=weave_name)
921
def _extract(self, versions):
922
self._extract_count += 1
923
return Weave._extract(self, versions)
926
class JoinOptimization(TestCase):
927
"""Test that Weave.join() doesn't extract all texts, only what must be done."""
930
w1 = InstrumentedWeave()
931
w2 = InstrumentedWeave()
934
txt1 = ['a\n', 'b\n']
935
txt2 = ['a\n', 'c\n']
936
txt3 = ['a\n', 'b\n', 'c\n']
938
w1.add_lines('txt0', [], txt0) # extract 1a
939
w2.add_lines('txt0', [], txt0) # extract 1b
940
w1.add_lines('txt1', ['txt0'], txt1)# extract 2a
941
w2.add_lines('txt2', ['txt0'], txt2)# extract 2b
942
w1.join(w2) # extract 3a to add txt2
943
w2.join(w1) # extract 3b to add txt1
945
w1.add_lines('txt3', ['txt1', 'txt2'], txt3) # extract 4a
946
w2.add_lines('txt3', ['txt2', 'txt1'], txt3) # extract 4b
947
# These secretly have inverted parents
949
# This should not have to do any extractions
950
w1.join(w2) # NO extract, texts already present with same parents
951
w2.join(w1) # NO extract, texts already present with same parents
953
self.assertEqual(4, w1._extract_count)
954
self.assertEqual(4, w2._extract_count)
956
def test_double_parent(self):
957
# It should not be considered illegal to add
958
# a revision with the same parent twice
959
w1 = InstrumentedWeave()
960
w2 = InstrumentedWeave()
963
txt1 = ['a\n', 'b\n']
964
txt2 = ['a\n', 'c\n']
965
txt3 = ['a\n', 'b\n', 'c\n']
967
w1.add_lines('txt0', [], txt0)
968
w2.add_lines('txt0', [], txt0)
969
w1.add_lines('txt1', ['txt0'], txt1)
970
w2.add_lines('txt1', ['txt0', 'txt0'], txt1)
971
# Same text, effectively the same, because the
972
# parent is only repeated
973
w1.join(w2) # extract 3a to add txt2
974
w2.join(w1) # extract 3b to add txt1
977
class TestNeedsRweave(TestCase):
978
"""Internal corner cases for when reweave is needed."""
980
def test_compatible_parents(self):
982
my_parents = set([1, 2, 3])
984
self.assertTrue(w1._compatible_parents(my_parents, set([3])))
986
self.assertTrue(w1._compatible_parents(my_parents, set(my_parents)))
987
# same empty corner case
988
self.assertTrue(w1._compatible_parents(set(), set()))
989
# other cannot contain stuff my_parents does not
990
self.assertFalse(w1._compatible_parents(set(), set([1])))
991
self.assertFalse(w1._compatible_parents(my_parents, set([1, 2, 3, 4])))
992
self.assertFalse(w1._compatible_parents(my_parents, set([4])))
added
removed
bzrlib/tests/test_weave.py
