Make MRO topological sorted

Python Help
21

If I understood correctly, you interpret “ordering rules imposed by inheritance relationships”, in Guido’s quote, exclusively as those appearing in the classes’ definitions, the local precedence order (LPO). This, as opposed to LPO plus the order from previously computed MROs for those classes, which I guess could be another interpretation.

Questions:

  1. To do topological sort to determine the MRO of a new class, one would need to visit the whole hierarchy (following __bases__), rather than the MRO of the parents, right?
  2. Suppose a class’ MRO has been computed. Assume that the corresponding topological sort chose a precedence A\prec B that is not imposed by the LPO. For example, your A0_B that admits the topological sorts A0_B, A, B or A0_B, B, A. Assume that when A0_B was defined, the first topological sort was chosen. Later a new class is defined that does impose B\prec A. For example class C(B,A): pass. Would the MRO of the first class ( A0_B ) be updated to A0_B, B, A or left as A0_B, A, B?

I think that if the answer to (2) is leave already computed MRO as they are, then monotonicity need not be satisfied. If the answer is to update all MROs, then they could be constantly changing as more classes get defined.

There is a property, that in the paper A monotonic superclass linearization for Dylan is called acceptable, that is that “only the shape of a class’s inheritance graph may be used in determining the linearization”. I understood this as A0_B’s linearization shouldn’t depend on C’s. I think that if all MRO’s get updated, then this property cannot be satisfied. Right?

3 Likes
22

Yes. It would be slower than visiting MRO of the parents because the whole hierarchy is a tree while MRO is a sequence. However, I think the performance impact would not be a big problem here because:

  1. The time complexity of both approaches is the same.
  2. The hierarchy tree is visited when defining classes, and it would not affect runtime performance

The MRO of A0_B should not be updated, because it is not even used for determining its child classes’ MRO. As I mentioned above, when A0_B is abstract, we can even skip computing A0_B’s MRO.

According to the definition of monotonicity in A Monotonic Superclass Linearization for Dylan:

A monotonic linearization is one in which every property inherited by a class is inherited or defined by one of its direct superclasses; that is, an inherited property cannot skip over all of the direct superclasses.

If I understand correctly, monotonicity basically means that the classes in a hierarchy tree is topological sorted. It does not implies any constraints between two method calls on two different classes. For example:

  1. if method A0_B.foo includes a super() call and A0_B.foo is called by A0_B().foo(), A0_B’s MRO is used
  2. when A0_B.foo is called by a super().foo() defined in A0_B_A1.foo and A0_B_A1.foo is called by A0_B_A1().foo(), A0_B_A1’s MRO is used.

In the latter case, the fact A0_B’s MRO is not used would not result in any monotonicity issue. Basically the proxy object created by super() is a pair of the root MRO and the index of the current class in the root MRO. The proxy object does not include the current class’s MRO.

23

New classes could be defined at runtime, right?

class A: pass
class B: pass

if __name__ == '__main__':
    lots_of_classes = []
    for x in range(100):
        lots_of_classes.append(type(f'C{x}', (B, A, ), {}))

Regarding monotonicity if MRO of previous classes don’t get updated after new classes are defines:

Let’s look at the example

class A: pass
class B: pass
class A0(A): pass
class A0_B(A0,B): pass

Assume, without loss of generality, that the topological sort chose the MRO for A0_B to be A0_B, A0, A, B. If the topological sort chose A0_B, A0, B, A instead, then swap the names of A and B in what follows. Now the code continues and suppose that there is a new class

class C(B, A): pass

The MRO for this is C, B, A, only choice. Let’s assume that you intend your algorithm to not update the MRO of A0_B. The problem with monotonicity happens if the code defines now

class D(A0_B, C): pass

No problem in terms of doing topological sort to choose an MRO for D. There is a topological sort agreeing with the local precedence order that is D, A0_B, A0, C, B, A, but a superclass of D is A0_B and in this, its MRO indicates (since we haven’t updated it) that A takes precedence over B, which is the reverse of what D’s MRO says.

1 Like
24

The proposal is that the order between A and B can be different in D’s MRO and A0_B’s MRO. The difference is not a violation of monotonicity if I understand the definition of monotonicity correctly.

25

In this link that you shared, see point 5:

A MRO is monotonic when the following is true: if C1 precedes C2 in the linearization of C, then C1 precedes C2 in the linearization of any subclass of C . Otherwise, the innocuous operation of deriving a new class could change the resolution order of methods, potentially introducing very subtle bugs.

