Use C3 (mostly) to compute IRO.issue21

Fixes #21

The 'mostly' is because interfaces are used in cases that C3 forbids;
when there's a conflict, we fallback to the legacy algorithm. It turns
out there are few conflicts (13K out of 149K total orderings in Plone).

I hoped the fix for #8 might shake out automatically, but it didn't.

Optimize the extremely common case of a __bases__ of length one.

In the benchmark, 4/5 of the interfaces and related objects have a base of length one.

Fix the bad IROs in the bundled ABC interfaces, and implement a way to get warnings or errors.

In running plone/buildout.coredev and tracking the RO requests, the
stats for equal, not equal, and inconsistent-so-fallback, I got
{'ros': 148868, 'eq': 138461, 'ne': 10407, 'inconsistent': 12934}

Add the interface module to the Attribute str.

This was extremely helpful tracking down the Plone problem; IDate is defined in multiple modules.

15 files changed, 1001 insertions, 54 deletions

diff --git a/src/zope/interface/__init__.py b/src/zope/interface/__init__.py
index 605b706..e282fbd 100644
--- a/src/zope/interface/__init__.py
+++ b/src/zope/interface/__init__.py
@@ -60,6 +60,7 @@ del _wire
 from zope.interface.declarations import Declaration
 from zope.interface.declarations import alsoProvides
 from zope.interface.declarations import classImplements
+from zope.interface.declarations import classImplementsFirst
 from zope.interface.declarations import classImplementsOnly
 from zope.interface.declarations import classProvides
 from zope.interface.declarations import directlyProvidedBy
@@ -88,3 +89,5 @@ from zope.interface.interfaces import IInterfaceDeclaration
 moduleProvides(IInterfaceDeclaration)
 
 __all__ = ('Interface', 'Attribute') + tuple(IInterfaceDeclaration)
+
+assert all(k in globals() for k in __all__)
diff --git a/src/zope/interface/common/__init__.py b/src/zope/interface/common/__init__.py
index acbc581..a8bedf0 100644
--- a/src/zope/interface/common/__init__.py
+++ b/src/zope/interface/common/__init__.py
@@ -121,19 +121,20 @@ class ABCInterfaceClass(InterfaceClass):
         # go ahead and give us a name to ease debugging.
         self.__name__ = name
         extra_classes = attrs.pop('extra_classes', ())
+        ignored_classes = attrs.pop('ignored_classes', ())
 
         if 'abc' not in attrs:
             # Something like ``IList(ISequence)``: We're extending
             # abc interfaces but not an ABC interface ourself.
-            self.__class__ = InterfaceClass
             InterfaceClass.__init__(self, name, bases, attrs)
-            for cls in extra_classes:
-                classImplements(cls, self)
+            ABCInterfaceClass.__register_classes(self, extra_classes, ignored_classes)
+            self.__class__ = InterfaceClass
             return
 
         based_on = attrs.pop('abc')
         self.__abc = based_on
         self.__extra_classes = tuple(extra_classes)
