1# util/_collections.py
2# Copyright (C) 2005-2016 the SQLAlchemy authors and contributors
3# <see AUTHORS file>
4#
5# This module is part of SQLAlchemy and is released under
6# the MIT License: http://www.opensource.org/licenses/mit-license.php
7
8"""Collection classes and helpers."""
9
10from __future__ import absolute_import
11import weakref
12import operator
13from .compat import threading, itertools_filterfalse, string_types, \
14    binary_types
15from . import py2k
16import types
17import collections
18
19EMPTY_SET = frozenset()
20
21
22class AbstractKeyedTuple(tuple):
23    __slots__ = ()
24
25    def keys(self):
26        """Return a list of string key names for this :class:`.KeyedTuple`.
27
28        .. seealso::
29
30            :attr:`.KeyedTuple._fields`
31
32        """
33
34        return list(self._fields)
35
36
37class KeyedTuple(AbstractKeyedTuple):
38    """``tuple`` subclass that adds labeled names.
39
40    E.g.::
41
42        >>> k = KeyedTuple([1, 2, 3], labels=["one", "two", "three"])
43        >>> k.one
44        1
45        >>> k.two
46        2
47
48    Result rows returned by :class:`.Query` that contain multiple
49    ORM entities and/or column expressions make use of this
50    class to return rows.
51
52    The :class:`.KeyedTuple` exhibits similar behavior to the
53    ``collections.namedtuple()`` construct provided in the Python
54    standard library, however is architected very differently.
55    Unlike ``collections.namedtuple()``, :class:`.KeyedTuple` is
56    does not rely on creation of custom subtypes in order to represent
57    a new series of keys, instead each :class:`.KeyedTuple` instance
58    receives its list of keys in place.   The subtype approach
59    of ``collections.namedtuple()`` introduces significant complexity
60    and performance overhead, which is not necessary for the
61    :class:`.Query` object's use case.
62
63    .. versionchanged:: 0.8
64        Compatibility methods with ``collections.namedtuple()`` have been
65        added including :attr:`.KeyedTuple._fields` and
66        :meth:`.KeyedTuple._asdict`.
67
68    .. seealso::
69
70        :ref:`ormtutorial_querying`
71
72    """
73
74    def __new__(cls, vals, labels=None):
75        t = tuple.__new__(cls, vals)
76        if labels:
77            t.__dict__.update(zip(labels, vals))
78        else:
79            labels = []
80        t.__dict__['_labels'] = labels
81        return t
82
83    @property
84    def _fields(self):
85        """Return a tuple of string key names for this :class:`.KeyedTuple`.
86
87        This method provides compatibility with ``collections.namedtuple()``.
88
89        .. versionadded:: 0.8
90
91        .. seealso::
92
93            :meth:`.KeyedTuple.keys`
94
95        """
96        return tuple([l for l in self._labels if l is not None])
97
98    def __setattr__(self, key, value):
99        raise AttributeError("Can't set attribute: %s" % key)
100
101    def _asdict(self):
102        """Return the contents of this :class:`.KeyedTuple` as a dictionary.
103
104        This method provides compatibility with ``collections.namedtuple()``,
105        with the exception that the dictionary returned is **not** ordered.
106
107        .. versionadded:: 0.8
108
109        """
110        return dict((key, self.__dict__[key]) for key in self.keys())
111
112
113class _LW(AbstractKeyedTuple):
114    __slots__ = ()
115
116    def __new__(cls, vals):
117        return tuple.__new__(cls, vals)
118
119    def __reduce__(self):
120        # for pickling, degrade down to the regular
121        # KeyedTuple, thus avoiding anonymous class pickling
122        # difficulties
123        return KeyedTuple, (list(self), self._real_fields)
124
125    def _asdict(self):
126        """Return the contents of this :class:`.KeyedTuple` as a dictionary."""
127
128        d = dict(zip(self._real_fields, self))
129        d.pop(None, None)
130        return d
131
132
133class ImmutableContainer(object):
134    def _immutable(self, *arg, **kw):
135        raise TypeError("%s object is immutable" % self.__class__.__name__)
136
137    __delitem__ = __setitem__ = __setattr__ = _immutable
138
139
140class immutabledict(ImmutableContainer, dict):
141
142    clear = pop = popitem = setdefault = \
143        update = ImmutableContainer._immutable
144
145    def __new__(cls, *args):
146        new = dict.__new__(cls)
147        dict.__init__(new, *args)
148        return new
149
150    def __init__(self, *args):
151        pass
152
153    def __reduce__(self):
154        return immutabledict, (dict(self), )
155
156    def union(self, d):
157        if not d:
158            return self
159        elif not self:
160            if isinstance(d, immutabledict):
161                return d
162            else:
163                return immutabledict(d)
164        else:
165            d2 = immutabledict(self)
166            dict.update(d2, d)
167            return d2
168
169    def __repr__(self):
170        return "immutabledict(%s)" % dict.__repr__(self)
171
172
173class Properties(object):
174    """Provide a __getattr__/__setattr__ interface over a dict."""
175
176    __slots__ = '_data',
177
178    def __init__(self, data):
179        object.__setattr__(self, '_data', data)
180
181    def __len__(self):
182        return len(self._data)
183
184    def __iter__(self):
185        return iter(list(self._data.values()))
186
187    def __add__(self, other):
188        return list(self) + list(other)
189
190    def __setitem__(self, key, object):
191        self._data[key] = object
192
193    def __getitem__(self, key):
194        return self._data[key]
195
196    def __delitem__(self, key):
197        del self._data[key]
198
199    def __setattr__(self, key, obj):
200        self._data[key] = obj
201
202    def __getstate__(self):
203        return {'_data': self._data}
204
205    def __setstate__(self, state):
206        object.__setattr__(self, '_data', state['_data'])
207
208    def __getattr__(self, key):
209        try:
210            return self._data[key]
211        except KeyError:
212            raise AttributeError(key)
213
214    def __contains__(self, key):
215        return key in self._data
216
217    def as_immutable(self):
218        """Return an immutable proxy for this :class:`.Properties`."""
219
220        return ImmutableProperties(self._data)
221
222    def update(self, value):
223        self._data.update(value)
224
225    def get(self, key, default=None):
226        if key in self:
227            return self[key]
228        else:
229            return default
230
231    def keys(self):
232        return list(self._data)
233
234    def values(self):
235        return list(self._data.values())
236
237    def items(self):
238        return list(self._data.items())
239
240    def has_key(self, key):
241        return key in self._data
242
243    def clear(self):
244        self._data.clear()
245
246
247class OrderedProperties(Properties):
248    """Provide a __getattr__/__setattr__ interface with an OrderedDict
249    as backing store."""
250
251    __slots__ = ()
252
253    def __init__(self):
254        Properties.__init__(self, OrderedDict())
255
256
257class ImmutableProperties(ImmutableContainer, Properties):
258    """Provide immutable dict/object attribute to an underlying dictionary."""
259
260    __slots__ = ()
261
262
263class OrderedDict(dict):
264    """A dict that returns keys/values/items in the order they were added."""
265
266    __slots__ = '_list',
267
268    def __reduce__(self):
269        return OrderedDict, (self.items(),)
270
271    def __init__(self, ____sequence=None, **kwargs):
272        self._list = []
273        if ____sequence is None:
274            if kwargs:
275                self.update(**kwargs)
276        else:
277            self.update(____sequence, **kwargs)
278
279    def clear(self):
280        self._list = []
281        dict.clear(self)
282
283    def copy(self):
284        return self.__copy__()
285
286    def __copy__(self):
287        return OrderedDict(self)
288
289    def sort(self, *arg, **kw):
290        self._list.sort(*arg, **kw)
291
292    def update(self, ____sequence=None, **kwargs):
293        if ____sequence is not None:
294            if hasattr(____sequence, 'keys'):
295                for key in ____sequence.keys():
296                    self.__setitem__(key, ____sequence[key])
297            else:
298                for key, value in ____sequence:
299                    self[key] = value
300        if kwargs:
301            self.update(kwargs)
302
303    def setdefault(self, key, value):
304        if key not in self:
305            self.__setitem__(key, value)
306            return value
307        else:
308            return self.__getitem__(key)
309
310    def __iter__(self):
311        return iter(self._list)
312
313    def keys(self):
314        return list(self)
315
316    def values(self):
317        return [self[key] for key in self._list]
318
319    def items(self):
320        return [(key, self[key]) for key in self._list]
321
322    if py2k:
323        def itervalues(self):
324            return iter(self.values())
325
326        def iterkeys(self):
327            return iter(self)
328
329        def iteritems(self):
330            return iter(self.items())
331
332    def __setitem__(self, key, object):
333        if key not in self:
334            try:
335                self._list.append(key)
336            except AttributeError:
337                # work around Python pickle loads() with
338                # dict subclass (seems to ignore __setstate__?)
339                self._list = [key]
340        dict.__setitem__(self, key, object)
341
342    def __delitem__(self, key):
343        dict.__delitem__(self, key)
344        self._list.remove(key)
345
346    def pop(self, key, *default):
347        present = key in self
348        value = dict.pop(self, key, *default)
349        if present:
350            self._list.remove(key)
351        return value
352
353    def popitem(self):
354        item = dict.popitem(self)
355        self._list.remove(item[0])
356        return item
357
358
359class OrderedSet(set):
360    def __init__(self, d=None):
361        set.__init__(self)
362        self._list = []
363        if d is not None:
364            self._list = unique_list(d)
365            set.update(self, self._list)
366        else:
367            self._list = []
368
369    def add(self, element):
370        if element not in self:
371            self._list.append(element)
372        set.add(self, element)
373
374    def remove(self, element):
375        set.remove(self, element)
376        self._list.remove(element)
377
378    def insert(self, pos, element):
379        if element not in self:
380            self._list.insert(pos, element)
381        set.add(self, element)
382
383    def discard(self, element):
384        if element in self:
385            self._list.remove(element)
386            set.remove(self, element)
387
388    def clear(self):
389        set.clear(self)
390        self._list = []
391
392    def __getitem__(self, key):
393        return self._list[key]
394
395    def __iter__(self):
396        return iter(self._list)
397
398    def __add__(self, other):
399        return self.union(other)
400
401    def __repr__(self):
402        return '%s(%r)' % (self.__class__.__name__, self._list)
403
404    __str__ = __repr__
405
406    def update(self, iterable):
407        for e in iterable:
408            if e not in self:
409                self._list.append(e)
410                set.add(self, e)
411        return self
412
413    __ior__ = update
414
415    def union(self, other):
416        result = self.__class__(self)
417        result.update(other)
418        return result
419
420    __or__ = union
421
422    def intersection(self, other):
423        other = set(other)
424        return self.__class__(a for a in self if a in other)
425
426    __and__ = intersection
427
428    def symmetric_difference(self, other):
429        other = set(other)
430        result = self.__class__(a for a in self if a not in other)
431        result.update(a for a in other if a not in self)
432        return result
433
434    __xor__ = symmetric_difference
435
436    def difference(self, other):
437        other = set(other)
438        return self.__class__(a for a in self if a not in other)
439
440    __sub__ = difference
441
442    def intersection_update(self, other):
443        other = set(other)
444        set.intersection_update(self, other)
445        self._list = [a for a in self._list if a in other]
446        return self
447
448    __iand__ = intersection_update
449
450    def symmetric_difference_update(self, other):
451        set.symmetric_difference_update(self, other)
452        self._list = [a for a in self._list if a in self]
453        self._list += [a for a in other._list if a in self]
454        return self
455
456    __ixor__ = symmetric_difference_update
457
458    def difference_update(self, other):
459        set.difference_update(self, other)
460        self._list = [a for a in self._list if a in self]
461        return self
462
463    __isub__ = difference_update
464
465
466class IdentitySet(object):
467    """A set that considers only object id() for uniqueness.
468
469    This strategy has edge cases for builtin types- it's possible to have
470    two 'foo' strings in one of these sets, for example.  Use sparingly.
471
472    """
473
474    _working_set = set
475
476    def __init__(self, iterable=None):
477        self._members = dict()
478        if iterable:
479            for o in iterable:
480                self.add(o)
481
482    def add(self, value):
483        self._members[id(value)] = value
484
485    def __contains__(self, value):
486        return id(value) in self._members
487
488    def remove(self, value):
489        del self._members[id(value)]
490
491    def discard(self, value):
492        try:
493            self.remove(value)
494        except KeyError:
495            pass
496
497    def pop(self):
498        try:
499            pair = self._members.popitem()
500            return pair[1]
501        except KeyError:
502            raise KeyError('pop from an empty set')
503
504    def clear(self):
505        self._members.clear()
506
507    def __cmp__(self, other):
508        raise TypeError('cannot compare sets using cmp()')
509
510    def __eq__(self, other):
511        if isinstance(other, IdentitySet):
512            return self._members == other._members
513        else:
514            return False
515
516    def __ne__(self, other):
517        if isinstance(other, IdentitySet):
518            return self._members != other._members
519        else:
520            return True
521
522    def issubset(self, iterable):
523        other = type(self)(iterable)
524
525        if len(self) > len(other):
526            return False
527        for m in itertools_filterfalse(other._members.__contains__,
528                                       iter(self._members.keys())):
529            return False
530        return True
531
532    def __le__(self, other):
533        if not isinstance(other, IdentitySet):
534            return NotImplemented
535        return self.issubset(other)
536
537    def __lt__(self, other):
538        if not isinstance(other, IdentitySet):
539            return NotImplemented
540        return len(self) < len(other) and self.issubset(other)
541
542    def issuperset(self, iterable):
543        other = type(self)(iterable)
544
545        if len(self) < len(other):
546            return False
547
548        for m in itertools_filterfalse(self._members.__contains__,
549                                       iter(other._members.keys())):
550            return False
551        return True
552
553    def __ge__(self, other):
554        if not isinstance(other, IdentitySet):
555            return NotImplemented
556        return self.issuperset(other)
557
558    def __gt__(self, other):
559        if not isinstance(other, IdentitySet):
560            return NotImplemented
561        return len(self) > len(other) and self.issuperset(other)
562
563    def union(self, iterable):
564        result = type(self)()
565        # testlib.pragma exempt:__hash__
566        members = self._member_id_tuples()
567        other = _iter_id(iterable)
568        result._members.update(self._working_set(members).union(other))
569        return result
570
571    def __or__(self, other):
572        if not isinstance(other, IdentitySet):
573            return NotImplemented
574        return self.union(other)
575
576    def update(self, iterable):
577        self._members = self.union(iterable)._members
578
579    def __ior__(self, other):
580        if not isinstance(other, IdentitySet):
581            return NotImplemented
582        self.update(other)
583        return self
584
585    def difference(self, iterable):
586        result = type(self)()
587        # testlib.pragma exempt:__hash__
588        members = self._member_id_tuples()
589        other = _iter_id(iterable)
590        result._members.update(self._working_set(members).difference(other))
591        return result
592
593    def __sub__(self, other):
594        if not isinstance(other, IdentitySet):
595            return NotImplemented
596        return self.difference(other)
597
598    def difference_update(self, iterable):
599        self._members = self.difference(iterable)._members
600
601    def __isub__(self, other):
602        if not isinstance(other, IdentitySet):
603            return NotImplemented
604        self.difference_update(other)
605        return self
606
607    def intersection(self, iterable):
608        result = type(self)()
609        # testlib.pragma exempt:__hash__
610        members = self._member_id_tuples()
611        other = _iter_id(iterable)
612        result._members.update(self._working_set(members).intersection(other))
613        return result
614
615    def __and__(self, other):
616        if not isinstance(other, IdentitySet):
617            return NotImplemented
618        return self.intersection(other)
619
620    def intersection_update(self, iterable):
621        self._members = self.intersection(iterable)._members
622
623    def __iand__(self, other):
624        if not isinstance(other, IdentitySet):
625            return NotImplemented
626        self.intersection_update(other)
627        return self
628
629    def symmetric_difference(self, iterable):
630        result = type(self)()
631        # testlib.pragma exempt:__hash__
632        members = self._member_id_tuples()
633        other = _iter_id(iterable)
634        result._members.update(
635            self._working_set(members).symmetric_difference(other))
636        return result
637
638    def _member_id_tuples(self):
639        return ((id(v), v) for v in self._members.values())
640
641    def __xor__(self, other):
642        if not isinstance(other, IdentitySet):
643            return NotImplemented
644        return self.symmetric_difference(other)
645
646    def symmetric_difference_update(self, iterable):
647        self._members = self.symmetric_difference(iterable)._members
648
649    def __ixor__(self, other):
650        if not isinstance(other, IdentitySet):
651            return NotImplemented
652        self.symmetric_difference(other)
653        return self
654
655    def copy(self):
656        return type(self)(iter(self._members.values()))
657
658    __copy__ = copy
659
660    def __len__(self):
661        return len(self._members)
662
663    def __iter__(self):
664        return iter(self._members.values())
665
666    def __hash__(self):
667        raise TypeError('set objects are unhashable')
668
669    def __repr__(self):
670        return '%s(%r)' % (type(self).__name__, list(self._members.values()))
671
672
673class WeakSequence(object):
674    def __init__(self, __elements=()):
675        self._storage = [
676            weakref.ref(element, self._remove) for element in __elements
677        ]
678
679    def append(self, item):
680        self._storage.append(weakref.ref(item, self._remove))
681
682    def _remove(self, ref):
683        self._storage.remove(ref)
684
685    def __len__(self):
686        return len(self._storage)
687
688    def __iter__(self):
689        return (obj for obj in
690                (ref() for ref in self._storage) if obj is not None)
691
692    def __getitem__(self, index):
693        try:
694            obj = self._storage[index]
695        except KeyError:
696            raise IndexError("Index %s out of range" % index)
697        else:
698            return obj()
699
700
701class OrderedIdentitySet(IdentitySet):
702    class _working_set(OrderedSet):
703        # a testing pragma: exempt the OIDS working set from the test suite's
704        # "never call the user's __hash__" assertions.  this is a big hammer,
705        # but it's safe here: IDS operates on (id, instance) tuples in the
706        # working set.
707        __sa_hash_exempt__ = True
708
709    def __init__(self, iterable=None):
710        IdentitySet.__init__(self)
711        self._members = OrderedDict()
712        if iterable:
713            for o in iterable:
714                self.add(o)
715
716
717class PopulateDict(dict):
718    """A dict which populates missing values via a creation function.
719
720    Note the creation function takes a key, unlike
721    collections.defaultdict.
722
723    """
724
725    def __init__(self, creator):
726        self.creator = creator
727
728    def __missing__(self, key):
729        self[key] = val = self.creator(key)
730        return val
731
732# Define collections that are capable of storing
733# ColumnElement objects as hashable keys/elements.
734# At this point, these are mostly historical, things
735# used to be more complicated.
736column_set = set
737column_dict = dict
738ordered_column_set = OrderedSet
739populate_column_dict = PopulateDict
740
741
742_getters = PopulateDict(operator.itemgetter)
743
744_property_getters = PopulateDict(
745    lambda idx: property(operator.itemgetter(idx)))
746
747
748def unique_list(seq, hashfunc=None):
749    seen = set()
750    seen_add = seen.add
751    if not hashfunc:
752        return [x for x in seq
753                if x not in seen
754                and not seen_add(x)]
755    else:
756        return [x for x in seq
757                if hashfunc(x) not in seen
758                and not seen_add(hashfunc(x))]
759
760
761class UniqueAppender(object):
762    """Appends items to a collection ensuring uniqueness.
763
764    Additional appends() of the same object are ignored.  Membership is
765    determined by identity (``is a``) not equality (``==``).
766    """
767
768    def __init__(self, data, via=None):
769        self.data = data
770        self._unique = {}
771        if via:
772            self._data_appender = getattr(data, via)
773        elif hasattr(data, 'append'):
774            self._data_appender = data.append
775        elif hasattr(data, 'add'):
776            self._data_appender = data.add
777
778    def append(self, item):
779        id_ = id(item)
780        if id_ not in self._unique:
781            self._data_appender(item)
782            self._unique[id_] = True
783
784    def __iter__(self):
785        return iter(self.data)
786
787
788def coerce_generator_arg(arg):
789    if len(arg) == 1 and isinstance(arg[0], types.GeneratorType):
790        return list(arg[0])
791    else:
792        return arg
793
794
795def to_list(x, default=None):
796    if x is None:
797        return default
798    if not isinstance(x, collections.Iterable) or \
799            isinstance(x, string_types + binary_types):
800        return [x]
801    elif isinstance(x, list):
802        return x
803    else:
804        return list(x)
805
806
807def has_intersection(set_, iterable):
808    """return True if any items of set_ are present in iterable.
809
810    Goes through special effort to ensure __hash__ is not called
811    on items in iterable that don't support it.
812
813    """
814    # TODO: optimize, write in C, etc.
815    return bool(
816        set_.intersection([i for i in iterable if i.__hash__])
817    )
818
819
820def to_set(x):
821    if x is None:
822        return set()
823    if not isinstance(x, set):
824        return set(to_list(x))
825    else:
826        return x
827
828
829def to_column_set(x):
830    if x is None:
831        return column_set()
832    if not isinstance(x, column_set):
833        return column_set(to_list(x))
834    else:
835        return x
836
837
838def update_copy(d, _new=None, **kw):
839    """Copy the given dict and update with the given values."""
840
841    d = d.copy()
842    if _new:
843        d.update(_new)
844    d.update(**kw)
845    return d
846
847
848def flatten_iterator(x):
849    """Given an iterator of which further sub-elements may also be
850    iterators, flatten the sub-elements into a single iterator.
851
852    """
853    for elem in x:
854        if not isinstance(elem, str) and hasattr(elem, '__iter__'):
855            for y in flatten_iterator(elem):
856                yield y
857        else:
858            yield elem
859
860
861class LRUCache(dict):
862    """Dictionary with 'squishy' removal of least
863    recently used items.
864
865    Note that either get() or [] should be used here, but
866    generally its not safe to do an "in" check first as the dictionary
867    can change subsequent to that call.
868
869    """
870
871    def __init__(self, capacity=100, threshold=.5):
872        self.capacity = capacity
873        self.threshold = threshold
874        self._counter = 0
875        self._mutex = threading.Lock()
876
877    def _inc_counter(self):
878        self._counter += 1
879        return self._counter
880
881    def get(self, key, default=None):
882        item = dict.get(self, key, default)
883        if item is not default:
884            item[2] = self._inc_counter()
885            return item[1]
886        else:
887            return default
888
889    def __getitem__(self, key):
890        item = dict.__getitem__(self, key)
891        item[2] = self._inc_counter()
892        return item[1]
893
894    def values(self):
895        return [i[1] for i in dict.values(self)]
896
897    def setdefault(self, key, value):
898        if key in self:
899            return self[key]
900        else:
901            self[key] = value
902            return value
903
904    def __setitem__(self, key, value):
905        item = dict.get(self, key)
906        if item is None:
907            item = [key, value, self._inc_counter()]
908            dict.__setitem__(self, key, item)
909        else:
910            item[1] = value
911        self._manage_size()
912
913    def _manage_size(self):
914        if not self._mutex.acquire(False):
915            return
916        try:
917            while len(self) > self.capacity + self.capacity * self.threshold:
918                by_counter = sorted(dict.values(self),
919                                    key=operator.itemgetter(2),
920                                    reverse=True)
921                for item in by_counter[self.capacity:]:
922                    try:
923                        del self[item[0]]
924                    except KeyError:
925                        # deleted elsewhere; skip
926                        continue
927        finally:
928            self._mutex.release()
929
930
931_lw_tuples = LRUCache(100)
932
933
934def lightweight_named_tuple(name, fields):
935    hash_ = (name, ) + tuple(fields)
936    tp_cls = _lw_tuples.get(hash_)
937    if tp_cls:
938        return tp_cls
939
940    tp_cls = type(
941        name, (_LW,),
942        dict([
943            (field, _property_getters[idx])
944            for idx, field in enumerate(fields) if field is not None
945        ] + [('__slots__', ())])
946    )
947
948    tp_cls._real_fields = fields
949    tp_cls._fields = tuple([f for f in fields if f is not None])
950
951    _lw_tuples[hash_] = tp_cls
952    return tp_cls
953
954
955class ScopedRegistry(object):
956    """A Registry that can store one or multiple instances of a single
957    class on the basis of a "scope" function.
958
959    The object implements ``__call__`` as the "getter", so by
960    calling ``myregistry()`` the contained object is returned
961    for the current scope.
962
963    :param createfunc:
964      a callable that returns a new object to be placed in the registry
965
966    :param scopefunc:
967      a callable that will return a key to store/retrieve an object.
968    """
969
970    def __init__(self, createfunc, scopefunc):
971        """Construct a new :class:`.ScopedRegistry`.
972
973        :param createfunc:  A creation function that will generate
974          a new value for the current scope, if none is present.
975
976        :param scopefunc:  A function that returns a hashable
977          token representing the current scope (such as, current
978          thread identifier).
979
980        """
981        self.createfunc = createfunc
982        self.scopefunc = scopefunc
983        self.registry = {}
984
985    def __call__(self):
986        key = self.scopefunc()
987        try:
988            return self.registry[key]
989        except KeyError:
990            return self.registry.setdefault(key, self.createfunc())
991
992    def has(self):
993        """Return True if an object is present in the current scope."""
994
995        return self.scopefunc() in self.registry
996
997    def set(self, obj):
998        """Set the value for the current scope."""
999
1000        self.registry[self.scopefunc()] = obj
1001
1002    def clear(self):
1003        """Clear the current scope, if any."""
1004
1005        try:
1006            del self.registry[self.scopefunc()]
1007        except KeyError:
1008            pass
1009
1010
1011class ThreadLocalRegistry(ScopedRegistry):
1012    """A :class:`.ScopedRegistry` that uses a ``threading.local()``
1013    variable for storage.
1014
1015    """
1016
1017    def __init__(self, createfunc):
1018        self.createfunc = createfunc
1019        self.registry = threading.local()
1020
1021    def __call__(self):
1022        try:
1023            return self.registry.value
1024        except AttributeError:
1025            val = self.registry.value = self.createfunc()
1026            return val
1027
1028    def has(self):
1029        return hasattr(self.registry, "value")
1030
1031    def set(self, obj):
1032        self.registry.value = obj
1033
1034    def clear(self):
1035        try:
1036            del self.registry.value
1037        except AttributeError:
1038            pass
1039
1040
1041def _iter_id(iterable):
1042    """Generator: ((id(o), o) for o in iterable)."""
1043
1044    for item in iterable:
1045        yield id(item), item
1046