#13501: Bugs in C3'salgorithm implementation in sage.misc.c3
--------------------------+-------------------------------------------------
Reporter: nthiery | Owner: nthiery
Type: defect | Status: new
Priority: major | Milestone: sage-5.4
Component: categories | Keywords: method resolution order
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies: #12895
Stopgaps: |
--------------------------+-------------------------------------------------
The current implementation of C3's algorithm in sage.misc.c3 (which is
used to compute the list of all the super categories of a category) is
incorrect.
Define indeed the following classes::
{{{
sage: class C(object): pass
....:
sage: class F(object): pass
....:
sage: class G(object): pass
....:
sage: class B(C,F): pass
....:
sage: class D(F,G): pass
....:
sage: class E(F): pass
....:
sage: class A(B,D,E): pass
....:
}}}
Which gives the following mro:
{{{
sage: A.mro()
[<class '__main__.A'>, <class '__main__.B'>, <class '__main__.C'>, <class
'__main__.D'>, <class '__main__.E'>, <class '__main__.F'>, <class
'__main__.G'>, <type 'object'>]
}}}
Here is now the same hierarchy using categories::
{{{
class Cs(Category):
def super_categories(self): return []
class Fs(Category):
def super_categories(self): return []
class Gs(Category):
def super_categories(self): return []
class Bs(Category):
def super_categories(self): return [Cs(), Fs()]
class Ds(Category):
def super_categories(self): return [Fs(), Gs()]
class Es(Category):
def super_categories(self): return [Fs()]
class As(Category):
def super_categories(self): return [Bs(), Ds(), Es()]
}}}
The super categories are not given in the same order (g,e,f instead of
e f g)::
{{{
sage: As().all_super_categories()
[Category of as, Category of bs, Category of cs, Category of ds, Category
of gs, Category of es, Category of fs]
}}}
This is due to popping X from the tail too early around line 186: O is
a candidate for being the next in line, but has not yet been
definitely chosen.
And indeed this is caught by the test suite::
{{{
sage: TestSuite(As()).run()
Failure in _test_category_graph:
Traceback (most recent call last):
...
AssertionError: False is not true
}}}
Here is another hierarchy with an inconsistent MRO which is not
detected by Sage's current C3::
{{{
class B(object): pass
class C(B): pass
class A(B, C): pass
Traceback (most recent call last):
File "<ipython console>", line 1, in <module>
TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution
order (MRO) for bases C, B
}}}
{{{
class Bs(Category):
def super_categories(self): return []
class Cs(Category):
def super_categories(self): return [Bs()]
class As(Category):
def super_categories(self): return [Bs(), Cs()]
class subcategory_class(object): # just to bypass the MRO error when
building the subcategory class
pass
sage: As()
Category of as
sage: As().all_super_categories()
[Category of as, Category of cs, Category of bs]
}}}
Here the issue comes from the fact that the C3 algorithm is supposed
to work on the mro's of the bases *together with* the list of the
bases, which the current Sage's implementation does not.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13501>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
