dagpkg: implement a better sorting algorithm

1 files 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 <fauno@parabola.nu>
+#           Michał Masłowski <mtjm@mtjm.eu>
 #
 # 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")"