Merge pull request #228 from zopefoundation/issue224

Let subclasses of BaseAdapterRegistry customize the data structures.

3 files changed, 901 insertions, 26 deletions

diff --git a/src/zope/interface/adapter.py b/src/zope/interface/adapter.py
index 86eedc3..8242b6b 100644
--- a/src/zope/interface/adapter.py
+++ b/src/zope/interface/adapter.py
@@ -13,6 +13,7 @@
 ##############################################################################
 """Adapter management
 """
+import itertools
 import weakref
 
 from zope.interface import implementer
@@ -30,6 +31,7 @@ __all__ = [
     'VerifyingAdapterRegistry',
 ]
 
+# In the CPython implementation,
 # ``tuple`` and ``list`` cooperate so that ``tuple([some list])``
 # directly allocates and iterates at the C level without using a
 # Python iterator. That's not the case for
@@ -46,8 +48,76 @@ __all__ = [
 # ``tuple(map(lambda t: t, range(10)))`` -> 958ns
 #
 # All three have substantial variance.
+##
+# On PyPy, this is also the best option.
+##
+# PyPy 2.7.18-7.3.3
+# ``tuple([t fon t in range(10)])``      -> 128ns
+# ``tuple(t for t in range(10))``        -> 175ns
+# ``tuple(map(lambda t: t, range(10)))`` -> 153ns
+##
+# PyPy 3.7.9 7.3.3-beta
+# ``tuple([t fon t in range(10)])``      ->  82ns
+# ``tuple(t for t in range(10))``        -> 177ns
+# ``tuple(map(lambda t: t, range(10)))`` -> 168ns
+#
 
 class BaseAdapterRegistry(object):
+    """
+    A basic implementation of the data storage and algorithms required
+    for a :class:`zope.interface.interfaces.IAdapterRegistry`.
+
+    Subclasses can set the following attributes to control how the data
+    is stored; in particular, these hooks can be helpful for ZODB
+    persistence. They can be class attributes that are the named (or similar) type, or
+    they can be methods that act as a constructor for an object that behaves
+    like the types defined here; this object will not assume that they are type
+    objects, but subclasses are free to do so:
+
+    _sequenceType = list
+      This is the type used for our two mutable top-level "byorder" sequences.
+      Must support mutation operations like ``append()`` and ``del seq[index]``.
+      These are usually small (< 10). Although at least one of them is
+      accessed when performing lookups or queries on this object, the other
+      is untouched. In many common scenarios, both are only required when
+      mutating registrations and subscriptions (like what
+      :meth:`zope.interface.interfaces.IComponents.registerUtility` does).
+      This use pattern makes it an ideal candidate to be a
+      :class:`~persistent.list.PersistentList`.
+    _leafSequenceType = tuple
+      This is the type used for the leaf sequences of subscribers.
+      It could be set to a ``PersistentList`` to avoid many unnecessary data
+      loads when subscribers aren't being used. Mutation operations are directed
+      through :meth:`_addValueToLeaf` and :meth:`_removeValueFromLeaf`; if you use
+      a mutable type, you'll need to override those.
+    _mappingType = dict
+      This is the mutable mapping type used for the keyed mappings.
+      A :class:`~persistent.mapping.PersistentMapping`
+      could be used to help reduce the number of data loads when the registry is large
+      and parts of it are rarely used. Further reductions in data loads can come from
+      using a :class:`~BTrees.OOBTree.OOBTree`, but care is required
+      to be sure that all required/provided
+      values are fully ordered (e.g., no required or provided values that are classes
+      can be used).
+    _providedType = dict
+      This is the mutable mapping type used for the ``_provided`` mapping.
+      This is separate from the generic mapping type because the values
+      are always integers, so one might choose to use a more optimized data
+      structure such as a :class:`~BTrees.OIBTree.OIBTree`.
+      The same caveats regarding key types
+      apply as for ``_mappingType``.
+
+    It is possible to also set these on an instance, but because of the need to
+    potentially also override :meth:`_addValueToLeaf` and :meth:`_removeValueFromLeaf`,
+    this may be less useful in a persistent scenario; using a subclass is recommended.
+
+    .. versionchanged:: 5.3.0
+        Add support for customizing the way internal data
+        structures are created.
+    .. versionchanged:: 5.3.0
+        Add methods :meth:`rebuild`, :meth:`allRegistrations`
+        and :meth:`allSubscriptions`.
+    """
 
     # List of methods copied from lookup sub-objects:
     _delegated = ('lookup', 'queryMultiAdapter', 'lookup1', 'queryAdapter',
@@ -73,15 +143,15 @@ class BaseAdapterRegistry(object):
         # but for order == 2 (that is, self._adapters[2]), we have:
         #   {r1 -> {r2 -> {provided -> {name -> value}}}}
         #
-        self._adapters = []
+        self._adapters = self._sequenceType()
 
         # {order -> {required -> {provided -> {name -> [value]}}}}
         # where the remarks about adapters above apply
-        self._subscribers = []
+        self._subscribers = self._sequenceType()
 
         # Set, with a reference count, keeping track of the interfaces
         # for which we have provided components:
-        self._provided = {}
+        self._provided = self._providedType()
 
         # Create ``_v_lookup`` object to perform lookup.  We make this a
         # separate object to to make it easier to implement just the
@@ -106,6 +176,12 @@ class BaseAdapterRegistry(object):
         self.__bases__ = bases
 
     def _setBases(self, bases):
+        """
+        If subclasses need to track when ``__bases__`` changes, they
+        can override this method.
+
+        Subclasses must still call this method.
+        """
         self.__dict__['__bases__'] = bases
         self.ro = ro.ro(self)
         self.changed(self)
@@ -119,6 +195,65 @@ class BaseAdapterRegistry(object):
         for name in self._delegated:
             self.__dict__[name] = getattr(self._v_lookup, name)
 
+    # Hooks for subclasses to define the types of objects used in
+    # our data structures.
+    # These have to be documented in the docstring, instead of local
+    # comments, because Sphinx autodoc ignores the comment and just writes
+    # "alias of list"
+    _sequenceType = list
+    _leafSequenceType = tuple
+    _mappingType = dict
+    _providedType = dict
+
+    def _addValueToLeaf(self, existing_leaf_sequence, new_item):
+        """
+        Add the value *new_item* to the *existing_leaf_sequence*, which may
+        be ``None``.
+
+        Subclasses that redefine `_leafSequenceType` should override this method.
+
+        :param existing_leaf_sequence:
+            If *existing_leaf_sequence* is not *None*, it will be an instance
+            of `_leafSequenceType`. (Unless the object has been unpickled
+            from an old pickle and the class definition has changed, in which case
+            it may be an instance of a previous definition, commonly a `tuple`.)
+
+        :return:
+           This method returns the new value to be stored. It may mutate the
+           sequence in place if it was not ``None`` and the type is mutable, but
+           it must also return it.
+
+        .. versionadded:: 5.3.0
+        """
+        if existing_leaf_sequence is None:
+            return (new_item,)
+        return existing_leaf_sequence + (new_item,)
+
+    def _removeValueFromLeaf(self, existing_leaf_sequence, to_remove):
+        """
+        Remove the item *to_remove* from the (non-``None``, non-empty)
+        *existing_leaf_sequence* and return the mutated sequence.
+
+        Subclasses that redefine `_leafSequenceType` should override
+        this method.
+
+        If there is more than one item that is equal to *to_remove*
+        they must all be removed.
+
+        :param existing_leaf_sequence:
+           As for `_addValueToLeaf`, probably an instance of
+           `_leafSequenceType` but possibly an older type; never `None`.
+        :return:
+           A version of *existing_leaf_sequence* with all items equal to
+           *to_remove* removed. Must not return `None`. However,
+           returning an empty
+           object, even of another type such as the empty tuple, ``()`` is
+           explicitly allowed; such an object will never be stored.
+
+        .. versionadded:: 5.3.0
+        """
+        return tuple([v for v in existing_leaf_sequence if v != to_remove])
+
     def changed(self, originally_changed):
         self._generation += 1
         self._v_lookup.changed(originally_changed)
@@ -135,14 +270,14 @@ class BaseAdapterRegistry(object):
         order = len(required)
         byorder = self._adapters
         while len(byorder) <= order:
-            byorder.append({})
+            byorder.append(self._mappingType())
         components = byorder[order]
         key = required + (provided,)
 
         for k in key:
             d = components.get(k)
             if d is None:
-                d = {}
+                d = self._mappingType()
                 components[k] = d
             components = d
 
@@ -177,6 +312,49 @@ class BaseAdapterRegistry(object):
 
         return components.get(name)
 
+    @classmethod
+    def _allKeys(cls, components, i, parent_k=()):
+        if i == 0:
+            for k, v in components.items():
+                yield parent_k + (k,), v
+        else:
+            for k, v in components.items():
+                new_parent_k = parent_k + (k,)
+                for x, y in cls._allKeys(v, i - 1, new_parent_k):
+                    yield x, y
+
+    def _all_entries(self, byorder):
+        # Recurse through the mapping levels of the `byorder` sequence,
+        # reconstructing a flattened sequence of ``(required, provided, name, value)``
+        # tuples that can be used to reconstruct the sequence with the appropriate
+        # registration methods.
+        #
+        # Locally reference the `byorder` data; it might be replaced while
+        # this method is running (see ``rebuild``).
+        for i, components in enumerate(byorder):
+            # We will have *i* levels of dictionaries to go before
+            # we get to the leaf.
+            for key, value in self._allKeys(components, i + 1):
+                assert len(key) == i + 2
+                required = key[:i]
+                provided = key[-2]
+                name = key[-1]
+                yield (required, provided, name, value)
+
+    def allRegistrations(self):
+        """
+        Yields tuples ``(required, provided, name, value)`` for all
+        the registrations that this object holds.
+
+        These tuples could be passed as the arguments to the
+        :meth:`register` method on another adapter registry to
+        duplicate the registrations this object holds.
+
+        .. versionadded:: 5.3.0
+        """
+        for t in self._all_entries(self._adapters):
+            yield t
+
     def unregister(self, required, provided, name, value=None):
         required = tuple([_convert_None_to_Interface(r) for r in required])
         order = len(required)
@@ -231,18 +409,18 @@ class BaseAdapterRegistry(object):
         order = len(required)
         byorder = self._subscribers
         while len(byorder) <= order:
-            byorder.append({})
+            byorder.append(self._mappingType())
         components = byorder[order]
         key = required + (provided,)
 
         for k in key:
             d = components.get(k)
             if d is None:
-                d = {}
+                d = self._mappingType()
                 components[k] = d
             components = d
 
-        components[name] = components.get(name, ()) + (value, )
+        components[name] = self._addValueToLeaf(components.get(name), value)
 
         if provided is not None:
             n = self._provided.get(provided, 0) + 1
@@ -252,6 +430,21 @@ class BaseAdapterRegistry(object):
 
         self.changed(self)
 
+    def allSubscriptions(self):
+        """
+        Yields tuples ``(required, provided, value)`` for all the
+        subscribers that this object holds.
+
+        These tuples could be passed as the arguments to the
+        :meth:`subscribe` method on another adapter registry to
+        duplicate the registrations this object holds.
+
+        .. versionadded:: 5.3.0
+        """
+        for required, provided, _name, value in self._all_entries(self._subscribers):
+            for v in value:
+                yield (required, provided, v)
+
     def unsubscribe(self, required, provided, value=None):
         required = tuple([_convert_None_to_Interface(r) for r in required])
         order = len(required)
@@ -274,13 +467,22 @@ class BaseAdapterRegistry(object):
         if not old:
             # this is belt-and-suspenders against the failure of cleanup below
             return  # pragma: no cover
-
+        len_old = len(old)
         if value is None:
+            # Removing everything; note that the type of ``new`` won't
+            # necessarily match the ``_leafSequenceType``, but that's
+            # OK because we're about to delete the entire entry
+            # anyway.
             new = ()
         else:
-            new = tuple([v for v in old if v != value])
-
-        if new == old:
+            new = self._removeValueFromLeaf(old, value)
+        # ``new`` may be the same object as ``old``, just mutated in place,
+        # so we cannot compare it to ``old`` to check for changes. Remove
+        # our reference to it now to avoid trying to do so below.
+        del old
+
+        if len(new) == len_old:
+            # No changes, so nothing could have been removed.
             return
 
         if new:
@@ -303,13 +505,68 @@ class BaseAdapterRegistry(object):
                 del byorder[-1]
 
         if provided is not None:
-            n = self._provided[provided] + len(new) - len(old)
+            n = self._provided[provided] + len(new) - len_old
             if n == 0:
                 del self._provided[provided]
                 self._v_lookup.remove_extendor(provided)
+            else:
+                self._provided[provided] = n
 
         self.changed(self)
 
+    def rebuild(self):
+        """
+        Rebuild (and replace) all the internal data structures of this
+        object.
+
+        This is useful, especially for persistent implementations, if
+        you suspect an issue with reference counts keeping interfaces
+        alive even though they are no longer used.
+
+        It is also useful if you or a subclass change the data types
+        (``_mappingType`` and friends) that are to be used.
+
+        This method replaces all internal data structures with new objects;
+        it specifically does not re-use any storage.
+
+        .. versionadded:: 5.3.0
+        """
+
+        # Grab the iterators, we're about to discard their data.
+        registrations = self.allRegistrations()
+        subscriptions = self.allSubscriptions()
+
+        def buffer(it):
+            # The generator doesn't actually start running until we
+            # ask for its next(), by which time the attributes will change
+            # unless we do so before calling __init__.
+            try:
+                first = next(it)
+            except StopIteration:
+                return iter(())
+
+            return itertools.chain((first,), it)
+
+        registrations = buffer(registrations)
+        subscriptions = buffer(subscriptions)
+
+
+        # Replace the base data structures as well as _v_lookup.
+        self.__init__(self.__bases__)
+        # Re-register everything previously registered and subscribed.
+        #
+        # XXX: This is going to call ``self.changed()`` a lot, all of
+        # which is unnecessary (because ``self.__init__`` just
+        # re-created those dependent objects and also called
+        # ``self.changed()``). Is this a bottleneck that needs fixed?
+        # (We could do ``self.changed = lambda _: None`` before
+        # beginning and remove it after to disable the presumably expensive
+        # part of passing that notification to the change of objects.)
+        for args in registrations:
+            self.register(*args)
+        for args in subscriptions:
+            self.subscribe(*args)
+
     # XXX hack to fake out twisted's use of a private api.  We need to get them
     # to use the new registed method.
     def get(self, _): # pragma: no cover
@@ -630,6 +887,10 @@ class AdapterLookup(AdapterLookupBase, LookupBase):
 
 @implementer(IAdapterRegistry)
 class AdapterRegistry(BaseAdapterRegistry):
+    """
+    A full implementation of ``IAdapterRegistry`` that adds support for
+    sub-registries.
+    """
 
     LookupClass = AdapterLookup
 
@@ -670,6 +931,9 @@ class VerifyingAdapterLookup(AdapterLookupBase, VerifyingBase):
 
 @implementer(IAdapterRegistry)
 class VerifyingAdapterRegistry(BaseAdapterRegistry):
+    """
+    The most commonly-used adapter registry.
+    """
 
     LookupClass = VerifyingAdapterLookup
 
diff --git a/src/zope/interface/tests/test_adapter.py b/src/zope/interface/tests/test_adapter.py
index e9ede66..a80e4f1 100644
--- a/src/zope/interface/tests/test_adapter.py
+++ b/src/zope/interface/tests/test_adapter.py
@@ -47,10 +47,70 @@ def _makeInterfaces():
     return IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1
 
 
+# Custom types to use as part of the AdapterRegistry data structures.
+# Our custom types do strict type checking to make sure
+# types propagate through the data tree as expected.
+class CustomDataTypeBase(object):
+    _data = None
+    def __getitem__(self, name):
+        return self._data[name]
+
+    def __setitem__(self, name, value):
+        self._data[name] = value
+
+    def __delitem__(self, name):
+        del self._data[name]
+
+    def __len__(self):
+        return len(self._data)
+
+    def __contains__(self, name):
+        return name in self._data
+
+    def __eq__(self, other):
+        if other is self:
+            return True
+        # pylint:disable=unidiomatic-typecheck
+        if type(other) != type(self):
+            return False
+        return other._data == self._data
+
+    def __repr__(self):
+        return repr(self._data)
+
+class CustomMapping(CustomDataTypeBase):
+    def __init__(self, other=None):
+        self._data = {}
+        if other:
+            self._data.update(other)
+        self.get = self._data.get
+        self.items = self._data.items
+
+
+class CustomSequence(CustomDataTypeBase):
+    def __init__(self, other=None):
+        self._data = []
+        if other:
+            self._data.extend(other)
+        self.append = self._data.append
+
+class CustomLeafSequence(CustomSequence):
+    pass
+
+class CustomProvided(CustomMapping):
+    pass
+
+
 class BaseAdapterRegistryTests(unittest.TestCase):
 
-    def _getTargetClass(self):
+    maxDiff = None
+
+    def _getBaseAdapterRegistry(self):
         from zope.interface.adapter import BaseAdapterRegistry
+        return BaseAdapterRegistry
+
+    def _getTargetClass(self):
+        BaseAdapterRegistry = self._getBaseAdapterRegistry()
         class _CUT(BaseAdapterRegistry):
             class LookupClass(object):
                 _changed = _extendors = ()
@@ -70,12 +130,23 @@ class BaseAdapterRegistryTests(unittest.TestCase):
     def _makeOne(self):
         return self._getTargetClass()()
 
+    def _getMappingType(self):
+        return dict
+
+    def _getProvidedType(self):
+        return dict
+
+    def _getMutableListType(self):
+        return list
+
+    def _getLeafSequenceType(self):
+        return tuple
+
     def test_lookup_delegation(self):
         CUT = self._getTargetClass()
         registry = CUT()
         for name in CUT._delegated:
-            self.assertTrue(
-                getattr(registry, name) is getattr(registry._v_lookup, name))
+            self.assertIs(getattr(registry, name), getattr(registry._v_lookup, name))
 
     def test__generation_on_first_creation(self):
         registry = self._makeOne()
@@ -97,13 +168,153 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         registry.__bases__ = (_Base,)
         self.assertEqual(registry._generation, 2)
 
+    def _check_basic_types_of_adapters(self, registry, expected_order=2):
+        self.assertEqual(len(registry._adapters), expected_order) # order 0 and order 1
+        self.assertIsInstance(registry._adapters, self._getMutableListType())
+        MT = self._getMappingType()
+        for mapping in registry._adapters:
+            self.assertIsInstance(mapping, MT)
+        self.assertEqual(registry._adapters[0], MT())
+        self.assertIsInstance(registry._adapters[1], MT)
+        self.assertEqual(len(registry._adapters[expected_order - 1]), 1)
+
+    def _check_basic_types_of_subscribers(self, registry, expected_order=2):
+        self.assertEqual(len(registry._subscribers), expected_order) # order 0 and order 1
+        self.assertIsInstance(registry._subscribers, self._getMutableListType())
+        MT = self._getMappingType()
+        for mapping in registry._subscribers:
+            self.assertIsInstance(mapping, MT)
+        if expected_order:
+            self.assertEqual(registry._subscribers[0], MT())
+            self.assertIsInstance(registry._subscribers[1], MT)
+            self.assertEqual(len(registry._subscribers[expected_order - 1]), 1)
+
     def test_register(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         registry.register([IB0], IR0, '', 'A1')
         self.assertEqual(registry.registered([IB0], IR0, ''), 'A1')
-        self.assertEqual(len(registry._adapters), 2) #order 0 and order 1
         self.assertEqual(registry._generation, 2)
+        self._check_basic_types_of_adapters(registry)
+        MT = self._getMappingType()
+        self.assertEqual(registry._adapters[1], MT({
+            IB0: MT({
+                IR0: MT({'': 'A1'})
+            })
+        }))
+        PT = self._getProvidedType()
+        self.assertEqual(registry._provided, PT({
+            IR0: 1
+        }))
+
+        registered = list(registry.allRegistrations())
+        self.assertEqual(registered, [(
+            (IB0,), # required
+            IR0, # provided
+            '', # name
+            'A1' # value
+        )])
+
+    def test_register_multiple_allRegistrations(self):
+        IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
+        registry = self._makeOne()
+        # Use several different depths and several different names
+        registry.register([], IR0, '', 'A1')
+        registry.register([], IR0, 'name1', 'A2')
+
+        registry.register([IB0], IR0, '', 'A1')
+        registry.register([IB0], IR0, 'name2', 'A2')
+        registry.register([IB0], IR1, '', 'A3')
+        registry.register([IB0], IR1, 'name3', 'A4')
+
+        registry.register([IB0, IB1], IR0, '', 'A1')
+        registry.register([IB0, IB2], IR0, 'name2', 'A2')
+        registry.register([IB0, IB2], IR1, 'name4', 'A4')
+        registry.register([IB0, IB3], IR1, '', 'A3')
+
+        def build_adapters(L, MT):
+            return L([
+                # 0
+                MT({
+                    IR0: MT({
+                        '': 'A1',
+                        'name1': 'A2'
+                    })
+                }),
+                # 1
+                MT({
+                    IB0: MT({
+                        IR0: MT({
+                            '': 'A1',
+                            'name2': 'A2'
+                        }),
+                        IR1: MT({
+                            '': 'A3',
+                            'name3': 'A4'
+                        })
+                    })
+                }),
+                # 3
+                MT({
+                    IB0: MT({
+                        IB1: MT({
+                            IR0: MT({'': 'A1'})
+                        }),
+                        IB2: MT({
+                            IR0: MT({'name2': 'A2'}),
+                            IR1: MT({'name4': 'A4'}),
+                        }),
+                        IB3: MT({
+                            IR1: MT({'': 'A3'})
+                        })
+                    }),
+                }),
+            ])
+
+        self.assertEqual(registry._adapters,
+                         build_adapters(L=self._getMutableListType(),
+                                        MT=self._getMappingType()))
+
+        registered = sorted(registry.allRegistrations())
+        self.assertEqual(registered, [
+            ((), IR0, '', 'A1'),
+            ((), IR0, 'name1', 'A2'),
+            ((IB0,), IR0, '', 'A1'),
+            ((IB0,), IR0, 'name2', 'A2'),
+            ((IB0,), IR1, '', 'A3'),
+            ((IB0,), IR1, 'name3', 'A4'),
+            ((IB0, IB1), IR0, '', 'A1'),
+            ((IB0, IB2), IR0, 'name2', 'A2'),
+            ((IB0, IB2), IR1, 'name4', 'A4'),
+            ((IB0, IB3), IR1, '', 'A3')
+        ])
+
+        # We can duplicate to another object.
+        registry2 = self._makeOne()
+        for args in registered:
+            registry2.register(*args)
+
+        self.assertEqual(registry2._adapters, registry._adapters)
+        self.assertEqual(registry2._provided, registry._provided)
+
+        # We can change the types and rebuild the data structures.
+        registry._mappingType = CustomMapping
+        registry._leafSequenceType = CustomLeafSequence
+        registry._sequenceType = CustomSequence
+        registry._providedType = CustomProvided
+        def addValue(existing, new):
+            existing = existing if existing is not None else CustomLeafSequence()
+            existing.append(new)
+            return existing
+        registry._addValueToLeaf = addValue
+
+        registry.rebuild()
+
+        self.assertEqual(registry._adapters,
+                         build_adapters(
+                             L=CustomSequence,
+                             MT=CustomMapping
+                         ))
 
     def test_register_with_invalid_name(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
@@ -117,8 +328,12 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         registry.register([None], IR0, '', 'A1')
         registry.register([None], IR0, '', None)
         self.assertEqual(len(registry._adapters), 0)
+        self.assertIsInstance(registry._adapters, self._getMutableListType())
+        registered = list(registry.allRegistrations())
+        self.assertEqual(registered, [])
 
     def test_register_with_same_value(self):
+        from zope.interface import Interface
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         _value = object()
@@ -126,10 +341,31 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         _before = registry._generation
         registry.register([None], IR0, '', _value)
         self.assertEqual(registry._generation, _before) # skipped changed()
+        self._check_basic_types_of_adapters(registry)
+        MT = self._getMappingType()
+        self.assertEqual(registry._adapters[1], MT(
+            {
+                Interface: MT(
+                    {
+                        IR0: MT({'': _value})
+                    }
+                )
+            }
+        ))
+        registered = list(registry.allRegistrations())
+        self.assertEqual(registered, [(
+            (Interface,), # required
+            IR0, # provided
+            '', # name
+            _value # value
+        )])
+
 
     def test_registered_empty(self):
         registry = self._makeOne()
         self.assertEqual(registry.registered([None], None, ''), None)
+        registered = list(registry.allRegistrations())
+        self.assertEqual(registered, [])
 
     def test_registered_non_empty_miss(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
@@ -144,22 +380,53 @@ class BaseAdapterRegistryTests(unittest.TestCase):
 
     def test_unregister_empty(self):
         registry = self._makeOne()
-        registry.unregister([None], None, '') #doesn't raise
+        registry.unregister([None], None, '') # doesn't raise
         self.assertEqual(registry.registered([None], None, ''), None)
+        self.assertEqual(len(registry._provided), 0)
 
     def test_unregister_non_empty_miss_on_required(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         registry.register([IB1], None, '', 'A1')
-        registry.unregister([IB2], None, '') #doesn't raise
+        registry.unregister([IB2], None, '') # doesn't raise
         self.assertEqual(registry.registered([IB1], None, ''), 'A1')
+        self._check_basic_types_of_adapters(registry)
+        MT = self._getMappingType()
+        self.assertEqual(registry._adapters[1], MT(
+            {
+                IB1: MT(
+                    {
+                        None: MT({'': 'A1'})
+                    }
+                )
+            }
+        ))
+        PT = self._getProvidedType()
+        self.assertEqual(registry._provided, PT({
+            None: 1
+        }))
 
     def test_unregister_non_empty_miss_on_name(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         registry.register([IB1], None, '', 'A1')
-        registry.unregister([IB1], None, 'nonesuch') #doesn't raise
+        registry.unregister([IB1], None, 'nonesuch') # doesn't raise
         self.assertEqual(registry.registered([IB1], None, ''), 'A1')
+        self._check_basic_types_of_adapters(registry)
+        MT = self._getMappingType()
+        self.assertEqual(registry._adapters[1], MT(
+            {
+                IB1: MT(
+                    {
+                        None: MT({'': 'A1'})
+                    }
+                )
+            }
+        ))
+        PT = self._getProvidedType()
+        self.assertEqual(registry._provided, PT({
+            None: 1
+        }))
 
     def test_unregister_with_value_not_None_miss(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
@@ -177,24 +444,79 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         another = object()
         registry.register([IB1, IB2], None, '', one)
         registry.register([IB1, IB3], None, '', another)
+        self._check_basic_types_of_adapters(registry, expected_order=3)
         self.assertIn(IB2, registry._adapters[2][IB1])
         self.assertIn(IB3, registry._adapters[2][IB1])
+        MT = self._getMappingType()
+        self.assertEqual(registry._adapters[2], MT(
+            {
+                IB1: MT(
+                    {
+                        IB2: MT({None: MT({'': one})}),
+                        IB3: MT({None: MT({'': another})})
+                    }
+                )
+            }
+        ))
+        PT = self._getProvidedType()
+        self.assertEqual(registry._provided, PT({
+            None: 2
+        }))
+
         registry.unregister([IB1, IB3], None, '', another)
         self.assertIn(IB2, registry._adapters[2][IB1])
         self.assertNotIn(IB3, registry._adapters[2][IB1])
+        self.assertEqual(registry._adapters[2], MT(
+            {
+                IB1: MT(
+                    {
+                        IB2: MT({None: MT({'': one})}),
+                    }
+                )
+            }
+        ))
+        self.assertEqual(registry._provided, PT({
+            None: 1
+        }))
 
     def test_unsubscribe_empty(self):
         registry = self._makeOne()
         registry.unsubscribe([None], None, '') #doesn't raise
         self.assertEqual(registry.registered([None], None, ''), None)
+        self._check_basic_types_of_subscribers(registry, expected_order=0)
 
     def test_unsubscribe_hit(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         orig = object()
         registry.subscribe([IB1], None, orig)
+        MT = self._getMappingType()
+        L = self._getLeafSequenceType()
+        PT = self._getProvidedType()
+        self._check_basic_types_of_subscribers(registry)
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                None: MT({
+                    '': L((orig,))
+                })
+            })
+        }))
+        self.assertEqual(registry._provided, PT({}))
         registry.unsubscribe([IB1], None, orig) #doesn't raise
         self.assertEqual(len(registry._subscribers), 0)
+        self.assertEqual(registry._provided, PT({}))
+
+    def assertLeafIdentity(self, leaf1, leaf2):
+        """
+        Implementations may choose to use new, immutable objects
+        instead of mutating existing subscriber leaf objects, or vice versa.
+
+        The default implementation uses immutable tuples, so they are never
+        the same. Other implementations may use persistent lists so they should be
+        the same and mutated in place. Subclasses testing this behaviour need to
+        override this method.
+        """
+        self.assertIsNot(leaf1, leaf2)
 
     def test_unsubscribe_after_multiple(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
@@ -207,11 +529,97 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         registry.subscribe([IB1], None, second)
         registry.subscribe([IB1], IR0, third)
         registry.subscribe([IB1], IR0, fourth)
-        registry.unsubscribe([IB1], IR0, fourth)
+        self._check_basic_types_of_subscribers(registry, expected_order=2)
+        MT = self._getMappingType()
+        L = self._getLeafSequenceType()
+        PT = self._getProvidedType()
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                None: MT({'': L((first, second))}),
+                IR0: MT({'': L((third, fourth))}),
+            })
+        }))
+        self.assertEqual(registry._provided, PT({
+            IR0: 2
+        }))
+        # The leaf objects may or may not stay the same as they are unsubscribed,
+        # depending on the implementation
+        IR0_leaf_orig = registry._subscribers[1][IB1][IR0]['']
+        Non_leaf_orig = registry._subscribers[1][IB1][None]['']
+
+        registry.unsubscribe([IB1], None, first)
         registry.unsubscribe([IB1], IR0, third)
