Merge pull request #188 from zopefoundation/issue8

Ensure Interface is the last item in the __sro__.

7 files changed, 224 insertions, 44 deletions

diff --git a/CHANGES.rst b/CHANGES.rst
index 44bb335..3d9bb5d 100644
--- a/CHANGES.rst
+++ b/CHANGES.rst
@@ -160,7 +160,7 @@
 
 - Adopt Python's standard `C3 resolution order
   <https://www.python.org/download/releases/2.3/mro/>`_ to compute the
-  ``__iro___`` and ``__sro___`` of interfaces, with tweaks to support
+  ``__iro__`` and ``__sro__`` of interfaces, with tweaks to support
   additional cases that are common in interfaces but disallowed for
   Python classes. Previously, an ad-hoc ordering that made no
   particular guarantees was used.
@@ -204,6 +204,12 @@
   `issue 190
   <https://github.com/zopefoundation/zope.interface/issues/190>`_.
 
+- Ensure that ``Interface`` is always the last item in the ``__iro__``
+  and ``__sro__``. This is usually the case, but if classes that do
+  not implement any interfaces are part of a class inheritance
+  hierarchy, ``Interface`` could be assigned too high a priority.
+  See `issue 8 <https://github.com/zopefoundation/zope.interface/issues/8>`_.
+
 
 4.7.2 (2020-03-10)
 ==================
diff --git a/docs/README.rst b/docs/README.rst
index a8068f8..831f19a 100644
--- a/docs/README.rst
+++ b/docs/README.rst
@@ -689,9 +689,22 @@ that lists the specification and all of it's ancestors:
    <InterfaceClass builtins.IBaz>,
    <InterfaceClass builtins.IFoo>,
    <InterfaceClass builtins.IBlat>,
-   <InterfaceClass zope.interface.Interface>,
-   <implementedBy ...object>)
-
+   <implementedBy ...object>,
+   <InterfaceClass zope.interface.Interface>)
+  >>> class IBiz(zope.interface.Interface):
+  ...    pass
+  >>> @zope.interface.implementer(IBiz)
+  ... class Biz(Baz):
+  ...    pass
+  >>> pprint(zope.interface.implementedBy(Biz).__sro__)
+  (<implementedBy builtins.Biz>,
+   <InterfaceClass builtins.IBiz>,
+   <implementedBy builtins.Baz>,
+   <InterfaceClass builtins.IBaz>,
+   <InterfaceClass builtins.IFoo>,
+   <InterfaceClass builtins.IBlat>,
+   <implementedBy ...object>,
+   <InterfaceClass zope.interface.Interface>)
 
 Tagged Values
 =============
diff --git a/src/zope/interface/common/tests/__init__.py b/src/zope/interface/common/tests/__init__.py
index ade2bf3..b285ad7 100644
--- a/src/zope/interface/common/tests/__init__.py
+++ b/src/zope/interface/common/tests/__init__.py
@@ -73,14 +73,24 @@ def add_verify_tests(cls, iface_classes_iter):
             def test_ro(self, stdlib_class=stdlib_class, iface=iface):
                 from zope.interface import ro
                 from zope.interface import implementedBy
+                from zope.interface import Interface
                 self.assertEqual(
                     tuple(ro.ro(iface, strict=True)),
                     iface.__sro__)
                 implements = implementedBy(stdlib_class)
+                sro = implements.__sro__
+                self.assertIs(sro[-1], Interface)
+
+                # Check that we got the strict C3 resolution order, unless we
+                # know we cannot. Note that 'Interface' is virtual base that doesn't
+                # necessarily appear at the same place in the calculated SRO as in the
+                # final SRO.
                 strict = stdlib_class not in self.NON_STRICT_RO
-                self.assertEqual(
-                    tuple(ro.ro(implements, strict=strict)),
-                    implements.__sro__)
+                isro = ro.ro(implements, strict=strict)
+                isro.remove(Interface)
+                isro.append(Interface)
+
+                self.assertEqual(tuple(isro), sro)
 
             name = 'test_auto_ro_' + suffix
             test_ro.__name__ = name
diff --git a/src/zope/interface/interface.py b/src/zope/interface/interface.py
index f9fb333..a8eac01 100644
--- a/src/zope/interface/interface.py
+++ b/src/zope/interface/interface.py
@@ -21,7 +21,8 @@ import weakref
 
 from zope.interface._compat import _use_c_impl
 from zope.interface.exceptions import Invalid
