1
=== modified file 'NEWS'
2
--- NEWS	2009-10-26 06:44:40 +0000
3
+++ NEWS	2009-10-26 14:59:15 +0000
4
@@ -46,6 +46,7 @@
5
46
  (John Arbash Meinel)
46
  (John Arbash Meinel)
6
47
47
7
48
* Peak memory under certain operations has been reduced significantly.
48
* Peak memory under certain operations has been reduced significantly.
8
49
  (eg, 'bzr branch launchpad standalone' is cut in half)
9
49
  (John Arbash Meinel)
50
  (John Arbash Meinel)
10
50
51
11
51
Documentation
52
Documentation
12
@@ -74,14 +75,14 @@
13
74
  (John Arbash Meinel)
75
  (John Arbash Meinel)
14
75
76
15
76
* ``bzrlib._static_tuple_c.StaticTuple`` is now available and used by
77
* ``bzrlib._static_tuple_c.StaticTuple`` is now available and used by
24
77
  the btree index parser. This class functions similarly to ``tuple``
78
  the btree index parser and the chk map parser. This class functions
25
78
  objects. However, it can only point to a limited collection of types.
79
  similarly to ``tuple`` objects. However, it can only point to a limited
26
79
  (Currently StaticTuple, str, unicode, None, bool, int, long, float, and
80
  collection of types.  (Currently StaticTuple, str, unicode, None, bool,
27
80
  not subclasses).  This allows us to remove it from the garbage collector
81
  int, long, float, but not subclasses).  This allows us to remove it from
28
81
  (it cannot be in a cycle), it also allows us to intern the objects. In
82
  the garbage collector (it cannot be in a cycle), it also allows us to
29
82
  testing, this can reduce peak memory by 20-40%, and significantly
83
  intern the objects. In testing, this can reduce peak memory by 20-40%,
30
83
  improve performance by removing objects from being inspected by the
84
  and significantly improve performance by removing objects from being
31
84
  garbage collector.  (John Arbash Meinel)
85
  inspected by the garbage collector.  (John Arbash Meinel)
32
85
86
33
86
* ``GroupCompressBlock._ensure_content()`` will now release the
87
* ``GroupCompressBlock._ensure_content()`` will now release the
34
87
  ``zlib.decompressobj()`` when the first request is for all of the
88
  ``zlib.decompressobj()`` when the first request is for all of the
35
88
89
36
=== modified file 'bzrlib/_chk_map_py.py'
37
--- bzrlib/_chk_map_py.py	2009-10-08 04:35:01 +0000
38
+++ bzrlib/_chk_map_py.py	2009-10-26 14:59:15 +0000
39
@@ -19,6 +19,8 @@
40
19
import zlib
19
import zlib
41
20
import struct
20
import struct
42
21
21
43
22
from bzrlib.static_tuple import StaticTuple
44
23
45
22
_LeafNode = None
24
_LeafNode = None
46
23
_InternalNode = None
25
_InternalNode = None
47
24
_unknown = None
26
_unknown = None
48
@@ -93,7 +95,7 @@
49
93
        value_lines = lines[pos:pos+num_value_lines]
95
        value_lines = lines[pos:pos+num_value_lines]
50
94
        pos += num_value_lines
96
        pos += num_value_lines
51
95
        value = '\n'.join(value_lines)
97
        value = '\n'.join(value_lines)
53
96
        items[tuple(elements[:-1])] = value
98
        items[StaticTuple.from_sequence(elements[:-1])] = value
54
97
    if len(items) != length:
99
    if len(items) != length:
55
98
        raise AssertionError("item count (%d) mismatch for key %s,"
100
        raise AssertionError("item count (%d) mismatch for key %s,"
56
99
            " bytes %r" % (length, key, bytes))
101
            " bytes %r" % (length, key, bytes))
57
@@ -141,7 +143,7 @@
58
141
    for line in lines[5:]:
143
    for line in lines[5:]:
59
142
        line = common_prefix + line
144
        line = common_prefix + line
60
143
        prefix, flat_key = line.rsplit('\x00', 1)
145
        prefix, flat_key = line.rsplit('\x00', 1)
62
144
        items[prefix] = (flat_key,)
146
        items[prefix] = StaticTuple(flat_key,)
63
145
    if len(items) == 0:
147
    if len(items) == 0:
64
146
        raise AssertionError("We didn't find any item for %s" % key)
148
        raise AssertionError("We didn't find any item for %s" % key)
65
147
    result._items = items
149
    result._items = items
66
@@ -155,4 +157,3 @@
67
155
    result._node_width = len(prefix)
157
    result._node_width = len(prefix)
68
156
    result._search_prefix = common_prefix
158
    result._search_prefix = common_prefix
69
157
    return result
159
    return result
70
158
71
159
160
72
=== modified file 'bzrlib/_chk_map_pyx.pyx'
73
--- bzrlib/_chk_map_pyx.pyx	2009-10-08 04:35:01 +0000
74
+++ bzrlib/_chk_map_pyx.pyx	2009-10-26 14:59:15 +0000
75
@@ -29,9 +29,8 @@
76
29
29
77
30
cdef extern from "Python.h":
30
cdef extern from "Python.h":
78
31
    ctypedef int Py_ssize_t # Required for older pyrex versions
31
    ctypedef int Py_ssize_t # Required for older pyrex versions
80
32
    struct _PyObject:
32
    ctypedef struct PyObject:
81
33
        pass
33
        pass
82
34
    ctypedef _PyObject PyObject
83
35
    int PyTuple_CheckExact(object p)
34
    int PyTuple_CheckExact(object p)
84
36
    Py_ssize_t PyTuple_GET_SIZE(object t)
35
    Py_ssize_t PyTuple_GET_SIZE(object t)
85
37
    int PyString_CheckExact(object)
36
    int PyString_CheckExact(object)
86
@@ -52,6 +51,18 @@
87
52
    char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
51
    char *PyString_AS_STRING_ptr "PyString_AS_STRING" (PyObject *s)
88
53
    object PyString_FromStringAndSize(char*, Py_ssize_t)
52
    object PyString_FromStringAndSize(char*, Py_ssize_t)
89
54
53
90
54
# cimport all of the definitions we will need to access
91
55
from _static_tuple_c cimport StaticTuple,\
92
56
    import_static_tuple_c, StaticTuple_New, \
93
57
    StaticTuple_Intern, StaticTuple_SET_ITEM, StaticTuple_CheckExact
94
58
95
59
cdef extern from "_static_tuple_c.h":
96
60
    # Defined explicitly rather than cimport-ing. Trying to use cimport, the
97
61
    # type for PyObject is a different class that happens to have the same
98
62
    # name...
99
63
    PyObject * StaticTuple_GET_ITEM_ptr "StaticTuple_GET_ITEM" (StaticTuple,
100
64
                                                                Py_ssize_t)
101
65
102
55
cdef extern from "zlib.h":
66
cdef extern from "zlib.h":
103
56
    ctypedef unsigned long uLong
67
    ctypedef unsigned long uLong
104
57
    ctypedef unsigned int uInt
68
    ctypedef unsigned int uInt
105
@@ -60,8 +71,14 @@
106
60
    uLong crc32(uLong crc, Bytef *buf, uInt len)
71
    uLong crc32(uLong crc, Bytef *buf, uInt len)
107
61
72
108
62
73
109
74
# Set up the StaticTuple C_API functionality
110
75
import_static_tuple_c()
111
76
112
77
cdef object _LeafNode
113
63
_LeafNode = None
78
_LeafNode = None
114
79
cdef object _InternalNode
115
64
_InternalNode = None
80
_InternalNode = None
116
81
cdef object _unknown
117
65
_unknown = None
82
_unknown = None
118
66
83
119
67
# We shouldn't just copy this from _dirstate_helpers_pyx
84
# We shouldn't just copy this from _dirstate_helpers_pyx
120
@@ -91,9 +108,9 @@
121
91
    cdef char *c_out
108
    cdef char *c_out
122
92
    cdef PyObject *bit
109
    cdef PyObject *bit
123
93
110
127
94
    if not PyTuple_CheckExact(key):
111
    if not StaticTuple_CheckExact(key):
128
95
        raise TypeError('key %r is not a tuple' % (key,))
112
        raise TypeError('key %r is not a StaticTuple' % (key,))
129
96
    num_bits = PyTuple_GET_SIZE(key)
113
    num_bits = len(key)
130
97
    # 4 bytes per crc32, and another 1 byte between bits
114
    # 4 bytes per crc32, and another 1 byte between bits
131
98
    num_out_bytes = (9 * num_bits) - 1
115
    num_out_bytes = (9 * num_bits) - 1
132
99
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
116
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
133
@@ -105,7 +122,7 @@
134
105
        # We use the _ptr variant, because GET_ITEM returns a borrowed
122
        # We use the _ptr variant, because GET_ITEM returns a borrowed
135
106
        # reference, and Pyrex assumes that returned 'object' are a new
123
        # reference, and Pyrex assumes that returned 'object' are a new
136
107
        # reference
124
        # reference
138
108
        bit = PyTuple_GET_ITEM_ptr(key, i)
125
        bit = StaticTuple_GET_ITEM_ptr(key, i)
139
109
        if not PyString_CheckExact_ptr(bit):
126
        if not PyString_CheckExact_ptr(bit):
140
110
            raise TypeError('Bit %d of %r is not a string' % (i, key))
127
            raise TypeError('Bit %d of %r is not a string' % (i, key))
141
111
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
128
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
142
@@ -129,9 +146,9 @@
143
129
    cdef char *c_out
146
    cdef char *c_out
144
130
    cdef PyObject *bit
147
    cdef PyObject *bit
145
131
148
149
132
    if not PyTuple_CheckExact(key):
149
    if not StaticTuple_CheckExact(key):
150
133
        raise TypeError('key %r is not a tuple' % (key,))
150
        raise TypeError('key %r is not a StaticTuple' % (key,))
151
134
    num_bits = PyTuple_GET_SIZE(key)
151
    num_bits = len(key)
152
135
    # 4 bytes per crc32, and another 1 byte between bits
152
    # 4 bytes per crc32, and another 1 byte between bits
153
136
    num_out_bytes = (5 * num_bits) - 1
153
    num_out_bytes = (5 * num_bits) - 1
154
137
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
154
    out = PyString_FromStringAndSize(NULL, num_out_bytes)
155
@@ -140,10 +157,10 @@
156
140
        if i > 0:
157
        if i > 0:
157
141
            c_out[0] = c'\x00'
158
            c_out[0] = c'\x00'
158
142
            c_out = c_out + 1
159
            c_out = c_out + 1
160
143
        bit = PyTuple_GET_ITEM_ptr(key, i)
160
        bit = StaticTuple_GET_ITEM_ptr(key, i)
161
144
        if not PyString_CheckExact_ptr(bit):
161
        if not PyString_CheckExact_ptr(bit):
164
145
            raise TypeError('Bit %d of %r is not a string: %r' % (i, key,
162
            raise TypeError('Bit %d of %r is not a string: %r'
165
146
            <object>bit))
163
                            % (i, key, <object>bit))
166
147
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
164
        c_bit = <Bytef *>PyString_AS_STRING_ptr(bit)
167
148
        c_len = PyString_GET_SIZE_ptr(bit)
165
        c_len = PyString_GET_SIZE_ptr(bit)
168
149
        crc_val = crc32(0, c_bit, c_len)
166
        crc_val = crc32(0, c_bit, c_len)
