| 1 | #!/usr/bin/env python3 |
| 2 | # buildorder.py - script to generate a build order respecting package dependencies |
| 3 | |
| 4 | import os, sys |
| 5 | |
| 6 | def die(msg): |
| 7 | print('ERROR: ' + msg) |
| 8 | sys.exit(1) |
| 9 | |
| 10 | if len(sys.argv) != 1: die('buildorder.py takes no arguments') |
| 11 | packages_dir = 'packages' |
| 12 | |
| 13 | class DebianPackage: |
| 14 | def __init__(self, name): |
| 15 | self.name = name |
| 16 | self.remaining_dependencies = set() # String |
| 17 | self.sub_packages = set() # String |
| 18 | self.prerequisite_for = set() # Packages that needs this package |
| 19 | |
| 20 | all_packages = [] # List of all DebianPackage:s |
| 21 | packages_map = {} # Mapping from package name to DebianPackage (if subpackage, mapping from subpackage name to parent package) |
| 22 | |
| 23 | for subdir_name in sorted(os.listdir(packages_dir)): |
| 24 | subdir_path = packages_dir + '/' + subdir_name |
| 25 | if os.path.exists(subdir_path + '/BROKEN.txt'): continue |
| 26 | build_sh_path = subdir_path + '/build.sh' |
| 27 | |
| 28 | this_package = DebianPackage(subdir_name) |
| 29 | all_packages.append(this_package) |
| 30 | packages_map[this_package.name] = this_package |
| 31 | |
| 32 | if not os.path.isfile(build_sh_path): die('The directory ' + subdir_name + ' does not contain build.sh') |
| 33 | with open(build_sh_path) as build_sh_file: |
| 34 | for line in build_sh_file: |
| 35 | if line.startswith('TERMUX_PKG_DEPENDS='): |
| 36 | deps_comma_separated = line[(line.index('=')+2):(len(line)-2)] |
| 37 | for dep in deps_comma_separated.split(','): |
| 38 | dep = dep.strip() |
| 39 | this_package.remaining_dependencies.add(dep) |
| 40 | for file_in_subdir_name in sorted(os.listdir(subdir_path)): |
| 41 | if file_in_subdir_name.endswith('.subpackage.sh'): |
| 42 | subpackage_name = file_in_subdir_name[0:-len(".subpackage.sh"):] |
| 43 | this_package.sub_packages.add(subpackage_name) |
| 44 | packages_map[subpackage_name] = this_package |
| 45 | with open(subdir_path + '/' + file_in_subdir_name) as subpackage_sh_file: |
| 46 | for line in subpackage_sh_file: |
| 47 | if line.startswith('TERMUX_SUBPKG_DEPENDS='): |
| 48 | deps_comma_separated = line[(line.index('=')+2):(len(line)-2)] |
| 49 | for dep in deps_comma_separated.split(','): |
| 50 | dep = dep.strip() |
| 51 | this_package.remaining_dependencies.add(dep) |
| 52 | this_package.remaining_dependencies.discard(this_package.name) # Do not depend on itself |
| 53 | this_package.remaining_dependencies.difference_update(this_package.sub_packages) # Do not depend on any sub package |
| 54 | |
| 55 | for package in all_packages: |
| 56 | for remaining in package.remaining_dependencies: |
| 57 | if not remaining in packages_map: die('Package ' + package.name + ' depends on non-existing package "' + remaining + '"') |
| 58 | packages_map[remaining].prerequisite_for.add(package) |
| 59 | |
| 60 | # List of all DebianPackage:s without dependencies |
| 61 | packages_without_deps = [p for p in all_packages if not p.remaining_dependencies] |
| 62 | if not packages_without_deps: die('No package without dependency - where to start?') |
| 63 | |
| 64 | # Sort alphabetically, but with libandroid-support first (since dependency on libandroid-support |
| 65 | # does not need to be declared explicitly, so anything might in theory depend on it to build): |
| 66 | packages_without_deps.sort(key=lambda p: 'aaaa' if p.name == 'libandroid-support' else p.name, reverse=True) |
| 67 | |
| 68 | # Topological sorting |
| 69 | build_order = [] |
| 70 | while packages_without_deps: |
| 71 | pkg = packages_without_deps.pop() |
| 72 | build_order.append(pkg) |
| 73 | for other_package in pkg.prerequisite_for: |
| 74 | other_package.remaining_dependencies.discard(pkg.name) # Remove this package |
| 75 | other_package.remaining_dependencies.difference_update(pkg.sub_packages) # .. and all its subpackages |
| 76 | if not other_package.remaining_dependencies: |
| 77 | # Check if the other package is ready to build now |
| 78 | packages_without_deps.append(other_package) |
| 79 | |
| 80 | if len(all_packages) != len(build_order): |
| 81 | print("ERROR: Cycle exists. Remaining: "); |
| 82 | for pkg in all_packages: |
| 83 | if pkg not in build_order: print(pkg.name) |
| 84 | sys.exit(1) |
| 85 | |
| 86 | for pkg in build_order: print(pkg.name) |
| 87 | |