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