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.

4 files changed, 187 insertions, 47 deletions

diff --git a/docs/api/declarations.rst b/docs/api/declarations.rst
index cf38b7f..ce52833 100644
--- a/docs/api/declarations.rst
+++ b/docs/api/declarations.rst
@@ -34,22 +34,6 @@ implementer_only
 .. autoclass:: implementer_only
 
 
-implements
-----------
-
-.. caution:: Does not work on Python 3.  Use the `implementer` decorator instead.
-
-.. autofunction:: implements
-
-
-implementsOnly
---------------
-
-.. caution:: Does not work on Python 3.  Use the `implementer_only` decorator instead.
-
-.. autofunction:: implementsOnly
-
-
 classImplementsOnly
 -------------------
 
@@ -99,34 +83,137 @@ Consider the following example:
 
    >>> from zope.interface import Interface
    >>> from zope.interface import classImplements
+   >>> from zope.interface.ro import is_consistent
    >>> class I1(Interface): pass
    ...
    >>> class I2(Interface): pass
    ...
-   >>> class I3(Interface): pass
+   >>> class IA(Interface): pass
    ...
-   >>> class I4(Interface): pass
+   >>> class IB(Interface): pass
    ...
    >>> class I5(Interface): pass
    ...
-   >>> @implementer(I3)
+   >>> @implementer(IA)
    ... class A(object):
    ...     pass
-   >>> @implementer(I4)
+   >>> @implementer(IB)
    ... class B(object):
    ...     pass
    >>> class C(A, B):
    ...   pass
    >>> classImplements(C, I1, I2)
    >>> [i.getName() for i in implementedBy(C)]
-   ['I1', 'I2', 'I3', 'I4']
+   ['I1', 'I2', 'IA', 'IB']
+
+Instances of ``C`` provide ``I1`` and ``I2``, plus whatever
+instances of ``A`` and ``B`` provide.
+
+.. doctest::
+
    >>> classImplements(C, I5)
    >>> [i.getName() for i in implementedBy(C)]
-   ['I1', 'I2', 'I5', 'I3', 'I4']
+   ['I1', 'I2', 'I5', 'IA', 'IB']
+
+Instances of ``C`` now also provide ``I5``. Notice how ``I5`` was
+added to the *end* of the list of things provided directly by ``C``.
+
+If we ask a class to implement an interface that extends
+an interface it already implements, that interface will go at the
+*beginning* of the list, in order to preserve a consistent resolution
+order.
+
+.. doctest::
+
+   >>> class I6(I5): pass
+   >>> class I7(IA): pass
+   >>> classImplements(C, I6, I7)
+   >>> [i.getName() for i in implementedBy(C)]
+   ['I6', 'I1', 'I2', 'I5', 'I7', 'IA', 'IB']
+   >>> is_consistent(implementedBy(C))
+   True
+
+This cannot be used to introduce duplicates.
+
+.. doctest::
+
+   >>> classImplements(C, IA, IB, I1, I2)
+   >>> [i.getName() for i in implementedBy(C)]
+   ['I6', 'I1', 'I2', 'I5', 'I7', 'IA', 'IB']
+
+
+classImplementsFirst
+--------------------
+
+.. autofunction:: classImplementsFirst
+
+Consider the following example:
+
+.. doctest::
+
+   >>> from zope.interface import Interface
+   >>> from zope.interface import classImplements
+   >>> from zope.interface import classImplementsFirst
+   >>> class I1(Interface): pass
+   ...
+   >>> class I2(Interface): pass
+   ...
+   >>> class IA(Interface): pass
+   ...
+   >>> class IB(Interface): pass
+   ...
+   >>> class I5(Interface): pass
+   ...
+   >>> @implementer(IA)
+   ... class A(object):
+   ...     pass
+   >>> @implementer(IB)
+   ... class B(object):
+   ...     pass
+   >>> class C(A, B):
+   ...   pass
+   >>> classImplementsFirst(C, I2)
+   >>> classImplementsFirst(C, I1)
+   >>> [i.getName() for i in implementedBy(C)]
+   ['I1', 'I2', 'IA', 'IB']
 
 Instances of ``C`` provide ``I1``, ``I2``, ``I5``, and whatever
 interfaces instances of ``A`` and ``B`` provide.
 
