/***************************************************************************** * * eval.c * * Arithmetical evaluation. * *****************************************************************************/ #include "m4.h" /***************************************************************************** * * First, a warm-up: Increment and decrement. * *****************************************************************************/ /***************************************************************************** * * opIncr * opDecr * * Returns the value of its argument, augmented or diminished by unity. * The extra ptokNil covers us in the case where $# is zero. * *****************************************************************************/ void STDCALL opAddItokDat(ARGV argv, DAT dat) { AT at = atTraditionalPtok(ptokArgv(1)); #ifdef STRICT_M4 if (ctokArgv != 1) { Warn("wrong number of arguments to %P", ptokArgv(0)); } #endif PushAt(at+dat); } DeclareOp(opIncr) { opAddItokDat(argv, 1); } DeclareOp(opDecr) { opAddItokDat(argv, -1); } /***************************************************************************** * * Now the gross part: Eval. * * Expression evaluation is performed by a parser which is a mix of * shift-reduce and recursive-descent. (Worst of both worlds.) * * The precedence table for our expression language reads * * (...) grouping > primary * + - unary * ** exponentiation * * / % multiplicative * + - additive * << >> shift * == != > >= < <= relational * ! logical-negate * ~ bit-negate * & bit-and * ^ bit-xor * | bit-or * && logical-and * || logical-or * * * COMPAT -- AT&T style uses ^ for exponentiation; we use it for xor * * NOTE: "the rest is bogus" went the original comment. I forget what * I meant by that. * * The precedence table for the C-style expression language reads * * (...) grouping \ primary * + - ~ ! unary / * * / % multiplative \ * + - additive \ * << >> shift | * < > <= >= relational | * == != equality \ secondary * & bit-and / * ^ bit-xor | * | bit-or | * && logical-and / * || logical-or / * ? : ternary > tertiary * * Recursive descent is performed on the primary/secondary/tertiary * scale, but shift-reduce is performed within the secondary phase. * * The reason is that the operators in the secondary phase are * (1) binary, and (2) non-recursive. These two properties * make shift-reduce easy to implement. * * Primaries are recursive, so they are easier to implement in * recursive-descent. Tertiaries would clog up the shift-reduce * grammar, so they've been moved to recursive-descent as well. * *****************************************************************************/ /***************************************************************************** * * EachEop * * Before calling this macro, define the following macros, each of * which will be called with three arguments, * * nm = operator name as a C identifier (e.g., "Add") * op = operator name as a bare token (e.g., "+") * cb = length of operator name * * The macros should be * * x1 -- for native C unary operators * x1a -- for native C unary operators which have binary aliases * x2 -- for native C binary operators * x2a -- for native C binary operators which have unary aliases * x2n -- for non-native C binary operators * xp -- for phantom operators, * in which case op and cb are useless * * The order in which operators appear is important for the purpose * of tokenization. Longer operators must precede shorter ones. * *****************************************************************************/ #define EachEop() \ x2(Shl, <<, 2) \ x2(Shr, >>, 2) \ x2(Le, <=, 2) \ x2(Ge, >=, 2) \ x2(Eq, ==, 2) \ x2(Ne, !=, 2) \ x2(Land, &&, 2) \ x2(Lor, ||, 2) \ x2n(Exp, **, 2) \ x2(Mul, *, 1) \ x2(Div, /, 1) \ x2(Mod, %, 1) \ x2a(Add, +, 1) /* These two must be */ \ x2a(Sub, -, 1) /* in exactly this order */ \ x2(Lt, <, 1) \ x2(Gt, >, 1) \ x2(Band, &, 1) \ x2(Bxor, ^, 1) \ x2(Bor, |, 1) \ x1(Lnot, !, 1) \ x1(Bnot, ~, 1) \ x1a(Plu, +, x) /* These two must be */ \ x1a(Neg, -, x) /* in exactly this order */ \ xp(Flush, @, 0) \ xp(Boe, @, 0) \ /***************************************************************************** * * MakeEop * * Each binary operator has a handler which returns the combined * value. * * Each unary operator has a handler which returns the operator * applied to its single argument. * * All the operators are C native, except for Exp, which is handled * directly. * *****************************************************************************/ typedef AT (STDCALL *EOP1)(AT at); typedef AT (STDCALL *EOP2)(AT a, AT b); #define x1(nm, op, cb) AT STDCALL at##nm##At(AT at) { return op at; } #define x1a(nm, op, cb) AT STDCALL at##nm##At(AT at) { return op at; } #define x2(nm, op, cb) AT STDCALL at##nm##AtAt(AT a, AT b) { return a op b; } #define x2a(nm, op, cb) AT STDCALL at##nm##AtAt(AT a, AT b) { return a op b; } #define x2n(nm, op, cb) #define xp(nm, op, cb) EachEop() #undef x1 #undef x1a #undef x2 #undef x2a #undef x2n #undef xp /***************************************************************************** * * atExpAtAt * * Implement the exponentiation operator. * * QUIRK! AT&T returns 1 if $2 < 0. GNU raises an error. * I side with AT&T on this, only out of laziness. * *****************************************************************************/ AT STDCALL atExpAtAt(AT a, AT b) { AT at = 1; while (b > 0) { if (b & 1) { at = at * a; } a = a * a; b = b / 2; } return at; } TOK tokExpr; /* Current expression context */ /***************************************************************************** * * MakeEopTab * * Table of operators and operator precedence. Each entry in the * table contains the name, length, handler, precedence, and * flags that describe what kind of operator it is. * * Items are listed in precedence order here; the EachBop will * emit the table corrctly. * *****************************************************************************/ typedef enum EOPFL { eopflUn = 1, eopflBin = 2, eopflAmb = 4, } EOPFL; typedef UINT PREC; /* Operator precedence */ typedef struct EOPI { PTCH ptch; CTCH ctch; union { EOP1 eop1; EOP2 eop2; } u; PREC prec; EOPFL eopfl; } EOPI, *PEOPI; #define MakeEopi(nm, ctch, pfn, prec, eopfl) \ { TEXT(nm), ctch, { (EOP1)pfn }, prec, eopfl }, enum { m4precNeg = 14, m4precPlu = 14, m4precExp = 13, m4precMul = 12, m4precDiv = 12, m4precMod = 12, m4precAdd = 11, m4precSub = 11, m4precShl = 10, m4precShr = 10, m4precEq = 9, m4precNe = 9, m4precGt = 9, m4precGe = 9, m4precLt = 9, m4precLe = 9, m4precLnot = 8, m4precBnot = 7, m4precBand = 6, m4precBxor = 5, m4precBor = 4, m4precLand = 3, m4precLor = 2, m4precFlush = 1, /* Flushing out everything but Boe */ m4precBoe = 0, /* Beginning-of-expression */ }; #define x1(nm, op, cb) static TCH rgtch##nm[cb] = #op; #define x1a(nm, op, cb) #define x2(nm, op, cb) static TCH rgtch##nm[cb] = #op; #define x2a(nm, op, cb) static TCH rgtch##nm[cb] = #op; #define x2n(nm, op, cb) static TCH rgtch##nm[cb] = #op; #define xp(nm, op, cb) EachEop() #undef x1 #undef x1a #undef x2 #undef x2a #undef x2n #undef xp #define x1(nm, op, cb) MakeEopi(rgtch##nm, cb, at##nm##At, m4prec##nm, eopflUn) #define x1a(nm, op, cb) MakeEopi(0, 0, at##nm##At, m4prec##nm, eopflUn) #define x2(nm, op, cb) MakeEopi(rgtch##nm, cb, at##nm##AtAt, m4prec##nm, eopflBin) #define x2a(nm, op, cb) MakeEopi(rgtch##nm, cb, at##nm##AtAt, m4prec##nm, eopflAmb + eopflBin) /* initially bin */ #define x2n(nm, op, cb) MakeEopi(rgtch##nm, cb, at##nm##AtAt, m4prec##nm, eopflBin) #define xp(nm, op, cb) MakeEopi(0, 0, 0, m4prec##nm, 0) EOPI rgeopi[] = { EachEop() }; #undef x1 #undef x1a #undef x2 #undef x2a #undef x2n #undef xp #define x1(nm, op, cb) ieopi##nm, #define x1a(nm, op, cb) ieopi##nm, #define x2(nm, op, cb) ieopi##nm, #define x2a(nm, op, cb) ieopi##nm, #define x2n(nm, op, cb) ieopi##nm, #define xp(nm, op, cb) ieopi##nm, typedef enum IEOPI { EachEop() ieopMax, } IEOPI; #undef x1 #undef x1a #undef x2 #undef x2a #undef x2n #define peopiBoe (&rgeopi[ieopiBoe]) #define peopiFlush (&rgeopi[ieopiFlush]) /***************************************************************************** * * fPrimary, fSecondary, fTertiary * * Forward declarations for the recursive-descent parser. * * Each parses a token/expression of the appropriate class * and leaves it on the top of the expression stack, or * returns 0 if the value could not be parsed. * *****************************************************************************/ F STDCALL fPrimary(void); F STDCALL fSecondary(void); #define fTertiary fSecondary /***************************************************************************** * * Cells * * The expression stack consists of structures which, for lack of * a better name, are called `cells'. Each cell can hold either * an expression operator or an integer, distinguished by the fEopi * field. * * In keeping with parser terminology, the act of pushing something * onto the stack is called `shifting'. Collapsing objects is called * `reducing'. * *****************************************************************************/ typedef struct CELL { F fEopi; union { PEOPI peopi; AT at; } u; } CELL, *PCELL; typedef UINT CCELL, ICELL; PCELL rgcellEstack; /* The expression stack */ PCELL pcellMax; /* End of the stack */ PCELL pcellCur; /* Next free cell */ INLINE PCELL pcellTos(ICELL icell) { Assert(pcellCur - 1 - icell >= rgcellEstack); return pcellCur - 1 - icell; } /***************************************************************************** * * Stack munging * * Quickie routines that poke at the top-of-stack. * *****************************************************************************/ INLINE F fWantOp(void) { return !pcellTos(1)->fEopi; } INLINE F fOpTos(ICELL icell) { return pcellTos(icell)->fEopi; } INLINE PEOPI peopiTos(ICELL icell) { Assert(fOpTos(icell)); return pcellTos(icell)->u.peopi; } INLINE AT atTos(ICELL icell) { Assert(!fOpTos(icell)); return pcellTos(icell)->u.at; } INLINE F fBinTos(ICELL icell) { return peopiTos(icell)->eopfl & eopflBin; } INLINE F fUnTos(ICELL icell) { return peopiTos(icell)->eopfl & eopflUn; } INLINE F fAmbTos(ICELL icell) { return peopiTos(icell)->eopfl & eopflAmb; } INLINE PREC precTos(ICELL icell) { return peopiTos(icell)->prec; } INLINE void UnFromAmb(ICELL icell) { Assert(fOpTos(icell)); pcellTos(icell)->u.peopi += (ieopiPlu - ieopiAdd); } /***************************************************************************** * * ShiftCell * * Shift a cell onto the expression stack. * * QShiftCell shifts in a cell assuming that the stack is already * big enough to handle it. * *****************************************************************************/ void STDCALL QShiftCell(UINT_PTR uiObj, F fEopi) { Assert(pcellCur < pcellMax); pcellCur->fEopi = fEopi; if (fEopi) { pcellCur->u.peopi = (PEOPI)uiObj; } else { pcellCur->u.at = (INT)uiObj; } pcellCur++; } void STDCALL ShiftCell(UINT_PTR uiObj, F fEopi) { if (pcellCur >= pcellMax) { CCELL ccell = (CCELL)(pcellMax - rgcellEstack + 128); /* Should be enough */ rgcellEstack = pvReallocPvCb(rgcellEstack, ccell * sizeof(CELL)); pcellCur = rgcellEstack + ccell - 128; pcellMax = rgcellEstack + ccell; } QShiftCell(uiObj, fEopi); } #define ShiftPeopi(peopi) ShiftCell((UINT_PTR)(peopi), 1) #define ShiftAt(at) ShiftCell((UINT_PTR)(at), 0) #define QShiftPeopi(peopi) QShiftCell((UINT_PTR)(peopi), 1) #define QShiftAt(at) QShiftCell((UINT_PTR)(at), 0) #define Drop(icell) (pcellCur -= (icell)) /***************************************************************************** * * ReducePrec * * Reduce until everything with higher precedence has been cleaned off. * * Tos(0) should be a fresh operator. * Everything underneath should be a valid partial evaluation. * *****************************************************************************/ void STDCALL Reduce(void) { PEOPI peopi; Assert(fOpTos(0)); /* Tos(0) should be an op */ Assert(!fOpTos(1)); /* Tos(1) should be an int */ Assert(fOpTos(2)); /* Tos(2) should be an op */ peopi = peopiTos(0); /* Save this */ Drop(1); /* before we drop it */ while (precTos(1) > peopi->prec) { AT at; if (fUnTos(1)) { at = peopiTos(1)->u.eop1(atTos(0)); Drop(2); /* Drop the op and the arg */ } else { Assert(fBinTos(1)); Assert(!fOpTos(2)); at = peopiTos(1)->u.eop2(atTos(2), atTos(0)); Drop(3); /* Drop the op and two args */ } QShiftAt(at); /* Shift the answer back on */ Assert(!fOpTos(0)); /* Tos(0) should be an int */ Assert(fOpTos(1)); /* Tos(1) should be an op */ } QShiftPeopi(peopi); /* Restore the original op */ } /***************************************************************************** * * fPrimary * * Parse the next expression token and shift it onto the expression * stack. Zero is returned if there is no next token, or the token * is invalid. * * Here is where parenthesized expressions are handled, in a * recursive-descent manner. * * Ambiguous operators (ones which can be either unary or binary) * are returned as binary. * *****************************************************************************/ F STDCALL fPrimary(void) { SkipWhitePtok(&tokExpr); /* Skip leading whitespace */ /* * First see if we can find an operator. */ { PEOPI peopi; for (peopi = rgeopi; peopi < &rgeopi[ieopiPlu]; peopi++) { if (peopi->ctch <= ctchSPtok(&tokExpr) && fEqPtchPtchCtch(ptchPtok(&tokExpr), peopi->ptch, peopi->ctch)) { EatHeadPtokCtch(&tokExpr, peopi->ctch); /* Eat the op */ ShiftPeopi(peopi); return 1; } } } /* * Didn't find an operator. Look for an integer. */ { AT at; if (fEvalPtokPat(&tokExpr, &at)) { ShiftAt(at); return 1; } } /* * Not an integer either. Maybe a parenthesized expression. */ { if (ptchPtok(&tokExpr)[0] == '(') { EatHeadPtokCtch(&tokExpr, 1); /* Eat the paren */ if (fTertiary()) { /* Leaves answer on top of stack */ if (ptchPtok(&tokExpr)[0] == ')') { EatHeadPtokCtch(&tokExpr, 1); /* Eat the paren */ return 1; } else { return 0; } } else { return 0; /* Trouble down below */ } } } /* * Unrecognized token. Return failure. */ return 0; } /***************************************************************************** * * fSecondary * * Parse an expression from the expression stream, leaving the * result on the top of the expression stack. * *****************************************************************************/ F STDCALL fSecondary(void) { ShiftPeopi(peopiBoe); /* Beginning-of-expression marker */ while (fPrimary()) { if (fWantOp()) { if (fOpTos(0)) { if (fBinTos(0)) { Reduce(); } else { return 0; /* Unary operator unexpected */ } } else { return 0; /* Integer unexpected */ } } else { /* Integer expected */ if (fOpTos(0)) { if (fAmbTos(0)) { UnFromAmb(0); /* Disambiguify */ ; /* Unary operator already shifted */ } else if (fUnTos(0)) { ; /* Unary operator already shifted */ } else { return 0; /* Binary operator unexpected */ } } else { ; /* Integer already shifted */ } } } if (fOpTos(0)) { return 0; /* Ended in partial expression */ } { AT at; ShiftPeopi(peopiFlush); /* Flush out the rest of the expr */ Reduce(); /* to get a single number back */ Assert(peopiTos(0) == peopiFlush); at = atTos(1); Assert(peopiTos(2) == peopiBoe); /* Should be back to start */ Drop(3); ShiftAt(at); } return 1; } /***************************************************************************** * * opEval * * Evaluate the first expr. * * QUIRK! AT&T m4 considers a consisting entirely of whitespace to * evaluate to zero. (Probably due to a default accumulator in the * initial state of the evaluator.) GNU considers it an error. * I side with GNU on this one. * * QUIRK! If a negative width is passed, AT&T silently treats it * as zero. GNU raises an error. I side with A&T out of laziness. * * QUIRK! If a width greater than around 8000 is passed, AT&T * silently treats it as zero. GNU uses the full value. I side * with GNU on this one. * *****************************************************************************/ DeclareOp(opEval) { if (ctokArgv) { SetStaticPtokPtchCtch(&tokExpr, ptchArgv(1), ctchArgv(1)); D(tokExpr.tsfl |= tsflScratch); if (fTertiary()) { PushAtRadixCtch(atTos(0), (unsigned)atTraditionalPtok(ptokArgv(2)), ctokArgv >= 3 ? atTraditionalPtok(ptokArgv(3)) :0); Drop(1); Assert(pcellCur == rgcellEstack); } else { TOK tokPre; SetStaticPtokPtchCtch(&tokPre, ptchArgv(1), ctchArgv(1) - ctchSPtok(&tokExpr)); Die("Expression error at %P <> %P", &tokPre, &tokExpr); } } }