169
@@ -195,6 +212,7 @@
170
195
    cdef char *prefix, *value_start, *prefix_tail
212
    cdef char *prefix, *value_start, *prefix_tail
171
196
    cdef char *next_null, *last_null, *line_start
213
    cdef char *next_null, *last_null, *line_start
172
197
    cdef char *c_entry, *entry_start
214
    cdef char *c_entry, *entry_start
173
215
    cdef StaticTuple entry_bits
174
198
216
175
199
    if _LeafNode is None:
217
    if _LeafNode is None:
176
200
        from bzrlib import chk_map
218
        from bzrlib import chk_map
177
@@ -265,12 +283,14 @@
178
265
            if next_line == NULL:
283
            if next_line == NULL:
179
266
                raise ValueError('missing trailing newline')
284
                raise ValueError('missing trailing newline')
180
267
            cur = next_line + 1
285
            cur = next_line + 1
182
268
        entry_bits = PyTuple_New(width)
286
        entry_bits = StaticTuple_New(width)
183
269
        for i from 0 <= i < num_prefix_bits:
287
        for i from 0 <= i < num_prefix_bits:
184
288
            # TODO: Use PyList_GetItem, or turn prefix_bits into a
185
289
            #       tuple/StaticTuple
186
270
            entry = prefix_bits[i]
290
            entry = prefix_bits[i]
187
271
            # SET_ITEM 'steals' a reference
291
            # SET_ITEM 'steals' a reference
188
272
            Py_INCREF(entry)
292
            Py_INCREF(entry)
190
273
            PyTuple_SET_ITEM(entry_bits, i, entry)
293
            StaticTuple_SET_ITEM(entry_bits, i, entry)
191
274
        value = PyString_FromStringAndSize(value_start, next_line - value_start)
294
        value = PyString_FromStringAndSize(value_start, next_line - value_start)
192
275
        # The next entry bit needs the 'tail' from the prefix, and first part
295
        # The next entry bit needs the 'tail' from the prefix, and first part
193
276
        # of the line
296
        # of the line
194
@@ -288,7 +308,7 @@
195
288
            memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
308
            memcpy(c_entry + prefix_tail_len, line_start, next_null - line_start)
196
289
        Py_INCREF(entry)
309
        Py_INCREF(entry)
197
290
        i = num_prefix_bits
310
        i = num_prefix_bits
199
291
        PyTuple_SET_ITEM(entry_bits, i, entry)
311
        StaticTuple_SET_ITEM(entry_bits, i, entry)
200
292
        while next_null != last_null: # We have remaining bits
312
        while next_null != last_null: # We have remaining bits
201
293
            i = i + 1
313
            i = i + 1
202
294
            if i > width:
314
            if i > width:
203
@@ -301,11 +321,12 @@
204
301
            entry = PyString_FromStringAndSize(entry_start,
321
            entry = PyString_FromStringAndSize(entry_start,
205
302
                                               next_null - entry_start)
322
                                               next_null - entry_start)
206
303
            Py_INCREF(entry)
323
            Py_INCREF(entry)
208
304
            PyTuple_SET_ITEM(entry_bits, i, entry)
324
            StaticTuple_SET_ITEM(entry_bits, i, entry)
209
305
        if len(entry_bits) != width:
325
        if len(entry_bits) != width:
210
306
            raise AssertionError(
326
            raise AssertionError(
211
307
                'Incorrect number of elements (%d vs %d)'
327
                'Incorrect number of elements (%d vs %d)'
212
308
                % (len(entry_bits)+1, width + 1))
328
                % (len(entry_bits)+1, width + 1))
213
329
        entry_bits = StaticTuple_Intern(entry_bits)
214
309
        PyDict_SetItem(items, entry_bits, value)
330
        PyDict_SetItem(items, entry_bits, value)
215
310
    if len(items) != length:
331
    if len(items) != length:
216
311
        raise ValueError("item count (%d) mismatch for key %s,"
332
        raise ValueError("item count (%d) mismatch for key %s,"
217
@@ -343,6 +364,8 @@
218
343
        _unknown = chk_map._unknown
364
        _unknown = chk_map._unknown
219
344
    result = _InternalNode(search_key_func=search_key_func)
365
    result = _InternalNode(search_key_func=search_key_func)
220
345
366
221
367
    if not StaticTuple_CheckExact(key):
222
368
        raise TypeError('key %r is not a StaticTuple' % (key,))
223
346
    if not PyString_CheckExact(bytes):
369
    if not PyString_CheckExact(bytes):
224
347
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
370
        raise TypeError('bytes must be a plain string not %s' % (type(bytes),))
225
348
371
226
@@ -384,7 +407,8 @@
227
384
        memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
407
        memcpy(c_item_prefix + prefix_length, cur, next_null - cur)
228
385
        flat_key = PyString_FromStringAndSize(next_null + 1,
408
        flat_key = PyString_FromStringAndSize(next_null + 1,
229
386
                                              next_line - next_null - 1)
409
                                              next_line - next_null - 1)
231
387
        PyDict_SetItem(items, item_prefix, (flat_key,))
410
        flat_key = StaticTuple(flat_key).intern()
232
411
        PyDict_SetItem(items, item_prefix, flat_key)
233
388
        cur = next_line + 1
412
        cur = next_line + 1
234
389
    assert len(items) > 0
413
    assert len(items) > 0
235
390
    result._items = items
414
    result._items = items
236
@@ -398,4 +422,3 @@
237
398
    result._node_width = len(item_prefix)
422
    result._node_width = len(item_prefix)
238
399
    result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
423
    result._search_prefix = PyString_FromStringAndSize(prefix, prefix_length)
239
400
    return result
424
    return result
240
401
241
402
425
242
=== modified file 'bzrlib/_static_tuple_c.pxd'
243
--- bzrlib/_static_tuple_c.pxd	2009-10-07 15:57:25 +0000
244
+++ bzrlib/_static_tuple_c.pxd	2009-10-26 14:59:15 +0000
245
@@ -36,5 +36,9 @@
246
36
36
247
37
    # Steals a reference and val must be a valid type, no checking is done
37
    # Steals a reference and val must be a valid type, no checking is done
248
38
    void StaticTuple_SET_ITEM(StaticTuple key, Py_ssize_t offset, object val)
38
    void StaticTuple_SET_ITEM(StaticTuple key, Py_ssize_t offset, object val)
250
39
    object StaticTuple_GET_ITEM(StaticTuple key, Py_ssize_t offset)
39
    # We would normally use PyObject * here. However it seems that cython/pyrex
251
40
    # treat the PyObject defined in this header as something different than one
252
41
    # defined in a .pyx file. And since we don't INCREF, we need a raw pointer,
253
42
    # not an 'object' return value.
254
43
    void *StaticTuple_GET_ITEM(StaticTuple key, Py_ssize_t offset)
255
40
    int StaticTuple_CheckExact(object)
44
    int StaticTuple_CheckExact(object)
256
41
45
257
=== modified file 'bzrlib/chk_map.py'
258
--- bzrlib/chk_map.py	2009-10-20 20:30:21 +0000
259
+++ bzrlib/chk_map.py	2009-10-26 14:59:15 +0000
260
@@ -52,6 +52,7 @@
261
52
    registry,
52
    registry,
262
53
    trace,
53
    trace,
263
54
    )
54
    )
264
55
from bzrlib.static_tuple import StaticTuple
265
55
56
266
56
# approx 4MB
57
# approx 4MB
267
57
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
58
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
268
@@ -114,8 +115,9 @@
269
114
        """
115
        """
270
115
        delete_count = 0
116
        delete_count = 0
271
116
        # Check preconditions first.
117
        # Check preconditions first.
274
117
        new_items = set([key for (old, key, value) in delta if key is not None
118
        as_st = StaticTuple.from_sequence
275
118
            and old is None])
119
        new_items = set([as_st(key) for (old, key, value) in delta
276
120
                         if key is not None and old is None])
277
119
        existing_new = list(self.iteritems(key_filter=new_items))
121
        existing_new = list(self.iteritems(key_filter=new_items))
278
120
        if existing_new:
122
        if existing_new:
