Controlling C3 to solve once for all the Method Resolution Order issues for category classes

[nthiery]

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

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.

Apply

• attachment: trac_13589-categories-c3_under_control-nt.patch

Depends on #12894
Depends on #12876
Depends on #11935
Depends on #12895
Depends on #10193

CC: @sagetrac-sage-combinat @simon-king-jena

Component: categories

Keywords: method resolution order, C3

Author: Nicolas M. Thiéry, Simon King

Reviewer: Simon King, Florent Hivert

Merged: sage-5.12.beta0

Issue created by migration from https://trac.sagemath.org/ticket/13589

[nthiery]

Changed dependencies from #13501 to #13501, #12894

[sagetrac-elixyre]

comment:3

Hello,

Could you update your patch, there is several hunk in the last sage versions (i work without combinat to use NCSF...)

patching file sage/categories/category.py
Hunk #6 FAILED at 1090
Hunk #7 FAILED at 1200
Hunk #9 FAILED at 2003
Hunk #10 FAILED at 2084
4 out of 11 hunks FAILED -- saving rejects to file sage/categories/category.py.rej
abort: patch failed to apply

Furthermore, it could be useful to add that quickly in sage. The graded Hopf algebras seems to be the last bastion before recurrent MRO errors.

Thanks, Jean-Baptiste

[simon-king-jena]

comment:4

I currently have

trac_14159_weak_value_triple_dict.patch
trac_14159_use_cdef_get.patch
trac_13184_sage_5.9.beta.patch
trac_14287-rebased.patch
trac_14217_base_functionality.patch
trac_12876_category_abstract_classes_for_hom.patch
trac11935_weak_pickling_by_construction-nt.patch
trac_11935-weak_pickling_by_construction-review-ts.patch
trac_14249-coercion_without_an_element.patch
trac_12894-classcall_setter-nt.patch
trac_12895-subcategory-methods-nt.patch
trac_12895-review.patch

on top of sage-5.9.rc0 (these all have positive review or are even merged in sage-5.10.beta), and then the patch fails to apply like this:

Füge trac_13589-categories-c3_under_control-nt.patch zur Seriendatei hinzu
Wende trac_13589-categories-c3_under_control-nt.patch an
Wende Patch auf Datei sage/categories/category.py an
FEHLSCHLAG von Teilstück #1 in Zeile 94
Teilstück #6 wurde erfolgreich in Zeile 1105 mit Unschärfe 1 angewandt (16 Zeilen verschoben).
FEHLSCHLAG von Teilstück #7 in Zeile 1289
Teilstück #9 wurde erfolgreich in Zeile 2152 mit Unschärfe 1 angewandt (58 Zeilen verschoben).
2 von 11 Teilstücken sind FEHLGESCHLAGEN -- speichere Ausschuss in Datei sage/categories/category.py.rej
Patch schlug fehl und Fortsetzung unmöglich (versuche -v)
Patch schlug fehl, Fehlerabschnitte noch im Arbeitsverzeichnis
Fehler beim Anwenden. Bitte beheben und trac_13589-categories-c3_under_control-nt.patch aktualisieren

So, there is some improvement with respect to what Jean-Baptiste reports. Nevertheless, it seems that dependencies should be stated, and probably the patch needs rebasing.

[simon-king-jena]

comment:5

In particular, the patch uses some CategoryWithAxiom, which is not defined here or in the given dependencies.

[simon-king-jena]

comment:6

I have not been able to find CategoryWithAxiom or category with axiom on trac.

[nthiery]

comment:7

Yes, this patch still needs a bit of work. It should be ready tuesday or so. You can have a look at the text in the patch where I describe the purpose and principle of the patch, but don't waste time with a more detailed review at this point!

Thanks!

[simon-king-jena]

comment:8

Hi Nicolas,

OK, I thought this is next, after #11935.

Best regards,
Simon

[nthiery]

comment:9

#12895 was next! And now I have to run behind :-)
Thanks for all your review work! I'll pile up some stuff for you soon and let you know :-)

[nthiery]

Changed dependencies from #13501, #12894 to #13501, #12894, #12895

[nthiery]

comment:11

Hi Simon,

The updated patch should be roughly close to completion. Most if not all tests should pass (they did when I was working on the patch in git; I may have screwed up my export back to mercurial, and/or some dependencies).

