← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_bencode_pyx.pyx

  • Committer: Martin Pool
  • Date: 2011-07-04 21:15:24 UTC
  • mto: (6034.1.1 filter-tree)
  • mto: This revision was merged to the branch mainline in revision 6035.
  • Revision ID: mbp@canonical.com-20110704211524-ilb7l6g4i3iizke7
Test exporting filtered tree to a zip (already works)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_bencode_pyx.pyx
 
1
# Copyright (C) 2007, 2009, 2010 Canonical 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Pyrex implementation for bencode coder/decoder"""
 
18
 
 
19
 
 
20
cdef extern from "stddef.h":
 
21
    ctypedef unsigned int size_t
 
22
 
 
23
cdef extern from "Python.h":
 
24
    ctypedef int  Py_ssize_t
 
25
    int PyInt_CheckExact(object o)
 
26
    int PyLong_CheckExact(object o)
 
27
    int PyString_CheckExact(object o)
 
28
    int PyTuple_CheckExact(object o)
 
29
    int PyList_CheckExact(object o)
 
30
    int PyDict_CheckExact(object o)
 
31
    int PyBool_Check(object o)
 
32
    object PyString_FromStringAndSize(char *v, Py_ssize_t len)
 
33
    char *PyString_AS_STRING(object o) except NULL
 
34
    Py_ssize_t PyString_GET_SIZE(object o) except -1
 
35
    object PyInt_FromString(char *str, char **pend, int base)
 
36
    int Py_GetRecursionLimit()
 
37
    int Py_EnterRecursiveCall(char *)
 
38
    void Py_LeaveRecursiveCall()
 
39
 
 
40
    int PyList_Append(object, object) except -1
 
41
 
 
42
cdef extern from "stdlib.h":
 
43
    void free(void *memblock)
 
44
    void *malloc(size_t size)
 
45
    void *realloc(void *memblock, size_t size)
 
46
    long strtol(char *, char **, int)
 
47
 
 
48
cdef extern from "string.h":
 
49
    void *memcpy(void *dest, void *src, size_t count)
 
50
 
 
51
cdef extern from "python-compat.h":
 
52
    int snprintf(char* buffer, size_t nsize, char* fmt, ...)
 
53
 
 
54
cdef class Decoder
 
55
cdef class Encoder
 
56
 
 
57
cdef extern from "_bencode_pyx.h":
 
58
    void D_UPDATE_TAIL(Decoder, int n)
 
59
    void E_UPDATE_TAIL(Encoder, int n)
 
60
 
 
61
# To maintain compatibility with older versions of pyrex, we have to use the
 
62
# relative import here, rather than 'bzrlib._static_tuple_c'
 
63
from _static_tuple_c cimport StaticTuple, StaticTuple_CheckExact, \
 
64
    import_static_tuple_c
 
65
 
 
66
import_static_tuple_c()
 
67
 
 
68
 
 
69
cdef class Decoder:
 
70
    """Bencode decoder"""
 
71
 
 
72
    cdef readonly char *tail
 
73
    cdef readonly int size
 
74
    cdef readonly int _yield_tuples
 
75
    cdef object text
 
76
 
 
77
    def __init__(self, s, yield_tuples=0):
 
78
        """Initialize decoder engine.
 
79
        @param  s:  Python string.
 
80
        """
 
81
        if not PyString_CheckExact(s):
 
82
            raise TypeError("String required")
 
83
 
 
84
        self.text = s
 
85
        self.tail = PyString_AS_STRING(s)
 
86
        self.size = PyString_GET_SIZE(s)
 
87
        self._yield_tuples = int(yield_tuples)
 
88
 
 
89
    def decode(self):
 
90
        result = self._decode_object()
 
91
        if self.size != 0:
 
92
            raise ValueError('junk in stream')
 
93
        return result
 
94
 
 
95
    def decode_object(self):
 
96
        return self._decode_object()
 
97
 
 
98
    cdef object _decode_object(self):
 
99
        cdef char ch
 
100
 
 
101
        if 0 == self.size:
 
102
            raise ValueError('stream underflow')
 
103
 
 
104
        if Py_EnterRecursiveCall("_decode_object"):
 
105
            raise RuntimeError("too deeply nested")
 
106
        try:
 
107
            ch = self.tail[0]
 
108
            if c'0' <= ch <= c'9':
 
109
                return self._decode_string()
 
110
            elif ch == c'l':
 
111
                D_UPDATE_TAIL(self, 1)
 
112
                return self._decode_list()
 
113
            elif ch == c'i':
 
114
                D_UPDATE_TAIL(self, 1)
 
115
                return self._decode_int()
 
116
            elif ch == c'd':
 
117
                D_UPDATE_TAIL(self, 1)
 
118
                return self._decode_dict()
 
119
            else:
 
120
                raise ValueError('unknown object type identifier %r' % ch)
 
121
        finally:
 
122
            Py_LeaveRecursiveCall()
 
123
 
 
124
    cdef int _read_digits(self, char stop_char) except -1:
 
125
        cdef int i
 
126
        i = 0
 
127
        while ((self.tail[i] >= c'0' and self.tail[i] <= c'9') or
 
128
               self.tail[i] == c'-') and i < self.size:
 
129
            i = i + 1
 
130
 
 
131
        if self.tail[i] != stop_char:
 
132
            raise ValueError("Stop character %c not found: %c" % 
 
133
                (stop_char, self.tail[i]))
 
134
        if (self.tail[0] == c'0' or 
 
135
                (self.tail[0] == c'-' and self.tail[1] == c'0')):
 
136
            if i == 1:
 
137
                return i
 
138
            else:
 
139
                raise ValueError # leading zeroes are not allowed
 
140
        return i
 
141
 
 
142
    cdef object _decode_int(self):
 
143
        cdef int i
 
144
        i = self._read_digits(c'e')
 
145
        self.tail[i] = 0
 
146
        try:
 
147
            ret = PyInt_FromString(self.tail, NULL, 10)
 
148
        finally:
 
149
            self.tail[i] = c'e'
 
150
        D_UPDATE_TAIL(self, i+1)
 
151
        return ret
 
152
 
 
153
    cdef object _decode_string(self):
 
154
        cdef int n
 
155
        cdef char *next_tail
 
156
        # strtol allows leading whitespace, negatives, and leading zeros
 
157
        # however, all callers have already checked that '0' <= tail[0] <= '9'
 
158
        # or they wouldn't have called _decode_string
 
159
        # strtol will stop at trailing whitespace, etc
 
160
        n = strtol(self.tail, &next_tail, 10)
 
161
        if next_tail == NULL or next_tail[0] != c':':
 
162
            raise ValueError('string len not terminated by ":"')
 
163
        # strtol allows leading zeros, so validate that we don't have that
 
164
        if (self.tail[0] == c'0'
 
165
            and (n != 0 or (next_tail - self.tail != 1))):
 
166
            raise ValueError('leading zeros are not allowed')
 
167
        D_UPDATE_TAIL(self, next_tail - self.tail + 1)
 
168
        if n == 0:
 
169
            return ''
 
170
        if n > self.size:
 
171
            raise ValueError('stream underflow')
 
172
        if n < 0:
 
173
            raise ValueError('string size below zero: %d' % n)
 
174
 
 
175
        result = PyString_FromStringAndSize(self.tail, n)
 
176
        D_UPDATE_TAIL(self, n)
 
177
        return result
 
178
 
 
179
    cdef object _decode_list(self):
 
180
        result = []
 
181
 
 
182
        while self.size > 0:
 
183
            if self.tail[0] == c'e':
 
184
                D_UPDATE_TAIL(self, 1)
 
185
                if self._yield_tuples:
 
186
                    return tuple(result)
 
187
                else:
 
188
                    return result
 
189
            else:
 
190
                # As a quick shortcut, check to see if the next object is a
 
191
                # string, since we know that won't be creating recursion
 
192
                # if self.tail[0] >= c'0' and self.tail[0] <= c'9':
 
193
                PyList_Append(result, self._decode_object())
 