279
121
            raise errors.InconsistentDeltaDelta(delta,
123
            raise errors.InconsistentDeltaDelta(delta,
280
@@ -135,7 +137,7 @@
281
135
137
282
136
    def _ensure_root(self):
138
    def _ensure_root(self):
283
137
        """Ensure that the root node is an object not a key."""
139
        """Ensure that the root node is an object not a key."""
285
138
        if type(self._root_node) is tuple:
140
        if type(self._root_node) is StaticTuple:
286
139
            # Demand-load the root
141
            # Demand-load the root
287
140
            self._root_node = self._get_node(self._root_node)
142
            self._root_node = self._get_node(self._root_node)
288
141
143
289
@@ -149,7 +151,7 @@
290
149
        :param node: A tuple key or node object.
151
        :param node: A tuple key or node object.
291
150
        :return: A node object.
152
        :return: A node object.
292
151
        """
153
        """
294
152
        if type(node) is tuple:
154
        if type(node) is StaticTuple:
295
153
            bytes = self._read_bytes(node)
155
            bytes = self._read_bytes(node)
296
154
            return _deserialise(bytes, node,
156
            return _deserialise(bytes, node,
297
155
                search_key_func=self._search_key_func)
157
                search_key_func=self._search_key_func)
298
@@ -196,7 +198,7 @@
299
196
            for key, value in sorted(node._items.iteritems()):
198
            for key, value in sorted(node._items.iteritems()):
300
197
                # Don't use prefix nor indent here to line up when used in
199
                # Don't use prefix nor indent here to line up when used in
301
198
                # tests in conjunction with assertEqualDiff
200
                # tests in conjunction with assertEqualDiff
303
199
                result.append('      %r %r' % (key, value))
201
                result.append('      %r %r' % (tuple(key), value))
304
200
        return result
202
        return result
305
201
203
306
202
    @classmethod
204
    @classmethod
307
@@ -220,6 +222,9 @@
308
220
        root_key = klass._create_directly(store, initial_value,
222
        root_key = klass._create_directly(store, initial_value,
309
221
            maximum_size=maximum_size, key_width=key_width,
223
            maximum_size=maximum_size, key_width=key_width,
310
222
            search_key_func=search_key_func)
224
            search_key_func=search_key_func)
311
225
        if type(root_key) is not StaticTuple:
312
226
            raise AssertionError('we got a %s instead of a StaticTuple'
313
227
                                 % (type(root_key),))
314
223
        return root_key
228
        return root_key
315
224
229
316
225
    @classmethod
230
    @classmethod
317
@@ -240,9 +245,11 @@
318
240
        node = LeafNode(search_key_func=search_key_func)
245
        node = LeafNode(search_key_func=search_key_func)
319
241
        node.set_maximum_size(maximum_size)
246
        node.set_maximum_size(maximum_size)
320
242
        node._key_width = key_width
247
        node._key_width = key_width
322
243
        node._items = dict(initial_value)
248
        as_st = StaticTuple.from_sequence
323
249
        node._items = dict([(as_st(key), val) for key, val
324
250
                                               in initial_value.iteritems()])
325
244
        node._raw_size = sum([node._key_value_len(key, value)
251
        node._raw_size = sum([node._key_value_len(key, value)
327
245
                              for key,value in initial_value.iteritems()])
252
                              for key,value in node._items.iteritems()])
328
246
        node._len = len(node._items)
253
        node._len = len(node._items)
329
247
        node._compute_search_prefix()
254
        node._compute_search_prefix()
330
248
        node._compute_serialised_prefix()
255
        node._compute_serialised_prefix()
331
@@ -484,11 +491,14 @@
332
484
    def iteritems(self, key_filter=None):
491
    def iteritems(self, key_filter=None):
333
485
        """Iterate over the entire CHKMap's contents."""
492
        """Iterate over the entire CHKMap's contents."""
334
486
        self._ensure_root()
493
        self._ensure_root()
335
494
        if key_filter is not None:
336
495
            as_st = StaticTuple.from_sequence
337
496
            key_filter = [as_st(key) for key in key_filter]
338
487
        return self._root_node.iteritems(self._store, key_filter=key_filter)
497
        return self._root_node.iteritems(self._store, key_filter=key_filter)
339
488
498
340
489
    def key(self):
499
    def key(self):
341
490
        """Return the key for this map."""
500
        """Return the key for this map."""
343
491
        if type(self._root_node) is tuple:
501
        if type(self._root_node) is StaticTuple:
344
492
            return self._root_node
502
            return self._root_node
345
493
        else:
503
        else:
346
494
            return self._root_node._key
504
            return self._root_node._key
347
@@ -503,6 +513,7 @@
348
503
        :param key: A key to map.
513
        :param key: A key to map.
349
504
        :param value: The value to assign to key.
514
        :param value: The value to assign to key.
350
505
        """
515
        """
351
516
        key = StaticTuple.from_sequence(key)
352
506
        # Need a root object.
517
        # Need a root object.
353
507
        self._ensure_root()
518
        self._ensure_root()
354
508
        prefix, node_details = self._root_node.map(self._store, key, value)
519
        prefix, node_details = self._root_node.map(self._store, key, value)
355
@@ -519,12 +530,15 @@
356
519
    def _node_key(self, node):
530
    def _node_key(self, node):
357
520
        """Get the key for a node whether it's a tuple or node."""
531
        """Get the key for a node whether it's a tuple or node."""
358
521
        if type(node) is tuple:
532
        if type(node) is tuple:
359
533
            node = StaticTuple.from_sequence(node)
360
534
        if type(node) is StaticTuple:
361
522
            return node
535
            return node
362
523
        else:
536
        else:
363
524
            return node._key
537
            return node._key
364
525
538
365
526
    def unmap(self, key, check_remap=True):
539
    def unmap(self, key, check_remap=True):
366
527
        """remove key from the map."""
540
        """remove key from the map."""
367
541
        key = StaticTuple.from_sequence(key)
368
528
        self._ensure_root()
542
        self._ensure_root()
369
529
        if type(self._root_node) is InternalNode:
543
        if type(self._root_node) is InternalNode:
370
530
            unmapped = self._root_node.unmap(self._store, key,
544
            unmapped = self._root_node.unmap(self._store, key,
371
@@ -544,7 +558,7 @@
372
544
558
373
545
        :return: The key of the root node.
559
        :return: The key of the root node.
374
546
        """
560
        """
376
547
        if type(self._root_node) is tuple:
561
        if type(self._root_node) is StaticTuple:
377
548
            # Already saved.
562
            # Already saved.
378
549
            return self._root_node
563
            return self._root_node
379
550
        keys = list(self._root_node.serialise(self._store))
564
        keys = list(self._root_node.serialise(self._store))
380
@@ -881,7 +895,7 @@
381
881
            lines.append(serialized[prefix_len:])
895
            lines.append(serialized[prefix_len:])
382
882
            lines.extend(value_lines)
896
            lines.extend(value_lines)
383
883
        sha1, _, _ = store.add_lines((None,), (), lines)
897
        sha1, _, _ = store.add_lines((None,), (), lines)
385
884
        self._key = ("sha1:" + sha1,)
898
        self._key = StaticTuple("sha1:" + sha1,).intern()
386
885
        bytes = ''.join(lines)
899
        bytes = ''.join(lines)
387
886
        if len(bytes) != self._current_size():
900
        if len(bytes) != self._current_size():
388
887
            raise AssertionError('Invalid _current_size')
901
            raise AssertionError('Invalid _current_size')
389
@@ -1004,6 +1018,9 @@
390
1004
        :param key: The key that the serialised node has.
1018
        :param key: The key that the serialised node has.
391
1005
        :return: An InternalNode instance.
1019
        :return: An InternalNode instance.
392
1006
        """
1020
        """
393
1021
        if type(key) is not StaticTuple:
394
1022
            raise AssertionError('deserialise should be called with a'
395
1023
                                 ' StaticTuple not %s' % (type(key),))
396
1007
        return _deserialise_internal_node(bytes, key,
1024
        return _deserialise_internal_node(bytes, key,
397
1008
                                          search_key_func=search_key_func)
1025
                                          search_key_func=search_key_func)
398
1009
1026
399
@@ -1034,7 +1051,7 @@
400
1034
            # for whatever we are missing
1051
            # for whatever we are missing
401
1035
            shortcut = True
1052
            shortcut = True
402
1036
            for prefix, node in self._items.iteritems():
1053
            for prefix, node in self._items.iteritems():
404
1037
                if node.__class__ is tuple:
1054
                if node.__class__ is StaticTuple:
405
1038
                    keys[node] = (prefix, None)
1055
                    keys[node] = (prefix, None)
406
1039
                else:
1056
                else:
407
1040
                    yield node, None
1057
                    yield node, None
408
@@ -1069,7 +1086,7 @@
409
1069
                    # A given key can only match 1 child node, if it isn't
1086
                    # A given key can only match 1 child node, if it isn't
410
1070
                    # there, then we can just return nothing
1087
                    # there, then we can just return nothing
411
1071
                    return
1088
                    return
413
1072
                if node.__class__ is tuple:
1089
                if node.__class__ is StaticTuple:
414
1073
                    keys[node] = (search_prefix, [key])
1090
                    keys[node] = (search_prefix, [key])
415
1074
                else:
1091
                else:
416
1075
                    # This is loaded, and the only thing that can match,
1092
                    # This is loaded, and the only thing that can match,
417
@@ -1102,7 +1119,7 @@
418
1102
                        # We can ignore this one
1119
                        # We can ignore this one
419
1103
                        continue
1120
                        continue
420
1104
                    node_key_filter = prefix_to_keys[search_prefix]
1121
                    node_key_filter = prefix_to_keys[search_prefix]
422
1105
                    if node.__class__ is tuple:
1122
                    if node.__class__ is StaticTuple:
423
1106
                        keys[node] = (search_prefix, node_key_filter)
1123
                        keys[node] = (search_prefix, node_key_filter)
424
1107
                    else:
1124
                    else:
425
1108
                        yield node, node_key_filter
1125
                        yield node, node_key_filter
426
@@ -1117,7 +1134,7 @@
427
1117
                        if sub_prefix in length_filter:
1134
                        if sub_prefix in length_filter:
428
1118
                            node_key_filter.extend(prefix_to_keys[sub_prefix])
1135
                            node_key_filter.extend(prefix_to_keys[sub_prefix])
429
1119
                    if node_key_filter: # this key matched something, yield it
1136
                    if node_key_filter: # this key matched something, yield it
431
1120
                        if node.__class__ is tuple:
1137
                        if node.__class__ is StaticTuple:
432
1121
                            keys[node] = (prefix, node_key_filter)
1138
                            keys[node] = (prefix, node_key_filter)
433
1122
                        else:
1139
                        else:
434
1123
                            yield node, node_key_filter
1140
                            yield node, node_key_filter
435
@@ -1255,7 +1272,7 @@
436
1255
        :return: An iterable of the keys inserted by this operation.
1272
        :return: An iterable of the keys inserted by this operation.
437
1256
        """
1273
        """
438
1257
        for node in self._items.itervalues():
1274
        for node in self._items.itervalues():
440
1258
            if type(node) is tuple:
1275
            if type(node) is StaticTuple:
441
1259
                # Never deserialised.
1276
                # Never deserialised.
442
1260
                continue
1277
                continue
443
1261
            if node._key is not None:
1278
            if node._key is not None:
444
@@ -1272,7 +1289,7 @@
445
1272
        lines.append('%s\n' % (self._search_prefix,))
1289
        lines.append('%s\n' % (self._search_prefix,))
446
1273
        prefix_len = len(self._search_prefix)
1290
        prefix_len = len(self._search_prefix)
447
1274
        for prefix, node in sorted(self._items.items()):
1291
        for prefix, node in sorted(self._items.items()):
449
1275
            if type(node) is tuple:
1292
            if type(node) is StaticTuple:
450
1276
                key = node[0]
1293
                key = node[0]
451
1277
            else:
1294
            else:
452
1278
                key = node._key[0]
1295
                key = node._key[0]
453
@@ -1282,7 +1299,7 @@
454
1282
                    % (serialised, self._search_prefix))
1299
                    % (serialised, self._search_prefix))
455
1283
            lines.append(serialised[prefix_len:])
1300
            lines.append(serialised[prefix_len:])
456
1284
        sha1, _, _ = store.add_lines((None,), (), lines)
1301
        sha1, _, _ = store.add_lines((None,), (), lines)
458
1285
        self._key = ("sha1:" + sha1,)
1302
        self._key = StaticTuple("sha1:" + sha1,).intern()
459
1286
        _page_cache.add(self._key, ''.join(lines))
1303
        _page_cache.add(self._key, ''.join(lines))
460
1287
        yield self._key
1304
        yield self._key
461
1288
1305
462
@@ -1317,7 +1334,7 @@
463
1317
            raise AssertionError("unserialised nodes have no refs.")
1334
            raise AssertionError("unserialised nodes have no refs.")
464
1318
        refs = []
1335
        refs = []
465
1319
        for value in self._items.itervalues():
1336
        for value in self._items.itervalues():
467
1320
            if type(value) is tuple:
1337
            if type(value) is StaticTuple:
468
1321
                refs.append(value)
1338
                refs.append(value)
469
1322
            else:
1339
            else:
470
1323
                refs.append(value.key())
1340
                refs.append(value.key())
471
@@ -1437,6 +1454,12 @@
472
1437
1454
473
1438
    def __init__(self, store, new_root_keys, old_root_keys,
1455
    def __init__(self, store, new_root_keys, old_root_keys,
474
1439
                 search_key_func, pb=None):
1456
                 search_key_func, pb=None):
475
1457
        # TODO: Should we add a StaticTuple barrier here? It would be nice to
476
1458
        #       force callers to use StaticTuple, because there will often be
477
1459
        #       lots of keys passed in here. And even if we cast it locally,
478
1460
        #       that just meanst that we will have *both* a StaticTuple and a
479
1461
        #       tuple() in memory, referring to the same object. (so a net
480
1462
        #       increase in memory, not a decrease.)
481
1440
        self._store = store
1463
        self._store = store
482
1441
        self._new_root_keys = new_root_keys
1464
        self._new_root_keys = new_root_keys
483
1442
        self._old_root_keys = old_root_keys
1465
        self._old_root_keys = old_root_keys
484
@@ -1444,11 +1467,16 @@
485
1444
        # All uninteresting chks that we have seen. By the time they are added
1467
        # All uninteresting chks that we have seen. By the time they are added
486
1445
        # here, they should be either fully ignored, or queued up for
1468
        # here, they should be either fully ignored, or queued up for
487
1446
        # processing
1469
        # processing
488
1470
        # TODO: This might grow to a large size if there are lots of merge
489
1471
        #       parents, etc. However, it probably doesn't scale to O(history)
490
1472
        #       like _processed_new_refs does.
491
1447
        self._all_old_chks = set(self._old_root_keys)
1473
        self._all_old_chks = set(self._old_root_keys)
492
1448
        # All items that we have seen from the old_root_keys
1474
        # All items that we have seen from the old_root_keys
493
1449
        self._all_old_items = set()
1475
        self._all_old_items = set()
494
1450
        # These are interesting items which were either read, or already in the
1476
        # These are interesting items which were either read, or already in the
495
1451
        # interesting queue (so we don't need to walk them again)
1477
        # interesting queue (so we don't need to walk them again)
496
1478
        # TODO: processed_new_refs becomes O(all_chks), consider switching to
497
1479
        #       SimpleSet here.
498
1452
        self._processed_new_refs = set()
1480
        self._processed_new_refs = set()
499
1453
        self._search_key_func = search_key_func
1481
        self._search_key_func = search_key_func
500
1454
1482
501
@@ -1466,6 +1494,7 @@
502
1466
        # this code. (We may want to evaluate saving the raw bytes into the
1494
        # this code. (We may want to evaluate saving the raw bytes into the
503
1467
        # page cache, which would allow a working tree update after the fetch
1495
        # page cache, which would allow a working tree update after the fetch
504
1468
        # to not have to read the bytes again.)
1496
        # to not have to read the bytes again.)
505
1497
        as_st = StaticTuple.from_sequence
506
1469
        stream = self._store.get_record_stream(keys, 'unordered', True)
1498
        stream = self._store.get_record_stream(keys, 'unordered', True)
507
1470
        for record in stream:
1499
        for record in stream:
508
1471
            if self._pb is not None:
1500
            if self._pb is not None:
509
@@ -1478,10 +1507,18 @@
510
1478
            if type(node) is InternalNode:
1507
            if type(node) is InternalNode:
511
1479
                # Note we don't have to do node.refs() because we know that
1508
                # Note we don't have to do node.refs() because we know that
512
1480
                # there are no children that have been pushed into this node
1509
                # there are no children that have been pushed into this node
513
1510
                # Note: Using as_st() here seemed to save 1.2MB, which would
514
1511
                #       indicate that we keep 100k prefix_refs around while
515
1512
                #       processing. They *should* be shorter lived than that...
516
1513
                #       It does cost us ~10s of processing time
517
1514
                #prefix_refs = [as_st(item) for item in node._items.iteritems()]
518
1481
                prefix_refs = node._items.items()
1515
                prefix_refs = node._items.items()
519
1482
                items = []
1516
                items = []
520
1483
            else:
1517
            else:
521
1484
                prefix_refs = []
1518
                prefix_refs = []
522
1519
                # Note: We don't use a StaticTuple here. Profiling showed a
523
1520
                #       minor memory improvement (0.8MB out of 335MB peak 0.2%)
524
1521
                #       But a significant slowdown (15s / 145s, or 10%)
525
1485
                items = node._items.items()
1522
                items = node._items.items()
526
1486
            yield record, node, prefix_refs, items
1523
            yield record, node, prefix_refs, items
527
1487
1524
528
@@ -1495,6 +1532,10 @@
529
1495
                                if p_r[1] not in all_old_chks]
1532
                                if p_r[1] not in all_old_chks]
