/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 #------------------------------------------------------------------------