/* File:      tst_aux.h
** Author(s): Ernie Johnson
** Contact:   xsb-contact@cs.sunysb.edu
** 
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
** 
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
** 
** XSB 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 Library General Public License for
** more details.
** 
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: tst_aux.h,v 1.7 2001/04/28 20:15:37 ejohnson Exp $
** 
*/


#ifndef PRIVATE_TST_DEFS

#define PRIVATE_TST_DEFS

#include "debugs/debug_tables.h"
#include "debugs/debug_tries.h"
#include "dynamic_stack.h"


/*===========================================================================*/

/*
 *                     Auxiliary Data Structures
 *                     =========================
 *
 *  This file contains typedefs of and macros for using some objects
 *  universally needed by the subsumptive components of the engine,
 *  i.e. the operations:
 *
 *  i) Subsumptive Call Check/Insert
 *  ii) Variant TST Answer Check/Insert
 *  iii) Relevant Answer Identification
 *  iv) Answer Consumption
 */

/*---------------------------------------------------------------------------*/

/*
 *  tstTermStack
 *  ------------
 *  For flattening a heap term during processing.
 */

extern DynamicStack tstTermStack;
#define TST_TERMSTACK_INITSIZE    25

#define TermStack_Top		((CPtr)DynStk_Top(tstTermStack))
#define TermStack_Base		((CPtr)DynStk_Base(tstTermStack))
#define TermStack_NumTerms	DynStk_NumFrames(tstTermStack)
#define TermStack_ResetTOS	DynStk_ResetTOS(tstTermStack)
#define TermStack_IsEmpty	DynStk_IsEmpty(tstTermStack)

#define TermStack_SetTOS(Index)			\
   DynStk_Top(tstTermStack) = TermStack_Base + Index

#define TermStack_Push(Term) {			\
   CPtr nextFrame;				\
   DynStk_Push(tstTermStack,nextFrame);		\
   *nextFrame = Term;				\
 }

#define TermStack_BlindPush(Term) {		\
   CPtr nextFrame;				\
   DynStk_BlindPush(tstTermStack,nextFrame);	\
   *nextFrame = Term;				\
 }

#define TermStack_Pop(Term) {			\
   CPtr curFrame;				\
   DynStk_BlindPop(tstTermStack,curFrame);	\
   Term = *curFrame;				\
 }

#define TermStack_Peek(Term) {			\
   CPtr curFrame;				\
   DynStk_BlindPeek(tstTermStack,curFrame);	\
   Term = *curFrame;				\
 }

/* Specialty Pushing Macros
   ------------------------ */
#define TermStack_NOOP      /* Nothing to push when constants match */

#define TermStack_PushFunctorArgs(CS_Cell)                   \
   TermStack_PushLowToHighVector( clref_val(CS_Cell) + 1,    \
				  get_arity((Psc)*clref_val(CS_Cell)) )

#define TermStack_PushListArgs(LIST_Cell) {	\
   CPtr pListHeadCell = clref_val(LIST_Cell);	\
   DynStk_ExpandIfOverflow(tstTermStack,2);	\
   TermStack_BlindPush( *(pListHeadCell + 1) );	\
   TermStack_BlindPush( *(pListHeadCell) );	\
 }

/*
 * The following macros enable the movement of an argument vector to
 * the TermStack.  Two versions are supplied depending on whether the
 * vector is arranged from high-to-low memory, such as an answer
 * template, or from low-to-high memory, such as the arguments of a
 * compound heap term.  The vector pointer is assumed to reference the
 * first element of the vector.
 */

#define TermStack_PushLowToHighVector(pVectorLow,Magnitude) {	\
   int i, numElements;						\
   CPtr pElement;						\
								\
   numElements = Magnitude;					\
   pElement = pVectorLow + numElements;				\
   DynStk_ExpandIfOverflow(tstTermStack,numElements);		\
   for (i = 0; i < numElements; i++) {				\
     pElement--;						\
     TermStack_BlindPush(*pElement);				\
   }								\
 }
   