530
1496
            new_refs = [p_r[1] for p_r in prefix_refs]
1533
            new_refs = [p_r[1] for p_r in prefix_refs]
531
1497
            all_old_chks.update(new_refs)
1534
            all_old_chks.update(new_refs)
532
1535
            # TODO: This might be a good time to turn items into StaticTuple
533
1536
            #       instances and possibly intern them. However, this does not
534
1537
            #       impact 'initial branch' performance, so I'm not worrying
535
1538
            #       about this yet
536
1498
            self._all_old_items.update(items)
1539
            self._all_old_items.update(items)
537
1499
            # Queue up the uninteresting references
1540
            # Queue up the uninteresting references
538
1500
            # Don't actually put them in the 'to-read' queue until we have
1541
            # Don't actually put them in the 'to-read' queue until we have
539
@@ -1553,6 +1594,9 @@
540
1553
            #       current design allows for this, as callers will do the work
1594
            #       current design allows for this, as callers will do the work
541
1554
            #       to make the results unique. We might profile whether we
1595
            #       to make the results unique. We might profile whether we
542
1555
            #       gain anything by ensuring unique return values for items
1596
            #       gain anything by ensuring unique return values for items
543
1597
            # TODO: This might be a good time to cast to StaticTuple, as
544
1598
            #       self._new_item_queue will hold the contents of multiple
545
1599
            #       records for an extended lifetime
546
1556
            new_items = [item for item in items
1600
            new_items = [item for item in items
547
1557
                               if item not in self._all_old_items]
1601
                               if item not in self._all_old_items]
548
1558
            self._new_item_queue.extend(new_items)
1602
            self._new_item_queue.extend(new_items)
549
@@ -1583,16 +1627,31 @@
550
1583
        if new_items:
1627
        if new_items:
551
1584
            yield None, new_items
1628
            yield None, new_items
552
1585
        refs = refs.difference(all_old_chks)
1629
        refs = refs.difference(all_old_chks)
553
1630
        processed_new_refs.update(refs)
554
1586
        while refs:
1631
        while refs:
555
1632
            # TODO: Using a SimpleSet for self._processed_new_refs and
556
1633
            #       saved as much as 10MB of peak memory. However, it requires
557
1634
            #       implementing a non-pyrex version.
558
1587
            next_refs = set()
1635
            next_refs = set()
559
1588
            next_refs_update = next_refs.update
1636
            next_refs_update = next_refs.update
560
1589
            # Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
1637
            # Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
561
1590
            # from 1m54s to 1m51s. Consider it.
1638
            # from 1m54s to 1m51s. Consider it.
562
1591
            for record, _, p_refs, items in self._read_nodes_from_store(refs):
1639
            for record, _, p_refs, items in self._read_nodes_from_store(refs):
565
1592
                items = [item for item in items
1640
                if all_old_items:
566
1593
                         if item not in all_old_items]
1641
                    # using the 'if' check saves about 145s => 141s, when
567
1642
                    # streaming initial branch of Launchpad data.
568
1643
                    items = [item for item in items
569
1644
                             if item not in all_old_items]
570
1594
                yield record, items
1645
                yield record, items
571
1595
                next_refs_update([p_r[1] for p_r in p_refs])
1646
                next_refs_update([p_r[1] for p_r in p_refs])
572
1647
                del p_refs
573
1648
            # set1.difference(set/dict) walks all of set1, and checks if it
574
1649
            # exists in 'other'.
575
1650
            # set1.difference(iterable) walks all of iterable, and does a
576
1651
            # 'difference_update' on a clone of set1. Pick wisely based on the
577
1652
            # expected sizes of objects.
578
1653
            # in our case it is expected that 'new_refs' will always be quite
579
1654
            # small.
580
1596
            next_refs = next_refs.difference(all_old_chks)
1655
            next_refs = next_refs.difference(all_old_chks)
581
1597
            next_refs = next_refs.difference(processed_new_refs)
1656
            next_refs = next_refs.difference(processed_new_refs)
582
1598
            processed_new_refs.update(next_refs)
1657
            processed_new_refs.update(next_refs)
583
@@ -1605,6 +1664,7 @@
584
1605
        self._old_queue = []
1664
        self._old_queue = []
585
1606
        all_old_chks = self._all_old_chks
1665
        all_old_chks = self._all_old_chks
586
1607
        for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
1666
        for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
587
1667
            # TODO: Use StaticTuple here?
588
1608
            self._all_old_items.update(items)
1668
            self._all_old_items.update(items)
589
1609
            refs = [r for _,r in prefix_refs if r not in all_old_chks]
1669
            refs = [r for _,r in prefix_refs if r not in all_old_chks]
590
1610
            self._old_queue.extend(refs)
1670
            self._old_queue.extend(refs)
591
@@ -1660,3 +1720,22 @@
592
1660
        )
1720
        )
593
1661
search_key_registry.register('hash-16-way', _search_key_16)
1721
search_key_registry.register('hash-16-way', _search_key_16)
594
1662
search_key_registry.register('hash-255-way', _search_key_255)
1722
search_key_registry.register('hash-255-way', _search_key_255)
595
1723
596
1724
597
1725
def _check_key(key):
598
1726
    """Helper function to assert that a key is properly formatted.
599
1727
600
1728
    This generally shouldn't be used in production code, but it can be helpful
601
1729
    to debug problems.
602
1730
    """
603
1731
    if type(key) is not StaticTuple:
604
1732
        raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
605
1733
    if len(key) != 1:
606
1734
        raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
607
1735
    if type(key[0]) is not str:
608
1736
        raise TypeError('key %r should hold a str, not %r'
609
1737
                        % (key, type(key[0])))
610
1738
    if not key[0].startswith('sha1:'):
611
1739
        raise ValueError('key %r should point to a sha1:' % (key,))
612
1740
613
1741
614
1663
1742
615
=== modified file 'bzrlib/groupcompress.py'
616
--- bzrlib/groupcompress.py	2009-10-19 15:45:10 +0000
617
+++ bzrlib/groupcompress.py	2009-10-26 14:59:15 +0000
618
@@ -1269,6 +1269,7 @@
619
1269
        """See VersionedFiles.clear_cache()"""
1269
        """See VersionedFiles.clear_cache()"""
620
1270
        self._group_cache.clear()
1270
        self._group_cache.clear()
621
1271
        self._index._graph_index.clear_cache()
1271
        self._index._graph_index.clear_cache()
622
1272
        self._index._int_cache.clear()
623
1272
1273
624
1273
    def _check_add(self, key, lines, random_id, check_content):
1274
    def _check_add(self, key, lines, random_id, check_content):
625
1274
        """check that version_id and lines are safe to add."""
1275
        """check that version_id and lines are safe to add."""
626
@@ -1832,6 +1833,9 @@
627
1832
        self.has_graph = parents
1833
        self.has_graph = parents
628
1833
        self._is_locked = is_locked
1834
        self._is_locked = is_locked
629
1834
        self._inconsistency_fatal = inconsistency_fatal
1835
        self._inconsistency_fatal = inconsistency_fatal
630
1836
        # GroupCompress records tend to have the same 'group' start + offset
631
1837
        # repeated over and over, this creates a surplus of ints
632
1838
        self._int_cache = {}
633
1835
        if track_external_parent_refs:
1839
        if track_external_parent_refs:
634
1836
            self._key_dependencies = knit._KeyRefs(
1840
            self._key_dependencies = knit._KeyRefs(
635
1837
                track_new_keys=track_new_keys)
1841
                track_new_keys=track_new_keys)
636
@@ -2013,11 +2017,24 @@
637
2013
        """Convert an index value to position details."""
2017
        """Convert an index value to position details."""
638
2014
        bits = node[2].split(' ')
2018
        bits = node[2].split(' ')
639
2015
        # It would be nice not to read the entire gzip.
2019
        # It would be nice not to read the entire gzip.
640
2020
        # start and stop are put into _int_cache because they are very common.
641
2021
        # They define the 'group' that an entry is in, and many groups can have
642
2022
        # thousands of objects.
643
2023
        # Branching Launchpad, for example, saves ~600k integers, at 12 bytes
644
2024
        # each, or about 7MB. Note that it might be even more when you consider
645
2025
        # how PyInt is allocated in separate slabs. And you can't return a slab
