# Make MRO topological sorted

**URL:** <https://discuss.python.org/t/make-mro-topological-sorted/32300>\
**Category:** Python Help\
**Created:** [August 25, 2023, 2:55pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300 "2023-08-25T14:55:08Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 2:55pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/1 "2023-08-25T14:55:08Z")

</div>

Python [MRO](https://www.python.org/download/releases/2.3/mro/) is a linear ordering of the base classes that is used to decide the order in which inherited methods are overridden. As mentioned in @guido’s [blog](http://python-history.blogspot.com/2010/06/method-resolution-order.html#:~:text=comes%20into%20play.-,Basically%2C%20the%20idea%20behind%20C3%20is%20that%20if%20you%20write%20down,such%20an%20ordering%20can%20not%20be%20determined%2C%20the%20algorithm%20will%20fail.,-Thus%2C%20in%20Python):

> Basically, the idea behind C3 is that if you write down all of the ordering rules imposed by inheritance relationships in a complex class hierarchy, the algorithm will determine a monotonic ordering of the classes that satisfies all of them. If such an ordering can not be determined, the algorithm will fail.

Unfortunately, sometimes even when there is a consistent monotonic ordering, the current MRO implementation might be failed to find it. For example, the following code will raise an error:

```auto
class A:
    pass

class B:
    pass

class A0(A):
    pass

class A1(A):
    pass

class A0_B(A0, B):
    pass

class B_A1(B, A1):
    pass

class A0_B_A1(A0_B, B_A1):
    pass

```

```auto
TypeError: Cannot create a consistent method resolution
order (MRO) for bases A, B

```

A workaround it to add more hints to the MRO. For example, we can change `class A0_B(A0, B)` to `class A0_B(A0, B, A)`:

```auto
class A:
    pass

class B:
    pass

class A0(A):
    pass

class A1(A):
    pass

# Changed from `class A0_B(A0, B):`
class A0_B(A0, B, A):
    pass

class B_A1(B, A1):
    pass

class A0_B_A1(A0_B, B_A1):
    pass

```

However, the workaround is not always possible, because the user of `A0_B` and `B_A1` might not be able to change `A0_B`’s implementation.

I think the best solution is to perform a proper topological sorting when determining the MRO of a class, instead of merging the MROs of the base classes.

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [August 25, 2023, 3:31pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/2 "2023-08-25T15:31:46Z")

</div>

> [@Atry](#):
>
> A workaround it to add more hints to the MRO. For example, we can change `class A0_B(A0, B)` to `class A0_B(A0, B, A)`:

This is not a hint, though - it’s an override. You’re changing the resolution order. And since there are multiple conflicting ways that this can be done, it MUST be done explicitly. Without it, A would come before B; you’re overriding that to specify that B comes before A.

Do you have an actual use-case for this, or is it just for toy examples? I’ve never come across any real-world hierarchy in which this linearization has been a problem.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 4:40pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/3 "2023-08-25T16:40:42Z")

</div>

Another example here:

```auto
from abc import ABC, abstractmethod
from typing import Generic, TypeVar, final
from uuid import UUID

ElementType = TypeVar('ElementType')

class ToReprStr(Generic[ElementType]):
    @final
    def to_repr_str(self, element: ElementType):
        return repr(element)

class LoggingMixin(ToReprStr[UUID], ABC):
    @abstractmethod
    def run(self) -> UUID:
        ...

    @final
    def logged_run(self, source: bytes):
        result = self.run()
        print(self.to_repr_str(result))
        return result

class ToStr(Generic[ElementType]):
    @final
    def to_str(self, element: ElementType):
        return str(element)

class AbstractFromStr(ABC):
    @abstractmethod
    def from_str(self, source: str):
        ...

class UUIDFromStr(AbstractFromStr):
    @final
    def from_str(self, source: str):
        return UUID(source)

class UUIDFromBytes(UUIDFromStr, ToStr[bytes]):
    @final
    def uuid_from_bytes(self, source: bytes):
        return self.from_str(self.to_str(source))

class RunParsingUUID(UUIDFromBytes, LoggingMixin):
    @final
    def run(self):
        return self.uuid_from_bytes(b"id")

```

Suppose `ToReprStr` and `LoggingMixin` are from a library to schedule some task in `run` and log the result. `ToStr`, `AbstractFromStr`, `UUIDFromStr`, and `UUIDFromBytes` are classes from another serialization/deserialization library.

Now you want to create `RunParsingUUID` using both libraries, and you got the error:

```auto
TypeError: Cannot create a consistent method resolution
order (MRO) for bases ABC, Generic

```

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [August 25, 2023, 4:43pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/4 "2023-08-25T16:43:40Z")

</div>

> [@Atry](#):
>
> Suppose `ToReprStr` and `LoggingMixin` are from a library to schedule some task in `run` and log the result. `ToStr`, `AbstractFromStr`, `UUIDFromStr`, and `UUIDFromBytes` are classes from another library to serialize things.

This is still looking very artificial and contrived. I ask again: Do you have an actual use-case for this?

I would expect to see this sort of code in an enterprisey Java codebase.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 4:46pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/5 "2023-08-25T16:46:57Z")

</div>

Yes it’s an artificial example. I have an actual example but I cannot share it here right now. I am happy to see that you can get the point that there could be some code similar to this.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 4:52pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/6 "2023-08-25T16:52:32Z")

</div>

@davidism Please don’t move this thread to Python Help. It’s not a post to ask help. Instead, it aims to discuss a design issue in C3 linearization. Especially, our current implementation of MRO does not actually fulfill @guido 's idea:

> Basically, the idea behind C3 is that if you write down all of the ordering rules imposed by inheritance relationships in a complex class hierarchy, the algorithm will determine a monotonic ordering of the classes that satisfies all of them. If such an ordering can not be determined, the algorithm will fail.

The example clearly shows that the current MRO implementation sometimes can fail to find a monotonic ordering even when the monotonic ordering exists.

Also the issue can be fixed by properly implementing topological sorting in the MRO implementation

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [August 25, 2023, 5:02pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/7 "2023-08-25T17:02:03Z")

</div>

> [@Atry](#):
>
> Yes it’s an artificial example. I have an actual example but I cannot share here right now. I am happy to see that you can get the point that there could be some code similar to this.

So far, all I’ve seen is that you can create toy examples, which can be done with anything. Are you able to create a cut-down version of the actual example?

> [@Atry](#):
>
> The example clearly shows that the current MRO implementation sometimes can fail to find a monotonic ordering even when the monotonic ordering exists.

What do you mean? There is no such ordering with what you have given, and you have to override the normal rules in order to create one. Comparing your example with the one you say adds a “hint”:

```auto
>>> A0_B. __mro__
(<class ' __main__.A0_B'>, <class ' __main__.A0'>, <class ' __main__.A'>, <class ' __main__.B'>, <class 'object'>)
>>> class A0_B(A0, B, A):
... pass
... 
>>> A0_B. __mro__
(<class ' __main__.A0_B'>, <class ' __main__.A0'>, <class ' __main__.B'>, <class ' __main__.A'>, <class 'object'>)

```

Note that the second version places B before A. This is a violation of expectation; the obvious linearization of A0(A) followed by B would place A before B. Python allows you to disagree explicitly, but this isn’t something that will happen automatically.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 5:14pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/8 "2023-08-25T17:14:29Z")

</div>

> What do you mean? There is no such ordering with what you have given, and you have to override the normal rules in order to create one. Comparing your example with the one you say adds a “hint”:

The purpose of linearization is to let the Python users to specify dependencies between classes, and the Python runtime will find a monotonic ordering. A proper implementation will require the MRO to be delayed determined by topological sorting, for each concrete class at least. For example, `A0_B(A0, B)` added the following restrictions in MRO:

```auto
A0_B -> A0
A0 -> B

```

Because of `A0(A)`, we also have:

```auto
A0 -> A

```

Note that the user did not specify the relationship between `A` and `B`, therefore, ideally the Python runtime should have the flexibility to determine the order between `A` and `B` according to @guido 's idea.

Unfortunately, the current implementation is based on merging MROs, not topological sorting, as a result, the order between `A` and `B` is not late-bound, resulting the error.

A better linearization implementation should be based on topological sorting.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 5:20pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/9 "2023-08-25T17:20:44Z")

</div>

What is worse is when `A` is `ABC` and `B` is `Generic`. Because `ABC` and `Generic` are independent from each other, users basically have no control to their ordering, and they can create conflicting MRO easily as shown in the `RunParsingUUID` example.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 5:25pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/10 "2023-08-25T17:25:45Z")

