/******************************************************************
 *  (C) Copyright 1994; dit/upm
 *  Distributed under the conditions stated in the
 *  TOPO General Public License (see file LICENSE)
 ******************************************************************
 *  $Log$
 ******************************************************************/

#ifndef lint
static char rcsid[]= "$Id$";
#endif

/******************************************************************
 *
 *  Santiago Pavon Gomez
 *
 *  17 Jan 1990
 *
 *  Management of LOTOS data type expressions
 *
 *  LOTOS data type expressions terms can be either variables or
 *  operations. Operations can have a list of operands.
 *  Variables can have one (hidden) value called Parameterized Value.
 *  That is the value the variable is symbolically standing for,
 *  during parameterised expansions.
 *  Data type subexpressions can be shared.
 *
 *  COMPILATION FLAGS:
 *     SDEBUG : activate debugging
 *
 *  LOG:
 *     21/09/9. santiago.
 *     Implementation of sharing in expressions.
 *     The operands are contained in a list of shareable expressions.
 *
 ******************************************************************/

/* LINTLIBRARY */

/* KJT 12/02/12: Added */
#include <stdlib.h>
#include "baexpr.h"
#include "batables.h"
#include "limisc.h"

/* KJT 22/01/23: added function prototypes */
int GetEqual();

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

/* IncCopyE
 * Increment the copy field of the cell c.
 */
#define IncCopyE(c) {(c)->copy += ((c)->copy)>=0  ? 1 : -1;}

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

/* DecCopyE
 * Decrement the copy field of the cell c.
 */
#define DecCopyE(c)  {(c)->copy -= ((c)->copy)>=0  ? 1 : -1;}


/******************************************************************
 *                                                                *
 *       Account of the number of the expression cells used       *
 *                                                                *
 ******************************************************************/

static int new_expr_count      = 0;
static int max_expr_count      = 0;
static int released_expr_count = 0;

/*
 * Account of the number of the tree nodes used.
 *
 */
static int new_tnode_count      = 0;
static int released_tnode_count = 0;
static int max_tnode_count      = 0;

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

/* InitE
 * Init this module
 */
void InitE()
{
#ifdef SDEBUG
  new_tnode_count      = 0;
  released_tnode_count = 0;
  max_tnode_count      = 0;
  new_expr_count       = 0;
  released_expr_count  = 0;
  max_expr_count       = 0;
#endif
}

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

/* StatE
 * Give statistics about the expression cells allocated and released.
 * nc  : number of expression cell queries originated by this module.
 * rc  : expression cell releases.
 * mc  : max used expression cells
 * ntn : number of tnodes queries originated by this module.
 * rtn : tnode releases.
 * mtn : max used tnodes
 */
void StatE( nc, rc, mc, ntn, rtn, mtn )
     int *nc, *rc, *mc, *ntn, *rtn, *mtn;
{
  *nc  = new_expr_count;
  *rc  = released_expr_count;
  *mc  = max_expr_count;
  *ntn = new_tnode_count;
  *rtn = released_tnode_count;
  *mtn = max_tnode_count;
}

/******************************************************************
 *                                                                *
 *              Functions to manage expression cells.             *
 *                                                                *
 ******************************************************************/

/* NewExprCell
 * Get memory for a new cell
 */
static ExprTyp NewExprCell()
{
#ifdef SDEBUG
  new_expr_count++;
  max_expr_count = MAX( max_expr_count, new_expr_count-released_expr_count );
#endif
  return (ExprTyp)NewCellM(sizeof(struct exprNodeTyp));
}

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

/* FreeExprCell
 * Dispose the memory used by the cell c.
 */
static void FreeExprCell( c )
     ExprTyp    c;
{
#ifdef SDEBUG
  released_expr_count++;
#endif
  FreeCellM( (void*)c , sizeof(struct exprNodeTyp) );
}

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

/* CopyECell
 * Copy the expression cell t.
 * Links e1 and e2 are set to NULL.
 */
static ExprTyp CopyECell( t )
     ExprTyp t;
{
  ExprTyp  nc;

  nc       = NewExprCell();
  nc->sons = NULL;
  nc->name = t->name;
  return nc;
}

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

/* StatExprReal
 * Statistic of the expression e with sharing.
 * po, pv and pl are the number of operation cells, variable cells and list
 * nodes respectively.
 */
static void StatExprReal( e, po, pv, pl )
     ExprTyp  e;
     int     *po, *pv, *pl;
{
  int var,op,list,n,i;

  *po = *pv = *pl = 0;
  if ( e != NULL ) {
    if ( !VisitedE(e) ) {
      if ( IsVariableE(e) ) {
	*pl = LookPVarE(e)!=NULL ? 1 : 0;
	++(*pv);
	StatExprReal(LookPVarE(e), &op, &var, &list );
	*po += op;
	*pv += var;
	*pl += list;
      }
      else {
	n = NumArgE(e);
	*pl = n;
	++(*po);
	for ( i=1; i<=n; i++ ) {
	  StatExprReal(LookArgE(e,i), &op, &var, &list );
	  *po += op;
	  *pv += var;
	  *pl += list;
	}
      }
    }
  }
}

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

/* StatExprVirtual
 * Statistic of the expression e without sharing.
 *  po, pv and pl are the number of operation cells, variable cells and list
 *  nodes respectively.
 */
static void StatExprVirtual( e, po, pv, pl )
     ExprTyp e;
     int     *po, *pv, *pl;
{
  int var,op,list,n,i;

  *po = *pv = *pl = 0;
  if (e != NULL) {
    LASSERT(OwnersE(e)!=0);
    if (IsVariableE(e)) {
      *pl = LookPVarE(e)!=NULL ? 1 : 0;
      ++(*pv);
      StatExprVirtual(LookPVarE(e), &op, &var, &list );
      *po += op;
      *pv += var;
      *pl += list;
    }
    else {
      n = NumArgE(e);
      *pl = n;
      ++(*po);
      for (i=1 ; i<=n ; i++) {
	StatExprVirtual(LookArgE(e,i), &op, &var, &list );
	*po += op;
	*pv += var;
	*pl += list;
      }
    }
  }
}

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

/* StatisticE
 * Statistic of node use in a single expression.
 *  nv,vv and ov are the virtual values of number of list nodes,
 *   variable and operation cells, i.e. without paying attention to the
 *   sharing feature.
 *  nr,vr and or are the real values, i.e. nodes and cells already counted
 *   in other expressions are not counted again here.
 */
