/*
* expr.c - Support routines for handling expressions
*
* Copyright (C) 1997-2003 Gero Kuhlmann <gero@gkminix.han.de>
*
* This program 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
* any later version.
*
* This program 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 program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*
* $Id: expr.c,v 1.4 2003/01/25 23:29:44 gkminix Exp $
*/
#include "mknbi.h"
#include "mgl.h"
/*
*****************************************************************************
*
* Delete whole expression tree
*/
void delexpr(ep)
struct expr *ep;
{
struct varinfo *vp1, *vp2;
int i;
if (ep != NULL) {
/* Delete any possible string constant */
if (isconst(ep) && exprtype(ep) == EXPR_STRING &&
ep->spec.cval.val.s != NULL)
free(ep->spec.cval.val.s);
/* Delete all variable info records */
vp1 = ep->spec.var.next;
while (vp1 != NULL) {
delexpr(vp1->index);
vp2 = vp1->next;
free(vp1);
vp1 = vp2;
}
delexpr(ep->spec.var.index);
/* Delete all subexpressions */
for (i = 0; i < ep->exprnum; i++)
delexpr(ep->exprlist[i]);
free(ep);
}
}
/*
*****************************************************************************
*
* Return the ordinal number of a scalar expression
*/
int getord(ep)
struct expr *ep;
{
int ret = 0;
#ifdef PARANOID
if (!isconst(ep))
interror(20, "cannot determine ordinal value from non-constant");
#endif
switch (exprtype(ep)) {
case EXPR_NUM:
ret = ep->spec.cval.val.i;
break;
case EXPR_BOOL:
ret = (ep->spec.cval.val.b ? 1 : 0);
break;
case EXPR_CHAR:
ret = ep->spec.cval.val.c & 0xff;
break;
case EXPR_ENUM:
ret = ep->spec.cval.val.e;
break;
#ifdef PARANOID
default:
interror(38, "cannot determine ordinal value from non-scalar");
break;
#endif
}
return(ret);
}
/*
*****************************************************************************
*
* Compare two strings
*/
static int str_compare(op, leftstr, rightstr)
int op;
char *leftstr;
char *rightstr;
{
int i, res;
#ifdef PARANOID
if (leftstr == NULL || rightstr == NULL)
interror(2, "NULL strings in expression");
#endif
i = strcmp(leftstr, rightstr);
res = FALSE;
switch(op) {
case CMD_EQ: res = (i == 0 ? TRUE : FALSE); break;
case CMD_GT: res = (i > 0 ? TRUE : FALSE); break;
case CMD_GE: res = (i >= 0 ? TRUE : FALSE); break;
case CMD_LT: res = (i < 0 ? TRUE : FALSE); break;
case CMD_LE: res = (i <= 0 ? TRUE : FALSE); break;
case CMD_NE: res = (i != 0 ? TRUE : FALSE); break;
}
return(res);
}
/*
*****************************************************************************
*
* Compare two integers
*/
static int int_compare(op, leftint, rightint)
int op;
int leftint;
int rightint;
{
int res;
res = FALSE;
switch(op) {
/* Are there any compilers which do not use 1 as a true value? Just
* to make sure we hardcode it here.
*/
case CMD_EQ: res = (leftint == rightint ? TRUE : FALSE); break;
case CMD_GT: res = (leftint > rightint ? TRUE : FALSE); break;
case CMD_GE: res = (leftint >= rightint ? TRUE : FALSE); break;
case CMD_LT: res = (leftint < rightint ? TRUE : FALSE); break;
case CMD_LE: res = (leftint <= rightint ? TRUE : FALSE); break;
case CMD_NE: res = (leftint != rightint ? TRUE : FALSE); break;
}
return(res);
}
/*
*****************************************************************************
*
* Collapse a string expression. This handles only one node!
*/
static void str_collapse(ep)
struct expr *ep;
{
char *cp;
size_t destsize, i;
size_t leftlen, rightlen;
char leftbuf[2], rightbuf[2];
char *leftstr, *rightstr;
/* Multiplication of a character with a number is special */
if (exprtype(ep->left) == EXPR_CHAR &&
exprtype(ep->right) == EXPR_NUM &&
ep->opcode == '*') {
#ifdef PARANOID
if (exprtype(ep) != EXPR_STRING)
interror(1, "invalid result type for string expression");
#endif
destsize = ep->type->size - 1;
i = getord(ep->right);
if (i > destsize) {
warning("string too long for concatenation, truncating");
i = destsize;
}
cp = (char *)nbmalloc(i + 1);
memset(cp, ep->left->spec.cval.val.c, i);
cp[i] = '\0';
ep->spec.cval.val.s = cp;
ep->spec.cval.t = &string_type;
return;
}
/* Make a string out of a character constant on the left side */
leftstr = NULL;
if (exprtype(ep->left) == EXPR_CHAR) {
leftbuf[0] = ep->left->spec.cval.val.c;
leftbuf[1] = '\0';
leftstr = leftbuf;
} else if (exprtype(ep->left) == EXPR_STRING)
leftstr = ep->left->spec.cval.val.s;
/* Make a string out of a character constant on the right side */
rightstr = NULL;
if (exprtype(ep->right) == EXPR_CHAR) {
rightbuf[0] = ep->right->spec.cval.val.c;
rightbuf[1] = '\0';
rightstr = rightbuf;
} else if (exprtype(ep->right) == EXPR_STRING)
rightstr = ep->right->spec.cval.val.s;
#ifdef PARANOID
/* Check if op is valid and strings are defined at all */
if (ep->opcode != '+' && !iscmdcond(ep))
interror(4, "invalid operation for strings");
if (leftstr == NULL || rightstr == NULL)
interror(5, "invalid types in string expression");
#endif
/* Handle string comparison */
if (iscmdcond(ep)) {
#ifdef PARANOID
if (ep->type != &bool_type)
interror(8, "invalid expression type for comparison");
#endif
ep->spec.cval.val.b = str_compare(ep->opcode, leftstr, rightstr);
return;
}
/* Check that result type is correct */
#ifdef PARANOID
if (exprtype(ep) != EXPR_STRING)
interror(24, "invalid result type for string expression");
#endif
/* Adjust string length */
leftlen = strlen(leftstr);
rightlen = strlen(rightstr);
destsize = ep->type->size - 1;
if (leftlen + rightlen > destsize) {
warning("string too long for concatenation, truncating");
if (leftlen > destsize)
leftlen = destsize;
rightlen = destsize - leftlen;
}
/* Concatenate both strings */
cp = (char *)nbmalloc(leftlen + rightlen + 1);
strncpy(cp, leftstr, leftlen);
strncpy(&cp[leftlen], rightstr, rightlen);
cp[leftlen+rightlen] = '\0';
ep->spec.cval.val.s = cp;
ep->spec.cval.t = &string_type;
}
/*
*****************************************************************************
*
* Collapse a binary numerical expression. This handles only one node!
*/
static void num_collapse(ep)
struct expr *ep;
{
int leftval, rightval;
int retval = 0;
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_NUM || exprtype(ep->right) != EXPR_NUM)
interror(21, "invalid types in numerical operation");
#endif
leftval = ep->left->spec.cval.val.i;
rightval = ep->right->spec.cval.val.i;
if (iscmdcond(ep)) {
#ifdef PARANOID
if (ep->type != &bool_type)
interror(6, "invalid expression type for comparison");
#endif
ep->spec.cval.val.b = int_compare(ep->opcode, leftval, rightval);
ep->spec.cval.t = &bool_type;
return;
}
#ifdef PARANOID
if (ep->type != &int_type)
interror(25, "invalid result type for numerical expression");
#endif
switch (ep->opcode) {
case '+':
retval = leftval + rightval;
break;
case '-':
retval = leftval - rightval;
break;
case '*':
retval = leftval * rightval;
break;
case '/':
retval = 0;
if (rightval == 0)
error("division by zero");
else
retval = leftval / rightval;
break;
case '%':
retval = 0;
if (rightval == 0)
error("division by zero");
else
retval = leftval % rightval;
break;
case CMD_AND:
retval = leftval & rightval;
break;
case CMD_OR:
retval = leftval | rightval;
break;
case CMD_XOR:
retval = leftval ^ rightval;
break;
#ifdef PARANOID
default:
interror(10, "invalid numerical operation");
#endif
}
ep->spec.cval.val.i = retval;
ep->spec.cval.t = &int_type;
}
/*
*****************************************************************************
*
* Collapse a binary boolean expression. This handles only one node!
*/
static void bool_collapse(ep)
struct expr *ep;
{
int leftval, rightval;
int retval = 0;
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_BOOL || exprtype(ep->right) != EXPR_BOOL)
interror(22, "invalid types in boolean operation");
if (ep->type != &bool_type)
interror(26, "invalid result type for boolean expression");
#endif
leftval = ep->left->spec.cval.val.b;
rightval = ep->right->spec.cval.val.b;
if (iscmdcond(ep))
retval = int_compare(ep->opcode, (leftval ? 1 : 0), (rightval ? 1 : 0));
else switch (ep->opcode) {
case CMD_AND:
retval = (leftval && rightval);
break;
case CMD_OR:
retval = (leftval || rightval);
break;
case CMD_XOR:
retval = (leftval == rightval ? 0 : 1);
break;
#ifdef PARANOID
default:
interror(11, "invalid numerical operation");
#endif
}
ep->spec.cval.val.b = retval & 0x0001;
ep->spec.cval.t = &bool_type;
}
/*
*****************************************************************************
*
* Collapse a unary expression. This handles only one node!
*/
static void unary_collapse(ep)
struct expr *ep;
{
switch (ep->opcode) {
case '-':
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_NUM || ep->type != &int_type)
interror(18, "invalid unary operation");
#endif
ep->spec.cval.val.i = -(ep->left->spec.cval.val.i);
ep->spec.cval.t = ep->left->spec.cval.t;
break;
case CMD_NOT:
#ifdef PARANOID
if (exprtype(ep->left) != exprtype(ep) ||
(ep->type != &int_type && ep->type != &bool_type))
interror(19, "invalid unary operation");
#endif
if (exprtype(ep) == EXPR_NUM)
ep->spec.cval.val.i = ~(ep->left->spec.cval.val.i);
else
ep->spec.cval.val.b = (ep->left->spec.cval.val.b ?
0 : 1);
ep->spec.cval.t = ep->left->spec.cval.t;
break;
case CMD_CHR:
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_NUM || ep->type != &char_type)
interror(33, "invalid call to 'chr'");
#endif
if (ep->left->spec.cval.val.i < 0x00 ||
ep->left->spec.cval.val.i > 0xff) {
error("argument to 'chr' out of range");
return;
}
ep->spec.cval.val.c = ep->left->spec.cval.val.i & 0xff;
ep->spec.cval.t = &char_type;
break;
case CMD_ORD:
#ifdef PARANOID
if (ep->type != &int_type)
interror(17, "invalid call to 'ord'");
#endif
ep->spec.cval.val.i = getord(ep->left);
ep->spec.cval.t = &int_type;
break;
case CMD_ODD:
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_NUM || ep->type != &bool_type)
interror(39, "invalid call to 'odd'");
#endif
ep->spec.cval.val.b = ep->left->spec.cval.val.i & 0x0001;
ep->spec.cval.t = &bool_type;
break;
case CMD_ABS:
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_NUM || ep->type != &int_type)
interror(34, "invalid call to 'abs'");
#endif
ep->spec.cval.val.i = abs(ep->left->spec.cval.val.i);
ep->spec.cval.t = &int_type;
break;
case CMD_SQR:
#ifdef PARANOID
if (exprtype(ep->left) != EXPR_NUM || ep->type != &int_type)
interror(35, "invalid call to 'sqr'");
#endif
ep->spec.cval.val.i = ep->left->spec.cval.val.i ^ 2;
ep->spec.cval.t = &int_type;
break;
case CMD_PRED:
#ifdef PARANOID
if (ep->left->type != ep->type || !isscalar(ep->type))
interror(12, "invalid call to 'pred'");
#endif
switch (exprtype(ep)) {
case EXPR_NUM:
if (ep->spec.cval.val.i <= ep->type->def.s.min)
warning("integer overflow");
else
ep->spec.cval.val.i--;
break;
case EXPR_BOOL:
if (ep->spec.cval.val.b <= ep->type->def.s.min)
warning("boolean overflow");
else
ep->spec.cval.val.b--;
break;
case EXPR_CHAR:
if (ep->spec.cval.val.c <= ep->type->def.s.min)
warning("char overflow");
else
ep->spec.cval.val.c--;
break;
case EXPR_ENUM:
if (ep->spec.cval.val.e <= ep->type->def.s.min)
warning("enumeration overflow");
else
ep->spec.cval.val.e--;
break;
default:
break;
}
break;
case CMD_SUCC:
#ifdef PARANOID
if (ep->left->type != ep->type || !isscalar(ep->type))
interror(13, "invalid call to 'succ'");
#endif
switch (exprtype(ep)) {
case EXPR_NUM:
if (ep->spec.cval.val.i >= ep->type->def.s.max)
warning("integer overflow");
else
ep->spec.cval.val.i++;
break;
case EXPR_BOOL:
if (ep->spec.cval.val.b >= ep->type->def.s.max)
warning("boolean overflow");
else
ep->spec.cval.val.b++;
break;
case EXPR_CHAR:
if (ep->spec.cval.val.c >= ep->type->def.s.max)
warning("char overflow");
else
ep->spec.cval.val.c++;
break;
case EXPR_ENUM:
if (ep->spec.cval.val.e >= ep->type->def.s.max)
warning("char overflow");
else
ep->spec.cval.val.e++;
break;
default:
break;
}
break;
#ifdef PARANOID
default:
interror(7, "invalid unary operation");
break;
#endif
}
}
/*
*****************************************************************************
*
* Collapse an internal function call. This handles only one node! Function
* subtrees are already reorganized and collapsed by the parser.
*/
static void func_collapse(ep)
struct expr *ep;
{
int i, num1, num2;
char *cp;
/* Can only collapse internal functions */
if (!iscmdintfunc(ep))
return;
/* Check if all subtrees are constant */
for (i = 0; i < ep->exprnum; i++)
if (!isconst(ep->exprlist[i]))
return;
/* Process all internal function which we can handle */
switch (ep->opcode) {
case CMD_STRLEN:
#ifdef PARANOID
if (ep->exprnum != 1 || ep->type != &int_type ||
exprtype(ep->exprlist[0]) != EXPR_STRING ||
ep->exprlist[0]->spec.cval.val.s == NULL)
interror(37, "invalid call to 'strlen'");
#endif
ep->spec.cval.val.i = strlen(ep->exprlist[0]->spec.cval.val.s);
break;
case CMD_STRSUB:
#ifdef PARANOID
if (ep->exprnum != 3 || ep->type != &string_type ||
exprtype(ep->exprlist[0]) != EXPR_STRING ||
exprtype(ep->exprlist[1]) != EXPR_NUM ||
exprtype(ep->exprlist[2]) != EXPR_NUM ||
ep->exprlist[0]->spec.cval.val.s == NULL)
interror(36, "invalid call to 'strsub'");
#endif
ep->spec.cval.val.s = NULL;
cp = ep->exprlist[0]->spec.cval.val.s;
num1 = ep->exprlist[1]->spec.cval.val.i;
num2 = ep->exprlist[2]->spec.cval.val.i + 1;
if (num2 > strlen(cp))
num2 = strlen(cp);
cp[num2] = '\0';
if (num1 >= num2)
copystr(&(ep->spec.cval.val.s), "");
else
copystr(&(ep->spec.cval.val.s), &(cp[num1]));
break;
default:
/* Do nothing if we can't handle it */
return;
}
/* Delete all subtrees after collapsing */
for (i = 0; i < ep->exprnum; i++)
delexpr(ep->exprlist[i]);
ep->spec.cval.t = ep->type;
ep->opcode = CMD_CONST;
ep->exprnum = 0;
}
/*
*****************************************************************************
*
* Collapse a expression
*/
static struct expr *collapse(ep)
struct expr *ep;
{
/* Just a safety measure */
if (ep == NULL)
return(ep);
/* Function calls have their subtrees already reorganized */
if (iscmdfunc(ep)) {
/* This will delete all subtrees, so no need to do it here */
func_collapse(ep);
return(ep);
}
/* Handle leaf node expression */
if (ep->exprnum == 0)
return(ep);
/* Handle unary operation */
if (ep->exprnum == 1) {
ep->left = collapse(ep->left);
if (isconst(ep->left)) {
/* If left tree is leaf node, collapse constant values */
unary_collapse(ep);
delexpr(ep->left);
ep->opcode = CMD_CONST;
ep->exprnum = 0;
}
return(ep);
}
/* We can handle only binary expressions below */
#ifdef PARANOID
if (ep->exprnum != 2)
interror(16, "invalid number of subexpressions");
#endif
/* Collapse both sides of the tree, and check for errors (NULL returned) */
ep->left = collapse(ep->left);
ep->right = collapse(ep->right);
if (ep->left == NULL || ep->right == NULL) {
delexpr(ep);
return(NULL);
}
/* Handle binary operations. Collapse if both sides are constant */
if (isconst(ep->left) && isconst(ep->right)) {
switch (exprtype(ep->left)) {
case EXPR_CHAR:
case EXPR_STRING:
str_collapse(ep);
break;
case EXPR_NUM:
num_collapse(ep);
break;
case EXPR_BOOL:
bool_collapse(ep);
break;
#ifdef PARANOID
case EXPR_ENUM:
/* We don't have any binary operations for enum types */
default:
interror(9, "invalid type for binary operation");
break;
#endif
}
delexpr(ep->left);
delexpr(ep->right);
ep->opcode = CMD_CONST;
ep->exprnum = 0;
}
return(ep);
}
/*
*****************************************************************************
*
* Flatten an expression. With associative operations we can change the
* branches so that the right tree is larger than the left one. This will
* ease later optimization by the code generator.
*/
static struct expr *flatten(ep)
struct expr *ep;
{
basictypes typeleft, typeright;
struct expr *tmp1, *tmp2;
/*
* Handle leaf node expressions and functions. In the latter case we
* leave the reorganization of the function subexpressions to the
* collapse step.
*/
if (ep == NULL || isfunc(ep) || ep->exprnum == 0)
return(ep);
/* At unary nodes only reorganize one tree */
if (ep->exprnum == 1) {
ep->left = flatten(ep->left);
return(ep);
}
/* Below we can only deal with binary expressions */
#ifdef PARANOID
if (ep->exprnum != 2)
interror(14, "invalid number of subexpressions");
#endif
/*
* Now we have only binary operations. If we have a commutative command
* AND the right tree is larger than the left, we can swap both nodes so
* that the right tree becomes the larger one. There are no commutative
* commands for string expressions (string addition is NOT commutative!).
*/
if (exprtype(ep) != EXPR_STRING && iscmdcommut(ep) &&
ep->left->exprnum > ep->right->exprnum) {
tmp1 = ep->right;
ep->right = ep->left;
ep->left = tmp1;
}
/*
* If we have a type change due to the operation or no scalar types, we
* cannot continue but can only flatten the subexpressions. In this check,
* character expressions count the same as string expressions.
*/
if ((typeleft = exprtype(ep->left)) == EXPR_CHAR)
typeleft = EXPR_STRING;
if ((typeright = exprtype(ep->right)) == EXPR_CHAR)
typeright = EXPR_STRING;
if (!isscalar(ep->left->type) || exprtype(ep) == EXPR_ENUM ||
exprtype(ep) != typeleft || exprtype(ep) != typeright) {
ep->left = flatten(ep->left);
ep->right = flatten(ep->right);
return(ep);
}
#ifdef PARANOID
if (typeleft != typeright)
interror(15, "invalid types in binary operation");
#endif
/* Scan through the tree until we reach an end on the left side */
ep->right = flatten(ep->right);
if (ep->left->exprnum == 0 || isfunc(ep->left))
return(ep);
ep->left = flatten(ep->left);
/*
* Reorganize associative expressions, so that the right tree becomes
* larger than the left one. This basically means to shift the
* braces in an expression:
*
* (A^B)^C ==> A^(B^C)
*/
if (iscmdassoc(ep) && ep->opcode == ep->left->opcode) {
tmp1 = ep->left->right;
ep->left->right = ep;
tmp2 = ep->left;
ep->left = tmp1;
tmp2->right = flatten(ep);
ep = tmp2;
}
return(ep);
}
/*
*****************************************************************************
*
* Collapse an expression by combining all constant nodes
*/
struct expr *reorg(ep)
struct expr *ep;
{
if (ep != NULL) {
ep = flatten(ep);
ep = collapse(ep);
}
return(ep);
}
syntax highlighted by Code2HTML, v. 0.9.1