buildorder.py: huge refactor

diff --git a/buildorder.py b/buildorder.py
index cd12de438ae725350135cf84aaa17d4cde7f744d..bb248a95c3d76e9d8f716db659323d1cd63cc053 100755 (executable)
--- a/buildorder.py
+++ b/buildorder.py
@@ -13,108 +13,185 @@ if len(sys.argv) != 1:
     die('buildorder.py takes no arguments')
 
 
     die('buildorder.py takes no arguments')
 
 

+class TermuxBuildFile(object):
+    def __init__(self, path):
+        self.path = path
+
+    def _get_dependencies(self):
+        pkg_dep_prefix = 'TERMUX_PKG_DEPENDS='
+        subpkg_dep_prefix = 'TERMUX_SUBPKG_DEPENDS='
+
+        with open(self.path) as f:
+            prefix = None
+            for line in f:
+                if line.startswith(pkg_dep_prefix):
+                    prefix = pkg_dep_prefix
+                elif line.startswith(subpkg_dep_prefix):
+                    prefix = subpkg_dep_prefix
+                else:
+                    continue
+
+                comma_deps = line[len(prefix):].replace('"', '')
+
+                return set([
+                    dep.strip() for dep in comma_deps.split(',')
+                    if 'libandroid-support' not in dep
+                ])
+
+        # no deps found
+        return set()
+
+

 class TermuxPackage(object):
 class TermuxPackage(object):

+    PACKAGES_DIR = 'packages'
+

     def __init__(self, name):
         self.name = name
     def __init__(self, name):
         self.name = name

-        self.remaining_dependencies = set()  # String
-        self.sub_packages = set()  # String
-        self.prerequisite_for = set()  # Packages that needs this package
+        self.dir = os.path.join(self.PACKAGES_DIR, name)
+
+        # search package build.sh
+        build_sh_path = os.path.join(self.dir, 'build.sh')
+        if not os.path.isfile(build_sh_path):
+            raise Exception("build.sh not found")
+
+        self.buildfile = TermuxBuildFile(build_sh_path)
+        self.deps = self.buildfile._get_dependencies()
+
+        # search subpackages
+        self.subpkgs = []
+
+        for filename in os.listdir(self.dir):
+            if not filename.endswith('.subpackage.sh'):
+                continue
+
+            subpkg_name = filename.split('.subpackage.sh')[0]
+            subpkg = TermuxSubPackage(subpkg_name, parent=self)
+
+            self.subpkgs.append(subpkg)
+            self.deps |= subpkg.deps
+
+        # Do not depend on itself
+        self.deps.discard(self.name)
+        # Do not depend on any sub package
+        self.deps.difference_update([subpkg.name for subpkg in self.subpkgs])
+
+        self.needed_by = set()  # to be completed outside, reverse of    deps
+
+    def __repr__(self):
+        return "<{} '{}'>".format(self.__class__.__name__, self.name)
+
+
+class TermuxSubPackage(TermuxPackage):
+
+    def __init__(self, name, parent=None):
+        if parent is None:
+            raise Exception("SubPackages should have a parent")
+
+        self.name = name
+        self.parent = parent
+        self.buildfile = TermuxBuildFile(os.path.join(self.parent.dir, name + '.subpackage.sh'))
+        self.deps = self.buildfile._get_dependencies()
+
+    def __repr__(self):
+        return "<{} '{}' parent='{}'>".format(self.__class__.__name__, self.name, self.parent)

 
 

-# List of all TermuxPackages
-all_packages = []
+
+# Tracks non-visited deps for each package
+remaining_deps = {}

 
 # Mapping from package name to TermuxPackage
 # (if subpackage, mapping from subpackage name to parent package)
 
 # Mapping from package name to TermuxPackage
 # (if subpackage, mapping from subpackage name to parent package)

-packages_map = {}
+pkgs_map = {}

 
 

-packages_dir = 'packages'
+# Reverse dependencies
+pkg_depends_on = {}

 
 

+PACKAGES_DIR = 'packages'

 
 

-def main():
-    for subdir_name in sorted(os.listdir(packages_dir)):
-        subdir_path = packages_dir + '/' + subdir_name

 
 

-        if os.path.exists(subdir_path + '/BROKEN.txt'):
-            continue
+def populate():

 
 

-        build_sh_path = subdir_path + '/build.sh'
+    for pkgdir_name in sorted(os.listdir(PACKAGES_DIR)):

 
 

-        this_package = TermuxPackage(subdir_name)
-        all_packages.append(this_package)
-        packages_map[this_package.name] = this_package
+        pkg = TermuxPackage(pkgdir_name)

 
 

