| 1 | #!/usr/bin/env python3 |
| 2 | # buildorder.py - 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 | # https://docs.python.org/3/library/itertools.html#itertools-recipes |
| 12 | |
| 13 | def unique_everseen(iterable, key=None): |
| 14 | "List unique elements, preserving order. Remember all elements ever seen." |
| 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 | sys.exit('ERROR: ' + msg) |
| 33 | |
| 34 | def rchop(thestring, ending): |
| 35 | if thestring.endswith(ending): |
| 36 | return thestring[:-len(ending)] |
| 37 | return thestring |
| 38 | |
| 39 | class TermuxBuildFile(object): |
| 40 | def __init__(self, path): |
| 41 | self.path = path |
| 42 | |
| 43 | def _get_dependencies(self): |
| 44 | pkg_dep_prefix = 'TERMUX_PKG_DEPENDS=' |
| 45 | pkg_build_dep_prefix = 'TERMUX_PKG_BUILD_DEPENDS=' |
| 46 | subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS=' |
| 47 | comma_deps = '' |
| 48 | |
| 49 | with open(self.path, encoding="utf-8") as f: |
| 50 | prefix = None |
| 51 | for line in f: |
| 52 | if line.startswith(pkg_dep_prefix): |
| 53 | prefix = pkg_dep_prefix |
| 54 | elif line.startswith(pkg_build_dep_prefix): |
| 55 | prefix = pkg_build_dep_prefix |
| 56 | elif line.startswith(subpkg_dep_prefix): |
| 57 | prefix = subpkg_dep_prefix |
| 58 | else: |
| 59 | continue |
| 60 | |
| 61 | comma_deps += line[len(prefix):].replace('"', '').replace("'", '').replace("\n", ",") |
| 62 | |
| 63 | # Remove trailing ',' that is otherwise replacing the final newline |
| 64 | comma_deps = comma_deps[:-1] |
| 65 | if not comma_deps: |
| 66 | # no deps found |
| 67 | return set() |
| 68 | |
| 69 | return set([ |
| 70 | # Replace parenthesis to handle version qualifiers, as in "gcc (>= 5.0)": |
| 71 | rchop(re.sub(r'\(.*?\)', '', dep).strip(), '-dev') for dep in comma_deps.split(',') |
| 72 | ]) |
| 73 | |
| 74 | |
| 75 | class TermuxPackage(object): |
| 76 | def __init__(self, dir_path): |
| 77 | self.dir = dir_path |
| 78 | self.name = os.path.basename(self.dir) |
| 79 | |
| 80 | # search package build.sh |
| 81 | build_sh_path = os.path.join(self.dir, 'build.sh') |
| 82 | if not os.path.isfile(build_sh_path): |
| 83 | raise Exception("build.sh not found for package '" + self.name + "'") |
| 84 | |
| 85 | self.buildfile = TermuxBuildFile(build_sh_path) |
| 86 | self.deps = self.buildfile._get_dependencies() |
| 87 | if 'libandroid-support' not in self.deps and self.name != 'libandroid-support': |
| 88 | # Every package may depend on libandroid-support without declaring it: |
| 89 | self.deps.add('libandroid-support') |
| 90 | |
| 91 | # search subpackages |
| 92 | self.subpkgs = [] |
| 93 | |
| 94 | for filename in os.listdir(self.dir): |
| 95 | if not filename.endswith('.subpackage.sh'): continue |
| 96 | subpkg = TermuxSubPackage(self.dir + '/' + filename, self) |
| 97 | |
| 98 | self.subpkgs.append(subpkg) |
| 99 | self.deps |= subpkg.deps |
| 100 | |
| 101 | # Do not depend on itself |
| 102 | self.deps.discard(self.name) |
| 103 | # Do not depend on any sub package |
| 104 | self.deps.difference_update([subpkg.name for subpkg in self.subpkgs]) |
| 105 | |
| 106 | self.needed_by = set() # to be completed outside, reverse of deps |
| 107 | |
| 108 | def __repr__(self): |
| 109 | return "<{} '{}'>".format(self.__class__.__name__, self.name) |
| 110 | |
| 111 | |
| 112 | class TermuxSubPackage(TermuxPackage): |
| 113 | def __init__(self, subpackage_file_path, parent): |
| 114 | if parent is None: |
| 115 | raise Exception("SubPackages should have a parent") |
| 116 | |
| 117 | self.buildfile = TermuxBuildFile(subpackage_file_path) |
| 118 | self.name = os.path.basename(subpackage_file_path).split('.subpackage.sh')[0] |
| 119 | self.parent = parent |
| 120 | self.deps = self.buildfile._get_dependencies() |
| 121 | |
| 122 | def __repr__(self): |
| 123 | return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent) |
| 124 | |
| 125 | |
| 126 | # Tracks non-visited deps for each package |
| 127 | remaining_deps = {} |
| 128 | |
| 129 | # Mapping from package name to TermuxPackage |
| 130 | # (if subpackage, mapping from subpackage name to parent package) |
| 131 | pkgs_map = {} |
| 132 | |
| 133 | # Reverse dependencies |
| 134 | pkg_depends_on = {} |
| 135 | |
| 136 | PACKAGES_DIRS = ['packages'] |
| 137 | |
| 138 | |
| 139 | def populate(): |
| 140 | all_packages = [] |
| 141 | for package_dir in PACKAGES_DIRS: |
| 142 | for pkgdir_name in sorted(os.listdir(package_dir)): |
| 143 | dir_path = package_dir + '/' + pkgdir_name |
| 144 | if os.path.isfile(dir_path + '/build.sh'): |
| 145 | all_packages.append(TermuxPackage(package_dir + '/' + pkgdir_name)) |
| 146 | |
| 147 | for pkg in all_packages: |
| 148 | if pkg.name in pkgs_map: die('Duplicated package: ' + pkg.name) |
| 149 | else: pkgs_map[pkg.name] = pkg |
| 150 | |
| 151 | for subpkg in pkg.subpkgs: |
| 152 | pkgs_map[subpkg.name] = pkg |
| 153 | remaining_deps[subpkg.name] = set(subpkg.deps) |
| 154 | |
| 155 | remaining_deps[pkg.name] = set(pkg.deps) |
| 156 | |
| 157 | all_pkg_names = set(pkgs_map.keys()) |
| 158 | |
| 159 | for name, pkg in pkgs_map.items(): |
| 160 | for dep_name in remaining_deps[name]: |
| 161 | if dep_name not in all_pkg_names: |
| 162 | die('Package %s depends on non-existing package "%s"' % ( |
| 163 | name, dep_name |
| 164 | )) |
| 165 | |
| 166 | dep_pkg = pkgs_map[dep_name] |
| 167 | dep_pkg.needed_by.add(pkg) |
| 168 | |
| 169 | |
| 170 | def generate_full_buildorder(): |
| 171 | build_order = [] |
| 172 | |
| 173 | # List of all TermuxPackages without dependencies |
| 174 | leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps] |
| 175 | |
| 176 | if not leaf_pkgs: |
| 177 | die('No package without dependencies - where to start?') |
| 178 | |
| 179 | # Sort alphabetically: |
| 180 | pkg_queue = sorted(leaf_pkgs, key=lambda p: p.name) |
| 181 | |
| 182 | # Topological sorting |
| 183 | visited = set() |
| 184 | |
| 185 | while pkg_queue: |
| 186 | pkg = pkg_queue.pop(0) |
| 187 | if pkg.name in visited: |
| 188 | continue |
| 189 | |
| 190 | # print("Processing {}:".format(pkg.name), pkg.needed_by) |
| 191 | visited.add(pkg.name) |
| 192 | build_order.append(pkg) |
| 193 | |
| 194 | for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name): |
| 195 | # Remove this pkg from deps |
| 196 | remaining_deps[other_pkg.name].discard(pkg.name) |
| 197 | # ... and all its subpackages |
| 198 | remaining_deps[other_pkg.name].difference_update( |
| 199 | [subpkg.name for subpkg in pkg.subpkgs] |
| 200 | ) |
| 201 | |
| 202 | if not remaining_deps[other_pkg.name]: # all deps were already appended? |
| 203 | pkg_queue.append(other_pkg) # should be processed |
| 204 | |
| 205 | if set(pkgs_map.values()) != set(build_order): |
| 206 | print("ERROR: Cycle exists. Remaining: ") |
| 207 | for name, pkg in pkgs_map.items(): |
| 208 | if pkg not in build_order: |
| 209 | print(name, remaining_deps[name]) |
| 210 | |
| 211 | sys.exit(1) |
| 212 | |
| 213 | return build_order |
| 214 | |
| 215 | def deps(pkg): |
| 216 | l = [] |
| 217 | for dep in sorted(pkg.deps): |
| 218 | l += deps_then_me(pkgs_map[dep]) |
| 219 | return l |
| 220 | |
| 221 | def deps_then_me(pkg): |
| 222 | l = [] |
| 223 | for dep in sorted(pkg.deps): |
| 224 | l += deps_then_me(pkgs_map[dep]) |
| 225 | l += [pkg] |
| 226 | return l |
| 227 | |
| 228 | |
| 229 | def generate_targets_buildorder(target_paths): |
| 230 | buildorder = [] |
| 231 | |
| 232 | for target_path in target_paths: |
| 233 | if target_path.endswith('/'): target_path = target_path[:-1] |
| 234 | pkgname = os.path.basename(target_path) |
| 235 | if not pkgname in pkgs_map: |
| 236 | die('Dependencies for ' + pkgname + ' could not be calculated (skip dependency check with -s)') |
| 237 | buildorder += deps(pkgs_map[pkgname]) |
| 238 | |
| 239 | return unique_everseen(buildorder) |
| 240 | |
| 241 | if __name__ == '__main__': |
| 242 | full_buildorder = len(sys.argv) == 1 |
| 243 | if not full_buildorder: |
| 244 | packages_real_path = os.path.realpath('packages') |
| 245 | for path in sys.argv[1:]: |
| 246 | if not os.path.isdir(path): |
| 247 | die('Not a directory: ' + path) |
| 248 | if path.endswith('/'): path = path[:-1] |
| 249 | parent_path = os.path.dirname(path) |
| 250 | if packages_real_path != os.path.realpath(parent_path): |
| 251 | PACKAGES_DIRS.append(parent_path) |
| 252 | |
| 253 | populate() |
| 254 | |
| 255 | if full_buildorder: |
| 256 | bo = generate_full_buildorder() |
| 257 | else: |
| 258 | bo = generate_targets_buildorder(sys.argv[1:]) |
| 259 | |
| 260 | for pkg in bo: |
| 261 | print(pkg.dir) |