| 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() |