+        self.__ignored_classes = tuple(ignored_classes)
 
         assert name[1:] == based_on.__name__, (name, based_on)
         methods = {
@@ -216,11 +217,14 @@ class ABCInterfaceClass(InterfaceClass):
         method.positional = method.positional[1:]
         return method
 
-    def __register_classes(self):
+    def __register_classes(self, conformers=None, ignored_classes=None):
         # Make the concrete classes already present in our ABC's registry
         # declare that they implement this interface.
-
-        for cls in self.getRegisteredConformers():
+        conformers = conformers if conformers is not None else self.getRegisteredConformers()
+        ignored = ignored_classes if ignored_classes is not None else self.__ignored_classes
+        for cls in conformers:
+            if cls in ignored:
+                continue
             classImplements(cls, self)
 
     def getABC(self):
diff --git a/src/zope/interface/common/builtins.py b/src/zope/interface/common/builtins.py
index 9262340..a07c0a3 100644
--- a/src/zope/interface/common/builtins.py
+++ b/src/zope/interface/common/builtins.py
@@ -37,7 +37,6 @@ __all__ = [
 ]
 
 # pylint:disable=no-self-argument
-
 class IList(collections.IMutableSequence):
     """
     Interface for :class:`list`
diff --git a/src/zope/interface/common/collections.py b/src/zope/interface/common/collections.py
index 9731069..6c0496e 100644
--- a/src/zope/interface/common/collections.py
+++ b/src/zope/interface/common/collections.py
@@ -177,6 +177,10 @@ class ISequence(IReversible,
                 ICollection):
     abc = abc.Sequence
     extra_classes = (UserString,)
+    # On Python 2, basestring is registered as an ISequence, and
+    # its subclass str is an IByteString. If we also register str as
+    # an ISequence, that tends to lead to inconsistent resolution order.
+    ignored_classes = (basestring,) if str is bytes else () # pylint:disable=undefined-variable
 
     @optional
     def __reversed__():
diff --git a/src/zope/interface/common/mapping.py b/src/zope/interface/common/mapping.py
index 13fa317..de56cf8 100644
--- a/src/zope/interface/common/mapping.py
+++ b/src/zope/interface/common/mapping.py
@@ -43,7 +43,7 @@ class IItemMapping(Interface):
         """
 
 
-class IReadMapping(IItemMapping, collections.IContainer):
+class IReadMapping(collections.IContainer, IItemMapping):
     """
     Basic mapping interface.
 
@@ -72,7 +72,7 @@ class IWriteMapping(Interface):
         """Set a new item in the mapping."""
 
 
-class IEnumerableMapping(IReadMapping, collections.ISized):
+class IEnumerableMapping(collections.ISized, IReadMapping):
     """
     Mapping objects whose items can be enumerated.
 
@@ -171,7 +171,7 @@ class IExtendedWriteMapping(IWriteMapping):
 
 class IFullMapping(
         collections.IMutableMapping,
-        IExtendedReadMapping, IExtendedWriteMapping, IClonableMapping, IMapping):
+        IExtendedReadMapping, IExtendedWriteMapping, IClonableMapping, IMapping,):
     """
     Full mapping interface.
 
diff --git a/src/zope/interface/common/tests/__init__.py b/src/zope/interface/common/tests/__init__.py
index 059e46c..ade2bf3 100644
--- a/src/zope/interface/common/tests/__init__.py
+++ b/src/zope/interface/common/tests/__init__.py
@@ -38,7 +38,8 @@ def iter_abc_interfaces(predicate=lambda iface: True):
         if not predicate(iface):
             continue
 
-        registered = list(iface.getRegisteredConformers())
+        registered = set(iface.getRegisteredConformers())
+        registered -= set(iface._ABCInterfaceClass__ignored_classes)
         if registered:
             yield iface, registered
 
@@ -50,24 +51,46 @@ def add_abc_interface_tests(cls, module):
 
 
 def add_verify_tests(cls, iface_classes_iter):
+    cls.maxDiff = None
     for iface, registered_classes in iface_classes_iter:
         for stdlib_class in registered_classes:
-
             def test(self, stdlib_class=stdlib_class, iface=iface):
                 if stdlib_class in self.UNVERIFIABLE or stdlib_class.__name__ in self.UNVERIFIABLE:
                     self.skipTest("Unable to verify %s" % stdlib_class)
 
                 self.assertTrue(self.verify(iface, stdlib_class))
 
-            name = 'test_auto_' + stdlib_class.__name__ + '_' + iface.__name__
+            suffix = "%s_%s_%s" % (
+                stdlib_class.__name__,
+                iface.__module__.replace('.', '_'),
+                iface.__name__
+            )
+            name = 'test_auto_' + suffix
             test.__name__ = name
-            assert not hasattr(cls, name)
+            assert not hasattr(cls, name), (name, list(cls.__dict__))
             setattr(cls, name, test)
 
+            def test_ro(self, stdlib_class=stdlib_class, iface=iface):
+                from zope.interface import ro
+                from zope.interface import implementedBy
+                self.assertEqual(
+                    tuple(ro.ro(iface, strict=True)),
+                    iface.__sro__)
+                implements = implementedBy(stdlib_class)
+                strict = stdlib_class not in self.NON_STRICT_RO
+                self.assertEqual(
+                    tuple(ro.ro(implements, strict=strict)),
+                    implements.__sro__)
+
+            name = 'test_auto_ro_' + suffix
+            test_ro.__name__ = name
+            assert not hasattr(cls, name)
+            setattr(cls, name, test_ro)
 
 class VerifyClassMixin(unittest.TestCase):
     verifier = staticmethod(verifyClass)
     UNVERIFIABLE = ()
+    NON_STRICT_RO = ()
 
     def _adjust_object_before_verify(self, iface, x):
         return x
diff --git a/src/zope/interface/common/tests/test_collections.py b/src/zope/interface/common/tests/test_collections.py
index 32ab801..f06e12e 100644
--- a/src/zope/interface/common/tests/test_collections.py
+++ b/src/zope/interface/common/tests/test_collections.py
@@ -17,6 +17,7 @@ try:
 except ImportError:
     import collections as abc
 from collections import deque
+from collections import OrderedDict
 
 
 try:
@@ -118,6 +119,9 @@ class TestVerifyClass(VerifyClassMixin, unittest.TestCase):
             type({}.viewitems()),
             type({}.viewkeys()),
         })
+        NON_STRICT_RO = {
+            OrderedDict
+        }
 
 add_abc_interface_tests(TestVerifyClass, collections.ISet.__module__)
 
diff --git a/src/zope/interface/declarations.py b/src/zope/interface/declarations.py
index 9c15b9b..1e9a2ea 100644
--- a/src/zope/interface/declarations.py
+++ b/src/zope/interface/declarations.py
@@ -449,35 +449,79 @@ def classImplementsOnly(cls, *interfaces):
 
 
 def classImplements(cls, *interfaces):
-    """Declare additional interfaces implemented for instances of a class
+    """
+    Declare additional interfaces implemented for instances of a class
 
-      The arguments after the class are one or more interfaces or
-      interface specifications (`~zope.interface.interfaces.IDeclaration` objects).
+    The arguments after the class are one or more interfaces or
+    interface specifications (`~zope.interface.interfaces.IDeclaration` objects).
 
-      The interfaces given (including the interfaces in the specifications)
-      are added to any interfaces previously declared.
+    The interfaces given (including the interfaces in the specifications)
+    are added to any interfaces previously declared. An effort is made to
+    keep a consistent C3 resolution order, but this cannot be guaranteed.
+
+    .. versionchanged:: 5.0.0
+       Each individual interface in *interfaces* may be added to either the
+       beginning or end of the list of interfaces declared for *cls*,
+       based on inheritance, in order to try to maintain a consistent
+       resolution order. Previously, all interfaces were added to the end.
     """
     spec = implementedBy(cls)
-    spec.declared += tuple(_normalizeargs(interfaces))
+    interfaces = tuple(_normalizeargs(interfaces))
+
+    before = []
+    after = []
+
+    # Take steps to try to avoid producing an invalid resolution
+    # order, while still allowing for BWC (in the past, we always
+    # appended)
+    for iface in interfaces:
+        for b in spec.declared:
+            if iface.extends(b):
+                before.append(iface)
+                break
+        else:
+            after.append(iface)
+    _classImplements_ordered(spec, tuple(before), tuple(after))
 
-    # compute the bases
-    bases = []
-    seen = {}
-    for b in spec.declared:
+
+def classImplementsFirst(cls, iface):
+    """
+    Declare that instances of *cls* additionally provide *iface*.
+
+    The second argument is an interface or interface specification.
+    It is added as the highest priority (first in the IRO) interface;
+    no attempt is made to keep a consistent resolution order.
+
+    .. versionadded:: 5.0.0
+    """
+    spec = implementedBy(cls)
+    _classImplements_ordered(spec, (iface,), ())
+
+
+def _classImplements_ordered(spec, before=(), after=()):
+    # eliminate duplicates
+    new_declared = []
+    seen = set()
+    for b in before + spec.declared + after:
         if b not in seen:
-            seen[b] = 1
-            bases.append(b)
+            new_declared.append(b)
+            seen.add(b)
 
-    if spec.inherit is not None:
+    spec.declared = tuple(new_declared)
+
+    # compute the bases
+    bases = new_declared # guaranteed no dupes
 
+    if spec.inherit is not None:
         for c in spec.inherit.__bases__:
             b = implementedBy(c)
             if b not in seen:
-                seen[b] = 1
+                seen.add(b)
                 bases.append(b)
 
     spec.__bases__ = tuple(bases)
 
+
 def _implements_advice(cls):
     interfaces, classImplements = cls.__dict__['__implements_advice_data__']
     del cls.__implements_advice_data__
@@ -664,6 +708,13 @@ class Provides(Declaration):  # Really named ProvidesClass
         self._cls = cls
         Declaration.__init__(self, *(interfaces + (implementedBy(cls), )))
 
+    def __repr__(self):
+        return "<%s.%s for %s>" % (
+            self.__class__.__module__,
+            self.__class__.__name__,
+            self._cls,
+        )
+
     def __reduce__(self):
         return Provides, self.__args
 
