Update Cava to 0.6.0
[termux-packages] / scripts / buildorder.py
CommitLineData
59f0d218
FF
1#!/usr/bin/env python3
2# buildorder.py - script to generate a build order respecting package dependencies
3
6521bf5c 4import os
00875c03 5import re
6521bf5c 6import sys
59f0d218 7
4f0cc219
FD
8from itertools import filterfalse
9
10
11# https://docs.python.org/3/library/itertools.html#itertools-recipes
12
13def 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
59f0d218 30
6521bf5c
FD
31def die(msg):
32 sys.exit('ERROR: ' + msg)
59f0d218 33
59f0d218 34
da6299f0
FD
35class TermuxBuildFile(object):
36 def __init__(self, path):
37 self.path = path
38
39 def _get_dependencies(self):
40 pkg_dep_prefix = 'TERMUX_PKG_DEPENDS='
45d85e7f 41 pkg_build_dep_prefix = 'TERMUX_PKG_BUILD_DEPENDS='
da6299f0
FD
42 subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS='
43
4e8d7d1e 44 with open(self.path, encoding="utf-8") as f:
da6299f0
FD
45 prefix = None
46 for line in f:
47 if line.startswith(pkg_dep_prefix):
48 prefix = pkg_dep_prefix
45d85e7f
FF
49 elif line.startswith(pkg_build_dep_prefix):
50 prefix = pkg_build_dep_prefix
da6299f0
FD
51 elif line.startswith(subpkg_dep_prefix):
52 prefix = subpkg_dep_prefix
53 else:
54 continue
55
539d9e6a 56 comma_deps = line[len(prefix):].replace('"', '').replace("'", '')
da6299f0
FD
57
58 return set([
00875c03 59 # Replace parenthesis to handle version qualifiers, as in "gcc (>= 5.0)":
74b5c53c 60 re.sub(r'\(.*?\)', '', dep).replace('-dev', '').strip() for dep in comma_deps.split(',')
da6299f0
FD
61 ])
62
63 # no deps found
64 return set()
65
66
37af75e4 67class TermuxPackage(object):
da6299f0
FD
68 PACKAGES_DIR = 'packages'
69
6521bf5c
FD
70 def __init__(self, name):
71 self.name = name
da6299f0
FD
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):
af8dfb45 77 raise Exception("build.sh not found for package '" + name + "'")
da6299f0
FD
78
79 self.buildfile = TermuxBuildFile(build_sh_path)
80 self.deps = self.buildfile._get_dependencies()
1858fd1b
FF
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')
da6299f0
FD
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
109class 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)
6521bf5c 122
da6299f0
FD
123
124# Tracks non-visited deps for each package
125remaining_deps = {}
6521bf5c 126
37af75e4 127# Mapping from package name to TermuxPackage
6521bf5c 128# (if subpackage, mapping from subpackage name to parent package)
da6299f0 129pkgs_map = {}
59f0d218 130
da6299f0
FD
131# Reverse dependencies
132pkg_depends_on = {}
6521bf5c 133
da6299f0 134PACKAGES_DIR = 'packages'
6521bf5c 135
15ea0fef 136
da6299f0 137def populate():
15ea0fef 138
da6299f0 139 for pkgdir_name in sorted(os.listdir(PACKAGES_DIR)):
15ea0fef 140
da6299f0 141 pkg = TermuxPackage(pkgdir_name)
15ea0fef 142
da6299f0
FD
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)
15ea0fef 150
da6299f0
FD
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:
15ea0fef 156 die('Package %s depends on non-existing package "%s"' % (
da6299f0 157 name, dep_name
15ea0fef 158 ))
15ea0fef 159
da6299f0
FD
160 dep_pkg = pkgs_map[dep_name]
161 dep_pkg.needed_by.add(pkg)
162
163
4f0cc219
FD
164def generate_full_buildorder():
165 build_order = []
166
37af75e4 167 # List of all TermuxPackages without dependencies
da6299f0
FD
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?')
15ea0fef 172
1858fd1b
FF
173 # Sort alphabetically:
174 pkg_queue = sorted(leaf_pkgs, key=lambda p: p.name)
15ea0fef
FD
175
176 # Topological sorting
da6299f0
FD
177 visited = set()
178
179 while pkg_queue:
180 pkg = pkg_queue.pop(0)
181 if pkg.name in visited:
182 continue
da6299f0
FD
183
184 # print("Processing {}:".format(pkg.name), pkg.needed_by)
0227e1a6 185 visited.add(pkg.name)
15ea0fef 186 build_order.append(pkg)
da6299f0
FD
187
188 for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
0227e1a6 189 # Remove this pkg from deps
da6299f0 190 remaining_deps[other_pkg.name].discard(pkg.name)
da6299f0
FD
191 # ... and all its subpackages
192 remaining_deps[other_pkg.name].difference_update(
193 [subpkg.name for subpkg in pkg.subpkgs]
194 )
195
0227e1a6
FD
196 if not remaining_deps[other_pkg.name]: # all deps were already appended?
197 pkg_queue.append(other_pkg) # should be processed
da6299f0 198
da6299f0 199 if set(pkgs_map.values()) != set(build_order):
15ea0fef 200 print("ERROR: Cycle exists. Remaining: ")
da6299f0 201 for name, pkg in pkgs_map.items():
15ea0fef 202 if pkg not in build_order:
da6299f0
FD
203 print(name, remaining_deps[name])
204
15ea0fef
FD
205 sys.exit(1)
206
4f0cc219 207 return build_order
15ea0fef 208
da6299f0 209
4f0cc219
FD
210def deps_then_me(pkg):
211 l = []
a8d10018 212
a8d10018 213 for dep in sorted(pkg.deps):
4f0cc219
FD
214 l += deps_then_me(pkgs_map[dep])
215 l += [pkg]
216
217 return l
218
219
220def generate_targets_buildorder(targetnames):
221 buildorder = []
222
223 for pkgname in targetnames:
e65ab762
FF
224 if not pkgname in pkgs_map:
225 die('Dependencies for ' + pkgname + ' could not be calculated (skip dependency check with -s)')
4f0cc219
FD
226 buildorder += deps_then_me(pkgs_map[pkgname])
227
228 return unique_everseen(buildorder)
a8d10018 229
15ea0fef 230if __name__ == '__main__':
da6299f0 231 populate()
a8d10018
FD
232
233 if len(sys.argv) == 1:
4f0cc219
FD
234 bo = generate_full_buildorder()
235 else:
236 bo = generate_targets_buildorder(sys.argv[1:])
a8d10018 237
4f0cc219
FD
238 for pkg in bo:
239 print(pkg.name)