void StatisticE( e, nv, vv, ov, nr, vr, or )
     ExprTyp e;
     int    *nv, *vv, *ov, *nr, *vr, *or;
{
  StatExprVirtual( e, ov, vv, nv );
  StatExprReal( e, or, vr, nr );
}


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

static int print_parameterized = PRINT_PARAM;

/* SetPrintParamE
 * Set the printing mode for the parameterized values in the expressions for
 * all the following calls to PrintE or ExprToStringE.
 *
 *  Modes :                                                         Examples:
 *
 *  PRINT_PARAM      -> the parameterized value
 *                      is printed as a comment. (default)               x(*E*)
 *  PRINT_ONLY_PARAM -> only the parameterized value is printed.         E
 *  PRINT_NO_PARAM   -> no parameterized value is printed.               x
 *
 */
void SetPrintParamE( mode )
     int mode;
{
  print_parameterized = mode;
}

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

/* PrintE
 * Print the expression e.
 * pstr is the function used to print strings.
 */
void PrintE( e, pstr )
     ExprTyp  e ;
     void     (*pstr)();
{
  char * stre;

  stre = ExprToStringE(e);
  pstr(stre);
  free(stre);
}


/******************************************************************
 *                                                                *
 *           ExprToStringE:                                        *
 *                                                                *
 *              - Constant and type definitions                   *
 *              - Auxiliar functions                              *
 *              - ExprToStringE function                           *
 *                                                                *
 ******************************************************************/


/*
 *  Esteban Perez Milla
 *
 *  19 May 92
 *
 *  This part of the module defines the function ExprToStringE,
 *  and the auxiliar functions, types and constants it uses.
 *  ExprToStringE converts an expression to a string, writing
 *  the necessary "ofsort"s, that make the string determine the
 *  operation correctly. The algorithm used writes the "ofsort"s,
 *  in the outer operations if possible, so as to write the minumum
 *  number of "ofsort"s.
 *
 */

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



/******************************************************************
 *                                                                *
 *        Constant and type definitions (ExprToStringE)            *
 *                                                                *
 ******************************************************************/

/* Ofsort constants
 */
#define OFSORT_NOT_COMPUTED  0
#define OFSORT_TRUE          1
#define OFSORT_FALSE        -1


/*  Structure of a node of the tree.
 *
 *    desc          : descriptor of the operation or variable.
 *    ofsort        : flag indicating the "ofsort" of the node (true, false or
 *                    not computed).
 *    possibleopsl  : list of possible operations in "ofsort" conflict
 *                    with the operation of the node.
 *    args          : pointer to the first argument of the node.
 *    nextfatherarg : pointer to the next argument of the father.
 *
 *  If the node represents a variable, it doesn't matter the value
 *  of the fields nextfatherarg, ofsort and possibleopsl.
 *
 */
typedef struct TNode { DescriptorTyp   desc;
		       int             ofsort;
		       ListTyp         possibleopsl;
		       struct TNode    *args;
		       struct TNode    *nextfatherarg;
		     } TNodeTyp, *TNodePtTyp;


/******************************************************************
 *                                                                *
 *                 Auxiliar functions (ExprToStringE)              *
 *                                                                *
 ******************************************************************/


/* IsOfsortExpr
 * Check if there are "ofsort" type operations in the expression e.
 * Return true if there is one "ofsort" type operation, at least, in e.
 * Return false if there aren't any "ofsort" type operations in e.
 */
static boolean IsOfsortExpr( e )
     ExprTyp e;
{
  boolean ofsort;
  int     n,i;
  ExprTyp ae;

  if (IsVariableE(e))  /*  e is a variable */
    ofsort = FALSE;
  else {
    ofsort = GetO_ofsort(LookNameE(e));
    n      = NumArgE(e);
    for ( i=1; (!ofsort) && (i<=n); i++ ) {
      ae     = LookArgE(e,i);
      ofsort = IsOfsortExpr(ae);
    }
  }
  return ofsort;
}

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

/* Split
 * Check if str is a string of type name_number.
 * If it is of that type, Split writes the number in the position
 * pointed by num and returns a string containing the name.
 * If it is not of that type, Split writes 0 in the position pointed
 * by num and returns NULL.
 */
static char *Split( str, num )
     char  *str;
     int   *num;
{
  char *name, *auxnum;
  int  i, j, k;

  for ( i=strlen(str)-1; (i>=0) && (str[i]>='0') && (str[i]<='9'); i-- )
    ;
  if ((str[i]=='_') && (i>0) && (i<strlen(str)-1)) {
    name=(char*)emalloc(i+1);
    for (j=0; j<i; j++)
      name[j]=str[j];
    name[j] = '\0';
    auxnum  = (char*)emalloc(strlen(str)-i);
    for ( j=i+1, k=0; (auxnum[k]=str[j])!='\0'; j++, k++ )
      ;
    *num = StringToInt(auxnum);
    free(auxnum);
  }
  else {
    name = NULL;
    *num = 0;
  }
  return name;
}

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

/* VarToStrE
 * Convert a variable expression e, to a string.
 * The value of print_parameterized is used.
 */
static char* VarToStrE( e )
     ExprTyp e;
{
  char *res, *aux, *auxres;

  res = NULL;
  if ((print_parameterized!=PRINT_ONLY_PARAM) || (LookPVarE(e)==NULL) ){
    res = (char*)emalloc(strlen(GetV_name(LookNameE(e)))+15);
    (void) sprintf(res, "%s_%d", GetV_name(LookNameE(e)), -LookNameE(e));
  }
  if ( LookPVarE(e)!=NULL && (print_parameterized == PRINT_PARAM ||
			      print_parameterized == PRINT_ONLY_PARAM )) {
    aux    = ExprToStringE(LookPVarE(e));
    if ( res!=NULL ){
      auxres = CopyString(res);
      res    = (char*)erealloc( (void*)ALIGN(res),
			       strlen(auxres)+strlen(aux)+5);
      (void)sprintf(res, "%s(*%s*)", auxres, aux);
      free(auxres);
    }
    else {
      res = (char*)emalloc(strlen(aux)+1);
      (void)sprintf( res, "%s", aux );
    }
    free(aux);
  }
  return (char*)res;
}

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

/* ConstToStrE
 * Convert a constant expression e, into a string.
 * If the name of the constant is name_number type, and
 * there is a variable, with name name in number position
 * in the table of variables, it returns the name of the constant
 * with ofsort.
 */
