Opened 4 years ago

Last modified 4 years ago

#23000 closed defect

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

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: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by nthiery)

#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 #20962 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 (1)

comment:1 Changed 4 years ago by nthiery

  • Description modified (diff)
Note: See TracTickets for help on using tickets.