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', '>>>>', 'bbb'])
758
# really it ought to reduce this to
759
# ['aaa', 'xxx', 'yyy', 'bbb']
762
def testClashReplace(self):
763
self.doMerge(['aaa'],
766
['<<<<', 'xxx', '====', 'yyy', 'zzz', '>>>>'])
768
def testNonClashInsert(self):
769
self.doMerge(['aaa'],
772
['<<<<', 'xxx', 'aaa', '====', 'yyy', 'zzz', '>>>>'])
774
self.doMerge(['aaa'],
780
def testDeleteAndModify(self):
781
"""Clashing delete and modification.
783
If one side modifies a region and the other deletes it then
784
there should be a conflict with one side blank.
787
#######################################
788
# skippd, not working yet
791
self.doMerge(['aaa', 'bbb', 'ccc'],
792
['aaa', 'ddd', 'ccc'],
794
['<<<<', 'aaa', '====', '>>>>', 'ccc'])
797
class JoinWeavesTests(TestBase):
799
super(JoinWeavesTests, self).setUp()
800
self.weave1 = Weave()
801
self.lines1 = ['hello\n']
802
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
803
self.weave1.add('v1', [], self.lines1)
804
self.weave1.add('v2', [0], ['hello\n', 'world\n'])
805
self.weave1.add('v3', [1], self.lines3)
807
def test_join_empty(self):
808
"""Join two empty weaves."""
809
eq = self.assertEqual
813
eq(w1.numversions(), 0)
815
def test_join_empty_to_nonempty(self):
816
"""Join empty weave onto nonempty."""
817
self.weave1.join(Weave())
818
self.assertEqual(len(self.weave1), 3)
820
def test_join_unrelated(self):
821
"""Join two weaves with no history in common."""
823
wb.add('b1', [], ['line from b\n'])
826
eq = self.assertEqual
828
eq(sorted(list(w1.iter_names())),
829
['b1', 'v1', 'v2', 'v3'])
831
def test_join_related(self):
832
wa = self.weave1.copy()
833
wb = self.weave1.copy()
834
wa.add('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
835
wb.add('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
836
eq = self.assertEquals
841
eq(wa.get_lines('b1'),
842
['hello\n', 'pale blue\n', 'world\n'])
844
def test_join_parent_disagreement(self):
845
"""Cannot join weaves with different parents for a version."""
848
wa.add('v1', [], ['hello\n'])
850
wb.add('v1', ['v0'], ['hello\n'])
851
self.assertRaises(WeaveError,
854
def test_join_text_disagreement(self):
855
"""Cannot join weaves with different texts for a version."""
858
wa.add('v1', [], ['hello\n'])
859
wb.add('v1', [], ['not\n', 'hello\n'])
860
self.assertRaises(WeaveError,
863
def test_join_unordered(self):
864
"""Join weaves where indexes differ.
866
The source weave contains a different version at index 0."""
867
wa = self.weave1.copy()
869
wb.add('x1', [], ['line from x1\n'])
870
wb.add('v1', [], ['hello\n'])
871
wb.add('v2', ['v1'], ['hello\n', 'world\n'])
873
eq = self.assertEquals
874
eq(sorted(wa.iter_names()), ['v1', 'v2', 'v3', 'x1',])
875
eq(wa.get_text('x1'), 'line from x1\n')
877
def test_reweave_with_empty(self):
879
wr = reweave(self.weave1, wb)
880
eq = self.assertEquals
881
eq(sorted(wr.iter_names()), ['v1', 'v2', 'v3'])
882
eq(wr.get_lines('v3'), ['hello\n', 'cruel\n', 'world\n'])
883
self.weave1.reweave(wb)
884
self.assertEquals(wr, self.weave1)
886
def test_join_with_ghosts_raises_parent_mismatch(self):
887
wa = self.weave1.copy()
889
wb.add('x1', [], ['line from x1\n'])
890
wb.add('v1', [], ['hello\n'])
891
wb.add('v2', ['v1', 'x1'], ['hello\n', 'world\n'])
892
self.assertRaises(errors.WeaveParentMismatch, wa.join, wb)
894
def test_reweave_with_ghosts(self):
895
"""Join that inserts parents of an existing revision.
897
This can happen when merging from another branch who
898
knows about revisions the destination does not. In
899
this test the second weave knows of an additional parent of
900
v2. Any revisions which are in common still have to have the
902
wa = self.weave1.copy()
904
wb.add('x1', [], ['line from x1\n'])
905
wb.add('v1', [], ['hello\n'])
906
wb.add('v2', ['v1', 'x1'], ['hello\n', 'world\n'])
908
eq = self.assertEquals
909
eq(sorted(wc.iter_names()), ['v1', 'v2', 'v3', 'x1',])
910
eq(wc.get_text('x1'), 'line from x1\n')
911
eq(wc.get_lines('v2'), ['hello\n', 'world\n'])
912
eq(wc.parent_names('v2'), ['v1', 'x1'])
913
self.weave1.reweave(wb)
914
self.assertEquals(wc, self.weave1)
917
if __name__ == '__main__':
920
sys.exit(unittest.main())
added
removed
bzrlib/selftest/test_weave.py
