genrebuild

#!/usr/bin/python
import argparse
import colorlog
from collections import defaultdict
import networkx as nx
import pyalpm
import random

# TODO: Automate this. The packages listed here depend on ghc/ghc-libs but don't have .so files.
HASKELL_DO_NOT_EXPAND = {
    'alex',
    'c2hs',
    'cabal-install',
    'cgrep',
    'git-annex',
    'git-repair',
    'happy',
    'hedgewars',
    'hopenpgp-tools',
    'pandoc-cli',
    'tamarin-prover',
    'uusi',
    'xmonad-utils',
}
# The packages listed here are always required on build time, not check()
HASKELL_REAL_MAKEDEPEND = {
    'alex',
    'happy',
    'pandoc-cli',
    'uusi',
}

parser = argparse.ArgumentParser(description='Rebuild generator and orderer, generates all haskell reverse deps too')
parser.add_argument('-H', '--haskell-check', action="store_true",
                                             help='Filter results for haskell-only rebuilds, also implies --expand, --expand-make, --expand-check, and --ignore ghc,ghc-static')
parser.add_argument('-e', '--expand', action="store_true",
                                      help='Expand all reverse deps')
parser.add_argument('-m', '--expand-make', action="store_true",
                                           help='Expand all reverse make deps')
parser.add_argument('-c', '--expand-check', action="store_true",
                                            help='Expand all reverse check deps')
parser.add_argument('--only-explicit-make-and-check', action="store_true",
                                            help='Only expand reverse make and check deps for packages that are explicitly passed to this script, not recursively')
parser.add_argument('--ignore', nargs='?', default="", help='Ignore packages, separated by comma')
parser.add_argument('-d', '--db', nargs='?', default="core,extra,multilib",
                                             help='Pacman sync db to consider, separated by comma. Defaulting to all stable dbs.')
parser.add_argument('--dbpath', nargs='?', default="/var/lib/pacman",
                                           help='Pacman sync db location. Default: /var/lib/pacman')
parser.add_argument('--dep', nargs='?', default="",
                                        help='Additional dependencies to consider, as colon-separated pairs separated by comma. Example: foo:bar means foo depends on bar.')
parser.add_argument('package', nargs='+', help='Packages to rebuild')
args = parser.parse_args()

if args.haskell_check:
    args.expand = True
    args.expand_make = True
    args.expand_check = True
    if args.ignore == "":
        args.ignore = "ghc,ghc-static"

args.ignore = set(args.ignore.split(","))
args.db = set(args.db.split(","))

logger = colorlog.getLogger()
logger.setLevel(colorlog.DEBUG)

handler = colorlog.StreamHandler()
handler.setFormatter(colorlog.ColoredFormatter())
logger.addHandler(handler)

rebuild_list = set(filter(lambda p: not p.endswith(":nocheck"), args.package))
original_rebuild_list = rebuild_list.copy()

package_db = defaultdict(dict)
pkglist = rebuild_list.copy()
reverse_deps = defaultdict(set)
G = nx.DiGraph()
handle = pyalpm.Handle(".", args.dbpath)

for db in args.db:
    db_handle = handle.register_syncdb(db, 0)
    for package in db_handle.search(""):
        if package.name in args.ignore:
            continue
        for field in ("depends", "makedepends", "checkdepends", "provides", "arch"):
            package_db[package.name][field] = getattr(package, field)

for pkg in package_db:
    package_db[pkg]["depends"] = {dep.split("=")[0].split(">")[0].split("<")[0] for dep in package_db[pkg]["depends"]}
    package_db[pkg]["makedepends"] = {dep.split("=")[0].split(">")[0].split("<")[0] for dep in package_db[pkg]["makedepends"]}
    package_db[pkg]["checkdepends"] = {dep.split("=")[0].split(">")[0].split("<")[0] for dep in package_db[pkg]["checkdepends"]}
    package_db[pkg]["provides"] = {dep.split("=")[0].split(">")[0].split("<")[0] for dep in package_db[pkg]["provides"]}


