~bzr-pqm/bzr/bzr.dev

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
# Copyright (C) 2009 Canonical Ltd
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA


#python2.4 support
cdef extern from "python-compat.h":
    pass

cdef extern from *:
    ctypedef unsigned int size_t
    int memcmp(void *, void*, size_t)
    void memcpy(void *, void*, size_t)
    void *memchr(void *s, int c, size_t len)
    long strtol(char *, char **, int)
    void sprintf(char *, char *, ...)

cdef extern from "Python.h":
    ctypedef int Py_ssize_t # Required for older pyrex versions
    ctypedef struct PyObject:
        pass
    int PyTuple_CheckExact(object p)
    Py_ssize_t PyTuple_GET_SIZE(object t)
    int PyString_CheckExact(object)
    char *PyString_AS_STRING(object s)
    Py_ssize_t PyString_GET_SIZE(object)

    int PyDict_SetItem(object d, object k, object v) except -1

    object PyTuple_New(Py_ssize_t count)
    void PyTuple_SET_ITEM(object t, Py_ssize_t offset, object)

    void Py_INCREF(object)

    PyObject * PyTuple_GET_ITEM_ptr "PyTuple_GET_ITEM" (object t,
                                                        Py_ssize_t offset)
    int PyString_CheckExact_ptr "PyString_CheckExact" (PyObject *p)
    Py_ssize_t PyString_GET_SIZE_ptr "PyString_GET_SIZE" (PyObject *s)
    char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
    object PyString_FromStringAndSize(char*, Py_ssize_t)

# cimport all of the definitions we will need to access
from _static_tuple_c cimport StaticTuple,\
    import_static_tuple_c, StaticTuple_New, \
    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact

cdef extern from "_static_tuple_c.h":
    # Defined explicitly rather than cimport-ing. Trying to use cimport, the
    # type for PyObject is a different class that happens to have the same
    # name...
    PyObject * StaticTuple_GET_ITEM_ptr "StaticTuple_GET_ITEM" (StaticTuple,
                                                                Py_ssize_t)

cdef extern from "zlib.h":
    ctypedef unsigned long uLong
    ctypedef unsigned int uInt
    ctypedef unsigned char Bytef

    uLong crc32(uLong crc, Bytef *buf, uInt len)


# Set up the StaticTuple C_API functionality
import_static_tuple_c()

cdef object _LeafNode
_LeafNode = None
cdef object _InternalNode
_InternalNode = None
cdef object _unknown
_unknown = None

# We shouldn't just copy this from _dirstate_helpers_pyx
cdef void* _my_memrchr(void *s, int c, size_t n): # cannot_raise
    # memrchr seems to be a GNU extension, so we have to implement it ourselves
    cdef char *pos
    cdef char *start

    start = <char*>s
    pos = start + n - 1
    while pos >= start:
        if pos[0] == c:
            return <void*>pos
        pos = pos - 1
    return NULL


def _search_key_16(key):
    """See chk_map._search_key_16."""
    cdef Py_ssize_t num_bits
    cdef Py_ssize_t i, j
    cdef Py_ssize_t num_out_bytes
    cdef Bytef *c_bit
    cdef uLong c_len
    cdef uInt crc_val
    cdef Py_ssize_t out_off
    cdef char *c_out
    cdef PyObject *bit

    if not StaticTuple_CheckExact(key):
        raise TypeError('key %r is not a StaticTuple' % (key,))
    num_bits = len(key)
    # 4 bytes per crc32, and another 1 byte between bits
    num_out_bytes = (9 * num_bits) - 1
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
    c_out = PyString_AS_STRING(out)
    for i from 0 <= i < num_bits:
        if i > 0:
            c_out[0] = c'\x00'
            c_out = c_out + 1
        # We use the _ptr variant, because GET_ITEM returns a borrowed
        # reference, and Pyrex assumes that returned 'object' are a new
        # reference
        bit = StaticTuple_GET_ITEM_ptr(key, i)
        if not PyString_CheckExact_ptr(bit):
            raise TypeError('Bit %d of %r is not a string' % (i, key))
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
        c_len = PyString_GET_SIZE_ptr(bit)
        crc_val = crc32(0, c_bit, c_len)
        # Hex(val) order
        sprintf(c_out, '%08X', crc_val)
        c_out = c_out + 8
    return out


