← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_diff.py

  • Committer: Wouter van Heyst
  • Date: 2006-06-06 12:06:20 UTC
  • mfrom: (1740 +trunk)
  • mto: This revision was merged to the branch mainline in revision 1752.
  • Revision ID: larstiq@larstiq.dyndns.org-20060606120620-50066b0951e4ef7c
merge bzr.dev 1740

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_diff.py
 
1
# Copyright (C) 2005, 2006 Canonical Development Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
 
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
16
 
1
17
from cStringIO import StringIO
2
18
 
3
19
from bzrlib.diff import internal_diff
4
20
from bzrlib.errors import BinaryFile
5
 
from bzrlib.tests import TestCase
 
21
import bzrlib.patiencediff
 
22
from bzrlib.tests import TestCase, TestCaseInTempDir
6
23
 
7
24
 
8
25
def udiff_lines(old, new, allow_binary=False):
11
28
    output.seek(0, 0)
12
29
    return output.readlines()
13
30
 
 
31
 
14
32
class TestDiff(TestCase):
 
33
 
15
34
    def test_add_nl(self):
16
35
        """diff generates a valid diff for patches that add a newline"""
17
36
        lines = udiff_lines(['boo'], ['boo\n'])
56
75
        self.assertRaises(BinaryFile, udiff_lines, [], [1023 * 'a' + '\x00'])
57
76
        udiff_lines([1023 * 'a' + '\x00'], [], allow_binary=True)
58
77
        udiff_lines([], [1023 * 'a' + '\x00'], allow_binary=True)
 
78
 
 
79
    def test_internal_diff_default(self):
 
80
        # Default internal diff encoding is utf8
 
81
        output = StringIO()
 
82
        internal_diff(u'old_\xb5', ['old_text\n'],
 
83
                    u'new_\xe5', ['new_text\n'], output)
 
84
        lines = output.getvalue().splitlines(True)
 
85
        self.check_patch(lines)
 
86
        self.assertEquals(['--- old_\xc2\xb5\t\n',
 
87
                           '+++ new_\xc3\xa5\t\n',
 
88
                           '@@ -1,1 +1,1 @@\n',
 
89
                           '-old_text\n',
 
90
                           '+new_text\n',
 
91
                           '\n',
 
92
                          ]
 
93
                          , lines)
 
94
 
 
95
    def test_internal_diff_utf8(self):
 
96
        output = StringIO()
 
97
        internal_diff(u'old_\xb5', ['old_text\n'],
 
98
                    u'new_\xe5', ['new_text\n'], output,
 
99
                    path_encoding='utf8')
 
100
        lines = output.getvalue().splitlines(True)
 
101
        self.check_patch(lines)
 
102
        self.assertEquals(['--- old_\xc2\xb5\t\n',
 
103
                           '+++ new_\xc3\xa5\t\n',
 
104
                           '@@ -1,1 +1,1 @@\n',
 
105
                           '-old_text\n',
 
106
                           '+new_text\n',
 
107
                           '\n',
 
108
                          ]
 
109
                          , lines)
 
110
 
 
111
    def test_internal_diff_iso_8859_1(self):
 
112
        output = StringIO()
 
113
        internal_diff(u'old_\xb5', ['old_text\n'],
 
114
                    u'new_\xe5', ['new_text\n'], output,
 
115
                    path_encoding='iso-8859-1')
 
116
        lines = output.getvalue().splitlines(True)
 
117
        self.check_patch(lines)
 
118
        self.assertEquals(['--- old_\xb5\t\n',
 
119
                           '+++ new_\xe5\t\n',
 
120
                           '@@ -1,1 +1,1 @@\n',
 
121
                           '-old_text\n',
 
122
                           '+new_text\n',
 
123
                           '\n',
 
124
                          ]
 
125
                          , lines)
 
126
 
 
127
    def test_internal_diff_returns_bytes(self):
 
128
        import StringIO
 
129
        output = StringIO.StringIO()
 
130
        internal_diff(u'old_\xb5', ['old_text\n'],
 
131
                    u'new_\xe5', ['new_text\n'], output)
 
132
        self.failUnless(isinstance(output.getvalue(), str),
 
133
            'internal_diff should return bytestrings')
 
134
 
 
135
 
 
136
class TestPatienceDiffLib(TestCase):
 
137
 
 
138
    def test_unique_lcs(self):
 
139
        unique_lcs = bzrlib.patiencediff.unique_lcs
 
140
        self.assertEquals(unique_lcs('', ''), [])
 
