Cannot create consistent method resolution order (MRO) when using filtered categories

[tobiasdiez]

Steps To Reproduce

In https://github.com/tobiasdiez/sage/tree/pytest-no-isolation-bug, run pytest --doctest src/sage/algebras/{af,ass,clifford}**.py.
(It is not necessary to really use this branch, but in it a few unrelated doctests are deleted to make investigation hopefully easier).

It's a combination of the following 3 doctests that trigger the error (but in a sage session it works well):

# src/sage/algebras/affine_nil_temperley_lieb.py
A = AffineNilTemperleyLiebTypeA(3)

# src/sage/algebras/associated_graded.py
A = Algebras(QQ).WithBasis().Filtered()

# src/sage/algebras/clifford_algebra.py
Qp = QuadraticForm(QQ, 3, [1,2,3,4,5,6])
Clp = CliffordAlgebra(Qp)

In particular, it works if you remove Filtered in the second line.

(Note that pytest by default doesn't isolate doctests from each other, so the code is just run in the same process, after an initial sage.all import - similar to how you would run it in a linear sage terminal session.)

(I'm using the meson build in a conda environment, but I doubt this makes a difference.)

Expected Behavior

Tests pass, as they do if you run pytest --doctest src/sage/algebras --isolated (with https://github.com/gilfree/pytest-isolate installed).

Actual Behavior

Fails with

    JoinCategory.subcategory_class (<class 'sage.categories.super_algebras_with_basis.SuperAlgebrasWithBasis.subcategory_class'>, <class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis.subcategory_class'>, <class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.Filtered.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.FiniteDimensional.subcategory_class'>) <class 'sage.structure.dynamic_class.DynamicMetaclass'>
    Cannot create a consistent method resolution
    order (MRO) for bases VectorSpaces.WithBasis.subcategory_class, FiniteDimensionalModulesWithBasis.subcategory_class
    JoinCategory.subcategory_class (<class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.Filtered.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.FiniteDimensional.subcategory_class'>) <class 'sage.structure.dynamic_class.DynamicMetaclass'>
    Cannot create a consistent method resolution
    order (MRO) for bases VectorSpaces.subcategory_class, Modules.FiniteDimensional.subcategory_class
    JoinCategory.subcategory_class (<class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.Filtered.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.FiniteDimensional.subcategory_class'>) <class 'sage.structure.dynamic_class.DynamicMetaclass'>
    Cannot create a consistent method resolution
    order (MRO) for bases VectorSpaces.WithBasis.subcategory_class, FiniteDimensionalModulesWithBasis.subcategory_class
    JoinCategory.subcategory_class (<class 'sage.categories.magmatic_algebras.MagmaticAlgebras.WithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.Filtered.subcategory_class'>, <class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.filtered_modules.FilteredModules.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.FiniteDimensional.subcategory_class'>) <class 'sage.structure.dynamic_class.DynamicMetaclass'>
    Cannot create a consistent method resolution
    order (MRO) for bases FiniteDimensionalModulesWithBasis.subcategory_class, VectorSpaces.WithBasis.subcategory_class, FilteredModules.subcategory_class, VectorSpaces.FiniteDimensional.subcategory_class
    JoinCategory.subcategory_class (<class 'sage.categories.filtered_algebras_with_basis.FilteredAlgebrasWithBasis.subcategory_class'>, <class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis.subcategory_class'>, <class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.Filtered.subcategory_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.FiniteDimensional.subcategory_class'>) <class 'sage.structure.dynamic_class.DynamicMetaclass'>
    Cannot create a consistent method resolution
    order (MRO) for bases VectorSpaces.WithBasis.subcategory_class, FiniteDimensionalModulesWithBasis.subcategory_class
    JoinCategory.parent_class (<class 'sage.categories.super_algebras_with_basis.SuperAlgebrasWithBasis.parent_class'>, <class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis.parent_class'>, <class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.parent_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.Filtered.parent_class'>, <class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.FiniteDimensional.parent_class'>) <class 'sage.structure.dynamic_class.DynamicMetaclass'>
    Cannot create a consistent method resolution
    order (MRO) for bases VectorSpaces.WithBasis.parent_class, FiniteDimensionalModulesWithBasis.parent_class

Additional Information

Similar #20460 and #20896

Does anyone has an idea how to debug this further?

Environment

Latest

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide

[user202729]

I can consistently reproduce this in a Sage session with

sage: A = AffineNilTemperleyLiebTypeA(3)
sage: B = Algebras(QQ).WithBasis().Filtered()
sage: Qp = QuadraticForm(QQ, 3, [1,2,3,4,5,6])
sage: Clp = CliffordAlgebra(Qp)

Evidently the issue is because the MRO are inconsistent.

ipdb> p metaclass(name, bases[1:3], {})
*** TypeError: Cannot create a consistent method resolution
order (MRO) for bases FiniteDimensionalModulesWithBasis.subcategory_class, VectorSpaces.WithBasis.subcategory_class
ipdb> bases[1:3]
(<class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis.subcategory_class'>, <class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>)
ipdb> bases[1].__mro__
(<class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis.subcategory_class'>,
...
<class 'sage.categories.finite_dimensional_modules_with_basis.FiniteDimensionalModulesWithBasis.subcategory_class'>,
<class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.subcategory_class'>,
...
<class 'object'>)
ipdb> bases[2].__mro__
(<class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional.subcategory_class'>,
<class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.subcategory_class'>,
<class 'sage.categories.vector_spaces.VectorSpaces.WithBasis.subcategory_class'>,
<class 'sage.categories.finite_dimensional_modules_with_basis.FiniteDimensionalModulesWithBasis.subcategory_class'>,
...
<class 'object'>)
ipdb> 

Which raises the question of how the ordering of the bases are specified. in category.py:

        return dynamic_class(class_name,
                             tuple(getattr(cat, name) for cat in self._super_categories_for_classes),
                             method_provider_cls, prepend_cls_bases=False,
                             doccls=doccls, reduction=reduction, cache=cache)

So the question is where _super_categories_for_classes comes from…

        (result, bases) = C3_sorted_merge([cat._all_super_categories
                                           for cat in self._super_categories] +
                                          [self._super_categories],
                                          category_sort_key)
        if not sorted(result, key=category_sort_key, reverse=True) == result:
            warn("Inconsistent sorting results for all super categories of {}".format(
                 self.__class__))
        self._super_categories_for_classes = bases

The function comes from #11943 which should be consistent with Python's MRO.

---

Visualizing the MRO, it looks like the following

MRO_of_FiniteDimensionalAlgebrasWithBasis.subcategory_class.pdf

MRO_of_FilteredModulesWithBasis.FiniteDimensional.subcategory_class.pdf

---

Maybe C3 algorithm has changed or something, but the identity specified in #11943 no longer holds:

ipdb> C = self._super_categories_for_classes[2]
ipdb> C.parent_class.mro() == [X.parent_class for X in C.all_super_categories()] + [object]
False
ipdb> C
Category of finite dimensional filtered modules with basis over (number fields and quotient fields and metric spaces)
ipdb> type(C)
<class 'sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.FiniteDimensional_with_category'>

More minimal example:

A = Algebras(QQ).WithBasis().Filtered()
from sage.categories.metric_spaces import MetricSpaces
Modules(Category.join([NumberFields(), QuotientFields(), MetricSpaces()])).Filtered()._test_category_graph()

---

https://ncatlab.org/nlab/show/filtered+object

        @cached_method
        def Filtered(self, base_ring=None):
            r"""
            Return the subcategory of the filtered objects of ``self``.

So, for C a category, in SageMath's terminology, C.Filtered() is a subcategory of C. (#16183 says it's a bit ambiguous, but doesn't matter for us.)

The problem is for some reason when the first line is included then the last line returns False:

A = Algebras(QQ).WithBasis().Filtered()
from sage.categories.metric_spaces import MetricSpaces
D = Modules(Category.join([NumberFields(), QuotientFields(), MetricSpaces()]))
D in D.Filtered().all_super_categories()

Which appears to boil down to

#A = Algebras(QQ).WithBasis().Filtered()  # the presence or absence of this line affect the result
from sage.categories.metric_spaces import MetricSpaces
C = Category.join([NumberFields(), QuotientFields(), MetricSpaces()])
D = Modules(C)  # vector spaces over C
E = D.super_categories()[0].Filtered()  # filtered modules over C
print(E.is_subcategory(D))

[user202729]

Actually part of the reason why it behaves weirdly is written here

    def extra_super_categories(self):
        r"""
        Add :class:`VectorSpaces` to the super categories of ``self`` if
        the base ring is a field.

        EXAMPLES::

            sage: Modules(QQ).Filtered().is_subcategory(VectorSpaces(QQ))
            True
            sage: Modules(ZZ).Filtered().extra_super_categories()
            []

        This makes sure that ``Modules(QQ).Filtered()`` returns an
        instance of :class:`FilteredModules` and not a join category of
        an instance of this class and of ``VectorSpaces(QQ)``::

            sage: type(Modules(QQ).Filtered())
            <class 'sage.categories.vector_spaces.VectorSpaces.Filtered_with_category'>

        .. TODO::

            Get rid of this workaround once there is a more systematic
            approach for the alias ``Modules(QQ)`` -> ``VectorSpaces(QQ)``.
            Probably the latter should be a category with axiom, and
            covariant constructions should play well with axioms.
        """