-        if not os.path.isfile(build_sh_path):
-            die('The directory ' + subdir_name + ' does not contain build.sh')
-
-        with open(build_sh_path) as build_sh_file:
-            for line in build_sh_file:
-                if line.startswith('TERMUX_PKG_DEPENDS='):
-                    deps_comma_separated = line[(line.index('=')+2):(len(line)-2)]
-                    for dep in deps_comma_separated.split(','):
-                        dep = dep.strip()
-                        if not dep.endswith('libandroid-support-dev'):
-                            this_package.remaining_dependencies.add(dep)
-
-        for file_in_subdir_name in sorted(os.listdir(subdir_path)):
-            if file_in_subdir_name.endswith('.subpackage.sh'):
-                subpackage_name = file_in_subdir_name[0:-len(".subpackage.sh"):]
-                this_package.sub_packages.add(subpackage_name)
-                packages_map[subpackage_name] = this_package
-                with open(subdir_path + '/' + file_in_subdir_name) as subpackage_sh_file:
-                    for line in subpackage_sh_file:
-                        if line.startswith('TERMUX_SUBPKG_DEPENDS='):
-                            deps_comma_separated = line[(line.index('=')+2):(len(line)-2)]
-                            for dep in deps_comma_separated.split(','):
-                                dep = dep.strip()
-                                this_package.remaining_dependencies.add(dep)
-        # Do not depend on itself
-        this_package.remaining_dependencies.discard(this_package.name)
-        # Do not depend on any sub package
-        this_package.remaining_dependencies.difference_update(this_package.sub_packages)
+        pkgs_map[pkg.name] = pkg
+
+        for subpkg in pkg.subpkgs:
+            pkgs_map[subpkg.name] = pkg
+            remaining_deps[subpkg.name] = set(subpkg.deps)
+
+        remaining_deps[pkg.name] = set(pkg.deps)

 
 

-    for package in all_packages:
-        for remaining in package.remaining_dependencies:
-            if remaining not in packages_map:
+    all_pkg_names = set(pkgs_map.keys())
+
+    for name, pkg in pkgs_map.items():
+        for dep_name in remaining_deps[name]:
+            if dep_name not in all_pkg_names:

                 die('Package %s depends on non-existing package "%s"' % (
                 die('Package %s depends on non-existing package "%s"' % (

-                 package.name, remaining
+                 name, dep_name

                 ))
                 ))

-            packages_map[remaining].prerequisite_for.add(package)

 
 

+            dep_pkg = pkgs_map[dep_name]
+            dep_pkg.needed_by.add(pkg)
+
+
+def buildorder():

     # List of all TermuxPackages without dependencies
     # List of all TermuxPackages without dependencies

-    packages_without_deps = [p for p in all_packages if not p.remaining_dependencies]
-    if not packages_without_deps:
-        die('No package without dependency - where to start?')
+    leaf_pkgs = [pkg for name, pkg in pkgs_map.items() if not pkg.deps]
+
+    if not leaf_pkgs:
+        die('No package without dependencies - where to start?')

 
     # Sort alphabetically, but with libandroid-support first (since dependency on libandroid-support
     # does not need to be declared explicitly, so anything might in theory depend on it to build):
 
     # Sort alphabetically, but with libandroid-support first (since dependency on libandroid-support
     # does not need to be declared explicitly, so anything might in theory depend on it to build):

-
-    packages_without_deps.sort(
-        key=lambda p: '' if p.name == 'libandroid-support' else p.name,
-        reverse=True)
+    pkg_queue = sorted(leaf_pkgs, key=lambda p: '' if p.name == 'libandroid-support' else p.name)

 
     # Topological sorting
     build_order = []
 
     # Topological sorting
     build_order = []

-    while packages_without_deps:
-        pkg = packages_without_deps.pop()
+    visited = set()
+
+    while pkg_queue:
+        pkg = pkg_queue.pop(0)
+        if pkg.name in visited:
+            continue
+        visited.add(pkg.name)
+
+        # print("Processing {}:".format(pkg.name), pkg.needed_by)
+

         build_order.append(pkg)
         build_order.append(pkg)

-        for other_package in pkg.prerequisite_for:
-            # Remove this package
-            other_package.remaining_dependencies.discard(pkg.name)
-            # .. and all its subpackages
-            other_package.remaining_dependencies.difference_update(pkg.sub_packages)
-            if not other_package.remaining_dependencies:
-                # Check if the other package is ready to build now
-                packages_without_deps.append(other_package)
-
-    if len(all_packages) != len(build_order):
+
+        for other_pkg in sorted(pkg.needed_by, key=lambda p: p.name):
+            # Mark this package as done
+            remaining_deps[other_pkg.name].discard(pkg.name)
+
+            # ... and all its subpackages
+            remaining_deps[other_pkg.name].difference_update(
+                [subpkg.name for subpkg in pkg.subpkgs]
+            )
+
+            if not remaining_deps[other_pkg.name]:  # all deps were pruned?
+                pkg_queue.append(other_pkg)
+
+    return build_order
+
+
+def generate_and_print_buildorder():
+    build_order = buildorder()
+
+    if set(pkgs_map.values()) != set(build_order):

         print("ERROR: Cycle exists. Remaining: ")
         print("ERROR: Cycle exists. Remaining: ")

-        for pkg in all_packages:
+        for name, pkg in pkgs_map.items():

             if pkg not in build_order:
             if pkg not in build_order:

-                print(pkg.name)
+                print(name, remaining_deps[name])
+

         sys.exit(1)
 
     for pkg in build_order:
         print(pkg.name)
 
         sys.exit(1)
 
     for pkg in build_order:
         print(pkg.name)
 

+    sys.exit(0)
+

 if __name__ == '__main__':
 if __name__ == '__main__':

-    main()
+    populate()
+    generate_and_print_buildorder()