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