-from zope.interface.ro import ro
+from zope.interface.ro import ro as calculate_ro
+from zope.interface import ro
 
 __all__ = [
     # Most of the public API from this module is directly exported
@@ -226,6 +227,10 @@ class Specification(SpecificationBase):
     """
     __slots__ = ()
 
+    # The root of all Specifications. This will be assigned `Interface`,
+    # once it is defined.
+    _ROOT = None
+
     # Copy some base class methods for speed
     isOrExtends = SpecificationBase.isOrExtends
     providedBy = SpecificationBase.providedBy
@@ -274,7 +279,7 @@ class Specification(SpecificationBase):
         for b in self.__bases__:
             b.unsubscribe(self)
 
-        # Register ourselves as a dependent of our bases
+        # Register ourselves as a dependent of our new bases
         self._bases = bases
         for b in bases:
             b.subscribe(self)
@@ -286,29 +291,76 @@ class Specification(SpecificationBase):
         __setBases,
         )
 
+    def _calculate_sro(self):
+        """
+        Calculate and return the resolution order for this object, using its ``__bases__``.
+
+        Ensures that ``Interface`` is always the last (lowest priority) element.
+        """
+        # We'd like to make Interface the lowest priority as a
+        # property of the resolution order algorithm. That almost
+        # works out naturally, but it fails when class inheritance has
+        # some bases that DO implement an interface, and some that DO
+        # NOT. In such a mixed scenario, you wind up with a set of
+        # bases to consider that look like this: [[..., Interface],
+        # [..., object], ...]. Depending on the order if inheritance,
+        # Interface can wind up before or after object, and that can
+        # happen at any point in the tree, meaning Interface can wind
+        # up somewhere in the middle of the order. Since Interface is
+        # treated as something that everything winds up implementing
+        # anyway (a catch-all for things like adapters), having it high up
+        # the order is bad. It's also bad to have it at the end, just before
+        # some concrete class: concrete classes should be HIGHER priority than
+        # interfaces (because there's only one class, but many implementations).
+        #
+        # One technically nice way to fix this would be to have
+        # ``implementedBy(object).__bases__ = (Interface,)``
+        #
+        # But: (1) That fails for old-style classes and (2) that causes
+        # everything to appear to *explicitly* implement Interface, when up
+        # to this point it's been an implicit virtual sort of relationship.
+        #
+        # So we force the issue by mutating the resolution order.
+
+        # Note that we let C3 use pre-computed __sro__ for our bases.
+        # This requires that by the time this method is invoked, our bases
+        # have settled their SROs. Thus, ``changed()`` must first
+        # update itself before telling its descendents of changes.
+        sro = calculate_ro(self, base_mros={
+            b: b.__sro__
+            for b in self.__bases__
+        })
+        root = self._ROOT
+        if root is not None and sro and sro[-1] is not root:
+            # In one dataset of 1823 Interface objects, 1117 ClassProvides objects,
+            # sro[-1] was root 4496 times, and only not root 118 times. So it's
+            # probably worth checking.
+
+            # Once we don't have to deal with old-style classes,
+            # we can add a check and only do this if base_count > 1,
+            # if we tweak the bootstrapping for ``<implementedBy object>``
+            sro = [
+                x
+                for x in sro
+                if x is not root
+            ]
+            sro.append(root)
+
+        return sro
+
     def changed(self, originally_changed):
-        """We, or something we depend on, have changed
+        """
+        We, or something we depend on, have changed.
+
+        By the time this is called, the things we depend on,
+        such as our bases, should themselves be stable.
         """
         self._v_attrs = None
 
         implied = self._implied
         implied.clear()
 
-        if len(self.__bases__) == 1:
-            # Fast path: One base makes it trivial to calculate
-            # the MRO.
-            sro = self.__bases__[0].__sro__
-            ancestors = [self]
-            ancestors.extend(sro)
-        else:
-            ancestors = ro(self)
-
-        try:
-            if Interface not in ancestors:
-                ancestors.append(Interface)
-        except NameError:
-            pass # defining Interface itself
-
+        ancestors = self._calculate_sro()
         self.__sro__ = tuple(ancestors)
         self.__iro__ = tuple([ancestor for ancestor in ancestors
                               if isinstance(ancestor, InterfaceClass)
@@ -318,7 +370,8 @@ class Specification(SpecificationBase):
             # We directly imply our ancestors:
             implied[ancestor] = ()
 
-        # Now, advise our dependents of change:
+        # Now, advise our dependents of change
+        # (being careful not to create the WeakKeyDictionary if not needed):
         for dependent in tuple(self._dependents.keys() if self._dependents else ()):
             dependent.changed(originally_changed)
 
@@ -647,6 +700,12 @@ class InterfaceClass(Element, InterfaceBase, Specification):
 
 
 Interface = InterfaceClass("Interface", __module__='zope.interface')
+# Interface is the only member of its own SRO.
+Interface._calculate_sro = lambda: (Interface,)
+Interface.changed(Interface)
+assert Interface.__sro__ == (Interface,)
+Specification._ROOT = Interface
+ro._ROOT = Interface
 
 
 class Attribute(Element):
diff --git a/src/zope/interface/ro.py b/src/zope/interface/ro.py
index dbffb53..7cb4f55 100644
--- a/src/zope/interface/ro.py
+++ b/src/zope/interface/ro.py
@@ -189,11 +189,25 @@ class _ClassBoolFromEnv(object):
         return val
 
 
+class _StaticMRO(object):
+    # A previously resolved MRO, supplied by the caller.
+    # Used in place of calculating it.
+
+    had_inconsistency = None # We don't know...
+
+    def __init__(self, C, mro):
+        self.leaf = C
+        self.__mro = tuple(mro)
+
+    def mro(self):
+        return list(self.__mro)
+
+
 class C3(object):
     # Holds the shared state during computation of an MRO.
 
     @staticmethod
-    def resolver(C, strict):
+    def resolver(C, strict, base_mros):
         strict = strict if strict is not None else C3.STRICT_RO
         factory = C3
         if strict:
@@ -201,7 +215,13 @@ class C3(object):
         elif C3.TRACK_BAD_IRO:
             factory = _TrackingC3
 
-        return factory(C, {})
+        memo = {}
+        base_mros = base_mros or {}
+        for base, mro in base_mros.items():
+            assert base in C.__bases__
+            memo[base] = _StaticMRO(base, mro)
+
+        return factory(C, memo)
 
     __mro = None
     __legacy_ro = None
@@ -229,6 +249,9 @@ class C3(object):
 
         self.bases_had_inconsistency = any(base.had_inconsistency for base in base_resolvers)
 
+        if len(C.__bases__) == 1:
+            self.__mro = [C] + memo[C.__bases__[0]].mro()
+
     @property
     def had_inconsistency(self):
         return self.direct_inconsistency or self.bases_had_inconsistency
@@ -520,10 +543,9 @@ class _ROComparison(object):
         left_lines = [str(x) for x in legacy_report]
         right_lines = [str(x) for x in c3_report]
 
-        # We have the same number of non-empty lines as we do items
-        # in the resolution order.
-        assert len(list(filter(None, left_lines))) == len(self.c3_ro)
-        assert len(list(filter(None, right_lines))) == len(self.c3_ro)
+        # We have the same number of lines in the report; this is not
+        # necessarily the same as the number of items in either RO.
+        assert len(left_lines) == len(right_lines)
 
         padding = ' ' * 2
         max_left = max(len(x) for x in left_lines)
@@ -547,20 +569,16 @@ class _ROComparison(object):
         return '\n'.join(lines)
 
 
-def ro(C, strict=None, log_changed_ro=None, use_legacy_ro=None):
+# Set to `Interface` once it is defined. This is used to
+# avoid logging false positives about changed ROs.
+_ROOT = None
+
+def ro(C, strict=None, base_mros=None, log_changed_ro=None, use_legacy_ro=None):
     """
     ro(C) -> list
 
     Compute the precedence list (mro) according to C3.
 
-    As an implementation note, this always calculates the full MRO by
-    examining all the bases recursively. If there are special cases
-    that can reuse pre-calculated partial MROs, such as a
-    ``__bases__`` of length one, the caller is responsible for
-    optimizing that. (This is because this function doesn't know how
-    to get the complete MRO of a base; it only knows how to get their
-    ``__bases__``.)
-
     :return: A fresh `list` object.
 
     .. versionchanged:: 5.0.0
@@ -568,7 +586,9 @@ def ro(C, strict=None, log_changed_ro=None, use_legacy_ro=None):
        keyword arguments. These are provisional and likely to be
        removed in the future. They are most useful for testing.
     """
-    resolver = C3.resolver(C, strict)
+    # The ``base_mros`` argument is for internal optimization and
+    # not documented.
+    resolver = C3.resolver(C, strict, base_mros)
     mro = resolver.mro()
 
     log_changed = log_changed_ro if log_changed_ro is not None else resolver.LOG_CHANGED_IRO
@@ -578,7 +598,16 @@ def ro(C, strict=None, log_changed_ro=None, use_legacy_ro=None):
         legacy_ro = resolver.legacy_ro
         assert isinstance(legacy_ro, list)
         assert isinstance(mro, list)
-        if legacy_ro != mro:
+        changed = legacy_ro != mro
+        if changed:
+            # Did only Interface move? The fix for issue #8 made that
+            # somewhat common. It's almost certainly not a problem, though,
+            # so allow ignoring it.
+            legacy_without_root = [x for x in legacy_ro if x is not _ROOT]
+            mro_without_root = [x for x in mro if x is not _ROOT]
+            changed = legacy_without_root != mro_without_root
+
+        if changed:
             comparison = _ROComparison(resolver, mro, legacy_ro)
             _logger().warning(
                 "Object %r has different legacy and C3 MROs:\n%s",
@@ -602,4 +631,4 @@ def is_consistent(C):
     Check if the resolution order for *C*, as computed by :func:`ro`, is consistent
     according to C3.
     """
-    return not C3.resolver(C, False).had_inconsistency
+    return not C3.resolver(C, False, None).had_inconsistency
diff --git a/src/zope/interface/tests/test_interface.py b/src/zope/interface/tests/test_interface.py
index 70e5d64..da7eb8c 100644
--- a/src/zope/interface/tests/test_interface.py
+++ b/src/zope/interface/tests/test_interface.py
@@ -438,6 +438,48 @@ class SpecificationTests(unittest.TestCase):
         self.assertTrue(spec.get('foo') is IFoo.get('foo'))
         self.assertTrue(spec.get('bar') is IBar.get('bar'))
 
+    def test_multiple_inheritance_no_interfaces(self):
+        # If we extend an object that implements interfaces,
+        # plus ane that doesn't, we do not interject `Interface`
+        # early in the resolution order. It stays at the end,
+        # like it should.
+        # See https://github.com/zopefoundation/zope.interface/issues/8
+        from zope.interface.interface import Interface
+        from zope.interface.declarations import implementer
+        from zope.interface.declarations import implementedBy
+
+        class IDefaultViewName(Interface):
+            pass
+
+        class Context(object):
+            pass
+
+        class RDBModel(Context):
+            pass
+
+        class IOther(Interface):
+            pass
+
+        @implementer(IOther)
+        class OtherBase(object):
+            pass
+
+        class Model(OtherBase, Context):
+            pass
+
+        self.assertEqual(
+            implementedBy(Model).__sro__,
+            (
+                implementedBy(Model),
+                implementedBy(OtherBase),
+                IOther,
+                implementedBy(Context),
+                implementedBy(object),
+                Interface, # This used to be wrong, it used to be 2 too high.
+            )
+        )
+
+
 class InterfaceClassTests(unittest.TestCase):
 
     def _getTargetClass(self):
diff --git a/src/zope/interface/tests/test_ro.py b/src/zope/interface/tests/test_ro.py
index 3a516b5..ce0a6f4 100644
--- a/src/zope/interface/tests/test_ro.py
+++ b/src/zope/interface/tests/test_ro.py
@@ -375,6 +375,27 @@ Object <InterfaceClass zope.interface.tests.test_ro.A> has different legacy and
         self.assertEqual(iro, legacy_iro)
 
 
+class TestC3(unittest.TestCase):
+    def _makeOne(self, C, strict=False, base_mros=None):
+        from zope.interface.ro import C3
+        return C3.resolver(C, strict, base_mros)
+
+    def test_base_mros_given(self):
+        c3 = self._makeOne(type(self), base_mros={unittest.TestCase: unittest.TestCase.__mro__})
+        memo = c3.memo
+        self.assertIn(unittest.TestCase, memo)
+        # We used the StaticMRO class
+        self.assertIsNone(memo[unittest.TestCase].had_inconsistency)
+
+    def test_one_base_optimization(self):
+        c3 = self._makeOne(type(self))
+        # Even though we didn't call .mro() yet, the MRO has been
+        # computed.
+        self.assertIsNotNone(c3._C3__mro) # pylint:disable=no-member
+        c3._merge = None
+        self.assertEqual(c3.mro(), list(type(self).__mro__))
+
+
 class Test_ROComparison(unittest.TestCase):
 
     class MockC3(object):