646
2026
        # to the OS if even 1 int on it is in use. Note though that Python uses
647
2027
        # a LIFO when re-using PyInt slots, which probably causes more
648
2028
        # fragmentation.
649
2016
        start = int(bits[0])
2029
        start = int(bits[0])
650
2030
        start = self._int_cache.setdefault(start, start)
651
2017
        stop = int(bits[1])
2031
        stop = int(bits[1])
652
2032
        stop = self._int_cache.setdefault(stop, stop)
653
2018
        basis_end = int(bits[2])
2033
        basis_end = int(bits[2])
654
2019
        delta_end = int(bits[3])
2034
        delta_end = int(bits[3])
656
2020
        return node[0], start, stop, basis_end, delta_end
2035
        # We can't use StaticTuple here, because node[0] is a BTreeGraphIndex
657
2036
        # instance...
658
2037
        return (node[0], start, stop, basis_end, delta_end)
659
2021
2038
660
2022
    def scan_unvalidated_index(self, graph_index):
2039
    def scan_unvalidated_index(self, graph_index):
661
2023
        """Inform this _GCGraphIndex that there is an unvalidated index.
2040
        """Inform this _GCGraphIndex that there is an unvalidated index.
662
2024
2041
663
=== modified file 'bzrlib/inventory.py'
664
--- bzrlib/inventory.py	2009-10-20 20:29:11 +0000
665
+++ bzrlib/inventory.py	2009-10-26 14:59:15 +0000
666
@@ -51,6 +51,7 @@
667
51
    )
51
    )
668
52
from bzrlib.symbol_versioning import deprecated_in, deprecated_method
52
from bzrlib.symbol_versioning import deprecated_in, deprecated_method
669
53
from bzrlib.trace import mutter
53
from bzrlib.trace import mutter
670
54
from bzrlib.static_tuple import StaticTuple
671
54
55
672
55
56
673
56
class InventoryEntry(object):
57
class InventoryEntry(object):
674
@@ -1599,8 +1600,6 @@
675
1599
        interesting.add(None) # this will auto-filter it in the loop
1600
        interesting.add(None) # this will auto-filter it in the loop
676
1600
        remaining_parents.discard(None) 
1601
        remaining_parents.discard(None) 
677
1601
        while remaining_parents:
1602
        while remaining_parents:
678
1602
            if None in remaining_parents:
679
1603
                import pdb; pdb.set_trace()
680
1604
            next_parents = set()
1603
            next_parents = set()
681
1605
            for entry in self._getitems(remaining_parents):
1604
            for entry in self._getitems(remaining_parents):
682
1606
                next_parents.add(entry.parent_id)
1605
                next_parents.add(entry.parent_id)
683
@@ -1615,7 +1614,7 @@
684
1615
        while directories_to_expand:
1614
        while directories_to_expand:
685
1616
            # Expand directories by looking in the
1615
            # Expand directories by looking in the
686
1617
            # parent_id_basename_to_file_id map
1616
            # parent_id_basename_to_file_id map
688
1618
            keys = [(f,) for f in directories_to_expand]
1617
            keys = [StaticTuple(f,).intern() for f in directories_to_expand]
689
1619
            directories_to_expand = set()
1618
            directories_to_expand = set()
690
1620
            items = self.parent_id_basename_to_file_id.iteritems(keys)
1619
            items = self.parent_id_basename_to_file_id.iteritems(keys)
691
1621
            next_file_ids = set([item[1] for item in items])
1620
            next_file_ids = set([item[1] for item in items])
692
@@ -1810,7 +1809,7 @@
693
1810
                        pass
1809
                        pass
694
1811
                deletes.add(file_id)
1810
                deletes.add(file_id)
695
1812
            else:
1811
            else:
697
1813
                new_key = (file_id,)
1812
                new_key = StaticTuple(file_id,)
698
1814
                new_value = result._entry_to_bytes(entry)
1813
                new_value = result._entry_to_bytes(entry)
699
1815
                # Update caches. It's worth doing this whether
1814
                # Update caches. It's worth doing this whether
700
1816
                # we're propagating the old caches or not.
1815
                # we're propagating the old caches or not.
701
@@ -1819,13 +1818,13 @@
702
1819
            if old_path is None:
1818
            if old_path is None:
703
1820
                old_key = None
1819
                old_key = None
704
1821
            else:
1820
            else:
706
1822
                old_key = (file_id,)
1821
                old_key = StaticTuple(file_id,)
707
1823
                if self.id2path(file_id) != old_path:
1822
                if self.id2path(file_id) != old_path:
708
1824
                    raise errors.InconsistentDelta(old_path, file_id,
1823
                    raise errors.InconsistentDelta(old_path, file_id,
709
1825
                        "Entry was at wrong other path %r." %
1824
                        "Entry was at wrong other path %r." %
710
1826
                        self.id2path(file_id))
1825
                        self.id2path(file_id))
711
1827
                altered.add(file_id)
1826
                altered.add(file_id)
713
1828
            id_to_entry_delta.append((old_key, new_key, new_value))
1827
            id_to_entry_delta.append(StaticTuple(old_key, new_key, new_value))
714
1829
            if result.parent_id_basename_to_file_id is not None:
1828
            if result.parent_id_basename_to_file_id is not None:
715
1830
                # parent_id, basename changes
1829
                # parent_id, basename changes
716
1831
                if old_path is None:
1830
                if old_path is None:
717
@@ -1923,7 +1922,13 @@
718
1923
        search_key_name = intern(info.get('search_key_name', 'plain'))
1922
        search_key_name = intern(info.get('search_key_name', 'plain'))
719
1924
        parent_id_basename_to_file_id = intern(info.get(
1923
        parent_id_basename_to_file_id = intern(info.get(
720
1925
            'parent_id_basename_to_file_id', None))
1924
            'parent_id_basename_to_file_id', None))
721
1925
        if not parent_id_basename_to_file_id.startswith('sha1:'):
722
1926
            raise ValueError('parent_id_basename_to_file_id should be a sha1'
723
1927
                             ' key not %r' % (parent_id_basename_to_file_id,))
724
1926
        id_to_entry = info['id_to_entry']
1928
        id_to_entry = info['id_to_entry']
725
1929
        if not id_to_entry.startswith('sha1:'):
726
1930
            raise ValueError('id_to_entry should be a sha1'
727
1931
                             ' key not %r' % (id_to_entry,))
728
1927
1932
729
1928
        result = CHKInventory(search_key_name)
1933
        result = CHKInventory(search_key_name)
730
1929
        result.revision_id = revision_id
1934
        result.revision_id = revision_id
731
@@ -1932,12 +1937,13 @@
732
1932
                            result._search_key_name)
1937
                            result._search_key_name)
733
1933
        if parent_id_basename_to_file_id is not None:
1938
        if parent_id_basename_to_file_id is not None:
734
1934
            result.parent_id_basename_to_file_id = chk_map.CHKMap(
1939
            result.parent_id_basename_to_file_id = chk_map.CHKMap(
736
1935
                chk_store, (parent_id_basename_to_file_id,),
1940
                chk_store, StaticTuple(parent_id_basename_to_file_id,),
737
1936
                search_key_func=search_key_func)
1941
                search_key_func=search_key_func)
738
1937
        else:
1942
        else:
739
1938
            result.parent_id_basename_to_file_id = None
1943
            result.parent_id_basename_to_file_id = None
740
1939
1944
742
1940
        result.id_to_entry = chk_map.CHKMap(chk_store, (id_to_entry,),
1945
        result.id_to_entry = chk_map.CHKMap(chk_store,
743
1946
                                            StaticTuple(id_to_entry,),
744
1941
                                            search_key_func=search_key_func)
1947
                                            search_key_func=search_key_func)
745
1942
        if (result.revision_id,) != expected_revision_id:
1948
        if (result.revision_id,) != expected_revision_id:
