From 3ae97f07be56a2669279ae6c5b0efe403d3ba313 Mon Sep 17 00:00:00 2001
From: Erich Eckner <git@eckner.net>
Date: Wed, 3 May 2017 13:08:32 +0200
Subject: breaking of loops optimized

---
 bin/get-assignment      | 49 ++++++++++++++++++++++++++++++++-----------------
 bin/get-package-updates | 12 ++++++++++++
 conf/default.conf       |  1 +
 3 files changed, 45 insertions(+), 17 deletions(-)

diff --git a/bin/get-assignment b/bin/get-assignment
index a35e415..69bfb3f 100755
--- a/bin/get-assignment
+++ b/bin/get-assignment
@@ -22,6 +22,7 @@ mkdir -p "${work_dir}/package-states"
 
 hand_out_assignment() {
 
+  # locked packages won't be handed out
   if [ -f "${work_dir}/package-states/$1.$2.$3.locked" ]; then
     return 0
   fi
@@ -29,6 +30,13 @@ hand_out_assignment() {
   echo "$1 $2 $3"
   echo "${SSH_CLIENT%% *}" > "${work_dir}/package-states/$1.$2.$3.locked"
 
+  # lock every loop this package breaks
+  grep "^${1//./\\.}\$" "${work_dir}/build-list.loops/"loop_* | \
+    cut -d: -f1 | \
+    tee -a "${work_dir}/package-states/$1.$2.$3.locked" | \
+    sed 's|$|.locked|' | \
+    xargs -rn1 touch
+
   rm -f "${lock_file}"
   exit 0
 
@@ -52,7 +60,7 @@ while read -r package git_revision repository; do
 
   if [ -f "${work_dir}/package-states/${package}.${git_revision}.${repository}.locked" ];
   then
-    if [ "${SSH_CLIENT%% *}" = "$(cat "${work_dir}/package-states/${package}.${git_revision}.${repository}.locked")" ]; then
+    if [ "${SSH_CLIENT%% *}" = "$(head -n1 "${work_dir}/package-states/${package}.${git_revision}.${repository}.locked")" ]; then
       num_jobs=$[${num_jobs}+1];
     fi
   else
@@ -90,23 +98,30 @@ while read -r package git_revision repository; do
 
 done < "${work_dir}/build-list"
 
-# Find first package which breaks a loop and is not locked
-
-if [ -s "${work_dir}/tsort.error" ]; then
-
-  grep -A1 '^tsort: -: input contains a loop:$' "${work_dir}/tsort.error" | \
-    cut -d' ' -f2 | \
-    grep -v -- '^-:$' | \
-    while read package; do
-
-      grep "^${package} " "${work_dir}/build-list" | \
-        while read -r package git_revision repository; do
-          hand_out_assignment "${package}" "${git_revision}" "${repository}"
-        done
-
-    done
+# Find package (of all packages which are not locked)
+# which breaks the most unlocked loops
+
+for package in $(
+  ls "${work_dir}/build-list.loops/"loop_* | \
+    sed 's|\.locked$||' | \
+    sort | \
+    uniq -u | \
+    # now, we have all unlocked loops
+    xargs cat | \
+    # now, we have their content
+    sort | \
+    uniq -c | \
+    sort -k1nr,1 | \
+    awk '{print $2}'
+  ); do
+
+  if assignment="$(grep "^${package} " "${work_dir}/build-list")"; then
+    hand_out_assignment ${assignment}
+  else
+    echo "'${package}' ..."
+  fi
 
-fi
+done
 
 # Remove the lock file
 
diff --git a/bin/get-package-updates b/bin/get-package-updates
index ac7e905..f6aef31 100755
--- a/bin/get-package-updates
+++ b/bin/get-package-updates
@@ -196,11 +196,23 @@ echo 'Now actually sort it.'
   awk '{print $4 " " $6 " " $7}' > \
   "${work_dir}/build-list.new.new"
 
+rm -f "${work_dir}/build-order.loops/*"
+
 if [ -s "${work_dir}/tsort.error" ]; then
   >&2 echo 'WARNING: There is a dependency cycle!'
   >&2 cat "${work_dir}/tsort.error"
   >&2 echo
   >&2 echo 'I will continue anyway.'
+  # save loops in separate files each, so breaking them is easier
+  awk '
+    /^tsort: \S+: input contains a loop:$/{
+      n++;
+      getline
+    }
+    {
+      print $2 >"'"${work_dir}"'/build-list.loops/loop_" n
+    }
+    ' "${work_dir}/tsort.error"
 else
   rm "${work_dir}/tsort.error"
 fi
diff --git a/conf/default.conf b/conf/default.conf
index 108b517..8482d81 100755
--- a/conf/default.conf
+++ b/conf/default.conf
@@ -33,6 +33,7 @@ max_parallel_build_per_client=2
 mkdir -p "${work_dir}"
 touch "${work_dir}/build-list"
 touch "${work_dir}/deletion-list"
+mkdir -p "${work_dir}/build-list.loops"
 
 for repo in "${!repo_paths[@]}"; do
 
-- 
cgit v1.2.3