How can I sort a list of Python classes by inheritance depth?

Question

How would I sort a list of classes in Python, making sure that any child class is before any of its parent classes in the list?

I ask because I want to see what type out of a list of types, an object belongs to, but find the most specific type, if it belongs to multiple.

Answer 1

Simply sort by len(cls.mro()).

If C2 is a subclass of C1, it must hold that len(C1.mro()) < len(C2.mro()) (because each class in C1.mro() must also appear in C2.mro()). Therefore, you can simply sort by the length of the mro list:

class A(object): pass
class X(object): pass
class B(A, X): pass
class C(B): pass
class D(C): pass

sorted([B, C, A, D, X], key = lambda cls: len(cls.mro()))
=> [__main__.A, __main__.X, __main__.B, __main__.C, __main__.D]

To also support old-style classes, you can replace cls.mro() with inspect.getmro(cls).

Answer 2

A better approach would be to use a set and then move along the inheritance tree of the target class.

def find_parent(target, class_set):
    if target in class_set:
        return [target]
    else:
        bases = []
        for parent in target.__bases__:
            result = find_parent(parent, class_set)
            if result is not None:
                bases.extend(result)
        return bases

Example:

class A(object):
    pass

class B(str):
    pass

class C(A):
    pass

class D(A, dict):
    pass

class_set = {dict, A}

print find_parent(A, class_set)
print find_parent(B, class_set)
print find_parent(C, class_set)
print find_parent(D, class_set)

Gives you this result:

[<class '__main__.A'>]
[]
[<class '__main__.A'>]
[<class '__main__.A'>, <type 'dict'>]