← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_bencode_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2008-08-28 20:13:31 UTC
  • mfrom: (3658 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3688.
  • Revision ID: john@arbash-meinel.com-20080828201331-dqffxf54l2heokll
Merge bzr.dev 3658

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)