141
        self.assertEquals(unique_lcs('a', 'a'), [(0,0)])
 
142
        self.assertEquals(unique_lcs('a', 'b'), [])
 
143
        self.assertEquals(unique_lcs('ab', 'ab'), [(0,0), (1,1)])
 
144
        self.assertEquals(unique_lcs('abcde', 'cdeab'), [(2,0), (3,1), (4,2)])
 
145
        self.assertEquals(unique_lcs('cdeab', 'abcde'), [(0,2), (1,3), (2,4)])
 
146
        self.assertEquals(unique_lcs('abXde', 'abYde'), [(0,0), (1,1), 
 
147
                                                         (3,3), (4,4)])
 
148
        self.assertEquals(unique_lcs('acbac', 'abc'), [(2,1)])
 
149
 
 
150
    def test_recurse_matches(self):
 
151
        def test_one(a, b, matches):
 
152
            test_matches = []
 
153
            bzrlib.patiencediff.recurse_matches(a, b, 0, 0, len(a), len(b),
 
154
                test_matches, 10)
 
155
            self.assertEquals(test_matches, matches)
 
156
 
 
157
        test_one(['a', '', 'b', '', 'c'], ['a', 'a', 'b', 'c', 'c'],
 
158
                 [(0, 0), (2, 2), (4, 4)])
 
159
        test_one(['a', 'c', 'b', 'a', 'c'], ['a', 'b', 'c'],
 
160
                 [(0, 0), (2, 1), (4, 2)])
 
161
 
 
162
        # recurse_matches doesn't match non-unique 
 
163
        # lines surrounded by bogus text.
 
164
        # The update has been done in patiencediff.SequenceMatcher instead
 
165
 
 
166
        # This is what it could be
 
167
        #test_one('aBccDe', 'abccde', [(0,0), (2,2), (3,3), (5,5)])
 
168
 
 
169
        # This is what it currently gives:
 
170
        test_one('aBccDe', 'abccde', [(0,0), (5,5)])
 
171
 
 
172
    def test_matching_blocks(self):
 
173
        def chk_blocks(a, b, expected_blocks):
 
174
            # difflib always adds a signature of the total
 
175
            # length, with no matching entries at the end
 
176
            s = bzrlib.patiencediff.PatienceSequenceMatcher(None, a, b)
 
177
            blocks = s.get_matching_blocks()
 
178
            self.assertEquals((len(a), len(b), 0), blocks[-1])
 
179
            self.assertEquals(expected_blocks, blocks[:-1])
 
180
 
 
181
        # Some basic matching tests
 
182
        chk_blocks('', '', [])
 
183
        chk_blocks([], [], [])
 
184
        chk_blocks('abcd', 'abcd', [(0, 0, 4)])
 
185
        chk_blocks('abcd', 'abce', [(0, 0, 3)])
 
186
        chk_blocks('eabc', 'abce', [(1, 0, 3)])
 
187
        chk_blocks('eabce', 'abce', [(1, 0, 4)])
 
188
        chk_blocks('abcde', 'abXde', [(0, 0, 2), (3, 3, 2)])
 
189
        chk_blocks('abcde', 'abXYZde', [(0, 0, 2), (3, 5, 2)])
 
190
        chk_blocks('abde', 'abXYZde', [(0, 0, 2), (2, 5, 2)])
 
191
        # This may check too much, but it checks to see that 
 
192
        # a copied block stays attached to the previous section,
 
193
        # not the later one.
 
194
        # difflib would tend to grab the trailing longest match
 
195
        # which would make the diff not look right
 
196
        chk_blocks('abcdefghijklmnop', 'abcdefxydefghijklmnop',
 
197
                   [(0, 0, 6), (6, 11, 10)])
 
198
 
 
199
        # make sure it supports passing in lists
 
200
        chk_blocks(
 
201
                   ['hello there\n',
 
202
                    'world\n',
 
203
                    'how are you today?\n'],
 
204
                   ['hello there\n',
 
205
                    'how are you today?\n'],
 
206
                [(0, 0, 1), (2, 1, 1)])
 
207
 
 
208
        # non unique lines surrounded by non-matching lines
 
209
        # won't be found
 
210
        chk_blocks('aBccDe', 'abccde', [(0,0,1), (5,5,1)])
 
211
 
 
212
        # But they only need to be locally unique
 
213
        chk_blocks('aBcDec', 'abcdec', [(0,0,1), (2,2,1), (4,4,2)])
 
214
 
 
215
        # non unique blocks won't be matched
 
