chiark - git - mdw - termux-packages/blob - scripts/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 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
  35 class TermuxBuildFile(object):
  36     def __init__(self, path):
  37         self.path = path
  38
  39     def _get_dependencies(self):
  40         pkg_dep_prefix = 'TERMUX_PKG_DEPENDS='
  41         subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS='
  42
  43         with open(self.path) as f:
  44             prefix = None
  45             for line in f:
  46                 if line.startswith(pkg_dep_prefix):
  47                     prefix = pkg_dep_prefix
  48                 elif line.startswith(subpkg_dep_prefix):
  49                     prefix = subpkg_dep_prefix
  50                 else:
  51                     continue
  52
  53                 comma_deps = line[len(prefix):].replace('"', '').replace("'", '')
  54
  55                 return set([
  56                     # Replace parenthesis to handle version qualifiers, as in "gcc (>= 5.0)":
  57                     re.sub(r'\(.*?\)', '', dep).replace('-dev', '').strip() for dep in comma_deps.split(',')
  58                 ])
  59
  60         # no deps found
  61         return set()
  62
  63
  64 class TermuxPackage(object):
  65     PACKAGES_DIR = 'packages'
  66
  67     def __init__(self, name):
  68         self.name = name
  69         self.dir = os.path.join(self.PACKAGES_DIR, name)
  70
  71         # search package build.sh
  72         build_sh_path = os.path.join(self.dir, 'build.sh')
  73         if not os.path.isfile(build_sh_path):
  74             raise Exception("build.sh not found for package '" + name + "'")
  75
  76         self.buildfile = TermuxBuildFile(build_sh_path)
  77         self.deps = self.buildfile._get_dependencies()
  78         if 'libandroid-support' not in self.deps and self.name != 'libandroid-support':
  79             # Every package may depend on libandroid-support without declaring it:
  80             self.deps.add('libandroid-support')
  81
  82         # search subpackages
  83         self.subpkgs = []
  84
  85         for filename in os.listdir(self.dir):
  86             if not filename.endswith('.subpackage.sh'):
  87                 continue
  88
  89             subpkg_name = filename.split('.subpackage.sh')[0]
  90             subpkg = TermuxSubPackage(subpkg_name, parent=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()  # to be completed outside, reverse of    deps
 101
 102     def __repr__(self):
 103         return "<{} '{}'>".format(self.__class__.__name__, self.name)
 104
 105
 106 class TermuxSubPackage(TermuxPackage):
 107
 108     def __init__(self, name, parent=None):
 109         if parent is None:
 110             raise Exception("SubPackages should have a parent")
 111
 112         self.name = name
 113         self.parent = parent
 114         self.buildfile = TermuxBuildFile(os.path.join(self.parent.dir, name + '.subpackage.sh'))
 115         self.deps = self.buildfile._get_dependencies()
 116
 117     def __repr__(self):
 118         return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent)
 119
 120
 121 # Tracks non-visited deps for each package
 122 remaining_deps = {}
 123
 124 # Mapping from package name to TermuxPackage
 125 # (if subpackage, mapping from subpackage name to parent package)
 126 pkgs_map = {}
 127
 128 # Reverse dependencies
 129 pkg_depends_on = {}
 130
 131 PACKAGES_DIR = 'packages'
 132
 133
 134 def populate():
 135
 136     for pkgdir_name in sorted(os.listdir(PACKAGES_DIR)):
 137
 138         pkg = TermuxPackage(pkgdir_name)
 139
 140         pkgs_map[pkg.name] = pkg
 141
 142         for subpkg in pkg.subpkgs:
 143             pkgs_map[subpkg.name] = pkg
 144             remaining_deps[subpkg.name] = set(subpkg.deps)
 145
 146         remaining_deps[pkg.name] = set(pkg.deps)
 147
 148     all_pkg_names = set(pkgs_map.keys())
 149
 150     for name, pkg in pkgs_map.items():
 151         for dep_name in remaining_deps[name]:
 152             if dep_name not in all_pkg_names:
 153                 die('Package %s depends on non-existing package "%s"' % (
 154                  name, dep_name
 155                 ))
 156
 157             dep_pkg = pkgs_map[dep_name]
 158             dep_pkg.needed_by.add(pkg)
 159
 160
 161 def generate_full_buildorder():
 162     build_order = []
 163
 164     # List of all TermuxPackages without dependencies
 165     leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps]
 166
 167     if not leaf_pkgs:
 168         die('No package without dependencies - where to start?')
 169
 170     # Sort alphabetically:
 171     pkg_queue = sorted(leaf_pkgs, key=lambda p: p.name)
 172
 173     # Topological sorting
 174     visited = set()
 175
 176     while pkg_queue:
 177         pkg = pkg_queue.pop(0)
 178         if pkg.name in visited:
 179             continue
 180
 181         # print("Processing {}:".format(pkg.name), pkg.needed_by)
 182         visited.add(pkg.name)
 183         build_order.append(pkg)
 184
 185         for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
 186             # Remove this pkg from deps
 187             remaining_deps[other_pkg.name].discard(pkg.name)
 188             # ... and all its subpackages
 189             remaining_deps[other_pkg.name].difference_update(
 190                 [subpkg.name for subpkg in pkg.subpkgs]
 191             )
 192
 193             if not remaining_deps[other_pkg.name]:  # all deps were already appended?
 194                 pkg_queue.append(other_pkg)  # should be processed
 195
 196     if set(pkgs_map.values()) != set(build_order):
 197         print("ERROR: Cycle exists. Remaining: ")
 198         for name, pkg in pkgs_map.items():
 199             if pkg not in build_order:
 200                 print(name, remaining_deps[name])
 201
 202         sys.exit(1)
 203
 204     return build_order
 205
 206
 207 def deps_then_me(pkg):
 208     l = []
 209
 210     for dep in sorted(pkg.deps):
 211         l += deps_then_me(pkgs_map[dep])
 212     l += [pkg]
 213
 214     return l
 215
 216
 217 def generate_targets_buildorder(targetnames):
 218     buildorder = []
 219
 220     for pkgname in targetnames:
 221         buildorder += deps_then_me(pkgs_map[pkgname])
 222
 223     return unique_everseen(buildorder)
 224
 225 if __name__ == '__main__':
 226     populate()
 227
 228     if len(sys.argv) == 1:
 229         bo = generate_full_buildorder()
 230     else:
 231         bo = generate_targets_buildorder(sys.argv[1:])
 232
 233     for pkg in bo:
 234         print(pkg.name)