Opened 8 years ago

Last modified 7 years ago

#11943 closed enhancement

The category graph should comply with Python's method resolution order — at Initial Version

Reported by: SimonKing Owned by: nthiery
Priority: major Milestone: sage-5.1
Component: categories Keywords: category graph, method resolution order
Cc: hivert, mderickx Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:


Let C be a category. C.all_super_categories() starts with C.super_categories() and finds all super categories inductively.

Unfortunately, the algorithm of C.all_super_categories() does not comply with the C3 algorithm, that is used by Python to determine the method resolution order for C.parent_class and C.element_class.

The aim of this ticket is to be more consistent. Eventually, for any category C (perhaps with modifications for hom categories), one should have

sage: C.parent_class.mro() == [X.parent_class for X in C.all_super_categories()] + [object]
sage: C.element_class.mro() == [X.element_class for X in C.all_super_categories()] + [object]

and that test should become part of the test suite.

At #11900, the implementation of all_super_categories() has been changed, so, work should rely on #11900.

Unfortunately, it seems that the C3 algorithm can not simply be imported from Python, even though Python uses it internally, namely in Objects/typeobject.c. Looking at the implementation, it requires that one gets a list of types, while we want to use it on a list of objects.

Therefore, we need to implement C3 from scratch. Implementing C3 is easy, but if it shall be fast, one needs to be careful.

In particular, one needs to be able to L.pop(0) quickly, where L is a list. Unfortunately, L.pop(0) is slow, even in Cython. I found that, if the lists are not too long, it is best to revert L and do L.pop() instead, which is optimized in Cython. See the discussion at sage-devel.

My plan is:

  • Provide the C3 algorithm in a new extension module sage.misc.c3
  • Use it to compute all_super_categories()
  • Add a test _test_category_graph, asserting that self.parent_class.mro() and self.all_super_categories() are compatible.

First tests indicate that the change of order on C.all_super_categories() is fine (sage does not crash, and most tests in sage.categories pass. However, one really needs to look at the performance.

Change History (0)

Note: See TracTickets for help on using tickets.