I still need to scan once again through the patch to check that everything is 100% doctested, and I also want to reread the explanations in sage.misc.c3_controlled. I'll do that tomorrow. But I think you can start reviewing it in particular checking whether the whole logic makes sense to you. Let me know if/when you start working on it so that we avoid conflicts.

Thanks!
Nicolas

[nthiery]

Changed dependencies from #13501, #12894, #12895 to #13501, #12894, #12876, #11935, #12895

[nthiery]

comment:13

For info: I am running the tests now and will report when I wake up.

[nthiery]

comment:14

All long tests passed on my machine with 5.10beta4 and the following patches applied:

trac_14612-gyw_test_speedup-ts.patch
trac_14574-folded.patch
trac_13735_fix_repr_lincomb.patch
trac_14123-binary-trees-maps-rebase-cs.patch
trac_12876_category_abstract_classes_for_hom.patch
trac11935_weak_pickling_by_construction-nt.patch
trac_11935-weak_pickling_by_construction-review-ts.patch
trac_12895-subcategory-methods-nt.patch
trac_13589-categories-c3_under_control-nt.patch

[nthiery]

comment:15

Ok, patchbot is happy too except for coverage in c3_controlled, doctest continuations, startup time and startup modules. The two first ones will be easy fixes. I'll investigate the two others this morning.

[nthiery]

comment:17

Hi Simon,

The patch is now completely ready for review:

• I fixed the coverage and continuation issue.
• I cythoned sage.misc.c3_controlled; hopefuly this will fix the startup time regression
• I went through the whole module, improved the doc and threw away some scories.
• I don't know why the bot complains about the non existent modules sage.categories.inspect and itertools. I guess its just confused. As for sage.misc.c3_controlled, well yes, it's new :-)
• I am running all long tests, and will report soon.

Thanks for your upcoming review!

Off to work on the main functorial construction patch!

                      Nicolas

[nthiery]

comment:18

Oops, I had forgotten a little improvement I wanted to do in the implementation of the total order. It looks a tiny bit less hacky now and could be a tiny bit faster.

All test pass. Running long tests now.

[nthiery]

comment:19

Gosh, I had fumbled my export and uploaded the wrong patch. Fixed!

[nthiery]

comment:21

Shoot, the Cythonisation has broken one longtest failure in sage.misc.c3_controlled. I am investigating this; the rest can be reviewed in the mean time.

The cythonization has not improved the startup time. It's not yet clear to me what can be causing the slower startup time. To be investigated ...

[simon-king-jena]

comment:22

Some random remarks:

• Why is Category._cmp_key a cached method and not a lazy attribute?

• Why is CategoryWithParameters._cmp_key a method and not a lazy attribute or at least a cached method?

• Why has this example

  sage: Groups().example().algebra(ZZ).categories()
  ...
  

  been completely removed from sage/categories/groups.py? Similarly sage: Modules(Integers(9)).all_super_categories() from sage/categories/modules.py etc.

• In the documentation of primer.py:

  However this must be considered as an *implementation detail*: `C_1` 
  and `C_2` are incomparable categories, then the order in which they 
  appear must be mathematically irrelevant:

  I guess there is "If" missing after the first colon.

• In sage/misc/c3_controlled.pyx, line 123: Should be "classes that an object inherits from.", not "classes that an object inherit from."

• ... line 139, "However, this has several inconvenients:" I guess this should be "However, this has several drawbacks" or "However, this is inconvenient in several regards" or so.

Do I understand correctly: As you outline in lines 148-166, the creation of classes will become slower (O(n^3) instead of O(n^2) for getting the MRO, etc) if one explicitly puts the desired MRO into a long list of bases. This would certainly be a reason for an increased startup time and other regressions. Therefore, in a first step, you compute short lists of bases that ensure that the C3 algorithm still reconstruct the intended MRO. However, is this additional step (namely: Computing lists of bases) takes some time, not affecting the startup time?

I still have to read the actual code (and not just the documentation). One question, though, which is in the spirit of #11935. In sage.categories.category, you have

        (result, bases) = C3_sorted_merge([cat._all_super_categories 
                                           for cat in self._super_categories] + 
                                          [self._super_categories], 
                                          key = attrcall('_cmp_key')) 
        self._super_categories_for_classes = bases 
        return [self] + result 

I guess in many cases the result will be the same up to the base rings. Shouldn't we think of a way to avoid duplication of work? I could imagine that here is the reason for the startup time regression.

[nthiery]

comment:23

Replying to @simon-king-jena:

Some random remarks:

