« back to all changes in this revision
Viewing changes to bzrlib/selftest/test_weave.py
- browse files at revision 1236
- compare with another revision
- download diff
- download tarball
- view history from revision 1236
- Committer: Martin Pool
- Date: 2005-09-13 08:20:13 UTC
- Revision ID: mbp@sourcefrog.net-20050913082013-15b0ffec911f2a0c
- fix up imports
- files added:
- HACKING
- bzrlib/plugins
- bzrlib/selftest
- bzrlib/util
- bzrlib/util/effbot
- bzrlib/util/effbot/org
- contrib/emacs
- patches
- tools
- files removed:
- bzrlib/statcache.py
- files renamed:
- elementtree/ => bzrlib/util/elementtree/
- urlgrabber/ => bzrlib/util/urlgrabber/
- contrib/bash/bzr => contrib/bash/bzr.simple
- bzrlib/newinventory.py => contrib/newinventory.py
- files modified:
- .bzrignore
added
removed
bzrlib/selftest/test_weave.py
1
#! /usr/bin/python2.4
2
3
# Copyright (C) 2005 by Canonical Ltd
4
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.
9
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.
14
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
18
19
20
# TODO: tests regarding version names
21
22
23
24
"""test suite for weave algorithm"""
25
26
27
import testsweet
28
from bzrlib.weave import Weave, WeaveFormatError
29
from bzrlib.weavefile import write_weave, read_weave
30
from bzrlib.selftest import TestCase
31
from pprint import pformat
32
33
34
try:
35
set
36
frozenset
37
except NameError:
38
from sets import Set, ImmutableSet
39
set = Set
40
frozenset = ImmutableSet
41
del Set, ImmutableSet
42
43
44
45
# texts for use in testing
46
TEXT_0 = ["Hello world"]
47
TEXT_1 = ["Hello world",
48
"A second line"]
49
50
51
52
class TestBase(TestCase):
53
def check_read_write(self, k):
54
"""Check the weave k can be written & re-read."""
55
from tempfile import TemporaryFile
56
tf = TemporaryFile()
57
58
write_weave(k, tf)
59
tf.seek(0)
60
k2 = read_weave(tf)
61
62
if k != k2:
63
tf.seek(0)
64
self.log('serialized weave:')
65
self.log(tf.read())
66
67
self.log('')
68
self.log('parents: %s' % (k._parents == k2._parents))
69
self.log(' %r' % k._parents)
70
self.log(' %r' % k2._parents)
71
self.log('')
72
73
74
self.fail('read/write check failed')
75
76
77
78
79
class Easy(TestBase):
80
def runTest(self):
81
k = Weave()
82
83
84
class StoreText(TestBase):
85
"""Store and retrieve a simple text."""
86
def runTest(self):
87
k = Weave()
88
idx = k.add('text0', [], TEXT_0)
89
self.assertEqual(k.get(idx), TEXT_0)
90
self.assertEqual(idx, 0)
91
92
93
94
class AnnotateOne(TestBase):
95
def runTest(self):
96
k = Weave()
97
k.add('text0', [], TEXT_0)
98
self.assertEqual(k.annotate(0),
99
[(0, TEXT_0[0])])
100
101
102
class StoreTwo(TestBase):
103
def runTest(self):
104
k = Weave()
105
106
idx = k.add('text0', [], TEXT_0)
107
self.assertEqual(idx, 0)
108
109
idx = k.add('text1', [], TEXT_1)
110
self.assertEqual(idx, 1)
111
112
self.assertEqual(k.get(0), TEXT_0)
113
self.assertEqual(k.get(1), TEXT_1)
114
115
116
117
class InvalidAdd(TestBase):
118
"""Try to use invalid version number during add."""
119
def runTest(self):
120
k = Weave()
121
122
self.assertRaises(IndexError,
123
k.add,
124
'text0',
125
[69],
126
['new text!'])
127
128
129
class InsertLines(TestBase):
130
"""Store a revision that adds one line to the original.
131
132
Look at the annotations to make sure that the first line is matched
133
and not stored repeatedly."""
134
def runTest(self):
135
k = Weave()
136
137
k.add('text0', [], ['line 1'])
138
k.add('text1', [0], ['line 1', 'line 2'])
139
140
self.assertEqual(k.annotate(0),
141
[(0, 'line 1')])
142
143
self.assertEqual(k.get(1),
144
['line 1',
145
'line 2'])
146
147
self.assertEqual(k.annotate(1),
148
[(0, 'line 1'),
149
(1, 'line 2')])
150
151
k.add('text2', [0], ['line 1', 'diverged line'])
152
153
self.assertEqual(k.annotate(2),
154
[(0, 'line 1'),
155
(2, 'diverged line')])
156
157
text3 = ['line 1', 'middle line', 'line 2']
158
k.add('text3',
159
[0, 1],
160
text3)
161
162
# self.log("changes to text3: " + pformat(list(k._delta(set([0, 1]), text3))))
163
164
self.log("k._weave=" + pformat(k._weave))
165
166
self.assertEqual(k.annotate(3),
167
[(0, 'line 1'),
168
(3, 'middle line'),
169
(1, 'line 2')])
170
171
# now multiple insertions at different places
172
k.add('text4',
173
[0, 1, 3],
174
['line 1', 'aaa', 'middle line', 'bbb', 'line 2', 'ccc'])
175
176
self.assertEqual(k.annotate(4),
177
[(0, 'line 1'),
178
(4, 'aaa'),
179
(3, 'middle line'),
180
(4, 'bbb'),
181
(1, 'line 2'),
182
(4, 'ccc')])
183
184
185
186
class DeleteLines(TestBase):
187
"""Deletion of lines from existing text.
188
189
Try various texts all based on a common ancestor."""
190
def runTest(self):
191
k = Weave()
192
193
base_text = ['one', 'two', 'three', 'four']
194
195
k.add('text0', [], base_text)
196
197
texts = [['one', 'two', 'three'],
198
['two', 'three', 'four'],
199
['one', 'four'],
200
['one', 'two', 'three', 'four'],
201
]
202
203
i = 1
204
for t in texts:
205
ver = k.add('text%d' % i,
206
[0], t)
207
i += 1
208
209
self.log('final weave:')
210
self.log('k._weave=' + pformat(k._weave))
211
212
for i in range(len(texts)):
213
self.assertEqual(k.get(i+1),
214
texts[i])
215
216
217
218
219
class SuicideDelete(TestBase):
220
"""Invalid weave which tries to add and delete simultaneously."""
221
def runTest(self):
222
k = Weave()
223
224
k._parents = [(),
225
]
226
k._weave = [('{', 0),
227
'first line',
228
('[', 0),
229
'deleted in 0',
230
(']', 0),
231
('}', 0),
232
]
233
################################### SKIPPED
234
# Weave.get doesn't trap this anymore
235
return
236
237
self.assertRaises(WeaveFormatError,
238
k.get,
239
0)
240
241
242
243
class CannedDelete(TestBase):
244
"""Unpack canned weave with deleted lines."""
245
def runTest(self):
246
k = Weave()
247
248
k._parents = [(),
249
frozenset([0]),
250
]
251
k._weave = [('{', 0),
252
'first line',
253
('[', 1),
254
'line to be deleted',
255
(']', 1),
256
'last line',
257
('}', 0),
258
]
259
260
self.assertEqual(k.get(0),
261
['first line',
262
'line to be deleted',
263
'last line',
264
])
265
266
self.assertEqual(k.get(1),
267
['first line',
268
'last line',
269
])
270
271
272
273
class CannedReplacement(TestBase):
274
"""Unpack canned weave with deleted lines."""
275
def runTest(self):
276
k = Weave()
277
278
k._parents = [frozenset(),
279
frozenset([0]),
280
]
281
k._weave = [('{', 0),
282
'first line',
283
('[', 1),
284
'line to be deleted',
285
(']', 1),
286
('{', 1),
287
'replacement line',
288
('}', 1),
289
'last line',
290
('}', 0),
291
]
292
293
self.assertEqual(k.get(0),
294
['first line',
295
'line to be deleted',
296
'last line',
297
])
298
299
self.assertEqual(k.get(1),
300
['first line',
301
'replacement line',
302
'last line',
303
])
304
305
306
307
class BadWeave(TestBase):
308
"""Test that we trap an insert which should not occur."""
309
def runTest(self):
310
k = Weave()
311
312
k._parents = [frozenset(),
313
]
314
k._weave = ['bad line',
315
('{', 0),
316
'foo {',
317
('{', 1),
318
' added in version 1',
319
('{', 2),
320
' added in v2',
321
('}', 2),
322
' also from v1',
323
('}', 1),
324
'}',
325
('}', 0)]
326
327
################################### SKIPPED
328
# Weave.get doesn't trap this anymore
329
return
330
331
332
self.assertRaises(WeaveFormatError,
333
k.get,
334
0)
335
336
337
class BadInsert(TestBase):
338
"""Test that we trap an insert which should not occur."""
339
def runTest(self):
340
k = Weave()
341
342
k._parents = [frozenset(),
343
frozenset([0]),
344
frozenset([0]),
345
frozenset([0,1,2]),
346
]
347
k._weave = [('{', 0),
348
'foo {',
349
('{', 1),
350
' added in version 1',
351
('{', 1),
352
' more in 1',
353
('}', 1),
354
('}', 1),
355
('}', 0)]
356
357
358
# this is not currently enforced by get
359
return ##########################################
360
361
self.assertRaises(WeaveFormatError,
362
k.get,
363
0)
364
365
self.assertRaises(WeaveFormatError,
366
k.get,
367
1)
368
369
370
class InsertNested(TestBase):
371
"""Insertion with nested instructions."""
372
def runTest(self):
373
k = Weave()
374
375
k._parents = [frozenset(),
376
frozenset([0]),
377
frozenset([0]),
378
frozenset([0,1,2]),
379
]
380
k._weave = [('{', 0),
381
'foo {',
382
('{', 1),
383
' added in version 1',
384
('{', 2),
385
' added in v2',
386
('}', 2),
387
' also from v1',
388
('}', 1),
389
'}',
390
('}', 0)]
391
392
self.assertEqual(k.get(0),
393
['foo {',
394
'}'])
395
396
self.assertEqual(k.get(1),
397
['foo {',
398
' added in version 1',
399
' also from v1',
400
'}'])
401
402
self.assertEqual(k.get(2),
403
['foo {',
404
' added in v2',
405
'}'])
406
407
self.assertEqual(k.get(3),
408
['foo {',
409
' added in version 1',
410
' added in v2',
411
' also from v1',
412
'}'])
413
414
415
416
class DeleteLines2(TestBase):
417
"""Test recording revisions that delete lines.
418
419
This relies on the weave having a way to represent lines knocked
420
out by a later revision."""
421
def runTest(self):
422
k = Weave()
423
424
k.add('text0', [], ["line the first",
425
"line 2",
426
"line 3",
427
"fine"])
428
429
self.assertEqual(len(k.get(0)), 4)
430
431
k.add('text1', [0], ["line the first",
432
"fine"])
433
434
self.assertEqual(k.get(1),
435
["line the first",
436
"fine"])
437
438
self.assertEqual(k.annotate(1),
439
[(0, "line the first"),
440
(0, "fine")])
441
442
443
444
class IncludeVersions(TestBase):
445
"""Check texts that are stored across multiple revisions.
446
447
Here we manually create a weave with particular encoding and make
448
sure it unpacks properly.
449
450
Text 0 includes nothing; text 1 includes text 0 and adds some
451
lines.
452
"""
453
454
def runTest(self):
455
k = Weave()
456
457
k._parents = [frozenset(), frozenset([0])]
458
k._weave = [('{', 0),
459
"first line",
460
('}', 0),
461
('{', 1),
462
"second line",
463
('}', 1)]
464
465
self.assertEqual(k.get(1),
466
["first line",
467
"second line"])
468
469
self.assertEqual(k.get(0),
470
["first line"])
471
472
473
class DivergedIncludes(TestBase):
474
"""Weave with two diverged texts based on version 0.
475
"""
476
def runTest(self):
477
k = Weave()
478
479
k._parents = [frozenset(),
480
frozenset([0]),
481
frozenset([0]),
482
]
483
k._weave = [('{', 0),
484
"first line",
485
('}', 0),
486
('{', 1),
487
"second line",
488
('}', 1),
489
('{', 2),
490
"alternative second line",
491
('}', 2),
492
]
493
494
self.assertEqual(k.get(0),
495
["first line"])
496
497
self.assertEqual(k.get(1),
498
["first line",
499
"second line"])
500
501
self.assertEqual(k.get(2),
502
["first line",
503
"alternative second line"])
504
505
self.assertEqual(list(k.inclusions([2])),
506
[0, 2])
507
508
509
510
class ReplaceLine(TestBase):
511
def runTest(self):
512
k = Weave()
513
514
text0 = ['cheddar', 'stilton', 'gruyere']
515
text1 = ['cheddar', 'blue vein', 'neufchatel', 'chevre']
516
517
k.add('text0', [], text0)
518
k.add('text1', [0], text1)
519
520
self.log('k._weave=' + pformat(k._weave))
521
522
self.assertEqual(k.get(0), text0)
523
self.assertEqual(k.get(1), text1)
524
525
526
527
class Merge(TestBase):
528
"""Storage of versions that merge diverged parents"""
529
def runTest(self):
530
k = Weave()
531
532
texts = [['header'],
533
['header', '', 'line from 1'],
534
['header', '', 'line from 2', 'more from 2'],
535
['header', '', 'line from 1', 'fixup line', 'line from 2'],
536
]
537
538
k.add('text0', [], texts[0])
539
k.add('text1', [0], texts[1])
540
k.add('text2', [0], texts[2])
541
k.add('merge', [0, 1, 2], texts[3])
542
543
for i, t in enumerate(texts):
544
self.assertEqual(k.get(i), t)
545
546
self.assertEqual(k.annotate(3),
547
[(0, 'header'),
548
(1, ''),
549
(1, 'line from 1'),
550
(3, 'fixup line'),
551
(2, 'line from 2'),
552
])
553
554
self.assertEqual(list(k.inclusions([3])),
555
[0, 1, 2, 3])
556
557
self.log('k._weave=' + pformat(k._weave))
558
559
self.check_read_write(k)
560
561
562
class Conflicts(TestBase):
563
"""Test detection of conflicting regions during a merge.
564
565
A base version is inserted, then two descendents try to
566
insert different lines in the same place. These should be
567
reported as a possible conflict and forwarded to the user."""
568
def runTest(self):
569
return # NOT RUN
570
k = Weave()
571
572
k.add([], ['aaa', 'bbb'])
573
k.add([0], ['aaa', '111', 'bbb'])
574
k.add([1], ['aaa', '222', 'bbb'])
575
576
merged = k.merge([1, 2])
577
578
self.assertEquals([[['aaa']],
579
[['111'], ['222']],
580
[['bbb']]])
581
582
583
584
class NonConflict(TestBase):
585
"""Two descendants insert compatible changes.
586
587
No conflict should be reported."""
588
def runTest(self):
589
return # NOT RUN
590
k = Weave()
591
592
k.add([], ['aaa', 'bbb'])
593
k.add([0], ['111', 'aaa', 'ccc', 'bbb'])
594
k.add([1], ['aaa', 'ccc', 'bbb', '222'])
595
596
597
598
599
600
class AutoMerge(TestBase):
601
def runTest(self):
602
k = Weave()
603
604
texts = [['header', 'aaa', 'bbb'],
605
['header', 'aaa', 'line from 1', 'bbb'],
606
['header', 'aaa', 'bbb', 'line from 2', 'more from 2'],
607
]
608
609
k.add('text0', [], texts[0])
610
k.add('text1', [0], texts[1])
611
k.add('text2', [0], texts[2])
612
613
self.log('k._weave=' + pformat(k._weave))
614
615
m = list(k.mash_iter([0, 1, 2]))
616
617
self.assertEqual(m,
618
['header', 'aaa',
619
'line from 1',
620
'bbb',
621
'line from 2', 'more from 2'])
622
623
624
625
class Khayyam(TestBase):
626
"""Test changes to multi-line texts, and read/write"""
627
def runTest(self):
628
rawtexts = [
629
"""A Book of Verses underneath the Bough,
630
A Jug of Wine, a Loaf of Bread, -- and Thou
631
Beside me singing in the Wilderness --
632
Oh, Wilderness were Paradise enow!""",
633
634
"""A Book of Verses underneath the Bough,
635
A Jug of Wine, a Loaf of Bread, -- and Thou
636
Beside me singing in the Wilderness --
637
Oh, Wilderness were Paradise now!""",
638
639
"""A Book of poems underneath the tree,
640
A Jug of Wine, a Loaf of Bread,
641
and Thou
642
Beside me singing in the Wilderness --
643
Oh, Wilderness were Paradise now!
644
645
-- O. Khayyam""",
646
647
"""A Book of Verses underneath the Bough,
648
A Jug of Wine, a Loaf of Bread,
649
and Thou
650
Beside me singing in the Wilderness --
651
Oh, Wilderness were Paradise now!""",
652
]
653
texts = [[l.strip() for l in t.split('\n')] for t in rawtexts]
654
655
k = Weave()
656
parents = set()
657
i = 0
658
for t in texts:
659
ver = k.add('text%d' % i,
660
list(parents), t)
661
parents.add(ver)
662
i += 1
663
664
self.log("k._weave=" + pformat(k._weave))
665
666
for i, t in enumerate(texts):
667
self.assertEqual(k.get(i), t)
668
669
self.check_read_write(k)
670
671
672
673
class MergeCases(TestBase):
674
def doMerge(self, base, a, b, mp):
675
from cStringIO import StringIO
676
from textwrap import dedent
677
678
def addcrlf(x):
679
return x + '\n'
680
681
w = Weave()
682
w.add('text0', [], map(addcrlf, base))
683
w.add('text1', [0], map(addcrlf, a))
684
w.add('text2', [0], map(addcrlf, b))
685
686
self.log('weave is:')
687
tmpf = StringIO()
688
write_weave(w, tmpf)
689
self.log(tmpf.getvalue())
690
691
self.log('merge plan:')
692
p = list(w.plan_merge(1, 2))
693
for state, line in p:
694
if line:
695
self.log('%12s | %s' % (state, line[:-1]))
696
697
self.log('merge:')
698
mt = StringIO()
699
mt.writelines(w.weave_merge(p))
700
mt.seek(0)
701
self.log(mt.getvalue())
702
703
mp = map(addcrlf, mp)
704
self.assertEqual(mt.readlines(), mp)
705
706
707
def testOneInsert(self):
708
self.doMerge([],
709
['aa'],
710
[],
711
['aa'])
712
713
def testSeparateInserts(self):
714
self.doMerge(['aaa', 'bbb', 'ccc'],
715
['aaa', 'xxx', 'bbb', 'ccc'],
716
['aaa', 'bbb', 'yyy', 'ccc'],
717
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
718
719
def testSameInsert(self):
720
self.doMerge(['aaa', 'bbb', 'ccc'],
721
['aaa', 'xxx', 'bbb', 'ccc'],
722
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'],
723
['aaa', 'xxx', 'bbb', 'yyy', 'ccc'])
724
725
def testOverlappedInsert(self):
726
self.doMerge(['aaa', 'bbb'],
727
['aaa', 'xxx', 'yyy', 'bbb'],
728
['aaa', 'xxx', 'bbb'],
729
['aaa', '<<<<', 'xxx', 'yyy', '====', 'xxx', '>>>>', 'bbb'])
730
731
# really it ought to reduce this to
732
# ['aaa', 'xxx', 'yyy', 'bbb']
733
734
735
def testClashReplace(self):
736
self.doMerge(['aaa'],
737
['xxx'],
738
['yyy', 'zzz'],
739
['<<<<', 'xxx', '====', 'yyy', 'zzz', '>>>>'])
740
741
def testNonClashInsert(self):
742
self.doMerge(['aaa'],
743
['xxx', 'aaa'],
744
['yyy', 'zzz'],
745
['<<<<', 'xxx', 'aaa', '====', 'yyy', 'zzz', '>>>>'])
746
747
self.doMerge(['aaa'],
748
['aaa'],
749
['yyy', 'zzz'],
750
['yyy', 'zzz'])
751
752
753
def testDeleteAndModify(self):
754
"""Clashing delete and modification.
755
756
If one side modifies a region and the other deletes it then
757
there should be a conflict with one side blank.
758
"""
759
760
#######################################
761
# skippd, not working yet
762
return
763
764
self.doMerge(['aaa', 'bbb', 'ccc'],
765
['aaa', 'ddd', 'ccc'],
766
['aaa', 'ccc'],
767
['<<<<', 'aaa', '====', '>>>>', 'ccc'])
768
769
770
771
if __name__ == '__main__':
772
import sys
773
import unittest
774
sys.exit(unittest.main())
775
Loggerhead is a web-based interface for Breezy
Version: 2.0.1