chiark - git - mdw - termux-packages/blob - 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 sys
   6
   7
   8 def die(msg):
   9     sys.exit('ERROR: ' + msg)
  10
  11
  12 if len(sys.argv) != 1:
  13     die('buildorder.py takes no arguments')
  14
  15
  16 class TermuxBuildFile(object):
  17     def __init__(self, path):
  18         self.path = path
  19
  20     def _get_dependencies(self):
  21         pkg_dep_prefix = 'TERMUX_PKG_DEPENDS='
  22         subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS='
  23
  24         with open(self.path) as f:
  25             prefix = None
  26             for line in f:
  27                 if line.startswith(pkg_dep_prefix):
  28                     prefix = pkg_dep_prefix
  29                 elif line.startswith(subpkg_dep_prefix):
  30                     prefix = subpkg_dep_prefix
  31                 else:
  32                     continue
  33
  34                 comma_deps = line[len(prefix):].replace('"', '')
  35
  36                 return set([
  37                     dep.strip() for dep in comma_deps.split(',')
  38                     if 'libandroid-support' not in dep
  39                 ])
  40
  41         # no deps found
  42         return set()
  43
  44
  45 class TermuxPackage(object):
  46     PACKAGES_DIR = 'packages'
  47
  48     def __init__(self, name):
  49         self.name = name
  50         self.dir = os.path.join(self.PACKAGES_DIR, name)
  51
  52         # search package build.sh
  53         build_sh_path = os.path.join(self.dir, 'build.sh')
  54         if not os.path.isfile(build_sh_path):
  55             raise Exception("build.sh not found")
  56
  57         self.buildfile = TermuxBuildFile(build_sh_path)
  58         self.deps = self.buildfile._get_dependencies()
  59
  60         # search subpackages
  61         self.subpkgs = []
  62
  63         for filename in os.listdir(self.dir):
  64             if not filename.endswith('.subpackage.sh'):
  65                 continue
  66
  67             subpkg_name = filename.split('.subpackage.sh')[0]
  68             subpkg = TermuxSubPackage(subpkg_name, parent=self)
  69
  70             self.subpkgs.append(subpkg)
  71             self.deps |= subpkg.deps
  72
  73         # Do not depend on itself
  74         self.deps.discard(self.name)
  75         # Do not depend on any sub package
  76         self.deps.difference_update([subpkg.name for subpkg in self.subpkgs])
  77
  78         self.needed_by = set()  # to be completed outside, reverse of    deps
  79
  80     def __repr__(self):
  81         return "<{} '{}'>".format(self.__class__.__name__, self.name)
  82
  83
  84 class TermuxSubPackage(TermuxPackage):
  85
  86     def __init__(self, name, parent=None):
  87         if parent is None:
  88             raise Exception("SubPackages should have a parent")
  89
  90         self.name = name
  91         self.parent = parent
  92         self.buildfile = TermuxBuildFile(os.path.join(self.parent.dir, name + '.subpackage.sh'))
  93         self.deps = self.buildfile._get_dependencies()
  94
  95     def __repr__(self):
  96         return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent)
  97
  98
  99 # Tracks non-visited deps for each package
 100 remaining_deps = {}
 101
 102 # Mapping from package name to TermuxPackage
 103 # (if subpackage, mapping from subpackage name to parent package)
 104 pkgs_map = {}
 105
 106 # Reverse dependencies
 107 pkg_depends_on = {}
 108
 109 PACKAGES_DIR = 'packages'
 110
 111
 112 def populate():
 113
 114     for pkgdir_name in sorted(os.listdir(PACKAGES_DIR)):
 115
 116         pkg = TermuxPackage(pkgdir_name)
 117
 118         pkgs_map[pkg.name] = pkg
 119
 120         for subpkg in pkg.subpkgs:
 121             pkgs_map[subpkg.name] = pkg
 122             remaining_deps[subpkg.name] = set(subpkg.deps)
 123
 124         remaining_deps[pkg.name] = set(pkg.deps)
 125
 126     all_pkg_names = set(pkgs_map.keys())
 127
 128     for name, pkg in pkgs_map.items():
 129         for dep_name in remaining_deps[name]:
 130             if dep_name not in all_pkg_names:
 131                 die('Package %s depends on non-existing package "%s"' % (
 132                  name, dep_name
 133                 ))
 134
 135             dep_pkg = pkgs_map[dep_name]
 136             dep_pkg.needed_by.add(pkg)
 137
 138
 139 def buildorder():
 140     # List of all TermuxPackages without dependencies
 141     leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps]
 142
 143     if not leaf_pkgs:
 144         die('No package without dependencies - where to start?')
 145
 146     # Sort alphabetically, but with libandroid-support first (since dependency on libandroid-support
 147     # does not need to be declared explicitly, so anything might in theory depend on it to build):
 148     pkg_queue = sorted(leaf_pkgs, key=lambda p: '' if p.name == 'libandroid-support' else p.name)
 149
 150     # Topological sorting
 151     build_order = []
 152     visited = set()
 153
 154     while pkg_queue:
 155         pkg = pkg_queue.pop(0)
 156         if pkg.name in visited:
 157             continue
 158         visited.add(pkg.name)
 159
 160         # print("Processing {}:".format(pkg.name), pkg.needed_by)
 161
 162         build_order.append(pkg)
 163
 164         for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
 165             # Mark this package as done
 166             remaining_deps[other_pkg.name].discard(pkg.name)
 167
 168             # ... and all its subpackages
 169             remaining_deps[other_pkg.name].difference_update(
 170                 [subpkg.name for subpkg in pkg.subpkgs]
 171             )
 172
 173             if not remaining_deps[other_pkg.name]:  # all deps were pruned?
 174                 pkg_queue.append(other_pkg)
 175
 176     return build_order
 177
 178
 179 def generate_and_print_buildorder():
 180     build_order = buildorder()
 181
 182     if set(pkgs_map.values()) != set(build_order):
 183         print("ERROR: Cycle exists. Remaining: ")
 184         for name, pkg in pkgs_map.items():
 185             if pkg not in build_order:
 186                 print(name, remaining_deps[name])
 187
 188         sys.exit(1)
 189
 190     for pkg in build_order:
 191         print(pkg.name)
 192
 193     sys.exit(0)
 194
 195 if __name__ == '__main__':
 196     populate()
 197     generate_and_print_buildorder()