#!/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 <spell> (external)
#         -> work_depends_spell
#           -> private_common_depends -> libstate.add_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#       -> optional_depends <spell> (external)
#         -> work_optional_depends_spell
#           -> query
#           -> private_common_depends -> libstate.add_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#       -> depends <provider> (external)
#         -> work_depends_provider
#           -> select provider
#           -> private_common_depends -> libstate.add_depends
#             -> add to NEW_DEPENDS
#             -> libstate.add_depends
#       -> optional_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"
 
  message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
           "${CHECK_COLOR}preparing environment...${DEFAULT_COLOR}"

  # 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)
  local SPELL_DIRECTORY=$SCRIPT_DIRECTORY
  local SECTION_DIRECTORY=${SPELL_DIRECTORY%/*}
  local GRIMOIRE=${SECTION_DIRECTORY%/*}

  local PROTECT_SORCERY=yes
  if  [  -x  $SCRIPT_DIRECTORY/PREPARE  ];  then
    # we need &&'s to preserve the proper return code (persistant_save
    # will probably succeed even if PREPARE fails)
    persistent_load &&
    . $SCRIPT_DIRECTORY/PREPARE &&
    persistent_save
  fi
}

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

 
  local PROTECT_SORCERY=yes
  if  [  -x  $SCRIPT_DIRECTORY/CONFIGURE  ];  then
    message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
             "${CHECK_COLOR}running configuration...${DEFAULT_COLOR}"
    # we need &&'s to preserve the proper return code (persistant_save
    # will probably succeed even if PREPARE fails)
    persistent_load &&
    . $SCRIPT_DIRECTORY/CONFIGURE &&
    persistent_save
  fi
}

#---------------------------------------------------------------------
## Run a spell's DEPENDS if it exists
## @param Spell
#---------------------------------------------------------------------
function run_depends() 
{ 
  local SPELL=$1
  debug "cast" "run_depends() - SCRIPT_DIRECTORY = $SCRIPT_DIRECTORY"
 
  local PROTECT_SORCERY=yes
  if  [  -x  $SCRIPT_DIRECTORY/DEPENDS  ];  then
    message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
             "${CHECK_COLOR}checking dependencies...${DEFAULT_COLOR}"

    # we need &&'s to preserve the proper return code (persistant_save
    # will probably succeed even if PREPARE fails)
    persistent_load &&
    .  $SCRIPT_DIRECTORY/DEPENDS &&
    persistent_save
  fi
}

#---------------------------------------------------------------------
## 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"
 
  local PROTECT_SORCERY=yes
  if  [  -x  $SCRIPT_DIRECTORY/UP_TRIGGERS ];  then
    message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
             "${CHECK_COLOR}checking for reverse triggers...${DEFAULT_COLOR}"
    # we need &&'s to preserve the proper return code (persistant_save
    # will probably succeed even if PREPARE fails)
    persistent_load &&
    . $SCRIPT_DIRECTORY/UP_TRIGGERS &&
    persistent_save
  fi
  
}
######################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

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

  # sub(/(.*)/, "", $2) removes a provider name
  eval $(awk -F : 'BEGIN {
    while (getline < ARGV[1] ) {
      if( $3=="on") {
        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 )
}

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

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

  # sub(/(.*)/, "", $2) removes a provider name
  eval $(awk -F : 'BEGIN {
    while (getline < ARGV[1] ) {
      if( $3=="on") {
        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 )
}

#---------------------------------------------------------------------
## 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"
  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 this, no sense in keeping it around
  hash_unset depends_looked_at

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

#---------------------------------------------------------------------
## 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
  local NEW_DEPENDS=""
  local triggerees=""
  local spell_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
      message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
               "${CHECK_COLOR}is exiled and will not be cast.${DEFAULT_COLOR}"
      return 1
    fi
    get_uncommitted_depends_file $SPELL spell_depends
    if  [  -n  "$RECONFIGURE"  ];  then
      rm  -f  $DEPENDS_CONFIG/$SPELL
      test -f $DEPENDS_CONFIG/$SPELL.p &&
      mkdir -p $ABANDONED_PERSIST      &&
      mv  -f  $DEPENDS_CONFIG/$SPELL.p $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        && 

    # possibly recast things that depend on us if option is set (-B)
    private_upward_depends $SPELL &&
    private_add_triggerees        &&
    private_add_depends           ||
    { debug "libdepends" "$FUNCNAME: false inside if." ; return 1; }
    # no point in keeping the file around if its empty...
    test -s $spell_depends || rm $spell_depends
  else 
    message  "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
             "${CHECK_COLOR}No work to do.${DEFAULT_COLOR}"
    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 case. Check if the spell is installed
## if it matters, etc...
## Perhaps this function is overly splayed out in elif's but its
## easier to add to later than what we had before...
## @param Spell
#---------------------------------------------------------------------
function private_should_cast()
{
  local decision
  # 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 spell_installed $1 ; then
    # spell is installed and no -R or -B, so dont cast
    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)
    tmp=$(grep "^.*:$1\(([^:]*)\)\?" $DEPENDS_STATUS|cut -f1 -d:|tr "\n" " ")
    local j each
    let j=${#UP_DEPENDS[*]}
    for each in $tmp; do
      UP_DEPENDS[$j]=$each
      let j++
    done
    spells=( ${spells[*]} ${tmp} )
  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
#---------------------------------------------------------------------
function real_depends()
{
  # see if theres another grimoire
  if [[ "$4" ]] ; 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}"
      return 1
    fi
  fi

  if ! codex_does_spell_exist $1 &> /dev/null; then
    work_depends_provider "$@"
  else
    work_depends_spell "$@"
  fi

}

#---------------------------------------------------------------------
## @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.
#---------------------------------------------------------------------
function real_optional_depends()
{

  # see if theres another grimoire
  if [[ "$5" ]] ; 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" "optional" "$2" "$3"
    fi
  fi

  if ! codex_does_spell_exist $1 &> /dev/null; then
    work_optional_depends_provider "$@"
  else
    work_optional_depends_spell "$@" 
  fi

}

#---------------------------------------------------------------------
## 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 status=()

  if [[ $3 ]] ; then
    message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
            "${CHECK_COLOR}requires some${DEFAULT_COLOR}" \
            "${SPELL_COLOR}${1}${DEFAULT_COLOR} ($3)."
  else
    message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
            "${CHECK_COLOR}requires some${DEFAULT_COLOR}" \
            "${SPELL_COLOR}${1}${DEFAULT_COLOR}."
  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}"
    return 1
  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" "required" "$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 -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 -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 [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      spell_ok $tmp && default=$tmp && break
    done
  fi

  select_provider "provider" "$default" 0 $CANDIDATES

  private_common_depends "$provider($1)" "on" "required" "$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
## @param disabled options (useless, but included for some reason)
## @param grimoire the spell is in, if its different than the current one
#---------------------------------------------------------------------
function work_depends_spell()
{
  debug "libdepends" "$FUNCNAME - $@"

  message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
          "${CHECK_COLOR}depends on" \
          "${SPELL_COLOR}${1}${DEFAULT_COLOR}"

  if spell_exiled $1 ; then
    hash_put $CANNOT_CAST_HASH "$1" "Exiled"
    message "${SPELL_COLOR}${1}${DEFAULT_COLOR} has been exiled!"
    return 1
  fi
  private_common_depends "$1" "on" "required" "$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 installed=no
  local status=()

  if [[ $4 ]] ; then
    message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
            "${CHECK_COLOR}optionally requires some${DEFAULT_COLOR}" \
            "${SPELL_COLOR}${1}${DEFAULT_COLOR} ($4)."
  else
    message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
            "${CHECK_COLOR}optionally requires some${DEFAULT_COLOR}" \
            "${SPELL_COLOR}${1}${DEFAULT_COLOR}."
  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 $DEPENDS_STATUS "$SPELL" ".*($1)")" ":" "status"
    local 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" "required" "$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 -q "\<$tmp\>" && default=$tmp
  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
        [[ $tmp ]] && echo $CANDIDATES|grep -q "\<$tmp\>" &&
        default=$tmp || default=none
      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 [[ ! $default ]]; then
    for tmp in $CANDIDATES; do
      spell_ok $tmp && default=$tmp && break
    done
  fi

  select_provider "provider" "$default" 1 $CANDIDATES

  if [ $provider == "none" ] ; then
    private_common_depends "($1)" "off" "optional" "$2" "$3"
  else
    private_common_depends "$provider($1)" "on" "optional" "$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
  
  # if $1 optionally depends on something exiled we always say no
  if spell_exiled $1 ; then 
    message "${SPELL_COLOR}${1}${DEFAULT_COLOR} has been exiled! not using as a depends"
    hash_put $CANNOT_CAST_HASH "$1" "Exiled"
    private_common_depends "$1" "off" "optional" "$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
        message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
                "${CHECK_COLOR}optionally depends on" \
                "${SPELL_COLOR}${1}${DEFAULT_COLOR}"
      else
        message "${SPELL_COLOR}${SPELL}${DEFAULT_COLOR}" \
                "${CHECK_COLOR}has a disabled optional depends on" \
                "${SPELL_COLOR}${1}${DEFAULT_COLOR}"
      fi
      private_common_depends "$1" "${status[2]}" "optional" "$2" "$3"
      return 0
    fi
  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"
    #\< and \> match the empty string at the start and end of a word
    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

  message "${SPELL_COLOR}${1}${DEFAULT_COLOR}" \
          "is an optional dependency for" \
          "${SPELL_COLOR}$SPELL${DEFAULT_COLOR} ($4)"

  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" "optional" "$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 answer spell

    # 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

    message -n "\n${QUERY_COLOR}Which one do you want? " \
               "[$default_char]$DEFAULT_COLOR "
    read   -t  $PROMPT_DELAY  -n  1 answer 
    [[ $answer ]] || answer=$default_char
    spell="$(hash_get CHAR_TO_SPELL $answer)"

    while [[ ! $spell ]] ; do
      message -n "\n${QUERY_COLOR}Which one do you want? " \
                 "[$default_char]$DEFAULT_COLOR "
      read   -t  $PROMPT_DELAY  -n  1 answer 
      [[ $answer ]] || answer=$default_char
      spell=$(hash_get CHAR_TO_SPELL $answer)
    done
    echo
    hash_unset CHAR_TO_SPELL
    eval $returnvar=\"$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 "
  echo $NEW_DEPENDS | grep -q "$TARGET" || 
  NEW_DEPENDS=( ${NEW_DEPENDS[*]} $spell)
  triggerees=( ${triggerees[*]} $TARGET )
}

#---------------------------------------------------------------------
# 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_COLOR}${SPELL}${DEFAULT_COLOR}" \
          "${CHECK_COLOR}is forcing a recast of" \
          "${SPELL_COLOR}${1}${DEFAULT_COLOR}"

  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" "$@"
  
  if [[ $2 == on ]] ; then
    # ${1%(*} = spell name (strips potential provider name)
    local spell_name=${1%(*}
    NEW_DEPENDS=( ${NEW_DEPENDS[*]} $spell_name )
  fi
  
  return 0
}

#---------------------------------------------------------------------
## Default trigger checking function. Asks user if they want to
## run the trigger.
#---------------------------------------------------------------------
function default_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() {
    running_trigger=0
    persistent_load
    if test -x $SCRIPT_DIRECTORY/TRIGGER_CHECK; then
      source $SCRIPT_DIRECTORY/TRIGGER_CHECK
    else
      default_trigger_check
    fi
    running_trigger=$?
    persistent_save
    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_put "$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 -q $SPELL; then
    hash_append "$CAST_HASH" "$SPELL" "basesystem"
    hash_append "$BACK_CAST_HASH" "basesystem" "$SPELL"
  fi

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

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

  hash_put "depends_looked_at" "$SPELL" "done"

}


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

#---------------------------------------------------------------------
# i dont know if this should be here
#---------------------------------------------------------------------
function show_depends()  
{
  debug "libdepends" "show_depends() - $@"
  local DEP_SPELL=`esc_str $1`
  local DEPTH=$2

  if  !  echo  "$DONE"  |  grep  -q  "$DEP_SPELL";  then
    DONE="$DONE  $1"

    function ld99()  {

     [[ $MAX_DEPTH ]] && [[ $DEPTH -ge $MAX_DEPTH ]] && return 1
 
      SPELL=`echo  $1 |  cut  -d :  -f1`
      STATUS=`echo  $1  |  cut  -d :  -f3`

      if    [  "$STATUS"  ==  "on"  ]; then
        echo          $1 
        show_depends  $SPELL $(( DEPTH + 1 ))
      fi
      
    }
    
    iterate "ld99" $'\n' "$(grep  ":$DEP_SPELL\(([^:]*)\)\?:" $DEPENDS_STATUS)"

  fi
}

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