#define TermStack_PushHighToLowVector(pVectorHigh,Magnitude) {	\
   int i, numElements;						\
   CPtr pElement;						\
								\
   numElements = Magnitude;					\
   pElement = pVectorHigh - numElements;			\
   DynStk_ExpandIfOverflow(tstTermStack,numElements);		\
   for (i = 0; i < numElements; i++) {				\
     pElement++;						\
     TermStack_BlindPush(*pElement);				\
   }								\
 }

/*
 * This macro copies an array of terms onto the TermStack, checking for
 * overflow only once at the beginning, rather than with each push.  The
 * elements to be pushed are assumed to exist in array elements
 * 0..(NumElements-1).
 */

#define TermStack_PushArray(Array,NumElements) {	\
   counter i;						\
   DynStk_ExpandIfOverflow(tstTermStack,NumElements);	\
   for ( i = 0;  i < NumElements;  i++ )		\
     TermStack_BlindPush(Array[i]);			\
 }

/* ------------------------------------------------------------------------- */

/*
 *  tstTermStackLog
 *  ---------------
 *  For noting the changes made to the tstTermStack during processing
 *  where backtracking is required.  Only the changes necessary to
 *  transform the tstTermStack from its current state to a prior state
 *  are logged.  Therefore, we only need record values popped from the
 *  tstTermStack.
 *
 *  Each frame of the log consists of the index of a tstTermStack
 *  frame and the value that was stored there.  tstTermStack values
 *  are reinstated as a side effect of a tstTermStackLog_Pop.
 */

typedef struct {
  int index;             /* location within the tstTermStack... */
  Cell value;            /* where this value appeared. */
} tstLogFrame;
typedef tstLogFrame *pLogFrame;

#define LogFrame_Index(Frame)	( (Frame)->index )
#define LogFrame_Value(Frame)	( (Frame)->value )


extern DynamicStack tstTermStackLog;
#define TST_TERMSTACKLOG_INITSIZE    20

#define TermStackLog_Top	((pLogFrame)DynStk_Top(tstTermStackLog))
#define TermStackLog_Base	((pLogFrame)DynStk_Base(tstTermStackLog))
#define TermStackLog_ResetTOS	DynStk_ResetTOS(tstTermStackLog)

/*
 * This doesn't always immediately follow a pop of the TermStack (see
 * tst_retrv.c).  Therefore the subterm is obtained from the TermStack
 * directly before more terms are pushed onto it.
 */
#define TermStackLog_PushFrame {				\
   pLogFrame nextFrame;						\
   DynStk_Push(tstTermStackLog,nextFrame);			\
   LogFrame_Index(nextFrame) = TermStack_Top - TermStack_Base;	\
   LogFrame_Value(nextFrame) = *(TermStack_Top);		\
 }

#define TermStackLog_PopAndReset {					\
   pLogFrame curFrame;							\
   DynStk_BlindPop(tstTermStackLog,curFrame)				\
   TermStack_Base[LogFrame_Index(curFrame)] = LogFrame_Value(curFrame);	\
 }

/*
 * Reset the TermStack elements down to and including the Index-th
 * entry in the Log.
 */
#define TermStackLog_Unwind(Index) {			\
   pLogFrame unwindBase = TermStackLog_Base + Index;	\
   while ( TermStackLog_Top > unwindBase )		\
     TermStackLog_PopAndReset;				\
 }

/* ------------------------------------------------------------------------- */

/*
 *  tstSymbolStack
 *  ---------------
 *  For constructing terms from the symbols stored along a path in the trie.
 */

extern DynamicStack tstSymbolStack;
#define TST_SYMBOLSTACK_INITSIZE   25

#define SymbolStack_Top		  ((CPtr)DynStk_Top(tstSymbolStack))
#define SymbolStack_Base	  ((CPtr)DynStk_Base(tstSymbolStack))
#define SymbolStack_NumSymbols	  (SymbolStack_Top - SymbolStack_Base)
#define SymbolStack_ResetTOS	  DynStk_ResetTOS(tstSymbolStack)
#define SymbolStack_IsEmpty	  DynStk_IsEmpty(tstSymbolStack)