</div>

Another problem of MRO merging is that it violates the assumption of backward-compatibility.

People usually assume that extracting parts of your class into an interface would not break backward-compatibility. Unfortunately, because of the current MRO implementation, the assumption is false.

For example, the following code would not result in an error:

```auto
from abc import ABC, abstractmethod
from typing import Generic, TypeVar, final
from uuid import UUID

ElementType = TypeVar('ElementType')

class ToReprStr(Generic[ElementType]):
    @final
    def to_repr_str(self, element: ElementType):
        return repr(element)

class LoggingMixin(ToReprStr[UUID], ABC):
    @abstractmethod
    def run(self) -> UUID:
        ...

    @final
    def logged_run(self, source: bytes):
        result = self.run()
        print(self.to_repr_str(result))
        return result

class ToStr(Generic[ElementType]):
    @final
    def to_str(self, element: ElementType):
        return str(element)

class UUIDFromStr:
    @final
    def from_str(self, source: str):
        return UUID(source)

class UUIDFromBytes(UUIDFromStr, ToStr[bytes]):
    @final
    def uuid_from_bytes(self, source: bytes):
        return self.from_str(self.to_str(source))

class RunParsingUUID(UUIDFromBytes, LoggingMixin):
    @final
    def run(self):
        return self.uuid_from_bytes(b"id")

```

