chiark - git - mdw - termux-packages/blob - scripts/buildorder.py

   1 #!/usr/bin/env python3
   2 "Script to generate a build order respecting package dependencies."
   3
   4 import os
   5 import re
   6 import sys
   7
   8 from itertools import filterfalse
   9
  10 def unique_everseen(iterable, key=None):
  11     """List unique elements, preserving order. Remember all elements ever seen.
  12     See https://docs.python.org/3/library/itertools.html#itertools-recipes
  13     Examples:
  14     unique_everseen('AAAABBBCCDAABBB') --> A B C D
  15     unique_everseen('ABBCcAD', str.lower) --> A B C D"""
  16     seen = set()
  17     seen_add = seen.add
  18     if key is None:
  19         for element in filterfalse(seen.__contains__, iterable):
  20             seen_add(element)
  21             yield element
  22     else:
  23         for element in iterable:
  24             k = key(element)
  25             if k not in seen:
  26                 seen_add(k)
  27                 yield element
  28
  29 def die(msg):
  30     "Exit the process with an error message."
  31     sys.exit('ERROR: ' + msg)
  32
  33 def parse_build_file_dependencies(path):
  34     "Extract the dependencies of a build.sh or *.subpackage.sh file."
  35     pkg_dep_prefix = 'TERMUX_PKG_DEPENDS='
  36     pkg_build_dep_prefix = 'TERMUX_PKG_BUILD_DEPENDS='
  37     subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS='
  38     dependencies = []
  39
  40     with open(path, encoding="utf-8") as build_script:
  41         prefix = None
  42         for line in build_script:
  43             if line.startswith(pkg_dep_prefix):
  44                 prefix = pkg_dep_prefix
  45             elif line.startswith(pkg_build_dep_prefix):
  46                 prefix = pkg_build_dep_prefix
  47             elif line.startswith(subpkg_dep_prefix):
  48                 prefix = subpkg_dep_prefix
  49             else:
  50                 continue
  51
  52             dependencies_string = line[len(prefix):]
  53             for char in "\"'\n":
  54                 dependencies_string = dependencies_string.replace(char, '')
  55
  56             for dependency_value in dependencies_string.split(','):
  57                 # Replace parenthesis to ignore version qualifiers as in "gcc (>= 5.0)":
  58                 dependency_value = re.sub(r'\(.*?\)', '', dependency_value).strip()
  59                 dependency_value = re.sub('-dev$', '', dependency_value)
  60                 dependencies.append(dependency_value)
  61
  62     return set(dependencies)
  63
  64 class TermuxPackage(object):
  65     "A main package definition represented by a directory with a build.sh file."
  66     def __init__(self, dir_path):
  67         self.dir = dir_path
  68         self.name = os.path.basename(self.dir)
  69
  70         # search package build.sh
  71         build_sh_path = os.path.join(self.dir, 'build.sh')
  72         if not os.path.isfile(build_sh_path):
  73             raise Exception("build.sh not found for package '" + self.name + "'")
  74
  75         self.deps = parse_build_file_dependencies(build_sh_path)
  76         if 'libandroid-support' not in self.deps and self.name != 'libandroid-support':
  77             # Every package may depend on libandroid-support without declaring it:
  78             self.deps.add('libandroid-support')
  79
  80         # search subpackages
  81         self.subpkgs = []
  82
  83         for filename in os.listdir(self.dir):
  84             if not filename.endswith('.subpackage.sh'):
  85                 continue
  86             subpkg = TermuxSubPackage(self.dir + '/' + filename, self)
  87
  88             self.subpkgs.append(subpkg)
  89             self.deps |= subpkg.deps
  90
  91         # Do not depend on itself
  92         self.deps.discard(self.name)
  93         # Do not depend on any sub package
  94         self.deps.difference_update([subpkg.name for subpkg in self.subpkgs])
  95
  96         self.needed_by = set()  # Populated outside constructor, reverse of deps.
  97
  98     def __repr__(self):
  99         return "<{} '{}'>".format(self.__class__.__name__, self.name)
 100
 101     def recursive_dependencies(self, pkgs_map):
 102         "All the dependencies of the package, both direct and indirect."
 103         result = []
 104         for dependency_name in sorted(self.deps):
 105             dependency_package = pkgs_map[dependency_name]
 106             result += dependency_package.recursive_dependencies(pkgs_map)
 107             result += [dependency_package]
 108         return unique_everseen(result)
 109
 110 class TermuxSubPackage:
 111     "A sub-package represented by a ${PACKAGE_NAME}.subpackage.sh file."
 112     def __init__(self, subpackage_file_path, parent):
 113         if parent is None:
 114             raise Exception("SubPackages should have a parent")
 115
 116         self.name = os.path.basename(subpackage_file_path).split('.subpackage.sh')[0]
 117         self.parent = parent
 118         self.deps = parse_build_file_dependencies(subpackage_file_path)
 119
 120     def __repr__(self):
 121         return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent)
 122
 123 def read_packages_from_directories(directories):
 124     """Construct a map from package name to TermuxPackage.
 125     For subpackages this maps from the subpackage name to the parent package."""
 126     pkgs_map = {}
 127     all_packages = []
 128
 129     for package_dir in directories:
 130         for pkgdir_name in sorted(os.listdir(package_dir)):
 131             dir_path = package_dir + '/' + pkgdir_name
 132             if os.path.isfile(dir_path + '/build.sh'):
 133                 new_package = TermuxPackage(package_dir + '/' + pkgdir_name)
 134
 135                 if new_package.name in pkgs_map:
 136                     die('Duplicated package: ' + new_package.name)
 137                 else:
 138                     pkgs_map[new_package.name] = new_package
 139                 all_packages.append(new_package)
 140
 141                 for subpkg in new_package.subpkgs:
 142                     if subpkg.name in pkgs_map:
 143                         die('Duplicated package: ' + subpkg.name)
 144                     else:
 145                         pkgs_map[subpkg.name] = new_package
 146                     all_packages.append(subpkg)
 147
 148     for pkg in all_packages:
 149         for dependency_name in pkg.deps:
 150             if dependency_name not in pkgs_map:
 151                 die('Package %s depends on non-existing package "%s"' % (pkg.name, dependency_name))
 152             dep_pkg = pkgs_map[dependency_name]
 153             if not isinstance(pkg, TermuxSubPackage):
 154                 dep_pkg.needed_by.add(pkg)
 155     return pkgs_map
 156
 157 def generate_full_buildorder(pkgs_map):
 158     "Generate a build order for building all packages."
 159     build_order = []
 160
 161     # List of all TermuxPackages without dependencies
 162     leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps]
 163
 164     if not leaf_pkgs:
 165         die('No package without dependencies - where to start?')
 166
 167     # Sort alphabetically:
 168     pkg_queue = sorted(leaf_pkgs, key=lambda p: p.name)
 169
 170     # Topological sorting
 171     visited = set()
 172
 173     # Tracks non-visited deps for each package
 174     remaining_deps = {}
 175     for name, pkg in pkgs_map.items():
 176         remaining_deps[name] = set(pkg.deps)
 177         for subpkg in pkg.subpkgs:
 178             remaining_deps[subpkg.name] = set(subpkg.deps)
 179
 180     while pkg_queue:
 181         pkg = pkg_queue.pop(0)
 182         if pkg.name in visited:
 183             continue
 184
 185         # print("Processing {}:".format(pkg.name), pkg.needed_by)
 186         visited.add(pkg.name)
 187         build_order.append(pkg)
 188
 189         for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
 190             # Remove this pkg from deps
 191             remaining_deps[other_pkg.name].discard(pkg.name)
 192             # ... and all its subpackages
 193             remaining_deps[other_pkg.name].difference_update(
 194                 [subpkg.name for subpkg in pkg.subpkgs]
 195             )
 196
 197             if not remaining_deps[other_pkg.name]:  # all deps were already appended?
 198                 pkg_queue.append(other_pkg)  # should be processed
 199
 200     if set(pkgs_map.values()) != set(build_order):
 201         print("ERROR: Cycle exists. Remaining: ")
 202         for name, pkg in pkgs_map.items():
 203             if pkg not in build_order:
 204                 print(name, remaining_deps[name])
 205
 206         sys.exit(1)
 207
 208     return build_order
 209
 210 def generate_target_buildorder(target_path, pkgs_map):
 211     "Generate a build order for building the dependencies of the specified package."
 212     if target_path.endswith('/'):
 213         target_path = target_path[:-1]
 214
 215     package_name = os.path.basename(target_path)
 216     package = pkgs_map[package_name]
 217     return package.recursive_dependencies(pkgs_map)
 218
 219 def main():
 220     "Generate the build order either for all packages or a specific one."
 221     packages_directories = ['packages']
 222     full_buildorder = len(sys.argv) == 1
 223     if not full_buildorder:
 224         packages_real_path = os.path.realpath('packages')
 225         for path in sys.argv[1:]:
 226             if not os.path.isdir(path):
 227                 die('Not a directory: ' + path)
 228             if path.endswith('/'):
 229                 path = path[:-1]
 230             parent_path = os.path.dirname(path)
 231             if packages_real_path != os.path.realpath(parent_path):
 232                 packages_directories.append(parent_path)
 233
 234     pkgs_map = read_packages_from_directories(packages_directories)
 235
 236     if full_buildorder:
 237         build_order = generate_full_buildorder(pkgs_map)
 238     else:
 239         build_order = generate_target_buildorder(sys.argv[1], pkgs_map)
 240
 241     for pkg in build_order:
 242         print(pkg.dir)
 243
 244 if __name__ == '__main__':
 245     main()