#!/bin/bash
#---------------------------------------------------------------------
## @Synopsis Functions for dealing with dependencies as a non-cyclic directed graph. Since that's such a mouthful, it will simply be referred to as a tree, even though it's not.
## @Copyright (C) 2002 The Source Mage Team <http://www.sourcemage.org>
## A spell is represented as a node containing some pieces of data
## seperated by colons.
## spell:dependent spell:on/off:type:casting_flag:is_a_target_flag
## @Contributers Chris Brien (christopher_brien@hotmail.com)
## @Contributers Paul Mahon (pmahon@sourcemage.org)
#---------------------------------------------------------------------

#
# conceptual function call tree...perhaps this will enlighten sorcery
# students..
#
# compute_uninstalled_depends (the entry point)
#   -> for each spell (this list grows during processing)
#     -> run PREPARE
#     -> run CONFIGURE
#     -> run DEPENDS
#       -> depends|runtime_depends <spell> (external)
#         -> work_depends_spell
#           -> private_common_depends -> libstate.add_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#       -> optional_depends|suggest_depends <spell> (external)
#         -> work_optional_depends_spell
#           -> query
#           -> private_common_depends -> libstate.add_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#       -> depends|runtime_depends <provider> (external)
#         -> work_depends_provider
#           -> select provider
#           -> private_common_depends -> libstate.add_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#       -> optional_depends|suggest_depends <provider> (external)
#         -> work_optional_depends_provider
#           -> select provider
#           -> private_common_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#     -> private_add_depends
#       -> update hash tables and lists from NEW_DEPENDS
#
# in other words, for every spell run its external files
# and then deal with their callbacks (depends and optional_depends)
# each of those calls eventually arrives at a dependency rule
# which is stored somewhere through libstate calls , and in an internal
# variable (NEW_DEPENDS). After we finish all the files we bundle up
# our new information and move to the next spell.
#

# Surprise env vars:
# SPELL: this is actually locally defined somewhere up the call stack
#  but from most function's point of view it should be there...
# COMPILE: set in cast. It means that the main spells should be recompiled
# RECONFIGURE: set in cast. I means that the info in the state depends should
#  be disregarded and replaced.
# PRETEND_NOT_INSTALLED: set here. It is a list of spells that are to be
#  recompiled, so they should not be treated as installed.
# CAST_HASH: The name of the hast table to put spells and dependencies
#  that are to be cast (only used in this lib)
# BACK_HASH: reverse of CAST_HASH will be used to handle failures
#  more gracefully someday...
# CANNOT_CAST: The name of the hash table to put spells that cannot be cast
#  and the reason why. Usualy because they are exiled or don't exist
#  (only used in this lib)


######################BEGIN CALLS TO OUTSIDE WORLD########################

#---------------------------------------------------------------------
## Run the spell's PREPARE script if it exists
## @param Spell to prepare
## @Globals SCRIPT_DIRECTORY
#---------------------------------------------------------------------
run_prepare()
{
  local SPELL=$1

  debug "cast" "run_prepare() - SPELL = $SPELL  SCRIPT_DIRECTORY = $SCRIPT_DIRECTORY"

  depends_message  "${SPELL}" "preparing environment..."

  # these are here so you can source section/grimoire level scripts in
  # PREPARE, which by definition runs before the spell is loaded
  # and they are defined as usual (see bug 8329)
  codex_get_spell_paths "$SCRIPT_DIRECTORY"

  local PROTECT_SORCERY=yes
  run_spell_file PREPARE prepare
  rc=$?
  return $rc
}

#---------------------------------------------------------------------
## This will be home to all "other" questions we are supposed to ask about
## during this phase of things, right now its a placeholder
## @param Spell
#---------------------------------------------------------------------
run_other() {
  local SPELL=$1
  # ask the questions about xinetd/initd script installation
  persistent_load &&
  query_services &&
  query_custom_cflags &&
  query_conflicts &&
  run_security &&
  persistent_save ||
  {
    persistent_clear
    log_failure_reason run_other #remove this if all the previous callers get one
    return 1
  }
#ask about other stuff

}

#---------------------------------------------------------------------
## Run the spell's CONFIGURE script if it exists
## @param Spell to configure
#---------------------------------------------------------------------
run_configure() {
  local SPELL=$1
  debug "cast" "run_configure() - SCRIPT_DIRECTORY = $SCRIPT_DIRECTORY"

  function run_configure_msg() {
    depends_message  "${SPELL}" "running configuration..."
  }

  local PROTECT_SORCERY=yes
  run_spell_file CONFIGURE configure run_configure_msg
  rc=$?
  return $rc
}

#---------------------------------------------------------------------
## Run a spell's DEPENDS if it exists
## @param Spell
#---------------------------------------------------------------------
run_depends() {
  local SPELL=$1
  debug "cast" "run_depends() - SCRIPT_DIRECTORY = $SCRIPT_DIRECTORY"

  function run_depends_msg() {
    depends_message  "${SPELL}" "checking dependencies..."
  }

  local PROTECT_SORCERY=yes
  run_spell_file DEPENDS depends run_depends_msg
  rc=$?
  return $rc
}

#---------------------------------------------------------------------
## Run a spell's UP_TRIGGERS if it exists
## @param Spell
#---------------------------------------------------------------------
run_up_triggers() {
  local SPELL=$1
  debug "cast" "run_up_triggers() - SCRIPT_DIRECTORY = $SCRIPT_DIRECTORY"

  function run_up_triggers_msg() {
    depends_message  "${SPELL}" "checking for reverse triggers..."
  }
  local PROTECT_SORCERY=yes
  run_spell_file UP_TRIGGERS up_triggers run_up_triggers_msg
  rc=$?
  return $rc
}

