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 JoinWeavesTests(TestBase):
687
super(JoinWeavesTests, self).setUp()
688
self.weave1 = Weave()
689
self.lines1 = ['hello\n']
690
self.lines3 = ['hello\n', 'cruel\n', 'world\n']
691
self.weave1.add_lines('v1', [], self.lines1)
692
self.weave1.add_lines('v2', ['v1'], ['hello\n', 'world\n'])
693
self.weave1.add_lines('v3', ['v2'], self.lines3)
695
def test_join_empty(self):
696
"""Join two empty weaves."""
697
eq = self.assertEqual
703
def test_join_empty_to_nonempty(self):
704
"""Join empty weave onto nonempty."""
705
self.weave1.join(Weave())
706
self.assertEqual(len(self.weave1), 3)
708
def test_join_unrelated(self):
709
"""Join two weaves with no history in common."""
711
wb.add_lines('b1', [], ['line from b\n'])
714
eq = self.assertEqual
716
eq(sorted(w1.versions()),
717
['b1', 'v1', 'v2', 'v3'])
719
def test_join_related(self):
720
wa = self.weave1.copy()
721
wb = self.weave1.copy()
722
wa.add_lines('a1', ['v3'], ['hello\n', 'sweet\n', 'world\n'])
723
wb.add_lines('b1', ['v3'], ['hello\n', 'pale blue\n', 'world\n'])
724
eq = self.assertEquals
729
eq(wa.get_lines('b1'),
730
['hello\n', 'pale blue\n', 'world\n'])
732
def test_join_parent_disagreement(self):
733
#join reconciles differening parents into a union.
736
wa.add_lines('v1', [], ['hello\n'])
737
wb.add_lines('v0', [], [])
738
wb.add_lines('v1', ['v0'], ['hello\n'])
740
self.assertEqual(['v0'], wa.get_parents('v1'))
742
def test_join_text_disagreement(self):
743
"""Cannot join weaves with different texts for a version."""
746
wa.add_lines('v1', [], ['hello\n'])
747
wb.add_lines('v1', [], ['not\n', 'hello\n'])
748
self.assertRaises(WeaveError,
751
def test_join_unordered(self):
752
"""Join weaves where indexes differ.
754
The source weave contains a different version at index 0."""
755
wa = self.weave1.copy()
757
wb.add_lines('x1', [], ['line from x1\n'])
758
wb.add_lines('v1', [], ['hello\n'])
759
wb.add_lines('v2', ['v1'], ['hello\n', 'world\n'])
761
eq = self.assertEquals
762
eq(sorted(wa.versions()), ['v1', 'v2', 'v3', 'x1',])
763
eq(wa.get_text('x1'), 'line from x1\n')
765
def test_written_detection(self):
766
# Test detection of weave file corruption.
768
# Make sure that we can detect if a weave file has
769
# been corrupted. This doesn't test all forms of corruption,
770
# but it at least helps verify the data you get, is what you want.
771
from cStringIO import StringIO
774
w.add_lines('v1', [], ['hello\n'])
775
w.add_lines('v2', ['v1'], ['hello\n', 'there\n'])
780
# Because we are corrupting, we need to make sure we have the exact text
781
self.assertEquals('# bzr weave file v5\n'
782
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
783
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
784
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n',
787
# Change a single letter
788
tmpf = StringIO('# bzr weave file v5\n'
789
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
790
'i 0\n1 90f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
791
'w\n{ 0\n. hello\n}\n{ 1\n. There\n}\nW\n')
795
self.assertEqual('hello\n', w.get_text('v1'))
796
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
797
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
798
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
800
# Change the sha checksum
801
tmpf = StringIO('# bzr weave file v5\n'
802
'i\n1 f572d396fae9206628714fb2ce00f72e94f2258f\nn v1\n\n'
803
'i 0\n1 f0f265c6e75f1c8f9ab76dcf85528352c5f215ef\nn v2\n\n'
804
'w\n{ 0\n. hello\n}\n{ 1\n. there\n}\nW\n')
808
self.assertEqual('hello\n', w.get_text('v1'))
809
self.assertRaises(errors.WeaveInvalidChecksum, w.get_text, 'v2')
810
self.assertRaises(errors.WeaveInvalidChecksum, w.get_lines, 'v2')
811
self.assertRaises(errors.WeaveInvalidChecksum, w.check)
814
class InstrumentedWeave(Weave):
815
"""Keep track of how many times functions are called."""
817
def __init__(self, weave_name=None):
818
self._extract_count = 0
819
Weave.__init__(self, weave_name=weave_name)
821
def _extract(self, versions):
822
self._extract_count += 1
823
return Weave._extract(self, versions)
826
class JoinOptimization(TestCase):
827
"""Test that Weave.join() doesn't extract all texts, only what must be done."""
830
w1 = InstrumentedWeave()
831
w2 = InstrumentedWeave()
834
txt1 = ['a\n', 'b\n']
835
txt2 = ['a\n', 'c\n']
836
txt3 = ['a\n', 'b\n', 'c\n']
838
w1.add_lines('txt0', [], txt0) # extract 1a
839
w2.add_lines('txt0', [], txt0) # extract 1b
840
w1.add_lines('txt1', ['txt0'], txt1)# extract 2a
841
w2.add_lines('txt2', ['txt0'], txt2)# extract 2b
842
w1.join(w2) # extract 3a to add txt2
843
w2.join(w1) # extract 3b to add txt1
845
w1.add_lines('txt3', ['txt1', 'txt2'], txt3) # extract 4a
846
w2.add_lines('txt3', ['txt2', 'txt1'], txt3) # extract 4b
847
# These secretly have inverted parents
849
# This should not have to do any extractions
850
w1.join(w2) # NO extract, texts already present with same parents
851
w2.join(w1) # NO extract, texts already present with same parents
853
self.assertEqual(4, w1._extract_count)
854
self.assertEqual(4, w2._extract_count)
856
def test_double_parent(self):
857
# It should not be considered illegal to add
858
# a revision with the same parent twice
859
w1 = InstrumentedWeave()
860
w2 = InstrumentedWeave()
863
txt1 = ['a\n', 'b\n']
864
txt2 = ['a\n', 'c\n']
865
txt3 = ['a\n', 'b\n', 'c\n']
867
w1.add_lines('txt0', [], txt0)
868
w2.add_lines('txt0', [], txt0)
869
w1.add_lines('txt1', ['txt0'], txt1)
870
w2.add_lines('txt1', ['txt0', 'txt0'], txt1)
871
# Same text, effectively the same, because the
872
# parent is only repeated
873
w1.join(w2) # extract 3a to add txt2
874
w2.join(w1) # extract 3b to add txt1
877
class TestNeedsReweave(TestCase):
878
"""Internal corner cases for when reweave is needed."""
880
def test_compatible_parents(self):
882
my_parents = set([1, 2, 3])
884
self.assertTrue(w1._compatible_parents(my_parents, set([3])))
886
self.assertTrue(w1._compatible_parents(my_parents, set(my_parents)))
887
# same empty corner case
888
self.assertTrue(w1._compatible_parents(set(), set()))
889
# other cannot contain stuff my_parents does not
890
self.assertFalse(w1._compatible_parents(set(), set([1])))
891
self.assertFalse(w1._compatible_parents(my_parents, set([1, 2, 3, 4])))
892
self.assertFalse(w1._compatible_parents(my_parents, set([4])))
added
removed
bzrlib/tests/test_weave.py