static char * ConstToStrE( e )
     ExprTyp e;
{
  char *res, *nameC;
  int  numC;

  if (((nameC=Split(GetO_name(LookNameE(e)), &numC))!=NULL) &&
      (numC>0) &&
      (numC<=LastTableV()) && (strcmp(nameC, GetV_name(-numC))==0)) {
    res = (char*)emalloc( strlen(GetO_name(LookNameE(e)))
			 +strlen(GetS_name(LookSortE(e)))+5
			 );
    (void) sprintf(res, "%s of %s", GetO_name(LookNameE(e)),
		   GetS_name(LookSortE(e)));
  }
  else
    res = CopyString(GetO_name(LookNameE(e)));
  return res;
}

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

/* NoOfsortEToS
 * Convert an expression e, without "ofsort" operations, to a string
 * that represents it.
 */
static char * NoOfsortEToS( e )
     ExprTyp e;
{
  ExprTyp ae;
  char   *aux1, *aux2, *res, *auxres, *oname;
  int     n,i;

  if (IsVariableE(e)) /* e is a variable */
    res = VarToStrE(e);
  else if (LookArgE(e,1)==NULL) /* e is a constant */
    res = ConstToStrE(e);
  else if (GetO_infix(LookNameE(e))) {  /* e is an infix operation */
    oname = CopyString(GetO_name(LookNameE(e)));
    ae    = LookArgE(e,1);
    aux1  = NoOfsortEToS(ae);
    ae    = LookArgE(e,2);
    aux2  = NoOfsortEToS(ae);
    res   = (char*)emalloc(strlen(aux1)+strlen(oname)+strlen(aux2)+5);
    if (IsOperationE(ae) && GetO_infix(LookNameE(ae)))
      (void) sprintf(res, "%s %s (%s)", aux1, oname, aux2);
    else
      (void) sprintf(res, "%s %s %s", aux1, oname, aux2);
    free(aux1);
    free(oname);
    free(aux2);
  }
  else { /* non infix operation; one argument, at least */
    res = (char*)emalloc(strlen(GetO_name(LookNameE(e)))+2);
    (void) sprintf(res, "%s(", GetO_name(LookNameE(e)));
    n = NumArgE(e);
    for (i=1 ; i<=n ; i++) {
      ae = LookArgE(e,i);
      aux1   = NoOfsortEToS(ae);
      auxres = CopyString(res);
      res    = (char*)erealloc( (void*)ALIGN(res),
			       strlen(auxres)+strlen(aux1)+2);
      (void) sprintf(res, "%s%s,", auxres, aux1);
      free (auxres);
      free (aux1);
    }
    res[strlen(res)-1]=')';  /* kill last comma; close brackets */
  }
  return res;
}

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


/* AllocTreeNode
 * Get memory for a new node of the tree.
 * Return a pointer to the new node.
 */
static TNodePtTyp AllocTreeNode()
{
#ifdef SDEBUG
  new_tnode_count++;
  max_tnode_count = MAX( max_tnode_count,
			new_tnode_count-released_tnode_count );
#endif
  return (TNodePtTyp)NewCellM(sizeof(TNodeTyp));
}

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

/* TreeMakeNode
 * Return a pointer to a node with the adequate values to represent the
 * outermost operation of the expression e.
 */
static TNodePtTyp TreeMakeNode(e)
     ExprTyp    e;
{
  TNodePtTyp  res;

  res       = AllocTreeNode();
  res->desc = LookNameE(e);
  if (res->desc > 0) {  /* it's an operation */
    res->ofsort = OFSORT_NOT_COMPUTED;
    res->possibleopsl = Copy_list(GetO_ofsortopl(LookNameE(e)),
				  (DataListTyp (*)())EchoInt);
  }
  else
    res->possibleopsl = NULL;
  res->args = NULL;
  res->nextfatherarg = NULL;
  return res;
}

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

/* ExprToTree
 * This function is defined below.
 */
static TNodePtTyp ExprToTree();

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

/* TreeMakeArgs
 * Make and put the arguments of the expression e as the arguments
 * of the node node in the tree.
 */
static void TreeMakeArgs( e, node )
     ExprTyp     e;
     TNodePtTyp  node;
{
  TNodePtTyp  aux;
  ExprTyp     iarge;
  int         n,i;

  if (node->desc < 0) /* node is a variable */
    if (LookPVarE(e)!=NULL)
      node->args = ExprToTree(LookPVarE(e));
    else
      node->args = NULL;
  else if (NumArgE(e)==0) /* e is a constant operation */
    node->args = NULL;
  else { /* e is an operation, one argument at least */
    n = NumArgE(e);
    iarge = LookArgE(e,1);
    node->args = aux = TreeMakeNode( iarge );
    TreeMakeArgs( iarge, aux );
    for (i=2 ; i<=n ; i++ ) {
      iarge = LookArgE(e,i);
      aux->nextfatherarg = TreeMakeNode( iarge );
      aux                = aux->nextfatherarg;
      TreeMakeArgs(iarge, aux);
    }
  }
}

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

/* ExprToTree
 * Convert an expression e to a tree that represents it.
 * Return a pointer to the root of the tree.
 */
static TNodePtTyp ExprToTree( e )
     ExprTyp e;
{
  TNodePtTyp res;

  res = TreeMakeNode( e );
  TreeMakeArgs( e, res );
  return res;
}

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

/* KillUpImpOps
 * Kill the operations that are not possible, in each node included
 * in the tree of root node, comparing with the father of the node.
 * narg is the position of node as an argument of its father (node
 * is first, second, third,...  argument of its father node).
 * Returns true, if any operation of the list of possible operations
 * of node was killed; false otherwise.
 */
static boolean KillUpImpOps( node, narg, father )
     TNodePtTyp  node;
     int         narg;
     TNodePtTyp  father;
{
  ListTyp   nodeop, fatherop, arg, aux;
  boolean   killedops, found;
  int       i;

  if (father->desc==GetEqual()) /* its father is a metabool Equal op.*/
    killedops = FALSE;
  else {
    killedops = FALSE;
    nodeop    = node->possibleopsl;
    while (nodeop!=NULL) {
      found    = FALSE;
      fatherop = father->possibleopsl;
      while ((!found) && (fatherop!=NULL)) {
	arg = GetO_argl((DescriptorTyp)LookInfo_list(fatherop));
	for (i=1; i<narg; i++)
	  arg = Next_list(arg);
	if ( GetO_sort((DescriptorTyp)LookInfo_list(nodeop))
	    == (DescriptorTyp)LookInfo_list(arg)
	    )
	  found = TRUE;
	else
	  fatherop = Next_list(fatherop);
      }
      if (found)
	nodeop = Next_list(nodeop);
      else { /* kill operation */
	killedops          = TRUE;
	aux                = Next_list(nodeop);
	node->possibleopsl = DeleteNode_list(nodeop, node->possibleopsl);
	nodeop             = aux;
      }
    }
  }
  return killedops;
}

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

