← Back to branch summary

~hardware-certification/zope3/certify-staging-2.5

« back to all changes in this revision

Viewing changes to src/BTrees/check.py

  • Committer: Marc Tardif
  • Date: 2008-04-26 19:03:34 UTC
  • Revision ID: cr3@lime-20080426190334-u16xo4llz56vliqf
Initial import.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/BTrees/check.py
 
1
##############################################################################
 
2
#
 
3
# Copyright (c) 2003 Zope Corporation and Contributors.
 
4
# All Rights Reserved.
 
5
#
 
6
# This software is subject to the provisions of the Zope Public License,
 
7
# Version 2.1 (ZPL).  A copy of the ZPL should accompany this distribution.
 
8
# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
 
9
# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 
10
# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
 
11
# FOR A PARTICULAR PURPOSE
 
12
#
 
13
##############################################################################
 
14
"""
 
15
Utilities for working with BTrees (TreeSets, Buckets, and Sets) at a low
 
16
level.
 
17
 
 
18
The primary function is check(btree), which performs value-based consistency
 
19
checks of a kind btree._check() does not perform.  See the function docstring
 
20
for details.
 
21
 
 
22
display(btree) displays the internal structure of a BTree (TreeSet, etc) to
 
23
stdout.
 
24
 
 
25
CAUTION:  When a BTree node has only a single bucket child, it can be
 
26
impossible to get at the bucket from Python code (__getstate__() may squash
 
27
the bucket object out of existence, as a pickling storage optimization).  In
 
28
such a case, the code here synthesizes a temporary bucket with the same keys
 
29
(and values, if the bucket is of a mapping type).  This has no first-order
 
30
consequences, but can mislead if you pay close attention to reported object
 
31
addresses and/or object identity (the synthesized bucket has an address
 
32
that doesn't exist in the actual BTree).
 
33
"""
 
34
 
 
35
from types import TupleType
 
36
 
 
37
from BTrees.OOBTree import OOBTree, OOBucket, OOSet, OOTreeSet
 
38
from BTrees.OIBTree import OIBTree, OIBucket, OISet, OITreeSet
 
39
from BTrees.IOBTree import IOBTree, IOBucket, IOSet, IOTreeSet
 
40
from BTrees.IIBTree import IIBTree, IIBucket, IISet, IITreeSet
 
41
from BTrees.IFBTree import IFBTree, IFBucket, IFSet, IFTreeSet
 
42
from BTrees.OLBTree import OLBTree, OLBucket, OLSet, OLTreeSet
 
43
from BTrees.LOBTree import LOBTree, LOBucket, LOSet, LOTreeSet
 
44
from BTrees.LLBTree import LLBTree, LLBucket, LLSet, LLTreeSet
 
45
from BTrees.LFBTree import LFBTree, LFBucket, LFSet, LFTreeSet
 
46
 
 
47
from ZODB.utils import positive_id, oid_repr
 
48
 
 
49
TYPE_UNKNOWN, TYPE_BTREE, TYPE_BUCKET = range(3)
 
50
 
 
51
_type2kind = {}
 
52
for kv in ('OO',
 
53
           'II', 'IO', 'OI', 'IF',
 
54
           'LL', 'LO', 'OL', 'LF',
 
55
           ):
 
56
    for name, kind in (
 
57
        ('BTree', (TYPE_BTREE, True)),
 
58
        ('Bucket', (TYPE_BUCKET, True)),
 
59
        ('TreeSet', (TYPE_BTREE, False)),
 
60
        ('Set', (TYPE_BUCKET, False)),
 
61
        ):
 
62
        _type2kind[globals()[kv+name]] = kind
 
63
 
 
64
# Return pair
 
65
#
 
66
#     TYPE_BTREE or TYPE_BUCKET, is_mapping
 
67
 
 
68
def classify(obj):
 
69
    return _type2kind[type(obj)]
 
70
 
 
71
 
 
72
BTREE_EMPTY, BTREE_ONE, BTREE_NORMAL = range(3)
 
73
 
 
74
# If the BTree is empty, returns
 
75
#
 
76
#     BTREE_EMPTY, [], []
 
77
#
 
78
# If the BTree has only one bucket, sometimes returns
 
79
#
 
80
#     BTREE_ONE, bucket_state, None
 
81
#
 
82
# Else returns
 
83
#
 
84
#     BTREE_NORMAL, list of keys, list of kids
 
85
#
 
86
# and the list of kids has one more entry than the list of keys.
 
87
#
 
88
# BTree.__getstate__() docs:
 
89
#
 
