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