/* KillDownImpOps
 * Kill the operations that are not possible, in each node included
 * in the tree of root node, comparing with the arguments of the node.
 * Return true, if any operation of the list of possible operations
 * of node was killed; false otherwise.
 */
static boolean KillDownImpOps(node)
     TNodePtTyp  node;
{
  TNodePtTyp  arg;
  int         narg, i;
  ListTyp     nodeop, nodeoparg, argop, aux;
  boolean     killedops, found;

  killedops = FALSE;
  for ( arg=node->args, narg=1;
       (arg!=NULL) && (Length_list(node->possibleopsl)>1);
       arg=arg->nextfatherarg, narg++) {
    nodeop = node->possibleopsl;
    while (nodeop!=NULL) {
      nodeoparg = GetO_argl((DescriptorTyp)LookInfo_list(nodeop));
      for (i=1; i<narg; i++)
	nodeoparg = Next_list(nodeoparg);
      if (arg->desc < 0) /* arg is a variable */
	if (GetV_sort(arg->desc)==(DescriptorTyp)LookInfo_list(nodeoparg))
	  found = TRUE;
	else
	  found = FALSE;
      else { /* argument is an operation */
	argop = arg->possibleopsl;
	found = FALSE;
	while ((!found) && (argop!=NULL))
	  if ( GetO_sort((DescriptorTyp)LookInfo_list(argop))
	      ==(DescriptorTyp)LookInfo_list(nodeoparg)
	      )
	    found = TRUE;
	  else
	    argop = Next_list(argop);
      }
      if (found)
	nodeop = Next_list(nodeop);
      else { /* kill operation */
	killedops          = TRUE;
	aux                = Next_list(nodeop);
	node->possibleopsl = DeleteNode_list(nodeop, node->possibleopsl);
	nodeop             = aux;
      }
    }
  }
  return killedops;
}

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

/* KillImpossibleOps
 * This function is declared below
 */
static void KillImpossibleOps ();

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

/* NKillImpossibleOps
 * Kill the operations that are not possible, in each node included
 * in the tree of root node.
 * narg is the position of node as an argument of its father (node
 * is first, second, third,...  argument of its father node).
 * If father==NULL, it means that node is an absolute root node (assumes
 * it has no father).
 * Returns true, if any operation of the list of possible operations
 * of node was killed; false otherwise.
 */
static boolean NKillImpossibleOps( node, narg, father )
     TNodePtTyp  node;
     int         narg;
     TNodePtTyp  father;
{
  boolean    killedops, argchanges;
  TNodePtTyp arg;
  int        i;

  if (node->desc < 0) { /* node is a variable */
    killedops = FALSE;
    if (node->args!=NULL)
      KillImpossibleOps(node->args);
  }
  else if (Length_list(node->possibleopsl)==1) { /* only one possible oper. */
    killedops = FALSE;
    for (arg=node->args, i=1; arg!=NULL; arg=arg->nextfatherarg, i++)
      (void) NKillImpossibleOps(arg, i, node);
  }
  else { /* more than one possible operation */
    if (father==NULL) /* it's the initial node */
      killedops = FALSE;
    else
      killedops = KillUpImpOps(node, narg, father);
    do {
      killedops  = KillDownImpOps(node) || killedops;
      argchanges = FALSE;
      for ( arg=node->args, i=1; arg!=NULL; arg=arg->nextfatherarg, i++ )
	argchanges = NKillImpossibleOps(arg, i, node) || argchanges;
    }
    while (argchanges);
  }
  return killedops;
}

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

/* KillImpossibleOps
 * Kill the operations that are not possible, in each node included
 * in the tree of root node, comparing with the father and the
 * arguments of the node.
 * It assumes that node is the absolute root of a tree, so it doesn't
 * compares node with its father (it assumes node has no father).
 */
static void KillImpossibleOps( node )
     TNodePtTyp node;
{
  (void)NKillImpossibleOps(node,0,(TNodePtTyp)NULL); /* it's the root node */
}

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

/* ComputeOfsorts
 * Calculates the ofsort for each node included in the tree
 * whose root is node.
 * Returns true, if any operation of the list of possible operations
 * of node was killed; false otherwise.
 */
static boolean ComputeOfsorts( node )
     TNodePtTyp  node;
{
  TNodePtTyp  arg;
  boolean     killedops, argchanges;
  ListTyp     nodeop, aux;
  int         sortcount, i;

  if (node->desc < 0) /* node is a variable */
    killedops = FALSE;
  else if (node->ofsort!=OFSORT_NOT_COMPUTED) { /* ofsort already computed */
    killedops = FALSE;
    for ( arg=node->args; arg!=NULL; arg=arg->nextfatherarg )
      (void)ComputeOfsorts(arg);
  }
  else if (node->desc==GetEqual()) {
    node->ofsort = OFSORT_FALSE;
    killedops    = FALSE;
    for ( arg=node->args; arg!=NULL; arg=arg->nextfatherarg )
      (void) ComputeOfsorts (arg);
  }
  else /* ofsort not computed */
    if (Length_list(node->possibleopsl)==1) { /* only one possible oper. */
      node ->ofsort = OFSORT_FALSE;
      killedops     = FALSE;
      for (arg=node->args; arg!=NULL; arg=arg->nextfatherarg)
	(void) ComputeOfsorts(arg);
    }
    else { /* more than one possible operation */
      for ( nodeop=node->possibleopsl, sortcount=0;
	   (nodeop!=NULL) && (sortcount<2);
	   nodeop = Next_list(nodeop))
	if ( GetO_sort((DescriptorTyp)LookInfo_list(nodeop))
	    == GetO_sort(node->desc)
	    )
	  sortcount++;
      if ( sortcount<2 ){ /* only one possible op. has the res. sort of node */
	killedops    = TRUE;
	node->ofsort = OFSORT_TRUE;
	nodeop       = node->possibleopsl;
	while (nodeop!=NULL)
	  if ( GetO_sort((DescriptorTyp)LookInfo_list(nodeop))
	      != GetO_sort(node->desc)
	      ) {
	    aux                = Next_list(nodeop);
	    node->possibleopsl = DeleteNode_list(nodeop, node->possibleopsl);
	    nodeop             = aux;
	  }
	  else
	    nodeop=Next_list(nodeop);
	for (arg=node->args, i=1; arg!=NULL; arg=arg->nextfatherarg, i++)
	  (void) NKillImpossibleOps (arg, i, node);
	for (arg=node->args; arg!=NULL; arg=arg->nextfatherarg)
	  (void) ComputeOfsorts (arg);
      }
      else { /* ofsort can't be computed now */
	killedops  = FALSE;
	argchanges = FALSE;
	for ( arg=node->args;
	     (arg!=NULL) && (!argchanges); arg=arg->nextfatherarg)
	  if (argchanges=ComputeOfsorts(arg)) {
	    KillImpossibleOps (node);
	    (void) ComputeOfsorts (node);
	  }
      }
    }
  return killedops;
}

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