216
        chk_blocks('aBcdEcdFg', 'abcdecdfg', [(0,0,1), (8,8,1)])
 
217
 
 
218
        # but locally unique ones will
 
219
        chk_blocks('aBcdEeXcdFg', 'abcdecdfg', [(0,0,1), (2,2,2),
 
220
                                              (5,4,1), (7,5,2), (10,8,1)])
 
221
 
 
222
        chk_blocks('abbabbXd', 'cabbabxd', [(7,7,1)])
 
223
        chk_blocks('abbabbbb', 'cabbabbc', [])
 
224
        chk_blocks('bbbbbbbb', 'cbbbbbbc', [])
 
225
 
 
226
    def test_opcodes(self):
 
227
        def chk_ops(a, b, expected_codes):
 
228
            s = bzrlib.patiencediff.PatienceSequenceMatcher(None, a, b)
 
229
            self.assertEquals(expected_codes, s.get_opcodes())
 
230
 
 
231
        chk_ops('', '', [])
 
232
        chk_ops([], [], [])
 
233
        chk_ops('abcd', 'abcd', [('equal',    0,4, 0,4)])
 
234
        chk_ops('abcd', 'abce', [('equal',   0,3, 0,3),
 
235
                                 ('replace', 3,4, 3,4)
 
236
                                ])
 
237
        chk_ops('eabc', 'abce', [('delete', 0,1, 0,0),
 
238
                                 ('equal',  1,4, 0,3),
 
239
                                 ('insert', 4,4, 3,4)
 
240
                                ])
 
241
        chk_ops('eabce', 'abce', [('delete', 0,1, 0,0),
 
242
                                  ('equal',  1,5, 0,4)
 
243
                                 ])
 
244
        chk_ops('abcde', 'abXde', [('equal',   0,2, 0,2),
 
245
                                   ('replace', 2,3, 2,3),
 
246
                                   ('equal',   3,5, 3,5)
 
247
                                  ])
 
248
        chk_ops('abcde', 'abXYZde', [('equal',   0,2, 0,2),
 
249
                                     ('replace', 2,3, 2,5),
 
250
                                     ('equal',   3,5, 5,7)
 
251
                                    ])
 
252
        chk_ops('abde', 'abXYZde', [('equal',  0,2, 0,2),
 
253
                                    ('insert', 2,2, 2,5),
 
254
                                    ('equal',  2,4, 5,7)
 
255
                                   ])
 
256
        chk_ops('abcdefghijklmnop', 'abcdefxydefghijklmnop',
 
257
                [('equal',  0,6,  0,6),
 
258
                 ('insert', 6,6,  6,11),
 
259
                 ('equal',  6,16, 11,21)
 
260
                ])
 
261
        chk_ops(
 
262
                [ 'hello there\n'
 
263
                , 'world\n'
 
264
                , 'how are you today?\n'],
 
265
                [ 'hello there\n'
 
266
                , 'how are you today?\n'],
 
267
                [('equal',  0,1, 0,1),
 
268
                 ('delete', 1,2, 1,1),
 
269
                 ('equal',  2,3, 1,2),
 
270
                ])
 
271
        chk_ops('aBccDe', 'abccde', 
 
272
                [('equal',   0,1, 0,1),
 
273
                 ('replace', 1,5, 1,5),
 
274
                 ('equal',   5,6, 5,6),
 
275
                ])
 
276
        chk_ops('aBcDec', 'abcdec', 
 
277
                [('equal',   0,1, 0,1),
 
278
                 ('replace', 1,2, 1,2),
 
279
                 ('equal',   2,3, 2,3),
 
280
                 ('replace', 3,4, 3,4),
 
281
                 ('equal',   4,6, 4,6),
 
282
                ])
 
283
        chk_ops('aBcdEcdFg', 'abcdecdfg', 
 
284
                [('equal',   0,1, 0,1),
 
285
                 ('replace', 1,8, 1,8),
 
286
                 ('equal',   8,9, 8,9)
 
287
                ])
 
288
        chk_ops('aBcdEeXcdFg', 'abcdecdfg', 
 
289
                [('equal',   0,1, 0,1),
 
290
                 ('replace', 1,2, 1,2),
 
291
                 ('equal',   2,4, 2,4),
 
292
                 ('delete', 4,5, 4,4),
 
293
                 ('equal',   5,6, 4,5),
 
294
                 ('delete', 6,7, 5,5),
 
295
                 ('equal',   7,9, 5,7),
 
296
                 ('replace', 9,10, 7,8),
 
297
                 ('equal',   10,11, 8,9)
 
298
                ])
 