90
# For an empty BTree (self->len == 0), None.
 
91
#
 
92
# For a BTree with one child (self->len == 1), and that child is a bucket,
 
93
# and that bucket has a NULL oid, a one-tuple containing a one-tuple
 
94
# containing the bucket's state:
 
95
#
 
96
#     (
 
97
#         (
 
98
#              child[0].__getstate__(),
 
99
#         ),
 
100
#     )
 
101
#
 
102
# Else a two-tuple.  The first element is a tuple interleaving the BTree's
 
103
# keys and direct children, of size 2*self->len - 1 (key[0] is unused and
 
104
# is not saved).  The second element is the firstbucket:
 
105
#
 
106
#     (
 
107
#          (child[0], key[1], child[1], key[2], child[2], ...,
 
108
#                                       key[len-1], child[len-1]),
 
109
#          self->firstbucket
 
110
#     )
 
111
 
 
112
_btree2bucket = {}
 
113
for kv in ('OO',
 
114
           'II', 'IO', 'OI', 'IF',
 
115
           'LL', 'LO', 'OL', 'LF',
 
116
           ):
 
117
    _btree2bucket[globals()[kv+'BTree']] = globals()[kv+'Bucket']
 
118
    _btree2bucket[globals()[kv+'TreeSet']] = globals()[kv+'Set']
 
119
 
 
120
def crack_btree(t, is_mapping):
 
121
    state = t.__getstate__()
 
122
    if state is None:
 
123
        return BTREE_EMPTY, [], []
 
124
 
 
125
    assert isinstance(state, TupleType)
 
126
    if len(state) == 1:
 
127
        state = state[0]
 
128
        assert isinstance(state, TupleType) and len(state) == 1
 
129
        state = state[0]
 
130
        return BTREE_ONE, state, None
 
131
 
 
132
    assert len(state) == 2
 
133
    data, firstbucket = state
 
134
    n = len(data)
 
135
    assert n & 1
 
136
    kids = []
 
137
    keys = []
 
138
    i = 0
 
139
    for x in data:
 
140
        if i & 1:
 
141
            keys.append(x)
 
142
        else:
 
143
            kids.append(x)
 
144
        i += 1
 
145
    return BTREE_NORMAL, keys, kids
 
146
 
 
147
# Returns
 
148
#
 
149
#     keys, values  # for a mapping; len(keys) == len(values) in this case
 
150
# or
 
151
#     keys, []      # for a set
 
152
#
 
153
# bucket.__getstate__() docs:
 
154
#
 
155
# For a set bucket (self->values is NULL), a one-tuple or two-tuple.  The
 
156
# first element is a tuple of keys, of length self->len.  The second element
 
157
# is the next bucket, present if and only if next is non-NULL:
 
158
#
 
159
#     (
 
160
#          (keys[0], keys[1], ..., keys[len-1]),
 
161
#          <self->next iff non-NULL>
 
162
#     )
 
163
#
 
164
# For a mapping bucket (self->values is not NULL), a one-tuple or two-tuple.
 
165
# The first element is a tuple interleaving keys and values, of length
 
166
# 2 * self->len.  The second element is the next bucket, present iff next is
 
167
# non-NULL:
 
168
#
 
169
#     (
 
170
#          (keys[0], values[0], keys[1], values[1], ...,
 
171
#                               keys[len-1], values[len-1]),
 
172
#          <self->next iff non-NULL>
 
173
#     )
 
174
 
 
175
def crack_bucket(b, is_mapping):
 
176
    state = b.__getstate__()
 
177
    assert isinstance(state, TupleType)
 
178
    assert 1 <= len(state) <= 2
 
179
    data = state[0]
 
180
    if not is_mapping:
 
181
        return data, []
 
182
    keys = []
 
183
    values = []
 
184
    n = len(data)
 
185
    assert n & 1 == 0
 
186
    i = 0
 
187
    for x in data:
 
188
        if i & 1:
 
189
            values.append(x)
 
190
        else:
 
191
            keys.append(x)
 
192
        i += 1
 
193
    return keys, values
 
194
 
 
195
def type_and_adr(obj):
 
196
    if hasattr(obj, '_p_oid'):
 
197
        oid = oid_repr(obj._p_oid)
 
198
    else:
 
199
        oid = 'None'
 
200
    return "%s (0x%x oid=%s)" % (type(obj).__name__, positive_id(obj), oid)
 
201
 
 
202
# Walker implements a depth-first search of a BTree (or TreeSet or Set or
 
203
# Bucket).  Subclasses must implement the visit_btree() and visit_bucket()
 