746
1943
            raise ValueError("Mismatched revision id and expected: %r, %r" %
1949
            raise ValueError("Mismatched revision id and expected: %r, %r" %
747
@@ -1965,7 +1971,8 @@
748
1965
        id_to_entry_dict = {}
1971
        id_to_entry_dict = {}
749
1966
        parent_id_basename_dict = {}
1972
        parent_id_basename_dict = {}
750
1967
        for path, entry in inventory.iter_entries():
1973
        for path, entry in inventory.iter_entries():
752
1968
            id_to_entry_dict[(entry.file_id,)] = entry_to_bytes(entry)
1974
            key = StaticTuple(entry.file_id,).intern()
753
1975
            id_to_entry_dict[key] = entry_to_bytes(entry)
754
1969
            p_id_key = parent_id_basename_key(entry)
1976
            p_id_key = parent_id_basename_key(entry)
755
1970
            parent_id_basename_dict[p_id_key] = entry.file_id
1977
            parent_id_basename_dict[p_id_key] = entry.file_id
756
1971
1978
757
@@ -1994,7 +2001,7 @@
758
1994
            parent_id = entry.parent_id
2001
            parent_id = entry.parent_id
759
1995
        else:
2002
        else:
760
1996
            parent_id = ''
2003
            parent_id = ''
762
1997
        return parent_id, entry.name.encode('utf8')
2004
        return StaticTuple(parent_id, entry.name.encode('utf8')).intern()
763
1998
2005
764
1999
    def __getitem__(self, file_id):
2006
    def __getitem__(self, file_id):
765
2000
        """map a single file_id -> InventoryEntry."""
2007
        """map a single file_id -> InventoryEntry."""
766
@@ -2005,7 +2012,7 @@
767
2005
            return result
2012
            return result
768
2006
        try:
2013
        try:
769
2007
            return self._bytes_to_entry(
2014
            return self._bytes_to_entry(
771
2008
                self.id_to_entry.iteritems([(file_id,)]).next()[1])
2015
                self.id_to_entry.iteritems([StaticTuple(file_id,)]).next()[1])
772
2009
        except StopIteration:
2016
        except StopIteration:
773
2010
            # really we're passing an inventory, not a tree...
2017
            # really we're passing an inventory, not a tree...
774
2011
            raise errors.NoSuchId(self, file_id)
2018
            raise errors.NoSuchId(self, file_id)
775
@@ -2024,7 +2031,7 @@
776
2024
                remaining.append(file_id)
2031
                remaining.append(file_id)
777
2025
            else:
2032
            else:
778
2026
                result.append(entry)
2033
                result.append(entry)
780
2027
        file_keys = [(f,) for f in remaining]
2034
        file_keys = [StaticTuple(f,).intern() for f in remaining]
781
2028
        for file_key, value in self.id_to_entry.iteritems(file_keys):
2035
        for file_key, value in self.id_to_entry.iteritems(file_keys):
782
2029
            entry = self._bytes_to_entry(value)
2036
            entry = self._bytes_to_entry(value)
783
2030
            result.append(entry)
2037
            result.append(entry)
784
@@ -2035,7 +2042,8 @@
785
2035
        # Perhaps have an explicit 'contains' method on CHKMap ?
2042
        # Perhaps have an explicit 'contains' method on CHKMap ?
786
2036
        if self._fileid_to_entry_cache.get(file_id, None) is not None:
2043
        if self._fileid_to_entry_cache.get(file_id, None) is not None:
787
2037
            return True
2044
            return True
789
2038
        return len(list(self.id_to_entry.iteritems([(file_id,)]))) == 1
2045
        return len(list(
790
2046
            self.id_to_entry.iteritems([StaticTuple(file_id,)]))) == 1
791
2039
2047
792
2040
    def is_root(self, file_id):
2048
    def is_root(self, file_id):
793
2041
        return file_id == self.root_id
2049
        return file_id == self.root_id
794
@@ -2193,7 +2201,7 @@
795
2193
            basename_utf8 = basename.encode('utf8')
2201
            basename_utf8 = basename.encode('utf8')
796
2194
            file_id = self._path_to_fileid_cache.get(cur_path, None)
2202
            file_id = self._path_to_fileid_cache.get(cur_path, None)
797
2195
            if file_id is None:
2203
            if file_id is None:
799
2196
                key_filter = [(current_id, basename_utf8)]
2204
                key_filter = [StaticTuple(current_id, basename_utf8)]
800
2197
                items = parent_id_index.iteritems(key_filter)
2205
                items = parent_id_index.iteritems(key_filter)
801
2198
                for (parent_id, name_utf8), file_id in items:
2206
                for (parent_id, name_utf8), file_id in items:
802
2199
                    if parent_id != current_id or name_utf8 != basename_utf8:
2207
                    if parent_id != current_id or name_utf8 != basename_utf8:
803
@@ -2215,16 +2223,16 @@
804
2215
            lines.append('search_key_name: %s\n' % (self._search_key_name,))
2223
            lines.append('search_key_name: %s\n' % (self._search_key_name,))
805
2216
            lines.append("root_id: %s\n" % self.root_id)
2224
            lines.append("root_id: %s\n" % self.root_id)
806
2217
            lines.append('parent_id_basename_to_file_id: %s\n' %
2225
            lines.append('parent_id_basename_to_file_id: %s\n' %
808
2218
                self.parent_id_basename_to_file_id.key())
2226
                (self.parent_id_basename_to_file_id.key()[0],))
809
2219
            lines.append("revision_id: %s\n" % self.revision_id)
2227
            lines.append("revision_id: %s\n" % self.revision_id)
811
2220
            lines.append("id_to_entry: %s\n" % self.id_to_entry.key())
2228
            lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
812
2221
        else:
2229
        else:
813
2222
            lines.append("revision_id: %s\n" % self.revision_id)
2230
            lines.append("revision_id: %s\n" % self.revision_id)
814
2223
            lines.append("root_id: %s\n" % self.root_id)
2231
            lines.append("root_id: %s\n" % self.root_id)
815
2224
            if self.parent_id_basename_to_file_id is not None:
2232
            if self.parent_id_basename_to_file_id is not None:
816
2225
                lines.append('parent_id_basename_to_file_id: %s\n' %
2233
                lines.append('parent_id_basename_to_file_id: %s\n' %
819
2226
                    self.parent_id_basename_to_file_id.key())
2234
                    (self.parent_id_basename_to_file_id.key()[0],))
820
2227
            lines.append("id_to_entry: %s\n" % self.id_to_entry.key())
2235
            lines.append("id_to_entry: %s\n" % (self.id_to_entry.key()[0],))
821
2228
        return lines
2236
        return lines
822
2229
2237
823
2230
    @property
2238
    @property
824
@@ -2271,8 +2279,8 @@
825
2271
        parent_id_index = self._chk_inventory.parent_id_basename_to_file_id
2279
        parent_id_index = self._chk_inventory.parent_id_basename_to_file_id
826
2272
        child_keys = set()
2280
        child_keys = set()
827
2273
        for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
2281
        for (parent_id, name_utf8), file_id in parent_id_index.iteritems(
830
2274
            key_filter=[(self.file_id,)]):
2282
            key_filter=[StaticTuple(self.file_id,)]):
831
2275
            child_keys.add((file_id,))
2283
            child_keys.add(StaticTuple(file_id,))
832
2276
        cached = set()
2284
        cached = set()
833
2277
        for file_id_key in child_keys:
2285
        for file_id_key in child_keys:
834
2278
            entry = self._chk_inventory._fileid_to_entry_cache.get(
2286
            entry = self._chk_inventory._fileid_to_entry_cache.get(
835
2279
2287
836
=== modified file 'bzrlib/repofmt/groupcompress_repo.py'
837
--- bzrlib/repofmt/groupcompress_repo.py	2009-10-19 16:21:20 +0000
838
+++ bzrlib/repofmt/groupcompress_repo.py	2009-10-26 14:59:15 +0000
839
@@ -53,6 +53,7 @@
840
53
    ResumedPack,
53
    ResumedPack,
841
54
    Packer,
54
    Packer,
842
55
    )
55
    )
843
56
from bzrlib.static_tuple import StaticTuple
844
56
57
845
57
58
846
58
class GCPack(NewPack):
59
class GCPack(NewPack):
847
@@ -814,14 +815,16 @@
848
814
                                 ' no new_path %r' % (file_id,))
815
                                 ' no new_path %r' % (file_id,))
849
815
            if new_path == '':
816
            if new_path == '':
850
816
                new_inv.root_id = file_id
817
                new_inv.root_id = file_id
852
817
                parent_id_basename_key = ('', '')
818
                parent_id_basename_key = StaticTuple('', '').intern()
853
818
            else:
819
            else:
854
819
                utf8_entry_name = entry.name.encode('utf-8')
820
                utf8_entry_name = entry.name.encode('utf-8')
856
820
                parent_id_basename_key = (entry.parent_id, utf8_entry_name)
821
                parent_id_basename_key = StaticTuple(entry.parent_id,
857
822
                                                     utf8_entry_name).intern()
858
821
            new_value = entry_to_bytes(entry)
823
            new_value = entry_to_bytes(entry)
859
822
            # Populate Caches?
824
            # Populate Caches?
860
823
            # new_inv._path_to_fileid_cache[new_path] = file_id
825
            # new_inv._path_to_fileid_cache[new_path] = file_id
862
824
            id_to_entry_dict[(file_id,)] = new_value
826
            key = StaticTuple(file_id).intern()
863
827
            id_to_entry_dict[key] = new_value
864
825
            parent_id_basename_dict[parent_id_basename_key] = file_id
828
            parent_id_basename_dict[parent_id_basename_key] = file_id
865
826
829
866
827
        new_inv._populate_from_dicts(self.chk_bytes, id_to_entry_dict,
830
        new_inv._populate_from_dicts(self.chk_bytes, id_to_entry_dict,
867
@@ -949,6 +952,10 @@
868
949
                        pb=pb):
952
                        pb=pb):
869
950
                for name, bytes in items:
953
                for name, bytes in items:
870
951
                    (name_utf8, file_id, revision_id) = bytes_to_info(bytes)
954
                    (name_utf8, file_id, revision_id) = bytes_to_info(bytes)
871
955
                    # TODO: consider interning file_id, revision_id here, or
872
956
                    #       pushing that intern() into bytes_to_info()
873
957
                    # TODO: rich_root should always be True here, for all
874
958
                    #       repositories that support chk_bytes
875
952
                    if not rich_root and name_utf8 == '':
959
                    if not rich_root and name_utf8 == '':
876
953
                        continue
960
                        continue
877
954
                    try:
961
                    try:
878
@@ -1189,7 +1196,9 @@
879
1189
            # are always rich-root, so there are no synthesised root records to
1196
            # are always rich-root, so there are no synthesised root records to
880
1190
            # ignore.
1197
            # ignore.
881
1191
            _, file_id, revision_id = bytes_to_info(bytes)
1198
            _, file_id, revision_id = bytes_to_info(bytes)
883
1192
            text_keys.add((file_id, revision_id))
1199
            file_id = intern(file_id)
884
1200
            revision_id = intern(revision_id)
885
1201
            text_keys.add(StaticTuple(file_id, revision_id).intern())
886
1193
        yield record
1202
        yield record
887
1194
1203
888
1195
1204
889
1196
1205
890
=== modified file 'bzrlib/tests/test__chk_map.py'
891
--- bzrlib/tests/test__chk_map.py	2009-04-09 20:23:07 +0000
892
+++ bzrlib/tests/test__chk_map.py	2009-10-26 14:59:15 +0000
893
@@ -20,6 +20,8 @@
894
20
    chk_map,
20
    chk_map,
895
21
    tests,
21
    tests,
896
22
    )
22
    )
897
23
from bzrlib.static_tuple import StaticTuple
898
24
stuple = StaticTuple
899
23
25
900
24
26
901
25
def load_tests(standard_tests, module, loader):
27
def load_tests(standard_tests, module, loader):
902
@@ -67,25 +69,25 @@
903
67
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
69
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
904
68
70
905
69
    def test_simple_16(self):
71
    def test_simple_16(self):
910
70
        self.assertSearchKey16('8C736521', ('foo',))
72
        self.assertSearchKey16('8C736521', stuple('foo',))
911
71
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
73
        self.assertSearchKey16('8C736521\x008C736521', stuple('foo', 'foo'))
912
72
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
74
        self.assertSearchKey16('8C736521\x0076FF8CAA', stuple('foo', 'bar'))
913
73
        self.assertSearchKey16('ED82CD11', ('abcd',))
75
        self.assertSearchKey16('ED82CD11', stuple('abcd',))
914
74
76
915
75
    def test_simple_255(self):
77
    def test_simple_255(self):
919
76
        self.assertSearchKey255('\x8cse!', ('foo',))
78
        self.assertSearchKey255('\x8cse!', stuple('foo',))
920
77
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
79
        self.assertSearchKey255('\x8cse!\x00\x8cse!', stuple('foo', 'foo'))
921
78
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
80
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', stuple('foo', 'bar'))
922
79
        # The standard mapping for these would include '\n', so it should be
81
        # The standard mapping for these would include '\n', so it should be
923
80
        # mapped to '_'
82
        # mapped to '_'
925
81
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
83
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', stuple('<', 'V'))
926
82
84
927
83
    def test_255_does_not_include_newline(self):
85
    def test_255_does_not_include_newline(self):
928
84
        # When mapping via _search_key_255, we should never have the '\n'
86
        # When mapping via _search_key_255, we should never have the '\n'
929
85
        # character, but all other 255 values should be present
87
        # character, but all other 255 values should be present
930
86
        chars_used = set()
88
        chars_used = set()
931
87
        for char_in in range(256):
89
        for char_in in range(256):
933
88
            search_key = self.module._search_key_255((chr(char_in),))
90
            search_key = self.module._search_key_255(stuple(chr(char_in),))
934
89
            chars_used.update(search_key)
91
            chars_used.update(search_key)
935
90
        all_chars = set([chr(x) for x in range(256)])
92
        all_chars = set([chr(x) for x in range(256)])
936
91
        unused_chars = all_chars.symmetric_difference(chars_used)
93
        unused_chars = all_chars.symmetric_difference(chars_used)
937
@@ -113,10 +115,11 @@
938
113
115
939
114
    def test_deserialise_empty(self):
116
    def test_deserialise_empty(self):
940
115
        node = self.module._deserialise_leaf_node(
117
        node = self.module._deserialise_leaf_node(
942
116
            "chkleaf:\n10\n1\n0\n\n", ("sha1:1234",))
118
            "chkleaf:\n10\n1\n0\n\n", stuple("sha1:1234",))
943
117
        self.assertEqual(0, len(node))
119
        self.assertEqual(0, len(node))
944
118
        self.assertEqual(10, node.maximum_size)
120
        self.assertEqual(10, node.maximum_size)
945
119
        self.assertEqual(("sha1:1234",), node.key())
121
        self.assertEqual(("sha1:1234",), node.key())
946
122
        self.assertIsInstance(node.key(), StaticTuple)