def _search_key_255(key):
    """See chk_map._search_key_255."""
    cdef Py_ssize_t num_bits
    cdef Py_ssize_t i, j
    cdef Py_ssize_t num_out_bytes
    cdef Bytef *c_bit
    cdef uLong c_len
    cdef uInt crc_val
    cdef Py_ssize_t out_off
    cdef char *c_out
    cdef PyObject *bit

    if not StaticTuple_CheckExact(key):
        raise TypeError('key %r is not a StaticTuple' % (key,))
    num_bits = len(key)
    # 4 bytes per crc32, and another 1 byte between bits
    num_out_bytes = (5 * num_bits) - 1
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
    c_out = PyString_AS_STRING(out)
    for i from 0 <= i < num_bits:
        if i > 0:
            c_out[0] = c'\x00'
            c_out = c_out + 1
        bit = StaticTuple_GET_ITEM_ptr(key, i)
        if not PyString_CheckExact_ptr(bit):
            raise TypeError('Bit %d of %r is not a string: %r'
                            % (i, key, <object>bit))
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
        c_len = PyString_GET_SIZE_ptr(bit)
        crc_val = crc32(0, c_bit, c_len)
        # MSB order
        c_out[0] = (crc_val >> 24) & 0xFF
        c_out[1] = (crc_val >> 16) & 0xFF
        c_out[2] = (crc_val >> 8) & 0xFF
        c_out[3] = (crc_val >> 0) & 0xFF
        for j from 0 <= j < 4:
            if c_out[j] == c'\n':
                c_out[j] = c'_'
        c_out = c_out + 4
    return out


cdef int _get_int_from_line(char **cur, char *end, char *message) except -1:
    """Read a positive integer from the data stream.

    :param cur: The start of the data, this will be moved to after the
        trailing newline when done.
    :param end: Do not parse any data past this byte.
    :return: The integer stored in those bytes
    """
    cdef int value
    cdef char *next_line, *next

    next_line = <char *>memchr(cur[0], c'\n', end - cur[0])
    if next_line == NULL:
        raise ValueError("Missing %s line\n" % message)

    value = strtol(cur[0], &next, 10)
    if next != next_line:
        raise ValueError("%s line not a proper int\n" % message)
    cur[0] = next_line + 1
    return value