/* TreeToString
 * This function is defined below.
 */
static char * TreeToString();

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

/* VarToStrT
 * Convert a variable node of the tree, node, to a string.
 * If the variable is parameterized, it returns a string with
 * the name of the variable and its parameterized value.
 */
static char* VarToStrT( node )
     TNodePtTyp node;
{
  char *res, *auxres, *aux;

  res = NULL;
  if ((print_parameterized!=PRINT_ONLY_PARAM) ||
      (node->args==NULL)){
    res = (char*)emalloc(strlen(GetV_name(node->desc))+15);
    (void) sprintf(res, "%s_%d", GetV_name(node->desc), -node->desc);
  }
  if ( node->args!=NULL && (print_parameterized == PRINT_PARAM ||
			    print_parameterized == PRINT_ONLY_PARAM) ) {
    aux    = TreeToString (node->args);
    if ( res!=NULL ){
      auxres = CopyString(res);
      res    = (char*)erealloc( (void*)ALIGN(res),
			       strlen(auxres)+strlen(aux)+5);
      (void) sprintf(res, "%s(*%s*)", auxres, aux);
      free (auxres);
    }
    else {
      res    = (char*)emalloc(strlen(aux)+1);
      (void) sprintf( res, "%s", aux );
    }
    free(aux);
  }
  return res;
}

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

/* ConstToStrT
 * Converts a constant operation node of the tree, node, to
 * a string, with "ofsort" if necessary.
 * If the name of the constant is name_number type, and
 * there is a variable, with name name in number position
 * in the table of variables, it returns the name of the constant
 * with "ofsort".
 */
static char* ConstToStrT( node )
     TNodePtTyp node;
{
  char *res, *nameC;
  int  numC;

  numC = 0;
  if ((node->ofsort==OFSORT_TRUE) ||
      (((nameC=Split(GetO_name(node->desc), &numC))!=NULL) &&
       (numC>0) &&
       (numC<=LastTableV()) && (strcmp(nameC, GetV_name(-numC))==0))) {
    res = (char*)emalloc( strlen(GetO_name(node->desc))
			 +strlen(GetS_name(GetO_sort(node->desc)))+5);
    (void) sprintf (res, "%s of %s",
		    GetO_name(node->desc), GetS_name(GetO_sort(node->desc)));
  }
  else
    res = CopyString(GetO_name(node->desc));
  return res;
}

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

/* TreeToString
 * Convert the tree whose root is node to a string.
 */
static char* TreeToString( node )
     TNodePtTyp node;
{
  TNodePtTyp arg, arg2;
  char       *res, *aux1, *aux2, *auxres, *oname;

  if (node->desc < 0) /* node is a variable */
    res = VarToStrT (node);
  else if (node->args==NULL) /* node is a constant */
    res = ConstToStrT (node);
  else if (GetO_infix (node->desc)) { /* node is an infix operation */
    oname = CopyString(GetO_name(node->desc));
    aux1 = TreeToString(node->args);
    aux2 = TreeToString(node->args->nextfatherarg);
    res  = (char*)emalloc(strlen(aux1)+strlen(aux2)+strlen(oname)+5);
    arg2 = node->args->nextfatherarg;
    if ( (arg2->desc > 0) && GetO_infix(arg2->desc)
	&&(arg2->ofsort!=OFSORT_TRUE))
      (void) sprintf(res, "%s %s (%s)", aux1, oname, aux2);
    else
      (void) sprintf(res, "%s %s %s", aux1, oname, aux2);
    free(aux1);
    free(oname);
    free(aux2);
    if (node->ofsort==OFSORT_TRUE) {
      auxres = CopyString(res);
      res    = (char*)erealloc( (void*)ALIGN(res),
			       strlen(auxres)
			       +strlen(GetS_name(GetO_sort(node->desc)))+7);
      (void) sprintf(res, "(%s) of %s",
		     auxres, GetS_name(GetO_sort(node->desc)));
      free (auxres);
    }
  }
  else { /* non infix, one argument at least */
    res = (char*)emalloc(strlen(GetO_name(node->desc))+2);
    (void) sprintf(res, "%s(", GetO_name(node->desc));
    for (arg=node->args; arg!=NULL; arg=arg->nextfatherarg) {
      aux1   = TreeToString(arg);
      auxres = CopyString(res);
      res    = (char*)erealloc( (void*)ALIGN(res),
			       strlen(auxres)+strlen(aux1)+2);
      (void) sprintf(res, "%s%s,", auxres, aux1);
      free (auxres);
      free(aux1);
    }
    res[strlen(res)-1]=')'; /* kill last comma; close brackets */
    if (node->ofsort==OFSORT_TRUE) {
      auxres = CopyString(res);
      res    = (char*)erealloc( (void*)ALIGN(res),
			       strlen(auxres)
			       +strlen(GetS_name(GetO_sort(node->desc)))+5
			       );
      (void) sprintf( res, "%s of %s", auxres,
		     GetS_name(GetO_sort(node->desc)));
      free (auxres);
    }
  }
  return res;
}

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

/* DispTree
 * Free the memory used by the nodes of the tree whose root is node
 */
static void DispTree ( node )
     TNodePtTyp  node;
{
  TNodePtTyp arg, nextarg;

  arg = node->args;
  while (arg!=NULL) {
    nextarg = arg->nextfatherarg;
    DispTree (arg);
    arg = nextarg;
  }
  Disp_list( node->possibleopsl );
  FreeCellM( (void*)node, sizeof(TNodeTyp) );
#ifdef SDEBUG
  released_tnode_count++;
#endif
}

/******************************************************************
 *                                                                *
 *                    Expression to String                        *
 *                                                                *
 ******************************************************************/

/* ExprToStringE
 * Return a string that represents the expression e.
 */