947
120
        self.assertIs(None, node._search_prefix)
123
        self.assertIs(None, node._search_prefix)
948
121
        self.assertIs(None, node._common_serialised_prefix)
124
        self.assertIs(None, node._common_serialised_prefix)
949
122
125
950
@@ -194,7 +197,8 @@
951
194
197
952
195
    def assertDeserialiseErrors(self, text):
198
    def assertDeserialiseErrors(self, text):
953
196
        self.assertRaises((ValueError, IndexError),
199
        self.assertRaises((ValueError, IndexError),
955
197
            self.module._deserialise_internal_node, text, 'not-a-real-sha')
200
            self.module._deserialise_internal_node, text,
956
201
                stuple('not-a-real-sha',))
957
198
202
958
199
    def test_raises_on_non_internal(self):
203
    def test_raises_on_non_internal(self):
959
200
        self.assertDeserialiseErrors('')
204
        self.assertDeserialiseErrors('')
960
@@ -211,7 +215,7 @@
961
211
215
962
212
    def test_deserialise_one(self):
216
    def test_deserialise_one(self):
963
213
        node = self.module._deserialise_internal_node(
217
        node = self.module._deserialise_internal_node(
965
214
            "chknode:\n10\n1\n1\n\na\x00sha1:abcd\n", ('sha1:1234',))
218
            "chknode:\n10\n1\n1\n\na\x00sha1:abcd\n", stuple('sha1:1234',))
966
215
        self.assertIsInstance(node, chk_map.InternalNode)
219
        self.assertIsInstance(node, chk_map.InternalNode)
967
216
        self.assertEqual(1, len(node))
220
        self.assertEqual(1, len(node))
968
217
        self.assertEqual(10, node.maximum_size)
221
        self.assertEqual(10, node.maximum_size)
969
@@ -221,7 +225,7 @@
970
221
225
971
222
    def test_deserialise_with_prefix(self):
226
    def test_deserialise_with_prefix(self):
972
223
        node = self.module._deserialise_internal_node(
227
        node = self.module._deserialise_internal_node(
974
224
            "chknode:\n10\n1\n1\npref\na\x00sha1:abcd\n", ('sha1:1234',))
228
            "chknode:\n10\n1\n1\npref\na\x00sha1:abcd\n", stuple('sha1:1234',))
975
225
        self.assertIsInstance(node, chk_map.InternalNode)
229
        self.assertIsInstance(node, chk_map.InternalNode)
976
226
        self.assertEqual(1, len(node))
230
        self.assertEqual(1, len(node))
977
227
        self.assertEqual(10, node.maximum_size)
231
        self.assertEqual(10, node.maximum_size)
978
@@ -230,7 +234,7 @@
979
230
        self.assertEqual({'prefa': ('sha1:abcd',)}, node._items)
234
        self.assertEqual({'prefa': ('sha1:abcd',)}, node._items)
980
231
235
981
232
        node = self.module._deserialise_internal_node(
236
        node = self.module._deserialise_internal_node(
983
233
            "chknode:\n10\n1\n1\npref\n\x00sha1:abcd\n", ('sha1:1234',))
237
            "chknode:\n10\n1\n1\npref\n\x00sha1:abcd\n", stuple('sha1:1234',))
984
234
        self.assertIsInstance(node, chk_map.InternalNode)
238
        self.assertIsInstance(node, chk_map.InternalNode)
985
235
        self.assertEqual(1, len(node))
239
        self.assertEqual(1, len(node))
986
236
        self.assertEqual(10, node.maximum_size)
240
        self.assertEqual(10, node.maximum_size)
987
@@ -240,7 +244,8 @@
988
240
244
989
241
    def test_deserialise_pref_with_null(self):
245
    def test_deserialise_pref_with_null(self):
990
242
        node = self.module._deserialise_internal_node(
246
        node = self.module._deserialise_internal_node(
992
243
            "chknode:\n10\n1\n1\npref\x00fo\n\x00sha1:abcd\n", ('sha1:1234',))
247
            "chknode:\n10\n1\n1\npref\x00fo\n\x00sha1:abcd\n",
993
248
            stuple('sha1:1234',))
994
244
        self.assertIsInstance(node, chk_map.InternalNode)
249
        self.assertIsInstance(node, chk_map.InternalNode)
995
245
        self.assertEqual(1, len(node))
250
        self.assertEqual(1, len(node))
996
246
        self.assertEqual(10, node.maximum_size)
251
        self.assertEqual(10, node.maximum_size)
997
@@ -250,7 +255,8 @@
998
250
255
999
251
    def test_deserialise_with_null_pref(self):
256
    def test_deserialise_with_null_pref(self):
1000
252
        node = self.module._deserialise_internal_node(
257
        node = self.module._deserialise_internal_node(
1002
253
            "chknode:\n10\n1\n1\npref\x00fo\n\x00\x00sha1:abcd\n", ('sha1:1234',))
258
            "chknode:\n10\n1\n1\npref\x00fo\n\x00\x00sha1:abcd\n",
1003
259
            stuple('sha1:1234',))
1004
254
        self.assertIsInstance(node, chk_map.InternalNode)
260
        self.assertIsInstance(node, chk_map.InternalNode)
1005
255
        self.assertEqual(1, len(node))
261
        self.assertEqual(1, len(node))
1006
256
        self.assertEqual(10, node.maximum_size)
262
        self.assertEqual(10, node.maximum_size)
1007
257
263
1008
=== modified file 'bzrlib/tests/test_chk_map.py'
1009
--- bzrlib/tests/test_chk_map.py	2009-10-08 04:35:01 +0000
1010
+++ bzrlib/tests/test_chk_map.py	2009-10-26 14:59:15 +0000
1011
@@ -31,6 +31,7 @@
1012
31
    LeafNode,
31
    LeafNode,
1013
32
    Node,
32
    Node,
1014
33
    )
33
    )
1015
34
from bzrlib.static_tuple import StaticTuple
1016
34
35
1017
35
36
1018
36
class TestNode(tests.TestCase):
37
class TestNode(tests.TestCase):
1019
@@ -831,13 +832,13 @@
1020
831
        # 'ab' and 'ac' nodes
832
        # 'ab' and 'ac' nodes
1021
832
        chkmap.map(('aad',), 'v')
833
        chkmap.map(('aad',), 'v')
1022
833
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
834
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
1025
834
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
835
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
1026
835
        self.assertIsInstance(chkmap._root_node._items['ac'], tuple)
836
        self.assertIsInstance(chkmap._root_node._items['ac'], StaticTuple)
1027
836
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
837
        # Unmapping 'acd' can notice that 'aa' is an InternalNode and not have
1028
837
        # to map in 'ab'
838
        # to map in 'ab'
1029
838
        chkmap.unmap(('acd',))
839
        chkmap.unmap(('acd',))
1030
839
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
840
        self.assertIsInstance(chkmap._root_node._items['aa'], InternalNode)
1032
840
        self.assertIsInstance(chkmap._root_node._items['ab'], tuple)
841
        self.assertIsInstance(chkmap._root_node._items['ab'], StaticTuple)
1033
841
842
1034
842
    def test_unmap_without_fitting_doesnt_page_in(self):
843
    def test_unmap_without_fitting_doesnt_page_in(self):
1035
843
        store = self.get_chk_bytes()
844
        store = self.get_chk_bytes()
1036
@@ -860,8 +861,8 @@
1037
860
        chkmap.map(('aaf',), 'v')
861
        chkmap.map(('aaf',), 'v')
1038
861
        # At this point, the previous nodes should not be paged in, but the
862
        # At this point, the previous nodes should not be paged in, but the
1039
862
        # newly added nodes would be
863
        # newly added nodes would be
1042
863
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
864
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1043
864
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
865
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1044
865
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
866
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
1045
866
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
867
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
1046
867
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
868
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1047
@@ -869,8 +870,8 @@
1048
869
        # Now unmapping one of the new nodes will use only the already-paged-in
870
        # Now unmapping one of the new nodes will use only the already-paged-in
1049
870
        # nodes to determine that we don't need to do more.
871
        # nodes to determine that we don't need to do more.
1050
871
        chkmap.unmap(('aaf',))
872
        chkmap.unmap(('aaf',))
1053
872
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
873
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1054
873
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
874
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1055
874
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
875
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
1056
875
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
876
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
1057
876
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
877
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1058
@@ -897,9 +898,9 @@
1059
897
        chkmap.map(('aad',), 'v')
898
        chkmap.map(('aad',), 'v')
1060
898
        # At this point, the previous nodes should not be paged in, but the
899
        # At this point, the previous nodes should not be paged in, but the
1061
899
        # newly added node would be
900
        # newly added node would be
1065
900
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
901
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1066
901
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
902
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1067
902
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
903
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
1068
903
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
904
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
1069
904
        # Unmapping the new node will check the existing nodes to see if they
905
        # Unmapping the new node will check the existing nodes to see if they
1070
905
        # would fit.
906
        # would fit.
1071
@@ -937,9 +938,9 @@
1072
937
        chkmap.map(('aad',), 'v')
938
        chkmap.map(('aad',), 'v')
1073
938
        # At this point, the previous nodes should not be paged in, but the
939
        # At this point, the previous nodes should not be paged in, but the
1074
939
        # newly added node would be
940
        # newly added node would be
1078
940
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
941
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1079
941
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
942
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1080
942
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
943
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
1081
943
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
944
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
1082
944
        # Now clear the page cache, and only include 2 of the children in the
945
        # Now clear the page cache, and only include 2 of the children in the
1083
945
        # cache
946
        # cache
1084
@@ -954,7 +955,7 @@
1085
954
        # Unmapping the new node will check the nodes from the page cache
955
        # Unmapping the new node will check the nodes from the page cache
1086
955
        # first, and not have to read in 'aaa'
956
        # first, and not have to read in 'aaa'
1087
956
        chkmap.unmap(('aad',))
957
        chkmap.unmap(('aad',))
1089
957
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
958
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1090
958
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
959
        self.assertIsInstance(chkmap._root_node._items['aab'], LeafNode)
1091
959
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
960
        self.assertIsInstance(chkmap._root_node._items['aac'], LeafNode)
1092
960
961
1093
@@ -974,9 +975,9 @@
1094
974
        chkmap.map(('aaf',), 'val')
975
        chkmap.map(('aaf',), 'val')
1095
975
        # At this point, the previous nodes should not be paged in, but the
976
        # At this point, the previous nodes should not be paged in, but the
1096
976
        # newly added node would be
977
        # newly added node would be
1100
977
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
978
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1101
978
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
979
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1102
979
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
980
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
1103
980
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
981
        self.assertIsInstance(chkmap._root_node._items['aad'], LeafNode)
1104
981
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
982
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1105
982
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
983
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1106
@@ -984,9 +985,9 @@
1107
984
        # Unmapping a new node will see the other nodes that are already in
985
        # Unmapping a new node will see the other nodes that are already in
1108
985
        # memory, and not need to page in anything else
986
        # memory, and not need to page in anything else
1109
986
        chkmap.unmap(('aad',))
987
        chkmap.unmap(('aad',))
1113
987
        self.assertIsInstance(chkmap._root_node._items['aaa'], tuple)
988
        self.assertIsInstance(chkmap._root_node._items['aaa'], StaticTuple)
1114
988
        self.assertIsInstance(chkmap._root_node._items['aab'], tuple)
989
        self.assertIsInstance(chkmap._root_node._items['aab'], StaticTuple)
