#!/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
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function run_other() {
  local SPELL=$1
  # ask the questions about xinetd/initd script installation
  persistent_load
  query_services
  query_custom_cflags
  persistent_save
# todo:
#ask about conflicts
#ask about other stuff

}

#---------------------------------------------------------------------
## Run the spell's CONFIGURE script if it exists
## @param Spell to configure
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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
    [[ $(hash_get "depends_looked_at" "$requester") == 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
#---------------------------------------------------------------------
function run_other_sub_depends() {
  $STD_DEBUG
  local this_spell=$1
  local SPELL sub_dependee sub_depends pair
  # 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#*:}
    if [[ $(hash_get depends_looked_at $sub_dependee) == 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.
#---------------------------------------------------------------------
function 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 processed_sub_depends $sub_dependee)
      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
    # 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########################

#---------------------------------------------------------------------
## 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
#---------------------------------------------------------------------
function compute_installed_depends() {
  #$1==hash table to fill
  local hash=$1
  touch $DEPENDS_STATUS $SPELL_STATUS &>/dev/null

  local pattern status
  if [[ $2 ]] ; then
    pattern="required|optional|runtime|suggest"
  else
    pattern="required|optional"
  fi
  status=${3:-on}

  # From here forward $1 and $2 are only used to refer to awk variables

  lock_file "$DEPENDS_STATUS"
  lock_file "$SPELL_STATUS"
  # sub(/(.*)/, "", $2) removes a provider name
  eval $(awk -v pattern="$pattern" -v status="$status" -F : 'BEGIN {
    while (getline < ARGV[1] ) {
      if( $3==status && ( $4 ~ pattern ) ) {
        sub(/\(.*\)/, "", $2);
        depmap[$1]=depmap[$1]" "$2" "
      }
    }
    while (getline < ARGV[2] ) {
      if( $3=="installed" || $3=="held") {
        printf("hash_put $hash %s \"%s\";\n",$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 fill with dependencies
#---------------------------------------------------------------------
function compute_reverse_installed_depends() {
  #$1==hash table to fill
  local hash=$1
  touch $DEPENDS_STATUS $SPELL_STATUS &>/dev/null

  local pattern status
  if [[ $2 ]] ; then
    pattern="required|optional|runtime|suggest"
  else
    pattern="required|optional"
  fi
  status=${3:-on}

  # From here forward $1 and $2 are only used to refer to awk variables

  lock_file "$DEPENDS_STATUS"
  lock_file "$SPELL_STATUS"
  # sub(/(.*)/, "", $2) removes a provider name
  eval $(awk -v pattern="$pattern" -v status="$status" -F : 'BEGIN {
    while (getline < ARGV[1] ) {
      if( $3==status && ( $4 ~ pattern ) ) {
        sub(/\(.*\)/, "", $2);
        depmap[$2]=depmap[$2]" "$1" "
      }
    }
    while (getline < ARGV[2] ) {
      if( $3=="installed" || $3=="held") {
        printf("hash_put $hash %s \"%s\";\n",$1,depmap[$1]);
      }
    }
  }' $DEPENDS_STATUS $SPELL_STATUS )
  unlock_file "$DEPENDS_STATUS"
  unlock_file "$SPELL_STATUS"
}

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

  # 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
    if [[ ! `hash_get depends_looked_at ${spells[$_idx]}` ]]; 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
#---------------------------------------------------------------------
function 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"

  # move this up to compute_uninstalled_depends?
  # 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:)

  # 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, ideally we should check in
    # depends/optional_depends and fail there
    if spell_exiled $1; then
      depends_message  "${SPELL}" "is exiled and will not be cast."
      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 echo "${RUNTIME_DEPENDS[*]}"| tr " " "\n" | grep -x -q "$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
#---------------------------------------------------------------------
function private_should_cast()
{
  local each
  # order is important here...
  if ! codex_does_spell_exist $1; then
    return 1
  elif echo "$PRETEND_NOT_INSTALLED" | grep -q " $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 echo "${UP_DEPENDS[*]}"| tr " " "\n" | grep -x -q "$1" ; then
    # if someone has determined this is an upward depend (-B)
    return 0
  elif echo "${TRIGGEREES[*]}"| tr " " "\n" | grep -x -q "$1" ; then
    # if its being triggered we need to look at it, despite its
    # installed status
    return 0
  elif echo "${FORCE_DEPENDS[*]}"| tr " " "\n" | grep -x -q "$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
#---------------------------------------------------------------------
function 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
}

#---------------------------------------------------------------------
## Find spells that optionally depended on the current spell but had the
## dependency disabled, ask if the user wants to recast the spell.
#---------------------------------------------------------------------
function 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

      enabled=""
      message "$spell" "has a disabled optional dependency on" "$1"
      if [[ $RECAST_OPTIONALS == always ]] ; then
        enabled=yes
      else
        local default=n
        [[ $RECAST_OPTIONALS == ask-yes ]] && default=y
        if query "Recast $spell with dependency enabled?" $default ; then
          enabled=yes
        fi
      fi
      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
  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
#---------------------------------------------------------------------
function 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

  # 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
        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
        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 ! codex_does_spell_exist $1 &> /dev/null; 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
#---------------------------------------------------------------------
function real_depends() {
  real_generic_required_depends "no" "a" "dependency" "required" "$@"
}

#---------------------------------------------------------------------
## Passthrough to real_generic_required_depends, specifies the
## parts that differ from required depends
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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

  # 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
        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
        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"
      private_common_depends "$1" "off" "$database_term" "$2" "$3"
    fi
  fi

  local target_spell
  if ! codex_does_spell_exist $1 &> /dev/null; 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
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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 &&
       query "Continue to use ${SPELL_COLOR}$tmp${DEFAULT_COLOR}?" y; then
      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 ]] && echo "$CANDIDATES" | grep -x -q "$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 ]] && echo "$CANDIDATES" | grep -x -q "$tmp" && default=$tmp
  fi

  # check if we've already answered this question
  if [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      echo " ${spells[@]} " |  grep -q " $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
#---------------------------------------------------------------------
function 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"
      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.
#---------------------------------------------------------------------
function 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" &&
          query "Continue to use ${SPELL_COLOR}$tmp${DEFAULT_COLOR}?" y; then
      private_common_depends "$tmp($1)" "on" "$database_term" "$2" "$3"
      return 0
    fi
    if [[ "$(search_depends_status_simple $DEPENDS_STATUS \
                                          "$SPELL" ".*($1)" "off")" ]] &&
        query "Continue to use ${SPELL_COLOR}[none]${DEFAULT_COLOR}?" y; then
      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 ]] && echo "$CANDIDATES" | grep -x -q "$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
      echo " ${spells[@]} " | grep -q " $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 name
## @param  addition to OPTS if enabled
## @param  addition to OPTS if disabled
## @param  description
## Handles optional dependency on a spell.
#---------------------------------------------------------------------
function 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"
    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"
    echo " ${spells[@]} " | grep -q " $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
     query "Do you want to use ${SPELL_COLOR}$1${DEFAULT_COLOR}?" "$stuff" &&
          install="on"
  else
    query "Do you want to cast ${SPELL_COLOR}$1${DEFAULT_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
#---------------------------------------------------------------------
function 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.
#---------------------------------------------------------------------
function real_up_trigger() {
  message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
           "${CHECK_COLOR}triggers a" \
           "${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
#---------------------------------------------------------------------
function 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
  echo " ${NEW_DEPENDS[@]} " | grep -q " $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.
#---------------------------------------------------------------------
function real_sub_depends() {
  $STD_DEBUG
  local requester=$SPELL
  local sub_dependee=$1
  local sub_depends=$2

  message "${SPELL}${DEFAULT_COLOR}" "requests" "$sub_dependee" \
          "${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)
#---------------------------------------------------------------------
function real_force_depends() {
  debug "libdepends" "$FUNCNAME - $SPELL - $@"
  local check=$(hash_get "depends_looked_at" "$1")

  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
#---------------------------------------------------------------------
function 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.
#---------------------------------------------------------------------
function 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.
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function 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 ]] &&
     ! echo "$base_deps"|grep -x -q "$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.
#---------------------------------------------------------------------
function 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
}

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

#---------------------------------------------------------------------
## Removes a dependency from the list.
#---------------------------------------------------------------------
function private_remove_dependees()
{
  local SPELL=$1
  local i
  echo "Removing dependees of $1"

  # spell is being removed from cast list, add to FAILED_LIST
  echo "$SPELL" >> $FAILED_LIST
  hash_put depends_looked_at $SPELL failed
  hash_unset "$CAST_HASH" "$SPELL"
  hash_put $CANNOT_CAST_HASH "$SPELL" "Failed"
}

#---------------------------------------------------------------------
## Sets a spell's aux. config info.
## @Globals SPELL
#---------------------------------------------------------------------
function 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
#---------------------------------------------------------------------
function real_show_up_depends()
{
    local i=0
    local MAX_DEPTH=$2
    local type=$3
    function show_up_depends_sub() {
        local each
        let i++
        [[ $MAX_DEPTH ]] && [[ $i -gt $MAX_DEPTH ]] && return
        for each in $(hash_get foo $1); do
            if ! [[ $(hash_get done $each) ]] ; 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
    if [[ "$type" == "verbose" ]] ; then
      lock_file "$DEPENDS_STATUS"
      show_up_depends_sub "$1"|while read line; do
        grep "$line:" "$DEPENDS_STATUS"
      done
      unlock_file "$DEPENDS_STATUS"
    else
      show_up_depends_sub "$1"|cut -f1 -d:
    fi|sort|uniq
    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
##
#---------------------------------------------------------------------
