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
24
"""test suite for weave algorithm"""
26
from pprint import pformat
28
from bzrlib.weave import Weave, WeaveFormatError, WeaveError
29
from bzrlib.weavefile import write_weave, read_weave
30
from bzrlib.selftest import TestCase
31
from bzrlib.osutils import sha_string
37
from sets import Set, ImmutableSet
39
frozenset = ImmutableSet
44
# texts for use in testing
45
TEXT_0 = ["Hello world"]
46
TEXT_1 = ["Hello world",
51
class TestBase(TestCase):
52
def check_read_write(self, k):
53
"""Check the weave k can be written & re-read."""
54
from tempfile import TemporaryFile
63
self.log('serialized weave:')
67
self.log('parents: %s' % (k._parents == k2._parents))
68
self.log(' %r' % k._parents)
69
self.log(' %r' % k2._parents)
73
self.fail('read/write check failed')
83
class StoreText(TestBase):
84
"""Store and retrieve a simple text."""
87
idx = k.add('text0', [], TEXT_0)
88
self.assertEqual(k.get(idx), TEXT_0)
89
self.assertEqual(idx, 0)
93
class AnnotateOne(TestBase):
96
k.add('text0', [], TEXT_0)
97
self.assertEqual(k.annotate(0),
101
class StoreTwo(TestBase):
105
idx = k.add('text0', [], TEXT_0)
106
self.assertEqual(idx, 0)
108
idx = k.add('text1', [], TEXT_1)
109
self.assertEqual(idx, 1)
111
self.assertEqual(k.get(0), TEXT_0)
112
self.assertEqual(k.get(1), TEXT_1)
116
class AddWithGivenSha(TestBase):
118
"""Add with caller-supplied SHA-1"""
122
k.add('text0', [], [t], sha1=sha_string(t))
126
class InvalidAdd(TestBase):
127
"""Try to use invalid version number during add."""
131
self.assertRaises(IndexError,
138
class RepeatedAdd(TestBase):
139
"""Add the same version twice; harmless."""
142
idx = k.add('text0', [], TEXT_0)
143
idx2 = k.add('text0', [], TEXT_0)
144
self.assertEqual(idx, idx2)
148
class InvalidRepeatedAdd(TestBase):
151
idx = k.add('text0', [], TEXT_0)
152
self.assertRaises(WeaveError,
156
['not the same text'])
157
self.assertRaises(WeaveError,
160
[12], # not the right parents
165
class InsertLines(TestBase):
166
"""Store a revision that adds one line to the original.
168
Look at the annotations to make sure that the first line is matched
169
and not stored repeatedly."""
173
k.add('text0', [], ['line 1'])
174
k.add('text1', [0], ['line 1', 'line 2'])
176
self.assertEqual(k.annotate(0),
179
self.assertEqual(k.get(1),
183
self.assertEqual(k.annotate(1),
187
k.add('text2', [0], ['line 1', 'diverged line'])
189
self.assertEqual(k.annotate(2),
191
(2, 'diverged line')])
193
text3 = ['line 1', 'middle line', 'line 2']
198
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
200
self.log("k._weave=" + pformat(k._weave))
202
self.assertEqual(k.annotate(3),
207
# now multiple insertions at different places
210
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
212
self.assertEqual(k.annotate(4),
222
class DeleteLines(TestBase):
223
"""Deletion of lines from existing text.
225
Try various texts all based on a common ancestor."""
229
base_text = ['one', 'two', 'three', 'four']
231
k.add('text0', [], base_text)
233
texts = [['one', 'two', 'three'],
234
['two', 'three', 'four'],
236
['one', 'two', 'three', 'four'],
241
ver = k.add('text%d' % i,
245
self.log('final weave:')
246
self.log('k._weave=' + pformat(k._weave))
248
for i in range(len(texts)):
249
self.assertEqual(k.get(i+1),
255
class SuicideDelete(TestBase):
256
"""Invalid weave which tries to add and delete simultaneously."""
262
k._weave = [('{', 0),
269
################################### SKIPPED
270
# Weave.get doesn't trap this anymore
273
self.assertRaises(WeaveFormatError,
279
class CannedDelete(TestBase):
280
"""Unpack canned weave with deleted lines."""
287
k._weave = [('{', 0),
290
'line to be deleted',
296
self.assertEqual(k.get(0),
298
'line to be deleted',
302
self.assertEqual(k.get(1),
309
class CannedReplacement(TestBase):
310
"""Unpack canned weave with deleted lines."""
314
k._parents = [frozenset(),
317
k._weave = [('{', 0),
320
'line to be deleted',
329
self.assertEqual(k.get(0),
331
'line to be deleted',
335
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
self.assertEqual(k.get(0),
432
self.assertEqual(k.get(1),
434
' added in version 1',
438
self.assertEqual(k.get(2),
443
self.assertEqual(k.get(3),
445
' added in version 1',
452
class DeleteLines2(TestBase):
453
"""Test recording revisions that delete lines.
455
This relies on the weave having a way to represent lines knocked
456
out by a later revision."""
460
k.add('text0', [], ["line the first",
465
self.assertEqual(len(k.get(0)), 4)
467
k.add('text1', [0], ["line the first",
470
self.assertEqual(k.get(1),
474
self.assertEqual(k.annotate(1),
475
[(0, "line the first"),
480
class IncludeVersions(TestBase):
481
"""Check texts that are stored across multiple revisions.
483
Here we manually create a weave with particular encoding and make
484
sure it unpacks properly.
486
Text 0 includes nothing; text 1 includes text 0 and adds some
493
k._parents = [frozenset(), frozenset([0])]
494
k._weave = [('{', 0),
501
self.assertEqual(k.get(1),
505
self.assertEqual(k.get(0),
509
class DivergedIncludes(TestBase):
510
"""Weave with two diverged texts based on version 0.
515
k._parents = [frozenset(),
519
k._weave = [('{', 0),
526
"alternative second line",
530
self.assertEqual(k.get(0),
533
self.assertEqual(k.get(1),
537
self.assertEqual(k.get(2),
539
"alternative second line"])
541
self.assertEqual(list(k.inclusions([2])),
546
class ReplaceLine(TestBase):
550
text0 = ['cheddar', 'stilton', 'gruyere']
551
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
553
k.add('text0', [], text0)
554
k.add('text1', [0], text1)
556
self.log('k._weave=' + pformat(k._weave))
558
self.assertEqual(k.get(0), text0)
559
self.assertEqual(k.get(1), text1)
563
class Merge(TestBase):
564
"""Storage of versions that merge diverged parents"""
569
['header', '', 'line from 1'],
570
['header', '', 'line from 2', 'more from 2'],
571
['header', '', 'line from 1', 'fixup line', 'line from 2'],
574
k.add('text0', [], texts[0])
575
k.add('text1', [0], texts[1])
576
k.add('text2', [0], texts[2])
577
k.add('merge', [0, 1, 2], texts[3])
579
for i, t in enumerate(texts):
580
self.assertEqual(k.get(i), t)
582
self.assertEqual(k.annotate(3),
590
self.assertEqual(list(k.inclusions([3])),
593
self.log('k._weave=' + pformat(k._weave))
595
self.check_read_write(k)
598
class Conflicts(TestBase):
599
"""Test detection of conflicting regions during a merge.
601
A base version is inserted, then two descendents try to
602
insert different lines in the same place. These should be
603
reported as a possible conflict and forwarded to the user."""
608
k.add([], ['aaa', 'bbb'])
609
k.add([0], ['aaa', '111', 'bbb'])
610
k.add([1], ['aaa', '222', 'bbb'])
612
merged = k.merge([1, 2])
614
self.assertEquals([[['aaa']],
620
class NonConflict(TestBase):
621
"""Two descendants insert compatible changes.
623
No conflict should be reported."""
628
k.add([], ['aaa', 'bbb'])
629
k.add([0], ['111', 'aaa', 'ccc', 'bbb'])
630
k.add([1], ['aaa', 'ccc', 'bbb', '222'])
636
class AutoMerge(TestBase):
640
texts = [['header', 'aaa', 'bbb'],
641
['header', 'aaa', 'line from 1', 'bbb'],
642
['header', 'aaa', 'bbb', 'line from 2', 'more from 2'],
645
k.add('text0', [], texts[0])
646
k.add('text1', [0], texts[1])
647
k.add('text2', [0], texts[2])
649
self.log('k._weave=' + pformat(k._weave))
651
m = list(k.mash_iter([0, 1, 2]))
657
'line from 2', 'more from 2'])
661
class Khayyam(TestBase):
662
"""Test changes to multi-line texts, and read/write"""
665
"""A Book of Verses underneath the Bough,
666
A Jug of Wine, a Loaf of Bread, -- and Thou
667
Beside me singing in the Wilderness --
668
Oh, Wilderness were Paradise enow!""",
670
"""A Book of Verses underneath the Bough,
671
A Jug of Wine, a Loaf of Bread, -- and Thou
672
Beside me singing in the Wilderness --
673
Oh, Wilderness were Paradise now!""",
675
"""A Book of poems underneath the tree,
676
A Jug of Wine, a Loaf of Bread,
678
Beside me singing in the Wilderness --
679
Oh, Wilderness were Paradise now!
683
"""A Book of Verses underneath the Bough,
684
A Jug of Wine, a Loaf of Bread,
686
Beside me singing in the Wilderness --
687
Oh, Wilderness were Paradise now!""",
689
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
695
ver = k.add('text%d' % i,
700
self.log("k._weave=" + pformat(k._weave))
702
for i, t in enumerate(texts):
703
self.assertEqual(k.get(i), t)
705
self.check_read_write(k)
709
class MergeCases(TestBase):
710
def doMerge(self, base, a, b, mp):
711
from cStringIO import StringIO
712
from textwrap import dedent
718
w.add('text0', [], map(addcrlf, base))
719
w.add('text1', [0], map(addcrlf, a))
720
w.add('text2', [0], map(addcrlf, b))
722
self.log('weave is:')
725
self.log(tmpf.getvalue())
727
self.log('merge plan:')
728
p = list(w.plan_merge(1, 2))
729
for state, line in p:
731
self.log('%12s | %s' % (state, line[:-1]))
735
mt.writelines(w.weave_merge(p))
737
self.log(mt.getvalue())
739
mp = map(addcrlf, mp)
740
self.assertEqual(mt.readlines(), mp)
743
def testOneInsert(self):
749
def testSeparateInserts(self):
750
self.doMerge(['aaa', 'bbb', 'ccc'],
751
['aaa', 'xxx', 'bbb', 'ccc'],
752
['aaa', 'bbb', 'yyy', 'ccc'],
753
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
755
def testSameInsert(self):
756
self.doMerge(['aaa', 'bbb', 'ccc'],
757
['aaa', 'xxx', 'bbb', 'ccc'],
758
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
759
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
761
def testOverlappedInsert(self):
762
self.doMerge(['aaa', 'bbb'],
763
['aaa', 'xxx', 'yyy', 'bbb'],
764
['aaa', 'xxx', 'bbb'],
765
['aaa', '<<<<', 'xxx', 'yyy', '====', 'xxx', '>>>>', 'bbb'])
767
# really it ought to reduce this to
768
# ['aaa', 'xxx', 'yyy', 'bbb']
771
def testClashReplace(self):
772
self.doMerge(['aaa'],
775
['<<<<', 'xxx', '====', 'yyy', 'zzz', '>>>>'])
777
def testNonClashInsert(self):
778
self.doMerge(['aaa'],
781
['<<<<', 'xxx', 'aaa', '====', 'yyy', 'zzz', '>>>>'])
783
self.doMerge(['aaa'],
789
def testDeleteAndModify(self):
790
"""Clashing delete and modification.
792
If one side modifies a region and the other deletes it then
793
there should be a conflict with one side blank.
796
#######################################
797
# skippd, not working yet
800
self.doMerge(['aaa', 'bbb', 'ccc'],
801
['aaa', 'ddd', 'ccc'],
803
['<<<<', 'aaa', '====', '>>>>', 'ccc'])
807
if __name__ == '__main__':
810
sys.exit(unittest.main())
added
removed
bzrlib/selftest/test_weave.py