1115
989
        self.assertIsInstance(chkmap._root_node._items['aac'], tuple)
990
        self.assertIsInstance(chkmap._root_node._items['aac'], StaticTuple)
1116
990
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
991
        self.assertIsInstance(chkmap._root_node._items['aae'], LeafNode)
1117
991
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
992
        self.assertIsInstance(chkmap._root_node._items['aaf'], LeafNode)
1118
992
993
1119
@@ -1031,8 +1032,8 @@
1120
1031
            {('a',): 'content here', ('b',): 'more content'},
1032
            {('a',): 'content here', ('b',): 'more content'},
1121
1032
            chk_bytes=basis._store, maximum_size=10)
1033
            chk_bytes=basis._store, maximum_size=10)
1122
1033
        list(target.iter_changes(basis))
1034
        list(target.iter_changes(basis))
1125
1034
        self.assertIsInstance(target._root_node, tuple)
1035
        self.assertIsInstance(target._root_node, StaticTuple)
1126
1035
        self.assertIsInstance(basis._root_node, tuple)
1036
        self.assertIsInstance(basis._root_node, StaticTuple)
1127
1036
1037
1128
1037
    def test_iter_changes_ab_ab_changed_values_shown(self):
1038
    def test_iter_changes_ab_ab_changed_values_shown(self):
1129
1038
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1039
        basis = self._get_map({('a',): 'content here', ('b',): 'more content'},
1130
@@ -1144,9 +1145,12 @@
1131
1144
1145
1132
1145
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1146
    def test_iteritems_keys_prefixed_by_2_width_nodes_hashed(self):
1133
1146
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
1147
        search_key_func = chk_map.search_key_registry.get('hash-16-way')
1137
1147
        self.assertEqual('E8B7BE43\x00E8B7BE43', search_key_func(('a', 'a')))
1148
        self.assertEqual('E8B7BE43\x00E8B7BE43',
1138
1148
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1149
                         search_key_func(StaticTuple('a', 'a')))
1139
1149
        self.assertEqual('71BEEFF9\x0000000000', search_key_func(('b', '')))
1150
        self.assertEqual('E8B7BE43\x0071BEEFF9',
1140
1151
                         search_key_func(StaticTuple('a', 'b')))
1141
1152
        self.assertEqual('71BEEFF9\x0000000000',
1142
1153
                         search_key_func(StaticTuple('b', '')))
1143
1150
        chkmap = self._get_map(
1154
        chkmap = self._get_map(
1144
1151
            {("a","a"):"content here", ("a", "b",):"more content",
1155
            {("a","a"):"content here", ("a", "b",):"more content",
1145
1152
             ("b", ""): 'boring content'},
1156
             ("b", ""): 'boring content'},
1146
@@ -1449,41 +1453,6 @@
1147
1449
                             , chkmap._dump_tree())
1453
                             , chkmap._dump_tree())
1148
1450
1454
1149
1451
1455
1150
1452
class TestSearchKeyFuncs(tests.TestCase):
1151
1453
1152
1454
    def assertSearchKey16(self, expected, key):
1153
1455
        self.assertEqual(expected, chk_map._search_key_16(key))
1154
1456
1155
1457
    def assertSearchKey255(self, expected, key):
1156
1458
        actual = chk_map._search_key_255(key)
1157
1459
        self.assertEqual(expected, actual, 'actual: %r' % (actual,))
1158
1460
1159
1461
    def test_simple_16(self):
1160
1462
        self.assertSearchKey16('8C736521', ('foo',))
1161
1463
        self.assertSearchKey16('8C736521\x008C736521', ('foo', 'foo'))
1162
1464
        self.assertSearchKey16('8C736521\x0076FF8CAA', ('foo', 'bar'))
1163
1465
        self.assertSearchKey16('ED82CD11', ('abcd',))
1164
1466
1165
1467
    def test_simple_255(self):
1166
1468
        self.assertSearchKey255('\x8cse!', ('foo',))
1167
1469
        self.assertSearchKey255('\x8cse!\x00\x8cse!', ('foo', 'foo'))
1168
1470
        self.assertSearchKey255('\x8cse!\x00v\xff\x8c\xaa', ('foo', 'bar'))
1169
1471
        # The standard mapping for these would include '\n', so it should be
1170
1472
        # mapped to '_'
1171
1473
        self.assertSearchKey255('\xfdm\x93_\x00P_\x1bL', ('<', 'V'))
1172
1474
1173
1475
    def test_255_does_not_include_newline(self):
1174
1476
        # When mapping via _search_key_255, we should never have the '\n'
1175
1477
        # character, but all other 255 values should be present
1176
1478
        chars_used = set()
1177
1479
        for char_in in range(256):
1178
1480
            search_key = chk_map._search_key_255((chr(char_in),))
1179
1481
            chars_used.update(search_key)
1180
1482
        all_chars = set([chr(x) for x in range(256)])
1181
1483
        unused_chars = all_chars.symmetric_difference(chars_used)
1182
1484
        self.assertEqual(set('\n'), unused_chars)
1183
1485
1184
1486
1185
1487
class TestLeafNode(TestCaseWithStore):
1456
class TestLeafNode(TestCaseWithStore):
1186
1488
1457
1187
1489
    def test_current_size_empty(self):
1458
    def test_current_size_empty(self):
1188
@@ -1908,18 +1877,19 @@
1189
1908
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1877
        search_key_func = chk_map.search_key_registry.get('hash-255-way')
1190
1909
        node = InternalNode(search_key_func=search_key_func)
1878
        node = InternalNode(search_key_func=search_key_func)
1191
1910
        leaf1 = LeafNode(search_key_func=search_key_func)
1879
        leaf1 = LeafNode(search_key_func=search_key_func)
1193
1911
        leaf1.map(None, ('foo bar',), 'quux')
1880
        leaf1.map(None, StaticTuple('foo bar',), 'quux')
1194
1912
        leaf2 = LeafNode(search_key_func=search_key_func)
1881
        leaf2 = LeafNode(search_key_func=search_key_func)
1198
1913
        leaf2.map(None, ('strange',), 'beast')
1882
        leaf2.map(None, StaticTuple('strange',), 'beast')
1199
1914
        self.assertEqual('\xbeF\x014', search_key_func(('foo bar',)))
1883
        self.assertEqual('\xbeF\x014', search_key_func(StaticTuple('foo bar',)))
1200
1915
        self.assertEqual('\x85\xfa\xf7K', search_key_func(('strange',)))
1884
        self.assertEqual('\x85\xfa\xf7K', search_key_func(StaticTuple('strange',)))
1201
1916
        node.add_node("\xbe", leaf1)
1885
        node.add_node("\xbe", leaf1)
1202
1917
        # This sets up a path that should not be followed - it will error if
1886
        # This sets up a path that should not be followed - it will error if
1203
1918
        # the code tries to.
1887
        # the code tries to.
1204
1919
        node._items['\xbe'] = None
1888
        node._items['\xbe'] = None
1205
1920
        node.add_node("\x85", leaf2)
1889
        node.add_node("\x85", leaf2)
1206
1921
        self.assertEqual([(('strange',), 'beast')],
1890
        self.assertEqual([(('strange',), 'beast')],
1208
1922
            sorted(node.iteritems(None, [('strange',), ('weird',)])))
1891
            sorted(node.iteritems(None, [StaticTuple('strange',),
1209
1892
                                         StaticTuple('weird',)])))
1210
1923
1893
1211
1924
    def test_iteritems_partial_empty(self):
1894
    def test_iteritems_partial_empty(self):
1212
1925
        node = InternalNode()
1895
        node = InternalNode()
1213
@@ -1932,7 +1902,7 @@
1214
1932
        # Ensure test validity: nothing paged in below the root.
1902
        # Ensure test validity: nothing paged in below the root.
1215
1933
        self.assertEqual(2,
1903
        self.assertEqual(2,
1216
1934
            len([value for value in node._items.values()
1904
            len([value for value in node._items.values()
1218
1935
                if type(value) == tuple]))
1905
                if type(value) is StaticTuple]))
1219
1936
        # now, mapping to k3 should add a k3 leaf
1906
        # now, mapping to k3 should add a k3 leaf
1220
1937
        prefix, nodes = node.map(None, ('k3',), 'quux')
1907
        prefix, nodes = node.map(None, ('k3',), 'quux')
1221
1938
        self.assertEqual("k", prefix)
1908
        self.assertEqual("k", prefix)
1222
@@ -1971,7 +1941,7 @@
1223
1971
        # Ensure test validity: nothing paged in below the root.
1941
        # Ensure test validity: nothing paged in below the root.
1224
1972
        self.assertEqual(2,
1942
        self.assertEqual(2,
1225
1973
            len([value for value in node._items.values()
1943
            len([value for value in node._items.values()
1227
1974
                if type(value) == tuple]))
1944
                if type(value) is StaticTuple]))
1228
1975
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1945
        # now, mapping to k23 causes k22 ('k2' in node) to split into k22 and
1229
1976
        # k23, which for simplicity in the current implementation generates
1946
        # k23, which for simplicity in the current implementation generates
1230
1977
        # a new internal node between node, and k22/k23.
1947
        # a new internal node between node, and k22/k23.
1231
@@ -2016,9 +1986,12 @@
1232
2016
        node = InternalNode(search_key_func=search_key_func)
1986
        node = InternalNode(search_key_func=search_key_func)
1233
2017
        node._key_width = 2
1987
        node._key_width = 2
1234
2018
        node._node_width = 4
1988
        node._node_width = 4
1238
2019
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(('a', 'b')))
1989
        self.assertEqual('E8B7BE43\x0071BEEFF9', search_key_func(
1239
2020
        self.assertEqual('E8B7', node._search_prefix_filter(('a', 'b')))
1990
            StaticTuple('a', 'b')))
1240
2021
        self.assertEqual('E8B7', node._search_prefix_filter(('a',)))
1991
        self.assertEqual('E8B7', node._search_prefix_filter(
1241
1992
            StaticTuple('a', 'b')))
1242
1993
        self.assertEqual('E8B7', node._search_prefix_filter(
1243
1994
            StaticTuple('a',)))
1244
2022
1995
1245
2023
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1996
    def test_unmap_k23_from_k1_k22_k23_gives_k1_k22_tree_new(self):
1246
2024
        chkmap = self._get_map(
1997
        chkmap = self._get_map(
Status:	Merged
Approved by:	Andrew Bennetts on 2009-10-26
Approved revision:	no longer in the source branch.
Merged at revision:	not available
Proposed branch:	lp:~jameinel/bzr/2.1-static-tuple-chk-map
Merge into:	lp:bzr
Diff against target:	1246 lines 10 files modified NEWS (+9/-8) bzrlib/_chk_map_py.py (+4/-3) bzrlib/_chk_map_pyx.pyx (+41/-18) bzrlib/_static_tuple_c.pxd (+5/-1) bzrlib/chk_map.py (+99/-20) bzrlib/groupcompress.py (+18/-1) bzrlib/inventory.py (+28/-20) bzrlib/repofmt/groupcompress_repo.py (+13/-4) bzrlib/tests/test__chk_map.py (+22/-16) bzrlib/tests/test_chk_map.py (+43/-70)
To merge this branch:	bzr merge lp:~jameinel/bzr/2.1-static-tuple-chk-map
Related bugs:	Link a bug report
Reviewer	Review Type	Date Requested	Status
Andrew Bennetts		2009-10-21	Approve on 2009-10-26
Review via email: mp+13740@code.launchpad.net