depsort.py

#! /usr/bin/env python2

import argparse
import sys

class Graph(object):
    def __init__(self):
        # `graph`: dict that maps each package to a set of its dependencies.
        self.graph = {}

    def add(self, dependent, dependency):
        """Add a dependency relationship to the graph"""
        self.graph.setdefault(dependent, set())
        self.graph.setdefault(dependency, set())
        if dependent != dependency:
            self.graph[dependent].add(dependency)

    def add_optional(self, dependent, dependency):
        """Add an optional (ordering only) dependency relationship to the graph

        Only call this after all mandatory requirements are added
        """
        if dependent in self.graph and dependency in self.graph:
            self.add(dependent, dependency)

    def find_order(self):
        """Do a topological sort on a dependency graph

        :Parameters:
            :Returns:
                iterator, sorted items form first to last
        """
        graph = dict((k, set(v)) for k, v in self.graph.items())
        while graph:
            # Find all items without a parent
            leftmost = [l for l, s in graph.items() if not s]
            if not leftmost:
                raise ValueError('Dependency cycle detected! %s' % graph)
            # If there is more than one, sort them for predictable order
            leftmost.sort()
            for result in leftmost:
                # Yield and remove them from the graph
                yield result
                graph.pop(result)
                for bset in graph.values():
                    bset.discard(result)


def lines_to_relationships(lines):
    """Do a topological sort from a list of space-separated lines

    :Parameters:
        `lines`: Iterable of lines in the format
            "dependent dependency_0 dependency_1 ... dependency_n"

    :Returns:
        iterator of (dependent, dependency) tuples
    """
    for line in lines:
        line = line.split()
        if line:
            dependent = line[0]
            for dependency in line:
                yield dependent, dependency


def topo_sort_lines(lines, lines_optional=()):
    """Do a topological sort from a list of space-separated lines

    :Parameters:
        `lines`: Iterable of lines in the format
            "dependent dependency_0 dependency_1 ... dependency_n"

        `lines`: Iterable of lines with *optional* (ordering-only) dependencies
            "dependent dependency_0 dependency_1 ... dependency_n"

    :Returns:
        string, Sorted dependencies, space-separated
    """
    graph = Graph()
    for dependent, dependency in lines_to_relationships(lines):
        graph.add(dependent, dependency)
    for dependent, dependency in lines_to_relationships(lines_optional):
        graph.add_optional(dependent, dependency)
    return ' '.join(graph.find_order())


def test_depsort_1():
    lines = [
        'c a',
        'b c',
        'd b',
        'w z',
        'a w',
    ]
    assert topo_sort_lines(lines) == 'z w a c b d'


def test_depsort_2():
    lines = [
        'l k',
        'm l',
        'a k',
        'd a',
        'l d',
        's l',
        'm s',
    ]
    assert topo_sort_lines(lines) == 'k a d l s m'


def test_depsort_3():
    lines = [
        'z a',
        's z',
        'z z',
        's s',
    ]
    assert topo_sort_lines(lines) == 'a z s'


def test_depsort_4():
    lines = [
        'f d',
        'g f',
        'r f',
        't r',
        'y t',
        'g y',
    ]
    assert topo_sort_lines(lines) == 'd f r t y g'


def test_depsort_5():
    lines = [
        'a b c d e f',
        'e f',
        'g',
    ]
    assert topo_sort_lines(lines) == 'b c d f g e a'


def test_depsort_6():
    lines = [
        ' numpy python ',
        ' kivy pygame pyjnius android ',
        ' python hostpython ',
        ' pygame sdl ',
        ' android pygame ',
        ' pyjnius python ',
        ' sdl python ',
        ' hostpython ',
    ]
    assert topo_sort_lines(lines) == (
        'hostpython python numpy pyjnius sdl pygame android kivy')


def test_depsort_optional_1():
    lines = [' myapp openssl python ']
    optional = ['python openssl']
    assert topo_sort_lines(lines, optional) == 'openssl python myapp'


def test_depsort_optional_2():
    lines = [' myapp openssl python ']
    # Just for testing purposes, make openssl soft-depend on python
    optional = ['openssl python']
    assert topo_sort_lines(lines, optional) == 'python openssl myapp'


def test_depsort_optional_3():
    lines = ['myapp openssl']
    optional = ['python openssl']
    assert topo_sort_lines(lines, optional) == 'openssl myapp'


def test_depsort_optional_4():
    lines = ['myapp python']
    optional = ['python openssl']
    assert topo_sort_lines(lines, optional) == 'python myapp'


def test_depsort_optional_4():
    lines = ['myapp']
    optional = ['python openssl']
    assert topo_sort_lines(lines, optional) == 'myapp'


def main(argv):
    parser = argparse.ArgumentParser(
        description="Sort dependencies given on standard input")
    parser.add_argument('--optional', type=argparse.FileType('r'),
                        help='File with optional (ordering-only) dependencies')
    args = parser.parse_args(argv[1:])
    return topo_sort_lines(sys.stdin, lines_optional=args.optional or [])


if __name__ == '__main__':
    print main(sys.argv)