A superclass’ MRO M_1 is a subset of any derived class’ MRO M_2. What this paragraph is saying is that this inclusion M_1\hookrightarrow M_2 is monotonic (more specifically order-preserving).

In the example, if A and B have a property / method with the same name, then in A0_B we would see the property / method from A, but then in D, which is a subclass of A0_B, we would see B’s property / method.

2 Likes
26

I think there is a big problem with the definition of monotonicity.

In A Monotonic Superclass Linearization for Dylan, monotonicity is defined as:

A monotonic linearization is one in which every property inherited by a class is inherited or defined by one of its direct superclasses; that is, an inherited property cannot skip over all of the direct superclasses.

The definition is different from this link

A MRO is monotonic when the following is true: if C1 precedes C2 in the linearization of C, then C1 precedes C2 in the linearization of any subclass of C . Otherwise, the innocuous operation of deriving a new class could change the resolution order of methods, potentially introducing very subtle bugs.

For example, suppose we have the following linearizations

  • MRO for A0_B: A0_B, A0, A, B
  • MRO for B_A1: B_A1, B, A1, A
  • MRO for A0_B_A1: A0_B_A1, B_A1, A0_B, A0, B, A1, A

Suppose the my_property is defined in both B.my_property and A.my_property, then A0_B_A1.my_property is resolved to B.my_property and B_A1.my_property is also resolved to B.my_property, therefore, we can say my_property “inherited by a class is inherited or defined by one of its direct superclasses”. It’s not a violation of monotonicity according to the paper’s definition.

On the other hand, in the paper, they also said:

This means that the linearization of a class must be an extension without reordering of the linearizations of all of its superclasses.

The claim is definitely false, because I already showed an example of reordering of the linearizations of all of its superclasses, which does not violate monotonicity. That is to say, preserving all subclasses’ MROs is a more restrictive characteristic than monotonicity.

No matter how monotonicity is defined, the point of this thread is that preserving all subclasses’ MROs can lead problems in Python code that looks good, as shown in the RunParsingUUID example.

27

We still haven’t seen any real-world use-cases here.

“Considered harmful” is perhaps a poor choice of words when you are clearly stating nothing more than a personal opinion (the “to me” qualifier). But regardless, how do you respond to this statement, which you quoted above:

How do you handle this problem? Because this is a very real problem. Subclassing shouldn’t change the behaviour any more than is defined in the subclass itself.

28

As I mentioned in the previous post, the claim is not a real problem because it is based on a different a definition of monotonicity.

Also the need of monotonicity is suspicious because:

  1. In practice, other languages, like Scala, use a looser linearization than C3, and they built sophisticated use cases of multiple inheritance on top of it, for example Scala compiler.
  2. I believe multiple inheritance usage like Scala compiler cannot be implemented with C3 linearization, because C3 cannot support even much simpler use cases like the RunParsingUUID example.
  3. Most superclasses in multiple inheritance are abstract mix-ins. The MRO for the abstract mix-ins are not actually visited anywhere other than merging into subclasses, therefore there is no visible behavior difference with or without monotonicity.
29

Yes, they (A Monotonic Superclass Linearization for Dylan) quoted it from this reference or theirs. They quoted the “Monotonicity Principle”, while your first link quoted the “Definition (Monotonic Linearization)” from the same article. See page 167 in the link. Yes, the “Monotonicity Principle” seems to be a more relaxed condition, than that of their Definition of Monotonic Linearization.

1 Like
30

I’m a little late to the party, let me state how I see this discussion as a Python user.

@Atry found a nit in Python implementation, and it’s totally fair to discuss the nit and possible solutions.

@Rosuav 's insistence on real-world use case, while a valid point, seems premature. Surely it’s OK to discuss things first?

I’d ask for two considerations:

  1. understandable algorithm
  2. doesn’t break code, even if it’s weird

Python’s MRO is notoriously hard for novice developers to grok, there’s a whole long document to describe it.
Would the proposed resolution algorithm make the resulting order easier or harder for a naive developer to understand?

Python is very dynamic, for example class bases can be swapped out at runtime. There’s bound to be a library somewhere that uses this trick, a quick search shows uses in Keras and SQLAlchemy.
The behaviour of the existing code should not change. If some corner case is changed, OP’s proposal would probably have to wait for the next major version of Python.

2 Likes
31

It’s very hard to discuss without non-toy examples. It’s not premature when the entire basis of discussion comes down to “this is completely unimportant and can be ignored” versus “this can’t currently be done”.