204
# methods, and arrange to call the walk() method.  walk() calls the
 
205
# visit_XYZ() methods once for each node in the tree, in depth-first
 
206
# left-to-right order.
 
207
 
 
208
class Walker:
 
209
    def __init__(self, obj):
 
210
        self.obj = obj
 
211
 
 
212
    # obj is the BTree (BTree or TreeSet).
 
213
    # path is a list of indices, from the root.  For example, if a BTree node
 
214
    # is child[5] of child[3] of the root BTree, [3, 5].
 
215
    # parent is the parent BTree object, or None if this is the root BTree.
 
216
    # is_mapping is True for a BTree and False for a TreeSet.
 
217
    # keys is a list of the BTree's internal keys.
 
218
    # kids is a list of the BTree's children.
 
219
    # If the BTree is an empty root node, keys == kids == [].
 
220
    # Else len(kids) == len(keys) + 1.
 
221
    # lo and hi are slice bounds on the values the elements of keys *should*
 
222
    # lie in (lo inclusive, hi exclusive).  lo is None if there is no lower
 
223
    # bound known, and hi is None if no upper bound is known.
 
224
 
 
225
    def visit_btree(self, obj, path, parent, is_mapping,
 
226
                    keys, kids, lo, hi):
 
227
        raise NotImplementedError
 
228
 
 
229
    # obj is the bucket (Bucket or Set).
 
230
    # path is a list of indices, from the root.  For example, if a bucket
 
231
    # node is child[5] of child[3] of the root BTree, [3, 5].
 
232
    # parent is the parent BTree object.
 
233
    # is_mapping is True for a Bucket and False for a Set.
 
234
    # keys is a list of the bucket's keys.
 
235
    # values is a list of the bucket's values.
 
236
    # If is_mapping is false, values == [].  Else len(keys) == len(values).
 
237
    # lo and hi are slice bounds on the values the elements of keys *should*
 
238
    # lie in (lo inclusive, hi exclusive).  lo is None if there is no lower
 
239
    # bound known, and hi is None if no upper bound is known.
 
240
 
 
241
    def visit_bucket(self, obj, path, parent, is_mapping,
 
242
                     keys, values, lo, hi):
 
243
        raise NotImplementedError
 
244
 
 
245
    def walk(self):
 
246
        obj = self.obj
 
247
        path = []
 
248
        stack = [(obj, path, None, None, None)]
 
249
        while stack:
 
250
            obj, path, parent, lo, hi = stack.pop()
 
251
            kind, is_mapping = classify(obj)
 
252
            if kind is TYPE_BTREE:
 
253
                bkind, keys, kids = crack_btree(obj, is_mapping)
 
254
                if bkind is BTREE_NORMAL:
 
255
                    # push the kids, in reverse order (so they're popped off
 
256
                    # the stack in forward order)
 
257
                    n = len(kids)
 
258
                    for i in range(len(kids)-1, -1, -1):
 
259
                        newlo, newhi = lo,  hi
 
260
                        if i < n-1:
 
261
                            newhi = keys[i]
 
262
                        if i > 0:
 
263
                            newlo = keys[i-1]
 
264
                        stack.append((kids[i],
 
265
                                      path + [i],
 
266
                                      obj,
 
267
                                      newlo,
 
268
                                      newhi))
 
269
 
 
270
                elif bkind is BTREE_EMPTY:
 
271
                    pass
 
272
                else:
 
273
                    assert bkind is BTREE_ONE
 
274
                    # Yuck.  There isn't a bucket object to pass on, as
 
275
                    # the bucket state is embedded directly in the BTree
 
276
                    # state.  Synthesize a bucket.
 
277
                    assert kids is None   # and "keys" is really the bucket
 
278
                                          # state
 
279
                    bucket = _btree2bucket[type(obj)]()
 
280
                    bucket.__setstate__(keys)
 
281
                    stack.append((bucket,
 
282
                                  path + [0],
 
283
                                  obj,
 
284
                                  lo,
 
285
                                  hi))
 
286
                    keys = []
 
287
                    kids = [bucket]
 
288
 
 
289
                self.visit_btree(obj,
 
290
                                 path,
 
291
                                 parent,
 
292
                                 is_mapping,
 
293
                                 keys,
 
294
                                 kids,
 
295
                                 lo,
 
296
                                 hi)
 
297
            else:
 
298
                assert kind is TYPE_BUCKET
 
299
                keys, values = crack_bucket(obj, is_mapping)
 