194
 
 
195
        raise ValueError('malformed list')
 
196
 
 
197
    cdef object _decode_dict(self):
 
198
        cdef char ch
 
199
 
 
200
        result = {}
 
201
        lastkey = None
 
202
 
 
203
        while self.size > 0:
 
204
            ch = self.tail[0]
 
205
            if ch == c'e':
 
206
                D_UPDATE_TAIL(self, 1)
 
207
                return result
 
208
            else:
 
209
                # keys should be strings only
 
210
                if self.tail[0] < c'0' or self.tail[0] > c'9':
 
211
                    raise ValueError('key was not a simple string.')
 
212
                key = self._decode_string()
 
213
                if lastkey >= key:
 
214
                    raise ValueError('dict keys disordered')
 
215
                else:
 
216
                    lastkey = key
 
217
                value = self._decode_object()
 
218
                result[key] = value
 
219
 
 
220
        raise ValueError('malformed dict')
 
221
 
 
222
 
 
223
def bdecode(object s):
 
224
    """Decode string x to Python object"""
 
225
    return Decoder(s).decode()
 
226
 
 
227
 
 
228
def bdecode_as_tuple(object s):
 
229
    """Decode string x to Python object, using tuples rather than lists."""
 
230
    return Decoder(s, True).decode()
 
231
 
 
232
 
 
233
class Bencached(object):
 
234
    __slots__ = ['bencoded']
 
235
 
 
236
    def __init__(self, s):
 
237
        self.bencoded = s
 
238
 
 
239
 
 
240
cdef enum:
 
241
    INITSIZE = 1024     # initial size for encoder buffer
 
242
    INT_BUF_SIZE = 32
 
243
 
 
244
 
 
245
cdef class Encoder:
 
246
    """Bencode encoder"""
 
247
 
 
248
    cdef readonly char *tail
 
249
    cdef readonly int size
 
250
    cdef readonly char *buffer
 
251
    cdef readonly int maxsize
 
252
 
 
253
    def __init__(self, int maxsize=INITSIZE):
 
254
        """Initialize encoder engine
 
255
        @param  maxsize:    initial size of internal char buffer
 
256
        """
 
257
        cdef char *p
 
258
 
 
259
        self.maxsize = 0
 
260
        self.size = 0
 
261
        self.tail = NULL
 
262
 
 
263
        p = <char*>malloc(maxsize)
 
264
        if p == NULL:
 
265
            raise MemoryError('Not enough memory to allocate buffer '
 
266
                              'for encoder')
 
267
        self.buffer = p
 
268
        self.maxsize = maxsize
 
269
        self.tail = p
 
270
 
 
271
    def __dealloc__(self):
 
272
        free(self.buffer)
 
273
        self.buffer = NULL
 
274
        self.maxsize = 0
 
275
 
 
276
    def __str__(self):
 
277
        if self.buffer != NULL and self.size != 0:
 
278
            return PyString_FromStringAndSize(self.buffer, self.size)
 
279
        else:
 
280
            return ''
 
281
 
 
282
    cdef int _ensure_buffer(self, int required) except 0:
 
283
        """Ensure that tail of CharTail buffer has enough size.
 
284
        If buffer is not big enough then function try to
 
285
        realloc buffer.
 
286
        """
 
287
        cdef char *new_buffer
 
288
        cdef int   new_size
 
289
 
 
290
        if self.size + required < self.maxsize:
 
291
            return 1
 
292
 
 
293
        new_size = self.maxsize
 
294
        while new_size < self.size + required:
 
295
            new_size = new_size * 2
 
296
        new_buffer = <char*>realloc(self.buffer, <size_t>new_size)
 
297
        if new_buffer == NULL:
 
298
            raise MemoryError('Cannot realloc buffer for encoder')
 
299
 
 
300
        self.buffer = new_buffer
 
301
        self.maxsize = new_size
 
302
        self.tail = &new_buffer[self.size]
 
303
        return 1
 
304
 
 
305
    cdef int _encode_int(self, int x) except 0:
 
306
        """Encode int to bencode string iNNNe
 
307
        @param  x:  value to encode
 
308
        """
 
