Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 1 | # |
| 2 | # This is a copy on write dictionary and set which abuses classes to try and be nice and fast. |
| 3 | # |
Brad Bishop | d7bf8c1 | 2018-02-25 22:55:05 -0500 | [diff] [blame] | 4 | # Copyright (C) 2006 Tim Ansell |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 5 | # |
Patrick Williams | 92b42cb | 2022-09-03 06:53:57 -0500 | [diff] [blame] | 6 | # SPDX-License-Identifier: GPL-2.0-only |
| 7 | # |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 8 | # Please Note: |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 9 | # Be careful when using mutable types (ie Dict and Lists) - operations involving these are SLOW. |
| 10 | # Assign a file to __warn__ to get warnings about slow operations. |
| 11 | # |
| 12 | |
Patrick Williams | c0f7c04 | 2017-02-23 20:41:17 -0600 | [diff] [blame] | 13 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 14 | import copy |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 15 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 16 | ImmutableTypes = ( |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 17 | bool, |
| 18 | complex, |
| 19 | float, |
| 20 | int, |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 21 | tuple, |
| 22 | frozenset, |
Patrick Williams | c0f7c04 | 2017-02-23 20:41:17 -0600 | [diff] [blame] | 23 | str |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 24 | ) |
| 25 | |
| 26 | MUTABLE = "__mutable__" |
| 27 | |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 28 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 29 | class COWMeta(type): |
| 30 | pass |
| 31 | |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 32 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 33 | class COWDictMeta(COWMeta): |
| 34 | __warn__ = False |
| 35 | __hasmutable__ = False |
| 36 | __marker__ = tuple() |
| 37 | |
| 38 | def __str__(cls): |
| 39 | # FIXME: I have magic numbers! |
| 40 | return "<COWDict Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) - 3) |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 41 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 42 | __repr__ = __str__ |
| 43 | |
| 44 | def cow(cls): |
| 45 | class C(cls): |
| 46 | __count__ = cls.__count__ + 1 |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 47 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 48 | return C |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 49 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 50 | copy = cow |
| 51 | __call__ = cow |
| 52 | |
| 53 | def __setitem__(cls, key, value): |
Patrick Williams | c0f7c04 | 2017-02-23 20:41:17 -0600 | [diff] [blame] | 54 | if value is not None and not isinstance(value, ImmutableTypes): |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 55 | if not isinstance(value, COWMeta): |
| 56 | cls.__hasmutable__ = True |
| 57 | key += MUTABLE |
| 58 | setattr(cls, key, value) |
| 59 | |
| 60 | def __getmutable__(cls, key, readonly=False): |
| 61 | nkey = key + MUTABLE |
| 62 | try: |
| 63 | return cls.__dict__[nkey] |
| 64 | except KeyError: |
| 65 | pass |
| 66 | |
| 67 | value = getattr(cls, nkey) |
| 68 | if readonly: |
| 69 | return value |
| 70 | |
| 71 | if not cls.__warn__ is False and not isinstance(value, COWMeta): |
| 72 | print("Warning: Doing a copy because %s is a mutable type." % key, file=cls.__warn__) |
| 73 | try: |
| 74 | value = value.copy() |
| 75 | except AttributeError as e: |
| 76 | value = copy.copy(value) |
| 77 | setattr(cls, nkey, value) |
| 78 | return value |
| 79 | |
| 80 | __getmarker__ = [] |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 81 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 82 | def __getreadonly__(cls, key, default=__getmarker__): |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 83 | """ |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 84 | Get a value (even if mutable) which you promise not to change. |
| 85 | """ |
| 86 | return cls.__getitem__(key, default, True) |
| 87 | |
| 88 | def __getitem__(cls, key, default=__getmarker__, readonly=False): |
| 89 | try: |
| 90 | try: |
| 91 | value = getattr(cls, key) |
| 92 | except AttributeError: |
| 93 | value = cls.__getmutable__(key, readonly) |
| 94 | |
| 95 | # This is for values which have been deleted |
| 96 | if value is cls.__marker__: |
| 97 | raise AttributeError("key %s does not exist." % key) |
| 98 | |
| 99 | return value |
| 100 | except AttributeError as e: |
| 101 | if not default is cls.__getmarker__: |
| 102 | return default |
| 103 | |
| 104 | raise KeyError(str(e)) |
| 105 | |
| 106 | def __delitem__(cls, key): |
| 107 | cls.__setitem__(key, cls.__marker__) |
| 108 | |
| 109 | def __revertitem__(cls, key): |
Patrick Williams | c0f7c04 | 2017-02-23 20:41:17 -0600 | [diff] [blame] | 110 | if key not in cls.__dict__: |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 111 | key += MUTABLE |
| 112 | delattr(cls, key) |
| 113 | |
| 114 | def __contains__(cls, key): |
| 115 | return cls.has_key(key) |
| 116 | |
| 117 | def has_key(cls, key): |
| 118 | value = cls.__getreadonly__(key, cls.__marker__) |
| 119 | if value is cls.__marker__: |
| 120 | return False |
| 121 | return True |
| 122 | |
| 123 | def iter(cls, type, readonly=False): |
| 124 | for key in dir(cls): |
| 125 | if key.startswith("__"): |
| 126 | continue |
| 127 | |
| 128 | if key.endswith(MUTABLE): |
| 129 | key = key[:-len(MUTABLE)] |
| 130 | |
| 131 | if type == "keys": |
| 132 | yield key |
| 133 | |
| 134 | try: |
| 135 | if readonly: |
| 136 | value = cls.__getreadonly__(key) |
| 137 | else: |
| 138 | value = cls[key] |
| 139 | except KeyError: |
| 140 | continue |
| 141 | |
| 142 | if type == "values": |
| 143 | yield value |
| 144 | if type == "items": |
| 145 | yield (key, value) |
Brad Bishop | 1a4b7ee | 2018-12-16 17:11:34 -0800 | [diff] [blame] | 146 | return |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 147 | |
| 148 | def iterkeys(cls): |
| 149 | return cls.iter("keys") |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 150 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 151 | def itervalues(cls, readonly=False): |
| 152 | if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False: |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 153 | print("Warning: If you aren't going to change any of the values call with True.", file=cls.__warn__) |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 154 | return cls.iter("values", readonly) |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 155 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 156 | def iteritems(cls, readonly=False): |
| 157 | if not cls.__warn__ is False and cls.__hasmutable__ and readonly is False: |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 158 | print("Warning: If you aren't going to change any of the values call with True.", file=cls.__warn__) |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 159 | return cls.iter("items", readonly) |
| 160 | |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 161 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 162 | class COWSetMeta(COWDictMeta): |
| 163 | def __str__(cls): |
| 164 | # FIXME: I have magic numbers! |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 165 | return "<COWSet Level: %i Current Keys: %i>" % (cls.__count__, len(cls.__dict__) - 3) |
| 166 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 167 | __repr__ = __str__ |
| 168 | |
| 169 | def cow(cls): |
| 170 | class C(cls): |
| 171 | __count__ = cls.__count__ + 1 |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 172 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 173 | return C |
| 174 | |
| 175 | def add(cls, value): |
| 176 | COWDictMeta.__setitem__(cls, repr(hash(value)), value) |
| 177 | |
| 178 | def remove(cls, value): |
| 179 | COWDictMeta.__delitem__(cls, repr(hash(value))) |
| 180 | |
| 181 | def __in__(cls, value): |
Patrick Williams | c0f7c04 | 2017-02-23 20:41:17 -0600 | [diff] [blame] | 182 | return repr(hash(value)) in COWDictMeta |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 183 | |
| 184 | def iterkeys(cls): |
| 185 | raise TypeError("sets don't have keys") |
| 186 | |
| 187 | def iteritems(cls): |
| 188 | raise TypeError("sets don't have 'items'") |
| 189 | |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 190 | |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 191 | # These are the actual classes you use! |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 192 | class COWDictBase(metaclass=COWDictMeta): |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 193 | __count__ = 0 |
| 194 | |
Andrew Geissler | c9f7865 | 2020-09-18 14:11:35 -0500 | [diff] [blame] | 195 | |
| 196 | class COWSetBase(metaclass=COWSetMeta): |
Patrick Williams | c124f4f | 2015-09-15 14:41:29 -0500 | [diff] [blame] | 197 | __count__ = 0 |