1############################################################################## 2# 3# Copyright 2011 Zope Foundation 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"""Python BTree implementation 15""" 16 17 18 19from persistent import Persistent 20 21from .Interfaces import BTreesConflictError 22from ._compat import PY3 23from ._compat import compare 24from ._compat import xrange 25 26# XXX: Fix these. These ignores are temporary to 27# reduce the noise and help find specific issues during 28# refactoring 29# pylint:disable=too-many-lines,fixme,protected-access 30# pylint:disable=attribute-defined-outside-init,redefined-builtin,no-else-return 31# pylint:disable=redefined-outer-name,bad-continuation,unused-variable 32# pylint:disable=too-many-branches,too-many-statements,arguments-differ,assigning-non-slot 33# pylint:disable=superfluous-parens,inconsistent-return-statements,unidiomatic-typecheck 34# pylint:disable=deprecated-method,consider-using-enumerate 35 36_marker = object() 37 38 39class _Base(Persistent): 40 41 __slots__ = () 42 # This is used to allocate storage for the keys. 43 # It's probably here so that we could, for example, use 44 # an ``array.array`` for native types. But nothing actually does 45 # that, everything is stored boxed. 46 # TODO: Figure out why not. 47 _key_type = list 48 49 def __init__(self, items=None): 50 self.clear() 51 if items: 52 self.update(items) 53 54 try: 55 # Detect the presence of the C extensions. 56 # If they're NOT around, we don't need to do any of the 57 # special pickle support to make Python versions look like 58 # C---we just rename the classes. By not defining these methods, 59 # we can (theoretically) avoid a bit of a slowdown. 60 # If the C extensions are around, we do need these methods, but 61 # these classes are unlikely to be used in production anyway. 62 __import__('BTrees._OOBTree') 63 except ImportError: # pragma: no cover 64 pass 65 else: 66 def __reduce__(self): 67 # Swap out the type constructor for the C version, if present. 68 func, typ_gna, state = Persistent.__reduce__(self) 69 # We ignore the returned type altogether in favor of 70 # our calculated class (which allows subclasses but replaces our exact 71 # type with the C equivalent) 72 typ = self.__class__ 73 gna = typ_gna[1:] 74 return (func, (typ,) + gna, state) 75 76 @property 77 def __class__(self): 78 type_self = type(self) 79 return type_self._BTree_reduce_as if type_self._BTree_reduce_up_bound is type_self else type_self 80 81 @property 82 def _BTree_reduce_as(self): 83 # Return the pickle replacement class for this object. 84 # If the C extensions are available, this will be the 85 # C type (setup by _fix_pickle), otherwise it will be the real 86 # type of this object. 87 # This implementation is replaced by _fix_pickle and exists for 88 # testing purposes. 89 return type(self) # pragma: no cover 90 91 _BTree_reduce_up_bound = _BTree_reduce_as 92 93class _ArithmeticMixin(object): 94 def __sub__(self, other): 95 return difference(self.__class__, self, other) 96 97 def __rsub__(self, other): 98 return difference(self._set_type, type(self)(other), self) 99 100 def __or__(self, other): 101 return union(self._set_type, self, other) 102 103 __ror__ = __or__ 104 105 def __and__(self, other): 106 return intersection(self._set_type, self, other) 107 108 __rand__ = __and__ 109 110 def __xor__(self, other): 111 return (self - other) | (other - self) 112 113 __rxor__ = __xor__ 114 115 116class _BucketBase(_ArithmeticMixin, _Base): 117 118 __slots__ = ('_keys', 119 '_next', 120 '_to_key', 121 ) 122 123 def clear(self): 124 self._keys = self._key_type() 125 self._next = None 126 127 def __len__(self): 128 return len(self._keys) 129 130 @property 131 def size(self): 132 return len(self._keys) 133 134 def _deleteNextBucket(self): 135 next = self._next 136 if next is not None: 137 self._next = next._next 138 139 def _search(self, key): 140 # Return non-negative index on success 141 # return -(insertion_index + 1) on fail 142 low = 0 143 keys = self._keys 144 high = len(keys) 145 while low < high: 146 i = (low + high) // 2 147 k = keys[i] 148 if k is key or k == key: 149 return i 150 151 if compare(k, key) < 0: 152 low = i + 1 153 else: 154 high = i 155 return -1 - low 156 157 def minKey(self, key=_marker): 158 if key is _marker or key is None: 159 return self._keys[0] 160 key = self._to_key(key) 161 index = self._search(key) 162 if index >= 0: 163 return key 164 index = -index - 1 165 if index < len(self._keys): 166 return self._keys[index] 167 else: 168 raise ValueError("no key satisfies the conditions") 169 170 def maxKey(self, key=_marker): 171 if key is _marker or key is None: 172 return self._keys[-1] 173 key = self._to_key(key) 174 index = self._search(key) 175 if index >= 0: 176 return key 177 else: 178 index = -index-1 179 if index: 180 return self._keys[index-1] 181 else: 182 raise ValueError("no key satisfies the conditions") 183 184 def _range(self, min=_marker, max=_marker, 185 excludemin=False, excludemax=False): 186 if min is _marker or min is None: 187 start = 0 188 if excludemin: 189 start = 1 190 else: 191 min = self._to_key(min) 192 start = self._search(min) 193 if start >= 0: 194 if excludemin: 195 start += 1 196 else: 197 start = -start - 1 198 if max is _marker or max is None: 199 end = len(self._keys) 200 if excludemax: 201 end -= 1 202 else: 203 max = self._to_key(max) 204 end = self._search(max) 205 if end >= 0: 206 if not excludemax: 207 end += 1 208 else: 209 end = -end - 1 210 211 return start, end 212 213 def keys(self, *args, **kw): 214 start, end = self._range(*args, **kw) 215 return self._keys[start:end] 216 217 def iterkeys(self, *args, **kw): 218 if not (args or kw): 219 return iter(self._keys) 220 keys = self._keys 221 return (keys[i] for i in xrange(*self._range(*args, **kw))) 222 223 def __iter__(self): 224 return iter(self._keys) 225 226 def __contains__(self, key): 227 try: 228 tree_key = self._to_key(key) 229 except TypeError: 230 # Can't convert the key, so can't possibly be in the tree 231 return False 232 233 return (self._search(tree_key) >= 0) 234 235 has_key = __contains__ 236 237 def _repr_helper(self, items): 238 type_self = type(self) 239 mod = type_self.__module__ 240 name = type_self.__name__ 241 name = name[:-2] if name.endswith("Py") else name 242 return "%s.%s(%r)" % (mod, name, items) 243 244 245class _SetIteration(object): 246 247 __slots__ = ('to_iterate', 248 'useValues', 249 '_iter', 250 'active', 251 'position', 252 'key', 253 'value', 254 ) 255 256 257 def __init__(self, to_iterate, useValues=False, default=None, sort=False): 258 if to_iterate is None: 259 to_iterate = () 260 self.to_iterate = to_iterate 261 if sort: 262 # Sorting is required for arbitrary iterables in the 263 # set functions like difference/union/intersection 264 assert not useValues 265 if not isinstance(to_iterate, _Base): 266 # We know _Base (Set, Bucket, Tree, TreeSet) will all 267 # iterate in sorted order. Other than that, we have no guarantee. 268 self.to_iterate = to_iterate = sorted(self.to_iterate) 269 270 if useValues: 271 try: 272 itmeth = to_iterate.iteritems 273 except AttributeError: 274 if PY3 and isinstance(to_iterate, dict): #pragma no cover Py3k 275 itmeth = to_iterate.items().__iter__ 276 else: 277 itmeth = to_iterate.__iter__ 278 useValues = False 279 else: 280 self.value = None 281 else: 282 itmeth = to_iterate.__iter__ 283 284 self.useValues = useValues 285 self._iter = itmeth() 286 self.active = True 287 self.position = 0 288 self.key = _marker 289 self.value = default 290 self.advance() 291 292 def advance(self): 293 try: 294 if self.useValues: 295 self.key, self.value = next(self._iter) 296 else: 297 self.key = next(self._iter) 298 self.position += 1 299 except StopIteration: 300 self.active = False 301 self.position = -1 302 303 return self 304 305class _MutableMappingMixin(object): 306 # Methods defined in collections.abc.MutableMapping that 307 # Bucket and Tree should both implement and can implement 308 # the same. We don't want to extend that class though, 309 # as the C version cannot. 310 def popitem(self): 311 """ 312 D.popitem() -> (k, v), remove and return some (key, value) pair 313 as a 2-tuple; but raise KeyError if D is empty. 314 """ 315 try: 316 key = next(iter(self)) 317 except StopIteration: 318 raise KeyError 319 value = self[key] 320 del self[key] 321 return key, value 322 323 324class Bucket(_MutableMappingMixin, _BucketBase): 325 326 __slots__ = () 327 _value_type = list 328 _to_value = lambda self, x: x 329 VALUE_SAME_CHECK = False 330 331 def setdefault(self, key, value): 332 key, value = self._to_key(key), self._to_value(value) 333 status, value = self._set(key, value, True) 334 return value 335 336 def pop(self, key, default=_marker): 337 try: 338 status, value = self._del(self._to_key(key)) 339 except KeyError: 340 if default is _marker: 341 raise 342 return default 343 else: 344 return value 345 346 def update(self, items): 347 if hasattr(items, 'iteritems'): 348 items = items.iteritems() 349 elif hasattr(items, 'items'): 350 items = items.items() 351 352 _si = self.__setitem__ 353 try: 354 for key, value in items: 355 _si(key, value) 356 except ValueError: 357 raise TypeError('items must be a sequence of 2-tuples') 358 359 def __setitem__(self, key, value): 360 self._set(self._to_key(key), self._to_value(value)) 361 362 def __delitem__(self, key): 363 self._del(self._to_key(key)) 364 365 def clear(self): 366 _BucketBase.clear(self) 367 self._values = self._value_type() 368 369 def get(self, key, default=None): 370 try: 371 key = self._to_key(key) 372 except TypeError: 373 # Can't convert, cannot possibly be present. 374 return default 375 index = self._search(key) 376 if index < 0: 377 return default 378 return self._values[index] 379 380 def __getitem__(self, key): 381 try: 382 tree_key = self._to_key(key) 383 except TypeError: 384 # Can't convert, so cannot possibly be present. 385 raise KeyError(key) 386 index = self._search(tree_key) 387 if index < 0: 388 raise KeyError(key) 389 return self._values[index] 390 391 def _set(self, key, value, ifunset=False): 392 """Set a value 393 394 Return: status, value 395 396 Status is: 397 None if no change 398 0 if change, but not size change 399 1 if change and size change 400 """ 401 index = self._search(key) 402 if index >= 0: 403 if (ifunset or 404 self.VALUE_SAME_CHECK and value == self._values[index] 405 ): 406 return None, self._values[index] 407 self._p_changed = True 408 self._values[index] = value 409 return 0, value 410 else: 411 self._p_changed = True 412 index = -index - 1 413 self._keys.insert(index, key) 414 self._values.insert(index, value) 415 return 1, value 416 417 def _del(self, key): 418 index = self._search(key) 419 if index >= 0: 420 self._p_changed = True 421 del self._keys[index] 422 return 0, self._values.pop(index) 423 raise KeyError(key) 424 425 def _split(self, index=-1): 426 if index < 0 or index >= len(self._keys): 427 index = len(self._keys) // 2 428 new_instance = type(self)() 429 new_instance._keys = self._keys[index:] 430 new_instance._values = self._values[index:] 431 del self._keys[index:] 432 del self._values[index:] 433 new_instance._next = self._next 434 self._next = new_instance 435 return new_instance 436 437 def values(self, *args, **kw): 438 start, end = self._range(*args, **kw) 439 return self._values[start:end] 440 441 def itervalues(self, *args, **kw): 442 values = self._values 443 return (values[i] for i in xrange(*self._range(*args, **kw))) 444 445 def items(self, *args, **kw): 446 keys = self._keys 447 values = self._values 448 return [(keys[i], values[i]) 449 for i in xrange(*self._range(*args, **kw))] 450 451 def iteritems(self, *args, **kw): 452 keys = self._keys 453 values = self._values 454 return ((keys[i], values[i]) 455 for i in xrange(*self._range(*args, **kw))) 456 457 def __getstate__(self): 458 keys = self._keys 459 values = self._values 460 data = [] 461 for i in range(len(keys)): 462 data.append(keys[i]) 463 data.append(values[i]) 464 data = tuple(data) 465 466 if self._next is not None: 467 return data, self._next 468 return (data, ) 469 470 def __setstate__(self, state): 471 if not isinstance(state[0], tuple): 472 raise TypeError("tuple required for first state element") 473 474 self.clear() 475 if len(state) == 2: 476 state, self._next = state 477 else: 478 self._next = None 479 state = state[0] 480 481 keys = self._keys 482 values = self._values 483 for i in range(0, len(state), 2): 484 keys.append(state[i]) 485 values.append(state[i+1]) 486 487 def _p_resolveConflict(self, s_old, s_com, s_new): 488 b_old = type(self)() 489 if s_old is not None: 490 b_old.__setstate__(s_old) 491 b_com = type(self)() 492 if s_com is not None: 493 b_com.__setstate__(s_com) 494 b_new = type(self)() 495 if s_new is not None: 496 b_new.__setstate__(s_new) 497 if (b_com._next != b_old._next or 498 b_new._next != b_old._next): 499 raise BTreesConflictError(-1, -1, -1, 0) 500 501 if not b_com or not b_new: 502 raise BTreesConflictError(-1, -1, -1, 12) 503 504 i_old = _SetIteration(b_old, True) 505 i_com = _SetIteration(b_com, True) 506 i_new = _SetIteration(b_new, True) 507 508 def merge_error(reason): 509 return BTreesConflictError( 510 i_old.position, i_com.position, i_new.position, reason) 511 512 result = type(self)() 513 514 def merge_output(it): 515 result._keys.append(it.key) 516 result._values.append(it.value) 517 it.advance() 518 519 while i_old.active and i_com.active and i_new.active: 520 cmpOC = compare(i_old.key, i_com.key) 521 cmpON = compare(i_old.key, i_new.key) 522 if cmpOC == 0: 523 if cmpON == 0: 524 if i_com.value == i_old.value: 525 result[i_old.key] = i_new.value 526 elif i_new.value == i_old.value: 527 result[i_old.key] = i_com.value 528 else: 529 raise merge_error(1) 530 i_old.advance() 531 i_com.advance() 532 i_new.advance() 533 elif (cmpON > 0): # insert in new 534 merge_output(i_new) 535 elif i_old.value == i_com.value: # deleted new 536 if i_new.position == 1: 537 # Deleted the first item. This will modify the 538 # parent node, so we don't know if merging will be 539 # safe 540 raise merge_error(13) 541 i_old.advance() 542 i_com.advance() 543 else: 544 raise merge_error(2) 545 elif cmpON == 0: 546 if cmpOC > 0: # insert committed 547 merge_output(i_com) 548 elif i_old.value == i_new.value: # delete committed 549 if i_com.position == 1: 550 # Deleted the first item. This will modify the 551 # parent node, so we don't know if merging will be 552 # safe 553 raise merge_error(13) 554 i_old.advance() 555 i_new.advance() 556 else: 557 raise merge_error(3) 558 else: # both keys changed 559 cmpCN = compare(i_com.key, i_new.key) 560 if cmpCN == 0: # dueling insert 561 raise merge_error(4) 562 if cmpOC > 0: # insert committed 563 if cmpCN > 0: # insert i_new first 564 merge_output(i_new) 565 else: 566 merge_output(i_com) 567 elif cmpON > 0: # insert i_new 568 merge_output(i_new) 569 else: 570 raise merge_error(5) # both deleted same key 571 572 while i_com.active and i_new.active: # new inserts 573 cmpCN = compare(i_com.key, i_new.key) 574 if cmpCN == 0: 575 raise merge_error(6) # dueling insert 576 if cmpCN > 0: # insert new 577 merge_output(i_new) 578 else: # insert committed 579 merge_output(i_com) 580 581 while i_old.active and i_com.active: # new deletes rest of original 582 cmpOC = compare(i_old.key, i_com.key) 583 if cmpOC > 0: # insert committed 584 merge_output(i_com) 585 elif cmpOC == 0 and (i_old.value == i_com.value): # del in new 586 i_old.advance() 587 i_com.advance() 588 else: # dueling deletes or delete and change 589 raise merge_error(7) 590 591 while i_old.active and i_new.active: 592 # committed deletes rest of original 593 cmpON = compare(i_old.key, i_new.key) 594 if cmpON > 0: # insert new 595 merge_output(i_new) 596 elif cmpON == 0 and (i_old.value == i_new.value): 597 # deleted in committed 598 i_old.advance() 599 i_new.advance() 600 else: # dueling deletes or delete and change 601 raise merge_error(8) 602 603 if i_old.active: # dueling deletes 604 raise merge_error(9) 605 606 while i_com.active: 607 merge_output(i_com) 608 609 while i_new.active: 610 merge_output(i_new) 611 612 if len(result._keys) == 0: #pragma: no cover 613 # If the output bucket is empty, conflict resolution doesn't have 614 # enough info to unlink it from its containing BTree correctly. 615 # 616 # XXX TS, 2012-11-16: I don't think this is possible 617 # 618 raise merge_error(10) 619 620 result._next = b_old._next 621 return result.__getstate__() 622 623 def __repr__(self): 624 return self._repr_helper(self.items()) 625 626class _MutableSetMixin(object): 627 # Like _MutableMappingMixin, but for sets. 628 def isdisjoint(self, other): 629 """ 630 Return True if two sets have a null intersection. 631 """ 632 for value in other: 633 if value in self: 634 return False 635 return True 636 637 def discard(self, key): 638 """ 639 Remove an element from the set if it is a member. 640 641 If not, do nothing and raise no exception. 642 """ 643 # Written this way to avoid catching and accidentally 644 # ignoring POSKeyError. 645 if key in self: 646 self.remove(key) 647 648 def pop(self): 649 """Return the popped value. Raise KeyError if empty.""" 650 # Get our iter first to avoid catching and accidentally 651 # ignoring POSKeyError 652 it = iter(self) 653 try: 654 value = next(it) 655 except StopIteration: 656 raise KeyError 657 self.discard(value) 658 return value 659 660 def __ior__(self, it): 661 self.update(it) 662 return self 663 664 def __iand__(self, it): 665 for value in (self - it): 666 self.discard(value) 667 return self 668 669 def __isub__(self, it): 670 if it is self: 671 self.clear() 672 else: 673 for value in it: 674 self.discard(value) 675 return self 676 677 def __ixor__(self, it): 678 if it is self: 679 self.clear() 680 else: 681 for value in it: 682 if value in self: 683 self.discard(value) 684 else: 685 self.add(value) 686 return self 687 688 689class Set(_MutableSetMixin, _BucketBase): 690 691 __slots__ = () 692 693 def add(self, key): 694 return self._set(self._to_key(key))[0] 695 696 insert = add 697 698 def remove(self, key): 699 self._del(self._to_key(key)) 700 701 def update(self, items): 702 add = self.add 703 for i in items: 704 add(i) 705 706 def __getstate__(self): 707 data = tuple(self._keys) 708 if self._next is not None: 709 return data, self._next 710 return (data, ) 711 712 def __setstate__(self, state): 713 if not isinstance(state[0], tuple): 714 raise TypeError('tuple required for first state element') 715 716 self.clear() 717 if len(state) == 2: 718 state, self._next = state 719 else: 720 self._next = None 721 state = state[0] 722 723 self._keys.extend(state) 724 725 726 def _set(self, key, value=None, ifunset=False): 727 index = self._search(key) 728 if index < 0: 729 index = -index - 1 730 self._p_changed = True 731 self._keys.insert(index, key) 732 return True, None 733 return False, None 734 735 def _del(self, key): 736 index = self._search(key) 737 if index >= 0: 738 self._p_changed = True 739 del self._keys[index] 740 return 0, 0 741 raise KeyError(key) 742 743 def __getitem__(self, i): 744 return self._keys[i] 745 746 def _split(self, index=-1): 747 if index < 0 or index >= len(self._keys): 748 index = len(self._keys) // 2 749 new_instance = type(self)() 750 new_instance._keys = self._keys[index:] 751 del self._keys[index:] 752 new_instance._next = self._next 753 self._next = new_instance 754 return new_instance 755 756 def _p_resolveConflict(self, s_old, s_com, s_new): 757 758 b_old = type(self)() 759 if s_old is not None: 760 b_old.__setstate__(s_old) 761 b_com = type(self)() 762 if s_com is not None: 763 b_com.__setstate__(s_com) 764 b_new = type(self)() 765 if s_new is not None: 766 b_new.__setstate__(s_new) 767 768 if (b_com._next != b_old._next or 769 b_new._next != b_old._next): # conflict: com or new changed _next 770 raise BTreesConflictError(-1, -1, -1, 0) 771 772 if not b_com or not b_new: # conflict: com or new empty 773 raise BTreesConflictError(-1, -1, -1, 12) 774 775 i_old = _SetIteration(b_old, True) 776 i_com = _SetIteration(b_com, True) 777 i_new = _SetIteration(b_new, True) 778 779 def merge_error(reason): 780 return BTreesConflictError( 781 i_old.position, i_com.position, i_new.position, reason) 782 783 result = type(self)() 784 785 def merge_output(it): 786 result._keys.append(it.key) 787 it.advance() 788 789 while i_old.active and i_com.active and i_new.active: 790 cmpOC = compare(i_old.key, i_com.key) 791 cmpON = compare(i_old.key, i_new.key) 792 if cmpOC == 0: 793 if cmpON == 0: # all match 794 merge_output(i_old) 795 i_com.advance() 796 i_new.advance() 797 elif cmpON > 0: # insert in new 798 merge_output(i_new) 799 else: # deleted new 800 if i_new.position == 1: 801 # Deleted the first item. This will modify the 802 # parent node, so we don't know if merging will be 803 # safe 804 raise merge_error(13) 805 i_old.advance() 806 i_com.advance() 807 elif cmpON == 0: 808 if cmpOC > 0: # insert committed 809 merge_output(i_com) 810 else: # delete committed 811 if i_com.position == 1: 812 # Deleted the first item. This will modify the 813 # parent node, so we don't know if merging will be 814 # safe 815 raise merge_error(13) 816 i_old.advance() 817 i_new.advance() 818 else: # both com and new keys changed 819 cmpCN = compare(i_com.key, i_new.key) 820 if cmpCN == 0: # both inserted same key 821 raise merge_error(4) 822 if cmpOC > 0: # insert committed 823 if cmpCN > 0: # insert i_new first 824 merge_output(i_new) 825 else: 826 merge_output(i_com) 827 elif cmpON > 0: # insert i_new 828 merge_output(i_new) 829 else: # both com and new deleted same key 830 raise merge_error(5) 831 832 while i_com.active and i_new.active: # new inserts 833 cmpCN = compare(i_com.key, i_new.key) 834 if cmpCN == 0: # dueling insert 835 raise merge_error(6) 836 if cmpCN > 0: # insert new 837 merge_output(i_new) 838 else: # insert committed 839 merge_output(i_com) 840 841 while i_old.active and i_com.active: # new deletes rest of original 842 cmpOC = compare(i_old.key, i_com.key) 843 if cmpOC > 0: # insert committed 844 merge_output(i_com) 845 elif cmpOC == 0: # del in new 846 i_old.advance() 847 i_com.advance() 848 else: # dueling deletes or delete and change 849 raise merge_error(7) 850 851 while i_old.active and i_new.active: 852 # committed deletes rest of original 853 cmpON = compare(i_old.key, i_new.key) 854 if cmpON > 0: # insert new 855 merge_output(i_new) 856 elif cmpON == 0: # deleted in committed 857 i_old.advance() 858 i_new.advance() 859 else: # dueling deletes or delete and change 860 raise merge_error(8) 861 862 if i_old.active: # dueling deletes 863 raise merge_error(9) 864 865 while i_com.active: 866 merge_output(i_com) 867 868 while i_new.active: 869 merge_output(i_new) 870 871 if len(result._keys) == 0: #pragma: no cover 872 # If the output bucket is empty, conflict resolution doesn't have 873 # enough info to unlink it from its containing BTree correctly. 874 # 875 # XXX TS, 2012-11-16: I don't think this is possible 876 # 877 raise merge_error(10) 878 879 result._next = b_old._next 880 return result.__getstate__() 881 882 def __repr__(self): 883 return self._repr_helper(self._keys) 884 885class _TreeItem(object): 886 887 __slots__ = ('key', 888 'child', 889 ) 890 891 def __init__(self, key, child): 892 self.key = key 893 self.child = child 894 895 896class _Tree(_ArithmeticMixin, _Base): 897 898 __slots__ = ('_data', 899 '_firstbucket', 900 ) 901 902 def __new__(cls, *args): 903 value = _Base.__new__(cls, *args) 904 # Empty trees don't get their __setstate__ called upon 905 # unpickling (or __init__, obviously), so clear() is never called 906 # and _data and _firstbucket are never defined, unless we do it here. 907 value._data = [] 908 value._firstbucket = None 909 return value 910 911 def setdefault(self, key, value): 912 return self._set(self._to_key(key), self._to_value(value), True)[1] 913 914 def pop(self, key, default=_marker): 915 try: 916 return self._del(self._to_key(key))[1] 917 except KeyError: 918 if default is _marker: 919 raise 920 return default 921 922 def update(self, items): 923 if hasattr(items, 'iteritems'): 924 items = items.iteritems() 925 elif hasattr(items, 'items'): 926 items = items.items() 927 928 set = self.__setitem__ 929 for i in items: 930 set(*i) 931 932 def __setitem__(self, key, value): 933 self._set(self._to_key(key), self._to_value(value)) 934 935 def __delitem__(self, key): 936 self._del(self._to_key(key)) 937 938 def clear(self): 939 if self._data: 940 # In the case of __init__, this was already set by __new__ 941 self._data = [] 942 self._firstbucket = None 943 944 def __nonzero__(self): 945 return bool(self._data) 946 __bool__ = __nonzero__ #Py3k rename 947 948 def __len__(self): 949 l = 0 950 bucket = self._firstbucket 951 while bucket is not None: 952 l += len(bucket._keys) 953 bucket = bucket._next 954 return l 955 956 @property 957 def size(self): 958 return len(self._data) 959 960 def _search(self, key): 961 data = self._data 962 if data: 963 lo = 0 964 hi = len(data) 965 i = hi // 2 966 while i > lo: 967 cmp_ = compare(data[i].key, key) 968 if cmp_ < 0: 969 lo = i 970 elif cmp_ > 0: 971 hi = i 972 else: 973 break 974 i = (lo + hi) // 2 975 return i 976 return -1 977 978 def _findbucket(self, key): 979 index = self._search(key) 980 if index >= 0: 981 child = self._data[index].child 982 if isinstance(child, self._bucket_type): 983 return child 984 return child._findbucket(key) 985 986 def __contains__(self, key): 987 try: 988 tree_key = self._to_key(key) 989 except TypeError: 990 # Can't convert the key, so can't possibly be in the tree 991 return False 992 return key in (self._findbucket(tree_key) or ()) 993 994 def has_key(self, key): 995 index = self._search(key) 996 if index < 0: 997 return False 998 r = self._data[index].child.has_key(key) 999 return r and r + 1 1000 1001 def keys(self, min=_marker, max=_marker, 1002 excludemin=False, excludemax=False, 1003 itertype='iterkeys'): 1004 if not self._data: 1005 return () 1006 1007 if min is not _marker and min is not None: 1008 min = self._to_key(min) 1009 bucket = self._findbucket(min) 1010 else: 1011 bucket = self._firstbucket 1012 1013 iterargs = min, max, excludemin, excludemax 1014 1015 return _TreeItems(bucket, itertype, iterargs) 1016 1017 def iterkeys(self, min=_marker, max=_marker, 1018 excludemin=False, excludemax=False): 1019 return iter(self.keys(min, max, excludemin, excludemax)) 1020 1021 def __iter__(self): 1022 return iter(self.keys()) 1023 1024 def minKey(self, min=_marker): 1025 if min is _marker or min is None: 1026 bucket = self._firstbucket 1027 else: 1028 min = self._to_key(min) 1029 bucket = self._findbucket(min) 1030 if bucket is not None: 1031 return bucket.minKey(min) 1032 raise ValueError('empty tree') 1033 1034 def maxKey(self, max=_marker): 1035 data = self._data 1036 if not data: 1037 raise ValueError('empty tree') 1038 if max is _marker or max is None: 1039 return data[-1].child.maxKey() 1040 1041 max = self._to_key(max) 1042 index = self._search(max) 1043 if index and compare(data[index].child.minKey(), max) > 0: 1044 index -= 1 #pragma: no cover no idea how to provoke this 1045 return data[index].child.maxKey(max) 1046 1047 1048 def _set(self, key, value=None, ifunset=False): 1049 if (self._p_jar is not None and 1050 self._p_oid is not None and 1051 self._p_serial is not None): 1052 self._p_jar.readCurrent(self) 1053 data = self._data 1054 if data: 1055 index = self._search(key) 1056 child = data[index].child 1057 else: 1058 index = 0 1059 child = self._bucket_type() 1060 self._firstbucket = child 1061 data.append(_TreeItem(None, child)) 1062 1063 result = child._set(key, value, ifunset) 1064 grew = result[0] 1065 if grew: 1066 if type(child) is type(self): 1067 max_size = type(self).max_internal_size 1068 else: 1069 max_size = type(self).max_leaf_size 1070 if child.size > max_size: 1071 self._grow(child, index) 1072 1073 # If a BTree contains only a single bucket, BTree.__getstate__() 1074 # includes the bucket's entire state, and the bucket doesn't get 1075 # an oid of its own. So if we have a single oid-less bucket that 1076 # changed, it's *our* oid that should be marked as changed -- the 1077 # bucket doesn't have one. 1078 if (grew is not None and 1079 type(child) is self._bucket_type and 1080 len(data) == 1 and 1081 child._p_oid is None): 1082 self._p_changed = 1 1083 return result 1084 1085 def _grow(self, child, index): 1086 self._p_changed = True 1087 new_child = child._split() 1088 self._data.insert(index+1, _TreeItem(new_child.minKey(), new_child)) 1089 if len(self._data) >= type(self).max_internal_size * 2: 1090 self._split_root() 1091 1092 def _split_root(self): 1093 child = type(self)() 1094 child._data = self._data 1095 child._firstbucket = self._firstbucket 1096 self._data = [_TreeItem(None, child)] 1097 self._grow(child, 0) 1098 1099 def _split(self, index=None): 1100 data = self._data 1101 if index is None: 1102 index = len(data) // 2 1103 1104 next = type(self)() 1105 next._data = data[index:] 1106 first = data[index] 1107 del data[index:] 1108 if len(data) == 0: 1109 self._firstbucket = None # lost our bucket, can't buy no beer 1110 if isinstance(first.child, type(self)): 1111 next._firstbucket = first.child._firstbucket 1112 else: 1113 next._firstbucket = first.child 1114 return next 1115 1116 def _del(self, key): 1117 if (self._p_jar is not None and 1118 self._p_oid is not None and 1119 self._p_serial is not None): 1120 self._p_jar.readCurrent(self) 1121 1122 data = self._data 1123 if not data: 1124 raise KeyError(key) 1125 1126 index = self._search(key) 1127 child = data[index].child 1128 1129 removed_first_bucket, value = child._del(key) 1130 1131 # See comment in _set about small trees 1132 if (len(data) == 1 and 1133 type(child) is self._bucket_type and 1134 child._p_oid is None): 1135 self._p_changed = True 1136 1137 # fix up the node key, but not for the 0'th one. 1138 if index > 0 and child.size and compare(key, data[index].key) == 0: 1139 self._p_changed = True 1140 data[index].key = child.minKey() 1141 1142 if removed_first_bucket: 1143 if index: 1144 data[index-1].child._deleteNextBucket() 1145 removed_first_bucket = False # clear flag 1146 else: 1147 self._firstbucket = child._firstbucket 1148 1149 if not child.size: 1150 if type(child) is self._bucket_type: 1151 if index: 1152 data[index-1].child._deleteNextBucket() 1153 else: 1154 self._firstbucket = child._next 1155 removed_first_bucket = True 1156 del data[index] 1157 self._p_changed = True 1158 1159 return removed_first_bucket, value 1160 1161 def _deleteNextBucket(self): 1162 self._data[-1].child._deleteNextBucket() 1163 1164 def __getstate__(self): 1165 data = self._data 1166 1167 if not data: 1168 # Note: returning None here causes our __setstate__ 1169 # to not be called on unpickling 1170 return None 1171 1172 if (len(data) == 1 and 1173 type(data[0].child) is not type(self) and 1174 data[0].child._p_oid is None 1175 ): 1176 return ((data[0].child.__getstate__(), ), ) 1177 1178 1179 data = iter(data) 1180 sdata = [next(data).child] 1181 for item in data: 1182 sdata.append(item.key) 1183 sdata.append(item.child) 1184 1185 return tuple(sdata), self._firstbucket 1186 1187 def __setstate__(self, state): 1188 if state and not isinstance(state[0], tuple): 1189 raise TypeError('tuple required for first state element') 1190 1191 self.clear() 1192 if state is None: 1193 return 1194 1195 if len(state) == 1: 1196 bucket = self._bucket_type() 1197 bucket.__setstate__(state[0][0]) 1198 state = [bucket], bucket 1199 1200 data, self._firstbucket = state 1201 data = list(reversed(data)) 1202 1203 # verify children are either tree or bucket nodes. 1204 # NOTE for tree-kind node type is compared as "is", not as 1205 # "isinstance", to match C version. 1206 for child in data[::2]: 1207 if not ((type(child) is type(self)) or 1208 isinstance(child, self._bucket_type)): 1209 raise TypeError("tree child %s is neither %s nor %s" % 1210 (_tp_name(type(child)), _tp_name(type(self)), 1211 _tp_name(self._bucket_type))) 1212 1213 self._data.append(_TreeItem(None, data.pop())) 1214 while data: 1215 key = data.pop() 1216 child = data.pop() 1217 self._data.append(_TreeItem(key, child)) 1218 1219 def _assert(self, condition, message): 1220 if not condition: 1221 raise AssertionError(message) 1222 1223 def _check(self, nextbucket=None): 1224 data = self._data 1225 assert_ = self._assert 1226 if not data: 1227 assert_(self._firstbucket is None, 1228 "Empty BTree has non-NULL firstbucket") 1229 return 1230 assert_(self._firstbucket is not None, 1231 "Non-empty BTree has NULL firstbucket") 1232 1233 child_class = type(data[0].child) 1234 for i in data: 1235 assert_(i.child is not None, "BTree has NULL child") 1236 assert_(type(i.child) is child_class, 1237 "BTree children have different types") 1238 assert_(i.child.size, "Bucket length < 1") 1239 1240 if child_class is type(self): 1241 assert_(self._firstbucket is data[0].child._firstbucket, 1242 "BTree has firstbucket different than " 1243 "its first child's firstbucket") 1244 for i in range(len(data)-1): 1245 data[i].child._check(data[i+1].child._firstbucket) 1246 data[-1].child._check(nextbucket) 1247 elif child_class is self._bucket_type: 1248 assert_(self._firstbucket is data[0].child, 1249 "Bottom-level BTree node has inconsistent firstbucket " 1250 "belief") 1251 for i in range(len(data)-1): 1252 assert_(data[i].child._next is data[i+1].child, 1253 "Bucket next pointer is damaged") 1254 assert_(data[-1].child._next is nextbucket, 1255 "Bucket next pointer is damaged") 1256 else: 1257 assert_(False, "Incorrect child type") 1258 1259 def _p_resolveConflict(self, old, com, new): 1260 s_old = _get_simple_btree_bucket_state(old) 1261 s_com = _get_simple_btree_bucket_state(com) 1262 s_new = _get_simple_btree_bucket_state(new) 1263 return (( 1264 self._bucket_type()._p_resolveConflict(s_old, s_com, s_new), ), ) 1265 1266 def __repr__(self): 1267 r = super(_Tree, self).__repr__() 1268 r = r.replace('Py', '') 1269 return r 1270 1271 1272def _get_simple_btree_bucket_state(state): 1273 if state is None: 1274 return state 1275 if not isinstance(state, tuple): 1276 raise TypeError("_p_resolveConflict: expected tuple or None for state") 1277 if len(state) == 2: # non-degenerate BTree, can't resolve 1278 raise BTreesConflictError(-1, -1, -1, 11) 1279 # Peel away wrapper to get to only-bucket state. 1280 if len(state) != 1: 1281 raise TypeError("_p_resolveConflict: expected 1- or 2-tuple for state") 1282 state = state[0] 1283 if not isinstance(state, tuple) or len(state) != 1: 1284 raise TypeError("_p_resolveConflict: expected 1-tuple containing " 1285 "bucket state") 1286 state = state[0] 1287 if not isinstance(state, tuple): 1288 raise TypeError("_p_resolveConflict: expected tuple for bucket state") 1289 return state 1290 1291 1292class _TreeItems(object): 1293 1294 __slots__ = ('firstbucket', 1295 'itertype', 1296 'iterargs', 1297 'index', 1298 'it', 1299 'v', 1300 '_len', 1301 ) 1302 1303 def __init__(self, firstbucket, itertype, iterargs): 1304 self.firstbucket = firstbucket 1305 self.itertype = itertype 1306 self.iterargs = iterargs 1307 self.index = -1 1308 self.it = iter(self) 1309 self.v = None 1310 self._len = None 1311 1312 def __getitem__(self, i): 1313 if isinstance(i, slice): 1314 return list(self)[i] 1315 if i < 0: 1316 i = len(self) + i 1317 if i < 0: 1318 raise IndexError(i) 1319 1320 if i < self.index: 1321 self.index = -1 1322 self.it = iter(self) 1323 1324 while i > self.index: 1325 try: 1326 self.v = next(self.it) 1327 except StopIteration: 1328 raise IndexError(i) 1329 else: 1330 self.index += 1 1331 return self.v 1332 1333 def __len__(self): 1334 if self._len is None: 1335 i = 0 1336 for _ in self: 1337 i += 1 1338 self._len = i 1339 return self._len 1340 1341 def __iter__(self): 1342 bucket = self.firstbucket 1343 itertype = self.itertype 1344 iterargs = self.iterargs 1345 done = 0 1346 # Note that we don't mind if the first bucket yields no 1347 # results due to an idiosyncrasy in how range searches are done. 1348 while bucket is not None: 1349 for k in getattr(bucket, itertype)(*iterargs): 1350 yield k 1351 done = 0 1352 if done: 1353 return 1354 bucket = bucket._next 1355 done = 1 1356 1357 1358class _TreeIterator(object): 1359 """ Faux implementation for BBB only. 1360 """ 1361 def __init__(self, items): #pragma: no cover 1362 raise TypeError( 1363 "TreeIterators are private implementation details " 1364 "of the C-based BTrees.\n\n" 1365 "Please use 'iter(tree)', rather than instantiating " 1366 "one directly." 1367 ) 1368 1369 1370class Tree(_MutableMappingMixin, _Tree): 1371 1372 __slots__ = () 1373 1374 def get(self, key, default=None): 1375 bucket = self._findbucket(key) 1376 if bucket: 1377 return bucket.get(key, default) 1378 return default 1379 1380 def __getitem__(self, key): 1381 bucket = self._findbucket(key) 1382 if bucket: 1383 return bucket[key] 1384 raise KeyError(key) 1385 1386 def values(self, min=_marker, max=_marker, 1387 excludemin=False, excludemax=False): 1388 return self.keys(min, max, excludemin, excludemax, 'itervalues') 1389 1390 def itervalues(self, min=_marker, max=_marker, 1391 excludemin=False, excludemax=False): 1392 return iter(self.values(min, max, excludemin, excludemax)) 1393 1394 def items(self, min=_marker, max=_marker, 1395 excludemin=False, excludemax=False): 1396 return self.keys(min, max, excludemin, excludemax, 'iteritems') 1397 1398 def iteritems(self, min=_marker, max=_marker, 1399 excludemin=False, excludemax=False): 1400 return iter(self.items(min, max, excludemin, excludemax)) 1401 1402 def byValue(self, min): 1403 return reversed( 1404 sorted((v, k) for (k, v) in self.iteritems() if v >= min)) 1405 1406 def insert(self, key, value): 1407 return bool(self._set(key, value, True)[0]) 1408 1409 1410class TreeSet(_MutableSetMixin, _Tree): 1411 1412 __slots__ = () 1413 1414 def add(self, key): 1415 return self._set(self._to_key(key))[0] 1416 1417 insert = add 1418 1419 def remove(self, key): 1420 self._del(self._to_key(key)) 1421 1422 def update(self, items): 1423 add = self.add 1424 for i in items: 1425 add(i) 1426 1427 _p_resolveConflict = _Tree._p_resolveConflict 1428 1429 1430class set_operation(object): 1431 1432 __slots__ = ( 1433 'func', 1434 'set_type', 1435 '__name__', 1436 '_module', 1437 ) 1438 1439 def __init__(self, func, set_type): 1440 self.func = func 1441 self.set_type = set_type 1442 self.__name__ = func.__name__ 1443 self._module = func.__module__ 1444 1445 __module__ = property( 1446 lambda self: self._module, 1447 lambda self, nv: setattr(self, '_module', nv) 1448 ) 1449 1450 def __call__(self, *a, **k): 1451 return self.func(self.set_type, *a, **k) 1452 1453 1454def difference(set_type, o1, o2): 1455 if o1 is None or o2 is None: 1456 return o1 1457 i1 = _SetIteration(o1, True, 0) 1458 i2 = _SetIteration(o2, False, 0, True) 1459 if i1.useValues: 1460 result = o1._mapping_type() 1461 def copy(i): 1462 result._keys.append(i.key) 1463 result._values.append(i.value) 1464 else: 1465 result = o1._set_type() 1466 def copy(i): 1467 result._keys.append(i.key) 1468 while i1.active and i2.active: 1469 cmp_ = compare(i1.key, i2.key) 1470 if cmp_ < 0: 1471 copy(i1) 1472 i1.advance() 1473 elif cmp_ == 0: 1474 i1.advance() 1475 i2.advance() 1476 else: 1477 i2.advance() 1478 while i1.active: 1479 copy(i1) 1480 i1.advance() 1481 return result 1482 1483def union(set_type, o1, o2): 1484 if o1 is None: 1485 return o2 1486 if o2 is None: 1487 return o1 1488 i1 = _SetIteration(o1, False, 0, True) 1489 i2 = _SetIteration(o2, False, 0, True) 1490 result = set_type() 1491 def copy(i): 1492 result._keys.append(i.key) 1493 while i1.active and i2.active: 1494 cmp_ = compare(i1.key, i2.key) 1495 if cmp_ < 0: 1496 copy(i1) 1497 i1.advance() 1498 elif cmp_ == 0: 1499 copy(i1) 1500 i1.advance() 1501 i2.advance() 1502 else: 1503 copy(i2) 1504 i2.advance() 1505 while i1.active: 1506 copy(i1) 1507 i1.advance() 1508 while i2.active: 1509 copy(i2) 1510 i2.advance() 1511 return result 1512 1513def intersection(set_type, o1, o2): 1514 if o1 is None: 1515 return o2 1516 if o2 is None: 1517 return o1 1518 i1 = _SetIteration(o1, False, 0, True) 1519 i2 = _SetIteration(o2, False, 0, True) 1520 result = set_type() 1521 def copy(i): 1522 result._keys.append(i.key) 1523 while i1.active and i2.active: 1524 cmp_ = compare(i1.key, i2.key) 1525 if cmp_ < 0: 1526 i1.advance() 1527 elif cmp_ == 0: 1528 copy(i1) 1529 i1.advance() 1530 i2.advance() 1531 else: 1532 i2.advance() 1533 return result 1534 1535def _prepMergeIterators(o1, o2): 1536 MERGE_DEFAULT = getattr(o1, 'MERGE_DEFAULT', None) 1537 if MERGE_DEFAULT is None: 1538 raise TypeError("invalid set operation") 1539 i1 = _SetIteration(o1, True, MERGE_DEFAULT) 1540 i2 = _SetIteration(o2, True, MERGE_DEFAULT) 1541 return i1, i2 1542 1543def weightedUnion(set_type, o1, o2, w1=1, w2=1): 1544 if o1 is None: 1545 if o2 is None: 1546 return 0, None 1547 return w2, o2 1548 if o2 is None: 1549 return w1, o1 1550 i1, i2 = _prepMergeIterators(o1, o2) 1551 MERGE = getattr(o1, 'MERGE', None) 1552 if MERGE is None and i1.useValues and i2.useValues: 1553 raise TypeError("invalid set operation") 1554 MERGE_WEIGHT = getattr(o1, 'MERGE_WEIGHT') 1555 if (not i1.useValues) and i2.useValues: 1556 i1, i2 = i2, i1 1557 w1, w2 = w2, w1 1558 _merging = i1.useValues or i2.useValues 1559 if _merging: 1560 result = o1._mapping_type() 1561 def copy(i, w): 1562 result._keys.append(i.key) 1563 result._values.append(MERGE_WEIGHT(i.value, w)) 1564 else: 1565 result = o1._set_type() 1566 def copy(i, w): 1567 result._keys.append(i.key) 1568 1569 while i1.active and i2.active: 1570 cmp_ = compare(i1.key, i2.key) 1571 if cmp_ < 0: 1572 copy(i1, w1) 1573 i1.advance() 1574 elif cmp_ == 0: 1575 result._keys.append(i1.key) 1576 if _merging: 1577 result._values.append(MERGE(i1.value, w1, i2.value, w2)) 1578 i1.advance() 1579 i2.advance() 1580 else: 1581 copy(i2, w2) 1582 i2.advance() 1583 while i1.active: 1584 copy(i1, w1) 1585 i1.advance() 1586 while i2.active: 1587 copy(i2, w2) 1588 i2.advance() 1589 return 1, result 1590 1591def weightedIntersection(set_type, o1, o2, w1=1, w2=1): 1592 if o1 is None: 1593 if o2 is None: 1594 return 0, None 1595 return w2, o2 1596 if o2 is None: 1597 return w1, o1 1598 i1, i2 = _prepMergeIterators(o1, o2) 1599 MERGE = getattr(o1, 'MERGE', None) 1600 if MERGE is None and i1.useValues and i2.useValues: 1601 raise TypeError("invalid set operation") 1602 if (not i1.useValues) and i2.useValues: 1603 i1, i2 = i2, i1 1604 w1, w2 = w2, w1 1605 _merging = i1.useValues or i2.useValues 1606 if _merging: 1607 result = o1._mapping_type() 1608 else: 1609 result = o1._set_type() 1610 while i1.active and i2.active: 1611 cmp_ = compare(i1.key, i2.key) 1612 if cmp_ < 0: 1613 i1.advance() 1614 elif cmp_ == 0: 1615 result._keys.append(i1.key) 1616 if _merging: 1617 result._values.append(MERGE(i1.value, w1, i2.value, w2)) 1618 i1.advance() 1619 i2.advance() 1620 else: 1621 i2.advance() 1622 if isinstance(result, (Set, TreeSet)): 1623 return w1 + w2, result 1624 return 1, result 1625 1626def multiunion(set_type, seqs): 1627 # XXX simple/slow implementation. Goal is just to get tests to pass. 1628 result = set_type() 1629 for s in seqs: 1630 try: 1631 iter(s) 1632 except TypeError: 1633 s = set_type((s, )) 1634 result.update(s) 1635 return result 1636 1637 1638def MERGE(self, value1, weight1, value2, weight2): 1639 return (value1 * weight1) + (value2 * weight2) 1640 1641def MERGE_WEIGHT_default(self, value, weight): 1642 return value 1643 1644def MERGE_WEIGHT_numeric(self, value, weight): 1645 return value * weight 1646 1647def _fix_pickle(mod_dict, mod_name): 1648 # Make the pure-Python objects pickle with the same 1649 # class names and types as the C extensions by setting the appropriate 1650 # _BTree_reduce_as attribute. 1651 # If the C extensions are not available, we also change the 1652 # __name__ attribute of the type to match the C name (otherwise 1653 # we wind up with *Py in the pickles) 1654 # Each module must call this as `_fix_pickle(globals(), __name__)` 1655 # at the bottom. 1656 1657 mod_prefix = mod_name.split('.')[-1][:2] # BTrees.OOBTree -> 'OO' 1658 bucket_name = mod_prefix + 'Bucket' 1659 py_bucket_name = bucket_name + 'Py' 1660 1661 have_c_extensions = mod_dict[bucket_name] is not mod_dict[py_bucket_name] 1662 1663 for name in 'Bucket', 'Set', 'BTree', 'TreeSet', 'TreeIterator': 1664 raw_name = mod_prefix + name 1665 py_name = raw_name + 'Py' 1666 try: 1667 py_type = mod_dict[py_name] 1668 except KeyError: 1669 if name == 'TreeIterator': 1670 # Optional 1671 continue 1672 raise # pragma: no cover 1673 raw_type = mod_dict[raw_name] # Could be C or Python 1674 1675 py_type._BTree_reduce_as = raw_type 1676 py_type._BTree_reduce_up_bound = py_type 1677 1678 if not have_c_extensions: # pragma: no cover 1679 # Set FooPy to have the __name__ of simply Foo. 1680 # We can't do this if the C extension is available, 1681 # because then mod_dict[FooPy.__name__] is not FooPy 1682 # and pickle refuses to save something like that. 1683 # On the other hand (no C extension) this makes our 1684 # Python pickle match the C version by default 1685 py_type.__name__ = raw_name 1686 py_type.__qualname__ = raw_name # Py 3.3+ 1687 1688 1689# tp_name returns full name of a type in the same way as how it is provided by 1690# typ->tp_name in C. 1691def _tp_name(typ): 1692 return '.'.join([typ.__module__, typ.__name__]) 1693