309
        cdef int n
 
310
        self._ensure_buffer(INT_BUF_SIZE)
 
311
        n = snprintf(self.tail, INT_BUF_SIZE, "i%de", x)
 
312
        if n < 0:
 
313
            raise MemoryError('int %d too big to encode' % x)
 
314
        E_UPDATE_TAIL(self, n)
 
315
        return 1
 
316
 
 
317
    cdef int _encode_long(self, x) except 0:
 
318
        return self._append_string(''.join(('i', str(x), 'e')))
 
319
 
 
320
    cdef int _append_string(self, s) except 0:
 
321
        cdef Py_ssize_t n
 
322
        n = PyString_GET_SIZE(s)
 
323
        self._ensure_buffer(n)
 
324
        memcpy(self.tail, PyString_AS_STRING(s), n)
 
325
        E_UPDATE_TAIL(self, n)
 
326
        return 1
 
327
 
 
328
    cdef int _encode_string(self, x) except 0:
 
329
        cdef int n
 
330
        cdef Py_ssize_t x_len
 
331
        x_len = PyString_GET_SIZE(x)
 
332
        self._ensure_buffer(x_len + INT_BUF_SIZE)
 
333
        n = snprintf(self.tail, INT_BUF_SIZE, '%d:', x_len)
 
334
        if n < 0:
 
335
            raise MemoryError('string %s too big to encode' % x)
 
336
        memcpy(<void *>(self.tail+n), PyString_AS_STRING(x), x_len)
 
337
        E_UPDATE_TAIL(self, n + x_len)
 
338
        return 1
 
339
 
 
340
    cdef int _encode_list(self, x) except 0:
 
341
        self._ensure_buffer(1)
 
342
        self.tail[0] = c'l'
 
343
        E_UPDATE_TAIL(self, 1)
 
344
 
 
345
        for i in x:
 
346
            self.process(i)
 
347
 
 
348
        self._ensure_buffer(1)
 
349
        self.tail[0] = c'e'
 
350
        E_UPDATE_TAIL(self, 1)
 
351
        return 1
 
352
 
 
353
    cdef int _encode_dict(self, x) except 0:
 
354
        self._ensure_buffer(1)
 
355
        self.tail[0] = c'd'
 
356
        E_UPDATE_TAIL(self, 1)
 
357
 
 
358
        keys = x.keys()
 
359
        keys.sort()
 
360
        for k in keys:
 
361
            if not PyString_CheckExact(k):
 
362
                raise TypeError('key in dict should be string')
 
363
            self._encode_string(k)
 
364
            self.process(x[k])
 
365
 
 
366
        self._ensure_buffer(1)
 
367
        self.tail[0] = c'e'
 
368
        E_UPDATE_TAIL(self, 1)
 
369
        return 1
 
370
 
 
371
    def process(self, object x):
 
372
        if Py_EnterRecursiveCall("encode"):
 
373
            raise RuntimeError("too deeply nested")
 
374
        try:
 
375
            if PyString_CheckExact(x):
 
376
                self._encode_string(x)
 
377
            elif PyInt_CheckExact(x):
 
378
                self._encode_int(x)
 
379
            elif PyLong_CheckExact(x):
 
380
                self._encode_long(x)
 
381
            elif (PyList_CheckExact(x) or PyTuple_CheckExact(x)
 
382
                  or StaticTuple_CheckExact(x)):
 
383
                self._encode_list(x)
 
384
            elif PyDict_CheckExact(x):
 
385
                self._encode_dict(x)
 
386
            elif PyBool_Check(x):
 
387
                self._encode_int(int(x))
 
388
            elif isinstance(x, Bencached):
 
389
                self._append_string(x.bencoded)
 
390
            else:
 
391
                raise TypeError('unsupported type %r' % x)
 
392
        finally:
 
393
            Py_LeaveRecursiveCall()
 
394
 
 
395
 
 
396
def bencode(x):
 
397
    """Encode Python object x to string"""
 
398
    encoder = Encoder()
 
399
    encoder.process(x)
 
400
    return str(encoder)