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

   1 #!/usr/bin/env python3
   2 # buildorder.py - script to generate a build order respecting package dependencies
   3
   4 import os
   5 import sys
   6
   7
   8 def die(msg):
   9     sys.exit('ERROR: ' + msg)
  10
  11
  12 class TermuxBuildFile(object):
  13     def __init__(self, path):
  14         self.path = path
  15
  16     def _get_dependencies(self):
  17         pkg_dep_prefix = 'TERMUX_PKG_DEPENDS='
  18         subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS='
  19
  20         with open(self.path) as f:
  21             prefix = None
  22             for line in f:
  23                 if line.startswith(pkg_dep_prefix):
  24                     prefix = pkg_dep_prefix
  25                 elif line.startswith(subpkg_dep_prefix):
  26                     prefix = subpkg_dep_prefix
  27                 else:
  28                     continue
  29
  30                 comma_deps = line[len(prefix):].replace('"', '')
  31
  32                 return set([
  33                     dep.strip() for dep in comma_deps.split(',')
  34                     if 'libandroid-support' not in dep
  35                 ])
  36
  37         # no deps found
  38         return set()
  39
  40
  41 class TermuxPackage(object):
  42     PACKAGES_DIR = 'packages'
  43
  44     def __init__(self, name):
  45         self.name = name
  46         self.dir = os.path.join(self.PACKAGES_DIR, name)
  47
  48         # search package build.sh
  49         build_sh_path = os.path.join(self.dir, 'build.sh')
  50         if not os.path.isfile(build_sh_path):
  51             raise Exception("build.sh not found")
  52
  53         self.buildfile = TermuxBuildFile(build_sh_path)
  54         self.deps = self.buildfile._get_dependencies()
  55
  56         # search subpackages
  57         self.subpkgs = []
  58
  59         for filename in os.listdir(self.dir):
  60             if not filename.endswith('.subpackage.sh'):
  61                 continue
  62
  63             subpkg_name = filename.split('.subpackage.sh')[0]
  64             subpkg = TermuxSubPackage(subpkg_name, parent=self)
  65
  66             self.subpkgs.append(subpkg)
  67             self.deps |= subpkg.deps
  68
  69         # Do not depend on itself
  70         self.deps.discard(self.name)
  71         # Do not depend on any sub package
  72         self.deps.difference_update([subpkg.name for subpkg in self.subpkgs])
  73
  74         self.needed_by = set()  # to be completed outside, reverse of    deps
  75
  76     def __repr__(self):
  77         return "<{} '{}'>".format(self.__class__.__name__, self.name)
  78
  79
  80 class TermuxSubPackage(TermuxPackage):
  81
  82     def __init__(self, name, parent=None):
  83         if parent is None:
  84             raise Exception("SubPackages should have a parent")
  85
  86         self.name = name
  87         self.parent = parent
  88         self.buildfile = TermuxBuildFile(os.path.join(self.parent.dir, name + '.subpackage.sh'))
  89         self.deps = self.buildfile._get_dependencies()
  90
  91     def __repr__(self):
  92         return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent)
  93
  94
  95 # Tracks non-visited deps for each package
  96 remaining_deps = {}
  97
  98 # Mapping from package name to TermuxPackage
  99 # (if subpackage, mapping from subpackage name to parent package)
 100 pkgs_map = {}
 101
 102 # Reverse dependencies
 103 pkg_depends_on = {}
 104
 105 PACKAGES_DIR = 'packages'
 106
 107
 108 def populate():
 109
 110     for pkgdir_name in sorted(os.listdir(PACKAGES_DIR)):
 111
 112         pkg = TermuxPackage(pkgdir_name)
 113
 114         pkgs_map[pkg.name] = pkg
 115
 116         for subpkg in pkg.subpkgs:
 117             pkgs_map[subpkg.name] = pkg
 118             remaining_deps[subpkg.name] = set(subpkg.deps)
 119
 120         remaining_deps[pkg.name] = set(pkg.deps)
 121
 122     all_pkg_names = set(pkgs_map.keys())
 123
 124     for name, pkg in pkgs_map.items():
 125         for dep_name in remaining_deps[name]:
 126             if dep_name not in all_pkg_names:
 127                 die('Package %s depends on non-existing package "%s"' % (
 128                  name, dep_name
 129                 ))
 130
 131             dep_pkg = pkgs_map[dep_name]
 132             dep_pkg.needed_by.add(pkg)
 133
 134
 135 def buildorder():
 136     # List of all TermuxPackages without dependencies
 137     leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps]
 138
 139     if not leaf_pkgs:
 140         die('No package without dependencies - where to start?')
 141
 142     # Sort alphabetically, but with libandroid-support first (since dependency on libandroid-support
 143     # does not need to be declared explicitly, so anything might in theory depend on it to build):
 144     pkg_queue = sorted(leaf_pkgs, key=lambda p: '' if p.name == 'libandroid-support' else p.name)
 145
 146     # Topological sorting
 147     build_order = []
 148     visited = set()
 149
 150     while pkg_queue:
 151         pkg = pkg_queue.pop(0)
 152         if pkg.name in visited:
 153             continue
 154
 155         # print("Processing {}:".format(pkg.name), pkg.needed_by)
 156         visited.add(pkg.name)
 157         build_order.append(pkg)
 158
 159         for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
 160             # Remove this pkg from deps
 161             remaining_deps[other_pkg.name].discard(pkg.name)
 162             # ... and all its subpackages
 163             remaining_deps[other_pkg.name].difference_update(
 164                 [subpkg.name for subpkg in pkg.subpkgs]
 165             )
 166
 167             if not remaining_deps[other_pkg.name]:  # all deps were already appended?
 168                 pkg_queue.append(other_pkg)  # should be processed
 169
 170     return build_order
 171
 172
 173 def generate_and_print_buildorder():
 174     build_order = buildorder()
 175
 176     if set(pkgs_map.values()) != set(build_order):
 177         print("ERROR: Cycle exists. Remaining: ")
 178         for name, pkg in pkgs_map.items():
 179             if pkg not in build_order:
 180                 print(name, remaining_deps[name])
 181
 182         sys.exit(1)
 183
 184     for pkg in build_order:
 185         print(pkg.name)
 186
 187     sys.exit(0)
 188
 189
 190 def print_after_deps_recursive(pkg):
 191     for dep in sorted(pkg.deps):
 192         print_after_deps_recursive(pkgs_map[dep])
 193     print(pkg.name)
 194
 195 if __name__ == '__main__':
 196     populate()
 197
 198     if len(sys.argv) == 1:
 199         generate_and_print_buildorder()
 200
 201     for target in sys.argv[1:]:
 202         print_after_deps_recursive(pkgs_map[target])