#13589: Controlling C3 to solve once for all the Method Resolution Order issues
for
category classes
--------------------------------------------------+-------------------------
Reporter: nthiery | Owner: nthiery
Type: defect | Status:
needs_review
Priority: major | Milestone: sage-5.11
Component: categories | Resolution:
Keywords: method resolution order, C3 | Work issues:
Report Upstream: N/A | Reviewers: Simon King,
Florent Hivert
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: #12894, #12876, #11935, #12895 | Stopgaps:
--------------------------------------------------+-------------------------
Description changed by nthiery:
Old description:
> {{{#!rst
> Teaser
> ------
>
> Python handles multiple inheritance by computing, for each class,
> a linear extension of all its super classes (the Method Resolution
> Order, MRO). The MRO is calculated recursively from local
> information (the *ordered* list of the direct super classes), with
> the so-called ``C3`` algorithm. This algorithm can fail if the local
> information is not consistent; worst, there exist hiearchies of
> classes with provably no consistent local information.
>
> For large hierarchy of classes, like those derived from categories in
> Sage, maintaining consistent local information by hand does not scale
> and leads to unpredictable ``C3`` failures (the dreaded "could not
> find a consistent method resolution order"); a maintenance nightmare.
>
> This patch implements a final solution to this problem. Namely, it
> allows for building automatically the local information from the bare
> class hierarchy in such a way that guarantees that the ``C3``
> algorithm will never fail.
>
> Err, but you said that this was provably impossible? Well, not if
> one relaxes a bit the hypotheses, but that's not something one
> would want to do by hand :-)
>
> Details
> -------
>
> Please see the extensive documentation at the top of the file
> sage/misc/c3_controlled.py in the attached patch.
>
> Content of the patch
> --------------------
>
> - Implement controlled C3 in sage.misc.c3_controlled.
>
> - Implement a total order in Category, and have Category use
> C3 controlled by this order instead of plain C3.
>
> - Tweak the current total order to minimize changes in the order of
> categories.
>
> - Update doctests w.r.t. remaining changes of in the order of
> categories.
>
> - Remove a coupld doctests displaying "all_super_categories" that did not
> bring useful information to the user nor intesting test, yet needed to be
> constantly updated; nothing but a good source of conflicts.
>
> - Rewrite doctests in sage.misc.c3 to be independent of categories
> since those do not use anymore this implementation of C3.
>
> - Resolve some ambiguities to make the code more independent of the
> order of categories. In particular, FiniteCoxeterGroups prefer
> __iter__ and some_elements from CoxeterGroups to that of
> FiniteGroups.
>
> - Update the section in the primer about order of categories.
>
> - Provide further tools in ``sage.misc.c3_controlled`` to
> experiment with C3 and friends.
>
> - Extract category_sample from category_graph
>
> Apply: [attachment:trac_13589-categories-c3_under_control-nt.patch]
>
> Credits
> -------
>
> This patch is a followup to a study of the C3 algorithm together with
> Florent Hivert, and to discussions with Simon King and his
> implementation of C3.
> }}}
New description:
{{{#!rst
Teaser
------
Python handles multiple inheritance by computing, for each class,
a linear extension of all its super classes (the Method Resolution
Order, MRO). The MRO is calculated recursively from local
information (the *ordered* list of the direct super classes), with
the so-called ``C3`` algorithm. This algorithm can fail if the local
information is not consistent; worst, there exist hiearchies of
classes with provably no consistent local information.
For large hierarchy of classes, like those derived from categories in
Sage, maintaining consistent local information by hand does not scale
and leads to unpredictable ``C3`` failures (the dreaded "could not
find a consistent method resolution order"); a maintenance nightmare.
This patch implements a final solution to this problem. Namely, it
allows for building automatically the local information from the bare
class hierarchy in such a way that guarantees that the ``C3``
algorithm will never fail.
Err, but you said that this was provably impossible? Well, not if
one relaxes a bit the hypotheses, but that's not something one
would want to do by hand :-)
Details
-------
Please see the extensive documentation at the top of the file
sage/misc/c3_controlled.py in the attached patch.
Content of the patch
--------------------
- Implement controlled C3 in sage.misc.c3_controlled.
- Implement a total order in Category, and have Category use
C3 controlled by this order instead of plain C3.
- Tweak the current total order to minimize changes in the order of
categories.
- Update doctests w.r.t. remaining changes of in the order of
categories.
- Remove a coupld doctests displaying "all_super_categories" that did not
bring useful information to the user nor intesting test, yet needed to be
constantly updated; nothing but a good source of conflicts.
- Rewrite doctests in sage.misc.c3 to be independent of categories
since those do not use anymore this implementation of C3.
- Resolve some ambiguities to make the code more independent of the
order of categories. In particular, FiniteCoxeterGroups prefer
__iter__ and some_elements from CoxeterGroups to that of
FiniteGroups.
- Update the section in the primer about order of categories.
- Provide further tools in ``sage.misc.c3_controlled`` to
experiment with C3 and friends.
- Extract category_sample from category_graph
Apply: trac_13589-categories-c3_under_control-nt.patch
Credits
-------
This patch is a followup to a study of the C3 algorithm together with
Florent Hivert, and to discussions with Simon King and his
implementation of C3.
}}}
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13589#comment:38>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