+.. doctest::
+
+   >>> classImplementsFirst(C, I5)
+   >>> [i.getName() for i in implementedBy(C)]
+   ['I5', 'I1', 'I2', 'IA', 'IB']
+
+Instances of ``C`` now also provide ``I5``. Notice how ``I5`` was
+added to the *beginning* of the list of things provided directly by
+``C``. Unlike `classImplements`, this ignores inheritance and other
+factors and does not attempt to ensure a consistent resolution order.
+
+.. doctest::
+
+   >>> class IBA(IB, IA): pass
+   >>> classImplementsFirst(C, IBA)
+   >>> classImplementsFirst(C, IA)
+   >>> [i.getName() for i in implementedBy(C)]
+   ['IA', 'IBA', 'I5', 'I1', 'I2', 'IB']
+
+This cannot be used to introduce duplicates.
+
+.. doctest::
+
+   >>> len(implementedBy(C).declared)
+   5
+   >>> classImplementsFirst(C, IA)
+   >>> classImplementsFirst(C, IBA)
+   >>> classImplementsFirst(C, IA)
+   >>> classImplementsFirst(C, IBA)
+   >>> [i.getName() for i in implementedBy(C)]
+   ['IBA', 'IA', 'I5', 'I1', 'I2', 'IB']
+   >>> len(implementedBy(C).declared)
+   5
+
 
 directlyProvides
 ----------------
@@ -332,14 +419,6 @@ Removing an interface that is provided through the class is not possible:
    ValueError: Can only remove directly provided interfaces.
 
 
-classProvides
--------------
-
-.. caution:: Does not work on Python 3.  Use the `provider` decorator instead.
-
-.. autofunction:: classProvides
-
-
 provider
 --------
 
@@ -413,6 +492,33 @@ When registering an adapter or utility component, the registry looks for the
 provided.
 
 
+Deprecated Functions
+--------------------
+
+implements
+~~~~~~~~~~
+
+.. caution:: Does not work on Python 3.  Use the `implementer` decorator instead.
+
+.. autofunction:: implements
+
+
+implementsOnly
+~~~~~~~~~~~~~~
+
+.. caution:: Does not work on Python 3.  Use the `implementer_only` decorator instead.
+
+.. autofunction:: implementsOnly
+
+
+classProvides
+~~~~~~~~~~~~~
+
+.. caution:: Does not work on Python 3.  Use the `provider` decorator instead.
+
+.. autofunction:: classProvides
+
+
 Querying The Interfaces Of Objects
 ==================================
 
@@ -592,7 +698,7 @@ Exmples for :meth:`Declaration.flattened`:
    >>> spec = Declaration(I4, spec)
    >>> i = spec.flattened()
    >>> [x.getName() for x in i]
-   ['I4', 'I2', 'I1', 'I3', 'Interface']
+   ['I4', 'I2', 'I3', 'I1', 'Interface']
    >>> list(i)
    []
 
diff --git a/docs/api/index.rst b/docs/api/index.rst
index e6affd8..7266966 100644
--- a/docs/api/index.rst
+++ b/docs/api/index.rst
@@ -12,3 +12,4 @@ Contents:
    adapters
    components
    common
+   ro
diff --git a/docs/api/ro.rst b/docs/api/ro.rst
new file mode 100644
index 0000000..f14192a
--- /dev/null
+++ b/docs/api/ro.rst
@@ -0,0 +1,19 @@
+===========================================
+ Computing The Resolution Order (Priority)
+===========================================
+
+Just as Python classes have a method resolution order that determines
+which implementation of a method gets used when inheritance is used,
+interfaces have a resolution order that determines their ordering when
+searching for adapters.
+
+That order is computed by ``zope.interface.ro.ro``. This is an
+internal module not generally needed by a user of ``zope.interface``,
+but its documentation can be helpful to understand how orders are
+computed.
+
+``zope.interface.ro``
+=====================
+
+.. automodule:: zope.interface.ro
+   :member-order: alphabetical
diff --git a/docs/verify.rst b/docs/verify.rst
index 06a0a0f..bf602d0 100644
--- a/docs/verify.rst
+++ b/docs/verify.rst
@@ -23,10 +23,13 @@ that an object provides this interface.
    >>> from zope.interface import Interface, Attribute, implementer
    >>> from zope.interface import Invalid
    >>> from zope.interface.verify import verifyObject
