Trivial dependency sorter (Python)

deps-sort.py

## deps-sort.py
## trivial dependency sort with stateful loop detection

class SortState():
    def __init__(self, origin):
        self._origin = origin
        self._cache = []

    @property
    def origin(self):
        return self._origin

    def append(self, item):
        self._cache.append(item)

    def cached_p(self, item) -> bool:
        return item in self._cache

    def __repr__(self):
        return "<%s (%s) %x>" % (self.__class__.__name__, self.origin, id(self))


def sort_one(item: str, whence: dict, state = None) -> list[str]:
    if state is None:
        state = SortState(item)
    else:
        state.append(item)
    for dep in whence[item]:
        if dep == item:
            raise RuntimeError(f"Circular dependency: {item} <=> {item}", state)
        elif dep == state.origin:
            raise RuntimeError(f"Circular transitive dependency {dep} <=> {item}", state)
        elif not state.cached_p(item):
            for nxt in sort_one(dep, whence, state):
                state.append(nxt)
                yield nxt
            yield dep


def sort_deps(whence: dict):
    for item in whence.keys():
        yield (*(dep for dep in sort_one(item, whence)), item)

print("Test dependency graph")

data = dict(a = ['b', 'c'],
            b = ['c', 'd'],
            c = ['d'],
            d = [])

for d in sort_deps(data):
    print(d)

print("Test circular dependency 1")

circ_data_a = dict(a = ['b', 'a', 'c'],
                   b = ['c', 'd'],
                   c = ['d'],
                   d = [])

try:
    for d in sort_deps(circ_data_a):
        print(d)
except RuntimeError as e:
    print("%s" % e)

print("Test circular dependency 2")

circ_data_b = dict(a = ['b', 'c'],
                   b = ['c', 'd'],
                   c = ['a'],
                   d = [])

try:
    for d in sort_deps(circ_data_b):
        print(d)
except RuntimeError as e:
    print("%s" % e)

## example output:
# Test dependency graph
# ('b', 'c', 'a')
# ('c', 'd', 'b')
# ('d', 'c')
# ('d',)
# Test circular dependency 1
# ('Circular dependency: a <=> a', <SortState (a) 82b0c1190>)
# Test circular dependency 2
# ('Circular transitive dependency a <=> c', <SortState (a) 82b0c1d10>)

The type signatures might be a little off, in this version. A generator is not a list[str]