However, if the author of the serialization library lets `UUIDFromStr` implement an interface, `RunParsingUUID` will be broken:

```auto
class AbstractFromStr(ABC):
    @abstractmethod
    def from_str(self, source: str):
        ...

class UUIDFromStr(AbstractFromStr):
    @final
    def from_str(self, source: str):
        return UUID(source)

```

---

<div class="post-metadata">

**Author:** ![jamestwebber](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/jamestwebber/32/12799_2.png) [@jamestwebber](https://discuss.python.org/u/jamestwebber)\
**Post date:** [August 25, 2023, 8:06pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/11 "2023-08-25T20:06:44Z")

</div>

> [@Atry](#):
>
> People usually assume that extracting parts of your class into an interface would not break backward-compatibility. Unfortunately, because of the current MRO implementation, the assumption is false.

But that’s not _MRO_ breaking compatibility, it’s the people who made a bad assumption about what would happen?

In contrast, changing the behavior from MRO would be massive breaking change.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 8:32pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/12 "2023-08-25T20:32:27Z")

</div>

> [@jamestwebber](#):
>
> But that’s not _MRO_ breaking compatibility, it’s the people who made a bad assumption about what would happen?

There are commits in CPython that already broke the backward compatibility.  
For example, in [this commit](https://github.com/python/cpython/commit/2e624690bd74071358566300b7ef0bc45f444a30), `_GeneratorContextManagerBase` is introduced, and the order between `AbstractContextManager` and `ContextDecorator` are changed, therefore, it is a backward incompatible change.

In fact, I guess the reason why `AbstractContextManager` and `ContextDecorator` were swapped is to work around the inconsistent MRO error in tests when introducing `_GeneratorContextManagerBase`. From my own experience, I sometimes need to randomly adjust the order of super classes in order to pass MRO check, even when the super classes look independent.

Unfortunately, randomly changing the order like [the commit](https://github.com/python/cpython/commit/2e624690bd74071358566300b7ef0bc45f444a30) did would create more breakage in users’ code.

---

<div class="post-metadata">

**Author:** ![jamestwebber](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/jamestwebber/32/12799_2.png) [@jamestwebber](https://discuss.python.org/u/jamestwebber)\
**Post date:** [August 25, 2023, 8:38pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/13 "2023-08-25T20:38:25Z")

</div>

> [@Atry](#):
>
> There are commits in CPython that already break the backward compatibility.

Those changes may have broken compatibility, sure. My point is that’s not possible for the current method of MRO to “break compatibility”. It _defines_ compatibility.

Perhaps what you meant is that a different method would allow changing inheritance in a way that would currently break compatibility. That’s different though.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 8:43pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/14 "2023-08-25T20:43:06Z")

</div>

This thread was created in the Idea board and improperly got moved to Python Help board. The motivation of this thread is to discuss the issues in the current MRO implementation. One of the issues is that the MRO implementation defines compatibility in a counterintuitive way, preventing library authors from keeping backward compatibility when adding features.

---

<div class="post-metadata">

**Author:** ![jamestwebber](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/jamestwebber/32/12799_2.png) [@jamestwebber](https://discuss.python.org/u/jamestwebber)\
**Post date:** [August 25, 2023, 8:51pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/15 "2023-08-25T20:51:31Z")

</div>

I understand, but changing the method resolution order is also a backwards-incompatible change, and it affects everyone. Somewhat improving the usability for new code can’t take precedence over that. So changing the method is clearly a non-starter.

Perhaps there could be improved documentation or better tooling to help people avoid those issues.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 8:54pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/16 "2023-08-25T20:54:13Z")

</div>

> [@jamestwebber](#):
>
> changing the method resolution order is also a backwards-incompatible change

I think it is possible to change the MRO implementation in a backward-compatible way. Because current MRO implementation is too strict, a looser implementation would not break backward-compatibility as long as it produces the same result for existing working cases.

---

<div class="post-metadata">

**Author:** ![gwerbin](https://avatars.discourse-cdn.com/v4/letter/g/76d3ee/32.png) [@gwerbin](https://discuss.python.org/u/gwerbin)\
**Post date:** [August 25, 2023, 10:48pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/17 "2023-08-25T22:48:09Z")

</div>

> [@Rosuav](#):
>
> I would expect to see this sort of code in an enterprisey Java codebase.

I don’t see how that disqualify is this as a legitimate example. This seems like a completely legitimate way to structure libraries and components within an application.

As for the idea, is it always the case that the current linear MRO is a strict subset of the topologically-sorted MRO? If that’s true, then I don’t see why this would be a breaking change for users.

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [August 25, 2023, 10:51pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/18 "2023-08-25T22:51:51Z")

</div>

> [@gwerbin](#):
>
> > [@Rosuav](#):
> >
> > I would expect to see this sort of code in an enterprisey Java codebase.
> 
> I don’t see how that disqualify is this as a legitimate example. This seems like a completely legitimate way to structure libraries and components within an application.

Inheriting from classes to manage formatting and logging? That isn’t something I see in most Python codebases. And the rules of Java are VERY different. (I’m not going to say whether it’s good or bad in a Java context, although I will say that “enterprisey” is not exactly a compliment.) Hence my repeated call for an actual **Python** use-case.

---

<div class="post-metadata">

**Author:** ![Atry](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/atry/32/13503_2.png) [@Atry](https://discuss.python.org/u/Atry)\
**Post date:** [August 25, 2023, 11:56pm UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/19 "2023-08-25T23:56:46Z")

</div>

I think you are essentially saying “I don’t use multiple inheritance, so any issues in MRO don’t bother me, and any usage of multiple inheritance is not Pythonic to me”.

IMHO, Python is a programming language that allows people to use it in different ways. In particular, built-in classes like `ABC` and `Generic` are commonly used in multiple inheritance in modern Python code. I believe the current MRO implementation would prevent `ABC` and `Generic` from being used in sophisticated use cases.

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [August 26, 2023, 12:03am UTC](https://discuss.python.org/t/make-mro-topological-sorted/32300/20 "2023-08-26T00:03:03Z")

</div>

> [@Atry](#):
>
> I think you are essentially saying “I don’t use multiple inheritance, so any issues in MRO don’t bother me, and any usage of multiple inheritance is not Pythonic to me”.

That is most definitely not true. Please don’t read into my words what I didn’t put there. I have used MI in many languages, including Python, and I have not had any problem with Python’s MRO rules.

[Next page](https://discuss.python.org/t/make-mro-topological-sorted/32300.md?page=2)