From fb5ee96054490596e4febdf459e5f5bd1b70e807 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Mas=C5=82owski?= Date: Thu, 9 Jan 2014 00:49:21 -0300 Subject: dagpkg: implement a better sorting algorithm --- dagpkg | 127 +++++++++++++++++++++++++++++++++-------------------------------- 1 file changed, 65 insertions(+), 62 deletions(-) diff --git a/dagpkg b/dagpkg index b4ef9e1..290c775 100755 --- a/dagpkg +++ b/dagpkg @@ -4,6 +4,7 @@ # them in topological order # # (c) 2014 Nicolás Reynolds +# Michał Masłowski # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by @@ -30,7 +31,6 @@ source $XDG_CONFIG_HOME/.makepkg.conf &>/dev/null || true # End inmediately but print an useful message trap_exit() { term_title "error!" - test ${depth} -eq 0 && error "(%s) %s (leftovers on %s)" \ "${0##*/}" "$@" "${temp_dir}" exit 1 @@ -41,29 +41,28 @@ trap 'trap_exit "TERM signal caught. Exiting..."' TERM HUP QUIT trap 'trap_exit "Aborted by user! Exiting..."' INT trap 'trap_exit "An unknown error has occurred. Exiting..."' ERR -# Source this PKGBUILD, if it doesn't exist, exit -if ! source ./PKGBUILD &>/dev/null ; then - error "No PKGBUILD in %s" "$PWD" - exit 1 -fi +source_pkgbuild() { + # Source this PKGBUILD, if it doesn't exist, exit + if ! source ./PKGBUILD &>/dev/null ; then + error "No PKGBUILD in %s" "$PWD" + exit 1 + fi -# Save resources -unset pkgdesc arch license groups backup install md5sums sha1sums \ - sha256sums source options &>/dev/null + # Save resources + unset pkgdesc arch license groups backup install md5sums sha1sums \ + sha256sums source options &>/dev/null -unset build package &>/dev/null + unset build package &>/dev/null -for _pkg in ${pkgname[@]}; do - unset package_${_pkg} &>/dev/null || true -done + for _pkg in ${pkgname[@]}; do + unset package_${_pkg} &>/dev/null || true + done -# This is the name of the package -name="${pkgbase:-${pkgname[0]}}" + # This is the name of the package + name="${pkgbase:-${pkgname[0]}}" +} -# The name of the previous package -prev="${3}" -depth="${2:-0}" -let next=${depth}+1 || true +source_pkgbuild # A temporary work dir and log file temp_dir="${1:-$(mktemp -dt ${name}-testpkg-XXXX)}" @@ -80,38 +79,42 @@ get_fullver() { } -# If it's already built we don't bother -is_built ${pkgname[0]} $(get_fullver ${epoch:-0} ${pkgver} ${pkgrel}) && -exit +# Mark array for DFS-based topological sort. See +# https://en.wikipedia.org/wiki/Topological_sort for an explanation of +# the algorithm. Key: package name, value: 0 for unvisited package, 1 +# during visit, 2 after visit. +declare -A marks -echo "${arch[@]}" | grep -qw "$CARCH" || warning "%s isn't ported to %s yet" ${name} ${CARCH} +# Visit a PKGBUILD for graph building. +visit_pkgbuild() { + # The name of the previous package + prev="${1}" -# If the envvar I contains this package, ignore it and exit -echo "$I" | grep -qw "$name" && -msg2 "%s ignored" ${name} && -exit + local name + source_pkgbuild -msg "%s (%s)" ${name} ${prev} + # Detect cycle or already visited package + case "${marks[$name]:-0}" in + 1) msg2 "cycle found with %s depending on %s" $prev $name + exit 1;; + 2) return;; + esac -build=false -if [ ! -z "${1}" -a ${depth} -eq 0 ]; then - build=true -fi + # If it's already built we don't bother + is_built ${pkgname[0]} $(get_fullver ${epoch:-0} ${pkgver} ${pkgrel}) && + return -# If we specified a work dir on the cli it means we want to skip -# dependency graph creation and jump to build whatever is there -if ! ${build}; then + echo "${arch[@]}" | grep -qw "$CARCH" || warning "%s isn't ported to %s yet" ${name} ${CARCH} - # Export a pair of current and previous package to get a list of graph - # edges - echo -e "${name}\t${prev:--}" >>${log} + # If the envvar I contains this package, ignore it and exit + echo "$I" | grep -qw "$name" && + msg2 "%s ignored" ${name} && + return - # Infinite loop detection, if the inverted pair current+prev was - # already seen, skip - if grep -q "${prev}[[:space:]]${name}" ${log} ; then - msg2 "infinite loop %s<->%s" $name $prev - exit - fi + msg "%s (%s)" ${name} ${prev} + + # Mark the package as being visited + marks[$name]=1 # Recurse into dependencies for d in ${depends[@]} ${makedepends[@]}; do @@ -124,37 +127,37 @@ if ! ${build}; then # Skip if not available test -z "$w" && continue - # revisited edge detection - # we use the basename of the package dir as pkgbase to avoid - # recalling an edge using one of the other pkgname's - if grep -q "^${w##*/}[[:space:]]" ${log} ; then - msg2 "edge %s already visited" ${d} - # add edge anyway but avoid reprocessing - echo -e "${w##*/}\t${name}" >>${log} - continue - fi - # Go to this dir pushd $w &>/dev/null - # Run this same command giving work dir, depth and previous package - $0 ${temp_dir} ${next} ${name} + visit_pkgbuild "$name" popd &>/dev/null done + + # Mark the package as finished + marks[$name]=2 + # Append it to the reversed list of packages to build. + echo "$name" >> "${log}" +} + +# If we specified a work dir on the cli it means we want to skip +# dependency graph creation and jump to build whatever is there +if [ -z "${1}" ]; then + # Visit the root PKGBUILD to make the graph. + visit_pkgbuild "" else msg "Resuming build..." fi -# end here if we're not the first package -test ${depth} -ne 0 && exit - # enter work dir pushd "${temp_dir}" &>/dev/null -# TODO do something when loops are discovered (fail? skip?) -tsort ${log} | head -n-1 | tac | nl | tac | while read order pkg; do +nl ${log} | while read order pkg; do # skip if already built - test -f "${pkg}/built_ok" && continue + if test -f "${pkg}/built_ok"; then + warning "tried to build %s twice" "%{pkg}" + continue + fi # where's this package? w="$(toru-where "$pkg")" -- cgit v1.2.3-2-g168b