def resolve_pkg(pkg):
    newpkgs = set()
    if pkg not in reverse_deps:
        if pkg not in package_db:
            logger.error(f"Package {pkg} not found in any db")
            exit(1)

        if args.haskell_check and (not ({"ghc", "ghc-libs"} & set(package_db[pkg]["depends"]) and package_db[pkg]["arch"] != "any")):
           return reverse_deps[pkg]

        for _pkg in package_db:
            if args.haskell_check and not ({"ghc", "ghc-libs"} & set(package_db[_pkg]["depends"]) and package_db[_pkg]["arch"] != "any"):
                continue
            if ({pkg} | package_db[pkg]["provides"]) & (package_db[_pkg]["depends"] | package_db[_pkg]["makedepends"] | \
                                                        package_db[_pkg]["checkdepends"]):
                reverse_deps[pkg].add(_pkg)
                if args.haskell_check and pkg in HASKELL_DO_NOT_EXPAND:
                    pass
                else:
                    if args.expand and ({pkg} | package_db[pkg]["provides"]) & package_db[_pkg]["depends"]:
                        newpkgs.add(_pkg)
                    if args.only_explicit_make_and_check and pkg not in original_rebuild_list:
                        continue
                    if args.expand_make and ({pkg} | package_db[pkg]["provides"]) & package_db[_pkg]["makedepends"]:
                        newpkgs.add(_pkg)
                    if args.expand_check and ({pkg} | package_db[pkg]["provides"]) & package_db[_pkg]["checkdepends"]:
                        newpkgs.add(_pkg)

    # Handle empty gracefully
    reverse_deps[pkg]
    return newpkgs


# Expand reverse dependencies
while len(pkglist) != len(reverse_deps):
    for pkg in list(pkglist):
        if pkg not in reverse_deps:
            pkglist |= resolve_pkg(pkg)


G.add_nodes_from(reverse_deps.keys())
for dep, pkgs in reverse_deps.items():
    for pkg in pkgs:
        if pkg in pkglist:
            G.add_edge(dep, pkg)


for dep_pair in args.dep.split(","):
    if not dep_pair:
        continue
    pkg, dep = dep_pair.split(":")
    G.add_edge(dep, pkg)


def flatten_frozenset(nodes):
    new_set = set()
    for node in nodes:
        if isinstance(node, (set, frozenset)):
            new_set |= node
        else:
            new_set.add(node)
    return frozenset(new_set)


for cycle in list(nx.algorithms.components.strongly_connected_components(G)):
    if len(cycle) == 1:
        continue
    logger.info("Found circular dependency: " + str(cycle))
    new_pkg = flatten_frozenset(cycle)
    package_db[new_pkg] = dict(depends=set())
    for pkg in cycle:
        package_db[new_pkg]["depends"] |= package_db[pkg]["depends"]
        for _pkg in package_db:
            if pkg in package_db[_pkg]["depends"]:
                package_db[_pkg]["depends"].add(new_pkg)

    for edge in list(G.edges):
        if edge[0] in cycle:
            G.add_edge(new_pkg, edge[1])
        if edge[1] in cycle:
            G.add_edge(edge[0], new_pkg)
    G.remove_nodes_from(cycle)


try:
    while cycles := nx.find_cycle(G):
        for cycle in cycles:
            if len(cycle) == 2 and cycle[0] == cycle[1]:
                logger.warning("Removing edge to resolve self-loop: " + str(cycle))
                G.remove_edge(cycle[0], cycle[1])
            else:
                logger.error("Found circular dependency after resolving: " + str(cycle))
                exit(1)
except nx.NetworkXNoCycle:
    pass