• Why is Category._cmp_key a cached method and not a lazy attribute?
• Why is CategoryWithParameters._cmp_key a method and not a lazy attribute or at least a cached method?

To be discussed. If I remember correctly, it's slightly easier to use
super in cached methods than attributes, but I guess both would work.

• Why has this example

  sage: Groups().example().algebra(ZZ).categories()
  ...
  

  been completely removed from sage/categories/groups.py? Similarly sage: Modules(Integers(9)).all_super_categories() from sage/categories/modules.py etc.

Because they neither bring useful test or information, and
need to be updated whenever the category order changes which is a good
source of conflicts.

• In the documentation of primer.py:

  However this must be considered as an *implementation detail*: `C_1` 
  and `C_2` are incomparable categories, then the order in which they 
  appear must be mathematically irrelevant:

  I guess there is "If" missing after the first colon.

• In sage/misc/c3_controlled.pyx, line 123: Should be "classes that an object inherits from.", not "classes that an object inherit from."

• ... line 139, "However, this has several inconvenients:" I guess this should be "However, this has several drawbacks" or "However, this is inconvenient in several regards" or so.

Thanks, I'll fix that! Probably on Monday, together with the fix for
the failing long test.

Do I understand correctly: As you outline in lines 148-166, the creation of classes will become slower (O(n^3) instead of O(n^2) for getting the MRO, etc) if one explicitly puts the desired MRO into a long list of bases. This would certainly be a reason for an increased startup time and other regressions. Therefore, in a first step, you compute short lists of bases that ensure that the C3 algorithm still reconstruct the intended MRO. However, is this additional step (namely: Computing lists of bases) takes some time, not affecting the startup time?

Please read further :-) That would be O(n^3) if one was brute forcing
the complete mro in the list of bases. Luckily it's more clever than
that! New bases are only added when absolutely necessary; in fact, in
the current situation it turns out that no base is actually added even
for non trivial categories like Fields or GradedHopfAlgebrasWithBasis.

I still have to read the actual code (and not just the documentation). One question, though, which is in the spirit of #11935. In sage.categories.category, you have

        (result, bases) = C3_sorted_merge([cat._all_super_categories 
                                           for cat in self._super_categories] + 
                                          [self._super_categories], 
                                          key = attrcall('_cmp_key')) 
        self._super_categories_for_classes = bases 
        return [self] + result 

I guess in many cases the result will be the same up to the base rings. Shouldn't we think of a way to avoid duplication of work? I could imagine that here is the reason for the startup time regression.

This code is only called if all_super_categories is called. And by
#11935 this should happen only once for all base ring in the same
category. (unless one calls explicitly all_super_categories). I have
not kept the timings under hand, but I did not see a difference in our
usual elliptic curves benchmark.

Cheers,
Nicolas

[simon-king-jena]

comment:24

For the record, the only failing example is this:

File "devel/sage/sage/misc/c3_controlled.pyx", line 266, in sage.misc.c3_controlled
Failed example:
    for l in L:                                          # long time
        x = HierarchyElement(10, l.to_poset())
        assert x.mro            == list(P)
        assert x.mro_controlled == list(P)
        assert x.all_bases_len() == 15
        assert x.all_bases_controlled_len() == 19
        try:
            x.mro_standard
            assert False
        except:
            pass
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/prerelease/sage-5.9.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 466, in _run
        self.execute(example, compiled, test.globs)
      File "/home/simon/SAGE/prerelease/sage-5.9.rc0/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 825, in execute
        exec compiled in globs
      File "<doctest sage.misc.c3_controlled[35]>", line 6, in <module>
        assert x.all_bases_controlled_len() == Integer(19)
    AssertionError

Indeed, on the command line, I get