299
 
 
300
    def test_multiple_ranges(self):
 
301
        # There was an earlier bug where we used a bad set of ranges,
 
302
        # this triggers that specific bug, to make sure it doesn't regress
 
303
        def chk_blocks(a, b, expected_blocks):
 
304
            # difflib always adds a signature of the total
 
305
            # length, with no matching entries at the end
 
306
            s = bzrlib.patiencediff.PatienceSequenceMatcher(None, a, b)
 
307
            blocks = s.get_matching_blocks()
 
308
            x = blocks.pop()
 
309
            self.assertEquals(x, (len(a), len(b), 0))
 
310
            self.assertEquals(expected_blocks, blocks)
 
311
 
 
312
        chk_blocks('abcdefghijklmnop'
 
313
                 , 'abcXghiYZQRSTUVWXYZijklmnop'
 
314
                 , [(0, 0, 3), (6, 4, 3), (9, 20, 7)])
 
315
 
 
316
        chk_blocks('ABCd efghIjk  L'
 
317
                 , 'AxyzBCn mo pqrstuvwI1 2  L'
 
318
                 , [(0,0,1), (1, 4, 2), (9, 19, 1), (12, 23, 3)])
 
319
 
 
320
        # These are rot13 code snippets.
 
321
        chk_blocks('''\
 
322
    trg nqqrq jura lbh nqq n svyr va gur qverpgbel.
 
323
    """
 
324
    gnxrf_netf = ['svyr*']
 
325
    gnxrf_bcgvbaf = ['ab-erphefr']
 
326
  
 
327
    qrs eha(frys, svyr_yvfg, ab_erphefr=Snyfr):
 
328
        sebz omeyvo.nqq vzcbeg fzneg_nqq, nqq_ercbegre_cevag, nqq_ercbegre_ahyy
 
329
        vs vf_dhvrg():
 
330
            ercbegre = nqq_ercbegre_ahyy
 
331
        ryfr:
 
332
            ercbegre = nqq_ercbegre_cevag
 
333
        fzneg_nqq(svyr_yvfg, abg ab_erphefr, ercbegre)
 
334
 
 
335
 
 
336
pynff pzq_zxqve(Pbzznaq):
 
337
'''.splitlines(True), '''\
 
338
    trg nqqrq jura lbh nqq n svyr va gur qverpgbel.
 
339
 
 
340
    --qel-eha jvyy fubj juvpu svyrf jbhyq or nqqrq, ohg abg npghnyyl 
 
341
    nqq gurz.
 
342
    """
 
343
    gnxrf_netf = ['svyr*']
 
344
    gnxrf_bcgvbaf = ['ab-erphefr', 'qel-eha']
 
345
 
 
346
    qrs eha(frys, svyr_yvfg, ab_erphefr=Snyfr, qel_eha=Snyfr):
 
347
        vzcbeg omeyvo.nqq
 
348
 
 
349
        vs qel_eha:
 
350
            vs vf_dhvrg():
 
351
                # Guvf vf cbvagyrff, ohg V'q engure abg envfr na reebe
 
352
                npgvba = omeyvo.nqq.nqq_npgvba_ahyy
 
353
            ryfr:
 
354
  npgvba = omeyvo.nqq.nqq_npgvba_cevag
 
355
        ryvs vf_dhvrg():
 
356
            npgvba = omeyvo.nqq.nqq_npgvba_nqq
 
357
        ryfr:
 
358
       npgvba = omeyvo.nqq.nqq_npgvba_nqq_naq_cevag
 
359
 
 
360
        omeyvo.nqq.fzneg_nqq(svyr_yvfg, abg ab_erphefr, npgvba)
 
361
 
 
362
 
 
363
pynff pzq_zxqve(Pbzznaq):
 
364
'''.splitlines(True)
 
365
, [(0,0,1), (1, 4, 2), (9, 19, 1), (12, 23, 3)])
 
366
 
 
367
    def test_patience_unified_diff(self):
 
368
        txt_a = ['hello there\n',
 
369
                 'world\n',
 
370
                 'how are you today?\n']
 
371
        txt_b = ['hello there\n',
 
372
                 'how are you today?\n']
 
373
        unified_diff = bzrlib.patiencediff.unified_diff
 
374
        psm = bzrlib.patiencediff.PatienceSequenceMatcher
 