@@ -794,6 +845,13 @@ class ClassProvides(Declaration, ClassProvidesBase):
         self.__args = (cls, metacls, ) + interfaces
         Declaration.__init__(self, *(interfaces + (implementedBy(metacls), )))
 
+    def __repr__(self):
+        return "<%s.%s for %s>" % (
+            self.__class__.__module__,
+            self.__class__.__name__,
+            self._cls,
+        )
+
     def __reduce__(self):
         return self.__class__, self.__args
 
diff --git a/src/zope/interface/interface.py b/src/zope/interface/interface.py
index ade6f42..3e81b6f 100644
--- a/src/zope/interface/interface.py
+++ b/src/zope/interface/interface.py
@@ -283,7 +283,14 @@ class Specification(SpecificationBase):
         implied = self._implied
         implied.clear()
 
-        ancestors = ro(self)
+        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:
@@ -647,7 +654,9 @@ class Attribute(Element):
         return ""
 
     def __str__(self):
-        of = self.interface.__name__ + '.' if self.interface else ''
+        of = ''
+        if self.interface is not None:
+            of = self.interface.__module__ + '.' + self.interface.__name__ + '.'
         return of + self.__name__ + self._get_str_info()
 
     def __repr__(self):
diff --git a/src/zope/interface/interfaces.py b/src/zope/interface/interfaces.py
index 6ac235a..bf0d6c7 100644
--- a/src/zope/interface/interfaces.py
+++ b/src/zope/interface/interfaces.py
@@ -441,6 +441,11 @@ class IInterfaceDeclaration(Interface):
         instances of ``A`` and ``B`` provide.
         """
 
+    def classImplementsFirst(cls, interface):
+        """
+        See :func:`zope.interface.classImplementsFirst`.
+        """
+
     def implementer(*interfaces):
         """Create a decorator for declaring interfaces implemented by a factory.
 
diff --git a/src/zope/interface/registry.py b/src/zope/interface/registry.py
index 3f1306f..90ae1ad 100644
--- a/src/zope/interface/registry.py
+++ b/src/zope/interface/registry.py
@@ -550,7 +550,7 @@ def _getAdapterRequired(factory, required):
                 r = implementedBy(r)
             else:
                 raise TypeError("Required specification must be a "
-                                "specification or class."
+                                "specification or class, not %r" % type(r)
                                 )
         result.append(r)
     return tuple(result)
diff --git a/src/zope/interface/ro.py b/src/zope/interface/ro.py
index 855f101..dbffb53 100644
--- a/src/zope/interface/ro.py
+++ b/src/zope/interface/ro.py
@@ -11,15 +11,71 @@
 # FOR A PARTICULAR PURPOSE.
 #
 ##############################################################################
-"""Compute a resolution order for an object and its bases
 """
+Compute a resolution order for an object and its bases.
+
+.. versionchanged:: 5.0
+   The resolution order is now based on the same C3 order that Python
+   uses for classes. In complex instances of multiple inheritance, this
+   may result in a different ordering.
+
+   In older versions, the ordering wasn't required to be C3 compliant,
+   and for backwards compatibility, it still isn't. If the ordering
+   isn't C3 compliant (if it is *inconsistent*), zope.interface will
+   make a best guess to try to produce a reasonable resolution order.
+   Still (just as before), the results in such cases may be
+   surprising.
+
+.. rubric:: Environment Variables
+
+Due to the change in 5.0, certain environment variables can be used to control errors
+and warnings about inconsistent resolution orders. They are listed in priority order, with
+variables at the bottom generally overriding variables above them.
+
+ZOPE_INTERFACE_WARN_BAD_IRO
+    If this is set to "1", then if there is at least one inconsistent resolution
+    order discovered, a warning (:class:`InconsistentResolutionOrderWarning`) will
+    be issued. Use the usual warning mechanisms to control this behaviour. The warning
+    text will contain additional information on debugging.
+ZOPE_INTERFACE_TRACK_BAD_IRO
+    If this is set to "1", then zope.interface will log information about each
+    inconsistent resolution order discovered, and keep those details in memory in this module
+    for later inspection.
+ZOPE_INTERFACE_STRICT_IRO
+    If this is set to "1", any attempt to use :func:`ro` that would produce a non-C3
+    ordering will fail by raising :class:`InconsistentResolutionOrderError`.
+
+There are two environment variables that are independent.
+
+ZOPE_INTERFACE_LOG_CHANGED_IRO
+    If this is set to "1", then if the C3 resolution order is different from
+    the legacy resolution order for any given object, a message explaining the differences
+    will be logged. This is intended to be used for debugging complicated IROs.
+ZOPE_INTERFACE_USE_LEGACY_IRO
+    If this is set to "1", then the C3 resolution order will *not* be used. The
+    legacy IRO will be used instead. This is a temporary measure and will be removed in the
+    future. It is intended to help during the transition.
+    It implies ``ZOPE_INTERFACE_LOG_CHANGED_IRO``.
+"""
+from __future__ import print_function
 __docformat__ = 'restructuredtext'
 
 __all__ = [
     'ro',
+    'InconsistentResolutionOrderError',
+    'InconsistentResolutionOrderWarning',
 ]
 
-def _mergeOrderings(orderings):
+__logger = None
+
+def _logger():
+    global __logger # pylint:disable=global-statement
+    if __logger is None:
+        import logging
+        __logger = logging.getLogger(__name__)
+    return __logger
+
+def _legacy_mergeOrderings(orderings):
     """Merge multiple orderings so that within-ordering order is preserved
 
     Orderings are constrained in such a way that if an object appears
