Computing the MRO

One question as of yet unanswered is how does Python determine the __mro__ for a type? A basic idea behind the algorithm is provided in this section. This is not essential for just using super, or reading following sections, so you can jump to the next section if you want.

Python determines the precedence of types (or the order in which they should be placed in any __mro__) from two kinds of constraints specified by the user:

  1. If A is a superclass of B, then B has precedence over A. Or, B should always appear before A in all __mro__s (that contain both). In short let's denote this as B > A.

  2. If C appears before D in the list of bases in a class statement (eg. class Z(C,D):), then C > D.

In addition, to avoid being ambiguous, Python adheres to the following principle:

  1. If E > F in one scenario (or one __mro__), then it should be that E > F in all scenarios (or all __mro__s).

We can satisfy the constraints if we build the __mro__ for each new class C we introduce, such that:

  1. All superclasses of C appear in the C.__mro__ (plus C itself, at the start), and

  2. The precedence of types in C.__mro__ does not conflict with the precedence of types in B.__mro__ for each B in C.__bases__.

Here the same problem is translated into a game. Consider a class hierarchy as follows:

Figure 2.2. A Simple Hierarchy

A Simple Hierarchy

Since only single inheritance is in play, it is easy to find the __mro__ of these classes. Let's say we define a new class as class N(A,B,C). To compute the __mro__, consider a game using abacus style beads over a series of strings.

Figure 2.3. Beads on Strings - Unsolvable

Beads on Strings - Unsolvable

Beads can move freely over the strings, but the strings cannot be cut or twisted. The strings from left to right contain beads in the order of __mro__ of each of the bases. The rightmost string contains one bead for each base, in the order the bases are specified in the class statement.

The objective is to line up beads in rows, so that each row contains beads with only one label (as done with the O bead in the diagram). Each string represents an ordering constraint, and if we can reach the goal, we would have an order that satisfies all constraints. We could then just read the labels off rows from the bottom up to get the __mro__ for N.

Unfortunately, we cannot solve this problem. The last two strings have C and B in different orders. However, if we change our class definition to class N(A,C,B), then we have some hope.

Figure 2.4. Beads on Strings - Solved

Beads on Strings - Solved

We just found out that N.__mro__ is (N,A,C,B,object) (note we inserted N at the head). The reader can try out this experiment in real Python (for the unsolvable case above, Python raises an exception). Observe that we even swapped the position of two strings, keeping the strings in the same order as the bases are specified in the class statement. The usefulness of this is seen later.

Sometimes, there might be more than one solution, as shown in the figure below. Consider four classes class A(object), class B(A), class C(object) and class D(C). If a new class is defined as class E(B, D), there are multiple possible solutions that satisfy all constraints.

Figure 2.5. Multiple Solutions

Multiple Solutions

Possible positions for A are shown as the little beads. The order can be kept unambiguous (more correctly, monotonic) if the following policies are followed:

  1. Arrange strings from left to right in order of appearance of bases in the class statement.

  2. Attempt to arrange beads in rows moving from bottom up, and left to right. What this means is that the MRO of class E(B, D) will be set to: (E,B,A,D,C,object). This is because A, being left of C, will be selected first as a candidate for the second row from bottom.

This, essentially, is the idea behind the algorithm used by Python to generate the __mro__ for any new type. The formal algorithm is formally explained elsewhere [mro-algorithm].