libdepengine: add short cut for grey dependency loops

The repeated dive into the same branches of the dependency tree
can be very wasteful. Lots of calls to recurse_depends can be
avoided when it is already known that a spell recursion will
turn up aborted because of a dependency loop (grey dependency).

This assumes that the situation only possibly changes when a spell
is actually cast.

I am not sure if my analysis is correct. I had the rather fatal
situation of a sorcery rebuild spinning for hours in a rendering
of dependency hell trying to decide what to build next after some
successful initial casts. This patch avoids that situation at least.

I also for some time whitnessed an immense delay on removing dependees
of a failed spell. I am not sure if this is now gone or could still
reappear. The whole dependency engine needs an overhaul in all its
wastefulness.

1 files changed, 24 insertions, 5 deletions

diff --git a/var/lib/sorcery/modules/libdepengine b/var/lib/sorcery/modules/libdepengine
index 8644ab57..02e9b329 100755
--- a/var/lib/sorcery/modules/libdepengine
+++ b/var/lib/sorcery/modules/libdepengine
@@ -45,6 +45,11 @@ depengine_entry_point() {
   local spell pending_list spell_status rc
   local spell_depends spell_sub_depends spell_rsub_depends
 
+  # Shortcut for avoiding grey dependency loop detection,
+  # see depengine_cast_engine(). Empty list to begin with.
+  # This is a global variable!
+  dpgn_grey_loop_spells=
+
   for spell in $(hash_get_table_fields dep_f_hash); do
     dpgn_set_spell_color $spell white
   done
@@ -101,14 +106,28 @@ depengine_cast_engine() {
   local org_color=$(dpgn_get_spell_color $spell)
   local rc
 
-  dpgn_set_spell_color $spell grey
-
-  recurse_depends $spell $in_trigger
-  rc=$?
-  if [[ $in_trigger != 0 ]] && [[ $rc == 2 ]] ; then
+  # Dependency recursion can hit a grey dependency loop many times
+  # and waste a lot of CPU cycles on that. The shortcut turns a pathological
+  # seemingly endless loop during a whole-system rebuild (about 1000 spells)
+  # into a non-issue.
+  if [[ $in_trigger != 0 ]] && list_find "$looped_spell_list" $spell; then
+    debug "libdepengine" "grey loop shortcut for $spell"
     dpgn_set_spell_color $spell $org_color
     return 2
+  else
+    dpgn_set_spell_color $spell grey
+    recurse_depends $spell $in_trigger
+    rc=$?
+    if [[ $in_trigger != 0 ]] && [[ $rc == 2 ]] ; then
+      debug "libdepengine" "got a grey loop for $spell"
+      dpgn_set_spell_color $spell $org_color
+      list_add looped_spell_list $spell
+      return 2
+    fi
   fi
+  # The grey loop detection shall start fresh on the next round of recursions
+  # once an actual action takes place that may change the situation.
+  dpgn_grey_loop_spells=
 
   spell_status=$(dpgn_get_spell_color $spell)
   if [[ $spell_status == grey ]] && [[ $rc == 0 ]] ; then