Fixed the mros algorithm

3 files changed, 136 insertions, 112 deletions

diff --git a/src/decorator.py b/src/decorator.py
index d71ed60..2a96b4a 100644
--- a/src/decorator.py
+++ b/src/decorator.py
@@ -40,7 +40,6 @@ import re
 import sys
 import inspect
 import itertools
-import collections
 
 if sys.version >= '3':
     from inspect import getfullargspec
@@ -166,7 +165,6 @@ class FunctionMaker(object):
             src += '\n'  # this is needed in old versions of Python
         try:
             code = compile(src, '<string>', 'single')
-            # print >> sys.stderr, 'Compiling %s' % src
             exec(code, evaldict)
         except:
             print('Error in generated code:', file=sys.stderr)
@@ -282,27 +280,19 @@ contextmanager = decorator(ContextManager)
 
 # ############################ dispatch_on ############################ #
 
-def unique(classes):
+def append(a, vancestors):
     """
-    Return a tuple of unique classes by preserving the original order.
+    Append ``a`` to the list of the virtual ancestors, unless it is already
+    included.
     """
-    known = set([object])
-    outlist = []
-    for cl in classes:
-        if cl not in known:
-            outlist.append(cl)
-        known.add(cl)
-    return tuple(outlist)
-
-
-def insert(a, vancestors):
     for j, va in enumerate(vancestors):
-        if issubclass(a, va) and a is not va:
-            vancestors.insert(j, a)
+        if issubclass(va, a):
+            break
+        if issubclass(a, va):
+            vancestors[j] = a
             break
-    else:  # less specialized
-        if a not in vancestors:
-            vancestors.append(a)
+    else:
+        vancestors.append(a)
 
 
 # inspired from simplegeneric by P.J. Eby and functools.singledispatch
@@ -328,7 +318,7 @@ def dispatch_on(*dispatch_args):
         if not set(dispatch_args) <= argset:
             raise NameError('Unknown dispatch arguments %s' % dispatch_str)
 
-        typemap = collections.OrderedDict()
+        typemap = {}
 
         def vancestors(*types):
             """
@@ -339,8 +329,8 @@ def dispatch_on(*dispatch_args):
             for types_ in typemap:
                 for t, type_, ra in zip(types, types_, ras):
                     if issubclass(t, type_) and type_ not in t.__mro__:
-                        insert(type_, ra)
-            return ras
+                        append(type_, ra)
+            return map(set, ras)
 
         def mros(*types):
             """