#define SymbolStack_Push(Symbol) {		\
   CPtr nextFrame;				\
   DynStk_Push(tstSymbolStack,nextFrame);	\
   *nextFrame = Symbol;				\
 }

#define SymbolStack_Pop(Symbol) {		\
   CPtr curFrame;				\
   DynStk_BlindPop(tstSymbolStack,curFrame);	\
   Symbol = *curFrame;				\
}

#define SymbolStack_Peek(Symbol) {		\
   CPtr curFrame;				\
   DynStk_BlindPeek(tstSymbolStack,curFrame);	\
   Symbol = *curFrame;				\
}

#define SymbolStack_PushPathRoot(Leaf,Root) {	\
   BTNptr btn = (BTNptr)Leaf;			\
   while ( ! IsTrieRoot(btn) ) {		\
     SymbolStack_Push(BTN_Symbol(btn));		\
     btn = BTN_Parent(btn);			\
   }						\
   Root = (void *)btn;				\
 }

#define SymbolStack_PushPath(Leaf) {  		\
   BTNptr root;					\
   SymbolStack_PushPathRoot(Leaf,root);		\
 }

/* ------------------------------------------------------------------------- */

/*
 *  tstTrail
 *  ---------
 *  For recording bindings made during processing.  This Trail performs
 *  simple WAM trailing -- it saves address locations only.
 */

extern DynamicStack tstTrail;
#define TST_TRAIL_INITSIZE    20

#define Trail_Top		((CPtr *)DynStk_Top(tstTrail))
#define Trail_Base		((CPtr *)DynStk_Base(tstTrail))
#define Trail_NumBindings	DynStk_NumFrames(tstTrail)
#define Trail_ResetTOS		DynStk_ResetTOS(tstTrail)

#define Trail_Push(Addr) {			\
   CPtr *nextFrame;				\
   DynStk_Push(tstTrail,nextFrame);		\
   *nextFrame = (CPtr)(Addr);			\
 }

#define Trail_PopAndReset {			\
   CPtr *curFrame;				\
   DynStk_BlindPop(tstTrail,curFrame);		\
   bld_free(*curFrame);				\
 }

#define Trail_Unwind_All	Trail_Unwind(0)

/*
 * Untrail down to and including the Index-th element.
 */
#define Trail_Unwind(Index) {			\
   CPtr *unwindBase = Trail_Base + Index;	\
   while ( Trail_Top > unwindBase )		\
     Trail_PopAndReset;				\
 }

/*=========================================================================*/

/*
 *			Using the Trie Stacks
 *			=====================
 */

#define ProcessNextSubtermFromTrieStacks(Symbol,StdVarNum) {	\
								\
   Cell subterm;						\
								\
   TermStack_Pop(subterm);					\
   XSB_Deref(subterm);						\
   switch ( cell_tag(subterm) ) {				\
   case XSB_REF:						\
   case XSB_REF1:						\
     if ( ! IsStandardizedVariable(subterm) ) {			\
       StandardizeVariable(subterm, StdVarNum);			\
       Trail_Push(subterm);					\
       Symbol = EncodeNewTrieVar(StdVarNum);			\
       StdVarNum++;						\
     }								\
     else							\
       Symbol = EncodeTrieVar(IndexOfStdVar(subterm));		\
     break;							\
   case XSB_STRING:						\
   case XSB_INT:						\
   case XSB_FLOAT:						\
     Symbol = EncodeTrieConstant(subterm);			\
     break;							\
   case XSB_STRUCT:						\
     Symbol = EncodeTrieFunctor(subterm);			\
     TermStack_PushFunctorArgs(subterm);			\
     break;							\
   case XSB_LIST:						\
     Symbol = EncodeTrieList(subterm);				\
     TermStack_PushListArgs(subterm);				\
     break;							\
   default:							\
     Symbol = 0;  /* avoid "uninitialized" compiler warning */	\
     TrieError_UnknownSubtermTag(subterm);			\
   }								\
 }

/*=========================================================================*/


#endif
