Source Code for Module SCons.compat._scons_sets

  1  """Classes to represent arbitrary sets (including sets of sets). 
  2   
  3  This module implements sets using dictionaries whose values are 
  4  ignored.  The usual operations (union, intersection, deletion, etc.) 
  5  are provided as both methods and operators. 
  6   
  7  Important: sets are not sequences!  While they support 'x in s', 
  8  'len(s)', and 'for x in s', none of those operations are unique for 
  9  sequences; for example, mappings support all three as well.  The 
 10  characteristic operation for sequences is subscripting with small 
 11  integers: s[i], for i in range(len(s)).  Sets don't support 
 12  subscripting at all.  Also, sequences allow multiple occurrences and 
 13  their elements have a definite order; sets on the other hand don't 
 14  record multiple occurrences and don't remember the order of element 
 15  insertion (which is why they don't support s[i]). 
 16   
 17  The following classes are provided: 
 18   
 19  BaseSet -- All the operations common to both mutable and immutable 
 20      sets. This is an abstract class, not meant to be directly 
 21      instantiated. 
 22   
 23  Set -- Mutable sets, subclass of BaseSet; not hashable. 
 24   
 25  ImmutableSet -- Immutable sets, subclass of BaseSet; hashable. 
 26      An iterable argument is mandatory to create an ImmutableSet. 
 27   
 28  _TemporarilyImmutableSet -- A wrapper around a Set, hashable, 
 29      giving the same hash value as the immutable set equivalent 
 30      would have.  Do not use this class directly. 
 31   
 32  Only hashable objects can be added to a Set. In particular, you cannot 
 33  really add a Set as an element to another Set; if you try, what is 
 34  actually added is an ImmutableSet built from it (it compares equal to 
 35  the one you tried adding). 
 36   
 37  When you ask if `x in y' where x is a Set and y is a Set or 
 38  ImmutableSet, x is wrapped into a _TemporarilyImmutableSet z, and 
 39  what's tested is actually `z in y'. 
 40   
 41  """ 
 42   
 43  # Code history: 
 44  # 
 45  # - Greg V. Wilson wrote the first version, using a different approach 
 46  #   to the mutable/immutable problem, and inheriting from dict. 
 47  # 
 48  # - Alex Martelli modified Greg's version to implement the current 
 49  #   Set/ImmutableSet approach, and make the data an attribute. 
 50  # 
 51  # - Guido van Rossum rewrote much of the code, made some API changes, 
 52  #   and cleaned up the docstrings. 
 53  # 
 54  # - Raymond Hettinger added a number of speedups and other 
 55  #   improvements. 
 56   
 57  # protect this import from the fixers... 
 58  exec('from itertools import ifilterfalse as filterfalse') 
 59   
 60  __all__ = ['BaseSet', 'Set', 'ImmutableSet'] 
 61   
 62 -class BaseSet(object): 
 63      """Common base class for mutable and immutable sets.""" 
 64   
 65      __slots__ = ['_data'] 
 66   
 67      # Constructor 
 68   
 69 -    def __init__(self): 
 70          """This is an abstract class.""" 
 71          # Don't call this from a concrete subclass! 
 72          if self.__class__ is BaseSet: 
 73              raise TypeError("BaseSet is an abstract class.  " 
 74                                "Use Set or ImmutableSet.") 
 75   
 76      # Standard protocols: __len__, __repr__, __str__, __iter__ 
 77   
 78 -    def __len__(self): 
 79          """Return the number of elements of a set.""" 
 80          return len(self._data) 
 81   
 82 -    def __repr__(self): 
 83          """Return string representation of a set. 
 84   
 85          This looks like 'Set([<list of elements>])'. 
 86          """ 
 87          return self._repr() 
 88   
 89      # __str__ is the same as __repr__ 
 90      __str__ = __repr__ 
 91   
 92 -    def _repr(self, sort_them=False): 
 93          elements = list(self._data.keys()) 
 94          if sort_them: 
 95              elements.sort() 
 96          return '%s(%r)' % (self.__class__.__name__, elements) 
 97   
 98 -    def __iter__(self): 
 99          """Return an iterator over the elements or a set. 
100   
101          This is the keys iterator for the underlying dict. 
102          """ 
103          # Wrapping name in () prevents fixer from "fixing" this 
104          return (self._data.iterkeys)() 
105   
106      # Three-way comparison is not supported.  However, because __eq__ is 
107      # tried before __cmp__, if Set x == Set y, x.__eq__(y) returns True and 
108      # then cmp(x, y) returns 0 (Python doesn't actually call __cmp__ in this 
109      # case). 
110   
111 -    def __cmp__(self, other): 
112          raise TypeError("can't compare sets using cmp()") 
113   
114      # Equality comparisons using the underlying dicts.  Mixed-type comparisons 
115      # are allowed here, where Set == z for non-Set z always returns False, 
116      # and Set != z always True.  This allows expressions like "x in y" to 
117      # give the expected result when y is a sequence of mixed types, not 
118      # raising a pointless TypeError just because y contains a Set, or x is 
119      # a Set and y contain's a non-set ("in" invokes only __eq__). 
120      # Subtle:  it would be nicer if __eq__ and __ne__ could return 
121      # NotImplemented instead of True or False.  Then the other comparand 
122      # would get a chance to determine the result, and if the other comparand 
123      # also returned NotImplemented then it would fall back to object address 
124      # comparison (which would always return False for __eq__ and always 
125      # True for __ne__).  However, that doesn't work, because this type 
126      # *also* implements __cmp__:  if, e.g., __eq__ returns NotImplemented, 
127      # Python tries __cmp__ next, and the __cmp__ here then raises TypeError. 
128   
129 -    def __eq__(self, other): 
130          if isinstance(other, BaseSet): 
131              return self._data == other._data 
132          else: 
133              return False 
134   
135 -    def __ne__(self, other): 
136          if isinstance(other, BaseSet): 
137              return self._data != other._data 
138          else: 
139              return True 
140   
141      # Copying operations 
142   
143 -    def copy(self): 
144          """Return a shallow copy of a set.""" 
145          result = self.__class__() 
146          result._data.update(self._data) 
147          return result 
148   
149      __copy__ = copy # For the copy module 
150   
151 -    def __deepcopy__(self, memo): 
152          """Return a deep copy of a set; used by copy module.""" 
153          # This pre-creates the result and inserts it in the memo 
154          # early, in case the deep copy recurses into another reference 
155          # to this same set.  A set can't be an element of itself, but 
156          # it can certainly contain an object that has a reference to 
157          # itself. 
158          from copy import deepcopy 
159          result = self.__class__() 
160          memo[id(self)] = result 
161          data = result._data 
162          value = True 
163          for elt in self: 
164              data[deepcopy(elt, memo)] = value 
165          return result 
166   
167      # Standard set operations: union, intersection, both differences. 
168      # Each has an operator version (e.g. __or__, invoked with |) and a 
169      # method version (e.g. union). 
170      # Subtle:  Each pair requires distinct code so that the outcome is 
171      # correct when the type of other isn't suitable.  For example, if 
172      # we did "union = __or__" instead, then Set().union(3) would return 
173      # NotImplemented instead of raising TypeError (albeit that *why* it 
174      # raises TypeError as-is is also a bit subtle). 
175   
176 -    def __or__(self, other): 
177          """Return the union of two sets as a new set. 
178   
179          (I.e. all elements that are in either set.) 
180          """ 
181          if not isinstance(other, BaseSet): 
182              return NotImplemented 
183          return self.union(other) 
184   
185 -    def union(self, other): 
186          """Return the union of two sets as a new set. 
187   
188          (I.e. all elements that are in either set.) 
189          """ 
190          result = self.__class__(self) 
191          result._update(other) 
192          return result 
193   
194 -    def __and__(self, other): 
195          """Return the intersection of two sets as a new set. 
196   
197          (I.e. all elements that are in both sets.) 
198          """ 
199          if not isinstance(other, BaseSet): 
200              return NotImplemented 
201          return self.intersection(other) 
202   
203 -    def intersection(self, other): 
204          """Return the intersection of two sets as a new set. 
205   
206          (I.e. all elements that are in both sets.) 
207          """ 
208          if not isinstance(other, BaseSet): 
209              other = Set(other) 
210          if len(self) <= len(other): 
211              little, big = self, other 
212          else: 
213              little, big = other, self 
214          common = iter(filter(big._data.has_key, little)) 
215          return self.__class__(common) 
216   
217 -    def __xor__(self, other): 
218          """Return the symmetric difference of two sets as a new set. 
219   
220          (I.e. all elements that are in exactly one of the sets.) 
221          """ 
222          if not isinstance(other, BaseSet): 
223              return NotImplemented 
224          return self.symmetric_difference(other) 
225   
226 -    def symmetric_difference(self, other): 
227          """Return the symmetric difference of two sets as a new set. 
228   
229          (I.e. all elements that are in exactly one of the sets.) 
230          """ 
231          result = self.__class__() 
232          data = result._data 
233          value = True 
234          selfdata = self._data 
235          try: 
236              otherdata = other._data 
237          except AttributeError: 
238              otherdata = Set(other)._data 
239          for elt in filterfalse(otherdata.has_key, selfdata): 
240              data[elt] = value 
241          for elt in filterfalse(selfdata.has_key, otherdata): 
242              data[elt] = value 
243          return result 
244   
245 -    def  __sub__(self, other): 
246          """Return the difference of two sets as a new Set. 
247   
248          (I.e. all elements that are in this set and not in the other.) 
249          """ 
250          if not isinstance(other, BaseSet): 
251              return NotImplemented 
252          return self.difference(other) 
253   
254 -    def difference(self, other): 
255          """Return the difference of two sets as a new Set. 
256   
257          (I.e. all elements that are in this set and not in the other.) 
258          """ 
259          result = self.__class__() 
260          data = result._data 
261          try: 
262              otherdata = other._data 
263          except AttributeError: 
264              otherdata = Set(other)._data 
265          value = True 
266          for elt in filterfalse(otherdata.has_key, self): 
267              data[elt] = value 
268          return result 
269   
270      # Membership test 
271   
272 -    def __contains__(self, element): 
273          """Report whether an element is a member of a set. 
274   
275          (Called in response to the expression `element in self'.) 
276          """ 
277          try: 
278              return element in self._data 
279          except TypeError: 
280              transform = getattr(element, "__as_temporarily_immutable__", None) 
281              if transform is None: 
282                  raise # re-raise the TypeError exception we caught 
283              return transform() in self._data 
284   
285      # Subset and superset test 
286   
287 -    def issubset(self, other): 
288          """Report whether another set contains this set.""" 
289          self._binary_sanity_check(other) 
290          if len(self) > len(other):  # Fast check for obvious cases 
291              return False 
292          for elt in filterfalse(other._data.has_key, self): 
293              return False 
294          return True 
295   
296 -    def issuperset(self, other): 
297          """Report whether this set contains another set.""" 
298          self._binary_sanity_check(other) 
299          if len(self) < len(other):  # Fast check for obvious cases 
300              return False 
301          for elt in filterfalse(self._data.has_key, other): 
302              return False 
303          return True 
304   
305      # Inequality comparisons using the is-subset relation. 
306      __le__ = issubset 
307      __ge__ = issuperset 
308   
309 -    def __lt__(self, other): 
310          self._binary_sanity_check(other) 
311          return len(self) < len(other) and self.issubset(other) 
312   
313 -    def __gt__(self, other): 
314          self._binary_sanity_check(other) 
315          return len(self) > len(other) and self.issuperset(other) 
316   
317      # Assorted helpers 
318   
319 -    def _binary_sanity_check(self, other): 
320          # Check that the other argument to a binary operation is also 
321          # a set, raising a TypeError otherwise. 
322          if not isinstance(other, BaseSet): 
323              raise TypeError("Binary operation only permitted between sets") 
324   
325 -    def _compute_hash(self): 
326          # Calculate hash code for a set by xor'ing the hash codes of 
327          # the elements.  This ensures that the hash code does not depend 
328          # on the order in which elements are added to the set.  This is 
329          # not called __hash__ because a BaseSet should not be hashable; 
330          # only an ImmutableSet is hashable. 
331          result = 0 
332          for elt in self: 
333              result ^= hash(elt) 
334          return result 
335   
336 -    def _update(self, iterable): 
337          # The main loop for update() and the subclass __init__() methods. 
338          data = self._data 
339   
340          # Use the fast update() method when a dictionary is available. 
341          if isinstance(iterable, BaseSet): 
342              data.update(iterable._data) 
343              return 
344   
345          value = True 
346   
347          if type(iterable) in (list, tuple, xrange): 
348              # Optimized: we know that __iter__() and next() can't 
349              # raise TypeError, so we can move 'try:' out of the loop. 
350              it = iter(iterable) 
351              while True: 
352                  try: 
353                      for element in it: 
354                          data[element] = value 
355                      return 
356                  except TypeError: 
357                      transform = getattr(element, "__as_immutable__", None) 
358                      if transform is None: 
359                          raise # re-raise the TypeError exception we caught 
360                      data[transform()] = value 
361          else: 
362              # Safe: only catch TypeError where intended 
363              for element in iterable: 
364                  try: 
365                      data[element] = value 
366                  except TypeError: 
367                      transform = getattr(element, "__as_immutable__", None) 
368                      if transform is None: 
369                          raise # re-raise the TypeError exception we caught 
370                      data[transform()] = value 
371   
372   
373 -class ImmutableSet(BaseSet): 
374      """Immutable set class.""" 
375   
376      __slots__ = ['_hashcode'] 
377   
378      # BaseSet + hashing 
379   
380 -    def __init__(self, iterable=None): 
381          """Construct an immutable set from an optional iterable.""" 
382          self._hashcode = None 
383          self._data = {} 
384          if iterable is not None: 
385              self._update(iterable) 
386   
387 -    def __hash__(self): 
388          if self._hashcode is None: 
389              self._hashcode = self._compute_hash() 
390          return self._hashcode 
391   
392 -    def __getstate__(self): 
393          return self._data, self._hashcode 
394   
395 -    def __setstate__(self, state): 
396          self._data, self._hashcode = state 
397   
398 -class Set(BaseSet): 
399      """ Mutable set class.""" 
400   
401      __slots__ = [] 
402   
403      # BaseSet + operations requiring mutability; no hashing 
404   
405 -    def __init__(self, iterable=None): 
406          """Construct a set from an optional iterable.""" 
407          self._data = {} 
408          if iterable is not None: 
409              self._update(iterable) 
410   
411 -    def __getstate__(self): 
412          # getstate's results are ignored if it is not 
413          return self._data, 
414   
415 -    def __setstate__(self, data): 
416          self._data, = data 
417   
418 -    def __hash__(self): 
419          """A Set cannot be hashed.""" 
420          # We inherit object.__hash__, so we must deny this explicitly 
421          raise TypeError("Can't hash a Set, only an ImmutableSet.") 
422   
423      # In-place union, intersection, differences. 
424      # Subtle:  The xyz_update() functions deliberately return None, 
425      # as do all mutating operations on built-in container types. 
426      # The __xyz__ spellings have to return self, though. 
427   
428 -    def __ior__(self, other): 
429          """Update a set with the union of itself and another.""" 
430          self._binary_sanity_check(other) 
431          self._data.update(other._data) 
432          return self 
433   
434 -    def union_update(self, other): 
435          """Update a set with the union of itself and another.""" 
436          self._update(other) 
437   
438 -    def __iand__(self, other): 
439          """Update a set with the intersection of itself and another.""" 
440          self._binary_sanity_check(other) 
441          self._data = (self & other)._data 
442          return self 
443   
444 -    def intersection_update(self, other): 
445          """Update a set with the intersection of itself and another.""" 
446          if isinstance(other, BaseSet): 
447              self &= other 
448          else: 
449              self._data = (self.intersection(other))._data 
450   
451 -    def __ixor__(self, other): 
452          """Update a set with the symmetric difference of itself and another.""" 
453          self._binary_sanity_check(other) 
454          self.symmetric_difference_update(other) 
455          return self 
456   
457 -    def symmetric_difference_update(self, other): 
458          """Update a set with the symmetric difference of itself and another.""" 
459          data = self._data 
460          value = True 
461          if not isinstance(other, BaseSet): 
462              other = Set(other) 
463          if self is other: 
464              self.clear() 
465          for elt in other: 
466              if elt in data: 
467                  del data[elt] 
468              else: 
469                  data[elt] = value 
470   
471 -    def __isub__(self, other): 
472          """Remove all elements of another set from this set.""" 
473          self._binary_sanity_check(other) 
474          self.difference_update(other) 
475          return self 
476   
477 -    def difference_update(self, other): 
478          """Remove all elements of another set from this set.""" 
479          data = self._data 
480          if not isinstance(other, BaseSet): 
481              other = Set(other) 
482          if self is other: 
483              self.clear() 
484          for elt in filter(data.has_key, other): 
485              del data[elt] 
486   
487      # Python dict-like mass mutations: update, clear 
488   
489 -    def update(self, iterable): 
490          """Add all values from an iterable (such as a list or file).""" 
491          self._update(iterable) 
492   
493 -    def clear(self): 
494          """Remove all elements from this set.""" 
495          self._data.clear() 
496   
497      # Single-element mutations: add, remove, discard 
498   
499 -    def add(self, element): 
500          """Add an element to a set. 
501   
502          This has no effect if the element is already present. 
503          """ 
504          try: 
505              self._data[element] = True 
506          except TypeError: 
507              transform = getattr(element, "__as_immutable__", None) 
508              if transform is None: 
509                  raise # re-raise the TypeError exception we caught 
510              self._data[transform()] = True 
511   
512 -    def remove(self, element): 
513          """Remove an element from a set; it must be a member. 
514   
515          If the element is not a member, raise a KeyError. 
516          """ 
517          try: 
518              del self._data[element] 
519          except TypeError: 
520              transform = getattr(element, "__as_temporarily_immutable__", None) 
521              if transform is None: 
522                  raise # re-raise the TypeError exception we caught 
523              del self._data[transform()] 
524   
525 -    def discard(self, element): 
526          """Remove an element from a set if it is a member. 
527   
528          If the element is not a member, do nothing. 
529          """ 
530          try: 
531              self.remove(element) 
532          except KeyError: 
533              pass 
534   
535 -    def pop(self): 
536          """Remove and return an arbitrary set element.""" 
537          return self._data.popitem()[0] 
538   
539 -    def __as_immutable__(self): 
540          # Return a copy of self as an immutable set 
541          return ImmutableSet(self) 
542   
543 -    def __as_temporarily_immutable__(self): 
544          # Return self wrapped in a temporarily immutable set 
545          return _TemporarilyImmutableSet(self) 
546   
547   
548 -class _TemporarilyImmutableSet(BaseSet): 
549      # Wrap a mutable set as if it was temporarily immutable. 
550      # This only supplies hashing and equality comparisons. 
551   
552 -    def __init__(self, set): 
553          self._set = set 
554          self._data = set._data  # Needed by ImmutableSet.__eq__() 
555   
556 -    def __hash__(self): 
557          return self._set._compute_hash() 
558   
559  # Local Variables: 
560  # tab-width:4 
561  # indent-tabs-mode:nil 
562  # End: 
563  # vim: set expandtab tabstop=4 shiftwidth=4: 
564