Merge pull request kivy#134 from encukou/depsolving

tito · tito · commit 0fdf735c25a5 · 2013-07-06T07:05:06.000-07:00
WIP: Add depsolving utility
diff --git a/depsort.py b/depsort.py
@@ -0,0 +1,199 @@
+#! /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)
