Windows-Server-2003/sdktools/nmake/rpn.cpp

840 lines
23 KiB
C++

// RPN.C -- expression evaluator
//
// Copyright (c) 1988-1990, Microsoft Corporation. All rights reserved.
//
// Purpose:
// This module contains NMAKE's expression evaluator routines.
//
// Revision History:
// 15-Nov-1993 JdR Major speed improvements
// 15-Oct-1993 HV Use tchar.h instead of mbstring.h directly, change STR*() to _ftcs*()
// 10-May-1993 HV Add include file mbstring.h
// Change the str* functions to STR*
// 04-Dec-1989 SB Add prototype for match() and chkInvokeAndPush()
// 09-Oct-1989 SB Added HACK to handle pointer arithmetic quirks; Done to
// avoid rewriting entire module
// 08-Oct-1989 SB '!if' expressions can be decimal, octal or hex now
// 05-Apr-1989 SB made all funcs NEAR; Reqd to make all function calls NEAR
// 19-Sep-1988 RB Split ptr_to_string(). Process ESCH in program invocations.
// 17-Aug-1988 RB Clean up.
// 28-Jun-1988 rj Added doCmd parameter to execLine.
// 23-Jun-1988 rj Add parameter to execLine (no echo of command).
// 25-May-1988 rb Change isspace to _istspace, isdigit to _istdigit.
#include "precomp.h"
#pragma hdrstop
#include "rpn.h"
char * GetEndQuote(void);
char * GetEndBracket(void);
void check_syntax_error(UCHAR);
void type_and_val(UCHAR, INT_PTR);
void pushIntoList(void);
void printList(void);
BOOL handleExpr(void);
BOOL handleExists(char*);
BOOL handleDefines(char*);
void getTok(void);
BOOL do_binary_op(UCHAR);
BOOL do_unary_op(UCHAR);
UCHAR match(char *tokPtr);
void chkInvocAndPush(RPNINFO *pListPtr);
#define TEMPSTACKSIZE 512 // size of temporary stack
#define LISTSIZE 1024 // size of list of rpn-form items
RPNINFO tempStack[TEMPSTACKSIZE]; // temporary/operand stack
RPNINFO rpnList[LISTSIZE]; // list of items in rpn order
char * text; // pointer to expr text in lbufPtr
UCHAR prevTok; // initial token put on tempstack
BOOL done; // true if there are no more tokens
UCHAR errRow; // first token is '(' so error table
// row val is 3. See check_syntax....
RPNINFO * pTop; // top item on tempStack
RPNINFO * pList; // next free slot in list
RPNINFO * pEnd = &(tempStack[TEMPSTACKSIZE-1]);
RPNINFO * pListEnd = &(rpnList[LISTSIZE-1]);
RPNINFO tokRec;
// do_binary_op() - do operation on two stack operands
//
// arguments: type - operator type code
//
// actions : pops first operand from the stack (tempStack).
// checks the types of the two operands (the operand
// that was popped as well as the operand currently
// on top of the stack).
// if both operands are integers then do the operation
// else if both operands are strings and operation is
// the equality operation then do it.
// else return FALSE ( illegal operation )
//
// modifies : tempStack - top element will now be the result of
// the operation.
BOOL
do_binary_op(
UCHAR type
)
{
INT_PTR *left;
INT_PTR *right;
RPNINFO *pOldTop;
pOldTop = pTop--; // pop one item off stack, with a ptr to it
right = &pOldTop->valPtr;
left = &pTop->valPtr;
if ((pOldTop->type == INTEGER) && (pTop->type == INTEGER)) {
switch (type) {
case LOGICAL_OR:
*left = *left || *right;
break;
case LOGICAL_AND:
*left = *left && *right;
break;
case BIT_OR:
*left |= *right;
break;
case BIT_XOR:
*left ^= *right;
break;
case BIT_AND:
*left &= *right;
break;
case NOT_EQUAL:
*left = *right != *left;
break;
case EQUAL:
*left = *right == *left;
break;
case GREATER_THAN:
*left = *left > *right;
break;
case LESS_THAN:
*left = *left < *right;
break;
case GREATER_EQ:
*left = *left >= *right;
break;
case LESS_EQ:
*left = *left <= *right;
break;
case SHFT_RIGHT:
*left >>= *right;
break;
case SHFT_LEFT:
*left <<= *right;
break;
case BINARY_MINUS:
*left -= *right;
break;
case ADD:
*left += *right;
break;
case MODULUS:
if (!*right)
makeError(line, DIVIDE_BY_ZERO);
*left %= *right;
break;
case DIVIDE:
if (!*right)
makeError(line, DIVIDE_BY_ZERO);
*left /= *right;
break;
case MULTIPLY:
*left *= *right;
break;
default:
return(FALSE);
break;
}
} else if ((pOldTop->type == STR) &&
(pTop->type == STR) &&
((type == EQUAL) || (type == NOT_EQUAL))) {
pTop->type = INTEGER;
*left = !_tcscmp((char *) *left, (char *) *right);
if (type == NOT_EQUAL) {
if (!do_unary_op(LOGICAL_NOT)) {
return(FALSE);
}
}
} else {
return(FALSE);
}
return(TRUE);
}
// do_unary_op() - do operation on top stack operand
//
// arguments: type - operator type code
//
// actions : checks the type of the top operand on the stack
// if operand is an integer then do the operation
// else return FALSE ( illegal operation )
//
// modifies : tempStack - top element will now be the result of
// the operation.
BOOL
do_unary_op(
UCHAR type
)
{
INT_PTR *L_top;
L_top = &pTop->valPtr;
if (pTop->type == INTEGER) {
switch (type) {
case UNARY_MINUS:
*L_top = -*L_top;
break;
case COMPLEMENT:
*L_top = ~*L_top;
break;
case LOGICAL_NOT:
*L_top = !*L_top;
break;
default:
return(FALSE);
break;
}
} else {
return(FALSE);
}
return(TRUE);
}
// GetEndQuote
//
// Return the pointer to the next double-quote character in text. A
// double-quote followed immediately by a double-quote is skipped.
//
// text : the global ptr to the buffer is moved up beyond this string.
char *
GetEndQuote()
{
char *pStart;
for (pStart = ++text; *text; ++text)
if (*text == '\"') {
if (text[1] == '\"')
++text;
else
break;
}
if (!*text)
makeError(line, SYNTAX_MISSING_END_CHAR, '\"');
*text++ = '\0'; // null byte over closing quote
return(pStart);
}
// GetEndBracket
//
// Lexes a program invocation.
//
// Program invocation is of the form: [ prog <arglist> ].
// Process escaped ']' here because this is where we do the lexing.
//
// text : the global ptr to the buffer is moved up beyond this string.
char *
GetEndBracket()
{
char *pStart;
for (pStart = ++text; *text; text = _tcsinc (text)) {
if (*text == ESCH && text[1] == ']')
memmove(text, text + 1, 1 + _tcslen(text + 1));
else if (*text == ']')
break;
}
if (!*text)
makeError(line, SYNTAX_MISSING_END_CHAR, ']');
*text++ = '\0'; // null byte over closing bracket
return(pStart);
}
// check_syntax_error() - check if there is a syntax error in expr
//
// arguments: type - type of the current token
//
// actions: checks the type of the current token against the type
// of the previous token.
//
// ERROR_TABLE :
// 2nd tok
//
// alpha op unary_op ( )
// ------------------------------------------------
// alpha | 0 | 1 | 0 | 0 | 1 |
// -------------------------------------------------
// op | 1 | 0 | 1 | 1 | 0 |
// -------------------------------------------------
// unary_op | 1 | 0 | 0 | 1 | 0 |
// -------------------------------------------------
// ( | 1 | 0 | 1 | 1 | 0 |
// -------------------------------------------------
// ) | 0 | 1 | 0 | 0 | 1 |
// -------------------------------------------------
// 1st tok.
//
// alpha : a primary ( integer, str, prog. invoc. )
// op : a binary operator
// unary_op : a unary operator ( ~, !, - ). A ZERO in the slot => error
//
// NOTE: ANY CHANGES TO THE TYPE VALUES WILL AFFECT THIS ROUTINE.
void
check_syntax_error(
UCHAR newTok
)
{
extern UCHAR errTable[5][5];
extern UCHAR errRow;
UCHAR errCol;
if (newTok == LEFT_PAREN)
errCol = 3;
else if (newTok == RIGHT_PAREN)
errCol = 4;
else if (newTok > LOGICAL_NOT)
errCol = 0;
else if (newTok > MULTIPLY)
errCol = 2;
else
errCol = 1;
if (!errTable[errRow][errCol])
makeError(line, SYNTAX_INVALID_EXPR);
errRow = errCol; // this becomes the first token the next time
}
// type_and_val()
//
// arguments: type - the type code of the present operator.
// val - ptr to a str/or integer
//
// initialises a record with the type code, after checking for any
// syntax errors. The new token is checked against the previous token
// for illegal combinations of tokens.
// initialises the record with the integer value/string ptr.
void
type_and_val(
UCHAR type,
INT_PTR val
)
{
extern RPNINFO tokRec; // returned to handleExpr
extern UCHAR prevTok; // token last seen
check_syntax_error(type);
prevTok = type;
tokRec.type = type;
tokRec.valPtr = val;
}
// match()
//
// arguments: tokPtr - ptr to a token string ( in tokTable )
//
// actions : looks for a substring in the expression buffer
// pointed to by 'text', that matches the given token.
// if substring found, returns TRUE, else returns FALSE.
UCHAR
match(
char *tokPtr
)
{
extern char *text;
char *t = text;
while (*tokPtr && (*t == *tokPtr)) {
t++;
tokPtr++;
}
if (!*tokPtr) {
text = t;
return(TRUE);
}
return(FALSE);
}
// getTok()
//
// arguments: none
//
// gets a token from the expression buffer.
// if the current char from the buffer is a space/tab, skip space/tabs
// until we get a non-space char ( could be NULL char ).
// Check if we are now at the beginning of one of the tokens in the
// tokenTable. This covers most tokens.
// Check if we have a minus. If a minus and the previous token was an
// integer, this is a binary minus, else a unary minus.
// If the current char is a double-quote, we are at the start of a
// string-token.
// If the current char is a '[', we are at the start of a program
// invocation. In both cases, the escape character is '\\'.
// If current char is a digit, we have a constant ( integer ).
// Else we have defined(ID).
// If none of the above, if current char is NULL, break out, else
// report error ( illegal character string has been found ).
//
// If we came to the NULL char at the end of the buffer, set global
// flag 'done' to TRUE, return a RIGHT_PAREN to match the opening
// LEFT_PAREN.
//
//
// modifies: text : ptr to expression buffer.
// prevTok: thru' calls to type_and_val().
// done : at end of buffer
// errRow : index into error table, thru calls to
// type_and_val()
// returns : token in tokRec(global, static to the module). The
// token has the new type/integer/ptr values.
void
getTok()
{
extern UCHAR prevTok;
extern BOOL done;
char c;
TOKTABREC *p;
char *ptr;
long constant;
c = *text;
if (c == ' ' || c == '\t') {
while(_istspace(c))
c = *++text; // skip white spaces
}
if (IS_OPERATORCHAR(c)) {
for (p = tokTable; p->op_str && !match(p->op_str); p++)
;
} else {
// make p point to last entry in table
p = &tokTable[(sizeof(tokTable) / sizeof(TOKTABREC)) - 1];
}
if (p->op_str) {
type_and_val(p->op, 0);
} else
if (c == '-') { // now check if binary or unary minus to be returned
text++;
if (prevTok == INTEGER)
type_and_val(BINARY_MINUS, 0);
else
type_and_val(UNARY_MINUS, 0);
} else
if (c == '\"') {
type_and_val(STR, (INT_PTR) GetEndQuote());
} else
if (c == '[') {
type_and_val(PROG_INVOC_STR, (INT_PTR) GetEndBracket());
} else { // integers and IDs handled here
if (_istdigit(c)) {
char *pNumber = text;
errno = 0; // Accept decimal, octal or hex no (richgi)
constant = strtol(text, &text, 0);
if (errno == ERANGE) {
*text = '\0';
makeError(line, CONST_TOO_BIG, pNumber);
}
if (_totupper(*text) == 'L')
text++;
type_and_val(INTEGER, constant);
} else { // defined(ID) comes here
if (c) {
if (!_tcsnicmp(text, "DEFINED", 7)) {
if (!(ptr = _tcschr(text, '(')))
makeError(line, SYNTAX_INVALID_EXPR);
ptr++;
text = ptr + _tcscspn(ptr, ")");
*text++ = '\0';
type_and_val(INTEGER, handleDefines(ptr));
}
else if (!_tcsnicmp(text, "EXIST", 5)) {
if (!(ptr = _tcschr(text, '(')))
makeError(line, SYNTAX_INVALID_EXPR);
ptr++;
text = ptr + _tcscspn(ptr, ")");
*text++ = '\0';
type_and_val(INTEGER, handleExists(ptr));
}
else
makeError(line, SYNTAX_INVALID_EXPR);
} else { // we are now at the end of the string (c is null)
done = TRUE;
type_and_val(RIGHT_PAREN, 0); // this is the last token
}
}
}
}
// chkInvocAndPush() - check if program invocation required
//
// arguments: pListPtr - might have a program invocation string
// present.
//
// actions : if this is a program invocation string, make the
// program invocation.
// the return value is got and placed on the stack.
// the type of the new stack element is now INTEGER.
// else place list item on stack.
//
// in either case it moves one item from list to stack.
void
chkInvocAndPush(
RPNINFO *pListPtr
)
{
++pTop;
if (pListPtr->type == PROG_INVOC_STR) {
pTop->valPtr = execLine((char *) pListPtr->valPtr, FALSE, TRUE, FALSE, NULL);
pTop->type = INTEGER;
} else {
*pTop = *pListPtr;
}
}
// processList()
//
// arguments: none
//
// actions : remove an item from the list.
// if the item is an operand, place it on the operand
// stack (tempStack).
// if the operand is a program invocation string, make
// the invocation, place the return code on stack.
// if the item is an operator, call the function to
// do the operation on one/two elements on tempStack.
//
// finally, check if there is exactly one item on stack.
// if this item has a value of zero, return FALSE.
// else return TRUE.
// if more than one item on stack, abort with error.
//
// modifies: pTop - ptr to top of tempStack.
// pList - ptr to next position in list.
BOOL
processList()
{
extern RPNINFO *pList;
extern RPNINFO *pTop;
RPNINFO *pTemp;
BOOL (* func)(UCHAR);
for (pTemp = rpnList; pTemp < pList; pTemp++) {
if (pTemp->type > LOGICAL_NOT) { // operand
chkInvocAndPush(pTemp);
} else {
if (pTemp->type > MULTIPLY)
func = do_unary_op;
else
func = do_binary_op;
if (!(*func)(pTemp->type))
makeError(line, BAD_OP_TYPES);
}
}
if ((pTop == tempStack) && (pTop->type == INTEGER))
if (!pTop->valPtr)
return(FALSE);
else
return(TRUE);
else
makeError(line, SYNTAX_INVALID_EXPR);
return(FALSE);
}
// pushIntoList()
//
// arguments: none
//
// actions : pops an item from the tempStack and pushes it onto
// the list. checks list for overflow ( internal error )
// and tempStack for underflow ( syntax error in expr ).
//
// modifies: tempTop - index of top of tempStack.
// nextInList - index to next position in list.
void
pushIntoList()
{
if (pTop < tempStack)
makeError(line, SYNTAX_INVALID_EXPR);
if (pList > pListEnd)
makeError(line, EXPR_TOO_LONG_INTERNAL);
#if !defined(NDEBUG)
// Keep track of the high water mark on the stack just for grins
{
static int iStackMax = 0;
if ( pList - rpnList > iStackMax )
iStackMax = (int) (pList - rpnList);
}
#endif
*pList++ = *pTop--;
}
// handleExpr()
//
// arguments: text - pointer to the buffer that has the expression.
//
// actions : calls getTok() to get tokens from the buffer. Places
// tokens in a tempStack, and moves them into a list in
// reverse-polish order.
//
// We need the list so that ALL syntax errors are caught
// BEFORE processing of the expression begins (especially
// program invocations that have side effects)
//
// Once the list is available, an operand stack is used
// Items are popped and pushed from this stack by the
// evaluation routines (add, mult, negate etc.)
//
// we don't really need a separate operand stack. the
// tempStack has served its purpose when the list is
// formed and so it may be used for operand processing.
BOOL
handleExpr()
{
extern RPNINFO tokRec;
BOOL fRParen; // was the token got a right paren?
extern BOOL done;
extern RPNINFO *pTop, *pList;
extern UCHAR errRow;
extern UCHAR prevTok;
pTop = tempStack;
pList = rpnList;
done = FALSE;
errRow = 3; // row for the first token put in,left paren
prevTok = LEFT_PAREN;
type_and_val(LEFT_PAREN, 0);
*pTop = tokRec;
while (!done) { // while there are more tokens in buffer
getTok();
fRParen = FALSE;
if (tokRec.type != LEFT_PAREN) {
while (precVector[tokRec.type] <= precVector[pTop->type]) {
if (!precVector[tokRec.type]) { // if RIGHT_PAREN pop till a
// left paren is seen
while (pTop->type != LEFT_PAREN)
pushIntoList();
fRParen = TRUE;
if (pTop < tempStack) {
makeError(line, SYNTAX_INVALID_EXPR);
} else {
pTop--; // pop the left paren
break;
}
} else {
pushIntoList();
}
}
}
// if token is a left paren, it has to go on the stack
if (!fRParen) {
if (pTop == pEnd)
makeError(line, EXPR_TOO_LONG_INTERNAL);
else
*++pTop = tokRec;
}
}
// check the stack here for not empty state
if (pTop != tempStack - 1)
makeError(line, SYNTAX_INVALID_EXPR);
return(processList());
}
// handleDefines()
//
// arguments: t pointer to buffer that has the identifier
//
// actions: Checks if one of 'ID' is present.
// Aborts with error if more IDs present.
// Is called for ifdef/ifndef/defined(ID).
//
// returns : TRUE if ID found in table. FALSE otherwise.
BOOL
handleDefines(
char *t
)
{
char *s;
s = _tcstok(t, " \t");
if (_tcstok(NULL, " \t")) {
makeError(line, SYNTAX_UNEXPECTED_TOKEN, s);
}
if (!s) {
makeError(line, MISSING_ARG_BEFORE_PAREN);
}
if (findMacro(s)) {
return(TRUE);
}
return(FALSE);
}
// handleExists()
//
// arguments: t pointer to buffer that has the identifier
//
// actions: Checks if 'name' is a valid file/directory
// Aborts with error if more names present.
// Is called for exist(name).
//
// returns : TRUE if ID found in table. FALSE otherwise.
BOOL
handleExists(
char *_t
)
{
char *s;
char *szUnQuoted;
BOOL fResult = FALSE;
char *szDelim;
char *t;
// make local copy, strip blank space before and after string
char *tSav = t = makeString(_t);
while (*t && WHITESPACE (*t)) {
t++;
}
s = t + _tcslen(t);
while (s > t) {
s = _tcsdec(t, s);
if (s) {
if (WHITESPACE (*s)) {
*s = '\0';
}
else {
break;
}
}
}
szDelim = ('\"' == *t) ? "\t" : " \t";
// DS 15360: if id starts with a quote,
// use "\t" instead of " \t" in _tcstok
// (handle paths with embedded spaces)
s = _tcstok(t, szDelim);
if (_tcstok(NULL, szDelim)) {
makeError(line, SYNTAX_UNEXPECTED_TOKEN, s);
}
if (NULL == s || NULL == (szUnQuoted = unQuote(s))) { // handle quoted names
makeError(line, MISSING_ARG_BEFORE_PAREN);
}
if (!_access(szUnQuoted, 0x00)) { // existence check
fResult = TRUE;
}
FREE(szUnQuoted);
FREE(tSav);
return(fResult);
}
// evalExpr()
//
// arguments: t pointer to buffer that has the expression
// kind specifies if it is if/ifdef/ifndef etc.
//
//
//
// returns : TRUE if expression evaluates to true.
// FALSE otherwise.
BOOL
evalExpr(
char *t,
UCHAR kind
)
{
if (!*t) {
makeError(line, SYNTAX_MISSING_DIRECTIVE);
}
switch (kind) {
case IFDEF_TYPE:
case ELSE_IFDEF_TYPE:
return(handleDefines(t));
case IFNDEF_TYPE:
case ELSE_IFNDEF_TYPE:
return((BOOL)!handleDefines(t));
default:
text = t;
return(handleExpr());
}
}