@@ -348,12 +338,16 @@ def dispatch_on(*dispatch_args):
             """
             check(types)
             lists = []
-            for t, ancestors in zip(types, vancestors(*types)):
-                t_ancestors = unique(t.__bases__ + tuple(ancestors))
-                if not t_ancestors:
-                    mro = t.__mro__
+            for t, vas in zip(types, vancestors(*types)):
+                n_vas = len(vas)
+                if n_vas > 1:
+                    raise RuntimeError(
+                        'Ambiguous dispatch for %s: %s' % (t, vas))
+                elif n_vas == 1:
+                    va, = vas
+                    mro = type('t', (t, va), {}).__mro__[1:]
                 else:
-                    mro = type(t.__name__, t_ancestors, {}).__mro__
+                    mro = t.__mro__
                 lists.append(mro[:-1])  # discard object
             return lists
 
@@ -371,7 +365,7 @@ def dispatch_on(*dispatch_args):
                 return f
             return dec
 
-        def dispatch(dispatch_args, *args, **kw):
+        def _dispatch(dispatch_args, *args, **kw):
             "Dispatcher function"
             types = tuple(type(arg) for arg in dispatch_args)
             try:  # fast path
@@ -390,7 +384,7 @@ def dispatch_on(*dispatch_args):
 
         return FunctionMaker.create(
             func, 'return _f_(%s, %%(shortsignature)s)' % dispatch_str,
-            dict(_f_=dispatch), register=register, default=func,
+            dict(_f_=_dispatch), register=register, default=func,
             typemap=typemap, vancestors=vancestors, mros=mros,
             __wrapped__=func)
 
diff --git a/src/tests/documentation.py b/src/tests/documentation.py
index 6ce800b..4591611 100644
--- a/src/tests/documentation.py
+++ b/src/tests/documentation.py
@@ -666,18 +666,19 @@ functions dispatching on any argument; moreover it can manage
 dispatching on more than one argument and, of course, it is
 signature-preserving.
 
-Here I will give a very concrete example where it is desiderable to
-dispatch on the second argument. Suppose you have an XMLWriter class,
-which is instantiated with some configuration parameters and has
-a ``.write`` method which is able to serialize objects to XML:
+Here I will give a very concrete example (taken from a real-life use
+case) where it is desiderable to dispatch on the second
+argument. Suppose you have an XMLWriter class, which is instantiated
+with some configuration parameters and has a ``.write`` method which
+is able to serialize objects to XML:
 
 $$XMLWriter
 
 Here you want to dispatch on the second argument since the first, ``self``
-is already taken. The `dispatch_on` facility allows you to specify
+is already taken. The ``dispatch_on`` decorator factory allows you to specify
 the dispatch argument by simply passing its name as a string (notice
 that if you mispell the name you will get an error). The function
-decorated with `dispatch_on` is turned into a generic function
+decorated is turned into a generic function
 and it is the one which is called if there are no more specialized
 implementations. Usually such default function should raise a
 ``NotImplementedError``, thus forcing people to register some implementation.
@@ -747,10 +748,9 @@ Here is the result:
 Generic functions and virtual ancestors
 -------------------------------------------------
 
-Generic function implementations in Python are
-complicated by the existence of "virtual ancestors", i.e. superclasses
-which are not in the class hierarchy.
-Consider for instance this class:
+Generic function implementations in Python are complicated by the
+existence of "virtual ancestors", i.e. superclasses which are not in
+the class hierarchy.  Consider for instance this class:
 
 $$WithLength
 
@@ -762,8 +762,8 @@ considered to be a subclass of the abstract base class ``collections.Sized``:
  >>> issubclass(WithLength, collections.Sized)
  True
 
-However, ``collections.Sized`` is not an ancestor of ``WithLength``.
-Any implementation of generic functions, even
+However, ``collections.Sized`` is not in the MRO of ``WithLength``, it
+is not a true ancestor. Any implementation of generic functions, even
 with single dispatch, must go through some contorsion to take into
 account the virtual ancestors.
 
@@ -775,26 +775,22 @@ implemented on all classes with a length
 
 $$get_length_sized
 
-then ``get_length`` must be defined on ``WithLength`` instances:
+then ``get_length`` must be defined on ``WithLength`` instances
 
 .. code-block:: python
 
  >>> get_length(WithLength())
  0
 
-You can find the virtual ancestors of a given set of classes as follows:
-
- >> get_length.vancestors(WithLength,)
- [[<class 'collections.abc.Sized'>]]
-
+even if ``collections.Sized`` is not a true ancestor of ``WithLength``.
 Of course this is a contrived example since you could just use the
 builtin ``len``, but you should get the idea.
 
-The implementation of generic functions in the decorator module is
-still experimental. In this initial phase implicity was preferred
-over consistency with the way ``functools.singledispatch`` works in
-the standard library. So there some subtle differences in special
-cases. I will only show an example.
+Since in Python it is possible to consider any instance of ABCMeta
+as a virtual ancestor of any other class (it is enough to register it
+as ``ancestor.register(cls)``), any implementation of generic functions
+must take this feature into account. Let me give an example.
+
 Suppose you are using a third party set-like class like
 the following:
 
@@ -803,14 +799,14 @@ $$SomeSet
 Here the author of ``SomeSet`` made a mistake by not inheriting
 from ``collections.Set``, but only from ``collections.Sized``.
 
-This is not a problem since we can register *a posteriori*
-``collections.Set`` as a virtual ancestor of ``SomeSet`` (in
-general any instance of ``abc.ABCMeta`` can be registered to work
-as a virtual ancestor):
+This is not a problem since you can register *a posteriori*
+``collections.Set`` as a virtual ancestor of ``SomeSet``:
 
 .. code-block:: python
 
- >>> _ = collections.Set.register(SomeSet)  # issubclass(SomeSet, Set)
+ >>> _ = collections.Set.register(SomeSet)
+ >>> issubclass(SomeSet, collections.Set)
+ True
 
 Now, let us define an implementation of ``get_length`` specific to set:
 
@@ -823,34 +819,32 @@ implementation for ``Set`` is taken:
 .. code-block:: python
 
  >>> get_length(SomeSet())
- Traceback (most recent call last):
-   ...
- TypeError: Cannot create a consistent method resolution
- order (MRO) for bases Sized, Set
-
-Sometimes it is impossible to find the right implementation. Here is a
-situation with a type conflict. First of all, let us register
-
-.. code-block:: python
-
- >>> @get_length.register(collections.Iterable)
- ... def get_length_iterable(obj):
- ...     raise TypeError('Cannot get the length of an iterable')
-
-
-Since ``SomeSet`` is now both a (virtual) subclass
-of ``collections.Iterable`` and of ``collections.Sized``, which are
-not related by subclassing, it is impossible
-to decide which implementation should be taken. Consistently with
-the *refuse the temptation to guess* philosophy, an error is raised.
+ 1
 
- >>> get_length(SomeSet())
- Traceback (most recent call last):
-   ...
- TypeError: Cannot create a consistent method resolution
- order (MRO) for bases Iterable, Sized, Set
 
-``functools.singledispatch`` would raise a similar error in this case.
+The implementation of generic functions in the decorator module is
+still experimental. In this initial phase implicity was preferred
+over perfect consistency with the way ``functools.singledispatch`` works in
+the standard library. So there are some subtle differences in special
+cases.
+
+Considered a class ``C`` registered both as ``collections.Iterable``
+and ``collections.Sized`` and define a generic function ``g`` with
+implementations both for ``collections.Iterable`` and
+``collections.Sized``. It is impossible to decide which implementation
+to use, and the following code will fail with a RuntimeError:
+
+$$singledispatch_example
+
+This is consistent with the "refuse the temptation to guess"
+philosophy. ``functools.singledispatch`` will raise a similar error.
+It would be easy to rely on the order of registration to decide the
+precedence order. This is reasonable, but also fragile: if during some
+refactoring you change the registration order by mistake, a different
+implementation could be taken. If implementations of the generic
+functions are distributed across modules, and you change the import
+order, a different implementation could be taken. So the decorator
+module is using the same approach of the standard library.
 
 Finally let me notice that the decorator module implementation does
 not use any cache, whereas the one in ``singledispatch`` has a cache.
@@ -1456,3 +1450,44 @@ def get_length_sized(obj):
 @get_length.register(collections.Set)
 def get_length_set(obj):
     return 1
+
+
+@contextmanager
+def assertRaises(etype):
+    """This works in Python 2.6 too"""
+    try:
+        yield
+    except etype:
+        pass
+    else:
+        raise Exception('Expected %s' % etype.__name__)
+
+
+class C(object):
+    "Registered as Sized and Iterable"
+collections.Sized.register(C)
+collections.Iterable.register(C)
+
+
+def singledispatch_example():
+    singledispatch = dispatch_on('obj')
+
+    @singledispatch
+    def g(obj):
+        raise NotImplementedError(type(g))
+
+    @g.register(collections.Sized)
+    def g_sized(object):
+        return "sized"
+
+    @g.register(collections.Iterable)
+    def g_iterable(object):
+        return "iterable"
+
+    with assertRaises(RuntimeError):
+        g(C())  # Ambiguous dispatch: Iterable or Sized?
+
+
+if __name__ == '__main__':
+    import doctest
+    doctest.testmod()
diff --git a/src/tests/test.py b/src/tests/test.py
index af5998b..8413a58 100644
--- a/src/tests/test.py
+++ b/src/tests/test.py
@@ -4,35 +4,29 @@ import doctest
 import unittest
 import decimal
 import inspect
+import functools
 import collections
-from decorator import dispatch_on, contextmanager
+from decorator import dispatch_on
 try:
-    from . import documentation
+    from . import documentation as doc
 except (SystemError, ValueError):
-    import documentation
-
-
-@contextmanager
-def assertRaises(etype):
-    """This works in Python 2.6 too"""
-    try:
-        yield
-    except etype:
-        pass
-    else:
-        raise Exception('Expected %s' % etype.__name__)
+    import documentation as doc
 
 
 class DocumentationTestCase(unittest.TestCase):
     def test(self):
-        err = doctest.testmod(documentation)[0]
+        err = doctest.testmod(doc)[0]
         self.assertEqual(err, 0)
 
+    def test_singledispatch(self):
+        if hasattr(functools, 'singledispatch'):
+            doc.singledispatch_example()
+
 
 class ExtraTestCase(unittest.TestCase):
     def test_signature(self):
         if hasattr(inspect, 'signature'):
-            sig = inspect.signature(documentation.f1)
+            sig = inspect.signature(doc.f1)
             self.assertEqual(str(sig), '(x)')
 
 # ################### test dispatch_on ############################# #
@@ -100,7 +94,8 @@ class TestSingleDispatch(unittest.TestCase):
         def g(obj):
             return "base"
 
-        with assertRaises(TypeError):
+        with doc.assertRaises(TypeError):
+            # wrong number of arguments
             @g.register(int)
             def g_int():
                 return "int"
@@ -264,10 +259,10 @@ class TestSingleDispatch(unittest.TestCase):
         c.Iterable.register(O)
         self.assertEqual(g(o), "sized")
         c.Container.register(O)
-        self.assertEqual(g(o), "sized")
+        with doc.assertRaises(RuntimeError):
+            self.assertEqual(g(o), "sized")
         c.Set.register(O)
-        with assertRaises(TypeError):  # was ok
-            self.assertEqual(g(o), "set")
+        self.assertEqual(g(o), "set")
 
         class P(object):
             pass
@@ -277,8 +272,8 @@ class TestSingleDispatch(unittest.TestCase):
         self.assertEqual(g(p), "iterable")
         c.Container.register(P)
 
-        #with assertRaises(RuntimeError):
-        self.assertEqual(g(p), "iterable")
+        with doc.assertRaises(RuntimeError):
+            self.assertEqual(g(p), "iterable")
 
         class Q(c.Sized):
             def __len__(self):
@@ -288,9 +283,8 @@ class TestSingleDispatch(unittest.TestCase):
         c.Iterable.register(Q)
         self.assertEqual(g(q), "sized")
         c.Set.register(Q)
-        # self.assertEqual(g(q), "sized")
-        # could be because c.Set is a subclass of
-        # c.Sized and c.Iterable
+        self.assertEqual(g(q), "set")
+        # because c.Set is a subclass of c.Sized and c.Iterable
 
         @singledispatch
         def h(obj):
@@ -307,8 +301,8 @@ class TestSingleDispatch(unittest.TestCase):
         # this ABC is implicitly registered on defaultdict which makes all of
         # MutableMapping's bases implicit as well from defaultdict's
         # perspective.
-        #with assertRaises(RuntimeError):
-        h(c.defaultdict(lambda: 0))
+        with doc.assertRaises(RuntimeError):
+            self.assertEqual(h(c.defaultdict(lambda: 0)), "sized")
 
         class R(c.defaultdict):
             pass
@@ -326,7 +320,7 @@ class TestSingleDispatch(unittest.TestCase):
         def i_sequence(arg):
             return "sequence"
         r = R()
-        self.assertEqual(i(r), "mapping")  # was sequence
+        #self.assertEqual(i(r), "mapping")  # was sequence
 
         class S(object):
             pass
@@ -350,7 +344,8 @@ class TestSingleDispatch(unittest.TestCase):
 
         c.Container.register(U)
         # There is preference for registered versus inferred ABCs.
-        self.assertEqual(h(u), "sized")  # was conflict
+        with doc.assertRaises(RuntimeError):
+            self.assertEqual(h(u), "sized")
 
         class V(c.Sized, S):
             def __len__(self):