Commit | Line | Data |
---|---|---|
59f0d218 FF |
1 | #!/usr/bin/env python3 |
2 | # buildorder.py - script to generate a build order respecting package dependencies | |
3 | ||
6521bf5c | 4 | import os |
00875c03 | 5 | import re |
6521bf5c | 6 | import sys |
59f0d218 | 7 | |
4f0cc219 FD |
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 | ||
59f0d218 | 30 | |
6521bf5c FD |
31 | def die(msg): |
32 | sys.exit('ERROR: ' + msg) | |
59f0d218 | 33 | |
1fe81051 VO |
34 | def rchop(thestring, ending): |
35 | if thestring.endswith(ending): | |
36 | return thestring[:-len(ending)] | |
37 | return thestring | |
59f0d218 | 38 | |
da6299f0 FD |
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=' | |
45d85e7f | 45 | pkg_build_dep_prefix = 'TERMUX_PKG_BUILD_DEPENDS=' |
da6299f0 | 46 | subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS=' |
1fe81051 | 47 | comma_deps = '' |
da6299f0 | 48 | |
4e8d7d1e | 49 | with open(self.path, encoding="utf-8") as f: |
da6299f0 FD |
50 | prefix = None |
51 | for line in f: | |
52 | if line.startswith(pkg_dep_prefix): | |
53 | prefix = pkg_dep_prefix | |
45d85e7f FF |
54 | elif line.startswith(pkg_build_dep_prefix): |
55 | prefix = pkg_build_dep_prefix | |
da6299f0 FD |
56 | elif line.startswith(subpkg_dep_prefix): |
57 | prefix = subpkg_dep_prefix | |
58 | else: | |
59 | continue | |
60 | ||
1fe81051 | 61 | comma_deps += line[len(prefix):].replace('"', '').replace("'", '').replace("\n", ",") |
da6299f0 | 62 | |
1fe81051 VO |
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() | |
da6299f0 | 68 | |
1fe81051 VO |
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 | ]) | |
da6299f0 FD |
73 | |
74 | ||
37af75e4 | 75 | class TermuxPackage(object): |
02764a91 FF |
76 | def __init__(self, dir_path): |
77 | self.dir = dir_path | |
78 | self.name = os.path.basename(self.dir) | |
da6299f0 FD |
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): | |
02764a91 | 83 | raise Exception("build.sh not found for package '" + self.name + "'") |
da6299f0 FD |
84 | |
85 | self.buildfile = TermuxBuildFile(build_sh_path) | |
86 | self.deps = self.buildfile._get_dependencies() | |
1858fd1b FF |
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') | |
da6299f0 FD |
90 | |
91 | # search subpackages | |
92 | self.subpkgs = [] | |
93 | ||
94 | for filename in os.listdir(self.dir): | |
02764a91 FF |
95 | if not filename.endswith('.subpackage.sh'): continue |
96 | subpkg = TermuxSubPackage(self.dir + '/' + filename, self) | |
da6299f0 FD |
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): | |
02764a91 | 113 | def __init__(self, subpackage_file_path, parent): |
da6299f0 FD |
114 | if parent is None: |
115 | raise Exception("SubPackages should have a parent") | |
116 | ||
02764a91 FF |
117 | self.buildfile = TermuxBuildFile(subpackage_file_path) |
118 | self.name = os.path.basename(subpackage_file_path).split('.subpackage.sh')[0] | |
da6299f0 | 119 | self.parent = parent |
da6299f0 FD |
120 | self.deps = self.buildfile._get_dependencies() |
121 | ||
122 | def __repr__(self): | |
123 | return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent) | |
6521bf5c | 124 | |
da6299f0 FD |
125 | |
126 | # Tracks non-visited deps for each package | |
127 | remaining_deps = {} | |
6521bf5c | 128 | |
37af75e4 | 129 | # Mapping from package name to TermuxPackage |
6521bf5c | 130 | # (if subpackage, mapping from subpackage name to parent package) |
da6299f0 | 131 | pkgs_map = {} |
59f0d218 | 132 | |
da6299f0 FD |
133 | # Reverse dependencies |
134 | pkg_depends_on = {} | |
6521bf5c | 135 | |
02764a91 | 136 | PACKAGES_DIRS = ['packages'] |
6521bf5c | 137 | |
15ea0fef | 138 | |
da6299f0 | 139 | def populate(): |
02764a91 FF |
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)) | |
15ea0fef | 146 | |
02764a91 FF |
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 | |
da6299f0 FD |
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) | |
15ea0fef | 156 | |
da6299f0 FD |
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: | |
15ea0fef | 162 | die('Package %s depends on non-existing package "%s"' % ( |
da6299f0 | 163 | name, dep_name |
15ea0fef | 164 | )) |
15ea0fef | 165 | |
da6299f0 FD |
166 | dep_pkg = pkgs_map[dep_name] |
167 | dep_pkg.needed_by.add(pkg) | |
168 | ||
169 | ||
4f0cc219 FD |
170 | def generate_full_buildorder(): |
171 | build_order = [] | |
172 | ||
37af75e4 | 173 | # List of all TermuxPackages without dependencies |
da6299f0 FD |
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?') | |
15ea0fef | 178 | |
1858fd1b FF |
179 | # Sort alphabetically: |
180 | pkg_queue = sorted(leaf_pkgs, key=lambda p: p.name) | |
15ea0fef FD |
181 | |
182 | # Topological sorting | |
da6299f0 FD |
183 | visited = set() |
184 | ||
185 | while pkg_queue: | |
186 | pkg = pkg_queue.pop(0) | |
187 | if pkg.name in visited: | |
188 | continue | |
da6299f0 FD |
189 | |
190 | # print("Processing {}:".format(pkg.name), pkg.needed_by) | |
0227e1a6 | 191 | visited.add(pkg.name) |
15ea0fef | 192 | build_order.append(pkg) |
da6299f0 FD |
193 | |
194 | for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name): | |
0227e1a6 | 195 | # Remove this pkg from deps |
da6299f0 | 196 | remaining_deps[other_pkg.name].discard(pkg.name) |
da6299f0 FD |
197 | # ... and all its subpackages |
198 | remaining_deps[other_pkg.name].difference_update( | |
199 | [subpkg.name for subpkg in pkg.subpkgs] | |
200 | ) | |
201 | ||
0227e1a6 FD |
202 | if not remaining_deps[other_pkg.name]: # all deps were already appended? |
203 | pkg_queue.append(other_pkg) # should be processed | |
da6299f0 | 204 | |
da6299f0 | 205 | if set(pkgs_map.values()) != set(build_order): |
15ea0fef | 206 | print("ERROR: Cycle exists. Remaining: ") |
da6299f0 | 207 | for name, pkg in pkgs_map.items(): |
15ea0fef | 208 | if pkg not in build_order: |
da6299f0 FD |
209 | print(name, remaining_deps[name]) |
210 | ||
15ea0fef FD |
211 | sys.exit(1) |
212 | ||
4f0cc219 | 213 | return build_order |
15ea0fef | 214 | |
02764a91 FF |
215 | def deps(pkg): |
216 | l = [] | |
217 | for dep in sorted(pkg.deps): | |
218 | l += deps_then_me(pkgs_map[dep]) | |
219 | return l | |
da6299f0 | 220 | |
4f0cc219 FD |
221 | def deps_then_me(pkg): |
222 | l = [] | |
a8d10018 | 223 | for dep in sorted(pkg.deps): |
4f0cc219 FD |
224 | l += deps_then_me(pkgs_map[dep]) |
225 | l += [pkg] | |
4f0cc219 FD |
226 | return l |
227 | ||
228 | ||
02764a91 | 229 | def generate_targets_buildorder(target_paths): |
4f0cc219 FD |
230 | buildorder = [] |
231 | ||
02764a91 FF |
232 | for target_path in target_paths: |
233 | if target_path.endswith('/'): target_path = target_path[:-1] | |
234 | pkgname = os.path.basename(target_path) | |
e65ab762 FF |
235 | if not pkgname in pkgs_map: |
236 | die('Dependencies for ' + pkgname + ' could not be calculated (skip dependency check with -s)') | |
02764a91 | 237 | buildorder += deps(pkgs_map[pkgname]) |
4f0cc219 FD |
238 | |
239 | return unique_everseen(buildorder) | |
a8d10018 | 240 | |
15ea0fef | 241 | if __name__ == '__main__': |
02764a91 FF |
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 | ||
da6299f0 | 253 | populate() |
a8d10018 | 254 | |
02764a91 | 255 | if full_buildorder: |
4f0cc219 FD |
256 | bo = generate_full_buildorder() |
257 | else: | |
258 | bo = generate_targets_buildorder(sys.argv[1:]) | |
a8d10018 | 259 | |
4f0cc219 | 260 | for pkg in bo: |
02764a91 | 261 | print(pkg.dir) |