300
                self.visit_bucket(obj,
 
301
                                  path,
 
302
                                  parent,
 
303
                                  is_mapping,
 
304
                                  keys,
 
305
                                  values,
 
306
                                  lo,
 
307
                                  hi)
 
308
 
 
309
 
 
310
class Checker(Walker):
 
311
    def __init__(self, obj):
 
312
        Walker.__init__(self, obj)
 
313
        self.errors = []
 
314
 
 
315
    def check(self):
 
316
        self.walk()
 
317
        if self.errors:
 
318
            s = "Errors found in %s:" % type_and_adr(self.obj)
 
319
            self.errors.insert(0, s)
 
320
            s = "\n".join(self.errors)
 
321
            raise AssertionError(s)
 
322
 
 
323
    def visit_btree(self, obj, path, parent, is_mapping,
 
324
                    keys, kids, lo, hi):
 
325
        self.check_sorted(obj, path, keys, lo, hi)
 
326
 
 
327
    def visit_bucket(self, obj, path, parent, is_mapping,
 
328
                     keys, values, lo, hi):
 
329
        self.check_sorted(obj, path, keys, lo, hi)
 
330
 
 
331
    def check_sorted(self, obj, path, keys, lo, hi):
 
332
        i, n = 0, len(keys)
 
333
        for x in keys:
 
334
            if lo is not None and not lo <= x:
 
335
                s = "key %r < lower bound %r at index %d" % (x, lo, i)
 
336
                self.complain(s, obj, path)
 
337
            if hi is not None and not x < hi:
 
338
                s = "key %r >= upper bound %r at index %d" % (x, hi, i)
 
339
                self.complain(s, obj, path)
 
340
            if i < n-1 and not x < keys[i+1]:
 
341
                s = "key %r at index %d >= key %r at index %d" % (
 
342
                    x, i, keys[i+1], i+1)
 
343
                self.complain(s, obj, path)
 
344
            i += 1
 
345
 
 
346
    def complain(self, msg, obj, path):
 
347
        s = "%s, in %s, path from root %s" % (
 
348
                msg,
 
349
                type_and_adr(obj),
 
350
                ".".join(map(str, path)))
 
351
        self.errors.append(s)
 
352
 
 
353
class Printer(Walker):
 
354
    def __init__(self, obj):
 
355
        Walker.__init__(self, obj)
 
356
 
 
357
    def display(self):
 
358
        self.walk()
 
359
 
 
360
    def visit_btree(self, obj, path, parent, is_mapping,
 
361
                    keys, kids, lo, hi):
 
362
        indent = "    " * len(path)
 
363
        print "%s%s %s with %d children" % (
 
364
                  indent,
 
365
                  ".".join(map(str, path)),
 
366
                  type_and_adr(obj),
 
367
                  len(kids))
 
368
        indent += "    "
 
369
        n = len(keys)
 
370
        for i in range(n):
 
371
            print "%skey %d: %r" % (indent, i, keys[i])
 
372
 
 
373
    def visit_bucket(self, obj, path, parent, is_mapping,
 
374
                     keys, values, lo, hi):
 
375
        indent = "    " * len(path)
 
376
        print "%s%s %s with %d keys" % (
 
377
                  indent,
 
378
                  ".".join(map(str, path)),
 
379
                  type_and_adr(obj),
 
380
                  len(keys))
 
381
        indent += "    "
 
382
        n = len(keys)
 
383
        for i in range(n):
 
384
            print "%skey %d: %r" % (indent, i, keys[i]),
 
385
            if is_mapping:
 
386
                print "value %r" % (values[i],)
 
387
 
 
388
def check(btree):
 
389
    """Check internal value-based invariants in a BTree or TreeSet.
 
390
 
 
391
    The btree._check() method checks internal C-level pointer consistency.
 
392
    The check() function here checks value-based invariants:  whether the
 
393
    keys in leaf bucket and internal nodes are in strictly increasing order,
 
394
    and whether they all lie in their expected range.  The latter is a subtle
 
395
    invariant that can't be checked locally -- it requires propagating
 
396
    range info down from the root of the tree, and modifying it at each
 
397
    level for each child.
 
398
 
 
399
    Raises AssertionError if anything is wrong, with a string detail
 
400
    explaining the problems.  The entire tree is checked before
 
401
    AssertionError is raised, and the string detail may be large (depending
 
402
    on how much went wrong).
 
403
    """
 
404
 
 
405
    Checker(btree).check()
 
406
 
 
407
def display(btree):
 
408
    "Display the internal structure of a BTree, Bucket, TreeSet or Set."
 
409
    Printer(btree).display()