So how significant is this? If the only examples are toys like the one from the opening, it’s not significant. What we need is a real example that shows how this actually makes a difference.

Sure, you can discuss it purely academically, but I don’t think there’ll be any support for making a change just on the basis of “hey, I can create a weird situation here”.

So I’m going to bow out of this discussion until there’s something concrete to discuss.

3 Likes
32

My proposal to address this would be to make better tooling that can be called in github actions that highlights the MRO changes resulting from a PR.

Then leave it to developers to decide if the change is necessary, acceptable, or effectively breaking.

My 2c: a lot of code depends on standard library, and caution is needed, yet, at the same time, standard library continues to evolve, and changes to implementation of stdlib public classes and their MRO are quite normal. Being able to highlight a particular implication to the reviewers is all that’s needed.

33

Even though the original motivation of this thread is not about local precedence order, local precedence order can result in problems sometimes, too.

Because modern Python introduced ABC and Generic, multiple inheritance becomes common. For example:

Roughly 5.4k Python files on GitHub define classes like class GenericThenABC(Generic[T], ABC): https://github.com/search?q=class+"Generic["+"%2C+ABC"+language%3APython&type=code&l=Python

Roughly 3.6k Python files GitHub define classes like class ABCThenGeneric(ABC, Generic[T]): https://github.com/search?q=class+"ABC%2C+Generic["+language%3APython&type=code&l=Python

Unfortunately, current linearization implementation does not allow for extending both ABCThenGeneric and GenericThenABC, because of the local precedence order between ABC and Generic must be consistent.

I understand local precedence order is sometimes very useful, but it would be nice to be able to opt-out local precedence order when it is not useful. Why do users need to care about the order between ABC and Generic?

34

Wait, isn’t local precedence order the one that is explicitly stated by the programmer in the code? As in class A(B, C, D): pass defining the order A\prec B, A\prec C, A\prec D? I would think that if anything, what was intentionally and explicitly written in the code is what is important to take into account.

Maybe I misunderstood and LPO also includes B\prec C, and C\prec D. Is that the case? Are these inequalities that ones that you were referring to as nice to be able to opt-out?

35

That’s my understanding of LPO and I think it’s nice to support opt-out, otherwise we will get the following error easily:

Python 3.11.4 (main, Jun 20 2023, 17:23:00) [Clang 14.0.3 (clang-1403.0.22.14.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import typing
>>> T = typing.TypeVar("T")
>>> import abc
>>> class A(abc.ABC, typing.Generic[T]): pass
... 
>>> class B(typing.Generic[T], abc.ABC): pass
... 
>>> class C(A[int], B[str]): pass
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<frozen abc>", line 106, in __new__
TypeError: Cannot create a consistent method resolution
order (MRO) for bases ABC, Generic
36

Have you considered implementing this change yourself using a metaclass? Metaclasses can change quite a few things, such as the order of base classes. You could in principle write a metaclass that e.g. removes mixins from the new class’ bases list that are already present from another base class, thereby preventing conflicts from arising. Probably you’d need to also move all traits/mixins to the end of the list as well, and perhaps sort them in a well-known order.

Or perhaps you could just recalculate and replace the __mro__ entirely, for that matter, though it’s been a while since I’ve played with anything like that. Probably you could remove traits from the initial bases list, create the class, and then replace the MRO with a differently-calculated one.

Indeed, if you made a metaclass for traits, in fact, you could probably put the implementation there, such that it’s not needed to explicitly request a metaclass in classes.

Mostly the point here is that if there was going to be a change in how Python did MRO linearization, a proposal would need some kind of demonstration of how it would be implemented, and a metaclass would be a good way to do that. (And, in the meantime, you’d have the feature you wanted anyway.)

2 Likes
37

Yes. I planned to create a meta class as a package, including some other more rules that have not been discussed here.

38

I am writing a document about mix-in best practices for my company’s project. Some pitfalls can be avoided by carefully designing the hierarchy. Some other pitfalls are almost unavoidable unless changing linearization implementation as discussed here. The meta class will be useful for both avoidable and unavoidable pitfalls.

39

I just wanted to chime in and voice support for the work you’re doing. I’ve felt for a long time that premature linearization in the class hierarchy is the wrong approach to MRO, and to me a topological sort seems like a much better option, in that it produces the obvious result (at least to me) and doesn’t throw spurious errors like the current mechanism.

I look forward to seeing how you develop this.

1 Like