13257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel# Access WeakSet through the weakref module. 23257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel# This code is separated-out because it is needed 33257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel# by abc.py to load everything else at startup. 43257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 53257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDanielfrom _weakref import ref 63257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 73257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel__all__ = ['WeakSet'] 83257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 93257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 103257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDanielclass _IterationGuard(object): 113257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # This context manager registers itself in the current iterators of the 123257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # weak container, such as to delay all removals until the context manager 133257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # exits. 143257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # This technique should be relatively thread-safe (since sets are). 153257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 163257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __init__(self, weakcontainer): 173257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # Don't create cycles 183257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.weakcontainer = ref(weakcontainer) 193257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 203257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __enter__(self): 213257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel w = self.weakcontainer() 223257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if w is not None: 233257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel w._iterating.add(self) 243257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self 253257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 263257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __exit__(self, e, t, b): 273257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel w = self.weakcontainer() 283257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if w is not None: 293257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel s = w._iterating 303257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel s.remove(self) 313257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if not s: 323257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel w._commit_removals() 333257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 343257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 353257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDanielclass WeakSet(object): 363257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __init__(self, data=None): 373257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data = set() 383257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def _remove(item, selfref=ref(self)): 393257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self = selfref() 403257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self is not None: 413257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._iterating: 423257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._pending_removals.append(item) 433257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel else: 443257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.discard(item) 453257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._remove = _remove 463257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # A list of keys to be removed 473257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._pending_removals = [] 483257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._iterating = set() 493257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if data is not None: 503257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.update(data) 513257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 523257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def _commit_removals(self): 533257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel l = self._pending_removals 543257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel discard = self.data.discard 553257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel while l: 563257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel discard(l.pop()) 573257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 583257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __iter__(self): 593257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel with _IterationGuard(self): 603257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel for itemref in self.data: 613257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel item = itemref() 623257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if item is not None: 633257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # Caveat: the iterator will keep a strong reference to 643257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel # `item` until it is resumed or closed. 653257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel yield item 663257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 673257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __len__(self): 683257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return len(self.data) - len(self._pending_removals) 693257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 703257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __contains__(self, item): 713257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel try: 723257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel wr = ref(item) 733257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel except TypeError: 743257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return False 753257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return wr in self.data 763257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 773257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __reduce__(self): 783257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return (self.__class__, (list(self),), 793257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel getattr(self, '__dict__', None)) 803257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 813257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __hash__ = None 823257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 833257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def add(self, item): 843257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 853257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 863257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.add(ref(item, self._remove)) 873257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 883257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def clear(self): 893257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 903257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 913257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.clear() 923257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 933257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def copy(self): 943257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.__class__(self) 953257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 963257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def pop(self): 973257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 983257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 993257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel while True: 1003257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel try: 1013257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel itemref = self.data.pop() 1023257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel except KeyError: 1033257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel raise KeyError('pop from empty WeakSet') 1043257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel item = itemref() 1053257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if item is not None: 1063257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return item 1073257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1083257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def remove(self, item): 1093257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 1103257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 1113257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.remove(ref(item)) 1123257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1133257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def discard(self, item): 1143257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 1153257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 1163257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.discard(ref(item)) 1173257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1183257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def update(self, other): 1193257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 1203257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 1213257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel for element in other: 1223257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.add(element) 1233257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1243257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __ior__(self, other): 1253257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.update(other) 1263257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self 1273257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1283257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def difference(self, other): 1293257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel newset = self.copy() 1303257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel newset.difference_update(other) 1313257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return newset 1323257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __sub__ = difference 1333257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1343257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def difference_update(self, other): 1353257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.__isub__(other) 1363257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __isub__(self, other): 1373257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 1383257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 1393257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self is other: 1403257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.clear() 1413257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel else: 1423257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.difference_update(ref(item) for item in other) 1433257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self 1443257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1453257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def intersection(self, other): 1463257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.__class__(item for item in other if item in self) 1473257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __and__ = intersection 1483257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1493257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def intersection_update(self, other): 1503257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.__iand__(other) 1513257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __iand__(self, other): 1523257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 1533257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 1543257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.intersection_update(ref(item) for item in other) 1553257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self 1563257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1573257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def issubset(self, other): 1583257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.data.issubset(ref(item) for item in other) 1593257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __le__ = issubset 1603257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1613257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __lt__(self, other): 1623257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.data < set(ref(item) for item in other) 1633257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1643257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def issuperset(self, other): 1653257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.data.issuperset(ref(item) for item in other) 1663257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __ge__ = issuperset 1673257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1683257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __gt__(self, other): 1693257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.data > set(ref(item) for item in other) 1703257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1713257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __eq__(self, other): 1723257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if not isinstance(other, self.__class__): 1733257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return NotImplemented 1743257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.data == set(ref(item) for item in other) 1753257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1763257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __ne__(self, other): 1773257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel opposite = self.__eq__(other) 1783257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if opposite is NotImplemented: 1793257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return NotImplemented 1803257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return not opposite 1813257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1823257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def symmetric_difference(self, other): 1833257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel newset = self.copy() 1843257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel newset.symmetric_difference_update(other) 1853257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return newset 1863257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __xor__ = symmetric_difference 1873257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1883257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def symmetric_difference_update(self, other): 1893257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.__ixor__(other) 1903257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def __ixor__(self, other): 1913257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self._pending_removals: 1923257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self._commit_removals() 1933257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel if self is other: 1943257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.clear() 1953257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel else: 1963257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel self.data.symmetric_difference_update(ref(item, self._remove) for item in other) 1973257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self 1983257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 1993257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def union(self, other): 2003257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return self.__class__(e for s in (self, other) for e in s) 2013257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel __or__ = union 2023257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel 2033257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel def isdisjoint(self, other): 2043257aa99321d745773a6bd1bd4ce7f6fafe74411Daryl McDaniel return len(self.intersection(other)) == 0 205