#---------------------------------------------------------------------
## process any sub-depends the current spell is going to provide
## These come from the live sub-depends table and from spells that
## have already been processed
#---------------------------------------------------------------------
run_our_sub_depends() {
  $STD_DEBUG
  local sub_depends pair
  # do all sub-depends on us from live-table first, they get priority
  # in case there is a conflict
  for triple in $(search_sub_depends "$SUB_DEPENDS_STATUS" '.*' "$SPELL") ; do
    # parse the line out, eventually these silly variable expansions should
    # be in functions or benchmarked against explode
    tmp=${triple%:*};
    requester=${tmp%:*};
    sub_dependee=${tmp#*:};
    sub_depends=${triple##*:}

    # if the requester has been processed skip any sub-depends its
    # previous instance requested, bug 11865
    local hash_depends_looked_at
    hash_get_ref "depends_looked_at" "$requester" hash_depends_looked_at
    [[ $hash_depends_looked_at == done ]] && continue

    process_sub_depends "$requester" "$sub_dependee" "$sub_depends" || return 1
  done

  # do all sub-depends from sub_dep_r_hash (things that we provide)
  for pair in $(hash_get sub_dep_r_hash $SPELL) ; do
    requester=${pair%:*}
    sub_depends=${pair#*:}

    process_sub_depends "$requester" "$SPELL" "$sub_depends" || return 1
  done
}

#---------------------------------------------------------------------
## run any sub-depends that we requested on behalf of the sub-dependee
#---------------------------------------------------------------------
run_other_sub_depends() {
  $STD_DEBUG
  local this_spell=$1
  local SPELL sub_dependee sub_depends pair
  local sub_dependee_looked_at
  # do all sub-depends from sub_dep_f_hash (things we request)
  for pair in $(hash_get sub_dep_f_hash $this_spell) ; do
    # FIXME, do this one spell at a time, rather than in whatever order we
    # see them it will reduce the number of run_details
    sub_dependee=${pair%:*}
    sub_depends=${pair#*:}
    hash_get_ref depends_looked_at $sub_dependee sub_dependee_looked_at
    if [[ $sub_dependee_looked_at == done ]]; then
      # load the spell and clear out any special variables
      SPELL=$sub_dependee
      run_details
      local NEW_SUB_DEPENDEES=""
      # afk 5-28-06: bash 3.0 breaks local foo=(), have to make this two lines
      local NEW_DEPENDS; NEW_DEPENDS=()
      local NEW_RUNTIME_DEPENDS; NEW_RUNTIME_DEPENDS=()
      process_sub_depends "$this_spell" "$sub_dependee" "$sub_depends" ||
      return 1

      # this is needed in case processing the sub-depends added a depends
      # isnt this fun?
      private_add_depends
    fi
  done
}

#---------------------------------------------------------------------
## Run a spell's SUB_DEPENDS file for a specific sub-depends.
## This is idempotent, if a sub-depends has already been processed it will
## not run the SUB_DEPENDS file again.
##
## Expects the sub-dependee to be loaded.
## If the spell does not have a SUB_DEPENDS file, it is a failure.
#---------------------------------------------------------------------
process_sub_depends() {
  $STD_DEBUG
  local requester=$1
  local sub_dependee=$2
  local sub_depends=$3
  local PROTECT_SORCERY=yes

  if test -x $SCRIPT_DIRECTORY/SUB_DEPENDS; then
    if ! list_find "$(hash_get processed_sub_depends $sub_dependee)" "$sub_depends"; then
      local rc=0

      local THIS_SUB_DEPENDS=$sub_depends
      local PROCESSED_SUB_DEPENDS
      hash_get_ref processed_sub_depends $sub_dependee PROCESSED_SUB_DEPENDS
      run_spell_file SUB_DEPENDS sub_depends || return 1
      hash_append processed_sub_depends $sub_dependee $sub_depends
    else
      debug libdepends "SUB_DEPENDS: $sub_dependee needs to provide $sub_depends but has already been processed"
    fi
  else
    message "${PROBLEM_COLOR}Sub-dependency of" \
      "${SPELL_COLOR}$requester${PROBLEM_COLOR} on" \
      "${SPELL_COLOR}$sub_dependee${PROBLEM_COLOR}" \
      "cannot be processed due to missing SUB_DEPENDS!$DEFAULT_COLOR"
    # sub-depends file doesnt exist, something messed up somewhere
    return 1
  fi
  # add the information to the uncommitted depends file
  local sub_depends_file rsub_depends_file
  get_uncommitted_sub_depends_file "$sub_dependee" sub_depends_file || return 1
  add_sub_depends "$sub_depends_file" "$requester" "$sub_dependee" "$sub_depends"
  get_uncommitted_rsub_depends_file "$requester" rsub_depends_file || return 1
  add_sub_depends "$rsub_depends_file" "$requester" "$sub_dependee" "$sub_depends"
}

######################END CALLS TO OUTSIDE WORLD########################

__comp_depends_aux() {
  #$2==hash table to fill
  touch "$DEPENDS_STATUS" "$SPELL_STATUS" >/dev/null 2>&1
  lock_file "$DEPENDS_STATUS"
  lock_file "$SPELL_STATUS"
  while read a b; do
    hash_put "$2" "$a" "$b"
  done < <(
    awk -F: -v reverse="$1" \
	-v pattern="required|optional${3:+|runtime|suggest}" \
	-v status="${4:-on}" '
	FNR == 1 { file++ }
	file == 1 {
		if ($3 == status && $4 ~ pattern) {
			# Remove provider name
			sub(/[(].*/, "", $2)
			if (reverse)
				depmap[$2] = depmap[$2] " " $1 " "
			else	depmap[$1] = depmap[$1] " " $2 " "
		}
		next
	}
	{
		if ($3 == "installed" || $3 == "held")
			print $1, depmap[$1]
	}
    ' "$DEPENDS_STATUS" "$SPELL_STATUS"
  )
  unlock_file "$DEPENDS_STATUS"
  unlock_file "$SPELL_STATUS"
}

#---------------------------------------------------------------------
## Create a map of spells to their dependent spells.
## Then for all installed or held spells, output a libhash command to
## join the spell name and dependency info.
## Then evaluate the output, thus filling a libhash with dependency info.
## @param Name of hash table to put dependencies
#---------------------------------------------------------------------
compute_installed_depends() {
  __comp_depends_aux 0 "$@"
}

#---------------------------------------------------------------------
## Create a map of spells to their dependent spells.
## Then for all installed or held spells, output a libhash command to
## join the spell name and dependency info.
## Then evaluate the output, thus filling a libhash with dependency info.
## @param Name of hash table to fill with dependencies
#---------------------------------------------------------------------
compute_reverse_installed_depends() {
  __comp_depends_aux 1 "$@"
}

#---------------------------------------------------------------------
## calling this will accomplish several things:
## <ol>
## <li> most importantly it finds the closure of all spells that need to
##    be cast
## <li> it builds a hash table mapping spells to their depends, possibly by
##    asking the user for input
## <li> it updates DEPENDS_STATUS, arguably it shouldn't be doing this.
## </ol>
##
## What happens: take all the spells we've been asked to resolve
## for each one of them run its details file
## the details file will call back to depends/optional_depends
## at this point we determine/find/query for depends info
## update the hash table, update DEPENDS_STATUS, and append to the
## list of spells to resolve
##
## @param Hashtable name for dependencies
## @param Hashtable name for spells with problem in resolution (or something)
## @param Hashtable name for spells which cannot cast
#---------------------------------------------------------------------
compute_uninstalled_depends()
{

  # $1=table to place spells in
  # $2=table to put problem spells in, $* = root spells

  debug "libdepends" "compute_depends of $*"
  local CAST_HASH="$1"
  local BACK_CAST_HASH="$2"
  local CANNOT_CAST_HASH="$3"
  BONUS_SPELLS=()
  shift 3
  local spell spells
  spells=( $@ )

  PRETEND_NOT_INSTALLED=" $@ "

  local _idx
  local looked_at

  # this is a list of all spells basesystem depends on it is used to
  # avoid loops with the "everything depends on basesystem" feature
  local base_deps
  base_deps=$(search_depends_status $DEPENDS_STATUS basesystem|cut -f2 -d:)

  # All specified spells are assumed to be not installed, or else -c and -r
  # would have to be specified all the time.

  for (( _idx=0 ; _idx<${#spells[*]} ; _idx++ )) ; do
    hash_get_ref depends_looked_at ${spells[$_idx]} looked_at
    if [[ ! $looked_at ]]; then
      if ! private_run_depends ${spells[$_idx]} ; then
        # i dont know if this will work, but it will have to suffice
        private_remove_dependees ${spells[$_idx]}
      fi
    else
      debug "libdepends" "already looked at ${spells[$_idx]}, skipping"
    fi
  done
  # we no longer need these, no sense in keeping them around
  hash_unset depends_looked_at
  hash_unset sub_dep_f_hash
  hash_unset sub_dep_r_hash
  hash_unset sub_depends_process
  hash_unset processed_sub_depends

  # we need this so processes on the other side of make know whats going on
  hash_export uncommitted_hash

  BONUS_SPELLS=( ${BONUS_SPELLS[*]} ${UP_DEPENDS[*]} )
}

#---------------------------------------------------------------------
## A private function for running a spell's DEPENDS script.
## No functions except libdepends functions should use this.
## @param Spell
#---------------------------------------------------------------------
private_run_depends()
{
  debug "libdepends" "$FUNCNAME - $*"
  local SPELL=$1

  # special accumulators for the current spell
  local NEW_DEPENDS=""
  local NEW_SUB_DEPENDEES=""
  local NEW_RUNTIME_DEPENDS=""
  local NEW_UP_DEPENDS=""
  local triggerees=""
  local spell_depends
  local spell_sub_depends

  hash_put "depends_looked_at" "$SPELL" "start"

  # We only need to run the stuff if we are going to be casting.
  # It only needs to be added to the casting hash table if we are
  # really casting it
  if private_should_cast $SPELL ; then

    # this cant go in private_should_cast because then the dependee wont
    # have a chance at being fixed
    # we check already here, so a specified spell isn't needlessly run
    if spell_exiled $1; then
      depends_message  "${SPELL}" "is exiled and will not be cast."
      log_failure_reason exiled $1
      return 1
    fi
    get_uncommitted_depends_file $SPELL spell_depends
    spell_sub_depends=$spell_depends.sub
    if  [  -n  "$RECONFIGURE"  ];  then
      local t_abandonded_p
      rm  -f  $DEPENDS_CONFIG/$SPELL
      test -f $DEPENDS_CONFIG/$SPELL.p &&
      mkdir -p $ABANDONED_PERSIST      &&
      lock_file "$DEPENDS_CONFIG/$SPELL.p" &&
      lock_start_transaction "$ABANDONED_PERSIST/$SPELL.p" t_abandonded_p &&
      mv -f "$DEPENDS_CONFIG/$SPELL.p" "$t_abandonded_p" &&
      unlock_file "$DEPENDS_CONFIG/$SPELL.p" &&
      lock_commit_transaction "$ABANDONED_PERSIST/$SPELL.p"
    fi
    prepare_spell_config
    SCRIPT_DIRECTORY=$(codex_find_spell_by_name $SPELL)
    run_prepare $SPELL            &&
    run_details                   &&
    run_configure $SPELL          &&
    run_other $SPELL              &&
    run_depends $SPELL            &&
    run_up_triggers $SPELL        &&
    run_our_sub_depends $SPELL        &&

    # possibly recast things that depend on us if option is set (-B)
    private_upward_depends $SPELL &&
    private_recast_optionals $SPELL &&
    private_add_triggerees        &&
    private_add_depends           ||
    { debug "libdepends" "$FUNCNAME failed to process $SPELL." ; return 1; }
    # no point in keeping the file around if its empty...
    test -s $spell_depends || rm -f $spell_depends $spell_sub_depends

    if real_list_find "${RUNTIME_DEPENDS[*]}" "$SPELL"; then
      local k=${#BONUS_SPELLS[@]}
      BONUS_SPELLS[$k]=$SPELL
    fi

    # this processes any sub-depends we requested and the sub-dependee
    # has already been processed, so we must process them on their behalf
    # this must be done after everything else!
    run_other_sub_depends "$SPELL" || return 1
  else
    depends_message "${SPELL}" "No work to do."
    hash_put "depends_looked_at" "$SPELL" "ignore"
  fi

  # if there weren't any depends no sense in keeping the file around
  return 0
}

#---------------------------------------------------------------------
## Decides if a spell should be cast, or if we can leave it alone.
## Check if the spell is installed, or if theres some other reason to
## rebuild it.
## @param Spell
#---------------------------------------------------------------------
private_should_cast()
{
  local each
  # order is important here...
  if ! codex_does_spell_exist $1; then
    return 1
  elif real_list_find "$PRETEND_NOT_INSTALLED" $1 ; then
    # always look at stuff on the command line unless its exiled
    return 0
  # from here on the spell was not on the command line...
  elif spell_held $1;  then
    # don't recast held even with -R
    return 1
  elif [[ "$RECAST_DOWN" ]] ; then
    # user gave -R so recast...
    return 0
  elif real_list_find "${UP_DEPENDS[*]}" $1; then
    # if someone has determined this is an upward depend (-B)
    return 0
  elif real_list_find "${TRIGGEREES[*]}" $1; then
    # if its being triggered we need to look at it, despite its
    # installed status
    return 0
  elif real_list_find "${FORCE_DEPENDS[*]}" $1; then
    return 0
  elif [[ "$(hash_get sub_depends_process $1)" != "" ]] ; then
    return 0
  elif spell_installed $1 ; then
    # returns success if want to cast
    want_lazy_update $1 && return 0 || return 1
  fi

  # we must need to install this as we know nothing else about it
  return 0
}
#---------------------------------------------------------------------
## @param Spell name
## Find all the spells that depend on the spell given as $1
#---------------------------------------------------------------------
private_upward_depends() {
  if [[ "$RECAST_UP" ]] ; then
    local tmp
    # Note, use the reverse depends tree for this when we get a chance
    # and/or move the weird pattern into library functions...
    # (afrayedknot 2005-10-02)
    lock_file "$DEPENDS_STATUS"
    tmp=$(grep "^.*:$1\(([^:]*)\)\?:" $DEPENDS_STATUS|cut -f1 -d:|tr "\n" " ")
    unlock_file "$DEPENDS_STATUS"
    local j k each
    let j=${#NEW_UP_DEPENDS[*]}
    for each in $tmp; do
      NEW_UP_DEPENDS[$j]=$each
      let j++
    done
    spells=( ${spells[*]} ${tmp} )
  fi
}

# shared code for both loops in private_recast_optionals
private_recast_optionals_sub() {
  local spell="$1"
  local message="$2"

  enabled=""
  message "$message"
  if [[ $RECAST_OPTIONALS == always ]]; then
    enabled=yes
  else
    local default=n
    [[ $RECAST_OPTIONALS == ask-yes ]] && default=y
    if query "Recast $spell with the dependency enabled?" $default; then
      enabled=yes
    fi
  fi
}

#---------------------------------------------------------------------
## Find spells that optionally depended on the current spell but had the
## dependency disabled, ask if the user wants to recast the spell.
## Also finds disabled features that the current spell is a provider of.
#---------------------------------------------------------------------
private_recast_optionals() {
  if [[ $RECAST_OPTIONALS ]] && [[ $RECAST_OPTIONALS != ignore ]] ; then
    local spell j enabled
    let j=${#NEW_UP_DEPENDS[*]}
    for spell in $(search_depends_status_exact $DEPENDS_STATUS \
                 '.*' "$1\(([^:]*)\)\?" off optional '.*' '.*'|cut -f1 -d:); do
      private_recast_optionals_sub $spell \
        "$spell has a disabled optional dependency on $1"
      if [[ $enabled ]] ; then
        NEW_UP_DEPENDS[$j]=$spell
        let j++
        # toggle the dependency, so the user doesn't get requeried
        toggle_depends_status $DEPENDS_STATUS $spell "$1(\([^:]*\))?"
        spells=( ${spells[*]} $spell )
      fi
    done

    # also check for disabled features that $1 is a provider of
    local features feature_regex
    # get the features and build a regex for quicker lookup
    features=$(codex_find_spell_provides $1)
    for feature in $features; do
      feature_regex="$feature\|$feature_regex"
    done
    feature_regex=${feature_regex%\\|}
    for spell in $(search_depends_status_exact $DEPENDS_STATUS \
                '.*' "($feature_regex)" off optional '.*' '.*'|cut -f1 -d:|sort -u); do
      private_recast_optionals_sub $spell \
        "$spell has a disabled optional dependency on $1 as a provider"
      if [[ $enabled ]] ; then
        NEW_UP_DEPENDS[$j]=$spell
        let j++
        # toggle all the features that $1 provides and set $1 as their provider
        for feature in $features; do
          change_spell_provider $DEPENDS_STATUS $spell "$1" "$feature" "on"
        done
        spells=( ${spells[*]} $spell )
      fi
    done
  fi
}

###################BEGIN CALLBACKS FROM OUTSIDE#######################

#---------------------------------------------------------------------
## @param  spell or provider name
## @param  addition to OPTS
## @param  description
## @param  grimoires to look in
## Delegates provider and spell cases to different worker functions.
## and gets grimoires if necessary for cross grimoire depends
##
## Called by real_depends and real_runtime_depends
#---------------------------------------------------------------------
real_generic_required_depends()
{
  local failure_ok=$1
  local article=$2
  local query_term=$3
  local database_term=$4
  shift 4

  if [[ "$1" == "-sub" ]] ; then
    local requested_sub_depends=$2
    shift 2
  fi

  if [[ $1 != ${1/ /} ]] ; then
    message "${PROBLEM_COLOR}Spell names must not contain spaces:" \
            "${DEFAULT_COLOR}${SPELL_COLOR}$1${DEFAULT_COLOR}"
    return 1
  fi

  # determine if we're dealing with a provider or a spell
  local is_provider
  if ! codex_does_spell_exist $1 &> /dev/null; then
    is_provider=yes
  fi

  # see if theres another grimoire
  if [[ "$4" ]] && ! [[ "$OVERRIDE_GRIMOIRES" ]] ; then
    local grimoire here nothere current

    for grimoire in $4; do
      if [[ "$grimoire" == "current" ]] ; then
        current=yes
      elif codex_find_grimoire "$grimoire" > /dev/null; then
        list_add here $grimoire
      else
        list_add nothere $grimoire
      fi
    done
    if [[ "$here" ]] || [[ "$current" ]] ; then
      if [[ "$nothere" ]] ; then
        depends_message "$SPELL" "has $article $query_term on${is_provider+ some}" "$1" "from $4."
        message "${SPELL_COLOR}$1${DEFAULT_COLOR}${CHECK_COLOR}" \
                "exists in the following grimoires${DEFAULT_COLOR}" \
                "${SPELL_COLOR}${4}${DEFAULT_COLOR}${CHECK_COLOR}"
        message "You dont have ${SPELL_COLOR}$nothere${DEFAULT_COLOR}" \
                "${CHECK_COLOR}but you have ${SPELL_COLOR}$here${DEFAULT_COLOR}"
        for grimoire in $nothere ; do
          if query "Get $grimoire grimoire?" n; then
            scribe add "$grimoire"
            unset GRIMOIRE_DIR[*]
            source $GRIMOIRE_LIST
            if codex_find_grimoire "$grimoire" > /dev/null; then
              list_add here $grimoire
            else
              message "${PROBLEM_COLOR}Failed to get grimoire${DEFAULT_COLOR}"
            fi
          fi
        done
    # else
    #   have all the grimoires, nothing to do, this is probably the case most
    #   of the time
      fi
    else
      if [[ "$nothere" ]] ; then
        depends_message "$SPELL" "has $article $query_term on${is_provider+ some}" "$1" "from $4."
        message "${CHECK_COLOR}You dont have any of the grimoires" \
                "${SPELL_COLOR}$4${DEFAULT_COLOR}${CHECK_COLOR}."
        message "You must add at least one grimoire to satisfy the" \
                "dependency.${DEFAULT_COLOR}"
        for grimoire in $nothere ; do
          if query "Get $grimoire grimoire?" n; then
            scribe add "$grimoire"
            unset GRIMOIRE_DIR[*]
            source $GRIMOIRE_LIST
            if codex_find_grimoire "$grimoire" > /dev/null; then
              list_add here $grimoire
            else
              message "${PROBLEM_COLOR}Failed to get grimoire${DEFAULT_COLOR}"
            fi
          fi
        done
      else
        # this is a bug, most likely with list_add in order for this
        # to happen, there has to be some grimoires to look in, and the
        # grimoires are neither installed nor uninstalled
        message "This is a bug, probably with list_add, please contact the" \
                "sorcery team, thanks."
        return 1
      fi
    fi
    if [[ ! $here ]] && [[ ! $current ]] ; then
      message "${PROBLEM_COLOR}no grimoire for $1 was retrieved${DEFAULT_COLOR}"
      if [[ $failure_ok == "no" ]] || ! query "Build $1 anyway?" y; then
        return 1
      fi
    fi
  fi

  local target_spell
  if [[ $is_provider ]]; then
    work_depends_provider "$failure_ok" "$article" \
                                   "$query_term" "$database_term" "$@" &&
    if [[ "$requested_sub_depends" ]]; then
      target_spell=$(get_spell_provider "$SPELL" "$1")
    fi
  else
    work_depends_spell "$failure_ok" "$article" \
                                   "$query_term" "$database_term" "$@" &&
    target_spell=$1
  fi &&
  for sub_depend in $requested_sub_depends; do
    sub_depends "$target_spell" "$sub_depend" || return 1
  done
}


#---------------------------------------------------------------------
## Passthrough to real_generic_required_depends, specifies the
## parts that differ from runtime depends
#---------------------------------------------------------------------
real_depends() {
  real_generic_required_depends "no" "a" "dependency" "required" "$@"
}

#---------------------------------------------------------------------
## Passthrough to real_generic_required_depends, specifies the
## parts that differ from required depends
#---------------------------------------------------------------------
real_runtime_depends() {
  real_generic_required_depends "yes" "a" "runtime dependency" "runtime" "$@"
}


#---------------------------------------------------------------------
## @param  spell or provider name
## @param  addition to OPTS if enabled
## @param  addition to OPTS if disabled
## @param  description
## @param  grimoires to look in
## Delegates provider and spell cases to different worker functions.
##
## Called by real_depends and real_runtime_depends
#---------------------------------------------------------------------
real_generic_optional_depends()
{
  local failure_ok=$1
  local article=$2
  local query_term=$3
  local database_term=$4
  shift 4

  if [[ "$1" == "-sub" ]] ; then
    local requested_sub_depends=$2
    shift 2
  fi

  if [[ $1 != ${1/ /} ]] ; then
    message "${PROBLEM_COLOR}Spell names must not contain spaces:" \
            "${DEFAULT_COLOR}${SPELL_COLOR}$1${DEFAULT_COLOR}"
    return 1
  fi

  # determine if we're dealing with a provider or a spell
  local is_provider
  if ! codex_does_spell_exist $1 &> /dev/null; then
    is_provider=yes
  fi

  # see if theres another grimoire
  if [[ "$5" ]] && ! [[ "$OVERRIDE_GRIMOIRES" ]] ; then
    local grimoire here nothere current
    for grimoire in $5; do
      if [[ "$grimoire" == "current" ]] ; then
        current=yes
      elif codex_find_grimoire "$grimoire" > /dev/null; then
        list_add here $grimoire
      else
        list_add nothere $grimoire
      fi
    done
    if [[ "$here" ]] || [[ "$current" ]] ; then
      if [[ "$nothere" ]] ; then
        depends_message "$SPELL" "has $article $query_term on${is_provider+ some}" "$1" "from $5."
        message "${SPELL_COLOR}$1${DEFAULT_COLOR}${CHECK_COLOR}" \
                "exists in the following grimoires${DEFAULT_COLOR}" \
                "${SPELL_COLOR}${5}${DEFAULT_COLOR}${CHECK_COLOR}"
        message "You dont have ${SPELL_COLOR}$nothere${DEFAULT_COLOR}" \
                "${CHECK_COLOR}but you have ${SPELL_COLOR}$here${DEFAULT_COLOR}"
        for grimoire in $nothere ; do
          if query "Get $grimoire grimoire?" n; then
            scribe add "$grimoire"
            unset GRIMOIRE_DIR[*]
            source $GRIMOIRE_LIST
            if codex_find_grimoire "$grimoire" > /dev/null; then
              list_add here $grimoire
            else
              message "${PROBLEM_COLOR}Failed to get grimoire${DEFAULT_COLOR}"
            fi
          fi
        done
    # else
    #   have all the grimoires, nothing to do, this is probably the case most
    #   of the time
      fi
    else
      if [[ "$nothere" ]] ; then
        depends_message "$SPELL" "has $article $query_term on${is_provider+ some}" "$1" "from $5."
        message "${CHECK_COLOR}You dont have any of the grimoires" \
                "${SPELL_COLOR}${5}${DEFAULT_COLOR}${CHECK_COLOR}."
        for grimoire in $nothere ; do
          if query "Get $grimoire grimoire?" n; then
            scribe add "$grimoire"
            unset GRIMOIRE_DIR[*]
            source $GRIMOIRE_LIST
            if codex_find_grimoire "$grimoire" > /dev/null; then
              list_add here $grimoire
            else
              message "${PROBLEM_COLOR}Failed to get grimoire${DEFAULT_COLOR}"
            fi
          fi
        done
      else
        # this is a bug, most likely with list_add in order for this
        # to happen, there has to be some grimoires to look in, and the
        # grimoires are neither installed nor uninstalled
        message "This is a bug, probably with list_add, please contact the" \
                "sorcery team, thanks."
        return 1
      fi
    fi
    if [[ ! $here ]] && [[ ! $current ]] ; then
      message "${PROBLEM_COLOR}no grimoire for $1 was retrieved${DEFAULT_COLOR}"
      message "Assuming dependency is off because it could not be met"
      if [[ $is_provider ]]; then
        private_common_depends "($1)" "off" "$database_term" "$2" "$3"
      else
        private_common_depends "$1" "off" "$database_term" "$2" "$3"
      fi
      return 0
    fi
  fi

  local target_spell
  if [[ $is_provider ]]; then
    work_optional_depends_provider "$failure_ok" "$article" \
                                   "$query_term" "$database_term" "$@" &&
    if [[ "$requested_sub_depends" ]]; then
      target_spell=$(get_spell_provider "$SPELL" "$1")
    fi
  else
    work_optional_depends_spell "$failure_ok" "$article" \
                                   "$query_term" "$database_term" "$@" &&
    target_spell=$1
  fi &&
  if [[ "$requested_sub_depends" ]] &&
     [[ "$target_spell" ]] &&
     is_depends_enabled "$SPELL" "$target_spell"; then
    for sub_depend in $requested_sub_depends; do
      sub_depends "$target_spell" "$sub_depend" || return 1
    done
  fi

}

#---------------------------------------------------------------------
## Passthrough to real_generic_optional_depends, specifies the
## parts that differ from suggest depends
#---------------------------------------------------------------------
real_optional_depends() {
  real_generic_optional_depends "no" "an" "optional dependency" "optional" "$@"
}

#---------------------------------------------------------------------
## Passthrough to real_generic_required_depends, specifies the
## parts that differ from optional depends
#---------------------------------------------------------------------
real_suggest_depends() {
  real_generic_optional_depends "yes" "a" "suggested dependency" "suggest" "$@"
}


#---------------------------------------------------------------------
## Asks the user what provider for a depends is desired if a choice
## has not ben made before.
## @param Service
## @param Enabled options
## @param Description
#---------------------------------------------------------------------
work_depends_provider()
{

  debug "libdepends" "$FUNCNAME - $@"
  local default tmp installed=no
  local choices
  local status=()

  local failure_ok=$1
  local article=$2
  local query_term=$3
  local database_term=$4
  shift 4

  if [[ $3 ]] ; then
    depends_message "${SPELL}" "has $article $query_term on some" "${1}" "($3)."
  else
    depends_message "$SPELL" "has $article $query_term on some" "${1}."
  fi

  local CANDIDATES=$( find_providers $1)
  if [[ ! $CANDIDATES ]] ; then
    message "${PROBLEM_COLOR}No providers of${DEFAULT_COLOR}" \
            "${SPELL_COLOR}$1${DEFAULT_COLOR}" \
            "${PROBLEM_COLOR} can be found!${DEFAULT_COLOR}"
    if [[ $failure_ok == "no" ]] || ! query "Build $1 anyway?" y; then
      return 1
    fi
  fi

  # if not reconfiguring check if theres already an answer in DEPENDS_STATUS
  if [[ ! $RECONFIGURE ]]; then
    # notice the clever ignorance of optional/required depends for the
    # provider case, if the user chose none, we would fall out during spell_ok
    # and we transparently switch between optional and required without
    # anyone noticing
    explode "$(search_depends_status $DEPENDS_STATUS "$SPELL" ".*($1)")" ":" "status"
    tmp=${status[1]%(*}    # Name of spell which provides $1
    if spell_ok $tmp; then
      message "${MESSAGE_COLOR}Using ${SPELL_COLOR}$tmp${DEFAULT_COLOR}"
      private_common_depends "$tmp($1)" "on" "$database_term" "$2" "$3"
      return 0
    fi
  fi

  # check if theres an abandoned answer, but only if its still a provider
  if [[ ! $default ]] && [ -e $ABANDONED_DEPENDS/$SPELL ] ; then
    tmp=$(search_depends_status $ABANDONED_DEPENDS/$SPELL "$SPELL" ".*($1)"|awk -F: '{print $2;exit}')
    [[ $tmp ]] && real_list_find "$CANDIDATES" "$tmp" && default=$tmp
  fi

  # check if theres a default provider
  if [[ ! $default ]]; then
    explode "$(search_default_provider $DEFAULT_PROVIDERS ".*" "$1")" ":" "status"
    tmp=${status[0]}
    [[ $tmp ]] && real_list_find "$CANDIDATES" "$tmp" && default=$tmp
  fi

  # check if we've already answered this question
  if [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      real_list_find "${spells[*]}" "$tmp" && default=$tmp && break
    done
  fi

  # check if theres a provider already installed
  # if there are multiple, try to select the previously used one
  if [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      spell_ok $tmp && real_list_add choices $tmp
    done
    if [[ $choices == ${choices##* } ]]; then
      default=$choices
    else
      explode "$(search_depends_status $DEPENDS_STATUS "$SPELL" ".*($1)")" ":" "status"
      local old_provider=${status[1]%(*} # Name of spell which provides $1
      if real_list_find "$choices" $old_provider; then
        default=$old_provider
      else
        default=${choices%% *}
      fi
    fi
  fi

  local provider
  select_provider "provider" "$default" 0 $CANDIDATES

  private_common_depends "$provider($1)" "on" "$database_term" "$2" ""
}

#---------------------------------------------------------------------
## One of the worker functions. Checks for exiled spell and passes
## on to the common dependency function, <@function private_common_depends>
## @param Spell
## @param enabled options
#---------------------------------------------------------------------
work_depends_spell()
{
  debug "libdepends" "$FUNCNAME - $@"

  local failure_ok=$1
  local article=$2
  local query_term=$3
  local database_term=$4
  shift 4

  depends_message "${SPELL}" "has $article $query_term on" "$1"

  if spell_exiled $1 ; then
    depends_message "${1}" "has been exiled!"
    if [[ $failure_ok == "no" ]] || ! query "Build $1 anyway?" y; then
      hash_put $CANNOT_CAST_HASH "$1" "Exiled"
      grep -qs $1 $FAILED_LIST || echo $1 >> $FAILED_LIST
      log_failure_reason exiled $1
      return 1
    fi
  fi
  private_common_depends "$1" "on" "$database_term" "$2" ""

}

#---------------------------------------------------------------------
## @param  provider name
## @param  addition to OPTS if enabled
## @param  addition to OPTS if disabled
## @param  description
## Handles optional dependency on a provider.
#---------------------------------------------------------------------
work_optional_depends_provider()
{

  debug "libdepends" "$FUNCNAME - $@"
  local default tmp choices installed=no
  local status=()

  local failure_ok=$1
  local article=$2
  local query_term=$3
  local database_term=$4
  shift 4

  if [[ $4 ]] ; then
    depends_message "${SPELL}" "has $article $query_term on some" "${1}" "($4)."
  else
    depends_message "${SPELL}" "has $article $query_term on some" "${1}."
  fi

  local CANDIDATES=$( find_providers $1)
  # if not reconfiguring check if theres already an answer in DEPENDS_STATUS
  if [[ ! $RECONFIGURE ]]; then
    explode "$(search_depends_status_simple $DEPENDS_STATUS "$SPELL" ".*($1)" "on")" ":" "status"
    local tmp=${status[1]%(*}    # Name of spell which provides $1
    if [[ "$tmp" ]] && spell_ok "$tmp"; then
      message "${MESSAGE_COLOR}Using ${SPELL_COLOR}$tmp${DEFAULT_COLOR}"
      private_common_depends "$tmp($1)" "on" "$database_term" "$2" "$3"
      return 0
    fi
    if [[ "$(search_depends_status_simple $DEPENDS_STATUS \
                                          "$SPELL" ".*($1)" "off")" ]]; then
      message "${MESSAGE_COLOR}Using ${SPELL_COLOR}[none]${DEFAULT_COLOR}"
      private_common_depends "$tmp($1)" "off" "$database_term" "$2" "$3"
      return 0
    fi
  fi

  # check if theres an abandoned answer, but only if its still a provider
  if [[ ! $default ]] && [ -e $ABANDONED_DEPENDS/$SPELL ] ; then
    tmp=$(search_depends_status_simple $ABANDONED_DEPENDS/$SPELL "$SPELL" ".*($1)" "on"|awk -F: '{print $2;exit}')
    if [[ $tmp ]] && real_list_find "$CANDIDATES" "$tmp"; then
      default=$tmp
    else
      tmp=$(search_depends_status_simple $ABANDONED_DEPENDS/$SPELL "$SPELL" ".*($1)" "off")
      [[ $tmp ]] && default=none
    fi
  fi

  # check if theres a default provider
  if [[ ! $default ]]; then
    tmp=$(search_default_provider $DEFAULT_PROVIDERS ".*" "$1")

    # make sure we found /something/ before trying to analyze it
    # otherwise we'll fall into the else case and use 'none' as the
    # provider, and short-circuit the other guesses
    if [[ $tmp ]] ; then
      explode "$tmp" ":" "status"
      tmp=${status[0]}
      if [[ ${status[2]} == on ]] ; then
        # if the user said "on" use the default rather than none
        # unless theres something wrong with the provider they chose
        # in which case fall back to none
        if [[ $tmp ]] && real_list_find "$CANDIDATES" "$tmp"; then
          default=$tmp
        else
          message "${PROBLEM_COLOR}The default provider is not good anymore!"
          message "Falling back to 'none' as the default choice.$DEFAULT_COLOR"
          default=none
        fi
      else
        default=none
      fi
    fi
  fi

  # check if we've already answered this question
  if [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      real_list_find "${spells[*]}" "$tmp" && default=$tmp && break
    done
  fi

  # check if theres a provider already installed
  # if there are multiple, try to select the previously used one
  if [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      spell_ok $tmp && real_list_add choices $tmp
    done
    if [[ $choices == ${choices##* } ]]; then
      default=$choices
    else
      # only search for enabled dependencies since none is already the default
      explode "$(search_depends_status_simple $DEPENDS_STATUS "$SPELL" ".*($1)" "on")" ":" "status"
      local old_provider=${status[1]%(*} # Name of spell which provides $1
      if real_list_find "$choices" $old_provider; then
        default=$old_provider
      else
        default=${choices%% *}
      fi
    fi
  fi

  local provider
  select_provider "provider" "$default" 1 $CANDIDATES

  if [ $provider == "none" ] ; then
    private_common_depends "($1)" "off" "$database_term" "$2" "$3"
  else
    private_common_depends "$provider($1)" "on" "$database_term" "$2" "$3"
  fi

}

#---------------------------------------------------------------------
## @param spell
## @param question
## @param default answer
##
## @return 0 on yes
## @return 1 on no
##
## Works just like normal query but can show short description of a
## spell and stops the timer for taking the default answer if
## h/H is pressed. Type of query is chosen in sorcery feature menu.
##
#---------------------------------------------------------------------
optional_depends_query()  {
  local _response
  local spell_name=$1
  local time_to_answer=$PROMPT_DELAY

  while true; do
    _response=""

    if [[ -z $SILENT ]]; then
      if [[ $SHOW_GAZE_SHORT_QUERY == off ]]; then
        echo -e -n "${QUERY_COLOR}$2 [$3] ${DEFAULT_COLOR}"
      else
        if [[ $3 == y ]]; then
          echo -e -n "${QUERY_COLOR}$2 [Y/n/h] ${DEFAULT_COLOR}"
        else
          echo -e -n "${QUERY_COLOR}$2 [y/N/h] ${DEFAULT_COLOR}"
        fi
      fi

      if [[ -n $time_to_answer ]]; then
        read -t $time_to_answer -n 1 _response
        echo
      else
        read -n 1 _response
        echo
      fi
    fi

    _response=${_response:=$3}
    case  $_response in
      n|N) return 1 ;;
      y|Y) return 0 ;;
      h|H) ( codex_set_current_spell_by_name $spell_name
           echo $SHORT
           echo More information at: $WEB_SITE
           )
           unset time_to_answer
    esac
  done
}

#---------------------------------------------------------------------
## @param  spell name
## @param  addition to OPTS if enabled
## @param  addition to OPTS if disabled
## @param  description
## Handles optional dependency on a spell.
#---------------------------------------------------------------------
work_optional_depends_spell()
{

  debug "libdepends" "$FUNCNAME - $@"
  local default

  local failure_ok=$1
  local article=$2
  local query_term=$3
  local database_term=$4
  shift 4

  # if $1 optionally depends on something exiled we always say no
  if spell_exiled $1 ; then
    depends_message "${1}" "has been exiled! not using as $article $query_term"
    # don't put it into the bad_spells hash, since it wasn't specified directly
    #hash_put $CANNOT_CAST_HASH "$1" "Exiled"
    private_common_depends "$1" "off" "$database_term" "$2" "$3"
    return 0
  fi


  if [[ ! $RECONFIGURE ]] ; then
    # See if there are preferences already in DEPENDS_STATUS, but only if
    # not reconfiguring...
    # example: icewm:imlib:off:optional:--with-imlib:--with-xpm
    local status=()
    explode "$(search_depends_status $DEPENDS_STATUS "$SPELL" "$1")" ":" "status"
    if [[ ${status[2]} ]] ; then
      # ah there are! use them
      if [[ ${status[2]} == "on" ]] ; then
        depends_message "${SPELL}" "has an enabled $query_term on" "${1}"
      else
        depends_message "${SPELL}" "has a disabled $query_term on" "${1}"
      fi
      private_common_depends "$1" "${status[2]}" "$database_term" "$2" "$3"
      return 0
    fi
  fi
  # colors differ from depends_message
  if [[ $4 ]]; then
    message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
            "has $article $query_term on" \
            "${SPELL_COLOR}$1${DEFAULT_COLOR} ($4)"
  else
    message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
            "has $article $query_term on" \
            "${SPELL_COLOR}$1${DEFAULT_COLOR}"
  fi


  # check for abandoned answers
  if [ -e $ABANDONED_DEPENDS/$SPELL ] ; then
    debug "libdepends" "Checking in abandoned depends"
    default=$(search_depends_status $ABANDONED_DEPENDS/$SPELL "$SPELL" "$1"|awk -F: '{print $3;exit}')
  fi

  # check the defaults file...
  # first for explicit $SPELL -> $2
  if [[ ! $default ]]; then
    debug "libdepends" "Checking in default answers"
    default=$(search_default_depends $DEFAULT_DEPENDS $SPELL $1|awk -F: '{print $3; exit}')
  fi

  # then for anything -> $2
  if [[ ! $default ]]; then
    debug "libdepends" "Checking in default answers"
    default=$(search_default_depends $DEFAULT_DEPENDS "" $1|awk -F: '{print $3; exit}')
  fi

  # then for $1 -> anything
  if [[ ! $default ]]; then
    debug "libdepends" "Checking in default answers"
    default=$(search_default_depends $DEFAULT_DEPENDS $SPELL "" |awk -F: '{print $3; exit}')
  fi

  # check the install queue
  if [[ ! $default ]]; then
    debug "libdepends" "Checking in queue"
    real_list_find "${spells[*]}" "$1" && default=on
  fi

  # check if installed/held
  if [[ ! $default ]]; then
    debug "libdepends" "Checking if already installed"
    spell_ok $1 && default=on
  fi

  # otherwise default to no
  [[ ! $default ]] && default=off

  local install=off

  local stuff
  [[ $default == off ]] && stuff=n || stuff=y

  if spell_ok $1 ; then
    optional_depends_query "$1" "Do you want to use ${SPELL_COLOR}$1${QUERY_COLOR}?" "$stuff" &&
        install="on"
  else
    optional_depends_query "$1" "Do you want to cast ${SPELL_COLOR}$1${QUERY_COLOR}?" "$stuff" &&
        install="on"
  fi

  private_common_depends "$1" "$install" "$database_term" "$2" "$3"
}

#---------------------------------------------------------------------
## @param  name of return variable
## @param  default answer
## @param  0 if required 1 if optional
## @param  list of possible providers
## Present a list to the user complete with info about whats installed
## and what isnt and allow a default value to be used
#---------------------------------------------------------------------
select_provider()
{
    local returnvar=$1
    local default=$2
    local optional=$3
    local i
    shift 3

    local each default_char=0 stuff=()
    local char

    # we can only read one character so use every one we can, I dont expect
    # there to be more than 62 providers

    # in bash 3.0 this expands to all the numbers and letters
    # stuff=({0..9} {a..z} {A..Z})
    # but we're still on bash 2 which cant do that, if someone
    # knows a better way to do this please tell me
    stuff=(0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v w x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z)

    if [ $optional == 1 ] ; then
      hash_put CHAR_TO_SPELL 0 "none"
      let i=1
      message "\t${DEFAULT_COLOR}(0)\t${SPELL_COLOR}[none]${DEFAULT_COLOR}"
    else
      let i=0
    fi

    for each in $@; do
      char=${stuff[$i]}
      hash_put CHAR_TO_SPELL $char $each

      [[ $each == $default ]] && default_char=$char
      if spell_ok $each ; then
        message "\t${DEFAULT_COLOR}($char)\t${SPELL_COLOR}$each${DEFAULT_COLOR}\t (installed)"
      else
        message "\t${DEFAULT_COLOR}($char)\t${SPELL_COLOR}$each${DEFAULT_COLOR}"
      fi
      let i++
    done

    local msg="\n${QUERY_COLOR}Which one do you want? [$default_char]$DEFAULT_COLOR "
    select_list_sub "$returnvar" CHAR_TO_SPELL "$msg" "$default_char"
    hash_unset CHAR_TO_SPELL
}

#---------------------------------------------------------------------
## @param Target of the trigger
## @param Action to execute (cast_self, check_self, etc).
##
## Create a trigger on ourself effecting the target spell,
## shorthand for putting a TRIGGERS file in the target spell.
#---------------------------------------------------------------------
real_up_trigger() {
  message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
           "${CHECK_COLOR}triggers a${DEFAULT_COLOR}" \
           "${SPELL_COLOR}${2}${DEFAULT_COLOR}" \
           "${CHECK_COLOR}on${DEFAULT_COLOR}" \
           "${SPELL_COLOR}${1}${DEFAULT_COLOR}"
  private_up_trigger $SPELL "$1" "$2"
}

#---------------------------------------------------------------------
## @param Current spell
## @param Target target of the trigger
## @param Action to execute (cast_self, check_self, etc).
##
## Register a trigger, when $SPELL is cast, a $ACTION is executed
## on $TARGET
#---------------------------------------------------------------------
private_up_trigger() {
  local SPELL=$1
  local TARGET=$2
  local ACTION=$3
  # this maps triggerers to their trigerees
  # perl -> cast_self:perl_module
  hash_append trg_f_hash  $SPELL "$TARGET:$ACTION" $'\n' &&
  # this maps trigerees to triggerers
  # cast_self:perl_module -> perl
  hash_append trg_r_hash  "$TARGET:$ACTION" " $SPELL "

  # afk 6-7-06 Im not sure this line is correct, it seems to only
  # make a circular depends, instead we want $TARGET to depend on $SPELL
  real_list_find "${NEW_DEPENDS[*]}" "$TARGET" ||
  NEW_DEPENDS=( ${NEW_DEPENDS[*]} $spell)

  triggerees=( ${triggerees[*]} $TARGET )
}

#---------------------------------------------------------------------
## @param spell providing the sub-depends
## @param name of sub-depends
##
## Request a sub-depends from $SPELL on $1 for $2
## This queues the sub-depends for later processing, if the sub-dependee
## does not already support the sub-depends.
#---------------------------------------------------------------------
real_sub_depends() {
  $STD_DEBUG
  local requester=$SPELL
  local sub_dependee=$1
  local sub_depends=$2

  message "${SPELL_COLOR}${SPELL}${MESSAGE_COLOR} requests" \
          "${SPELL_COLOR}$sub_dependee${DEFAULT_COLOR}" \
          "${CHECK_COLOR}with ${SPELL_COLOR}$sub_depends${DEFAULT_COLOR}"

  # Check if the sub-depends is already known
  if spell_ok $sub_dependee; then
    if [[ $(search_sub_depends "$SUB_DEPENDS_STATUS" "$requester" \
                              "$sub_dependee" "$sub_depends") != "" ]]; then
      debug "libdepends" "$FUNCNAME -- $requester -> $sub_dependee" \
                         "-> $sub_depends provided by installed spell"
      return 0
    fi

    # the spell is installed, but the sub-depends isn't recorded, ask the
    # spell if the sub-depends is enabled through the PRE_SUB_DEPENDS file.
    (
      THIS_SUB_DEPENDS=$sub_depends
      if ! tablet_set_spell $sub_dependee ; then
        codex_set_current_spell_by_name $sub_dependee || return 1
      fi
      run_spell_file PRE_SUB_DEPENDS pre_sub_depends
      rc=$?
      return $rc
    ) && {
      debug "libdepends" "adding altruistic sub-depends for $sub_dependee with $sub_depends from $requester"
      add_sub_depends "$SUB_DEPENDS_STATUS" "$requester" \
                      "$sub_dependee" "$sub_depends"
      hash_append sub_dep_f_hash $requester $sub_dependee:$sub_depends $'\n'
      hash_append sub_dep_r_hash $sub_dependee $requester:$sub_depends $'\n'
      return 0
    }
  fi

  # if didnt return above, then we know the sub-depends is not on the system
  # so the spell must be (re)cast, check to see if we're allowed to do that
  if ! real_list_find "$PRETEND_NOT_INSTALLED" $sub_dependee &&
     spell_held $sub_dependee; then
    # spell is held and not explicitly requested, so we cant recast the
    # spell with the sub-depends requested
    message "${PROBLEM_COLOR}Sub-depends requested on" \
            "a held spell: $SPELL_COLOR$sub_dependee$DEFAULT_COLOR"
    return 1
  fi

  # add to hashes for lookup later in depends resolution
  hash_append sub_dep_f_hash $requester $sub_dependee:$sub_depends $'\n'
  hash_append sub_dep_r_hash $sub_dependee $requester:$sub_depends $'\n'

  # spell is either not installed, or is installed but without the
  # sub-depends, we must (re)cast it
  NEW_SUB_DEPENDEES=( ${NEW_SUB_DEPENDEES[*]} $sub_dependee )
  hash_put sub_depends_process $sub_dependee "yes"
  return 0
}

#---------------------------------------------------------------------
## Force a spell to be recast, if it comes up for processing
## if the spell was already looked at and processed nothing happens
## if the spell was already looked at and didnt need processing, then
## it'll get re-processed (assuming the caller also did a depends on it)
#---------------------------------------------------------------------
real_force_depends() {
  debug "libdepends" "$FUNCNAME - $SPELL - $@"
  local check
  hash_get_ref "depends_looked_at" "$1" check

  message "${SPELL}" "is forcing a recast of" "${1}"

  if [[ "$check" == "ignore" ]] ; then
    hash_put "depends_looked_at" "$1" ""
  fi
  FORCE_DEPENDS=( ${FORCE_DEPENDS[*]} $1 )
}

#---------------------------------------------------------------------
## all the depends callbacks eventually bottom out here
## if a spell depends or doesnt depend on some other spell
## @param Spell
## @param on/off
#---------------------------------------------------------------------
private_common_depends()
{
  debug "libdepends" "$FUNCNAME - $SPELL - $@"
  add_depends $spell_depends "$SPELL" "$@"

  # runtime and suggested depends have no formal dependency info
  if [[ $2 == on ]] ; then
    # ${1%(*} = spell name (strips potential provider name)
    local spell_name=${1%(*}
    case $3 in
      runtime|suggest)
           NEW_RUNTIME_DEPENDS=( ${NEW_RUNTIME_DEPENDS[*]} $spell_name ) ;;
      *)   NEW_DEPENDS=( ${NEW_DEPENDS[*]} $spell_name ) ;;
    esac
  fi


  return 0
}

#---------------------------------------------------------------------
## Default trigger checking function. Asks user if they want to
## run the trigger.
#---------------------------------------------------------------------
real_default_sorcery_trigger_check() {
  message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
           "${CHECK_COLOR}triggers a" \
           "${SPELL_COLOR}${ACTION}${DEFAULT_COLOR}" \
           "${CHECK_COLOR}on${DEFAULT_COLOR}" \
           "${SPELL_COLOR}${TARGET}${DEFAULT_COLOR}"
  query "Run the trigger?" y
}

#---------------------------------------------------------------------
## Inspects each trigger, asks the user if they want to run it.
#---------------------------------------------------------------------
private_add_triggerees() {

  # add the spells that we trigger to the $spells list
  # having duplicate items is okay
  local ACTION TARGET
  local running_trigger

  # run the trigger check file
  # this is made into a sub-function just to reduce duplication...
  function private_add_triggerees_sub1() {
    run_spell_file TRIGGER_CHECK trigger_check
    running_trigger=$?
    if [[ $running_trigger == 0 ]] ; then
      private_up_trigger "$SPELL" "$TARGET" "$ACTION"
    fi
  }

  # frontend to help with calling the trigger check file
  function private_add_triggerees_sub2() {
    local ACTION=$1
    private_add_triggerees_sub1
  }

  for ACTION in cast_self check_self dispel_self run_script; do
    for TARGET in $(get_triggerees $SPELL on_cast $ACTION); do
      spell_ok $TARGET || continue
      if [[ $ACTION == run_script ]] ; then
        iterate private_add_triggerees_sub2 $'\n' \
                          "$(get_run_script_triggers $SPELL on_cast $TARGET)"
      else
        private_add_triggerees_sub1
      fi
    done
  done
  return 0
}


#---------------------------------------------------------------------
## Adds the dependency to the hastable
#---------------------------------------------------------------------
private_add_depends()
{
  debug "libdepends" "$FUNCNAME: SPELL=$SPELL, NEW_DEPENDS=${NEW_DEPENDS[*]}"
  hash_append "$CAST_HASH" "$SPELL" "${NEW_DEPENDS[*]}"

  for child in ${NEW_DEPENDS[*]}; do
    hash_append "$BACK_CAST_HASH" "$child" "$SPELL"
  done

  # force implied basesystem dependency in the depends tree
  if [[ $FORCE_BASESYSTEM_DEPENDS == on ]] &&
     [[ $SPELL != basesystem ]] &&
     ! real_list_find "$base_deps" "$SPELL"; then
    hash_append "$CAST_HASH" "$SPELL" "basesystem"
    hash_append "$BACK_CAST_HASH" "basesystem" "$SPELL"
  fi

  spells=( ${spells[*]} ${NEW_DEPENDS[*]}
                        ${NEW_SUB_DEPENDEES[*]}
                        ${NEW_RUNTIME_DEPENDS[*]} )

  RUNTIME_DEPENDS=( ${RUNTIME_DEPENDS[*]} ${NEW_RUNTIME_DEPENDS[*]} )

  TRIGGEREES=( ${TRIGGEREES[*]} ${triggerees[*]} )
  spells=( ${spells[*]} ${triggerees[*]} )

  UP_DEPENDS=( ${UP_DEPENDS[*]} ${NEW_UP_DEPENDS[*]} )

  hash_put "depends_looked_at" "$SPELL" "done"

}

#---------------------------------------------------------------------
## Determine if spell should be lazily updated, possible asks the user
## what to do.
#---------------------------------------------------------------------
want_lazy_update() {
  if [[ $LAZY_DEPENDS_UPDATES ]] && [[ $LAZY_DEPENDS_UPDATES != ignore ]] ; then
    if does_spell_need_update "$1" ; then
      depends_message "$1" "needs updating"
      if [[ "$LAZY_DEPENDS_UPDATES" == always ]] ; then
        return 0
      else
        default=n
        [[ $LAZY_DEPENDS_UPDATES == ask-yes ]] && default=y
        query "Would you like to update it?" $default && return 0 || return 1
      fi
    fi
  fi
  return 1
}

depends_message() {
  if [[ $# -ge 2 ]] ; then
    message -n "${SPELL_COLOR}${1}${DEFAULT_COLOR}" \
               "${CHECK_COLOR}${2}${DEFAULT_COLOR}"
  fi
  if [[ $# -ge 3 ]] ; then
    message -n " ${SPELL_COLOR}${3}${DEFAULT_COLOR}"
  fi
  if [[ $# -ge 4 ]] ; then
    message -n " $4"
  fi
  message ""
}

#########################BEGIN OTHER STUFF############################

#---------------------------------------------------------------------
## @param Spell name
## Removes a dependency and its dependees from the to_cast list.
#---------------------------------------------------------------------
private_remove_dependees()
{
  local spell=$1
  local removed_list dependee dependees
  message "${PROBLEM_COLOR}Removing dependees of $SPELL_COLOR$spell$DEFAULT_COLOR"

  # take care of the spell
  private_discard_spell $spell fail

  # take care of the dependees and their dependees and ...
  recurse_remove_dependees() {
    local spell=$1
    local dependees dependee
    while uncommitted_upward_depends $spell dependees; do
      [[ -z $dependees ]] && break
      for dependee in $dependees; do
        private_discard_spell $dependee
        real_list_add removed_list $dependee
        recurse_remove_dependees $dependee
      done
    done
  }

  recurse_remove_dependees $spell

  # take care of dependencies of removed dependees
  # but don't remove them if they were specified manually or
  # if they wouldn't be cast at all or
  # if something else needs them
  recurse_remove_dependencies() {
    local spell=$1
    local dependency dependees ignore dependees2
    # use BACK_CAST_HASH since we've already cleared CAST_HASH
    # it is in the form of dependency : dependee1 dependee2 ...
    for dependency in $(hash_get_table_fields $BACK_CAST_HASH); do
      hash_get_ref $BACK_CAST_HASH $dependency dependees
      if real_list_find "$dependees" $spell &&
        hash_get_ref "depends_looked_at" "$dependency" ignore &&
        [[ $ignore != ignore ]] &&
        uncommitted_upward_depends $dependency dependees2 &&
        [[ -z $dependees2 ]] &&
        ! real_list_find "$SPELLS" $dependency; then
          hash_unset_part $BACK_CAST_HASH $dependency $spell
          private_discard_spell $dependency
          recurse_remove_dependencies $dependency
      fi
    done
  }

  for dependee in $removed_list; do
    recurse_remove_dependencies $dependee
  done
}

#---------------------------------------------------------------------
## @param Spell name
## Does the actual removal
#---------------------------------------------------------------------
private_discard_spell()
{
  local spell=$1
  local failed=$2

  grep -qs $spell $FAILED_LIST && return 0

  if [[ $failed == fail ]]; then
    # spell is being removed from cast list, add to FAILED_LIST
    # the rest we want to just show up as dropped
    echo "$spell" >> $FAILED_LIST
  fi
  hash_put depends_looked_at $spell failed
  hash_unset "$CAST_HASH" "$spell"
  hash_put $CANNOT_CAST_HASH "$spell" "Failed"

  local bonus=${BONUS_SPELLS[@]}
  local up_depends=${UP_DEPENDS[@]}
  if real_list_find "$bonus" $spell; then
    real_list_remove bonus $spell
    BONUS_SPELLS=( $bonus )
  fi
  if real_list_find "$up_depends" $spell; then
    real_list_remove up_depends $spell
    UP_DEPENDS=( $up_depends )
  fi
}

#---------------------------------------------------------------------
## @param Spell name
## @param Return variable
## Find all the spells already processed that depend on the spell given as $1
## Unlike private_upward_depends, this one works with the uncommitted info
#---------------------------------------------------------------------
uncommitted_upward_depends() {
  local _spell=$1
  local _upvar=$2
  local candidate _dependees _deps

  for candidate in $(hash_get_table_fields $CAST_HASH); do
    hash_get_ref $CAST_HASH $candidate _deps
    if real_list_find "$_deps" $_spell; then
      real_list_add _dependees $candidate
    fi
  done

  if [[ -n $_upvar ]]; then
    upvar $_upvar $_dependees
  else
    echo $_dependees
  fi
}

#---------------------------------------------------------------------
## Sets a spell's aux. config info.
## @Globals SPELL
#---------------------------------------------------------------------
run_spell_config()
{

  SPELL_CONFIG=$DEPENDS_CONFIG/$SPELL
  debug "libdepends" "run_spell_config() - DEPENDS_CONFIG=$DEPENDS_CONFIG SPELL=$SPELL, SPELL_CONFIG=$SPELL_CONFIG DEPENDS_STATUS=$DEPENDS_STATUS"

  if  [  -x  $SPELL_CONFIG  ];  then
    debug "libdepends" "run_spell_config() - found $SPELL_CONFIG"
    .  $SPELL_CONFIG
  fi
}

#---------------------------------------------------------------------
## Output the upward dependencies of the specified spell
## @Param spell
## @Param depth (optional)
## @Param fast -- if set only show spells, not full depends db entries
## @Param all - if set returns also runtime dependencies
#---------------------------------------------------------------------
real_show_up_depends()
{
    local i=0
    local MAX_DEPTH=$2
    local type=$3
    local all=$4
    function show_up_depends_sub() {
        local each dependencies checked
        let i++
        [[ $MAX_DEPTH ]] && [[ $i -gt $MAX_DEPTH ]] && return
        hash_get_ref foo $1 dependencies
        for each in $dependencies; do
            hash_get_ref done $each checked
            if ! [[ $checked ]] ; then
                hash_put done $each done
                echo $each:$1
                show_up_depends_sub $each
            elif [[ "$type" == "verbose" ]] ; then
                echo $each:$1
            fi
        done
    }
    hash_reset foo
    hash_reset done
    compute_reverse_installed_depends foo $all
    if [[ "$type" == "verbose" ]] ; then
      lock_file "$DEPENDS_STATUS"
      show_up_depends_sub "$1"|while read line; do
        grep -e "$line:" -e "$line([^)(]*):" "$DEPENDS_STATUS"
      done
      unlock_file "$DEPENDS_STATUS"
    else
      show_up_depends_sub "$1"|cut -f1 -d:
    fi|sort -u
    hash_reset foo
    hash_reset done
}


#---------------------------------------------------------------------
##=back
##
##=head1 LICENSE
##
## This software is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 2 of the License, or
## (at your option) any later version.
##
## This software is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.
##
## You should have received a copy of the GNU General Public License
## along with this software; if not, write to the Free Software
## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
##
#---------------------------------------------------------------------
