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)
64
self.fail('read/write check failed')
74
class StoreText(TestBase):
75
"""Store and retrieve a simple text."""
78
idx = k.add('text0', [], TEXT_0)
79
self.assertEqual(k.get(idx), TEXT_0)
80
self.assertEqual(idx, 0)
84
class AnnotateOne(TestBase):
87
k.add('text0', [], TEXT_0)
88
self.assertEqual(k.annotate(0),
92
class StoreTwo(TestBase):
96
idx = k.add('text0', [], TEXT_0)
97
self.assertEqual(idx, 0)
99
idx = k.add('text1', [], TEXT_1)
100
self.assertEqual(idx, 1)
102
self.assertEqual(k.get(0), TEXT_0)
103
self.assertEqual(k.get(1), TEXT_1)
107
class AddWithGivenSha(TestBase):
109
"""Add with caller-supplied SHA-1"""
113
k.add('text0', [], [t], sha1=sha_string(t))
117
class InvalidAdd(TestBase):
118
"""Try to use invalid version number during add."""
122
self.assertRaises(IndexError,
129
class RepeatedAdd(TestBase):
130
"""Add the same version twice; harmless."""
133
idx = k.add('text0', [], TEXT_0)
134
idx2 = k.add('text0', [], TEXT_0)
135
self.assertEqual(idx, idx2)
139
class InvalidRepeatedAdd(TestBase):
142
idx = k.add('text0', [], TEXT_0)
143
self.assertRaises(WeaveError,
147
['not the same text'])
148
self.assertRaises(WeaveError,
151
[12], # not the right parents
156
class InsertLines(TestBase):
157
"""Store a revision that adds one line to the original.
159
Look at the annotations to make sure that the first line is matched
160
and not stored repeatedly."""
164
k.add('text0', [], ['line 1'])
165
k.add('text1', [0], ['line 1', 'line 2'])
167
self.assertEqual(k.annotate(0),
170
self.assertEqual(k.get(1),
174
self.assertEqual(k.annotate(1),
178
k.add('text2', [0], ['line 1', 'diverged line'])
180
self.assertEqual(k.annotate(2),
182
(2, 'diverged line')])
184
text3 = ['line 1', 'middle line', 'line 2']
189
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
191
self.log("k._weave=" + pformat(k._weave))
193
self.assertEqual(k.annotate(3),
198
# now multiple insertions at different places
201
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
203
self.assertEqual(k.annotate(4),
213
class DeleteLines(TestBase):
214
"""Deletion of lines from existing text.
216
Try various texts all based on a common ancestor."""
220
base_text = ['one', 'two', 'three', 'four']
222
k.add('text0', [], base_text)
224
texts = [['one', 'two', 'three'],
225
['two', 'three', 'four'],
227
['one', 'two', 'three', 'four'],
232
ver = k.add('text%d' % i,
236
self.log('final weave:')
237
self.log('k._weave=' + pformat(k._weave))
239
for i in range(len(texts)):
240
self.assertEqual(k.get(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,
270
class CannedDelete(TestBase):
271
"""Unpack canned weave with deleted lines."""
278
k._weave = [('{', 0),
281
'line to be deleted',
287
self.assertEqual(k.get(0),
289
'line to be deleted',
293
self.assertEqual(k.get(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',
320
self.assertEqual(k.get(0),
322
'line to be deleted',
326
self.assertEqual(k.get(1),
334
class BadWeave(TestBase):
335
"""Test that we trap an insert which should not occur."""
339
k._parents = [frozenset(),
341
k._weave = ['bad line',
345
' added in version 1',
354
################################### SKIPPED
355
# Weave.get doesn't trap this anymore
359
self.assertRaises(WeaveFormatError,
364
class BadInsert(TestBase):
365
"""Test that we trap an insert which should not occur."""
369
k._parents = [frozenset(),
374
k._weave = [('{', 0),
377
' added in version 1',
385
# this is not currently enforced by get
386
return ##########################################
388
self.assertRaises(WeaveFormatError,
392
self.assertRaises(WeaveFormatError,
397
class InsertNested(TestBase):
398
"""Insertion with nested instructions."""
402
k._parents = [frozenset(),
407
k._weave = [('{', 0),
410
' added in version 1',
419
self.assertEqual(k.get(0),
423
self.assertEqual(k.get(1),
425
' added in version 1',
429
self.assertEqual(k.get(2),
434
self.assertEqual(k.get(3),
436
' added in version 1',
443
class DeleteLines2(TestBase):
444
"""Test recording revisions that delete lines.
446
This relies on the weave having a way to represent lines knocked
447
out by a later revision."""
451
k.add('text0', [], ["line the first",
456
self.assertEqual(len(k.get(0)), 4)
458
k.add('text1', [0], ["line the first",
461
self.assertEqual(k.get(1),
465
self.assertEqual(k.annotate(1),
466
[(0, "line the first"),
471
class IncludeVersions(TestBase):
472
"""Check texts that are stored across multiple revisions.
474
Here we manually create a weave with particular encoding and make
475
sure it unpacks properly.
477
Text 0 includes nothing; text 1 includes text 0 and adds some
484
k._parents = [frozenset(), frozenset([0])]
485
k._weave = [('{', 0),
492
self.assertEqual(k.get(1),
496
self.assertEqual(k.get(0),
500
class DivergedIncludes(TestBase):
501
"""Weave with two diverged texts based on version 0.
506
k._parents = [frozenset(),
510
k._weave = [('{', 0),
517
"alternative second line",
521
self.assertEqual(k.get(0),
524
self.assertEqual(k.get(1),
528
self.assertEqual(k.get(2),
530
"alternative second line"])
532
self.assertEqual(list(k.inclusions([2])),
537
class ReplaceLine(TestBase):
541
text0 = ['cheddar', 'stilton', 'gruyere']
542
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
544
k.add('text0', [], text0)
545
k.add('text1', [0], text1)
547
self.log('k._weave=' + pformat(k._weave))
549
self.assertEqual(k.get(0), text0)
550
self.assertEqual(k.get(1), text1)
554
class Merge(TestBase):
555
"""Storage of versions that merge diverged parents"""
560
['header', '', 'line from 1'],
561
['header', '', 'line from 2', 'more from 2'],
562
['header', '', 'line from 1', 'fixup line', 'line from 2'],
565
k.add('text0', [], texts[0])
566
k.add('text1', [0], texts[1])
567
k.add('text2', [0], texts[2])
568
k.add('merge', [0, 1, 2], texts[3])
570
for i, t in enumerate(texts):
571
self.assertEqual(k.get(i), t)
573
self.assertEqual(k.annotate(3),
581
self.assertEqual(list(k.inclusions([3])),
584
self.log('k._weave=' + pformat(k._weave))
586
self.check_read_write(k)
589
class Conflicts(TestBase):
590
"""Test detection of conflicting regions during a merge.
592
A base version is inserted, then two descendents try to
593
insert different lines in the same place. These should be
594
reported as a possible conflict and forwarded to the user."""
599
k.add([], ['aaa', 'bbb'])
600
k.add([0], ['aaa', '111', 'bbb'])
601
k.add([1], ['aaa', '222', 'bbb'])
603
merged = k.merge([1, 2])
605
self.assertEquals([[['aaa']],
611
class NonConflict(TestBase):
612
"""Two descendants insert compatible changes.
614
No conflict should be reported."""
619
k.add([], ['aaa', 'bbb'])
620
k.add([0], ['111', 'aaa', 'ccc', 'bbb'])
621
k.add([1], ['aaa', 'ccc', 'bbb', '222'])
627
class AutoMerge(TestBase):
631
texts = [['header', 'aaa', 'bbb'],
632
['header', 'aaa', 'line from 1', 'bbb'],
633
['header', 'aaa', 'bbb', 'line from 2', 'more from 2'],
636
k.add('text0', [], texts[0])
637
k.add('text1', [0], texts[1])
638
k.add('text2', [0], texts[2])
640
self.log('k._weave=' + pformat(k._weave))
642
m = list(k.mash_iter([0, 1, 2]))
648
'line from 2', 'more from 2'])
652
class Khayyam(TestBase):
653
"""Test changes to multi-line texts, and read/write"""
656
"""A Book of Verses underneath the Bough,
657
A Jug of Wine, a Loaf of Bread, -- and Thou
658
Beside me singing in the Wilderness --
659
Oh, Wilderness were Paradise enow!""",
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 now!""",
666
"""A Book of poems underneath the tree,
667
A Jug of Wine, a Loaf of Bread,
669
Beside me singing in the Wilderness --
670
Oh, Wilderness were Paradise now!
674
"""A Book of Verses underneath the Bough,
675
A Jug of Wine, a Loaf of Bread,
677
Beside me singing in the Wilderness --
678
Oh, Wilderness were Paradise now!""",
680
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
686
ver = k.add('text%d' % i,
691
self.log("k._weave=" + pformat(k._weave))
693
for i, t in enumerate(texts):
694
self.assertEqual(k.get(i), t)
696
self.check_read_write(k)
700
class MergeCases(TestBase):
701
def doMerge(self, base, a, b, mp):
702
from cStringIO import StringIO
703
from textwrap import dedent
709
w.add('text0', [], map(addcrlf, base))
710
w.add('text1', [0], map(addcrlf, a))
711
w.add('text2', [0], map(addcrlf, b))
713
self.log('weave is:')
716
self.log(tmpf.getvalue())
718
self.log('merge plan:')
719
p = list(w.plan_merge(1, 2))
720
for state, line in p:
722
self.log('%12s | %s' % (state, line[:-1]))
726
mt.writelines(w.weave_merge(p))
728
self.log(mt.getvalue())
730
mp = map(addcrlf, mp)
731
self.assertEqual(mt.readlines(), mp)
734
def testOneInsert(self):
740
def testSeparateInserts(self):
741
self.doMerge(['aaa', 'bbb', 'ccc'],
742
['aaa', 'xxx', 'bbb', 'ccc'],
743
['aaa', 'bbb', 'yyy', 'ccc'],
744
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
746
def testSameInsert(self):
747
self.doMerge(['aaa', 'bbb', 'ccc'],
748
['aaa', 'xxx', 'bbb', 'ccc'],
749
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
750
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
752
def testOverlappedInsert(self):
753
self.doMerge(['aaa', 'bbb'],
754
['aaa', 'xxx', 'yyy', 'bbb'],
755
['aaa', 'xxx', 'bbb'],
756
['aaa', '<<<<<<<', 'xxx', 'yyy', '=======', 'xxx',
759
# really it ought to reduce this to
760
# ['aaa', 'xxx', 'yyy', 'bbb']
763
def testClashReplace(self):
764
self.doMerge(['aaa'],
767
['<<<<<<<', 'xxx', '=======', 'yyy', 'zzz',
770
def testNonClashInsert(self):
771
self.doMerge(['aaa'],
774
['<<<<<<<', 'xxx', 'aaa', '=======', 'yyy', 'zzz',
777
self.doMerge(['aaa'],
783
def testDeleteAndModify(self):
784
"""Clashing delete and modification.
786
If one side modifies a region and the other deletes it then
787
there should be a conflict with one side blank.
790
#######################################
791
# skippd, not working yet
794
self.doMerge(['aaa', 'bbb', 'ccc'],
795
['aaa', 'ddd', 'ccc'],
797
['<<<<<<<<', 'aaa', '=======', '>>>>>>>', 'ccc'])
800
class JoinWeavesTests(TestBase):
802
super(JoinWeavesTests, self).setUp()
803
self.weave1 = Weave()
804
self.lines1 = ['hello\n']
805
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
806
self.weave1.add('v1', [], self.lines1)
807
self.weave1.add('v2', [0], ['hello\n', 'world\n'])
808
self.weave1.add('v3', [1], self.lines3)
810
def test_join_empty(self):
811
"""Join two empty weaves."""
812
eq = self.assertEqual
816
eq(w1.numversions(), 0)
818
def test_join_empty_to_nonempty(self):
819
"""Join empty weave onto nonempty."""
820
self.weave1.join(Weave())
821
self.assertEqual(len(self.weave1), 3)
823
def test_join_unrelated(self):
824
"""Join two weaves with no history in common."""
826
wb.add('b1', [], ['line from b\n'])
829
eq = self.assertEqual
831
eq(sorted(list(w1.iter_names())),
832
['b1', 'v1', 'v2', 'v3'])
834
def test_join_related(self):
835
wa = self.weave1.copy()
836
wb = self.weave1.copy()
837
wa.add('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
838
wb.add('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
839
eq = self.assertEquals
844
eq(wa.get_lines('b1'),
845
['hello\n', 'pale blue\n', 'world\n'])
847
def test_join_parent_disagreement(self):
848
"""Cannot join weaves with different parents for a version."""
851
wa.add('v1', [], ['hello\n'])
853
wb.add('v1', ['v0'], ['hello\n'])
854
self.assertRaises(WeaveError,
857
def test_join_text_disagreement(self):
858
"""Cannot join weaves with different texts for a version."""
861
wa.add('v1', [], ['hello\n'])
862
wb.add('v1', [], ['not\n', 'hello\n'])
863
self.assertRaises(WeaveError,
866
def test_join_unordered(self):
867
"""Join weaves where indexes differ.
869
The source weave contains a different version at index 0."""
870
wa = self.weave1.copy()
872
wb.add('x1', [], ['line from x1\n'])
873
wb.add('v1', [], ['hello\n'])
874
wb.add('v2', ['v1'], ['hello\n', 'world\n'])
876
eq = self.assertEquals
877
eq(sorted(wa.iter_names()), ['v1', 'v2', 'v3', 'x1',])
878
eq(wa.get_text('x1'), 'line from x1\n')
880
def test_reweave_with_empty(self):
882
wr = reweave(self.weave1, wb)
883
eq = self.assertEquals
884
eq(sorted(wr.iter_names()), ['v1', 'v2', 'v3'])
885
eq(wr.get_lines('v3'), ['hello\n', 'cruel\n', 'world\n'])
886
self.weave1.reweave(wb)
887
self.assertEquals(wr, self.weave1)
889
def test_join_with_ghosts_raises_parent_mismatch(self):
890
wa = self.weave1.copy()
892
wb.add('x1', [], ['line from x1\n'])
893
wb.add('v1', [], ['hello\n'])
894
wb.add('v2', ['v1', 'x1'], ['hello\n', 'world\n'])
895
self.assertRaises(errors.WeaveParentMismatch, wa.join, wb)
897
def test_reweave_with_ghosts(self):
898
"""Join that inserts parents of an existing revision.
900
This can happen when merging from another branch who
901
knows about revisions the destination does not. In
902
this test the second weave knows of an additional parent of
903
v2. Any revisions which are in common still have to have the
905
wa = self.weave1.copy()
907
wb.add('x1', [], ['line from x1\n'])
908
wb.add('v1', [], ['hello\n'])
909
wb.add('v2', ['v1', 'x1'], ['hello\n', 'world\n'])
911
eq = self.assertEquals
912
eq(sorted(wc.iter_names()), ['v1', 'v2', 'v3', 'x1',])
913
eq(wc.get_text('x1'), 'line from x1\n')
914
eq(wc.get_lines('v2'), ['hello\n', 'world\n'])
915
eq(wc.parent_names('v2'), ['v1', 'x1'])
916
self.weave1.reweave(wb)
917
self.assertEquals(wc, self.weave1)
920
if __name__ == '__main__':
923
sys.exit(unittest.main())
added
removed
bzrlib/selftest/test_weave.py
