#13501: Fix two bugs in sage.misc.c3's implementation of the algorithm C3
-------------------------------------------------+--------------------------
Reporter: nthiery | Owner:
Type: defect | Status:
positive_review
Priority: major | Milestone: sage-5.5
Component: categories | Resolution:
Keywords: method resolution order | Work issues:
Report Upstream: N/A | Reviewers: Simon King
Authors: Nicolas M. Thiéry, Simon King | Merged in:
Dependencies: | Stopgaps:
-------------------------------------------------+--------------------------
Changes (by nthiery):
* status: needs_work => positive_review
Old description:
> 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.
>
> '''Apply''':
> * [attachment:trac_13501-categories-c3_fix-nt.patch]
> * [attachment:trac_13501-c3-speedup-sk.patch]
New description:
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.
'''Apply''':
* [attachment:trac_13501-categories-c3_fix-nt.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13501#comment:41>
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.
