Skip to content

Instantly share code, notes, and snippets.

@outofmbufs
Created October 1, 2021 19:13
Show Gist options
  • Save outofmbufs/901945b01b726df00021c9ca95c838ef to your computer and use it in GitHub Desktop.
Save outofmbufs/901945b01b726df00021c9ca95c838ef to your computer and use it in GitHub Desktop.
Rewrote the python MRO (C3 method resolution order) in python, just as an exercise in understanding it
# toy example re-implementing C3 method resolution order
# (MRO, as used for python multi-inheritance)
#
# Algorithm snippets in comments come from:
# https://www.python.org/download/releases/2.3/mro/
# and are notated as [2.3MRO]
#
# A Hier represents a class hierarchy, with a name, and a possibly-empty
# list of bases (each base itself also a Hier).
#
# Examples: two base classes, C1 and C2, that do not inherit:
#
# C1 = Hier('C1')
# C2 = Hier('C2')
#
# A subclass with single inheritance:
#
# D1 = Hier('D1', C1)
#
# A subclass with multiple inheritance:
#
# D2 = Hier('D2', C1, C2)
#
# Illegal python class hierarchies can be represented as Hiers:
#
# class X: pass
# class Y: pass
# class A(X, Y): pass
# class B(Y, X): pass
# class C(A, B): pass # raises TypeError, no MRO
#
# But this works:
#
# _O = Hier('object') # implicit
# X = Hier('X', _O)
# Y = Hier('Y', _O)
# A = Hier('A', X, Y)
# B = Hier('B', Y, X)
# C = Hier('C', A, B)
#
# though, of course, L(C) will raise an exception (for the same reason
# that the python interpreter does for this hierarchy). But this is why
# why Hiers are used instead of simply using dummy python classes - so
# these situations can be modeled and explored.
#
class Hier:
def __init__(self, token, *bases):
self.token = token
# allow naked strings in bases (shorthand for Hier('foo'))
self.bases = [b if hasattr(b, 'token') else Hier(b) for b in bases]
def __repr__(self):
if self.bases:
breps = ", " + ", ".join(repr(x) for x in self.bases)
else:
breps = ""
return f"Hier('{self.token}'{breps})"
def __eq__(self, other):
try:
return self.token == other.token
except AttributeError:
return NotImplemented
def __str__(self):
if not self.bases:
return self.token
btoks = ""
sep = ""
for b in self.bases:
btoks += sep + b.token
sep = ", "
return f"{self.token}({btoks})"
def L(c):
# from [2.3MRO]:
# L[C(B1 ... BN)] = C + merge(L[B1], ... L[BN], B1 ... BN)
# NOTE: the (trivial/degenerate) case of c.bases=[] results in empty
# lists, which _merge already has to handle in general anyway.
return [c] + _merge(*[L(b) for b in c.bases], c.bases)
# Return a list of the tokens instead of a list of the Hiers; essentially
# this is a "list of strings" version of L() better for printing results
def sL(c):
return [x.token for x in L(c)]
def _strict_find_good_head(hierlists):
# from [2.3MRO] -- (paraphrasing)
# Find the first "good" head, defined as: the first head
# of a list that is not in the tail of any (other) list
#
# Question: [2.3MRO] explicitly says (quoting):
# if this head is not in the tail of any of
# the other lists, then add it to the linearization
# **NOTE THIS** ^^^^^^^^^
#
# Not sure how important this 'other lists' qualifier really is.
# A list of subclasses of a class cannot (well, should not) contain
# the class itself. Ignoring that qualifier would simplify this code.
for i, cx in enumerate(hierlists):
otherlists = (x for j, x in enumerate(hierlists) if i != j)
candidate, *_ = cx
if all(candidate not in tail for _, *tail in otherlists):
return candidate
raise ValueError("Could not complete merge")
# version of _find_good_head that ignores the "other lists" qualifier
def _lax_find_good_head(hierlists):
for candidate, *_ in hierlists:
if all(candidate not in tail for _, *tail in hierlists):
return candidate
raise ValueError("Could not complete merge")
_find_good_head = _lax_find_good_head
def _merge(*lists):
merged = []
# loop until nothing but empties are left
while lists := [lz for lz in lists if lz]:
# from [2.3MRO] --
# find a good head, use it, remove it from all lists
# If can't find a good head, can't resolve an MRO
# ... ValueError raised in _find_good_head
# Then remove this one from all candidate lists.
# When nothing but empties are left (handled in 'while'), done.
head = _find_good_head(lists)
merged.append(head)
lists = [[b for b in lz if b != head] for lz in lists]
return merged
if __name__ == "__main__":
import unittest
class TestMethods(unittest.TestCase):
def test1(self):
# some trivial cases
_O = Hier('_O')
self.assertEqual(sL(_O), ['_O'])
A = Hier('A', _O)
self.assertEqual(sL(A), ['A', '_O'])
def test2(self):
# test case taken directly from [2.3MRO]
_O = Hier('_O')
F = Hier('F', _O)
E = Hier('E', _O)
D = Hier('D', _O)
C = Hier('C', D, F)
B = Hier('B', D, E)
A = Hier('A', B, C)
self.assertEqual(sL(A), ['A', 'B', 'C', 'D', 'E', 'F', '_O'])
def test3(self):
# test case taken directly from [2.3MRO]
# Same as prior test except B is (E, D) instead of (D, E)
# This changes the result, per discussion in [2.3MRO]
_O = Hier('_O')
F = Hier('F', _O)
E = Hier('E', _O)
D = Hier('D', _O)
C = Hier('C', D, F)
B = Hier('B', E, D)
A = Hier('A', B, C)
self.assertEqual(sL(A), ['A', 'B', 'E', 'C', 'D', 'F', '_O'])
def test4(self):
# test case taken directly from [2.3MRO]
_O = Hier('_O')
A = Hier('A', _O)
B = Hier('B', _O)
C = Hier('C', _O)
D = Hier('D', _O)
E = Hier('E', _O)
K1 = Hier('K1', A, B, C)
K2 = Hier('K2', D, B, E)
K3 = Hier('K3', D, A)
Z = Hier('Z', K1, K2, K3)
self.assertEqual(sL(Z), ['Z', 'K1', 'K2', 'K3',
'D', 'A', 'B', 'C', 'E', '_O'])
def test5(self):
# test case taken directly from [2.3MRO]
_O = Hier('_O')
X = Hier('X', _O)
Y = Hier('Y', _O)
A = Hier('A', X, Y)
B = Hier('B', Y, X)
self.assertEqual(sL(A), ['A', 'X', 'Y', '_O'])
self.assertEqual(sL(B), ['B', 'Y', 'X', '_O'])
C = Hier('C', A, B)
self.assertRaises(ValueError, sL, C)
def test6(self):
# test case taken directly from [2.3MRO]
F = Hier('F')
E = Hier('E', F)
G = Hier('G', F, E)
# this is ambiguous, so raises an exception
self.assertRaises(ValueError, sL, G)
# interestingly, this example is one of the very few that
# is affected by the inclusion of B1 ... BN as the last list
# in the expansion:
# L[C(B1 ... BN)] = C + merge(L[B1] ... L[BN], B1 ... BN)
# This was discovered when earlier versions of the code
# inadvertently omitted that argument yet it made no
# difference in any of the other tests (!)
#
# To demonstrate that... :
def badL(c):
# leaves out the final B1 .. BN list compared to correct L
return [c] + _merge(*[L(b) for b in c.bases])
# this will return something, whereas the correct L bombs:
self.assertTrue(badL(G)) # i.e., it returns something
def test7(self):
# test case taken from C3 OOPSLA paper
Pane = Hier('Pane')
ScrollingMixin = Hier('ScrollingMixin')
EditingMixin = Hier('EditingMixin')
ScrollablePane = Hier('ScrollablePane', Pane, ScrollingMixin)
EditablePane = Hier('EditablePane', Pane, EditingMixin)
ESPane = Hier('ESPane', ScrollablePane, EditablePane)
self.assertEqual(sL(ESPane), ['ESPane',
'ScrollablePane',
'EditablePane',
'Pane',
'ScrollingMixin',
'EditingMixin'])
def test8(self):
# test case taken from C3 OOPSLA paper
Obj = Hier('Obj')
Boat = Hier('Boat', Obj)
DayBoat = Hier('DayBoat', Boat)
WheelBoat = Hier('WheelBoat', Boat)
EngineLess = Hier('EngineLess', DayBoat)
SmallMultiHull = Hier('SmallMultiHull', DayBoat)
PedalWheel = Hier('PedalWheel', EngineLess, WheelBoat)
SmallCat = Hier('SmallCat', SmallMultiHull)
Pedalo = Hier('Pedalo', PedalWheel, SmallCat)
self.assertEqual(sL(Pedalo), ['Pedalo',
'PedalWheel',
'EngineLess',
'SmallCat',
'SmallMultiHull',
'DayBoat',
'WheelBoat',
'Boat',
'Obj'])
def test9(self):
# test case taken from stackoverflow (lol, where else?!?)
_O = Hier('_O')
A = Hier('A', _O)
B = Hier('B', A)
C = Hier('C', A)
D = Hier('D', A)
E = Hier('E', B, C)
F = Hier('F', B, D)
G = Hier('G', C, D)
H = Hier('H', E, F, G)
self.assertEqual(sL(H), ['H', 'E', 'F', 'B', 'G',
'C', 'D', 'A', '_O'])
# try the tests again with the other find_good_head algorithm
def test_alternate_head(self):
# yeah, this is a questionable hack, justified in the
# name of "all of this is just for demonstration/learning"
global _find_good_head
prev = _find_good_head
if _find_good_head == _strict_find_good_head:
_find_good_head = _lax_find_good_head
else:
_find_good_head = _strict_find_good_head
for test in [f for f in dir(self) if f.startswith('test')]:
if test != 'test_alternate_head':
getattr(self, test)()
_find_good_head = prev
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment