X-Git-Url: https://git.distorted.org.uk/~mdw/termux-packages/blobdiff_plain/a8d10018d470dd14739257b04ec33e98de5df89e..f7690a8bbddec3a0b45bb8245db96ae8aaf3499a:/buildorder.py

diff --git a/buildorder.py b/buildorder.py
index 273a10d5..fa02f7a9 100755
--- a/buildorder.py
+++ b/buildorder.py
@@ -4,6 +4,28 @@
 import os
 import sys
 
+from itertools import filterfalse
+
+
+# https://docs.python.org/3/library/itertools.html#itertools-recipes
+
+def unique_everseen(iterable, key=None):
+    "List unique elements, preserving order. Remember all elements ever seen."
+    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
+    # unique_everseen('ABBCcAD', str.lower) --> A B C D
+    seen = set()
+    seen_add = seen.add
+    if key is None:
+        for element in filterfalse(seen.__contains__, iterable):
+            seen_add(element)
+            yield element
+    else:
+        for element in iterable:
+            k = key(element)
+            if k not in seen:
+                seen_add(k)
+                yield element
+
 
 def die(msg):
     sys.exit('ERROR: ' + msg)
@@ -132,7 +154,9 @@ def populate():
             dep_pkg.needed_by.add(pkg)
 
 
-def buildorder():
+def generate_full_buildorder():
+    build_order = []
+
     # List of all TermuxPackages without dependencies
     leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps]
 
@@ -144,36 +168,27 @@ def buildorder():
     pkg_queue = sorted(leaf_pkgs, key=lambda p: '' if p.name == 'libandroid-support' else p.name)
 
     # Topological sorting
-    build_order = []
     visited = set()
 
     while pkg_queue:
         pkg = pkg_queue.pop(0)
         if pkg.name in visited:
             continue
-        visited.add(pkg.name)
 
         # print("Processing {}:".format(pkg.name), pkg.needed_by)
-
+        visited.add(pkg.name)
         build_order.append(pkg)
 
         for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
-            # Mark this package as done
+            # Remove this pkg from deps
             remaining_deps[other_pkg.name].discard(pkg.name)
-
             # ... and all its subpackages
             remaining_deps[other_pkg.name].difference_update(
                 [subpkg.name for subpkg in pkg.subpkgs]
             )
 
-            if not remaining_deps[other_pkg.name]:  # all deps were pruned?
-                pkg_queue.append(other_pkg)
-
-    return build_order
-
-
-def generate_and_print_buildorder():
-    build_order = buildorder()
+            if not remaining_deps[other_pkg.name]:  # all deps were already appended?
+                pkg_queue.append(other_pkg)  # should be processed
 
     if set(pkgs_map.values()) != set(build_order):
         print("ERROR: Cycle exists. Remaining: ")
@@ -183,22 +198,34 @@ def generate_and_print_buildorder():
 
         sys.exit(1)
 
-    for pkg in build_order:
-        print(pkg.name)
+    return build_order
 
-    sys.exit(0)
 
+def deps_then_me(pkg):
+    l = []
 
-def print_after_deps_recursive(pkg):
     for dep in sorted(pkg.deps):
-        print_after_deps_recursive(pkgs_map[dep])
-    print(pkg.name)
+        l += deps_then_me(pkgs_map[dep])
+    l += [pkg]
+
+    return l
+
+
+def generate_targets_buildorder(targetnames):
+    buildorder = []
+
+    for pkgname in targetnames:
+        buildorder += deps_then_me(pkgs_map[pkgname])
+
+    return unique_everseen(buildorder)
 
 if __name__ == '__main__':
     populate()
 
     if len(sys.argv) == 1:
-        generate_and_print_buildorder()
+        bo = generate_full_buildorder()
+    else:
+        bo = generate_targets_buildorder(sys.argv[1:])
 
-    for target in sys.argv[1:]:
-        print_after_deps_recursive(pkgs_map[target])
+    for pkg in bo:
+        print(pkg.name)