Opened 4 years ago

Last modified 4 years ago

#23000 closed defect

Add trivial `AdditiveGroups.Finite` category, and workaround MRO issue — at Version 6

Reported by: nthiery Owned by:
Priority: major Milestone: sage-8.0
Component: categories Keywords:
Cc: tscrim Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/nthiery/add_trivial__additivegroups_finite__category__and_workaround_mro_issue (Commits, GitHub, GitLab) Commit: bc94ce675b1b3c380c1aef09cd036f9c41dacef4
Dependencies: Stopgaps:

Status badges

Description (last modified by tscrim)

#18700 implements a new category AdditiveGroups.Finite. Without further change, this triggered the following doctest failure:

sage: K = simplicial_complexes.Simplex(2)
sage: H = Hom(K,K)
sage: id = H.identity()
sage: id.induced_homology_morphism(GF(13)).base_ring()
Traceback (most recent call last)
.../opt/sage-git2/src/sage/misc/c3_controlled.pyx in sage.misc.c3_controlled.C3_sorted_merge (/opt/sage-git2/src/build/cythonized/sage/misc/c3_controlled.c:5151)()
    936                     heads[j] = X
    937                     tailset = tailsets[j]
--> 938                     tailset.remove(key(X))
    939                 else:
    940                     del heads[j]

KeyError: (258, 65)

This is yet another avatar of lack of robustness of categories over base rings, which will be fixed by #22962 when module categories will be singleton. To get the ball rolling for #18700 which is otherwise ready, this ticket provides a quick workaround which should be robust enough for now.

Detailed analysis

Recall that

  • categories are endowed with a total order which is used to ensure that the Method Resolution Orders chosen by Python are always consistent. This total order shall refine the subcategory relation. This is achieved by assigning a comparison key to each category according to the order in which they are created.
  • To make the total order more reproducible from one session to the other, the first piece of the comparison key is given by a bit array of flags which are set according to whether the category is a subcategory of some "atom categories": FacadeSets, FiniteSets, ...
  • To avoid creating many copies of the same hierarchy of classes, parametrized categories may share their parent/element/... classes, and therefore the same comparison key.

In the case at hand, depending on the order in which categories were created, the assumption of refining the subcategory relation got broken (I still need to analyze this precisely): Modules(GF(3)).FiniteDimensional() got a key smaller than its super category AdditiveGroup().Finite()

This risk will vanish by itself when module categories will be singleton. In the mean time, adding "Modules" to the list of atom categories guarantee that AdditiveGroups().Finite() gets a strictly smaller key.

Change History (6)

comment:1 Changed 4 years ago by nthiery

  • Description modified (diff)

comment:2 Changed 4 years ago by nthiery

  • Branch set to u/nthiery/add_trivial__additivegroups_finite__category__and_workaround_mro_issue

comment:3 Changed 4 years ago by nthiery

  • Cc tscrim added
  • Commit set to da3ddcd201fd481431881083266cdea0a42c6453
  • Component changed from PLEASE CHANGE to categories
  • Status changed from new to needs_info
  • Type changed from PLEASE CHANGE to defect

All tests passed on my machine.

Not yet "needs review" for I want to dig once more in to check a detail I did not quite fully understand yet in the failure.


New commits:

da3ddcd23000: Add trivial category, and workaround MRO issue

comment:4 Changed 4 years ago by git

  • Commit changed from da3ddcd201fd481431881083266cdea0a42c6453 to bc94ce675b1b3c380c1aef09cd036f9c41dacef4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bc94ce623000: Add trivial AdditiveGroups.Finite category, and workaround MRO issue

comment:5 Changed 4 years ago by nthiery

(force repushed after fixing the commit message).

comment:6 Changed 4 years ago by tscrim

  • Description modified (diff)

Okay, I think I understand why this change is needed. Did you manage to track down the detail you mentioned in comment:3?

Note: See TracTickets for help on using tickets.