char * ExprToStringE( e )
     ExprTyp e;
{
  TNodePtTyp root;
  char       *res;

  LASSERT(e != NULL);
  if ((!GetO_tableOfsort()) || (!IsOfsortExpr(e)))
    res = NoOfsortEToS(e);
  else {
    root = ExprToTree(e);
    KillImpossibleOps(root);
    (void) ComputeOfsorts(root);
    res = TreeToString(root);
    DispTree(root);
  }
  return res;
}


/******************************************************************
 *                                                                *
 *                    End of ExprToStringE                         *
 *                                                                *
 ******************************************************************/


static void DrawExprPrintList( list, pstr )
     ListTyp   list;
     void      (*pstr)();
{
  for ( ; list!=NULL ; list=Next_list(list))
    if (LookInfo_list(list)==0)
      pstr("   ");
    else
      pstr(" | ");
}

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

static void DrawExprAux( e, plist, lastarg, pstr )
     ExprTyp   e;
     ListTyp  *plist;
     boolean   lastarg;
     void      (*pstr)();
{
  int n,i;

  DrawExprPrintList( *plist, pstr );
  pstr(" |> ");
  if (lastarg) {
    *plist = Add_list((DataListTyp)0,*plist);
  }
  else {
    *plist = Add_list((DataListTyp)1,*plist);
  }
  PrintInt( pstr, LookNameE(e) );
  pstr(" ");
  if (LookNameE(e)>0)
    PrintO(LookNameE(e),pstr);
  else
    PrintV(LookNameE(e),FALSE,pstr);
  pstr(" (copy=");
  PrintInt(pstr,OwnersE(e));
  pstr(")");
  pstr(" (address=");
  PrintInt(pstr,(int)e);
  pstr(")\n");
  if ( LookNameE(e)>0 ) {
    n = NumArgE(e);
    for ( i=1; i<=n; i++ )
      DrawExprAux( LookArgE(e,i), plist, i==n, pstr );
  }
  else {
    if ( LookPVarE(e)!=NULL )
      DrawExprAux( LookPVarE(e), plist, TRUE, pstr );
  }
  *plist = DeleteNode_list(Last_list(*plist),*plist);
}

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

/* DrawE
 * Draw an expression e.
 * pstr is the function used to print strings.
 */
void DrawE( e, pstr )
     ExprTyp    e;
     void     (*pstr)();
{
  ListTyp list;

  list = Create_list();
  DrawExprAux( e, &list, TRUE, pstr );
  LASSERT(list == NULL);
}

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

/* PE
 * Prints an expression in stdout
 */
void PE(e)
     ExprTyp e;
{
  PrintE(e,PrintString);
}

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

/* DE
 * Draw an expression in stdout
 */
void DE(e)
     ExprTyp e;
{
  DrawE(e,PrintString);
}

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

/* EqualE
 * Return TRUE if e1 and e2 are equal, FALSE otherwise.
 */
boolean EqualE( e1, e2 )
     ExprTyp e1,e2;
{
  int      n1,i;
  ExprTyp a1,a2;

  if (e1==e2)
    return TRUE;
  if ( LookNameE(e1) != LookNameE(e2) )
    return FALSE;
  else {
    n1 = NumArgE(e1);
    LASSERT(n1 == NumArgE(e2));
    for ( i=1; i<=n1; i++ ) {
      a1 = LookArgE(e1,i);
      a2 = LookArgE(e2,i);
      if ( !EqualE(a1,a2) )
	return FALSE;
    }
    return TRUE;
  }
}

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

/* LookSortE
 * Return the sort of the expression ve.
 */
int LookSortE( ve )
     ExprTyp  ve;
{
  LASSERT(ve!=NULL);
  if (IsVariableE(ve))
    return GetV_sort(LookNameE(ve));
  else
    return GetO_sort(LookNameE(ve));
}

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

/* IsConstE
 *  Returns true if there is no variables in the expression ve.
 */
boolean IsConstE( ve )
     ExprTyp  ve;
{
  int n,i;
  ExprTyp  a;

  if (ve==NULL)
    return TRUE;
  else
    if (IsVariableE(ve))
      return FALSE;
    else {
      n = NumArgE(ve);
      for (i=1 ; i<=n ; i++) {
	a = LookArgE(ve,i);
	if (! IsConstE(a) )
	  return FALSE;
      }
      return TRUE;
    }
}

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

/* NumArgE
 *  Returns the number of arguments of the expression e.
 */
int NumArgE( e )
     ExprTyp  e;
{
  LASSERT(e!=NULL);
  if (IsVariableE(e))
    return 0;
  return Length_list(e->sons);
}

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

/* LookNameE
 *  Returns the name of the expression e.
 *  These name is the descriptor for the table of operation or variables.
 *  For variables is a negative value.
 */
int LookNameE( e )
     ExprTyp  e;
{
  return e->name;
}

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

/* LookTypeE
 *  Returns the type of the expression e: VariableC or OperationC
 */
int LookTypeE( e )
     ExprTyp  e;
{
  return e->name < 0 ? VariableC : OperationC ;
}

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

/* ChangeNameE
 * Change the name of an expression e
 */
void ChangeNameE( e, new_name )
     ExprTyp  e;
     int      new_name;
{
  e->name = new_name;
}

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

/* LookArgE
 * Look at the n-th argument of the operation e.
 */
ExprTyp LookArgE( e , n )
     ExprTyp  e;
     int      n;
{
  register ListTyp l;

  LASSERT(e!=NULL);
  LASSERT( (NumArgE(e)>=n) || (NumArgE(e)==0) );
  l = e->sons;
  if (l == NULL) return NULL;
  while ( n-- > 1 )
    l = Next_list(l);
  LASSERT(OwnersE((ExprTyp)LookInfo_list(l))!=0);
  return (ExprTyp)LookInfo_list(l);
}

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

/* GetArgE
 * Get the n-th argument of the operation e.
 */
ExprTyp GetArgE( e , n )
     ExprTyp  e;
     int      n;
{
  ListTyp l;

  LASSERT(e!=NULL);
  LASSERT( (NumArgE(e)>=n) || (NumArgE(e)==0) );
  l = e->sons;
  if (l == NULL) return NULL;
  while (n-->1)
    l = Next_list(l);
  LASSERT( LookInfo_list(l) != NULL );
  LASSERT(OwnersE((ExprTyp)LookInfo_list(l))!=0);
  e = (ExprTyp)GetInfo_list(l);
  DecCopyE(e);
  return e;
}

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

/* PutArgE
 * Put a as the n-th argument of the operation e.
 */