@@ -38,18 +94,18 @@ def _mergeOrderings(orderings):
 
     """
 
-    seen = {}
+    seen = set()
     result = []
     for ordering in reversed(orderings):
         for o in reversed(ordering):
             if o not in seen:
-                seen[o] = 1
+                seen.add(o)
                 result.insert(0, o)
 
     return result
 
-def _flatten(ob):
-    result = [ob]
+def _legacy_flatten(begin):
+    result = [begin]
     i = 0
     for ob in iter(result):
         i += 1
@@ -61,8 +117,489 @@ def _flatten(ob):
         result[i:i] = ob.__bases__
     return result
 
+def _legacy_ro(ob):
+    return _legacy_mergeOrderings([_legacy_flatten(ob)])
+
+###
+# Compare base objects using identity, not equality. This matches what
+# the CPython MRO algorithm does, and is *much* faster to boot: that,
+# plus some other small tweaks makes the difference between 25s and 6s
+# in loading 446 plone/zope interface.py modules (1925 InterfaceClass,
+# 1200 Implements, 1100 ClassProvides objects)
+###
+
+
+class InconsistentResolutionOrderWarning(PendingDeprecationWarning):
+    """
+    The warning issued when an invalid IRO is requested.
+    """
+
+class InconsistentResolutionOrderError(TypeError):
+    """
+    The error raised when an invalid IRO is requested in strict mode.
+    """
+
+    def __init__(self, c3, base_tree_remaining):
+        self.C = c3.leaf
+        base_tree = c3.base_tree
+        self.base_ros = {
+            base: base_tree[i + 1]
+            for i, base in enumerate(self.C.__bases__)
+        }
+        # Unfortunately, this doesn't necessarily directly match
+        # up to any transformation on C.__bases__, because
+        # if any were fully used up, they were removed already.
+        self.base_tree_remaining = base_tree_remaining
+
+        TypeError.__init__(self)
+
+    def __str__(self):
+        import pprint
+        return "%s: For object %r.\nBase ROs:\n%s\nConflict Location:\n%s" % (
+            self.__class__.__name__,
+            self.C,
+            pprint.pformat(self.base_ros),
+            pprint.pformat(self.base_tree_remaining),
+        )
+
+
+class _ClassBoolFromEnv(object):
+    """
+    Non-data descriptor that reads a transformed environment variable
+    as a boolean, and caches the result in the class.
+    """
+
+    def __get__(self, inst, klass):
+        import os
+        for cls in klass.__mro__:
+            my_name = None
+            for k in dir(klass):
+                if k in cls.__dict__ and cls.__dict__[k] is self:
+                    my_name = k
+                    break
+            if my_name is not None:
+                break
+        else: # pragma: no cover
+            raise RuntimeError("Unable to find self")
+
+        env_name = 'ZOPE_INTERFACE_' + my_name
+        val = os.environ.get(env_name, '') == '1'
+        setattr(klass, my_name, val)
+        setattr(klass, 'ORIG_' + my_name, self)
+        return val
+
+
+class C3(object):
+    # Holds the shared state during computation of an MRO.
+
+    @staticmethod
+    def resolver(C, strict):
+        strict = strict if strict is not None else C3.STRICT_RO
+        factory = C3
+        if strict:
+            factory = _StrictC3
+        elif C3.TRACK_BAD_IRO:
+            factory = _TrackingC3
+
+        return factory(C, {})
+
+    __mro = None
+    __legacy_ro = None
+    direct_inconsistency = False
+
+    def __init__(self, C, memo):
+        self.leaf = C
+        self.memo = memo
+        kind = self.__class__
+
+        base_resolvers = []
+        for base in C.__bases__:
+            if base not in memo:
+                resolver = kind(base, memo)
+                memo[base] = resolver
+            base_resolvers.append(memo[base])
+
+        self.base_tree = [
+            [C]
+        ] + [
+            memo[base].mro() for base in C.__bases__
+        ] + [
+            list(C.__bases__)
+        ]
+
+        self.bases_had_inconsistency = any(base.had_inconsistency for base in base_resolvers)
+
+    @property
+    def had_inconsistency(self):
+        return self.direct_inconsistency or self.bases_had_inconsistency
+
+    @property
+    def legacy_ro(self):
+        if self.__legacy_ro is None:
+            self.__legacy_ro = tuple(_legacy_ro(self.leaf))
+        return list(self.__legacy_ro)
+
+    TRACK_BAD_IRO = _ClassBoolFromEnv()
+    STRICT_RO = _ClassBoolFromEnv()
+    WARN_BAD_IRO = _ClassBoolFromEnv()
+    LOG_CHANGED_IRO = _ClassBoolFromEnv()
+    USE_LEGACY_IRO = _ClassBoolFromEnv()
+    BAD_IROS = ()
+
+    def _warn_iro(self):
+        if not self.WARN_BAD_IRO:
+            # For the initial release, one must opt-in to see the warning.
+            # In the future (2021?) seeing at least the first warning will
+            # be the default
+            return
+        import warnings
+        warnings.warn(
+            "An inconsistent resolution order is being requested. "
+            "(Interfaces should follow the Python class rules known as C3.) "
+            "For backwards compatibility, zope.interface will allow this, "
+            "making the best guess it can to produce as meaningful an order as possible. "
+            "In the future this might be an error. Set the warning filter to error, or set "
+            "the environment variable 'ZOPE_INTERFACE_TRACK_BAD_IRO' to '1' and examine "
+            "ro.C3.BAD_IROS to debug, or set 'ZOPE_INTERFACE_STRICT_IRO' to raise exceptions.",
+            InconsistentResolutionOrderWarning,
+        )
+
+    @staticmethod
+    def _can_choose_base(base, base_tree_remaining):
+        # From C3:
+        # nothead = [s for s in nonemptyseqs if cand in s[1:]]
+        for bases in base_tree_remaining:
+            if not bases or bases[0] is base:
+                continue
+
+            for b in bases:
+                if b is base:
+                    return False
+        return True
+
+    @staticmethod
+    def _nonempty_bases_ignoring(base_tree, ignoring):
+        return list(filter(None, [
+            [b for b in bases if b is not ignoring]
+            for bases
+            in base_tree
+        ]))
+
+    def _choose_next_base(self, base_tree_remaining):
+        """
+        Return the next base.
+
+        The return value will either fit the C3 constraints or be our best
+        guess about what to do. If we cannot guess, this may raise an exception.
+        """
+        base = self._find_next_C3_base(base_tree_remaining)
+        if base is not None:
+            return base
+        return self._guess_next_base(base_tree_remaining)
+
+    def _find_next_C3_base(self, base_tree_remaining):
+        """
+        Return the next base that fits the constraints, or ``None`` if there isn't one.
+        """
+        for bases in base_tree_remaining:
+            base = bases[0]
+            if self._can_choose_base(base, base_tree_remaining):
+                return base
+        return None
+
+    class _UseLegacyRO(Exception):
+        pass
+
+    def _guess_next_base(self, base_tree_remaining):
+        # Narf. We may have an inconsistent order (we won't know for
+        # sure until we check all the bases). Python cannot create
+        # classes like this:
+        #
+        # class B1:
+        #   pass
+        # class B2(B1):
+        #   pass
+        # class C(B1, B2): # -> TypeError; this is like saying C(B1, B2, B1).
+        #  pass
+        #
+        # However, older versions of zope.interface were fine with this order.
+        # A good example is ``providedBy(IOError())``. Because of the way
+        # ``classImplements`` works, it winds up with ``__bases__`` ==
+        # ``[IEnvironmentError, IIOError, IOSError, <implementedBy Exception>]``
+        # (on Python 3). But ``IEnvironmentError`` is a base of both ``IIOError``
+        # and ``IOSError``. Previously, we would get a resolution order of
+        # ``[IIOError, IOSError, IEnvironmentError, IStandardError, IException, Interface]``
+        # but the standard Python algorithm would forbid creating that order entirely.
 
-def ro(object):
-    """Compute a "resolution order" for an object
+        # Unlike Python's MRO, we attempt to resolve the issue. A few
+        # heuristics have been tried. One was:
+        #
+        # Strip off the first (highest priority) base of each direct
+        # base one at a time and seeing if we can come to an agreement
+        # with the other bases. (We're trying for a partial ordering
+        # here.) This often resolves cases (such as the IOSError case
+        # above), and frequently produces the same ordering as the
+        # legacy MRO did. If we looked at all the highest priority
+        # bases and couldn't find any partial ordering, then we strip
+        # them *all* out and begin the C3 step again. We take care not
+        # to promote a common root over all others.
+        #
+        # If we only did the first part, stripped off the first
+        # element of the first item, we could resolve simple cases.
+        # But it tended to fail badly. If we did the whole thing, it
+        # could be extremely painful from a performance perspective
+        # for deep/wide things like Zope's OFS.SimpleItem.Item. Plus,
+        # anytime you get ExtensionClass.Base into the mix, you're
+        # likely to wind up in trouble, because it messes with the MRO
+        # of classes. Sigh.
+        #
+        # So now, we fall back to the old linearization (fast to compute).
+        self._warn_iro()
+        self.direct_inconsistency = InconsistentResolutionOrderError(self, base_tree_remaining)
+        raise self._UseLegacyRO
+
+    def _merge(self):
+        # Returns a merged *list*.
+        result = self.__mro = []
+        base_tree_remaining = self.base_tree
+        base = None
+        while 1:
+            # Take last picked base out of the base tree wherever it is.
+            # This differs slightly from the standard Python MRO and is needed
+            # because we have no other step that prevents duplicates
+            # from coming in (e.g., in the inconsistent fallback path)
+            base_tree_remaining = self._nonempty_bases_ignoring(base_tree_remaining, base)
+
+            if not base_tree_remaining:
+                return result
+            try:
+                base = self._choose_next_base(base_tree_remaining)
+            except self._UseLegacyRO:
+                self.__mro = self.legacy_ro
+                return self.legacy_ro
+
+            result.append(base)
+
+    def mro(self):
+        if self.__mro is None:
+            self.__mro = tuple(self._merge())
+        return list(self.__mro)
+
+
+class _StrictC3(C3):
+    __slots__ = ()
+    def _guess_next_base(self, base_tree_remaining):
+        raise InconsistentResolutionOrderError(self, base_tree_remaining)
+
+
+class _TrackingC3(C3):
+    __slots__ = ()
+    def _guess_next_base(self, base_tree_remaining):
+        import traceback
+        bad_iros = C3.BAD_IROS
+        if self.leaf not in bad_iros:
+            if bad_iros == ():
+                import weakref
+                # This is a race condition, but it doesn't matter much.
+                bad_iros = C3.BAD_IROS = weakref.WeakKeyDictionary()
+            bad_iros[self.leaf] = t = (
+                InconsistentResolutionOrderError(self, base_tree_remaining),
+                traceback.format_stack()
+            )
+            _logger().warning("Tracking inconsistent IRO: %s", t[0])
+        return C3._guess_next_base(self, base_tree_remaining)
+
+
+class _ROComparison(object):
+    # Exists to compute and print a pretty string comparison
+    # for differing ROs.
+    # Since we're used in a logging context, and may actually never be printed,
+    # this is a class so we can defer computing the diff until asked.
+
+    # Components we use to build up the comparison report
+    class Item(object):
+        prefix = '  '
+        def __init__(self, item):
+            self.item = item
+        def __str__(self):
+            return "%s%s" % (
+                self.prefix,
+                self.item,
+            )
+
+    class Deleted(Item):
+        prefix = '- '
+
+    class Inserted(Item):
+        prefix = '+ '
+
+    Empty = str
+
+    class ReplacedBy(object): # pragma: no cover
+        prefix = '- '
+        suffix = ''
+        def __init__(self, chunk, total_count):
+            self.chunk = chunk
+            self.total_count = total_count
+
+        def __iter__(self):
+            lines = [
+                self.prefix + str(item) + self.suffix
+                for item in self.chunk
+            ]
+            while len(lines) < self.total_count:
+                lines.append('')
+
+            return iter(lines)
+
+    class Replacing(ReplacedBy):
+        prefix = "+ "
+        suffix = ''
+
+
+    _c3_report = None
+    _legacy_report = None
+
+    def __init__(self, c3, c3_ro, legacy_ro):
+        self.c3 = c3
+        self.c3_ro = c3_ro
+        self.legacy_ro = legacy_ro
+
+    def __move(self, from_, to_, chunk, operation):
+        for x in chunk:
+            to_.append(operation(x))
+            from_.append(self.Empty())
+
+    def _generate_report(self):
+        if self._c3_report is None:
+            import difflib
+            # The opcodes we get describe how to turn 'a' into 'b'. So
+            # the old one (legacy) needs to be first ('a')
+            matcher = difflib.SequenceMatcher(None, self.legacy_ro, self.c3_ro)
+            # The reports are equal length sequences. We're going for a
+            # side-by-side diff.
+            self._c3_report = c3_report = []
+            self._legacy_report = legacy_report = []
+            for opcode, leg1, leg2, c31, c32 in matcher.get_opcodes():
+                c3_chunk = self.c3_ro[c31:c32]
+                legacy_chunk = self.legacy_ro[leg1:leg2]
+
+                if opcode == 'equal':
+                    # Guaranteed same length
+                    c3_report.extend((self.Item(x) for x in c3_chunk))
+                    legacy_report.extend(self.Item(x) for x in legacy_chunk)
+                if opcode == 'delete':
+                    # Guaranteed same length
+                    assert not c3_chunk
+                    self.__move(c3_report, legacy_report, legacy_chunk, self.Deleted)
+                if opcode == 'insert':
+                    # Guaranteed same length
+                    assert not legacy_chunk
+                    self.__move(legacy_report, c3_report, c3_chunk, self.Inserted)
+                if opcode == 'replace': # pragma: no cover (How do you make it output this?)
+                    # Either side could be longer.
+                    chunk_size = max(len(c3_chunk), len(legacy_chunk))
+                    c3_report.extend(self.Replacing(c3_chunk, chunk_size))
+                    legacy_report.extend(self.ReplacedBy(legacy_chunk, chunk_size))
+
+        return self._c3_report, self._legacy_report
+
+    @property
+    def _inconsistent_label(self):
+        inconsistent = []
+        if self.c3.direct_inconsistency:
+            inconsistent.append('direct')
+        if self.c3.bases_had_inconsistency:
+            inconsistent.append('bases')
+        return '+'.join(inconsistent) if inconsistent else 'no'
+
+    def __str__(self):
+        c3_report, legacy_report = self._generate_report()
+        assert len(c3_report) == len(legacy_report)
+
+        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)
+
+        padding = ' ' * 2
+        max_left = max(len(x) for x in left_lines)
+        max_right = max(len(x) for x in right_lines)
+
+        left_title = 'Legacy RO (len=%s)' % (len(self.legacy_ro),)
+
+        right_title = 'C3 RO (len=%s; inconsistent=%s)' % (
+            len(self.c3_ro),
+            self._inconsistent_label,
+        )
+        lines = [
+            (padding + left_title.ljust(max_left) + padding + right_title.ljust(max_right)),
+            padding + '=' * (max_left + len(padding) + max_right)
+        ]
+        lines += [
+            padding + left.ljust(max_left) + padding + right
+            for left, right in zip(left_lines, right_lines)
+        ]
+
+        return '\n'.join(lines)
+
+
+def ro(C, strict=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
+       Add the *strict*, *log_changed_ro* and *use_legacy_ro*
+       keyword arguments. These are provisional and likely to be
+       removed in the future. They are most useful for testing.
+    """
+    resolver = C3.resolver(C, strict)
+    mro = resolver.mro()
+
+    log_changed = log_changed_ro if log_changed_ro is not None else resolver.LOG_CHANGED_IRO
+    use_legacy = use_legacy_ro if use_legacy_ro is not None else resolver.USE_LEGACY_IRO
+
+    if log_changed or use_legacy:
+        legacy_ro = resolver.legacy_ro
+        assert isinstance(legacy_ro, list)
+        assert isinstance(mro, list)
+        if legacy_ro != mro:
+            comparison = _ROComparison(resolver, mro, legacy_ro)
+            _logger().warning(
+                "Object %r has different legacy and C3 MROs:\n%s",
+                C, comparison
+            )
+        if resolver.had_inconsistency and legacy_ro == mro:
+            comparison = _ROComparison(resolver, mro, legacy_ro)
+            _logger().warning(
+                "Object %r had inconsistent IRO and used the legacy RO:\n%s"
+                "\nInconsistency entered at:\n%s",
+                C, comparison, resolver.direct_inconsistency
+            )
+        if use_legacy:
+            return legacy_ro
+
+    return mro
+
+
+def is_consistent(C):
+    """
+    Check if the resolution order for *C*, as computed by :func:`ro`, is consistent
+    according to C3.
     """
-    return _mergeOrderings([_flatten(object)])
+    return not C3.resolver(C, False).had_inconsistency
diff --git a/src/zope/interface/tests/test_declarations.py b/src/zope/interface/tests/test_declarations.py
index ccf4dde..0cdb326 100644
--- a/src/zope/interface/tests/test_declarations.py
+++ b/src/zope/interface/tests/test_declarations.py
@@ -191,9 +191,13 @@ class DeclarationTests(unittest.TestCase):
         from zope.interface.interface import InterfaceClass
         IFoo = InterfaceClass('IFoo')
         IBar = InterfaceClass('IBar')
+        # This is the same as calling ``Declaration(IBar, IFoo, IBar)``
+        # which doesn't make much sense, but here it is. In older
+        # versions of zope.interface, the __iro__ would have been
+        # IFoo, IBar, Interface, which especially makes no sense.
         decl = self._makeOne(IBar, (IFoo, IBar))
         # Note that decl.__iro__ has IFoo first.
-        self.assertEqual(list(decl.flattened()), [IFoo, IBar, Interface])
+        self.assertEqual(list(decl.flattened()), [IBar, IFoo, Interface])
 
     def test___sub___unrelated_interface(self):
         from zope.interface.interface import InterfaceClass
@@ -1122,6 +1126,13 @@ class ProvidesClassTests(unittest.TestCase):
             return foo.__provides__
         self.assertRaises(AttributeError, _test)
 
+    def test__repr__(self):
+        inst = self._makeOne(type(self))
+        self.assertEqual(
+            repr(inst),
+            "<zope.interface.Provides for %r>"  % type(self)
+        )
+
 
 class Test_Provides(unittest.TestCase):
 
@@ -1391,6 +1402,12 @@ class ClassProvidesTests(unittest.TestCase):
         self.assertEqual(cp.__reduce__(),
                          (self._getTargetClass(), (Foo, type(Foo), IBar)))
 
+    def test__repr__(self):
+        inst = self._makeOne(type(self), type)
+        self.assertEqual(
+            repr(inst),
+            "<zope.interface.declarations.ClassProvides for %r>"  % type(self)
+        )
 
 class Test_directlyProvidedBy(unittest.TestCase):
 
diff --git a/src/zope/interface/tests/test_interface.py b/src/zope/interface/tests/test_interface.py
index 7bde955..df7f84b 100644
--- a/src/zope/interface/tests/test_interface.py
+++ b/src/zope/interface/tests/test_interface.py
@@ -1911,7 +1911,7 @@ class AttributeTests(ElementTests):
         method.interface = type(self)
         r = repr(method)
         self.assertTrue(r.startswith('<zope.interface.interface.Attribute object at'), r)
-        self.assertTrue(r.endswith(' AttributeTests.TestAttribute>'), r)
+        self.assertTrue(r.endswith(' ' + __name__ + '.AttributeTests.TestAttribute>'), r)
 
     def test__repr__wo_interface(self):
         method = self._makeOne()
@@ -1923,7 +1923,7 @@ class AttributeTests(ElementTests):
         method = self._makeOne()
         method.interface = type(self)
         r = str(method)
-        self.assertEqual(r, 'AttributeTests.TestAttribute')
+        self.assertEqual(r, __name__ + '.AttributeTests.TestAttribute')
 
     def test__str__wo_interface(self):
         method = self._makeOne()
@@ -1998,7 +1998,7 @@ class MethodTests(AttributeTests):
         method.interface = type(self)
         r = repr(method)
         self.assertTrue(r.startswith('<zope.interface.interface.Method object at'), r)
-        self.assertTrue(r.endswith(' MethodTests.TestMethod(**kw)>'), r)
+        self.assertTrue(r.endswith(' ' + __name__ + '.MethodTests.TestMethod(**kw)>'), r)
 
     def test__repr__wo_interface(self):
         method = self._makeOne()
@@ -2012,7 +2012,7 @@ class MethodTests(AttributeTests):
         method.kwargs = 'kw'
         method.interface = type(self)
         r = str(method)
-        self.assertEqual(r, 'MethodTests.TestMethod(**kw)')
+        self.assertEqual(r, __name__ + '.MethodTests.TestMethod(**kw)')
 
     def test__str__wo_interface(self):
         method = self._makeOne()
diff --git a/src/zope/interface/tests/test_ro.py b/src/zope/interface/tests/test_ro.py
index 0756c6d..3a516b5 100644
--- a/src/zope/interface/tests/test_ro.py
+++ b/src/zope/interface/tests/test_ro.py
@@ -14,12 +14,13 @@
 """Resolution ordering utility tests"""
 import unittest
 
+# pylint:disable=blacklisted-name,protected-access,attribute-defined-outside-init
 
 class Test__mergeOrderings(unittest.TestCase):
 
     def _callFUT(self, orderings):
-        from zope.interface.ro import _mergeOrderings
-        return _mergeOrderings(orderings)
+        from zope.interface.ro import _legacy_mergeOrderings
+        return _legacy_mergeOrderings(orderings)
 
     def test_empty(self):
         self.assertEqual(self._callFUT([]), [])
@@ -30,7 +31,7 @@ class Test__mergeOrderings(unittest.TestCase):
     def test_w_duplicates(self):
         self.assertEqual(self._callFUT([['a'], ['b', 'a']]), ['b', 'a'])
 
-    def test_suffix_across_multiple_duplicats(self):
+    def test_suffix_across_multiple_duplicates(self):
         O1 = ['x', 'y', 'z']
         O2 = ['q', 'z']
         O3 = [1, 3, 5]
@@ -42,8 +43,8 @@ class Test__mergeOrderings(unittest.TestCase):
 class Test__flatten(unittest.TestCase):
 
     def _callFUT(self, ob):
-        from zope.interface.ro import _flatten
-        return _flatten(ob)
+        from zope.interface.ro import _legacy_flatten
+        return _legacy_flatten(ob)
 
     def test_w_empty_bases(self):
         class Foo(object):
@@ -78,10 +79,10 @@ class Test__flatten(unittest.TestCase):
 
 
 class Test_ro(unittest.TestCase):
-
-    def _callFUT(self, ob):
-        from zope.interface.ro import ro
-        return ro(ob)
+    maxDiff = None
+    def _callFUT(self, ob, **kwargs):
+        from zope.interface.ro import _legacy_ro
+        return _legacy_ro(ob, **kwargs)
 
     def test_w_empty_bases(self):
         class Foo(object):
@@ -113,3 +114,286 @@ class Test_ro(unittest.TestCase):
             pass
         self.assertEqual(self._callFUT(Qux),
                          [Qux, Bar, Baz, Foo, object])
+
+    def _make_IOErr(self):
+        # This can't be done in the standard C3 ordering.
+        class Foo(object):
+            def __init__(self, name, *bases):
+                self.__name__ = name
+                self.__bases__ = bases
+            def __repr__(self): # pragma: no cover
+                return self.__name__
+
+        # Mimic what classImplements(IOError, IIOError)
+        # does.
+        IEx = Foo('IEx')
+        IStdErr = Foo('IStdErr', IEx)
+        IEnvErr = Foo('IEnvErr', IStdErr)
+        IIOErr = Foo('IIOErr', IEnvErr)
+        IOSErr = Foo('IOSErr', IEnvErr)
+
+        IOErr = Foo('IOErr', IEnvErr, IIOErr, IOSErr)
+        return IOErr, [IOErr, IIOErr, IOSErr, IEnvErr, IStdErr, IEx]
+
+    def test_non_orderable(self):
+        IOErr, bases = self._make_IOErr()
+
+        self.assertEqual(self._callFUT(IOErr), bases)
+
+    def test_mixed_inheritance_and_implementation(self):
+        # https://github.com/zopefoundation/zope.interface/issues/8
+        # This test should fail, but doesn't, as described in that issue.
+        # pylint:disable=inherit-non-class
+        from zope.interface import implementer
+        from zope.interface import Interface
+        from zope.interface import providedBy
+        from zope.interface import implementedBy
+
+        class IFoo(Interface):
+            pass
+
+        @implementer(IFoo)
+        class ImplementsFoo(object):
+            pass
+
+        class ExtendsFoo(ImplementsFoo):
+            pass
+
+        class ImplementsNothing(object):
+            pass
+
+        class ExtendsFooImplementsNothing(ExtendsFoo, ImplementsNothing):
+            pass
+
+        self.assertEqual(
+            self._callFUT(providedBy(ExtendsFooImplementsNothing())),
+            [implementedBy(ExtendsFooImplementsNothing),
+             implementedBy(ExtendsFoo),
+             implementedBy(ImplementsFoo),
+             IFoo,
+             Interface,
+             implementedBy(ImplementsNothing),
+             implementedBy(object)])
+
+
+class Test_c3_ro(Test_ro):
+
+    def setUp(self):
+        Test_ro.setUp(self)
+        from zope.testing.loggingsupport import InstalledHandler
+        self.log_handler = handler = InstalledHandler('zope.interface.ro')
+        self.addCleanup(handler.uninstall)
+
+    def _callFUT(self, ob, **kwargs):
+        from zope.interface.ro import ro
+        return ro(ob, **kwargs)
+
+    def test_complex_diamond(self, base=object):
+        # https://github.com/zopefoundation/zope.interface/issues/21
+        O = base
+        class F(O):
+            pass
+        class E(O):
+            pass
+        class D(O):
+            pass
+        class C(D, F):
+            pass
+        class B(D, E):
+            pass
+        class A(B, C):
+            pass
+
+        if hasattr(A, 'mro'):
+            self.assertEqual(A.mro(), self._callFUT(A))
+
+        return A
+
+    def test_complex_diamond_interface(self):
+        from zope.interface import Interface
+
+        IA = self.test_complex_diamond(Interface)
+
+        self.assertEqual(
+            [x.__name__ for x in IA.__iro__],
+            ['A', 'B', 'C', 'D', 'E', 'F', 'Interface']
+        )
+
+    def test_complex_diamond_use_legacy_argument(self):
+        from zope.interface import Interface
+
+        A = self.test_complex_diamond(Interface)
+        legacy_A_iro = self._callFUT(A, use_legacy_ro=True)
+        self.assertNotEqual(A.__iro__, legacy_A_iro)
+
+        # And logging happened as a side-effect.
+        self._check_handler_complex_diamond()
+
+    def test_complex_diamond_compare_legacy_argument(self):
+        from zope.interface import Interface
+
+        A = self.test_complex_diamond(Interface)
+        computed_A_iro = self._callFUT(A, log_changed_ro=True)
+        # It matches, of course, but we did log a warning.
+        self.assertEqual(tuple(computed_A_iro), A.__iro__)
+        self._check_handler_complex_diamond()
+
+    def _check_handler_complex_diamond(self):
+        handler = self.log_handler
+        self.assertEqual(1, len(handler.records))
+        record = handler.records[0]
+
+        self.assertEqual('\n'.join(l.rstrip() for l in record.getMessage().splitlines()), """\
+Object <InterfaceClass zope.interface.tests.test_ro.A> has different legacy and C3 MROs:
+  Legacy RO (len=7)                                  C3 RO (len=7; inconsistent=no)
+  ====================================================================================================
+    <InterfaceClass zope.interface.tests.test_ro.A>    <InterfaceClass zope.interface.tests.test_ro.A>
+    <InterfaceClass zope.interface.tests.test_ro.B>    <InterfaceClass zope.interface.tests.test_ro.B>
+  - <InterfaceClass zope.interface.tests.test_ro.E>
+    <InterfaceClass zope.interface.tests.test_ro.C>    <InterfaceClass zope.interface.tests.test_ro.C>
+    <InterfaceClass zope.interface.tests.test_ro.D>    <InterfaceClass zope.interface.tests.test_ro.D>
+                                                     + <InterfaceClass zope.interface.tests.test_ro.E>
+    <InterfaceClass zope.interface.tests.test_ro.F>    <InterfaceClass zope.interface.tests.test_ro.F>
+    <InterfaceClass zope.interface.Interface>          <InterfaceClass zope.interface.Interface>""")
+
+    def test_ExtendedPathIndex_implement_thing_implementedby_super(self):
+        # See https://github.com/zopefoundation/zope.interface/pull/182#issuecomment-598754056
+        from zope.interface import ro
+        # pylint:disable=inherit-non-class
+        class _Based(object):
+            __bases__ = ()
+
+            def __init__(self, name, bases=(), attrs=None):
+                self.__name__ = name
+                self.__bases__ = bases
+
+            def __repr__(self):
+                return self.__name__
+
+        Interface = _Based('Interface', (), {})
+
+        class IPluggableIndex(Interface):
+            pass
+
+        class ILimitedResultIndex(IPluggableIndex):
+            pass
+
+        class IQueryIndex(IPluggableIndex):
+            pass
+
+        class IPathIndex(Interface):
+            pass
+
+        # A parent class who implements two distinct interfaces whose
+        # only common ancestor is Interface. An easy case.
+        # @implementer(IPathIndex, IQueryIndex)
+        # class PathIndex(object):
+        #     pass
+        obj = _Based('object')
+        PathIndex = _Based('PathIndex', (IPathIndex, IQueryIndex, obj))
+
+        # Child class that tries to put an interface the parent declares
+        # later ahead of the parent.
+        # @implementer(ILimitedResultIndex, IQueryIndex)
+        # class ExtendedPathIndex(PathIndex):
+        #     pass
+        ExtendedPathIndex = _Based('ExtendedPathIndex',
+                                   (ILimitedResultIndex, IQueryIndex, PathIndex))
+
+        # We were able to resolve it, and in exactly the same way as
+        # the legacy RO did, even though it is inconsistent.
+        result = self._callFUT(ExtendedPathIndex, log_changed_ro=True)
+        self.assertEqual(result, [
+            ExtendedPathIndex,
+            ILimitedResultIndex,
+            PathIndex,
+            IPathIndex,
+            IQueryIndex,
+            IPluggableIndex,
+            Interface,
+            obj])
+
+        record, = self.log_handler.records
+        self.assertIn('used the legacy', record.getMessage())
+
+        with self.assertRaises(ro.InconsistentResolutionOrderError):
+            self._callFUT(ExtendedPathIndex, strict=True)
+
+    def test_OSError_IOError(self):
+        if OSError is not IOError:
+            # Python 2
+            self.skipTest("Requires Python 3 IOError == OSError")
+        from zope.interface.common import interfaces
+        from zope.interface import providedBy
+
+        self.assertEqual(
+            list(providedBy(OSError()).flattened()),
+            [
+                interfaces.IOSError,
+                interfaces.IIOError,
+                interfaces.IEnvironmentError,
+                interfaces.IStandardError,
+                interfaces.IException,
+                interfaces.Interface,
+            ])
+
+    def test_non_orderable(self):
+        import warnings
+        from zope.interface import ro
+        try:
+            # If we've already warned, we must reset that state.
+            del ro.__warningregistry__
+        except AttributeError:
+            pass
+
+        with warnings.catch_warnings():
+            warnings.simplefilter('error')
+            orig_val = ro.C3.WARN_BAD_IRO
+            ro.C3.WARN_BAD_IRO = True
+            try:
+                with self.assertRaises(ro.InconsistentResolutionOrderWarning):
+                    super(Test_c3_ro, self).test_non_orderable()
+            finally:
+                ro.C3.WARN_BAD_IRO = orig_val
+
+        IOErr, _ = self._make_IOErr()
+        with self.assertRaises(ro.InconsistentResolutionOrderError):
+            self._callFUT(IOErr, strict=True)
+
+        old_val = ro.C3.TRACK_BAD_IRO
+        try:
+            ro.C3.TRACK_BAD_IRO = True
+            with warnings.catch_warnings():
+                warnings.simplefilter('ignore')
+                self._callFUT(IOErr)
+            self.assertIn(IOErr, ro.C3.BAD_IROS)
+        finally:
+            ro.C3.TRACK_BAD_IRO = old_val
+
+        iro = self._callFUT(IOErr)
+        legacy_iro = self._callFUT(IOErr, use_legacy_ro=True)
+        self.assertEqual(iro, legacy_iro)
+
+
+class Test_ROComparison(unittest.TestCase):
+
+    class MockC3(object):
+        direct_inconsistency = False
+        bases_had_inconsistency = False
+
+    def _makeOne(self, c3=None, c3_ro=(), legacy_ro=()):
+        from zope.interface.ro import _ROComparison
+        return _ROComparison(c3 or self.MockC3(), c3_ro, legacy_ro)
+
+    def test_inconsistent_label(self):
+        comp = self._makeOne()
+        self.assertEqual('no', comp._inconsistent_label)
+
+        comp.c3.direct_inconsistency = True
+        self.assertEqual("direct", comp._inconsistent_label)
+
+        comp.c3.bases_had_inconsistency = True
+        self.assertEqual("direct+bases", comp._inconsistent_label)
+
+        comp.c3.direct_inconsistency = False
+        self.assertEqual('bases', comp._inconsistent_label)