#!/usr/bin/env python3 # -*- coding: utf-8 -*- # SPDX-License-Identifier: GPL-2.0 # Copyright (C) 2019-present Team LibreELEC (https://libreelec.tv) import sys, os, codecs, json, argparse, re ROOT_PKG = "__root__" class LibreELEC_Package: def __init__(self, name, section): self.name = name self.section = section self.deps = {"bootstrap": [], "init": [], "host": [], "target": []} self.wants = [] self.wantedby = [] self.unpacks = [] def __repr__(self): s = f"{name:<9}: {self.name}" s = f"{s}\n{section:<9}: {self.section}" for t in self.deps: s = f"{s}\n{t:<9}: {self.deps[t]}" s = f"{s}\n{'UNPACKS':<9}: {self.unpacks}" s = f"{s}\n{'NEEDS':<9}: {self.wants}" s = f"{s}\n{'WANTED BY':<9}: {self.wantedby}" return s def addDependencies(self, target, packages): for d in " ".join(packages.split()).split(): self.deps[target].append(d) name = d.split(":")[0] if name not in self.wants and name != self.name: self.wants.append(name) def delDependency(self, target, package): if package in self.deps[target]: self.deps[target].remove(package) name = package.split(":")[0] if name in self.wants: self.wants.remove(name) def addReference(self, package): name = package.split(":")[0] if name not in self.wantedby: self.wantedby.append(name) def delReference(self, package): name = package.split(":")[0] if name in self.wantedby: self.wantedby.remove(name) def addUnpack(self, packages): if packages.strip(): self.unpacks = packages.strip().split() def isReferenced(self): return False if self.wants == [] else True def isWanted(self): return False if self.wantedby == [] else True def references(self, package): return package in self.wants # Reference material: # https://www.electricmonk.nl/docs/dependency_resolving_algorithm/dependency_resolving_algorithm.html class Node: def __init__(self, name, target, section): self.name = name self.target = target self.section = section self.fqname = f"{name}:{target}" self.edges = [] def appendEdges(self, node): # Add the node itself... if node not in self.edges: self.edges.append(node) # as well as its edges for e in node.edges: if e not in self.edges: self.edges.append(e) # Return True if the dependencies of the specified node are met by this node def satisfies(self, node): for e in node.edges: if e not in self.edges: return False return True def __repr__(self): s = f"{'name':<9}: {self.name}" s = f"{s}\n{'target':<9}: {self.target}" s = f"{s}\n{'fqname':<9}: {self.fqname}" s = f"{s}\n{'common':<9}: {self.commonName()}" s = f"{s}\n{'section':<9}: {self.section}" for e in self.edges: s = f"{s}\nEDGE: {e.fqname}" return s def commonName(self): return self.name if self.target == "target" else f"{self.name}:{self.target}" def addEdge(self, node): if node not in self.edges: self.edges.append(node) def eprint(*args, **kwargs): print(*args, file=sys.stderr, **kwargs) # Read a JSON list of all possible packages from stdin, removing newlines def loadPackages(): jdata = json.loads(f"[{sys.stdin.read().replace(chr(10),'')[:-1]}]") map = {} # Load "global" packages first for pkg in jdata: if pkg["hierarchy"] == "global": map[pkg["name"]] = initPackage(pkg) # Then the "local" packages, as these will replace any matching "global" packages for pkg in jdata: if pkg["hierarchy"] == "local": map[pkg["name"]] = initPackage(pkg) return map # Create a fully formed LibreELEC_Package object def initPackage(package): pkg = LibreELEC_Package(package["name"], package["section"]) for target in ["bootstrap", "init", "host", "target"]: pkg.addDependencies(target, package[target]) pkg.addUnpack(package["unpack"]) return pkg # Split name:target into components def split_package(name): parts = name.split(":") pn = parts[0] pt = parts[1] if len(parts) != 1 else "target" return (pn, pt) # Return a list of packages of the specified type def get_packages_by_target(target, list): newlist = [] for p in list: (pn, pt) = split_package(p) if target in ["target", "init"] and pt in ["target", "init"]: newlist.append(p) elif target in ["bootstrap", "host"] and pt in ["bootstrap", "host"]: newlist.append(p) return newlist # For the specified node iterate over the list of scheduled nodes and return the first # position where we could possibly build this node (ie. all dependencies satisfied). def findbuildpos(node, list): # Keep a running total of all dependencies as we progress through the list alldeps = Node("", "", "") candidate = None for n in list: alldeps.appendEdges(n) if alldeps.satisfies(node): if len(n.edges) > len(node.edges): if candidate == None: candidate = n break candidate = n return list.index(candidate) + 1 if candidate else -1 # Resolve dependencies for a node def dep_resolve(node, resolved, unresolved): unresolved.append(node) for edge in node.edges: if edge not in resolved: if edge in unresolved: raise Exception(( f"Circular reference detected: {node.fqname} -> {edge.commonName()}\n" f"Remove {edge.commonName()} from {node.name} package.mk::PKG_DEPENDS_{node.target.upper()}" )) dep_resolve(edge, resolved, unresolved) if node not in resolved: resolved.append(node) unresolved.remove(node) # Return a list of build steps for the trigger packages def get_build_steps(args, nodes): resolved = [] unresolved = [] # When building the image the :target packages must be installed. # # However, if we are not building the image then only build the packages # and don't install them as it's likely we will be building discrete add-ons # which are installed outside of the image. # install = True if "image" in args.build else False for pkgname in [x for x in args.build if x]: if pkgname.find(":") == -1: pkgname = f"{pkgname}:target" if pkgname in nodes: dep_resolve(nodes[pkgname], resolved, unresolved) # Abort if any references remain unresolved if unresolved != []: eprint("The following dependencies have not been resolved:") for dep in unresolved: eprint(f" {dep}") raise("Unresolved references") # Output list of resolved dependencies for pkg in resolved: task = "build" if pkg.fqname.endswith(":host") or pkg.fqname.endswith(":init") or not install else "install" yield(task, pkg.fqname) # Reduce the complete list of packages to a map of those packages that will # be needed for the build. def processPackages(args, packages): # Add dummy package to ensure build/install dependencies are not culled pkg = { "name": ROOT_PKG, "section": "virtual", "hierarchy": "global", "bootstrap": "", "init": "", "host": " ".join(get_packages_by_target("host", args.build)), "target": " ".join(get_packages_by_target("target", args.build)), "unpack": "" } packages[pkg["name"]] = initPackage(pkg) # Resolve reverse references that we can use to ignore unreferenced packages for pkgname in packages: for opkgname in packages: opkg = packages[opkgname] if opkg.references(pkgname): if pkgname in packages: packages[pkgname].addReference(opkgname) # Identify unused packages while True: changed = False for pkgname in packages: pkg = packages[pkgname] if pkg.isWanted(): for opkgname in pkg.wantedby: if opkgname != ROOT_PKG: if not packages[opkgname].isWanted(): pkg.delReference(opkgname) changed = True if not changed: break # Create a new map of "needed" packages needed_map = {} for pkgname in packages: pkg = packages[pkgname] if pkg.isWanted() or pkgname == ROOT_PKG: needed_map[pkgname] = pkg # Validate package dependency references if not args.ignore_invalid: for pkgname in needed_map: pkg = needed_map[pkgname] for t in pkg.deps: for d in pkg.deps[t]: if split_package(d)[0] not in needed_map: msg = f'Invalid package reference: dependency {d} in package {pkgname}::PKG_DEPENDS_{t.upper()} is not valid' if args.warn_invalid: eprint(f"WARNING: {msg}") else: raise Exception(msg) node_map = {} # Convert all packages to target-specific nodes for pkgname in needed_map: pkg = needed_map[pkgname] for target in pkg.deps: if pkg.deps[target]: node = Node(pkgname, target, pkg.section) node_map[node.fqname] = node # Ensure all referenced dependencies exist as a basic node for pkgname in needed_map: pkg = needed_map[pkgname] for target in pkg.deps: for dep in pkg.deps[target]: dfq = dep if dep.find(":") != -1 else f"{dep}:target" if dfq not in node_map: (dfq_p, dfq_t) = split_package(dfq) if dfq_p in packages: dpkg = packages[dfq_p] node_map[dfq] = Node(dfq_p, dfq_t, dpkg.section) elif not args.ignore_invalid: raise Exception(f"Invalid package! Package {dfq_p} cannot be found for this PROJECT/DEVICE/ARCH") # To each target-specific node, add the corresponding # target-specific dependency nodes ("edges") for name in node_map: node = node_map[name] if node.name not in needed_map: if args.warn_invalid: continue else: raise Exception(f"Invalid package! Package {node.name} cannot be found for this PROJECT/DEVICE/ARCH") for dep in needed_map[node.name].deps[node.target]: dfq = dep if dep.find(":") != -1 else f"{dep}:target" if dfq in node_map: node.addEdge(node_map[dfq]) return node_map #--------------------------------------------- parser = argparse.ArgumentParser(description="Generate package dependency list for the requested build/install packages. \ Package data will be read from stdin in JSON format.", \ formatter_class=lambda prog: argparse.HelpFormatter(prog,max_help_position=25,width=90)) parser.add_argument("-b", "--build", nargs="+", metavar="PACKAGE", required=True, \ help="Space-separated list of build trigger packages, either for host or target. Required property - specify at least one package.") parser.add_argument("--warn-invalid", action="store_true", default=False, \ help="Warn about invalid/missing dependency packages, perhaps excluded by a PKG_ARCH incompatability. Default is to abort.") parser.add_argument("--ignore-invalid", action="store_true", default=False, \ help="Ignore invalid packages.") group = parser.add_mutually_exclusive_group() group.add_argument("--show-wants", action="store_true", \ help="Output \"wants\" dependencies for each step.") group.add_argument("--hide-wants", action="store_false", dest="show_wants", default=True, \ help="Disable --show-wants. This is the default.") parser.add_argument("--with-json", metavar="FILE", \ help="File into which JSON formatted plan will be written.") args = parser.parse_args() ALL_PACKAGES = loadPackages() loaded = len(ALL_PACKAGES) REQUIRED_PKGS = processPackages(args, ALL_PACKAGES) # Identify list of packages to build/install steps = [step for step in get_build_steps(args, REQUIRED_PKGS)] eprint(f"Packages loaded : {loaded}") eprint(f"Build trigger(s): {len(args.build)} [{' '.join(args.build)}]") eprint(f"Package steps : {len(steps)}") eprint("") # Write the JSON build plan (with dependencies) if args.with_json: plan = [] for step in steps: (pkg_name, target) = split_package(step[1]) plan.append({"task": step[0], "name": step[1], "section": ALL_PACKAGES[pkg_name].section, "wants": [d.fqname for d in REQUIRED_PKGS[step[1]].edges], "unpacks": ALL_PACKAGES[pkg_name].unpacks if pkg_name in ALL_PACKAGES else []}) with open(args.with_json, "w") as out: print(json.dumps(plan, indent=2, sort_keys=False), file=out) # Output build/install steps if args.show_wants: for step in steps: node = (REQUIRED_PKGS[step[1]]) wants = [edge.fqname for edge in node.edges] print(f"{step[0]:<7} {step[1].replace(':target',''):<25} (wants: {', '.join(wants).replace(':target','')})") else: for step in steps: print(f"{step[0]:<7} {step[1].replace(':target','')}")