def topo_sort(revisions):
    """revisions: dict id -> parents"""

    done = set()
    remaining = set(revisions)

    set_revisions = {
        rev: (set(parents), parents)
        for rev, parents in revisions.items()
    }

    while remaining:
        for rev in remaining.copy():
            set_parents, parents = set_revisions[rev]
            if set_parents <= done:
                yield (rev, parents)
                done.add(rev)
                remaining.remove(rev)