+
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                None: MT({'': L((second,))}),
+                IR0: MT({'': L((fourth,))}),
+            })
+        }))
+        self.assertEqual(registry._provided, PT({
+            IR0: 1
+        }))
+        IR0_leaf_new = registry._subscribers[1][IB1][IR0]['']
+        Non_leaf_new = registry._subscribers[1][IB1][None]['']
+
+        self.assertLeafIdentity(IR0_leaf_orig, IR0_leaf_new)
+        self.assertLeafIdentity(Non_leaf_orig, Non_leaf_new)
+
         registry.unsubscribe([IB1], None, second)
-        registry.unsubscribe([IB1], None, first)
+        registry.unsubscribe([IB1], IR0, fourth)
+        self.assertEqual(len(registry._subscribers), 0)
+        self.assertEqual(len(registry._provided), 0)
+
+    def test_subscribe_unsubscribe_identical_objects_provided(self):
+        # https://github.com/zopefoundation/zope.interface/issues/227
+        IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
+        registry = self._makeOne()
+        first = object()
+        registry.subscribe([IB1], IR0, first)
+        registry.subscribe([IB1], IR0, first)
+
+        MT = self._getMappingType()
+        L = self._getLeafSequenceType()
+        PT = self._getProvidedType()
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                IR0: MT({'': L((first, first))}),
+            })
+        }))
+        self.assertEqual(registry._provided, PT({
+            IR0: 2
+        }))
+
+        registry.unsubscribe([IB1], IR0, first)
+        registry.unsubscribe([IB1], IR0, first)
         self.assertEqual(len(registry._subscribers), 0)
