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