The C3 algorithm#
The C3 algorithm is used as method resolution order for new style classes in Python. The implementation here is used to order the list of super categories of a category.
AUTHOR:
Simon King (2011-11): initial version.
- sage.misc.c3.C3_algorithm(start, bases, attribute, proper)#
An implementation of the C3 algorithm.
C3 is the algorithm used by Python to construct the method resolution order for new style classes involving multiple inheritance.
After github issue #11943 this implementation was used to compute the list of super categories of a category; see
all_super_categories()
. The purpose is to ensure that list of super categories matches with the method resolution order of the parent or element classes of a category.Since github issue #13589, this implementation is superseded by that in
sage.misc.c3_controlled
, that puts theC3
algorithm under control of some total order on categories. This guarantees thatC3
always finds a consistent Method Resolution Order. For background, seesage.misc.c3_controlled
.INPUT:
start
– an object; the returned list is built upon data provided by certain attributes ofstart
.bases
– a string; the name of an attribute ofstart
providing a list of objects.attribute
– a string; the name of an attribute of the objects provided ingetattr(start,bases)
. That attribute is supposed to provide a list.
ASSUMPTIONS:
Our implementation of the algorithm only works on lists of objects that compare equal if and only if they are identical.
OUTPUT:
A list, the result of the C3 algorithm applied to the list
[getattr(X,attribute) for X in getattr(start,bases)]
.EXAMPLES:
We create a class for elements in a hierarchy that uses the
C3
algorithm to compute, for each element, a linear extension of the elements above it:.. TODO:: Move back the __init__ at the beginning
sage: from sage.misc.c3 import C3_algorithm sage: class HierarchyElement(UniqueRepresentation): ….: @lazy_attribute ….: def _all_bases(self): ….: return C3_algorithm(self, ‘_bases’, ‘_all_bases’, False) ….: def __repr__(self): ….: return self._name ….: def __init__(self, name, bases): ….: self._name = name ….: self._bases = list(bases)
We construct a little hierarchy:
sage: T = HierarchyElement("T", ()) sage: X = HierarchyElement("X", (T,)) sage: Y = HierarchyElement("Y", (T,)) sage: A = HierarchyElement("A", (X, Y)) sage: B = HierarchyElement("B", (Y, X)) sage: Foo = HierarchyElement("Foo", (A, B))
And inspect the linear extensions associated to each element:
sage: T._all_bases [T] sage: X._all_bases [X, T] sage: Y._all_bases [Y, T] sage: A._all_bases [A, X, Y, T] sage: B._all_bases [B, Y, X, T]
So far so good. However:
sage: Foo._all_bases Traceback (most recent call last): ... ValueError: Cannot merge the items X, Y.
The
C3
algorithm is not able to create a consistent linear extension. Indeed, its specifications impose that, ifX
andY
appear in a certain order in the linear extension for an element of the hierarchy, then they should appear in the same order for any lower element. This is clearly not possibly forFoo
, sinceA
andB
impose incompatible orders. If the above was a hierarchy of classes, Python would complain that it cannot calculate a consistent Method Resolution Order.