sage: for l in L:
....:     print "l =",l
....:     x = HierarchyElement(10, l.to_poset())
....:     print x.all_bases_controlled_len()
....:     
l = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
19
l = [10, 9, 8, 7, 6, 5, 4, 3, 1, 2]
19
l = [10, 9, 8, 7, 6, 5, 4, 2, 3, 1]
19
l = [10, 9, 8, 7, 6, 5, 4, 2, 1, 3]
19
l = [10, 9, 8, 7, 6, 5, 4, 1, 3, 2]
19
l = [10, 9, 8, 7, 6, 5, 4, 1, 2, 3]
19
l = [10, 9, 8, 7, 6, 5, 3, 4, 2, 1]
18
...
l = [10, 7, 9, 8, 5, 6, 4, 1, 3, 2]
20
l = [10, 7, 9, 8, 5, 6, 4, 1, 2, 3]
20
l = [10, 7, 9, 8, 5, 6, 3, 4, 2, 1]
18
l = [10, 7, 9, 8, 5, 6, 3, 4, 1, 2]
18
...
l = [10, 7, 9, 8, 4, 5, 6, 1, 3, 2]
20
l = [10, 7, 9, 8, 4, 5, 6, 1, 2, 3]
20
l = [10, 7, 9, 8, 4, 5, 1, 6, 3, 2]
17
l = [10, 7, 9, 8, 4, 5, 1, 6, 2, 3]
17
l = [10, 7, 9, 6, 8, 5, 4, 3, 2, 1]
19
...
l = [10, 7, 9, 6, 8, 5, 4, 1, 2, 3]
19
l = [10, 7, 9, 6, 8, 5, 3, 4, 2, 1]
16
l = [10, 7, 9, 6, 8, 5, 3, 4, 1, 2]
16
l = [10, 7, 9, 6, 8, 4, 5, 3, 2, 1]
18
l = [10, 7, 9, 6, 8, 4, 5, 3, 1, 2]
18
l = [10, 7, 9, 6, 8, 4, 5, 2, 3, 1]
18
l = [10, 7, 9, 6, 8, 4, 5, 2, 1, 3]
18
l = [10, 7, 9, 6, 8, 4, 5, 1, 3, 2]
18
l = [10, 7, 9, 6, 8, 4, 5, 1, 2, 3]
18
l = [10, 7, 9, 6, 8, 4, 2, 5, 3, 1]
17
l = [10, 7, 9, 6, 8, 4, 2, 5, 1, 3]
17
l = [10, 7, 9, 6, 4, 8, 5, 3, 2, 1]
19
l = [10, 7, 9, 6, 4, 8, 5, 3, 1, 2]
19
...
l = [10, 7, 4, 8, 9, 6, 5, 1, 2, 3]
19
l = [10, 7, 4, 8, 9, 6, 2, 5, 3, 1]
16
l = [10, 7, 4, 8, 9, 6, 2, 5, 1, 3]
16
l = [10, 7, 4, 8, 9, 5, 6, 3, 2, 1]
18
l = [10, 7, 4, 8, 9, 5, 6, 3, 1, 2]
18
...
l = [10, 7, 4, 8, 5, 9, 6, 1, 2, 3]
17
l = [10, 7, 4, 8, 5, 9, 1, 6, 3, 2]
16
l = [10, 7, 4, 8, 5, 9, 1, 6, 2, 3]
16
sage:

I am not surprise that some posets are easier to control than others. Why do you expect that all_bases_controlled_len is the same in all cases?

[nthiery]

comment:71

I started to work on the things we had discussed over the phone. I attached the preliminary patch to see what the patchbot says.

[simon-king-jena]

comment:72

One typo in the review patch: "It is sematically equivalent" should be "It is semantically equivalent". Also I think you mean

:func:`operator.attrgetter```("cmp_key")``

not

:func:`operator.attrgetter```(category)``

I wonder: You changed the default sort function from category_sort_key to identity (as we agreed on by phone), but you do not explicitly use the now non-default category_sort_key when calling c3_sorted_merge in sage.categories.category, isn't it? That should be fixed.

[simon-king-jena]

comment:73

Worse: Compilation of sage.misc.c3_controlled fails with

