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.selftest 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",
42
class TestBase(TestCase):
43
def check_read_write(self, k):
44
"""Check the weave k can be written & re-read."""
45
from tempfile import TemporaryFile
54
self.log('serialized weave:')
58
self.log('parents: %s' % (k._parents == k2._parents))
59
self.log(' %r' % k._parents)
60
self.log(' %r' % k2._parents)
62
self.fail('read/write check failed')
65
class WeaveContains(TestBase):
66
"""Weave __contains__ operator"""
69
self.assertFalse('foo' in k)
70
k.add('foo', [], TEXT_1)
71
self.assertTrue('foo' in k)
79
class StoreText(TestBase):
80
"""Store and retrieve a simple text."""
83
idx = k.add('text0', [], TEXT_0)
84
self.assertEqual(k.get(idx), TEXT_0)
85
self.assertEqual(idx, 0)
89
class AnnotateOne(TestBase):
92
k.add('text0', [], TEXT_0)
93
self.assertEqual(k.annotate(0),
97
class StoreTwo(TestBase):
101
idx = k.add('text0', [], TEXT_0)
102
self.assertEqual(idx, 0)
104
idx = k.add('text1', [], TEXT_1)
105
self.assertEqual(idx, 1)
107
self.assertEqual(k.get(0), TEXT_0)
108
self.assertEqual(k.get(1), TEXT_1)
112
class AddWithGivenSha(TestBase):
114
"""Add with caller-supplied SHA-1"""
118
k.add('text0', [], [t], sha1=sha_string(t))
122
class InvalidAdd(TestBase):
123
"""Try to use invalid version number during add."""
127
self.assertRaises(IndexError,
134
class RepeatedAdd(TestBase):
135
"""Add the same version twice; harmless."""
138
idx = k.add('text0', [], TEXT_0)
139
idx2 = k.add('text0', [], TEXT_0)
140
self.assertEqual(idx, idx2)
144
class InvalidRepeatedAdd(TestBase):
147
idx = k.add('text0', [], TEXT_0)
148
self.assertRaises(WeaveError,
152
['not the same text'])
153
self.assertRaises(WeaveError,
156
[12], # not the right parents
161
class InsertLines(TestBase):
162
"""Store a revision that adds one line to the original.
164
Look at the annotations to make sure that the first line is matched
165
and not stored repeatedly."""
169
k.add('text0', [], ['line 1'])
170
k.add('text1', [0], ['line 1', 'line 2'])
172
self.assertEqual(k.annotate(0),
175
self.assertEqual(k.get(1),
179
self.assertEqual(k.annotate(1),
183
k.add('text2', [0], ['line 1', 'diverged line'])
185
self.assertEqual(k.annotate(2),
187
(2, 'diverged line')])
189
text3 = ['line 1', 'middle line', 'line 2']
194
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
196
self.log("k._weave=" + pformat(k._weave))
198
self.assertEqual(k.annotate(3),
203
# now multiple insertions at different places
206
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
208
self.assertEqual(k.annotate(4),
218
class DeleteLines(TestBase):
219
"""Deletion of lines from existing text.
221
Try various texts all based on a common ancestor."""
225
base_text = ['one', 'two', 'three', 'four']
227
k.add('text0', [], base_text)
229
texts = [['one', 'two', 'three'],
230
['two', 'three', 'four'],
232
['one', 'two', 'three', 'four'],
237
ver = k.add('text%d' % i,
241
self.log('final weave:')
242
self.log('k._weave=' + pformat(k._weave))
244
for i in range(len(texts)):
245
self.assertEqual(k.get(i+1),
251
class SuicideDelete(TestBase):
252
"""Invalid weave which tries to add and delete simultaneously."""
258
k._weave = [('{', 0),
265
################################### SKIPPED
266
# Weave.get doesn't trap this anymore
269
self.assertRaises(WeaveFormatError,
275
class CannedDelete(TestBase):
276
"""Unpack canned weave with deleted lines."""
283
k._weave = [('{', 0),
286
'line to be deleted',
292
self.assertEqual(k.get(0),
294
'line to be deleted',
298
self.assertEqual(k.get(1),
305
class CannedReplacement(TestBase):
306
"""Unpack canned weave with deleted lines."""
310
k._parents = [frozenset(),
313
k._weave = [('{', 0),
316
'line to be deleted',
325
self.assertEqual(k.get(0),
327
'line to be deleted',
331
self.assertEqual(k.get(1),
339
class BadWeave(TestBase):
340
"""Test that we trap an insert which should not occur."""
344
k._parents = [frozenset(),
346
k._weave = ['bad line',
350
' added in version 1',
359
################################### SKIPPED
360
# Weave.get doesn't trap this anymore
364
self.assertRaises(WeaveFormatError,
369
class BadInsert(TestBase):
370
"""Test that we trap an insert which should not occur."""
374
k._parents = [frozenset(),
379
k._weave = [('{', 0),
382
' added in version 1',
390
# this is not currently enforced by get
391
return ##########################################
393
self.assertRaises(WeaveFormatError,
397
self.assertRaises(WeaveFormatError,
402
class InsertNested(TestBase):
403
"""Insertion with nested instructions."""
407
k._parents = [frozenset(),
412
k._weave = [('{', 0),
415
' added in version 1',
424
self.assertEqual(k.get(0),
428
self.assertEqual(k.get(1),
430
' added in version 1',
434
self.assertEqual(k.get(2),
439
self.assertEqual(k.get(3),
441
' added in version 1',
448
class DeleteLines2(TestBase):
449
"""Test recording revisions that delete lines.
451
This relies on the weave having a way to represent lines knocked
452
out by a later revision."""
456
k.add('text0', [], ["line the first",
461
self.assertEqual(len(k.get(0)), 4)
463
k.add('text1', [0], ["line the first",
466
self.assertEqual(k.get(1),
470
self.assertEqual(k.annotate(1),
471
[(0, "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
self.assertEqual(k.get(1),
501
self.assertEqual(k.get(0),
505
class DivergedIncludes(TestBase):
506
"""Weave with two diverged texts based on version 0.
511
k._parents = [frozenset(),
515
k._weave = [('{', 0),
522
"alternative second line",
526
self.assertEqual(k.get(0),
529
self.assertEqual(k.get(1),
533
self.assertEqual(k.get(2),
535
"alternative second line"])
537
self.assertEqual(list(k.inclusions([2])),
542
class ReplaceLine(TestBase):
546
text0 = ['cheddar', 'stilton', 'gruyere']
547
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
549
k.add('text0', [], text0)
550
k.add('text1', [0], text1)
552
self.log('k._weave=' + pformat(k._weave))
554
self.assertEqual(k.get(0), text0)
555
self.assertEqual(k.get(1), text1)
559
class Merge(TestBase):
560
"""Storage of versions that merge diverged parents"""
565
['header', '', 'line from 1'],
566
['header', '', 'line from 2', 'more from 2'],
567
['header', '', 'line from 1', 'fixup line', 'line from 2'],
570
k.add('text0', [], texts[0])
571
k.add('text1', [0], texts[1])
572
k.add('text2', [0], texts[2])
573
k.add('merge', [0, 1, 2], texts[3])
575
for i, t in enumerate(texts):
576
self.assertEqual(k.get(i), t)
578
self.assertEqual(k.annotate(3),
586
self.assertEqual(list(k.inclusions([3])),
589
self.log('k._weave=' + pformat(k._weave))
591
self.check_read_write(k)
594
class Conflicts(TestBase):
595
"""Test detection of conflicting regions during a merge.
597
A base version is inserted, then two descendents try to
598
insert different lines in the same place. These should be
599
reported as a possible conflict and forwarded to the user."""
604
k.add([], ['aaa', 'bbb'])
605
k.add([0], ['aaa', '111', 'bbb'])
606
k.add([1], ['aaa', '222', 'bbb'])
608
merged = k.merge([1, 2])
610
self.assertEquals([[['aaa']],
616
class NonConflict(TestBase):
617
"""Two descendants insert compatible changes.
619
No conflict should be reported."""
624
k.add([], ['aaa', 'bbb'])
625
k.add([0], ['111', 'aaa', 'ccc', 'bbb'])
626
k.add([1], ['aaa', 'ccc', 'bbb', '222'])
632
class AutoMerge(TestBase):
636
texts = [['header', 'aaa', 'bbb'],
637
['header', 'aaa', 'line from 1', 'bbb'],
638
['header', 'aaa', 'bbb', 'line from 2', 'more from 2'],
641
k.add('text0', [], texts[0])
642
k.add('text1', [0], texts[1])
643
k.add('text2', [0], texts[2])
645
self.log('k._weave=' + pformat(k._weave))
647
m = list(k.mash_iter([0, 1, 2]))
653
'line from 2', 'more from 2'])
657
class Khayyam(TestBase):
658
"""Test changes to multi-line texts, and read/write"""
661
"""A Book of Verses underneath the Bough,
662
A Jug of Wine, a Loaf of Bread, -- and Thou
663
Beside me singing in the Wilderness --
664
Oh, Wilderness were Paradise enow!""",
666
"""A Book of Verses underneath the Bough,
667
A Jug of Wine, a Loaf of Bread, -- and Thou
668
Beside me singing in the Wilderness --
669
Oh, Wilderness were Paradise now!""",
671
"""A Book of poems underneath the tree,
672
A Jug of Wine, a Loaf of Bread,
674
Beside me singing in the Wilderness --
675
Oh, Wilderness were Paradise now!
679
"""A Book of Verses underneath the Bough,
680
A Jug of Wine, a Loaf of Bread,
682
Beside me singing in the Wilderness --
683
Oh, Wilderness were Paradise now!""",
685
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
691
ver = k.add('text%d' % i,
696
self.log("k._weave=" + pformat(k._weave))
698
for i, t in enumerate(texts):
699
self.assertEqual(k.get(i), t)
701
self.check_read_write(k)
705
class MergeCases(TestBase):
706
def doMerge(self, base, a, b, mp):
707
from cStringIO import StringIO
708
from textwrap import dedent
714
w.add('text0', [], map(addcrlf, base))
715
w.add('text1', [0], map(addcrlf, a))
716
w.add('text2', [0], map(addcrlf, b))
718
self.log('weave is:')
721
self.log(tmpf.getvalue())
723
self.log('merge plan:')
724
p = list(w.plan_merge(1, 2))
725
for state, line in p:
727
self.log('%12s | %s' % (state, line[:-1]))
731
mt.writelines(w.weave_merge(p))
733
self.log(mt.getvalue())
735
mp = map(addcrlf, mp)
736
self.assertEqual(mt.readlines(), mp)
739
def testOneInsert(self):
745
def testSeparateInserts(self):
746
self.doMerge(['aaa', 'bbb', 'ccc'],
747
['aaa', 'xxx', 'bbb', 'ccc'],
748
['aaa', 'bbb', 'yyy', 'ccc'],
749
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
751
def testSameInsert(self):
752
self.doMerge(['aaa', 'bbb', 'ccc'],
753
['aaa', 'xxx', 'bbb', 'ccc'],
754
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
755
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
757
def testOverlappedInsert(self):
758
self.doMerge(['aaa', 'bbb'],
759
['aaa', 'xxx', 'yyy', 'bbb'],
760
['aaa', 'xxx', 'bbb'],
761
['aaa', '<<<<<<<', 'xxx', 'yyy', '=======', 'xxx',
764
# really it ought to reduce this to
765
# ['aaa', 'xxx', 'yyy', 'bbb']
768
def testClashReplace(self):
769
self.doMerge(['aaa'],
772
['<<<<<<<', 'xxx', '=======', 'yyy', 'zzz',
775
def testNonClashInsert(self):
776
self.doMerge(['aaa'],
779
['<<<<<<<', 'xxx', 'aaa', '=======', 'yyy', 'zzz',
782
self.doMerge(['aaa'],
788
def testDeleteAndModify(self):
789
"""Clashing delete and modification.
791
If one side modifies a region and the other deletes it then
792
there should be a conflict with one side blank.
795
#######################################
796
# skippd, not working yet
799
self.doMerge(['aaa', 'bbb', 'ccc'],
800
['aaa', 'ddd', 'ccc'],
802
['<<<<<<<<', 'aaa', '=======', '>>>>>>>', 'ccc'])
805
class JoinWeavesTests(TestBase):
807
super(JoinWeavesTests, self).setUp()
808
self.weave1 = Weave()
809
self.lines1 = ['hello\n']
810
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
811
self.weave1.add('v1', [], self.lines1)
812
self.weave1.add('v2', [0], ['hello\n', 'world\n'])
813
self.weave1.add('v3', [1], self.lines3)
815
def test_join_empty(self):
816
"""Join two empty weaves."""
817
eq = self.assertEqual
821
eq(w1.numversions(), 0)
823
def test_join_empty_to_nonempty(self):
824
"""Join empty weave onto nonempty."""
825
self.weave1.join(Weave())
826
self.assertEqual(len(self.weave1), 3)
828
def test_join_unrelated(self):
829
"""Join two weaves with no history in common."""
831
wb.add('b1', [], ['line from b\n'])
834
eq = self.assertEqual
836
eq(sorted(list(w1.iter_names())),
837
['b1', 'v1', 'v2', 'v3'])
839
def test_join_related(self):
840
wa = self.weave1.copy()
841
wb = self.weave1.copy()
842
wa.add('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
843
wb.add('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
844
eq = self.assertEquals
849
eq(wa.get_lines('b1'),
850
['hello\n', 'pale blue\n', 'world\n'])
852
def test_join_parent_disagreement(self):
853
"""Cannot join weaves with different parents for a version."""
856
wa.add('v1', [], ['hello\n'])
858
wb.add('v1', ['v0'], ['hello\n'])
859
self.assertRaises(WeaveError,
862
def test_join_text_disagreement(self):
863
"""Cannot join weaves with different texts for a version."""
866
wa.add('v1', [], ['hello\n'])
867
wb.add('v1', [], ['not\n', 'hello\n'])
868
self.assertRaises(WeaveError,
871
def test_join_unordered(self):
872
"""Join weaves where indexes differ.
874
The source weave contains a different version at index 0."""
875
wa = self.weave1.copy()
877
wb.add('x1', [], ['line from x1\n'])
878
wb.add('v1', [], ['hello\n'])
879
wb.add('v2', ['v1'], ['hello\n', 'world\n'])
881
eq = self.assertEquals
882
eq(sorted(wa.iter_names()), ['v1', 'v2', 'v3', 'x1',])
883
eq(wa.get_text('x1'), 'line from x1\n')
added
removed
bzrlib/selftest/weave.py