def pass1(pkg):
    NG = nx.DiGraph()
    NG.add_nodes_from(pkg)
    for dep, pkgs in reverse_deps.items():
        for _pkg in pkgs:
            if _pkg in pkg and dep in pkg:
                NG.add_edge(dep, _pkg)
    nocheck_pkg = set()

    while nx.algorithms.components.number_strongly_connected_components(NG) != len(NG):
        found = False
        while True:
            node = random.choice(list(NG))
            if node in HASKELL_REAL_MAKEDEPEND:
                continue
            for rdep in list(NG.successors(node)):
                if node not in package_db[rdep]["depends"]:
                    logger.warning(f"Removing soft dep to solve circular dependency: {node} <- {rdep}")
                    NG.remove_edge(node, rdep)
                    nocheck_pkg.add(rdep)
                    found = True
                    break

            if found:
                break

        if not found:
            logger.error(f"Removing HARD dep to solve circular dependency:  {node} <- {rdep}")
            NG.remove_edge(node, rdep)
            nocheck_pkg.add(rdep)

    pass1 = []
    for _pkg in nx.topological_sort(NG):
        if _pkg in nocheck_pkg:
            pass1.append(_pkg + ":nocheck")
        else:
            pass1.append(_pkg)
    logger.debug("Cycle Solver pass1: " + " ".join(pass1))
    return pass1, NG, nocheck_pkg

def pass2(NG, nocheck_pkg):
    best_pass2 = False
    nocheck_pkg_bak = nocheck_pkg.copy()
    # Try 3 times, use the most optimal result
    for _ in range(3):
        _pass2 = []
        broken_set = set()
        nocheck_pkg = nocheck_pkg_bak.copy()
        loop_detector = 0

        while nocheck_pkg | broken_set:
            for pkg in nocheck_pkg | broken_set:
                if not (package_db[pkg]["depends"] | package_db[pkg]["makedepends"] | package_db[pkg]["checkdepends"]) & broken_set:
                    loop_detector = 0
                    to_break = set([rdep for rdep in reverse_deps[pkg] if pkg in package_db[rdep]["depends"] and rdep in NG])
                    last_to_break = False
                    while to_break != last_to_break:
                        last_to_break = to_break
                        for _pkg in set(to_break):
                            to_break = to_break | set([rdep for rdep in reverse_deps[_pkg] if _pkg in package_db[rdep]["depends"] and rdep in NG])
                    # if not to_break <= (nocheck_pkg | broken_set):
                    #     continue
                    _pass2.append(pkg)
                    broken_set |= to_break
                    if pkg in broken_set:
                        broken_set.remove(pkg)
                    if pkg in nocheck_pkg:
                        nocheck_pkg.remove(pkg)
                    break
            else:
                loop_detector += 1
                if loop_detector > 20:
                    logger.error("Cycle Solver pass2 loop detected, let's abort!")
                    _pass2 = []
                    break

                logger.warning("Cycle Solver pass2 (try " + str(_) + ") found no package to build cleanly, adding more nocheck packages...")
                for pkg in broken_set:
                    if pkg in nocheck_pkg_bak and not package_db[pkg]["depends"] & broken_set:
                        _pass2.append(pkg + ":nocheck")
                        nocheck_pkg.add(pkg)
                        broken_set.remove(pkg)
                        break

        if not _pass2:
            logger.error("Cycle Solver pass2 failed to resolve any packages, retrying from pass1...")
            raise RuntimeError

        if best_pass2 is False or len(_pass2) < len(best_pass2):
            best_pass2 = _pass2.copy()

    logger.debug("Cycle Solver pass2: " + " ".join(best_pass2))
    return best_pass2

result = []
for pkg in nx.topological_sort(G):
    if isinstance(pkg, str):
        result.append(pkg)
    else:
        # Try 3 times for a more optimal result
        best_build_order = False
        for _ in range(3):
            _pass1, NG, nocheck_pkg = pass1(pkg)
            try:
                _pass2 = pass2(NG, nocheck_pkg)
            except RuntimeError:
                logger.warning("Cycle Solver retrying from pass1...")
                continue
            if best_build_order is False or len(_pass1) + len(_pass2) < len(best_build_order):
                if best_build_order is not False:
                    logger.info("Cycle Solver found a better build order (length: %d -> %d)" % (len(best_build_order), len(_pass1) + len(_pass2)))
                best_build_order = _pass1 + _pass2
        result.extend(best_build_order)

print(" ".join(result))