/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/mdiff.py

  • Committer: Martin Pool
  • Date: 2005-08-24 08:59:32 UTC
  • Revision ID: mbp@sourcefrog.net-20050824085932-c61f1f1f1c930e13
- Add a simple UIFactory 

  The idea of this is to let a client of bzrlib set some 
  policy about how output is displayed.

  In this revision all that's done is that progress bars
  are constructed by a policy established by the application
  rather than being randomly constructed in the library 
  or passed down the calls.  This avoids progress bars
  popping up while running the test suite and cleans up
  some code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/mdiff.py
 
1
# (C) 2005 Matt Mackall
 
2
# (C) 2005 Canonical Ltd
 
3
 
 
4
# based on code by Matt Mackall, hacked by Martin Pool
 
5
 
 
6
# mm's code works line-by-line; this just works on byte strings.
 
7
# Possibly slower; possibly gives better results for code not
 
8
# regularly separated by newlines and anyhow a bit simpler.
 
9
 
 
10
 
 
11
# This program is free software; you can redistribute it and/or modify
 
12
# it under the terms of the GNU General Public License as published by
 
13
# the Free Software Foundation; either version 2 of the License, or
 
14
# (at your option) any later version.
 
15
 
 
16
# This program is distributed in the hope that it will be useful,
 
17
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
18
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
19
# GNU General Public License for more details.
 
20
 
 
21
# You should have received a copy of the GNU General Public License
 
22
# along with this program; if not, write to the Free Software
 
23
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
24
 
 
25
 
 
26
# TODO: maybe work on files not strings?
 
27
 
 
28
# FIXME: doesn't work properly on files without trailing newlines
 
29
 
 
30
import unittest
 
31
import difflib, sys, struct
 
32
from cStringIO import StringIO
 
33
 
 
34
def linesplit(a):
 
35
    """Split into two lists: content and line positions.
 
36
 
 
37
    This returns (al, ap).
 
38
 
 
39
    al[i] is the string content of line i of the file, including its
 
40
    newline (if any).
 
41
 
 
42
    ap[i] is the byte position in the file where that line starts.
 
43
 
 
44
    ap[-1] is the byte position of the end of the file (i.e. the
 
45
    length of the file.)
 
46
 
 
47
    This transformation allows us to do a line-based diff and then map
 
48
    back to byte positions.
 
49
    """
 
50
 
 
51
    al, ap = [], []
 
52
    last = 0
 
53
 
 
54
    n = a.find("\n") + 1
 
55
    while n > 0:
 
56
        ap.append(last)
 
57
        al.append(a[last:n])
 
58
        last = n
 
59
        n = a.find("\n", n) + 1
 
60
 
 
61
    if last < len(a):
 
62
        al.append(a[last:])
 
63
        ap.append(last)
 
64
 
 
65
    # position at the end
 
66
    ap.append(len(a))
 
67
 
 
68
    return (al, ap)
 
69
 
 
70
 
 
71
def diff(a, b):
 
72
    # TODO: Use different splits, perhaps rsync-like, for binary files?
 
73
    
 
74
    (al, ap) = linesplit(a)
 
75
    (bl, bp) = linesplit(b)
 
76
 
 
77
    d = difflib.SequenceMatcher(None, al, bl)
 
78
    
 
79
    ## sys.stderr.write('  ~ real_quick_ratio: %.4f\n' % d.real_quick_ratio())
 
80
    
 
81
    for o, m, n, s, t in d.get_opcodes():
 
82
        if o == 'equal': continue
 
83
        # a[m:n] should be replaced by b[s:t]
 
84
        if s == t:
 
85
            yield ap[m], ap[n], ''
 
86
        else:
 
87
            yield ap[m], ap[n], ''.join(bl[s:t])
 
88
 
 
89
 
 
90
def tobinary(ops):
 
91
    b = StringIO()
 
92
    for f in ops:
 
93
        b.write(struct.pack(">III", f[0], f[1], len(f[2])))
 
94
        b.write(f[2])
 
95
    return b.getvalue()
 
96
 
 
97
 
 
98
def bdiff(a, b):
 
99
    return tobinary(diff(a, b))
 
100
 
 
101
 
 
102
def patch(t, ops):
 
103
    last = 0
 
104
    b = StringIO()
 
105
 
 
106
    for m, n, r in ops:
 
107
        b.write(t[last:m])
 
108
        if r:
 
109
            b.write(r)
 
110
        last = n
 
111
        
 
112
    b.write(t[last:])
 
113
    return b.getvalue()
 
114
 
 
115
 
 
116
def frombinary(b):
 
117
    bin = StringIO(b)
 
118
    while True:
 
119
        p = bin.read(12)
 
120
        if not p:
 
121
            break
 
122
 
 
123
        m, n, l = struct.unpack(">III", p)
 
124
        
 
125
        if l == 0:
 
126
            r = ''
 
127
        else:
 
128
            r = bin.read(l)
 
129
            if len(r) != l:
 
130
                raise Exception("truncated patch data")
 
131
            
 
132
        yield m, n, r
 
133
 
 
134
 
 
135
def bpatch(t, b):
 
136
    return patch(t, frombinary(b))
 
137
 
 
138
 
 
139
 
 
140
 
 
141
class TestDiffPatch(unittest.TestCase):
 
142
    def doDiffPatch(self, old, new):
 
143
        diff = bdiff(old, new)
 
144
        result = bpatch(old, diff)
 
145
        self.assertEquals(new, result)
 
146
 
 
147
 
 
148
    def testSimpleDiff(self):
 
149
        """Simply add a line at the end"""
 
150
        self.doDiffPatch('a\nb\n', 'a\nb\nc\n')
 
151
        
 
152
 
 
153
        
 
154
    def testTrailingLine(self):
 
155
        """Test diff that adds an unterminated line.
 
156
 
 
157
        (Old versions didn't do this properly.)"""
 
158
        self.doDiffPatch('a\nb\nc\n',
 
159
                         'a\nb\nc\nd')
 
160
 
 
161
 
 
162
if __name__ == '__main__':
 
163
    unittest.main()