375
        self.assertEquals([ '---  \n',
 
376
                           '+++  \n',
 
377
                           '@@ -1,3 +1,2 @@\n',
 
378
                           ' hello there\n',
 
379
                           '-world\n',
 
380
                           ' how are you today?\n'
 
381
                          ]
 
382
                          , list(unified_diff(txt_a, txt_b,
 
383
                                 sequencematcher=psm)))
 
384
        txt_a = map(lambda x: x+'\n', 'abcdefghijklmnop')
 
385
        txt_b = map(lambda x: x+'\n', 'abcdefxydefghijklmnop')
 
386
        # This is the result with LongestCommonSubstring matching
 
387
        self.assertEquals(['---  \n',
 
388
                           '+++  \n',
 
389
                           '@@ -1,6 +1,11 @@\n',
 
390
                           ' a\n',
 
391
                           ' b\n',
 
392
                           ' c\n',
 
393
                           '+d\n',
 
394
                           '+e\n',
 
395
                           '+f\n',
 
396
                           '+x\n',
 
397
                           '+y\n',
 
398
                           ' d\n',
 
399
                           ' e\n',
 
400
                           ' f\n']
 
401
                          , list(unified_diff(txt_a, txt_b)))
 
402
        # And the patience diff
 
403
        self.assertEquals(['---  \n',
 
404
                           '+++  \n',
 
405
                           '@@ -4,6 +4,11 @@\n',
 
406
                           ' d\n',
 
407
                           ' e\n',
 
408
                           ' f\n',
 
409
                           '+x\n',
 
410
                           '+y\n',
 
411
                           '+d\n',
 
412
                           '+e\n',
 
413
                           '+f\n',
 
414
                           ' g\n',
 
415
                           ' h\n',
 
416
                           ' i\n',
 
417
                          ]
 
418
                          , list(unified_diff(txt_a, txt_b,
 
419
                                 sequencematcher=psm)))
 
420
 
 
421
 
 
422
class TestPatienceDiffLibFiles(TestCaseInTempDir):
 
423
 
 
424
    def test_patience_unified_diff_files(self):
 
425
        txt_a = ['hello there\n',
 
426
                 'world\n',
 
427
                 'how are you today?\n']
 
428
        txt_b = ['hello there\n',
 
429
                 'how are you today?\n']
 
430
        open('a1', 'wb').writelines(txt_a)
 
431
        open('b1', 'wb').writelines(txt_b)
 
432
 
 
433
        unified_diff_files = bzrlib.patiencediff.unified_diff_files
 
434
        psm = bzrlib.patiencediff.PatienceSequenceMatcher
 
435
        self.assertEquals(['--- a1 \n',
 
436
                           '+++ b1 \n',
 
437
                           '@@ -1,3 +1,2 @@\n',
 
438
                           ' hello there\n',
 
439
                           '-world\n',
 
440
                           ' how are you today?\n',
 
441
                          ]
 
442
                          , list(unified_diff_files('a1', 'b1',
 
443
                                 sequencematcher=psm)))
 
444
 
 
445
        txt_a = map(lambda x: x+'\n', 'abcdefghijklmnop')
 
446
        txt_b = map(lambda x: x+'\n', 'abcdefxydefghijklmnop')
 
447
        open('a2', 'wb').writelines(txt_a)
 
448
        open('b2', 'wb').writelines(txt_b)
 
449
 
 
450
        # This is the result with LongestCommonSubstring matching
 
451
        self.assertEquals(['--- a2 \n',
 
452
                           '+++ b2 \n',
 
453
                           '@@ -1,6 +1,11 @@\n',
 
454
                           ' a\n',
 
455
                           ' b\n',
 
456
                           ' c\n',
 
457
                           '+d\n',
 
458
                           '+e\n',
 
459
                           '+f\n',
 
460
                           '+x\n',
 
461
                           '+y\n',
 
462
                           ' d\n',
 
463
                           ' e\n',
 
464
                           ' f\n']
 
465
                          , list(unified_diff_files('a2', 'b2')))
 
466
 
 
467
        # And the patience diff
 
468
        self.assertEquals(['--- a2 \n',
 
469
                           '+++ b2 \n',
 
470
                           '@@ -4,6 +4,11 @@\n',
 
471
                           ' d\n',
 
472
                           ' e\n',
 
473
                           ' f\n',
 
474
                           '+x\n',
 
475
                           '+y\n',
 
476
                           '+d\n',
 
477
                           '+e\n',
 
478
                           '+f\n',
 
479
                           ' g\n',
 
480
                           ' h\n',
 
481
                           ' i\n',
 
482
                          ]
 
483
                          , list(unified_diff_files('a2', 'b2',
 
484
                                 sequencematcher=psm)))