Welcome, guest | Sign In | My Account | Store | Cart

This function allows you to calculate the Method Resolution Order (MRO, or sometimes linearization) of a class or base classes. This is the so-called "C3" algorithm, as used by Python (new-style classes, from version 2.3 and higher). The MRO is the order of base classes that Python uses to search for methods and attributes. For single inheritance, the MRO is obvious and straight-forward and not very exciting, but for multiple inheritance it's not always obvious what the MRO should be.

Python, 111 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
def mro(*bases):
    """Calculate the Method Resolution Order of bases using the C3 algorithm.

    Suppose you intended creating a class K with the given base classes. This
    function returns the MRO which K would have, *excluding* K itself (since
    it doesn't yet exist), as if you had actually created the class.

    Another way of looking at this, if you pass a single class K, this will
    return the linearization of K (the MRO of K, *including* itself).
    """
    seqs = [list(C.__mro__) for C in bases] + [list(bases)]
    res = []
    while True:
      non_empty = list(filter(None, seqs))
      if not non_empty:
          # Nothing left to process, we're done.
          return tuple(res)
      for seq in non_empty:  # Find merge candidates among seq heads.
          candidate = seq[0]
          not_head = [s for s in non_empty if candidate in s[1:]]
          if not_head:
              # Reject the candidate.
              candidate = None
          else:
              break
      if not candidate:
          raise TypeError("inconsistent hierarchy, no C3 MRO is possible")
      res.append(candidate)
      for seq in non_empty:
          # Remove candidate.
          if seq[0] == candidate:
              del seq[0]



###

if __name__ == '__main__':
    # Run self-tests. Prints nothing if they succeed.
    O = object
    class SeriousOrderDisagreement:
        class X(O): pass
        class Y(O): pass
        class A(X, Y): pass
        class B(Y, X): pass
        bases = (A, B)

    try:
        x = mro(*SeriousOrderDisagreement.bases)
    except TypeError:
        pass
    else:
        print("failed test, mro should have raised but got %s instead" % (x,))

    class Example0:  # Trivial single inheritance case.
        class A(O): pass
        class B(A): pass
        class C(B): pass
        class D(C): pass
        tester = D
        expected = (D, C, B, A, O)

    class Example1:
        class F(O): pass
        class E(O): pass
        class D(O): pass
        class C(D, F): pass
        class B(D, E): pass
        class A(B, C): pass
        tester = A
        expected = (A, B, C, D, E, F, O)

    class Example2:
        class F(O): pass
        class E(O): pass
        class D(O): pass
        class C(D, F): pass
        class B(E, D): pass
        class A(B, C): pass
        tester = A
        expected = (A, B, E, C, D, F, O)

    class Example3:
        class A(O): pass
        class B(O): pass
        class C(O): pass
        class D(O): pass
        class E(O): pass
        class K1(A, B, C): pass
        class K2(D, B, E): pass
        class K3(D, A): pass
        class Z(K1, K2, K3): pass

        assert mro(A) == (A, O)
        assert mro(B) == (B, O)
        assert mro(C) == (C, O)
        assert mro(D) == (D, O)
        assert mro(E) == (E, O)
        assert mro(K1) == (K1, A, B, C, O)
        assert mro(K2) == (K2, D, B, E, O)
        assert mro(K3) == (K3, D, A, O)

        tester = Z
        expected = (Z, K1, K2, K3, D, A, B, C, E, O)

    for example in [Example0, Example1, Example2, Example3]:
        # First test that the expected result is the same as what Python
        # actually generates.
        assert example.expected == example.tester.__mro__
        # Now check the calculated MRO.
        assert mro(example.tester) == example.expected

Particularly when dealing with multiple inheritance, you need a way to determine in which order to search a class and its superclasses. Normally Python handles that automatically, but on occasion you might need to generate this Method Resolution Order yourself, without (or before) creating the class. This function will do this.

Historically, Python has used three different algorithms. Two of them are obsolete.

Python 1.x and 2.x classic classes use an algorithm which can give buggy results for certain inheritance relationships. In Python 3, classic classes are gone.

With the introduction of new-style classes in Python 2.2, a new algorithm was used. Unfortunately that also turned out to be buggy, and it was replaced in Python 2.3 with the proven C3 algorithm. This function calculates the C3 MRO of a list of base classes.

For a detailed (and rather technical) discussion of the C3 algorithm and why it is preferred, see Michele Simionato's excellent essay here:

http://www.python.org/download/releases/2.3/mro/

I had need of this when writing a metaclass that needed to interrogate the base classes, and all of their superclasses, before creating the new class. I initially tried a trick, using

type('fake name', bases, {}).__mro__

to have Python create a throw-away class with the same base classes, but that turned out to fragile and hard to use, leading to RecursionError in my metaclass. So I wrote this to calculate the MRO of the base classes without relying on type().

1 comment

Steven D'Aprano (author) 10 years, 5 months ago  # | flag

This has been written for Python 3, but also works in any version of Python from 2.3 onwards.

Created by Steven D'Aprano on Sat, 11 Jun 2011 (MIT)
Python recipes (4591)
Steven D'Aprano's recipes (22)

Required Modules

  • (none specified)

Other Information and Tasks