+        self.assertEqual(registry._provided, PT())
+
+    def test_subscribe_unsubscribe_nonequal_objects_provided(self):
+        # https://github.com/zopefoundation/zope.interface/issues/227
+        IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
+        registry = self._makeOne()
+        first = object()
+        second = object()
+        registry.subscribe([IB1], IR0, first)
+        registry.subscribe([IB1], IR0, second)
+
+        MT = self._getMappingType()
+        L = self._getLeafSequenceType()
+        PT = self._getProvidedType()
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                IR0: MT({'': L((first, second))}),
+            })
+        }))
+        self.assertEqual(registry._provided, PT({
+            IR0: 2
+        }))
+
+        registry.unsubscribe([IB1], IR0, first)
+        registry.unsubscribe([IB1], IR0, second)
+        self.assertEqual(len(registry._subscribers), 0)
+        self.assertEqual(registry._provided, PT())
 
     def test_unsubscribe_w_None_after_multiple(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
@@ -221,6 +629,7 @@ class BaseAdapterRegistryTests(unittest.TestCase):
 
         registry.subscribe([IB1], None, first)
         registry.subscribe([IB1], None, second)
+        self._check_basic_types_of_subscribers(registry, expected_order=2)
         registry.unsubscribe([IB1], None)
         self.assertEqual(len(registry._subscribers), 0)
 
@@ -228,17 +637,31 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         registry.subscribe([IB1], None, 'A1')
+        self._check_basic_types_of_subscribers(registry, expected_order=2)
+        registry.unsubscribe([IB2], None, '') # doesn't raise
         self.assertEqual(len(registry._subscribers), 2)
-        registry.unsubscribe([IB2], None, '') #doesn't raise
-        self.assertEqual(len(registry._subscribers), 2)
+        MT = self._getMappingType()
+        L = self._getLeafSequenceType()
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                None: MT({'': L(('A1',))}),
+            })
+        }))
 
     def test_unsubscribe_non_empty_miss_on_value(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         registry.subscribe([IB1], None, 'A1')
+        self._check_basic_types_of_subscribers(registry, expected_order=2)
+        registry.unsubscribe([IB1], None, 'A2') # doesn't raise
         self.assertEqual(len(registry._subscribers), 2)
-        registry.unsubscribe([IB1], None, 'A2') #doesn't raise
-        self.assertEqual(len(registry._subscribers), 2)
+        MT = self._getMappingType()
+        L = self._getLeafSequenceType()
+        self.assertEqual(registry._subscribers[1], MT({
+            IB1: MT({
+                None: MT({'': L(('A1',))}),
+            })
+        }))
 
     def test_unsubscribe_with_value_not_None_miss(self):
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
@@ -253,6 +676,7 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         self.fail("Example method, not intended to be called.")
 
     def test_unsubscribe_instance_method(self):
+        # Checking that the values are compared by equality, not identity
         IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
         registry = self._makeOne()
         self.assertEqual(len(registry._subscribers), 0)
@@ -260,6 +684,162 @@ class BaseAdapterRegistryTests(unittest.TestCase):
         registry.unsubscribe([IB1], None, self._instance_method_notify_target)
         self.assertEqual(len(registry._subscribers), 0)
 
+    def test_subscribe_multiple_allRegistrations(self):
+        IB0, IB1, IB2, IB3, IB4, IF0, IF1, IR0, IR1 = _makeInterfaces() # pylint:disable=unused-variable
+        registry = self._makeOne()
+        # Use several different depths and several different values
+        registry.subscribe([], IR0, 'A1')
+        registry.subscribe([], IR0, 'A2')
+
+        registry.subscribe([IB0], IR0, 'A1')
+        registry.subscribe([IB0], IR0, 'A2')
+        registry.subscribe([IB0], IR1, 'A3')
+        registry.subscribe([IB0], IR1, 'A4')
+
+        registry.subscribe([IB0, IB1], IR0, 'A1')
+        registry.subscribe([IB0, IB2], IR0, 'A2')
+        registry.subscribe([IB0, IB2], IR1, 'A4')
+        registry.subscribe([IB0, IB3], IR1, 'A3')
+
+
+        def build_subscribers(L, F, MT):
+            return L([
+                # 0
+                MT({
+                    IR0: MT({
+                        '': F(['A1', 'A2'])
+                    })
+                }),
+                # 1
+                MT({
+                    IB0: MT({
+                        IR0: MT({
+                            '': F(['A1', 'A2'])
+                        }),
+                        IR1: MT({
+                            '': F(['A3', 'A4'])
+                        })
+                    })
+                }),
+                # 3
+                MT({
+                    IB0: MT({
+                        IB1: MT({
+                            IR0: MT({'': F(['A1'])})
+                        }),
+                        IB2: MT({
+                            IR0: MT({'': F(['A2'])}),
+                            IR1: MT({'': F(['A4'])}),
+                        }),
+                        IB3: MT({
+                            IR1: MT({'': F(['A3'])})
+                        })
+                    }),
+                }),
+            ])
+
+        self.assertEqual(registry._subscribers,
+                         build_subscribers(
+                             L=self._getMutableListType(),
+                             F=self._getLeafSequenceType(),
+                             MT=self._getMappingType()
+                         ))
+
+        def build_provided(P):
+            return P({
+                IR0: 6,
+                IR1: 4,
+            })
+
+
+        self.assertEqual(registry._provided,
+                         build_provided(P=self._getProvidedType()))
+
+        registered = sorted(registry.allSubscriptions())
+        self.assertEqual(registered, [
+            ((), IR0, 'A1'),
+            ((), IR0, 'A2'),
+            ((IB0,), IR0, 'A1'),
+            ((IB0,), IR0, 'A2'),
+            ((IB0,), IR1, 'A3'),
+            ((IB0,), IR1, 'A4'),
+            ((IB0, IB1), IR0, 'A1'),
+            ((IB0, IB2), IR0, 'A2'),
+            ((IB0, IB2), IR1, 'A4'),
+            ((IB0, IB3), IR1, 'A3')
+        ])
+
+        # We can duplicate this to another object
+        registry2 = self._makeOne()
+        for args in registered:
+            registry2.subscribe(*args)
+
+        self.assertEqual(registry2._subscribers, registry._subscribers)
+        self.assertEqual(registry2._provided, registry._provided)
+
+        # We can change the types and rebuild the data structures.
+        registry._mappingType = CustomMapping
+        registry._leafSequenceType = CustomLeafSequence
+        registry._sequenceType = CustomSequence
+        registry._providedType = CustomProvided
+        def addValue(existing, new):
+            existing = existing if existing is not None else CustomLeafSequence()
+            existing.append(new)
+            return existing
+        registry._addValueToLeaf = addValue
+
+        registry.rebuild()
+
+        self.assertEqual(registry._subscribers,
+                         build_subscribers(
+                             L=CustomSequence,
+                             F=CustomLeafSequence,
+                             MT=CustomMapping
+                         ))
+
+
+class CustomTypesBaseAdapterRegistryTests(BaseAdapterRegistryTests):
+
+    def _getMappingType(self):
+        return CustomMapping
+
+    def _getProvidedType(self):
+        return CustomProvided
+
+    def _getMutableListType(self):
+        return CustomSequence
+
+    def _getLeafSequenceType(self):
+        return CustomLeafSequence
+
+    def _getBaseAdapterRegistry(self):
+        from zope.interface.adapter import BaseAdapterRegistry
+        class CustomAdapterRegistry(BaseAdapterRegistry):
+            _mappingType = self._getMappingType()
+            _sequenceType = self._getMutableListType()
+            _leafSequenceType = self._getLeafSequenceType()
+            _providedType = self._getProvidedType()
+
+            def _addValueToLeaf(self, existing_leaf_sequence, new_item):
+                if not existing_leaf_sequence:
+                    existing_leaf_sequence = self._leafSequenceType()
+                existing_leaf_sequence.append(new_item)
+                return existing_leaf_sequence
+
+            def _removeValueFromLeaf(self, existing_leaf_sequence, to_remove):
+                without_removed = BaseAdapterRegistry._removeValueFromLeaf(
+                    self,
+                    existing_leaf_sequence,
+                    to_remove)
+                existing_leaf_sequence[:] = without_removed
+                assert to_remove not in existing_leaf_sequence
+                return existing_leaf_sequence
+
+        return CustomAdapterRegistry
+
+    def assertLeafIdentity(self, leaf1, leaf2):
+        self.assertIs(leaf1, leaf2)
+
 
 class LookupBaseFallbackTests(unittest.TestCase):
 
diff --git a/src/zope/interface/tests/test_registry.py b/src/zope/interface/tests/test_registry.py
index cb1fdf9..e9e89ad 100644
--- a/src/zope/interface/tests/test_registry.py
+++ b/src/zope/interface/tests/test_registry.py
@@ -2320,6 +2320,37 @@ class ComponentsTests(unittest.TestCase):
         self.assertEqual(_called_1, [bar])
         self.assertEqual(_called_2, [bar])
 
+    def test_register_unregister_identical_objects_provided(self, identical=True):
+        # https://github.com/zopefoundation/zope.interface/issues/227
+        class IFoo(Interface):
+            pass
+
+        comp = self._makeOne()
+        first = object()
+        second = first if identical else object()
+
+        comp.registerUtility(first, provided=IFoo)
+        comp.registerUtility(second, provided=IFoo, name='bar')
+
+        self.assertEqual(len(comp.utilities._subscribers), 1)
+        self.assertEqual(comp.utilities._subscribers, [{
+            IFoo: {'': (first, ) if identical else (first, second)}
+        }])
+        self.assertEqual(comp.utilities._provided, {
+            IFoo: 3 if identical else 4
+        })
+
+        res = comp.unregisterUtility(first, provided=IFoo)
+        self.assertTrue(res)
+        res = comp.unregisterUtility(second, provided=IFoo, name='bar')
+        self.assertTrue(res)
+
+        self.assertEqual(comp.utilities._provided, {})
+        self.assertEqual(len(comp.utilities._subscribers), 0)
+
+    def test_register_unregister_nonequal_objects_provided(self):
+        self.test_register_unregister_identical_objects_provided(identical=False)
+
 
 class UnhashableComponentsTests(ComponentsTests):