+   >>> oname, __name__ = __name__, 'base' # Pretend we're in a module, not a doctest
    >>> class IBase(Interface):
    ...     x = Attribute("The X attribute")
+   >>> __name__ = 'module' # Pretend to be a different module.
    >>> class IFoo(IBase):
    ...     y = Attribute("The Y attribute")
+   >>> __name__ = oname; del oname
    >>> class Foo(object):
    ...     pass
    >>> def verify_foo(**kwargs):
@@ -48,8 +51,8 @@ defined.
    >>> verify_foo()
    The object <Foo...> has failed to implement interface <...IFoo>:
        Does not declaratively implement the interface
-       The IBase.x attribute was not provided
-       The IFoo.y attribute was not provided
+       The base.IBase.x attribute was not provided
+       The module.IFoo.y attribute was not provided
 
 If we add the two missing attributes, we still have the error about not
 declaring the correct interface.
@@ -116,13 +119,13 @@ exception.
    ... class Foo(object):
    ...     x = 1
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The IFoo.y attribute was not provided.
+   The object <Foo...> has failed to implement interface <...IFoo>: The module.IFoo.y attribute was not provided.
    >>> @implementer(IFoo)
    ... class Foo(object):
    ...     def __init__(self):
    ...         self.y = 2
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The IBase.x attribute was not provided.
+   The object <Foo...> has failed to implement interface <...IFoo>: The base.IBase.x attribute was not provided.
 
 If both attributes are missing, an exception is raised reporting
 both errors.
@@ -134,23 +137,25 @@ both errors.
     ...     pass
     >>> verify_foo()
     The object <Foo ...> has failed to implement interface <...IFoo>:
-        The IBase.x attribute was not provided
-        The IFoo.y attribute was not provided
+        The base.IBase.x attribute was not provided
+        The module.IFoo.y attribute was not provided
 
 If an attribute is implemented as a property that raises an ``AttributeError``
 when trying to get its value, the attribute is considered missing:
 
 .. doctest::
 
+   >>> oname, __name__ = __name__, 'module'
    >>> class IFoo(Interface):
    ...     x = Attribute('The X attribute')
+   >>> __name__ = oname; del oname
    >>> @implementer(IFoo)
    ... class Foo(object):
    ...     @property
    ...     def x(self):
    ...         raise AttributeError
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The IFoo.x attribute was not provided.
+   The object <Foo...> has failed to implement interface <...IFoo>: The module.IFoo.x attribute was not provided.
 
 
 Any other exception raised by a property will propagate to the caller of
@@ -190,13 +195,15 @@ that takes one argument. If we don't provide it, we get an error.
 
 .. doctest::
 
+   >>> oname, __name__ = __name__, 'module'
    >>> class IFoo(Interface):
    ...    def simple(arg1): "Takes one positional argument"
+   >>> __name__ = oname; del oname
    >>> @implementer(IFoo)
    ... class Foo(object):
    ...    pass
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The IFoo.simple(arg1) attribute was not provided.
+   The object <Foo...> has failed to implement interface <...IFoo>: The module.IFoo.simple(arg1) attribute was not provided.
 
 Once they exist, they are checked to be callable, and for compatible signatures.
 
@@ -206,7 +213,7 @@ Not being callable is an error.
 
    >>> Foo.simple = 42
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The contract of IFoo.simple(arg1) is violated because '42' is not a method.
+   The object <Foo...> has failed to implement interface <...IFoo>: The contract of module.IFoo.simple(arg1) is violated because '42' is not a method.
 
 Taking too few arguments is an error. (Recall that the ``self``
 argument is implicit.)
