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