2 # buildorder.py - script to generate a build order respecting package dependencies
8 from itertools
import filterfalse
11 # https://docs.python.org/3/library/itertools.html#itertools-recipes
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
20 for element
in filterfalse(seen
.__contains__
, iterable
):
24 for element
in iterable
:
32 sys
.exit('ERROR: ' + msg
)
34 def rchop(thestring
, ending
):
35 if thestring
.endswith(ending
):
36 return thestring
[:-len(ending
)]
39 class TermuxBuildFile(object):
40 def __init__(self
, path
):
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='
49 with
open(self
.path
, encoding
="utf-8") as 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
61 comma_deps
+= line
[len(prefix
):].replace('"', '').replace("'", '').replace("\n", ",")
63 # Remove trailing ',' that is otherwise replacing the final newline
64 comma_deps
= comma_deps
[:-1]
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(',')
75 class TermuxPackage(object):
76 PACKAGES_DIR
= 'packages'
78 def __init__(self
, name
):
80 self
.dir = os
.path
.join(self
.PACKAGES_DIR
, name
)
82 # search package build.sh
83 build_sh_path
= os
.path
.join(self
.dir, 'build.sh')
84 if not os
.path
.isfile(build_sh_path
):
85 raise Exception("build.sh not found for package '" + name
+ "'")
87 self
.buildfile
= TermuxBuildFile(build_sh_path
)
88 self
.deps
= self
.buildfile
._get_dependencies()
89 if 'libandroid-support' not in self
.deps
and self
.name
!= 'libandroid-support':
90 # Every package may depend on libandroid-support without declaring it:
91 self
.deps
.add('libandroid-support')
96 for filename
in os
.listdir(self
.dir):
97 if not filename
.endswith('.subpackage.sh'):
100 subpkg_name
= filename
.split('.subpackage.sh')[0]
101 subpkg
= TermuxSubPackage(subpkg_name
, parent
=self
)
103 self
.subpkgs
.append(subpkg
)
104 self
.deps |
= subpkg
.deps
106 # Do not depend on itself
107 self
.deps
.discard(self
.name
)
108 # Do not depend on any sub package
109 self
.deps
.difference_update([subpkg
.name
for subpkg
in self
.subpkgs
])
111 self
.needed_by
= set() # to be completed outside, reverse of deps
114 return "<{} '{}'>".format(self
.__class__
.__name__
, self
.name
)
117 class TermuxSubPackage(TermuxPackage
):
119 def __init__(self
, name
, parent
=None):
121 raise Exception("SubPackages should have a parent")
125 self
.buildfile
= TermuxBuildFile(os
.path
.join(self
.parent
.dir, name
+ '.subpackage.sh'))
126 self
.deps
= self
.buildfile
._get_dependencies()
129 return "<{} '{}' parent='{}'>".format(self
.__class__
.__name__
, self
.name
, self
.parent
)
132 # Tracks non-visited deps for each package
135 # Mapping from package name to TermuxPackage
136 # (if subpackage, mapping from subpackage name to parent package)
139 # Reverse dependencies
142 PACKAGES_DIR
= 'packages'
147 for pkgdir_name
in sorted(os
.listdir(PACKAGES_DIR
)):
149 pkg
= TermuxPackage(pkgdir_name
)
151 pkgs_map
[pkg
.name
] = pkg
153 for subpkg
in pkg
.subpkgs
:
154 pkgs_map
[subpkg
.name
] = pkg
155 remaining_deps
[subpkg
.name
] = set(subpkg
.deps
)
157 remaining_deps
[pkg
.name
] = set(pkg
.deps
)
159 all_pkg_names
= set(pkgs_map
.keys())
161 for name
, pkg
in pkgs_map
.items():
162 for dep_name
in remaining_deps
[name
]:
163 if dep_name
not in all_pkg_names
:
164 die('Package %s depends on non-existing package "%s"' %
(
168 dep_pkg
= pkgs_map
[dep_name
]
169 dep_pkg
.needed_by
.add(pkg
)
172 def generate_full_buildorder():
175 # List of all TermuxPackages without dependencies
176 leaf_pkgs
= [pkg
for name
, pkg
in pkgs_map
.items() if not pkg
.deps
]
179 die('No package without dependencies - where to start?')
181 # Sort alphabetically:
182 pkg_queue
= sorted(leaf_pkgs
, key
=lambda p
: p
.name
)
184 # Topological sorting
188 pkg
= pkg_queue
.pop(0)
189 if pkg
.name
in visited
:
192 # print("Processing {}:".format(pkg.name), pkg.needed_by)
193 visited
.add(pkg
.name
)
194 build_order
.append(pkg
)
196 for other_pkg
in sorted(pkg
.needed_by
, key
=lambda p
: p
.name
):
197 # Remove this pkg from deps
198 remaining_deps
[other_pkg
.name
].discard(pkg
.name
)
199 # ... and all its subpackages
200 remaining_deps
[other_pkg
.name
].difference_update(
201 [subpkg
.name
for subpkg
in pkg
.subpkgs
]
204 if not remaining_deps
[other_pkg
.name
]: # all deps were already appended?
205 pkg_queue
.append(other_pkg
) # should be processed
207 if set(pkgs_map
.values()) != set(build_order
):
208 print("ERROR: Cycle exists. Remaining: ")
209 for name
, pkg
in pkgs_map
.items():
210 if pkg
not in build_order
:
211 print(name
, remaining_deps
[name
])
218 def deps_then_me(pkg
):
221 for dep
in sorted(pkg
.deps
):
222 l
+= deps_then_me(pkgs_map
[dep
])
228 def generate_targets_buildorder(targetnames
):
231 for pkgname
in targetnames
:
232 if not pkgname
in pkgs_map
:
233 die('Dependencies for ' + pkgname
+ ' could not be calculated (skip dependency check with -s)')
234 buildorder
+= deps_then_me(pkgs_map
[pkgname
])
236 return unique_everseen(buildorder
)
238 if __name__
== '__main__':
241 if len(sys
.argv
) == 1:
242 bo
= generate_full_buildorder()
244 bo
= generate_targets_buildorder(sys
.argv
[1:])