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