#13589: a proposal to solve once for all the recurrent Method Resolution Order issues for category classes

[Nicolas M. Thiery]

Dear categories and multiple inheritance fans,

Let me advertise here #13589 which contains a proposal for solving
once for all the recurrent Method Resolution Order issues with large
hierarchies of classes, in particular those derived from
categories. In the short run what I would need is feedback on whether
this proposal sounds reasonable, before I proceed with it.

Executive summary:

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 and especially with the upcoming category patches (#10963),
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.

#13589 is a proposal for solving this problem once for all. 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 on the patch attached to the ticket.

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.

The patch is also available on the Sage-Combinat queue (guarded out by
default by +functorial_construction).

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.

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Andrew Mathas]

Hi  Nicolas,

Your two patches:

• trac_10963-more_functorial_constructions-nt.patch
  
• trac_12895-subcategory-methods-nt.patch
  

both seem to break the 5.3 queue. I haven't checked 5.4-rc1.

Andrew

[Nicolas M. Thiery]

Hi Andrew!

On Tue, Oct 09, 2012 at 06:58:11AM -0700, Andrew Mathas wrote:
> Your two patches:
> * trac_10963-more_functorial_constructions-nt.patch
> * trac_12895-subcategory-methods-nt.patch

> both seem to break the 5.3 queue. I haven't checked 5.4-rc1.

Are you sure? I haven't changed those in a while, and the patches
apply smoothly for me.

Please follow up only on sage-combinat, if not just me, since this is
not directly related to this topic.