/* * expr.c - Support routines for handling expressions * * Copyright (C) 1997-2003 Gero Kuhlmann * * 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); }