def _deserialise_leaf_node(bytes, key, search_key_func=None):
    """Deserialise bytes, with key key, into a LeafNode.

    :param bytes: The bytes of the node.
    :param key: The key that the serialised node has.
    """
    cdef char *c_bytes, *cur, *next, *end
    cdef char *next_line
    cdef Py_ssize_t c_bytes_len, prefix_length, items_length
    cdef int maximum_size, width, length, i, prefix_tail_len
    cdef int num_value_lines, num_prefix_bits
    cdef char *prefix, *value_start, *prefix_tail
    cdef char *next_null, *last_null, *line_start
    cdef char *c_entry, *entry_start
    cdef StaticTuple entry_bits

    if _LeafNode is None:
        from bzrlib import chk_map
        _LeafNode = chk_map.LeafNode
        _InternalNode = chk_map.InternalNode
        _unknown = chk_map._unknown

    result = _LeafNode(search_key_func=search_key_func)
    # Splitlines can split on '\r' so don't use it, split('\n') adds an
    # extra '' if the bytes ends in a final newline.
    if not PyString_CheckExact(bytes):
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))

    c_bytes = PyString_AS_STRING(bytes)
    c_bytes_len = PyString_GET_SIZE(bytes)

    if c_bytes_len < 9 or memcmp(c_bytes, "chkleaf:\n", 9) != 0:
        raise ValueError("not a serialised leaf node: %r" % bytes)
    if c_bytes[c_bytes_len - 1] != c'\n':
        raise ValueError("bytes does not end in a newline")

    end = c_bytes + c_bytes_len
    cur = c_bytes + 9
    maximum_size = _get_int_from_line(&cur, end, "maximum_size")
    width = _get_int_from_line(&cur, end, "width")
    length = _get_int_from_line(&cur, end, "length")

    next_line = <char *>memchr(cur, c'\n', end - cur)
    if next_line == NULL:
        raise ValueError('Missing the prefix line\n')
    prefix = cur
    prefix_length = next_line - cur
    cur = next_line + 1

    prefix_bits = []
    prefix_tail = prefix
    num_prefix_bits = 0
    next_null = <char *>memchr(prefix, c'\0', prefix_length)
    while next_null != NULL:
        num_prefix_bits = num_prefix_bits + 1
        prefix_bits.append(
            PyString_FromStringAndSize(prefix_tail, next_null - prefix_tail))
        prefix_tail = next_null + 1
        next_null = <char *>memchr(prefix_tail, c'\0', next_line - prefix_tail)
    prefix_tail_len = next_line - prefix_tail

    if num_prefix_bits >= width:
        raise ValueError('Prefix has too many nulls versus width')

    items_length = end - cur
    items = {}
    while cur < end:
        line_start = cur
        next_line = <char *>memchr(cur, c'\n', end - cur)
        if next_line == NULL:
            raise ValueError('null line\n')
        last_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
        if last_null == NULL:
            raise ValueError('fail to find the num value lines null')
        next_null = last_null + 1 # move past NULL
        num_value_lines = _get_int_from_line(&next_null, next_line + 1,
                                             "num value lines")
        cur = next_line + 1
        value_start = cur
        # Walk num_value_lines forward
        for i from 0 <= i < num_value_lines:
            next_line = <char *>memchr(cur, c'\n', end - cur)
            if next_line == NULL:
                raise ValueError('missing trailing newline')
            cur = next_line + 1
        entry_bits = StaticTuple_New(width)
        for i from 0 <= i < num_prefix_bits:
            # TODO: Use PyList_GetItem, or turn prefix_bits into a
            #       tuple/StaticTuple
            entry = prefix_bits[i]
            # SET_ITEM 'steals' a reference
            Py_INCREF(entry)
            StaticTuple_SET_ITEM(entry_bits, i, entry)
        value = PyString_FromStringAndSize(value_start, next_line - value_start)
        # The next entry bit needs the 'tail' from the prefix, and first part
        # of the line
        entry_start = line_start
        next_null = <char *>memchr(entry_start, c'\0',
                                   last_null - entry_start + 1)
        if next_null == NULL:
            raise ValueError('bad no null, bad')
        entry = PyString_FromStringAndSize(NULL,
                    prefix_tail_len + next_null - line_start)
        c_entry = PyString_AS_STRING(entry)
        if prefix_tail_len > 0:
            memcpy(c_entry, prefix_tail, prefix_tail_len)
        if next_null - line_start > 0:
            memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
        Py_INCREF(entry)
        i = num_prefix_bits
        StaticTuple_SET_ITEM(entry_bits, i, entry)
        while next_null != last_null: # We have remaining bits
            i = i + 1
            if i > width:
                raise ValueError("Too many bits for entry")
            entry_start = next_null + 1
            next_null = <char *>memchr(entry_start, c'\0',
                                       last_null - entry_start + 1)
            if next_null == NULL:
                raise ValueError('bad no null')
            entry = PyString_FromStringAndSize(entry_start,
                                               next_null - entry_start)
            Py_INCREF(entry)
            StaticTuple_SET_ITEM(entry_bits, i, entry)
        if len(entry_bits) != width:
            raise AssertionError(
                'Incorrect number of elements (%d vs %d)'
                % (len(entry_bits)+1, width + 1))
        entry_bits = StaticTuple_Intern(entry_bits)
        PyDict_SetItem(items, entry_bits, value)
    if len(items) != length:
        raise ValueError("item count (%d) mismatch for key %s,"
                         " bytes %r" % (length, entry_bits, bytes))
    result._items = items
    result._len = length
    result._maximum_size = maximum_size
    result._key = key
    result._key_width = width
    result._raw_size = items_length + length * prefix_length
    if length == 0:
        result._search_prefix = None
        result._common_serialised_prefix = None
    else:
        result._search_prefix = _unknown
        result._common_serialised_prefix = PyString_FromStringAndSize(prefix,
                                                prefix_length)
    if c_bytes_len != result._current_size():
        raise AssertionError('_current_size computed incorrectly %d != %d',
            c_bytes_len, result._current_size())
    return result