@@ -215,7 +222,7 @@ argument is implicit.)
 
    >>> Foo.simple = lambda self: "I take no arguments"
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The contract of IFoo.simple(arg1) is violated because '<lambda>()' doesn't allow enough arguments.
+   The object <Foo...> has failed to implement interface <...IFoo>: The contract of module.IFoo.simple(arg1) is violated because '<lambda>()' doesn't allow enough arguments.
 
 Requiring too many arguments is an error.
 
@@ -223,7 +230,7 @@ Requiring too many arguments is an error.
 
    >>> Foo.simple = lambda self, a, b: "I require two arguments"
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The contract of IFoo.simple(arg1) is violated because '<lambda>(a, b)' requires too many arguments.
+   The object <Foo...> has failed to implement interface <...IFoo>: The contract of module.IFoo.simple(arg1) is violated because '<lambda>(a, b)' requires too many arguments.
 
 Variable arguments can be used to implement the required number, as
 can arguments with defaults.
@@ -242,21 +249,25 @@ variable keyword arguments, the implementation must also accept them.
 
 .. doctest::
 
+   >>> oname, __name__ = __name__, 'module'
    >>> class IFoo(Interface):
    ...    def needs_kwargs(**kwargs): pass
+   >>> __name__ = oname; del oname
    >>> @implementer(IFoo)
    ... class Foo(object):
    ...     def needs_kwargs(self, a=1, b=2): pass
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The contract of IFoo.needs_kwargs(**kwargs) is violated because 'Foo.needs_kwargs(a=1, b=2)' doesn't support keyword arguments.
+   The object <Foo...> has failed to implement interface <...IFoo>: The contract of module.IFoo.needs_kwargs(**kwargs) is violated because 'Foo.needs_kwargs(a=1, b=2)' doesn't support keyword arguments.
 
+   >>> oname, __name__ = __name__, 'module'
    >>> class IFoo(Interface):
    ...    def needs_varargs(*args): pass
+   >>> __name__ = oname; del oname
    >>> @implementer(IFoo)
    ... class Foo(object):
    ...     def needs_varargs(self, **kwargs): pass
    >>> verify_foo()
-   The object <Foo...> has failed to implement interface <...IFoo>: The contract of IFoo.needs_varargs(*args) is violated because 'Foo.needs_varargs(**kwargs)' doesn't support variable arguments.
+   The object <Foo...> has failed to implement interface <...IFoo>: The contract of module.IFoo.needs_varargs(*args) is violated because 'Foo.needs_varargs(**kwargs)' doesn't support variable arguments.
 
 Of course, missing attributes are also found and reported, and the
 source interface of the missing attribute is included. Similarly, when
@@ -264,10 +275,13 @@ the failing method is from a parent class, that is also reported.
 
 .. doctest::
 
+   >>> oname, __name__ = __name__, 'base'
    >>> class IBase(Interface):
    ...    def method(arg1): "Takes one positional argument"
+   >>> __name__ = 'module'
    >>> class IFoo(IBase):
    ...    x = Attribute('The X attribute')
+   >>> __name__ = oname; del oname
    >>> class Base(object):
    ...    def method(self): "I don't have enough arguments"
    >>> @implementer(IFoo)
@@ -275,8 +289,8 @@ the failing method is from a parent class, that is also reported.
    ...    pass
    >>> verify_foo()
    The object <Foo...> has failed to implement interface <...IFoo>:
-       The contract of IBase.method(arg1) is violated because 'Base.method()' doesn't allow enough arguments
-       The IFoo.x attribute was not provided
+       The contract of base.IBase.method(arg1) is violated because 'Base.method()' doesn't allow enough arguments
+       The module.IFoo.x attribute was not provided
 
 Verifying Classes
 =================
@@ -299,4 +313,4 @@ attributes, cannot be verified.
     ...        print(e)
 
     >>> verify_foo_class()
-    The object <class 'Foo'> has failed to implement interface <...IFoo>: The contract of IBase.method(arg1) is violated because 'Base.method(self)' doesn't allow enough arguments.
+    The object <class 'Foo'> has failed to implement interface <...IFoo>: The contract of base.IBase.method(arg1) is violated because 'Base.method(self)' doesn't allow enough arguments.