void PutArgE( e , a , n )
     ExprTyp  e, a;
     int      n;
{
  ListTyp l;

  LASSERT(e!=NULL);
  LASSERT( (NumArgE(e)>=n) || (NumArgE(e)==0) );
  l = e->sons;
  while (n-->1)
    l = Next_list(l);
  LASSERT( LookInfo_list(l) == NULL );
  PutInfo_list(l,(DataListTyp)a);
  IncCopyE(a);
}

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

/* MakeE
 * Make an expression. If the expression is an operation then
 * the arguments can be added with AddArgE later.
 *  k indicates the expression type.
 *  d is the descriptor index in the table of operation or variables.
 */
ExprTyp MakeE( d, k )
     int  d;
     int  k;
{
  ExprTyp  c;

  LASSERT( ((k==VariableC)&&(d<0)) || ((k==OperationC)&&(d>0)) );
  c       = NewExprCell();
  c->name = d;
  c->sons = NULL;
  c->copy = 0;
  return (ExprTyp)c;
}

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

/* AddArgE
 * Add the argument a to the operation e.
 */
void AddArgE( e, a )
     ExprTyp  e, a;
{
  ListTyp  l,la;

  LASSERT(e!=NULL);
  LASSERT(a!=NULL);
  la = CreateNode_list();
  PutInfo_list(la,(DataListTyp)a);
  IncCopyE(a);
  if ( e->sons == NULL ) {
    e->sons = la;
  }
  else {
    l = e->sons;
    while (Next_list(l) != NULL)
      l = Next_list(l);
    l->next  = la;
  }
}

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

/* Apply_Proc_ArgsE
 * Apply procedure p to all the arguments of the operation e.
 */
void Apply_Proc_ArgsE( e, p )
     ExprTyp   e;
     void    (*p)();
{
  ListTyp l;

  LASSERT(p!=NULL);
  l = e->sons;
  while (l != NULL) {
    (*p)(l->info);
    l = Next_list(l);
  }
}

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

/* Apply_Func_ArgsE
 * Replace each argument a of e by f(a).
 */
void Apply_Func_ArgsE( e, f )
     ExprTyp   e;
     ExprTyp (*f)();
{
  ListTyp l;

  LASSERT(f!=NULL);
  l = e->sons;
  while (l != NULL) {
    l->info = (DataListTyp)(*f)(l->info);
    l       = Next_list(l);
  }
}

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

/* IsVoidE
 * Return TRUE if the expression is NULL.
 */
boolean IsVoidE( e )
     ExprTyp  e;
{
  return e==NULL;
}

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

/* OwnersE
 * Number of entities sharing the expression e.
 */
int OwnersE( e )
     ExprTyp  e;
{
  return e->copy;
}

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

/* ShareE
 * Increment the sharing counter of the expression e in one unit.
 */
ExprTyp ShareE( e )
     ExprTyp e;
{
  LASSERT(e!=NULL);
  IncCopyE(e);
  return e;
}

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

/* UnshareE
 * Decrement the sharing counter of the expression e in one unit.
 */
ExprTyp UnshareE( e )
     ExprTyp e;
{
  LASSERT(e!=NULL);
  LASSERT(OwnersE(e)!=0);
  DecCopyE(e);
  return e;
}

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

/* CopyE2
 * Copy an expression.
 */
static ExprTyp CopyE2( e )
     ExprTyp  e;
{
  ExprTyp  ne;

  ne       = CopyECell(e);
  ne->copy = 1;
  if (e->sons != NULL)
    if (e->name > 0) /* operation */
      ne->sons = Copy_list(e->sons,(DataListTyp(*)())CopyE2);
    else
      PutPVarE(ne,LookPVarE(e));
  return ne;
}

/* CopyE
 * Copy an expression.
 */
ExprTyp CopyE( e )
     ExprTyp  e;
{
  ExprTyp  ne;

  ne = CopyE2(e);
  ne->copy = 0;
  return ne;
}

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

/* GetExpr2
 * Get an expression
 */
static ExprTyp GetExpr2( e )
     ExprTyp  e;
{
  if ( (e->copy==1) || (e->copy==-1) ) {
    if (e->name > 0) /* operation */
      Apply_Func_list(e->sons,(DataListTyp(*)())GetExpr2);
    return e;
  }
  else {
    DecCopyE(e);
    return ShareE(CopyE(e));
  }
}


/* GetE
 * Subtract a copy of the expression e ( copy e and free e ).
 */
ExprTyp GetE( e )
     ExprTyp  e;
{
  if (e->copy == 0) {
    if (e->name > 0) /* operation */
      Apply_Func_list(e->sons,(DataListTyp(*)())GetExpr2);
    return e;
  }
  else
    return CopyE(e);
}

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

/* GlueE
 * The expression e2 is placed in the memory used by e1.
 * The old e1 disappears.
 *  NOTE: e1 can be the argument of other expression but e2 not.
 */
void GlueE( e1, e2 )
     ExprTyp e1,e2;
{
  ListTyp  l,aux;
  ExprTyp e;

  LASSERT(e1 != e2);
  LASSERT(e1 != NULL);
  LASSERT(e2 != NULL);
  e1->name = e2->name;
  l        = e1->sons;
  while (l != NULL) {
    e = (ExprTyp)LookInfo_list(l);
    LASSERT(OwnersE(e)!=0);
    DecCopyE(e);
    FreeE(e);
    aux = l;
    l   = Next_list(l);
    DispNode_list(aux);
  }
  if ( e2->copy == 0 ) {
    e1->sons = e2->sons;
    FreeExprCell(e2);
  }
  else {
    l = e2->sons;
    if ( l!=NULL ) {
      e1->sons = CreateNode_list();
      PutInfo_list(e1->sons,(DataListTyp)ShareE((ExprTyp)l->info));
      for ( aux=e1->sons, l=Next_list(l);
	   l!=NULL;
	   aux=aux->next, l=Next_list(l) ) {
	aux->next = CreateNode_list();
	PutInfo_list(aux->next,(DataListTyp)ShareE((ExprTyp)l->info));
      }
    }
    else
      e1->sons = Create_list();
  }
}

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

/* FreeE
 * Free the expression e.
 */
void FreeE( e )
     ExprTyp  e;
{
  ListTyp aux,l,n;

  while (e->copy==0) {
    n = e->sons;
    FreeExprCell(e);
    if (n == NULL)
      return;
    for (l=Next_list(n) ; l!=NULL ; ) {
      e = (ExprTyp)l->info;
      LASSERT(e->copy!=0);
      aux = l;
      l   = Next_list(l);
      DispNode_list(aux);
      DecCopyE(e);
      FreeE(e);
    }
    e = (ExprTyp)n->info;
    LASSERT(e->copy!=0);
    DecCopyE(e);
    DispNode_list(n);
  }
}

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

