Python implementation of the C3 algorithm used in Python for MRO

c3.py

from functools import lru_cache
from typing import Dict, Hashable, List, Optional, TypeVar

T = TypeVar("T", bound=Hashable)


def c3_linearize(dep_tree: Dict[T, List[T]], root: T) -> List[T]:
    """Linearize a dependency tree"""

    @lru_cache(None)
    def helper(root: T) -> List[T]:
        return [
            root,
            *c3_merge(*(helper(dep) for dep in dep_tree[root]), dep_tree[root]),
        ]

    def c3_merge(*args: List[T]) -> List[T]:
        merge_remaining = [list(l) for l in args]
        merge: List[T] = []
        while any(len(l) > 0 for l in merge_remaining):
            # select good candidate
            candidate: Optional[T] = None
            for i in range(len(merge_remaining)):
                if len(merge_remaining[i]) == 0:
                    continue
                head = merge_remaining[i][0]
                # see if a good candidate
                head_is_good_candidate = False
                for j in range(i + 1, len(merge_remaining)):
                    tail_other_list = merge_remaining[j][1:]
                    if head not in tail_other_list:
                        head_is_good_candidate = True
                        break
                if head_is_good_candidate:
                    candidate = head
                    break
            if candidate is None:
                raise Exception("Failure to linearize profile hierarchy")
            # save candidate to merge
            merge.append(candidate)
            # remove candidate from all lists it appears in
            for i in range(len(merge_remaining)):
                if candidate in merge_remaining[i]:
                    merge_remaining[i].remove(candidate)
        return merge

    return helper(root)


if __name__ == "__main__":
    dep_tree: Dict[str, List[str]] = dict(
        a=[],
        b=["a"],
        c=["b", "a"],
    )

    print(c3_linearize(dep_tree, "c"))