/var/lib/sorcery/modules/libdepengine

     1	#!/bin/bash
     2	#------------------------------------------------------------------------
     3	## @Synopsis Implements sorcery's dependency/trigger tree walking engine.
     4	##
     5	## @Copyright (C) 2005 The Source Mage Team <http://www.sourcemage.org>
     6	##
     7	## In the simple model, without triggers, we color graph nodes (spells)
     8	## white, and as we recursiely visit them, mark them grey. When all of
     9	## a spell's children have been visited, and successfully cast, we
    10	## cast the spell, and mark the node either black:0 or
    11	## black:<non-zero> (eg black:34) for success or failure respectively.
    12	## If a child fails we mark the current node black:<non-zero> and
    13	## return. In the case that we visit a child that is grey, a dependency
    14	## loop is detected, currently we ignore it and build the tail spell anyway,
    15	## in the future we could break optional depends and cast some spell twice.
    16	##
    17	## The more complex model implemented below includes the above, but after
    18	## a spell builds (or fails), it colors itself brown and executes its triggers.
    19	## This is a little more complicated because there could be multiple
    20	## triggers on a single spell and cycles are frequent. If successful, the
    21	## spell marks each trigger as a 'pending trigger' . Then if that spell is
    22	## the last triggerer, the trigger is registered (possibly from another
    23	## spell), and the trigger is not grey (depends cycle, indicating it is
    24	## unsafe to cast the spell) the spell is cast in a special variant of the
    25	## above algorithm. The key difference is that if a grey node is encountered
    26	## (depends cycle), instead of breaking it, the spell gracefully backs
    27	## off and the trigger is left on the pending triggers list while other
    28	## triggers are executed. All the triggers for the spell are executed
    29	## similarly until there are no triggers left, or no progress is made. If
    30	## after all spells are cast there are still pending triggers they are
    31	## built at that point without the graceful cycle handling.
    32	##
    33	#------------------------------------------------------------------------
    34	
    35	
    36	#------------------------------------------------------------------------
    37	## This is the entry point for the dependency engine, it handles top level
    38	## tasks. It invokes the cast_engine on each requested spell and cleans
    39	## up any left-over pending triggers.
    40	#------------------------------------------------------------------------
    41	function depengine_entry_point() {
    42	  $STD_DEBUG
    43	  local spell_list=$1
    44	  local need_cast_list=$2
    45	  local spell pending_list spell_status rc
    46	  local spell_depends spell_sub_depends spell_rsub_depends
    47	
    48	  for spell in $(hash_get_table_fields dep_f_hash); do
    49	    dpgn_set_spell_color $spell white
    50	  done
    51	
    52	  for spell in $spell_list; do
    53	    spell_status=$(dpgn_get_spell_color $spell)
    54	    if [[ $spell_status != white ]] ; then
    55	      debug "libdepengine" "already did $spell"
    56	    else
    57	      depengine_cast_engine $spell
    58	    fi
    59	  done
    60	
    61	  pending_list=$(dpgn_get_all_pending_triggers)
    62	  while [[ $pending_list ]] ; do
    63	    for spell in $pending_list; do
    64	      if dpgn_is_pending_trigger_registered $spell; then
    65	        depengine_cast_engine $spell
    66	        rc=$?
    67	        [[ $rc == 1 ]] && dpgn_unregister_pending_trigger $spell
    68	      fi
    69	    done
    70	    pending_list=$(dpgn_get_all_pending_triggers)
    71	  done
    72	
    73	  if [[ $CAST_PASS == "four" ]]; then
    74	    # Now clean up uncommitted dependency files.
    75	    # During cast it is too early, since things can get re-cast via triggers
    76	    # and then miss the configuration (empty OPTS).
    77	    # See issue #662 in chiliproject.
    78	    debug "libdepengine" "Cleanup of all uncommitted files"
    79	    for spell in $spell_list; do
    80	      get_uncommitted_depends_file      $spell spell_depends
    81	      get_uncommitted_sub_depends_file  $spell spell_sub_depends
    82	      get_uncommitted_rsub_depends_file $spell spell_rsub_depends
    83	      rm -f "$spell_sub_depends" "$spell_rsub_depends" "$spell_depends"
    84	    done
    85	  fi
    86	
    87	  return 0
    88	}
    89	
    90	#------------------------------------------------------------------------
    91	## Top level routine for executing a graph node
    92	## Builds the children, then itself, then executes triggers.
    93	##
    94	## @param Spell to cast
    95	## @param In trigger flag, default 0. If 1 and a depends loop exists back-off and fail gracefully.
    96	#------------------------------------------------------------------------
    97	function depengine_cast_engine() {
    98	  $STD_DEBUG
    99	  local spell=$1
   100	  local in_trigger=${2:-0}
   101	  local org_color=$(dpgn_get_spell_color $spell)
   102	  local rc
   103	
   104	  dpgn_set_spell_color $spell grey
   105	
   106	  recurse_depends $spell $in_trigger
   107	  rc=$?
   108	  if [[ $in_trigger != 0 ]] && [[ $rc == 2 ]] ; then
   109	    dpgn_set_spell_color $spell $org_color
   110	    return 2
   111	  fi
   112	
   113	  spell_status=$(dpgn_get_spell_color $spell)
   114	  if [[ $spell_status == grey ]] && [[ $rc == 0 ]] ; then
   115	    dpgn_cast_spell_front $spell
   116	    rc=$?
   117	  fi
   118	
   119	  dpgn_set_spell_color $spell brown
   120	
   121	  if [[ $rc == 0 ]] ; then
   122	    # if some other spell is going to trigger us *and* it is marked
   123	    # grey, this is a cycle involving triggers (yuck!)
   124	    # when that happens dont execute $spell's triggers
   125	    # because it will be re-triggered
   126	    local grey_triggerer=0
   127	    local hash_triggerers
   128	    hash_get_ref trg_r_hash $spell:cast_self hash_triggerers
   129	    for triggerer in $hash_triggerers; do
   130	      # note that $spell's status is grey
   131	      [[ $triggerer == $spell ]] && continue
   132	      hash_get_ref state_hash $triggerer child_status
   133	      if [[ $child_status == grey ]] ; then
   134	        debug "libdepengine" "$spell has a $child_status triggerer on $triggerer!"
   135	        grey_triggerer=1
   136	        break
   137	      fi
   138	    done
   139	    if [[ $grey_triggerer == 0 ]] ; then
   140	      execute_triggers $spell 0
   141	    fi
   142	  else
   143	    # execute triggers that were delayed because of us
   144	    # despite the fact that we failed
   145	    execute_triggers $spell 1
   146	  fi
   147	
   148	  dpgn_set_spell_color $spell black:$rc
   149	
   150	  return $rc
   151	}
   152	
   153	#------------------------------------------------------------------------
   154	## Iterative recursive step. Build each of the spell's dependencies.
   155	## @param Spell
   156	## @param In trigger flag (optional) if 1, then back off more readily in the event of a dependency loop.
   157	## @global MINUS_K if 'yes', then act like make -k and continue building
   158	## @global dependent spells even if another one fails.
   159	##
   160	#------------------------------------------------------------------------
   161	function recurse_depends() {
   162	  $STD_DEBUG
   163	  local spell=$1
   164	  local in_trigger=${2:-0}
   165	  local rc=0
   166	  local hash_childs
   167	  hash_get_ref dep_f_hash $spell hash_childs
   168	  for child in $hash_childs; do
   169	
   170	    # check if any of our dependencies failed while we weren't looking
   171	    # if one did, bail out, if MINUS_K is set then skip this and build
   172	    # everything we can
   173	    if [[ $MINUS_K == no ]] ; then
   174	      local hash_childs2
   175	      hash_get_ref dep_f_hash $spell hash_childs2
   176	      for _child in $hash_childs2; do
   177	        case $(dpgn_get_spell_color $_child) in
   178	          black:0)
   179	            :
   180	          ;;
   181	          black:*)
   182	            debug libdepengine "$spell already had a failed dep on $_child"
   183	            return 1
   184	          ;;
   185	        esac
   186	      done
   187	    fi
   188	
   189	    child_status=$(dpgn_get_spell_color $child)
   190	    case $child_status in
   191	      white)
   192	        tmp_rc=0
   193	        if list_find "$need_cast_list" $child; then
   194	          depengine_cast_engine $child $in_trigger
   195	          tmp_rc=$?
   196	          if [[ $tmp_rc != 0 ]] ; then
   197	            rc=$tmp_rc
   198	            [[ $MINUS_K == no ]] && break
   199	          fi
   200	        fi
   201	      ;;
   202	      grey)
   203	       if [[ $in_trigger != 0 ]] ; then
   204	         debug "libdepengine" "found grey depend from trigger $spell -> $child"
   205	         return 2
   206	       else
   207	         debug "libdepengine" "detected a dependency loop $spell -> $child"
   208	       fi
   209	      ;;
   210	      brown)
   211	        debug "libdepengine" "found brown depend $spell -> $child"
   212	      ;;
   213	      black:0)
   214	        debug "libdepengine" "$child already built properly, continuing"
   215	      ;;
   216	      black:*)
   217	        debug "libdepengine" "$child failed, minus_k is $MINUS_K"
   218	        rc=1
   219	        [[ $MINUS_K == no ]] && break
   220	      ;;
   221	    esac
   222	  done
   223	  # build anything that will trigger us. this helps keep the order right.
   224	  # most of the time, we'll also depend on the triggerer, this just
   225	  # catches those cases where we dont, and doesn't worry too much
   226	  # about a failure
   227	  if [[ $rc == 0 ]] ; then
   228	    local hash_triggerers
   229	    hash_get_ref trg_r_hash $spell:cast_self hash_triggerers
   230	    for triggerer in $hash_triggerers; do
   231	      trgrr_status=$(dpgn_get_spell_color $triggerer)
   232	      if [[ "$trgrr_status" == "white" ]] ; then
   233	        if list_find "$need_cast_list" $triggerer; then
   234	          depengine_cast_engine $triggerer $in_trigger
   235	        fi
   236	      fi
   237	    done
   238	  fi
   239	  return $rc
   240	}
   241	
   242	#------------------------------------------------------------------------
   243	## Attempt to run all this spell's triggers. Some triggers may not be
   244	## runable at this time, or it may be better to run them later.
   245	#------------------------------------------------------------------------
   246	function execute_triggers() {
   247	  $STD_DEBUG
   248	  local spell=$1
   249	  local failed=$2
   250	  local trigger rc
   251	  local trg_array trg_action trg_target stuff trg_color
   252	
   253	  function execute_triggers_sub() {
   254	    trigger=$1
   255	    explode "$trigger" : trg_array
   256	    trg_target=${trg_array[0]}
   257	    trg_action=${trg_array[1]}
   258	    # get the other spells that trigger this action
   259	    trg_color=$(dpgn_get_spell_color $trg_target)
   260	
   261	    # do trigger specific stuff, set needs_register to 1 if
   262	    # casting is needed
   263	    if [[ $failed == 0 ]]; then
   264	      local needs_register=""
   265	
   266	      if [[ $trg_action == cast_self ]] ; then
   267	        if ! [[ $CAST_PASS == three ]] ; then
   268	          message "${MESSAGE_COLOR}Queued cast_self on" \
   269	                  "${SPELL_COLOR}$trg_target${DEFAULT_COLOR}."
   270	        fi
   271	        needs_register=1
   272	      elif [[ $trg_action == check_self ]] ; then
   273	        if [[ $trg_color != brown ]] ; then
   274	          if [[ $CAST_PASS == three ]] ; then
   275	            needs_register=1
   276	          else
   277	            message "${MESSAGE_COLOR}Performing check_self on" \
   278	                    "${SPELL_COLOR}$trg_target${DEFAULT_COLOR}"
   279	            if cleanse --nofix_quick "$trg_target"; then
   280	              echo "${trg_target}" >> $CHECK_TRIGGERS_SUCCESS
   281	            else
   282	              echo "${trg_target}" >> $CHECK_TRIGGERS_FAILURE
   283	              needs_register=1
   284	            fi
   285	          fi
   286	        fi
   287	      elif [[ $CAST_PASS != three ]] ; then
   288	        # run any other trigger besides the two above
   289	        # but not if we're summoning
   290	        local action=cast
   291	        do_trigger "$trg_target:$spell:on_cast:$trg_action"
   292	      fi
   293	
   294	      # a brown trigger is a loop, drop it
   295	      if [[ $needs_register ]] && [[ $trg_color != brown ]] ; then
   296	        dpgn_register_pending_trigger $trg_target
   297	      fi
   298	    fi
   299	
   300	    # if there are no white triggerers, we are the last triggerer
   301	    local last=1
   302	    local triggerers
   303	    hash_get_ref trg_r_hash $trg_target:$trg_action triggerers
   304	    for triggerer in $triggerers; do
   305	      [[ $triggerer == $spell ]] && continue
   306	      if [[ $(dpgn_get_spell_color $triggerer) == white ]] ; then
   307	        last=0
   308	        break
   309	      fi
   310	    done
   311	
   312	    # decide if the trigger should be executed
   313	    if [[ $last == 1 ]] &&
   314	          dpgn_is_pending_trigger_registered $trg_target &&
   315	          [[ $trg_color != grey ]] ; then
   316	      list_add stuff $trg_target
   317	    fi
   318	  }
   319	  iterate execute_triggers_sub $'\n' "$(hash_get trg_f_hash $spell)"
   320	
   321	  local curr_list=$stuff
   322	  local prev_list=""
   323	  local item
   324	  # execute triggers, so may not be executable so delay them and try
   325	  # again. Give up when there are no triggers left, or no progress
   326	  # is made. Left-over triggers are cleaned up at the end.
   327	  while [[ $curr_list ]] && [[ "$curr_list" != "$prev_list" ]] ; do
   328	    prev_list="$curr_list"
   329	    for item in $prev_list; do
   330	      if dpgn_is_pending_trigger_registered $item; then
   331	        depengine_cast_engine $item 1
   332	        rc=$?
   333	        if [[ $rc == 2 ]] ; then
   334	          list_add curr_list $item
   335	        fi
   336	      fi
   337	    done
   338	  done
   339	  return 0
   340	}
   341	
   342	### helpers ####
   343	#------------------------------------------------------------------------
   344	## frontend to cast spells, unregisters pending triggers if any
   345	#------------------------------------------------------------------------
   346	function dpgn_cast_spell_front() {
   347	  if ! [[ $CAST_PASS ]] ; then
   348	    message "ERROR: Missing cast pass variable!!"
   349	    exit 1
   350	  fi
   351	
   352	  if [[ $COMPILE ]] || dpgn_is_pending_trigger_registered $1; then
   353	    args="-c "
   354	  fi
   355	
   356	  if [[ $CAST_PASS == three ]] ; then
   357	    # pass four can finish first if there are triggers that aren't run
   358	    # or spells fail.
   359	    if test -f $TMP_DIR/pass_four.done; then
   360	      message "Pass four completed! bailing out!!!"
   361	      # we're in a seperate bash subshell, exiting here is okay
   362	      exit
   363	    fi
   364	    bash $SAFE_CAST $args $1 &>/dev/null
   365	  else
   366	    bash $SAFE_CAST $args $1
   367	  fi
   368	  local rc=$?
   369	
   370	  dpgn_unregister_pending_trigger $1
   371	  return $rc
   372	}
   373	
   374	#------------------------------------------------------------------------
   375	## set the spell color
   376	#------------------------------------------------------------------------
   377	function dpgn_set_spell_color() {
   378	  hash_put state_hash $1 $2
   379	}
   380	#------------------------------------------------------------------------
   381	## get the spell color
   382	#------------------------------------------------------------------------
   383	function dpgn_get_spell_color() {
   384	  hash_get state_hash $1
   385	}
   386	
   387	#------------------------------------------------------------------------
   388	## Mark this spell as a pending trigger
   389	#------------------------------------------------------------------------
   390	function dpgn_register_pending_trigger() {
   391	  hash_put pending_triggers $1 1
   392	}
   393	
   394	#------------------------------------------------------------------------
   395	## determine if a trigger is pending or not
   396	#------------------------------------------------------------------------
   397	function dpgn_is_pending_trigger_registered() {
   398	  local pending
   399	  hash_get_ref pending_triggers $1 pending
   400	  [[ $pending == 1 ]]
   401	}
   402	
   403	#------------------------------------------------------------------------
   404	## mark spell as no longer needing a trigger
   405	#------------------------------------------------------------------------
   406	function dpgn_unregister_pending_trigger() {
   407	  hash_unset pending_triggers $1
   408	}
   409	
   410	#------------------------------------------------------------------------
   411	## return all the pending triggers
   412	#------------------------------------------------------------------------
   413	function dpgn_get_all_pending_triggers() {
   414	  hash_get_table_fields pending_triggers
   415	}
   416	
   417	#------------------------------------------------------------------------
   418	##=back
   419	##
   420	##=head1 LICENSE
   421	##
   422	## This software is free software; you can redistribute it and/or modify
   423	## it under the terms of the GNU General Public License as published by
   424	## the Free Software Foundation; either version 2 of the License, or
   425	## (at your option) any later version.
   426	##
   427	## This software is distributed in the hope that it will be useful,
   428	## but WITHOUT ANY WARRANTY; without even the implied warranty of
   429	## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   430	## GNU General Public License for more details.
   431	##
   432	## You should have received a copy of the GNU General Public License
   433	## along with this software; if not, write to the Free Software
   434	## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   435	##
   436	#------------------------------------------------------------------------