Error compiling Cython file:
------------------------------------------------------------
...

        sage: from sage.misc.c3_controlled import category_sort_key
        sage: category_sort_key(Rings()) is Rings()._cmp_key
        True
    """
    return C._cmp_key
           ^
------------------------------------------------------------

sage/misc/c3_controlled.pyx:377:12: undeclared name not builtin: C

[simon-king-jena]

comment:74

After trivially changing it, building Sage works, but it crashes at startup with

/home/simon/SAGE/prerelease/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/categories/category.pyc in _all_super_categories(self=Category of category_singleton)
    871              Category of rngs,
    872              Category of semirings,
    873              Category of monoids,
    874              Category of semigroups,
    875              Category of magmas,
    876              Category of commutative additive groups,
    877              Category of commutative additive monoids,
    878              Category of commutative additive semigroups,
    879              Category of additive magmas,
    880              Category of sets,
    881              Category of sets with partial maps,
    882              Category of objects]
    883         """
    884         (result, bases) = C3_sorted_merge([cat._all_super_categories
    885                                            for cat in self._super_categories] +
--> 886                                           [self._super_categories])
        self._super_categories = [Category of rngs, Category of semirings]
    887         self._super_categories_for_classes = bases
    888         return [self] + result
    889 
    890     @lazy_attribute
    891     def _all_super_categories_proper(self):
    892         r"""
    893         All the proper super categories of this category.
    894 
    895         Since :trac:`11943`, the order of super categories is
    896         determined by Python's method resolution order C3 algorithm.
    897 
    898         .. seealso:: :meth:`all_super_categories`
    899 
    900         .. note:: this attribute is likely to eventually become a tuple.
    901 

/home/simon/SAGE/prerelease/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/misc/c3_controlled.so in sage.misc.c3_controlled.C3_sorted_merge (sage/misc/c3_controlled.c:4377)()

KeyError: Category of sets

But this can be fixed by using key=category_sort_key in C3_sorted_merge.

Hence, with the following diff, Sage starts:

diff --git a/sage/categories/category.py b/sage/categories/category.py
--- a/sage/categories/category.py
+++ b/sage/categories/category.py
@@ -883,7 +883,8 @@
         """
         (result, bases) = C3_sorted_merge([cat._all_super_categories
                                            for cat in self._super_categories] +
-                                          [self._super_categories])
+                                          [self._super_categories],
+                                          key = category_sort_key)
         self._super_categories_for_classes = bases
         return [self] + result
 
diff --git a/sage/misc/c3_controlled.pyx b/sage/misc/c3_controlled.pyx
--- a/sage/misc/c3_controlled.pyx
+++ b/sage/misc/c3_controlled.pyx
@@ -374,7 +374,7 @@
         sage: category_sort_key(Rings()) is Rings()._cmp_key
         True
     """
-    return C._cmp_key
+    return category._cmp_key
 
 cdef class CmpKey:
     r"""

[nthiery]

comment:75

Oops, sorry for the wasted time; I posted this in a rush and it was half baked with the last round of changes not tested ... Here is an updated patch which fixes the mentionned issues.

[simon-king-jena]

comment:76

Attachment: trac13589_cython_cmp_key-review-nt.patch.gz

The patch looks good. I only wonder about the findings of the startup-time plugin.

[simon-king-jena]

comment:77

Why the heck is no patchbot giving a result? It is now 15 hours after attaching the review patch!

[simon-king-jena]

Work Issues: commit message for review patch

[simon-king-jena]

comment:78

Hooray, patchbot is back, and says:

+With 60% confidence, startup time increased by at least 0.5%
+With 96% confidence, startup time increased by at least 0.25%
+With 99.1% confidence, startup time increased by at least 0.1%

60% confidence is not significant, hence, we only have a significant regression of 0.25%, which I deem acceptable and a price worth paying.

So, I'm already putting it to positive review, but please add a proper commit message to the review patch!

[nthiery]

comment:79

Excellent! I'll fold the patches together and double check the commit message tomorrow.

[nthiery]

Changed work issues from commit message for review patch to none

[nthiery]

Attachment: trac_13589-categories-c3_under_control-nt.patch.gz

[nthiery]

comment:81

Patchbot getting confused again about which patch to apply.

Apply: trac_13589-categories-c3_under_control-nt.patch

Getting really tired of this ...

[darijgr]

comment:82

Without the colon perhaps?

apply trac_13589-categories-c3_under_control-nt.patch

(No idea how it works, I just want all the stuff depending on this to be checked.)

[jdemeyer]

Merged: sage-5.12.beta0

[jdemeyer]

comment:85

While looking through the Sage sources, I noticed the following doctest, coming from this ticket:

    sage: for l in L:
    ....:     x = HierarchyElement(10, l.to_poset())
    ....:     try:
    ....:         x.mro_standard
    ....:         assert False
    ....:     except:
    ....:         pass
    ....:     assert x.mro            == list(P)
    ....:     assert x.mro_controlled == list(P)
    ....:     assert x.all_bases_len() == 15
    ....:     stats.append(x.all_bases_controlled_len()-x.all_bases_len())

What is the purpose of the assert False here? I am asking because

try:
    foo()
    assert False
except:
    pass

is entirely equivalent to

try:
    foo()
except:
    pass

[jdemeyer]

comment:86

bump

[nthiery]

comment:87

Replying to @jdemeyer:

bump

Thanks for spotting, that was an oversight indeed! See #17106 (needs review).