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