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