/* LookPVarE
 * Return the parameterized value of the variable v.
 */
ExprTyp LookPVarE( v )
     ExprTyp v;
{
  LASSERT(v!=NULL);
  LASSERT(LookTypeE(v)==VariableC);
  if (v->sons != NULL)
    return LookArgE(v,1);
  else
    return NULL;
}

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

/* GetPVarE
 * Get the parameterized value of the variable v.
 * This value will be null after this function.
 */
ExprTyp GetPVarE( v )
     ExprTyp  v;
{
  ExprTyp res;

  LASSERT(v!=NULL);
  LASSERT(LookTypeE(v)==VariableC);
  if (v->sons != NULL) {
    res = GetArgE(v,1);
    Disp_list(v->sons);
    v->sons = NULL;
    return res;
  }
  else
    return NULL;
}

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

/* PutPVarE
 * Put the parameterized value p to the variable v.
 * The variable v can not already have a parameterized value.
 */
void PutPVarE( v, p )
     ExprTyp v, p;
{
  LASSERT(v!=NULL);
  LASSERT(LookArgE(v,1)==NULL);
  LASSERT(LookTypeE(v)==VariableC);
  AddArgE(v,p);
}

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

static ExprListTyp le;

static void VarInExprAux( e )
     ExprTyp e;
{
  int n,i;

  if ( IsVariableE(e) ) {
    if ( !In_list((DataListTyp)e,le,EqualE) )
      le = InsertEL(MakeE(LookNameE(e),VariableC),le);
  }
  else /* operation */ {
    n = NumArgE(e);
    for ( i=1 ; i<=n ; i++ )
      VarInExprAux( LookArgE(e,i) );
  }
}

/* VarsInE
 * Return a list with the variables used in the expression e.
 */
ListTyp VarsInE( e )
     ExprTyp e;
{
  le = CreateEL();
  VarInExprAux( e );
  return le;
}

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

/* UnParVarE
 * Unparameterize a variable. Example : UnParVarE(x(*succ(0)*)) => succ(0)
 * The parameterized value is glued onto the variable and the remainder
 * expression cell is disposed.
 */
void UnParVarE( v )
     ExprTyp v;
{
  ListTyp l;
  ExprTyp e;

  LASSERT(LookArgE(v,1)!=NULL);
  l = v->sons;
  LASSERT(Next_list(l)==NULL);
  e = (ExprTyp)LookInfo_list(l);
  DispNode_list(l);
  v->name = e->name;
  v->sons = e->sons;
  DecCopyE(e);
  if (e->copy==0)
    FreeExprCell(e);
}

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

/* CopyUntilVarE2
 *
 */
static ExprTyp CopyUntilVarE2( e )
     ExprTyp  e;
{
  ExprTyp  ne;

  ne       = CopyECell(e);
  ne->copy = 1;
  if ( e->name > 0 )  /* operation */
    ne->sons = Copy_list(e->sons,(DataListTyp(*)())CopyUntilVarE2);
  return ne;
}

/* CopyUntilVarE
 * Copy an expression until variables
 * (without copying the parameterized values).
 */
ExprTyp CopyUntilVarE( e )
     ExprTyp  e;
{
  ExprTyp  ne;

  ne       = CopyUntilVarE2(e);
  ne->copy = 0;
  return ne;
}

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

/* FreeUntilVarE2
 * Free an expression until variables.
 */
static void FreeUntilVarE2( e )
     ExprTyp  e;
{
  LASSERT(e->copy!=0);
  DecCopyE(e);
  FreeUntilVarE((ExprTyp)e);
}

/* FreeUntilVarE
 * Free the expression e until variables.
 * The parameterized value is simply ignored.
 */
void FreeUntilVarE( e )
     ExprTyp  e;
{
  if ( e->copy==0 ) {
    if ( e->name > 0 ) /* operation */
      Free_list(e->sons,FreeUntilVarE2);
    else
      Free_list(e->sons,(void(*)())UnshareE);
    FreeExprCell(e);
  }
}


/******************************************************************
 *                                                                *
 *                   Visits to expressions                        *
 *            Running expressions avoiding revisiting             *
 *                                                                *
 *    NOTE : side effect : the copy counters will be changed      *
 *           temorarily during a visit.                           *
 *                                                                *
 ******************************************************************/


/*
 *  list to mark expressions cells with copy greater than one.
 */
static ListTyp visitedExprNodes;

static void ChangeCopySignE( e )
     ExprTyp e;
{
  LASSERT(e!=NULL);
  e->copy = -e->copy;
}

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

/* Begin_VisitE
 * Start a visit to expressions.
 * This function must be invoked before exploring the expressions.
 */
void Begin_VisitE()
{
  visitedExprNodes  = Create_list();
}

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

/* VisitedE
 * Declare a expression cell as "visited".
 * If it had already been visited return TRUE else FALSE.
 * Those cells with (|copy|>1) are stored and their copy fields get
 * changed of signus.
 * After visiting all the expressions, End_VisitE should be called to
 * undo the changes on the expressions.
 */
boolean VisitedE( e )
     ExprTyp e;
{
  if ( OwnersE(e)<0 ) {
    LASSERT(In_list((DataListTyp)e,visitedExprNodes,EqInt));
    return TRUE;
  }
  if ( OwnersE(e)>1 ) {
    LASSERT(!In_list((DataListTyp)e,visitedExprNodes,EqInt));
    ChangeCopySignE( e );
    visitedExprNodes = Insert_list((DataListTyp)e,visitedExprNodes);
  }
  return FALSE;
}

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

/* UnVisitE
 * Declare a expression cell as "not visited".
 * Set its copy signus to positive.
 */
void UnVisitE( e )
     ExprTyp e;
{
  ListTyp n;

  LASSERT(OwnersE(e)<0);
  ChangeCopySignE( e );
  n = LookFor_list( (DataListTyp)e, visitedExprNodes, EqInt );
  LASSERT( n!=NULL );
  visitedExprNodes = DeleteNode_list(n,visitedExprNodes);
}

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

/* End_VisitE
 * End the visit to expressions.
 * Release track of visited cells and restore altered copy fields.
 */
void End_VisitE()
{
  Free_list( visitedExprNodes, ChangeCopySignE );
  visitedExprNodes = Create_list();
}

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

















