Skip to content

Instantly share code, notes, and snippets.

@trk9001
Last active October 14, 2020 21:13
Show Gist options
  • Save trk9001/90a50a69a12911b20af8e6708b73a9ec to your computer and use it in GitHub Desktop.
Save trk9001/90a50a69a12911b20af8e6708b73a9ec to your computer and use it in GitHub Desktop.
Demonstration of Python's C3 Method Resolution Order using a complex example.

The text in mro.md shows the steps of computing the MRO of the class M from the following script, using the C3 linearization algorithm. For more info, see this paper explaining the method resolution order used by Python since version 2.3.

#!/usr/bin/env python

class X:
  pass

class Y:
  pass

class Z:
  pass

class A(X):
  pass

class B(Y, Z):
  pass

class N:
  pass

class M(B, A, Z, N):
  pass

from pprint import pprint
pprint(M.mro())

It gives the following output.

[<class '__main__.M'>,
 <class '__main__.B'>,
 <class '__main__.Y'>,
 <class '__main__.A'>,
 <class '__main__.Z'>,
 <class '__main__.X'>,
 <class '__main__.N'>,
 <class 'object'>]

The MRO's of B, A, Z and N are trivial to compute:

L(B) = BYZ,
L(A) = AX,
L(Z) = Z,
L(N) = N

The MRO of M is:

L(M) = M + merge(L(B), L(A), L(Z), L(N), BAZN)

=> L(M) = M + merge(BYZ, AX, Z, N, BAZN)
=> L(M) = MB + merge(YZ, AX, Z, N, AZN)
=> L(M) = MBY + merge(Z, AX, Z, N, AZN)
=> L(M) = MBYA + merge(Z, X, Z, N, ZN)
=> L(M) = MBYAZ + merge(X, N, N)
=> L(M) = MBYAZX + merge(N, N)
=> L(M) = MBYAZXN

This result is confirmed by the output of the script. For a description of the merge function, see the paper referenced in README.md.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment