#13589: Controlling C3 to solve once for all the Method Resolution Order issues
for
category classes
------------------------------------------+---------------------------------
Reporter: nthiery | Owner: nthiery
Type: defect | Status: new
Priority: major | Milestone: sage-5.5
Component: categories | Keywords: method
resolution order, C3
Work issues: | Report Upstream: N/A
Reviewers: Simon King, Florent Hivert | Authors: Nicolas M.
Thiéry
Merged in: | Dependencies: #13501
Stopgaps: |
------------------------------------------+---------------------------------
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.
Status: the patch is functional, but still breaks a couple things here and
there. In particular, some doctests need to be updated w.r.t. some changes
in MRO and super_categories output. I will fix this as soon as the
principle will be accepted.
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>
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.