def _deserialise_internal_node(bytes, key, search_key_func=None):
    cdef char *c_bytes, *cur, *next, *end
    cdef char *next_line
    cdef Py_ssize_t c_bytes_len, prefix_length
    cdef int maximum_size, width, length, i, prefix_tail_len
    cdef char *prefix, *line_prefix, *next_null, *c_item_prefix

    if _InternalNode is None:
        from bzrlib import chk_map
        _LeafNode = chk_map.LeafNode
        _InternalNode = chk_map.InternalNode
        _unknown = chk_map._unknown
    result = _InternalNode(search_key_func=search_key_func)

    if not StaticTuple_CheckExact(key):
        raise TypeError('key %r is not a StaticTuple' % (key,))
    if not PyString_CheckExact(bytes):
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))

    c_bytes = PyString_AS_STRING(bytes)
    c_bytes_len = PyString_GET_SIZE(bytes)

    if c_bytes_len < 9 or memcmp(c_bytes, "chknode:\n", 9) != 0:
        raise ValueError("not a serialised internal node: %r" % bytes)
    if c_bytes[c_bytes_len - 1] != c'\n':
        raise ValueError("bytes does not end in a newline")

    items = {}
    cur = c_bytes + 9
    end = c_bytes + c_bytes_len
    maximum_size = _get_int_from_line(&cur, end, "maximum_size")
    width = _get_int_from_line(&cur, end, "width")
    length = _get_int_from_line(&cur, end, "length")

    next_line = <char *>memchr(cur, c'\n', end - cur)
    if next_line == NULL:
        raise ValueError('Missing the prefix line\n')
    prefix = cur
    prefix_length = next_line - cur
    cur = next_line + 1

    while cur < end:
        # Find the null separator
        next_line = <char *>memchr(cur, c'\n', end - cur)
        if next_line == NULL:
            raise ValueError('missing trailing newline')
        next_null = <char *>_my_memrchr(cur, c'\0', next_line - cur)
        if next_null == NULL:
            raise ValueError('bad no null')
        item_prefix = PyString_FromStringAndSize(NULL,
            prefix_length + next_null - cur)
        c_item_prefix = PyString_AS_STRING(item_prefix)
        if prefix_length:
            memcpy(c_item_prefix, prefix, prefix_length)
        memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
        flat_key = PyString_FromStringAndSize(next_null + 1,
                                              next_line - next_null - 1)
        flat_key = StaticTuple(flat_key).intern()
        PyDict_SetItem(items, item_prefix, flat_key)
        cur = next_line + 1
    assert len(items) > 0
    result._items = items
    result._len = length
    result._maximum_size = maximum_size
    result._key = key
    result._key_width = width
    # XXX: InternalNodes don't really care about their size, and this will
    #      change if we add prefix compression
    result._raw_size = None # len(bytes)
    result._node_width = len(item_prefix)
    result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
    return result