From bd5139c89e714bb7e10a0da55d9a10f51e93516c Mon Sep 17 00:00:00 2001 From: Steve Bennett Date: Fri, 12 May 2017 13:33:44 +1000 Subject: [PATCH] expr: Replace expression engine Rework the expression engine to use recursive descent evaluation rather than a shunting yard algorithm. Among other things, it is easier to make lazy operators and the ternary operator work correctly. In particular, the following expression no longer crashes: $(99?9,99?9:*9:999)?9) And the code is now smaller. Signed-off-by: Steve Bennett --- jim.c | 1529 ++++++++++++++++++++++--------------------------------- jim.h | 2 +- regtest.tcl | 5 + tests/expr.test | 8 + 4 files changed, 611 insertions(+), 933 deletions(-) diff --git a/jim.c b/jim.c index 9e2bb81..f4e1d54 100644 --- a/jim.c +++ b/jim.c @@ -4916,12 +4916,8 @@ static Jim_Obj *JimExpandDictSugar(Jim_Interp *interp, Jim_Obj *objPtr) static Jim_Obj *JimExpandExprSugar(Jim_Interp *interp, Jim_Obj *objPtr) { - Jim_Obj *resultObjPtr; - - if (Jim_EvalExpression(interp, objPtr, &resultObjPtr) == JIM_OK) { - /* Note that the result has a ref count of 1, but we need a ref count of 0 */ - resultObjPtr->refCount--; - return resultObjPtr; + if (Jim_EvalExpression(interp, objPtr) == JIM_OK) { + return Jim_GetResult(interp); } return NULL; } @@ -5557,6 +5553,7 @@ void Jim_FreeInterp(Jim_Interp *i) printf("Objects still in the free list:\n"); while (objPtr) { const char *type = objPtr->typePtr ? objPtr->typePtr->name : "string"; + Jim_String(objPtr); if (objPtr->bytes && strlen(objPtr->bytes) > 20) { printf("%p (%d) %-10s: '%.20s...'\n", @@ -7574,13 +7571,12 @@ static int JimParseExprNumber(struct JimParserCtx *pc); static int JimParseExprIrrational(struct JimParserCtx *pc); static int JimParseExprBoolean(struct JimParserCtx *pc); -/* Exrp's Stack machine operators opcodes. */ - -/* Binary operators (numbers) */ +/* expr operator opcodes. */ enum { /* Continues on from the JIM_TT_ space */ - /* Operations */ + + /* Binary operators (numbers) */ JIM_EXPROP_MUL = JIM_TT_EXPR_OP, /* 20 */ JIM_EXPROP_DIV, JIM_EXPROP_MOD, @@ -7599,45 +7595,26 @@ enum JIM_EXPROP_BITAND, /* 35 */ JIM_EXPROP_BITXOR, JIM_EXPROP_BITOR, - - /* Note must keep these together */ JIM_EXPROP_LOGICAND, /* 38 */ - JIM_EXPROP_LOGICAND_LEFT, - JIM_EXPROP_LOGICAND_RIGHT, - - /* and these */ - JIM_EXPROP_LOGICOR, /* 41 */ - JIM_EXPROP_LOGICOR_LEFT, - JIM_EXPROP_LOGICOR_RIGHT, - - /* and these */ - /* Ternary operators */ - JIM_EXPROP_TERNARY, /* 44 */ - JIM_EXPROP_TERNARY_LEFT, - JIM_EXPROP_TERNARY_RIGHT, - - /* and these */ - JIM_EXPROP_COLON, /* 47 */ - JIM_EXPROP_COLON_LEFT, - JIM_EXPROP_COLON_RIGHT, + JIM_EXPROP_LOGICOR, /* 39 */ + JIM_EXPROP_TERNARY, /* 40 */ + JIM_EXPROP_COLON, /* 41 */ + JIM_EXPROP_POW, /* 42 */ - JIM_EXPROP_POW, /* 50 */ - -/* Binary operators (strings) */ - JIM_EXPROP_STREQ, /* 51 */ + /* Binary operators (strings) */ + JIM_EXPROP_STREQ, /* 43 */ JIM_EXPROP_STRNE, JIM_EXPROP_STRIN, JIM_EXPROP_STRNI, -/* Unary operators (numbers) */ - JIM_EXPROP_NOT, /* 55 */ + /* Unary operators (numbers) */ + JIM_EXPROP_NOT, /* 47 */ JIM_EXPROP_BITNOT, JIM_EXPROP_UNARYMINUS, JIM_EXPROP_UNARYPLUS, /* Functions */ - JIM_EXPROP_FUNC_FIRST, /* 59 */ - JIM_EXPROP_FUNC_INT = JIM_EXPROP_FUNC_FIRST, + JIM_EXPROP_FUNC_INT, /* 51 */ JIM_EXPROP_FUNC_WIDE, JIM_EXPROP_FUNC_ABS, JIM_EXPROP_FUNC_DOUBLE, @@ -7667,47 +7644,47 @@ enum JIM_EXPROP_FUNC_FMOD, }; -struct JimExprState -{ - Jim_Obj **stack; - int stacklen; - int opcode; - int skip; +/* A expression node is either a term or an operator + * If a node is an operator, 'op' points to the details of the operator and it's terms. + */ +struct JimExprNode { + int type; /* JIM_TT_xxx */ + struct Jim_Obj *objPtr; /* The object for a term, or NULL for an operator */ + + struct JimExprNode *left; /* For all operators */ + struct JimExprNode *right; /* For binary operators */ + struct JimExprNode *ternary; /* For ternary operator only */ }; /* Operators table */ typedef struct Jim_ExprOperator { const char *name; - int (*funcop) (Jim_Interp *interp, struct JimExprState * e); + int (*funcop) (Jim_Interp *interp, struct JimExprNode *opnode); unsigned char precedence; unsigned char arity; - unsigned char lazy; + unsigned char attr; unsigned char namelen; } Jim_ExprOperator; -static void ExprPush(struct JimExprState *e, Jim_Obj *obj) -{ - Jim_IncrRefCount(obj); - e->stack[e->stacklen++] = obj; -} +static Jim_Obj *JimExprGetTerm(Jim_Interp *interp, struct JimExprNode *node); +static int JimExprGetTermBoolean(Jim_Interp *interp, struct JimExprNode *node); +static int JimExprEvalTermNode(Jim_Interp *interp, struct JimExprNode *node); -static Jim_Obj *ExprPop(struct JimExprState *e) -{ - JimPanic((e->stacklen <= 0, "expr stack underflow")); - return e->stack[--e->stacklen]; -} - -static int JimExprOpNumUnary(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpNumUnary(Jim_Interp *interp, struct JimExprNode *node) { int intresult = 1; int rc = JIM_OK; - Jim_Obj *A = ExprPop(e); double dA, dC = 0; jim_wide wA, wC = 0; + Jim_Obj *A; + + if ((A = JimExprGetTerm(interp, node->left)) == NULL) { + return JIM_ERR; + } if ((A->typePtr != &doubleObjType || A->bytes) && JimGetWideNoErr(interp, A, &wA) == JIM_OK) { - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_FUNC_INT: case JIM_EXPROP_FUNC_WIDE: case JIM_EXPROP_FUNC_ROUND: @@ -7732,7 +7709,7 @@ static int JimExprOpNumUnary(Jim_Interp *interp, struct JimExprState *e) } } else if ((rc = Jim_GetDouble(interp, A, &dA)) == JIM_OK) { - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_FUNC_INT: case JIM_EXPROP_FUNC_WIDE: wC = dA; @@ -7767,10 +7744,10 @@ static int JimExprOpNumUnary(Jim_Interp *interp, struct JimExprState *e) if (rc == JIM_OK) { if (intresult) { - ExprPush(e, Jim_NewIntObj(interp, wC)); + Jim_SetResultInt(interp, wC); } else { - ExprPush(e, Jim_NewDoubleObj(interp, dC)); + Jim_SetResult(interp, Jim_NewDoubleObj(interp, dC)); } } @@ -7787,20 +7764,25 @@ static double JimRandDouble(Jim_Interp *interp) return (double)x / (unsigned long)~0; } -static int JimExprOpIntUnary(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpIntUnary(Jim_Interp *interp, struct JimExprNode *node) { - Jim_Obj *A = ExprPop(e); jim_wide wA; + Jim_Obj *A; + int rc; + + if ((A = JimExprGetTerm(interp, node->left)) == NULL) { + return JIM_ERR; + } - int rc = Jim_GetWide(interp, A, &wA); + rc = Jim_GetWide(interp, A, &wA); if (rc == JIM_OK) { - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_BITNOT: - ExprPush(e, Jim_NewIntObj(interp, ~wA)); + Jim_SetResultInt(interp, ~wA); break; case JIM_EXPROP_FUNC_SRAND: JimPrngSeed(interp, (unsigned char *)&wA, sizeof(wA)); - ExprPush(e, Jim_NewDoubleObj(interp, JimRandDouble(interp))); + Jim_SetResult(interp, Jim_NewDoubleObj(interp, JimRandDouble(interp))); break; default: abort(); @@ -7812,25 +7794,29 @@ static int JimExprOpIntUnary(Jim_Interp *interp, struct JimExprState *e) return rc; } -static int JimExprOpNone(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpNone(Jim_Interp *interp, struct JimExprNode *node) { - JimPanic((e->opcode != JIM_EXPROP_FUNC_RAND, "JimExprOpNone only support rand()")); + JimPanic((node->type != JIM_EXPROP_FUNC_RAND, "JimExprOpNone only support rand()")); - ExprPush(e, Jim_NewDoubleObj(interp, JimRandDouble(interp))); + Jim_SetResult(interp, Jim_NewDoubleObj(interp, JimRandDouble(interp))); return JIM_OK; } #ifdef JIM_MATH_FUNCTIONS -static int JimExprOpDoubleUnary(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpDoubleUnary(Jim_Interp *interp, struct JimExprNode *node) { int rc; - Jim_Obj *A = ExprPop(e); double dA, dC; + Jim_Obj *A; + + if ((A = JimExprGetTerm(interp, node->left)) == NULL) { + return JIM_ERR; + } rc = Jim_GetDouble(interp, A, &dA); if (rc == JIM_OK) { - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_FUNC_SIN: dC = sin(dA); break; @@ -7879,7 +7865,7 @@ static int JimExprOpDoubleUnary(Jim_Interp *interp, struct JimExprState *e) default: abort(); } - ExprPush(e, Jim_NewDoubleObj(interp, dC)); + Jim_SetResult(interp, Jim_NewDoubleObj(interp, dC)); } Jim_DecrRefCount(interp, A); @@ -7889,19 +7875,26 @@ static int JimExprOpDoubleUnary(Jim_Interp *interp, struct JimExprState *e) #endif /* A binary operation on two ints */ -static int JimExprOpIntBin(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpIntBin(Jim_Interp *interp, struct JimExprNode *node) { - Jim_Obj *B = ExprPop(e); - Jim_Obj *A = ExprPop(e); jim_wide wA, wB; int rc = JIM_ERR; + Jim_Obj *A, *B; + + if ((A = JimExprGetTerm(interp, node->left)) == NULL) { + return JIM_ERR; + } + if ((B = JimExprGetTerm(interp, node->right)) == NULL) { + Jim_DecrRefCount(interp, A); + return JIM_ERR; + } if (Jim_GetWide(interp, A, &wA) == JIM_OK && Jim_GetWide(interp, B, &wB) == JIM_OK) { jim_wide wC; rc = JIM_OK; - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_LSHIFT: wC = wA << wB; break; @@ -7958,7 +7951,7 @@ static int JimExprOpIntBin(Jim_Interp *interp, struct JimExprState *e) /* Shift left by the word size or more is undefined. */ uB %= S; - if (e->opcode == JIM_EXPROP_ROTR) { + if (node->type == JIM_EXPROP_ROTR) { uB = S - uB; } wC = (unsigned long)(uA << uB) | (uA >> (S - uB)); @@ -7967,8 +7960,7 @@ static int JimExprOpIntBin(Jim_Interp *interp, struct JimExprState *e) default: abort(); } - ExprPush(e, Jim_NewIntObj(interp, wC)); - + Jim_SetResultInt(interp, wC); } Jim_DecrRefCount(interp, A); @@ -7979,14 +7971,20 @@ static int JimExprOpIntBin(Jim_Interp *interp, struct JimExprState *e) /* A binary operation on two ints or two doubles (or two strings for some ops) */ -static int JimExprOpBin(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpBin(Jim_Interp *interp, struct JimExprNode *node) { int rc = JIM_OK; double dA, dB, dC = 0; jim_wide wA, wB, wC = 0; + Jim_Obj *A, *B; - Jim_Obj *B = ExprPop(e); - Jim_Obj *A = ExprPop(e); + if ((A = JimExprGetTerm(interp, node->left)) == NULL) { + return JIM_ERR; + } + if ((B = JimExprGetTerm(interp, node->right)) == NULL) { + Jim_DecrRefCount(interp, A); + return JIM_ERR; + } if ((A->typePtr != &doubleObjType || A->bytes) && (B->typePtr != &doubleObjType || B->bytes) && @@ -7994,7 +7992,7 @@ static int JimExprOpBin(Jim_Interp *interp, struct JimExprState *e) /* Both are ints */ - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_POW: case JIM_EXPROP_FUNC_POW: if (wA == 0 && wB < 0) { @@ -8059,7 +8057,7 @@ static int JimExprOpBin(Jim_Interp *interp, struct JimExprState *e) } } if (Jim_GetDouble(interp, A, &dA) == JIM_OK && Jim_GetDouble(interp, B, &dB) == JIM_OK) { - switch (e->opcode) { + switch (node->type) { #ifndef JIM_MATH_FUNCTIONS case JIM_EXPROP_POW: case JIM_EXPROP_FUNC_POW: @@ -8131,7 +8129,7 @@ static int JimExprOpBin(Jim_Interp *interp, struct JimExprState *e) /* XXX: Could optimise the eq/ne case by checking lengths */ int i = Jim_StringCompareObj(interp, A, B, 0); - switch (e->opcode) { + switch (node->type) { case JIM_EXPROP_LT: wC = i < 0; goto intresult; @@ -8159,10 +8157,10 @@ done: Jim_DecrRefCount(interp, B); return rc; intresult: - ExprPush(e, Jim_NewIntObj(interp, wC)); + Jim_SetResultInt(interp, wC); goto done; doubleresult: - ExprPush(e, Jim_NewDoubleObj(interp, dC)); + Jim_SetResult(interp, Jim_NewDoubleObj(interp, dC)); goto done; } @@ -8180,18 +8178,26 @@ static int JimSearchList(Jim_Interp *interp, Jim_Obj *listObjPtr, Jim_Obj *valOb return 0; } -static int JimExprOpStrBin(Jim_Interp *interp, struct JimExprState *e) -{ - Jim_Obj *B = ExprPop(e); - Jim_Obj *A = ExprPop(e); + +static int JimExprOpStrBin(Jim_Interp *interp, struct JimExprNode *node) +{ + Jim_Obj *A, *B; jim_wide wC; - switch (e->opcode) { + if ((A = JimExprGetTerm(interp, node->left)) == NULL) { + return JIM_ERR; + } + if ((B = JimExprGetTerm(interp, node->right)) == NULL) { + Jim_DecrRefCount(interp, A); + return JIM_ERR; + } + + switch (node->type) { case JIM_EXPROP_STREQ: case JIM_EXPROP_STRNE: wC = Jim_StringEqObj(A, B); - if (e->opcode == JIM_EXPROP_STRNE) { + if (node->type == JIM_EXPROP_STRNE) { wC = !wC; } break; @@ -8204,7 +8210,7 @@ static int JimExprOpStrBin(Jim_Interp *interp, struct JimExprState *e) default: abort(); } - ExprPush(e, Jim_NewIntObj(interp, wC)); + Jim_SetResultInt(interp, wC); Jim_DecrRefCount(interp, A); Jim_DecrRefCount(interp, B); @@ -8230,149 +8236,59 @@ static int ExprBool(Jim_Interp *interp, Jim_Obj *obj) return -1; } -static int JimExprOpAndLeft(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpAnd(Jim_Interp *interp, struct JimExprNode *node) { - Jim_Obj *skip = ExprPop(e); - Jim_Obj *A = ExprPop(e); - int rc = JIM_OK; + /* evaluate left */ + int result = JimExprGetTermBoolean(interp, node->left); - switch (ExprBool(interp, A)) { - case 0: - /* false, so skip RHS opcodes with a 0 result */ - e->skip = JimWideValue(skip); - ExprPush(e, Jim_NewIntObj(interp, 0)); - break; - - case 1: - /* true so continue */ - break; - - case -1: - /* Invalid */ - rc = JIM_ERR; + if (result == 1) { + /* true so evaluate right */ + result = JimExprGetTermBoolean(interp, node->right); } - Jim_DecrRefCount(interp, A); - Jim_DecrRefCount(interp, skip); - - return rc; -} - -static int JimExprOpOrLeft(Jim_Interp *interp, struct JimExprState *e) -{ - Jim_Obj *skip = ExprPop(e); - Jim_Obj *A = ExprPop(e); - int rc = JIM_OK; - - switch (ExprBool(interp, A)) { - case 0: - /* false, so do nothing */ - break; - - case 1: - /* true so skip RHS opcodes with a 1 result */ - e->skip = JimWideValue(skip); - ExprPush(e, Jim_NewIntObj(interp, 1)); - break; - - case -1: - /* Invalid */ - rc = JIM_ERR; - break; + if (result == -1) { + return JIM_ERR; } - Jim_DecrRefCount(interp, A); - Jim_DecrRefCount(interp, skip); - - return rc; + Jim_SetResultInt(interp, result); + return JIM_OK; } -static int JimExprOpAndOrRight(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpOr(Jim_Interp *interp, struct JimExprNode *node) { - Jim_Obj *A = ExprPop(e); - int rc = JIM_OK; - - switch (ExprBool(interp, A)) { - case 0: - ExprPush(e, Jim_NewIntObj(interp, 0)); - break; + /* evaluate left */ + int result = JimExprGetTermBoolean(interp, node->left); - case 1: - ExprPush(e, Jim_NewIntObj(interp, 1)); - break; - - case -1: - /* Invalid */ - rc = JIM_ERR; - break; + if (result == 0) { + /* false so evaluate right */ + result = JimExprGetTermBoolean(interp, node->right); } - Jim_DecrRefCount(interp, A); - - return rc; -} - -static int JimExprOpTernaryLeft(Jim_Interp *interp, struct JimExprState *e) -{ - Jim_Obj *skip = ExprPop(e); - Jim_Obj *A = ExprPop(e); - int rc = JIM_OK; - - /* Repush A */ - ExprPush(e, A); - - switch (ExprBool(interp, A)) { - case 0: - /* false, skip RHS opcodes */ - e->skip = JimWideValue(skip); - /* Push a dummy value */ - ExprPush(e, Jim_NewIntObj(interp, 0)); - break; - - case 1: - /* true so do nothing */ - break; - - case -1: - /* Invalid */ - rc = JIM_ERR; - break; + if (result == -1) { + return JIM_ERR; } - Jim_DecrRefCount(interp, A); - Jim_DecrRefCount(interp, skip); - - return rc; + Jim_SetResultInt(interp, result); + return JIM_OK; } -static int JimExprOpColonLeft(Jim_Interp *interp, struct JimExprState *e) +static int JimExprOpTernary(Jim_Interp *interp, struct JimExprNode *node) { - Jim_Obj *skip = ExprPop(e); - Jim_Obj *B = ExprPop(e); - Jim_Obj *A = ExprPop(e); + /* evaluate left */ + int result = JimExprGetTermBoolean(interp, node->left); - /* No need to check for A as non-boolean */ - if (ExprBool(interp, A)) { - /* true, so skip RHS opcodes */ - e->skip = JimWideValue(skip); - /* Repush B as the answer */ - ExprPush(e, B); + if (result == 1) { + /* true so select right */ + return JimExprEvalTermNode(interp, node->right); } - - Jim_DecrRefCount(interp, skip); - Jim_DecrRefCount(interp, A); - Jim_DecrRefCount(interp, B); - return JIM_OK; -} - -static int JimExprOpNull(Jim_Interp *interp, struct JimExprState *e) -{ - return JIM_OK; + else if (result == 0) { + /* false so select ternary */ + return JimExprEvalTermNode(interp, node->ternary); + } + /* error */ + return JIM_ERR; } enum { - LAZY_NONE, - LAZY_OP, - LAZY_LEFT, - LAZY_RIGHT, - RIGHT_ASSOC, /* reuse this field for right associativity too */ + OP_FUNC = 0x0001, /* function syntax */ + OP_RIGHT_ASSOC = 0x0002, /* right associative */ }; /* name - precedence - arity - opcode @@ -8382,7 +8298,7 @@ enum * The following macros pre-compute the string length at compile time. */ #define OPRINIT_ATTR(N, P, ARITY, F, ATTR) {N, F, P, ARITY, ATTR, sizeof(N) - 1} -#define OPRINIT(N, P, ARITY, F) OPRINIT_ATTR(N, P, ARITY, F, LAZY_NONE) +#define OPRINIT(N, P, ARITY, F) OPRINIT_ATTR(N, P, ARITY, F, 0) static const struct Jim_ExprOperator Jim_ExprOperators[] = { OPRINIT("*", 110, 2, JimExprOpBin), @@ -8410,24 +8326,13 @@ static const struct Jim_ExprOperator Jim_ExprOperators[] = { OPRINIT("^", 49, 2, JimExprOpIntBin), OPRINIT("|", 48, 2, JimExprOpIntBin), - OPRINIT_ATTR("&&", 10, 2, NULL, LAZY_OP), - OPRINIT_ATTR(NULL, 10, 2, JimExprOpAndLeft, LAZY_LEFT), - OPRINIT_ATTR(NULL, 10, 2, JimExprOpAndOrRight, LAZY_RIGHT), - - OPRINIT_ATTR("||", 9, 2, NULL, LAZY_OP), - OPRINIT_ATTR(NULL, 9, 2, JimExprOpOrLeft, LAZY_LEFT), - OPRINIT_ATTR(NULL, 9, 2, JimExprOpAndOrRight, LAZY_RIGHT), - - OPRINIT_ATTR("?", 5, 2, JimExprOpNull, LAZY_OP), - OPRINIT_ATTR(NULL, 5, 2, JimExprOpTernaryLeft, LAZY_LEFT), - OPRINIT_ATTR(NULL, 5, 2, JimExprOpNull, LAZY_RIGHT), - - OPRINIT_ATTR(":", 5, 2, JimExprOpNull, LAZY_OP), - OPRINIT_ATTR(NULL, 5, 2, JimExprOpColonLeft, LAZY_LEFT), - OPRINIT_ATTR(NULL, 5, 2, JimExprOpNull, LAZY_RIGHT), + OPRINIT("&&", 10, 2, JimExprOpAnd), + OPRINIT("||", 9, 2, JimExprOpOr), + OPRINIT_ATTR("?", 5, 3, JimExprOpTernary, OP_RIGHT_ASSOC), + OPRINIT_ATTR(":", 5, 3, NULL, OP_RIGHT_ASSOC), /* Precedence is higher than * and / but lower than ! and ~, and right-associative */ - OPRINIT_ATTR("**", 120, 2, JimExprOpBin, RIGHT_ASSOC), + OPRINIT_ATTR("**", 120, 2, JimExprOpBin, OP_RIGHT_ASSOC), OPRINIT("eq", 60, 2, JimExprOpStrBin), OPRINIT("ne", 60, 2, JimExprOpStrBin), @@ -8435,45 +8340,45 @@ static const struct Jim_ExprOperator Jim_ExprOperators[] = { OPRINIT("in", 55, 2, JimExprOpStrBin), OPRINIT("ni", 55, 2, JimExprOpStrBin), - OPRINIT("!", 150, 1, JimExprOpNumUnary), - OPRINIT("~", 150, 1, JimExprOpIntUnary), - OPRINIT(NULL, 150, 1, JimExprOpNumUnary), - OPRINIT(NULL, 150, 1, JimExprOpNumUnary), + OPRINIT_ATTR("!", 150, 1, JimExprOpNumUnary, OP_RIGHT_ASSOC), + OPRINIT_ATTR("~", 150, 1, JimExprOpIntUnary, OP_RIGHT_ASSOC), + OPRINIT_ATTR(" -", 150, 1, JimExprOpNumUnary, OP_RIGHT_ASSOC), + OPRINIT_ATTR(" +", 150, 1, JimExprOpNumUnary, OP_RIGHT_ASSOC), - OPRINIT("int", 200, 1, JimExprOpNumUnary), - OPRINIT("wide", 200, 1, JimExprOpNumUnary), - OPRINIT("abs", 200, 1, JimExprOpNumUnary), - OPRINIT("double", 200, 1, JimExprOpNumUnary), - OPRINIT("round", 200, 1, JimExprOpNumUnary), - OPRINIT("rand", 200, 0, JimExprOpNone), - OPRINIT("srand", 200, 1, JimExprOpIntUnary), + OPRINIT_ATTR("int", 200, 1, JimExprOpNumUnary, OP_FUNC), + OPRINIT_ATTR("wide", 200, 1, JimExprOpNumUnary, OP_FUNC), + OPRINIT_ATTR("abs", 200, 1, JimExprOpNumUnary, OP_FUNC), + OPRINIT_ATTR("double", 200, 1, JimExprOpNumUnary, OP_FUNC), + OPRINIT_ATTR("round", 200, 1, JimExprOpNumUnary, OP_FUNC), + OPRINIT_ATTR("rand", 200, 0, JimExprOpNone, OP_FUNC), + OPRINIT_ATTR("srand", 200, 1, JimExprOpIntUnary, OP_FUNC), #ifdef JIM_MATH_FUNCTIONS - OPRINIT("sin", 200, 1, JimExprOpDoubleUnary), - OPRINIT("cos", 200, 1, JimExprOpDoubleUnary), - OPRINIT("tan", 200, 1, JimExprOpDoubleUnary), - OPRINIT("asin", 200, 1, JimExprOpDoubleUnary), - OPRINIT("acos", 200, 1, JimExprOpDoubleUnary), - OPRINIT("atan", 200, 1, JimExprOpDoubleUnary), - OPRINIT("atan2", 200, 2, JimExprOpBin), - OPRINIT("sinh", 200, 1, JimExprOpDoubleUnary), - OPRINIT("cosh", 200, 1, JimExprOpDoubleUnary), - OPRINIT("tanh", 200, 1, JimExprOpDoubleUnary), - OPRINIT("ceil", 200, 1, JimExprOpDoubleUnary), - OPRINIT("floor", 200, 1, JimExprOpDoubleUnary), - OPRINIT("exp", 200, 1, JimExprOpDoubleUnary), - OPRINIT("log", 200, 1, JimExprOpDoubleUnary), - OPRINIT("log10", 200, 1, JimExprOpDoubleUnary), - OPRINIT("sqrt", 200, 1, JimExprOpDoubleUnary), - OPRINIT("pow", 200, 2, JimExprOpBin), - OPRINIT("hypot", 200, 2, JimExprOpBin), - OPRINIT("fmod", 200, 2, JimExprOpBin), + OPRINIT_ATTR("sin", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("cos", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("tan", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("asin", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("acos", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("atan", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("atan2", 200, 2, JimExprOpBin, OP_FUNC), + OPRINIT_ATTR("sinh", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("cosh", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("tanh", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("ceil", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("floor", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("exp", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("log", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("log10", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("sqrt", 200, 1, JimExprOpDoubleUnary, OP_FUNC), + OPRINIT_ATTR("pow", 200, 2, JimExprOpBin, OP_FUNC), + OPRINIT_ATTR("hypot", 200, 2, JimExprOpBin, OP_FUNC), + OPRINIT_ATTR("fmod", 200, 2, JimExprOpBin, OP_FUNC), #endif }; #undef OPRINIT -#undef OPRINIT_LAZY +#undef OPRINIT_ATTR #define JIM_EXPR_OPERATORS_NUM \ (sizeof(Jim_ExprOperators)/sizeof(struct Jim_ExprOperator)) @@ -8632,31 +8537,40 @@ static int JimParseExprBoolean(struct JimParserCtx *pc) return JIM_ERR; } +static const struct Jim_ExprOperator *JimExprOperatorInfoByOpcode(int opcode) +{ + static Jim_ExprOperator dummy_op; + if (opcode < JIM_TT_EXPR_OP) { + return &dummy_op; + } + return &Jim_ExprOperators[opcode - JIM_TT_EXPR_OP]; +} + static int JimParseExprOperator(struct JimParserCtx *pc) { int i; - int bestIdx = -1, bestLen = 0; + const struct Jim_ExprOperator *bestOp = NULL; + int bestLen = 0; /* Try to get the longest match. */ for (i = 0; i < (signed)JIM_EXPR_OPERATORS_NUM; i++) { - const char * const opname = Jim_ExprOperators[i].name; - const int oplen = Jim_ExprOperators[i].namelen; + const struct Jim_ExprOperator *op = &Jim_ExprOperators[i]; - if (opname == NULL || opname[0] != pc->p[0]) { + if (op->name[0] != pc->p[0]) { continue; } - if (oplen > bestLen && strncmp(opname, pc->p, oplen) == 0) { - bestIdx = i + JIM_TT_EXPR_OP; - bestLen = oplen; + if (op->namelen > bestLen && strncmp(op->name, pc->p, op->namelen) == 0) { + bestOp = op; + bestLen = op->namelen; } } - if (bestIdx == -1) { + if (bestOp == NULL) { return JIM_ERR; } /* Validate paretheses around function arguments */ - if (bestIdx >= JIM_EXPROP_FUNC_FIRST) { + if (bestOp->attr & OP_FUNC) { const char *p = pc->p + bestLen; int len = pc->len - bestLen; @@ -8672,19 +8586,10 @@ static int JimParseExprOperator(struct JimParserCtx *pc) pc->p += bestLen; pc->len -= bestLen; - pc->tt = bestIdx; + pc->tt = (bestOp - Jim_ExprOperators) + JIM_TT_EXPR_OP; return JIM_OK; } -static const struct Jim_ExprOperator *JimExprOperatorInfoByOpcode(int opcode) -{ - static Jim_ExprOperator dummy_op; - if (opcode < JIM_TT_EXPR_OP) { - return &dummy_op; - } - return &Jim_ExprOperators[opcode - JIM_TT_EXPR_OP]; -} - const char *jim_tt_name(int type) { static const char * const tt_names[JIM_TT_EXPR_OP] = @@ -8726,35 +8631,42 @@ static const Jim_ObjType exprObjType = { JIM_TYPE_REFERENCES, }; -/* Expr bytecode structure */ -typedef struct ExprByteCode +/* expr tree structure */ +struct ExprTree { - ScriptToken *token; /* Tokens array. */ - int len; /* Length as number of tokens. */ + struct JimExprNode *expr; /* The first operator or term */ + struct JimExprNode *nodes; /* Storage of all nodes in the tree */ + int len; /* Number of nodes in use */ int inUse; /* Used for sharing. */ -} ExprByteCode; +}; -static void ExprFreeByteCode(Jim_Interp *interp, ExprByteCode * expr) +static void ExprTreeFreeNodes(Jim_Interp *interp, struct JimExprNode *nodes, int num) { int i; - - for (i = 0; i < expr->len; i++) { - Jim_DecrRefCount(interp, expr->token[i].objPtr); + for (i = 0; i < num; i++) { + if (nodes[i].objPtr) { + Jim_DecrRefCount(interp, nodes[i].objPtr); + } } - Jim_Free(expr->token); + Jim_Free(nodes); +} + +static void ExprTreeFree(Jim_Interp *interp, struct ExprTree *expr) +{ + ExprTreeFreeNodes(interp, expr->nodes, expr->len); Jim_Free(expr); } static void FreeExprInternalRep(Jim_Interp *interp, Jim_Obj *objPtr) { - ExprByteCode *expr = (void *)objPtr->internalRep.ptr; + struct ExprTree *expr = (void *)objPtr->internalRep.ptr; if (expr) { if (--expr->inUse != 0) { return; } - ExprFreeByteCode(interp, expr); + ExprTreeFree(interp, expr); } } @@ -8767,385 +8679,153 @@ static void DupExprInternalRep(Jim_Interp *interp, Jim_Obj *srcPtr, Jim_Obj *dup dupPtr->typePtr = NULL; } -/* Check if an expr program looks correct - * Sets an error result on invalid - */ -static int ExprCheckCorrectness(Jim_Interp *interp, Jim_Obj *exprObjPtr, ExprByteCode * expr) +struct ExprBuilder { + int parencount; /* count of outstanding parentheses */ + int level; /* recursion depth */ + ParseToken *token; /* The current token */ + ParseToken *first_token; /* The first token */ + Jim_Stack stack; /* stack of pending terms */ + Jim_Obj *exprObjPtr; /* the original expression */ + Jim_Obj *fileNameObj; /* filename of the original expression */ + struct JimExprNode *nodes; /* storage for all nodes */ + struct JimExprNode *next; /* storage for the next node */ +}; + +#ifdef DEBUG_SHOW_EXPR +static void JimShowExprNode(struct JimExprNode *node, int level) { int i; - int stacklen = 0; - int ternary = 0; - int lasttt = JIM_TT_NONE; - const char *errmsg; - - /* Try to check if there are stack underflows, - * and make sure at the end of the program there is - * a single result on the stack. */ - for (i = 0; i < expr->len; i++) { - ScriptToken *t = &expr->token[i]; - const struct Jim_ExprOperator *op = JimExprOperatorInfoByOpcode(t->type); - lasttt = t->type; - - stacklen -= op->arity; - - if (stacklen < 0) { - break; - } - if (t->type == JIM_EXPROP_TERNARY || t->type == JIM_EXPROP_TERNARY_LEFT) { - ternary++; - } - else if (t->type == JIM_EXPROP_COLON || t->type == JIM_EXPROP_COLON_LEFT) { - if (--ternary < 0) { - /* got : without preceding ? */ - stacklen = 1; - break; - } - } - - /* All operations and operands add one to the stack */ - stacklen++; - } - if (stacklen == 1 && ternary == 0) { - return JIM_OK; + for (i = 0; i < level; i++) { + printf(" "); } - - if (stacklen <= 0) { - /* Too few args */ - if (lasttt >= JIM_EXPROP_FUNC_FIRST) { - errmsg = "too few arguments for math function"; - Jim_SetResultString(interp, "too few arguments for math function", -1); - } else { - errmsg = "premature end of expression"; + if (TOKEN_IS_EXPR_OP(node->type)) { + printf("%s\n", jim_tt_name(node->type)); + if (node->left) { + JimShowExprNode(node->left, level + 1); } - } - else if (stacklen > 1) { - if (lasttt >= JIM_EXPROP_FUNC_FIRST) { - errmsg = "too many arguments for math function"; - } else { - errmsg = "extra tokens at end of expression"; + if (node->right) { + JimShowExprNode(node->right, level + 1); + } + if (node->ternary) { + JimShowExprNode(node->ternary, level + 1); } } else { - errmsg = "invalid ternary expression"; + printf("[%s] %s\n", jim_tt_name(node->type), Jim_String(node->objPtr)); } - Jim_SetResultFormatted(interp, "syntax error in expression \"%#s\": %s", exprObjPtr, errmsg); - return JIM_ERR; } +#endif -/* This procedure converts every occurrence of || and && opereators - * in lazy unary versions. - * - * a b || is converted into: - * - * a |L b |R - * - * a b && is converted into: +#define EXPR_UNTIL_CLOSE 0x0001 +#define EXPR_FUNC_ARGS 0x0002 +#define EXPR_TERNARY 0x0004 + +/** + * Parse the subexpression at builder->token and return with the node on the stack. + * builder->token is advanced to the next unconsumed token. + * Returns JIM_OK if OK or JIM_ERR on error and leaves a message in the interpreter result. * - * a &L b &R + * 'precedence' is the precedence of the current operator. Tokens are consumed until an operator + * with an equal or lower precedence is reached (or strictly lower if right associative). * - * "|L" checks if 'a' is true: - * 1) if it is true pushes 1 and skips instructions to reach - * the opcode just after |R. - * 2) if it is false does nothing. - * "|R" checks if 'b' is true: - * 1) if it is true pushes 1, otherwise pushes 0. + * If EXPR_UNTIL_CLOSE is set, the subexpression extends up to and including the next close parenthesis. + * If EXPR_FUNC_ARGS is set, multiple subexpressions (terms) are expected separated by comma + * If EXPR_TERNARY is set, two subexpressions (terms) are expected separated by colon * - * "&L" checks if 'a' is true: - * 1) if it is true does nothing. - * 2) If it is false pushes 0 and skips instructions to reach - * the opcode just after &R - * "&R" checks if 'a' is true: - * if it is true pushes 1, otherwise pushes 0. + * 'exp_numterms' indicates how many terms are expected. Normally this is 1, but may be more for EXPR_FUNC_ARGS and EXPR_TERNARY. */ -static int ExprAddLazyOperator(Jim_Interp *interp, ExprByteCode * expr, ParseToken *t) +static int ExprTreeBuildTree(Jim_Interp *interp, struct ExprBuilder *builder, int precedence, int flags, int exp_numterms) { - int i; + int rc; + struct JimExprNode *node; + /* Calculate the stack length expected after pushing the number of expected terms */ + int exp_stacklen = builder->stack.len + exp_numterms; - int leftindex, arity, offset; + builder->level++; - /* Search for the end of the first operator */ - leftindex = expr->len - 1; + while (builder->token->type != JIM_TT_EOL) { + ParseToken *t = builder->token++; + int prevtt; - arity = 1; - while (arity) { - if (leftindex < 0) { - return JIM_ERR; + if (t == builder->first_token) { + prevtt = JIM_TT_NONE; } - ScriptToken *tt = &expr->token[leftindex]; - - if (tt->type >= JIM_TT_EXPR_OP) { - arity += JimExprOperatorInfoByOpcode(tt->type)->arity; + else { + prevtt = t[-1].type; } - arity--; - leftindex--; - } - leftindex++; - - /* Move them up */ - memmove(&expr->token[leftindex + 2], &expr->token[leftindex], - sizeof(*expr->token) * (expr->len - leftindex)); - expr->len += 2; - offset = (expr->len - leftindex) - 1; - - /* Now we rely on the fact that the left and right version have opcodes - * 1 and 2 after the main opcode respectively - */ - expr->token[leftindex + 1].type = t->type + 1; - expr->token[leftindex + 1].objPtr = interp->emptyObj; - - expr->token[leftindex].type = JIM_TT_EXPR_INT; - expr->token[leftindex].objPtr = Jim_NewIntObj(interp, offset); - /* Now add the 'R' operator */ - expr->token[expr->len].objPtr = interp->emptyObj; - expr->token[expr->len].type = t->type + 2; - expr->len++; - - /* Do we need to adjust the skip count for any &L, |L, ?L or :L in the left operand? */ - for (i = leftindex - 1; i > 0; i--) { - const struct Jim_ExprOperator *op = JimExprOperatorInfoByOpcode(expr->token[i].type); - if (op->lazy == LAZY_LEFT) { - if (JimWideValue(expr->token[i - 1].objPtr) + i - 1 >= leftindex) { - JimWideValue(expr->token[i - 1].objPtr) += 2; + if (t->type == JIM_TT_SUBEXPR_START) { + if (builder->stack.len == exp_stacklen) { + Jim_SetResultFormatted(interp, "unexpected open parenthesis in expression: \"%#s\"", builder->exprObjPtr); + return JIM_ERR; } - } - } - return JIM_OK; -} - -static int ExprAddOperator(Jim_Interp *interp, ExprByteCode * expr, ParseToken *t) -{ - struct ScriptToken *token = &expr->token[expr->len]; - const struct Jim_ExprOperator *op = JimExprOperatorInfoByOpcode(t->type); - - if (op->lazy == LAZY_OP) { - if (ExprAddLazyOperator(interp, expr, t) != JIM_OK) { - Jim_SetResultFormatted(interp, "Expression has bad operands to %s", op->name); - return JIM_ERR; - } - } - else { - token->objPtr = interp->emptyObj; - token->type = t->type; - expr->len++; - } - return JIM_OK; -} - -/** - * Returns the index of the COLON_LEFT to the left of 'right_index' - * taking into account nesting. - * - * The expression *must* be well formed, thus a COLON_LEFT will always be found. - */ -static int ExprTernaryGetColonLeftIndex(ExprByteCode *expr, int right_index) -{ - int ternary_count = 1; - - right_index--; - - while (right_index > 1) { - if (expr->token[right_index].type == JIM_EXPROP_TERNARY_LEFT) { - ternary_count--; - } - else if (expr->token[right_index].type == JIM_EXPROP_COLON_RIGHT) { - ternary_count++; - } - else if (expr->token[right_index].type == JIM_EXPROP_COLON_LEFT && ternary_count == 1) { - return right_index; - } - right_index--; - } - - /*notreached*/ - return -1; -} - -/** - * Find the left/right indices for the ternary expression to the left of 'right_index'. - * - * Returns 1 if found, and fills in *prev_right_index and *prev_left_index. - * Otherwise returns 0. - */ -static int ExprTernaryGetMoveIndices(ExprByteCode *expr, int right_index, int *prev_right_index, int *prev_left_index) -{ - int i = right_index - 1; - int ternary_count = 1; - - while (i > 1) { - if (expr->token[i].type == JIM_EXPROP_TERNARY_LEFT) { - if (--ternary_count == 0 && expr->token[i - 2].type == JIM_EXPROP_COLON_RIGHT) { - *prev_right_index = i - 2; - *prev_left_index = ExprTernaryGetColonLeftIndex(expr, *prev_right_index); - return 1; + builder->parencount++; + rc = ExprTreeBuildTree(interp, builder, 0, EXPR_UNTIL_CLOSE, 1); + if (rc != JIM_OK) { + return rc; } + /* A complete subexpression is on the stack */ } - else if (expr->token[i].type == JIM_EXPROP_COLON_RIGHT) { - if (ternary_count == 0) { - return 0; + else if (t->type == JIM_TT_SUBEXPR_END) { + if (!(flags & EXPR_UNTIL_CLOSE)) { + if (builder->stack.len == exp_stacklen && builder->level > 1) { + builder->token--; + builder->level--; + return JIM_OK; + } + Jim_SetResultFormatted(interp, "unexpected closing parenthesis in expression: \"%#s\"", builder->exprObjPtr); + return JIM_ERR; + } + builder->parencount--; + if (builder->stack.len == exp_stacklen) { + /* Return with the expected number of subexpressions on the stack */ + break; } - ternary_count++; - } - i--; - } - return 0; -} - -/* -* ExprTernaryReorderExpression description -* ======================================== -* -* ?: is right-to-left associative which doesn't work with the stack-based -* expression engine. The fix is to reorder the bytecode. -* -* The expression: -* -* expr 1?2:0?3:4 -* -* Has initial bytecode: -* -* '1' '2' (40=TERNARY_LEFT) '2' (41=TERNARY_RIGHT) '2' (43=COLON_LEFT) '0' (44=COLON_RIGHT) -* '2' (40=TERNARY_LEFT) '3' (41=TERNARY_RIGHT) '2' (43=COLON_LEFT) '4' (44=COLON_RIGHT) -* -* The fix involves simulating this expression instead: -* -* expr 1?2:(0?3:4) -* -* With the following bytecode: -* -* '1' '2' (40=TERNARY_LEFT) '2' (41=TERNARY_RIGHT) '10' (43=COLON_LEFT) '0' '2' (40=TERNARY_LEFT) -* '3' (41=TERNARY_RIGHT) '2' (43=COLON_LEFT) '4' (44=COLON_RIGHT) (44=COLON_RIGHT) -* -* i.e. The token COLON_RIGHT at index 8 is moved towards the end of the stack, all tokens above 8 -* are shifted down and the skip count of the token JIM_EXPROP_COLON_LEFT at index 5 is -* incremented by the amount tokens shifted down. The token JIM_EXPROP_COLON_RIGHT that is moved -* is identified as immediately preceeding a token JIM_EXPROP_TERNARY_LEFT -* -* ExprTernaryReorderExpression works thus as follows : -* - start from the end of the stack -* - while walking towards the beginning of the stack -* if token=JIM_EXPROP_COLON_RIGHT then -* find the associated token JIM_EXPROP_TERNARY_LEFT, which allows to -* find the associated token previous(JIM_EXPROP_COLON_RIGHT) -* find the associated token previous(JIM_EXPROP_LEFT_RIGHT) -* if all found then -* perform the rotation -* update the skip count of the token previous(JIM_EXPROP_LEFT_RIGHT) -* end if -* end if -* -* Note: care has to be taken for nested ternary constructs!!! -*/ -static int ExprTernaryReorderExpression(Jim_Interp *interp, ExprByteCode *expr) -{ - int i; - - for (i = expr->len - 1; i > 1; i--) { - int prev_right_index; - int prev_left_index; - int j; - ScriptToken tmp; - - if (expr->token[i].type != JIM_EXPROP_COLON_RIGHT) { - continue; - } - - /* COLON_RIGHT found: get the indexes needed to move the tokens in the stack (if any) */ - if (ExprTernaryGetMoveIndices(expr, i, &prev_right_index, &prev_left_index) == 0) { - continue; } - if (prev_left_index < 0) { - return -1; - } - - /* - ** rotate tokens down - ** - ** +-> [i] : JIM_EXPROP_COLON_RIGHT - ** | | | - ** | V V - ** | [...] : ... - ** | | | - ** | V V - ** | [...] : ... - ** | | | - ** | V V - ** +- [prev_right_index] : JIM_EXPROP_COLON_RIGHT - */ - tmp = expr->token[prev_right_index]; - for (j = prev_right_index; j < i; j++) { - expr->token[j] = expr->token[j + 1]; - } - expr->token[i] = tmp; - - /* Increment the 'skip' count associated to the previous JIM_EXPROP_COLON_LEFT token - * - * This is 'colon left increment' = i - prev_right_index - * - * [prev_left_index] : JIM_EXPROP_LEFT_RIGHT - * [prev_left_index-1] : skip_count - * - */ - JimWideValue(expr->token[prev_left_index-1].objPtr) += (i - prev_right_index); - - /* Adjust for i-- in the loop */ - i++; - } - return 0; -} - -static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList *tokenlist, Jim_Obj *exprObjPtr, Jim_Obj *fileNameObj) -{ - Jim_Stack stack; - ExprByteCode *expr; - int ok = 1; - int i; - int prevtt = JIM_TT_NONE; - int have_ternary = 0; - - /* -1 for EOL */ - int count = tokenlist->count - 1; - - expr = Jim_Alloc(sizeof(*expr)); - expr->inUse = 1; - expr->len = 0; - - Jim_InitStack(&stack); - - /* Need extra bytecodes for lazy operators. - * Also check for the ternary operator - */ - for (i = 0; i < tokenlist->count; i++) { - ParseToken *t = &tokenlist->list[i]; - const struct Jim_ExprOperator *op = JimExprOperatorInfoByOpcode(t->type); - - if (op->lazy == LAZY_OP) { - count += 2; - /* Ternary is a lazy op but also needs reordering */ - if (t->type == JIM_EXPROP_TERNARY) { - have_ternary = 1; + else if (t->type == JIM_TT_SUBEXPR_COMMA) { + if (!(flags & EXPR_FUNC_ARGS)) { + if (builder->stack.len == exp_stacklen) { + /* handle the comma back at the parent level */ + builder->token--; + builder->level--; + return JIM_OK; + } + Jim_SetResultFormatted(interp, "unexpected comma in expression: \"%#s\"", builder->exprObjPtr); + return JIM_ERR; } + else { + /* If we see more terms than expected, it is an error */ + if (builder->stack.len > exp_stacklen) { + Jim_SetResultFormatted(interp, "too many arguments to math function"); + return JIM_ERR; + } + } + /* just go onto the next arg */ } - } - - expr->token = Jim_Alloc(sizeof(ScriptToken) * count); - - for (i = 0; i < tokenlist->count && ok; i++) { - ParseToken *t = &tokenlist->list[i]; - - /* Next token will be stored here */ - struct ScriptToken *token = &expr->token[expr->len]; - - if (t->type == JIM_TT_EOL) { - break; + else if (t->type == JIM_EXPROP_COLON) { + if (!(flags & EXPR_TERNARY)) { + if (builder->level != 1) { + /* handle the comma back at the parent level */ + builder->token--; + builder->level--; + return JIM_OK; + } + Jim_SetResultFormatted(interp, ": without ? in expression: \"%#s\"", builder->exprObjPtr); + return JIM_ERR; + } + if (builder->stack.len == exp_stacklen) { + /* handle the comma back at the parent level */ + builder->token--; + builder->level--; + return JIM_OK; + } + /* just go onto the next term */ } - - if (TOKEN_IS_EXPR_OP(t->type)) { + else if (TOKEN_IS_EXPR_OP(t->type)) { const struct Jim_ExprOperator *op; - ParseToken *tt; /* Convert -/+ to unary minus or unary plus if necessary */ - if (prevtt == JIM_TT_NONE || prevtt == JIM_TT_SUBEXPR_START || prevtt == JIM_TT_SUBEXPR_COMMA || prevtt >= JIM_TT_EXPR_OP) { + if (TOKEN_IS_EXPR_OP(prevtt) || TOKEN_IS_EXPR_START(prevtt)) { if (t->type == JIM_EXPROP_SUB) { t->type = JIM_EXPROP_UNARYMINUS; } @@ -9156,68 +8836,72 @@ static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList op = JimExprOperatorInfoByOpcode(t->type); - /* Handle precedence */ - while ((tt = Jim_StackPeek(&stack)) != NULL) { - const struct Jim_ExprOperator *tt_op = - JimExprOperatorInfoByOpcode(tt->type); - - /* Note that right-to-left associativity of ?: operator is handled later. - */ + if (op->precedence < precedence || (!(op->attr & OP_RIGHT_ASSOC) && op->precedence == precedence)) { + /* next op is lower precedence, or equal and left associative, so done here */ + builder->token--; + break; + } - if (op->arity != 1 && tt_op->precedence >= op->precedence) { - /* Don't reduce if right associative with equal precedence? */ - if (tt_op->precedence == op->precedence && tt_op->lazy == RIGHT_ASSOC) { - break; - } - if (ExprAddOperator(interp, expr, tt) != JIM_OK) { - ok = 0; - goto err; - } - Jim_StackPop(&stack); + if (op->attr & OP_FUNC) { + if (builder->token->type != JIM_TT_SUBEXPR_START) { + Jim_SetResultString(interp, "missing arguments for math function", -1); + return JIM_ERR; } - else { - break; + builder->token++; + if (op->arity == 0) { + if (builder->token->type != JIM_TT_SUBEXPR_END) { + Jim_SetResultString(interp, "too many arguments for math function", -1); + return JIM_ERR; + } + builder->token++; + goto noargs; } + builder->parencount++; + + /* This will push left and return right */ + rc = ExprTreeBuildTree(interp, builder, 0, EXPR_FUNC_ARGS | EXPR_UNTIL_CLOSE, op->arity); + } + else if (t->type == JIM_EXPROP_TERNARY) { + /* Collect the two arguments to the ternary operator */ + rc = ExprTreeBuildTree(interp, builder, op->precedence, EXPR_TERNARY, 2); + } + else { + /* Recursively handle everything on the right until we see a precendence <= op->precedence or == and right associative + * and push that on the term stack + */ + rc = ExprTreeBuildTree(interp, builder, op->precedence, 0, 1); } - Jim_StackPush(&stack, t); - } - else if (t->type == JIM_TT_SUBEXPR_START) { - Jim_StackPush(&stack, t); - } - else if (t->type == JIM_TT_SUBEXPR_END || t->type == JIM_TT_SUBEXPR_COMMA) { - /* Reduce the expression back to the previous ( or , */ - ok = 0; - while (Jim_StackLen(&stack)) { - ParseToken *tt = Jim_StackPop(&stack); - if (tt->type == JIM_TT_SUBEXPR_START || tt->type == JIM_TT_SUBEXPR_COMMA) { - if (t->type == JIM_TT_SUBEXPR_COMMA) { - /* Need to push back the previous START or COMMA in the case of comma */ - Jim_StackPush(&stack, tt); - } - ok = 1; - break; - } - if (ExprAddOperator(interp, expr, tt) != JIM_OK) { - goto err; - } + if (rc != JIM_OK) { + return rc; } - if (!ok) { - Jim_SetResultFormatted(interp, "Unexpected close parenthesis in expression: \"%#s\"", exprObjPtr); - goto err; + +noargs: + node = builder->next++; + node->type = t->type; + + if (op->arity >= 3) { + node->ternary = Jim_StackPop(&builder->stack); + } + if (op->arity >= 2) { + node->right = Jim_StackPop(&builder->stack); } + if (op->arity >= 1) { + node->left = Jim_StackPop(&builder->stack); + } + + /* Now push the node */ + Jim_StackPush(&builder->stack, node); } else { Jim_Obj *objPtr = NULL; /* This is a simple non-operator term, so create and push the appropriate object */ - token->type = t->type; /* Two consecutive terms without an operator is invalid */ if (!TOKEN_IS_EXPR_START(prevtt) && !TOKEN_IS_EXPR_OP(prevtt)) { - Jim_SetResultFormatted(interp, "missing operator in expression: \"%#s\"", exprObjPtr); - ok = 0; - goto err; + Jim_SetResultFormatted(interp, "missing operator in expression: \"%#s\"", builder->exprObjPtr); + return JIM_ERR; } /* Immediately create a double or int object? */ @@ -9236,69 +8920,105 @@ static ExprByteCode *ExprCreateByteCode(Jim_Interp *interp, const ParseTokenList } } - if (objPtr) { - token->objPtr = objPtr; - } - else { + if (!objPtr) { /* Everything else is stored a simple string term */ - token->objPtr = Jim_NewStringObj(interp, t->token, t->len); + objPtr = Jim_NewStringObj(interp, t->token, t->len); if (t->type == JIM_TT_CMD) { /* Only commands need source info */ - JimSetSourceInfo(interp, token->objPtr, fileNameObj, t->line); + JimSetSourceInfo(interp, objPtr, builder->fileNameObj, t->line); } } - expr->len++; + + /* Now push a term node */ + node = builder->next++; + node->objPtr = objPtr; + Jim_IncrRefCount(node->objPtr); + node->type = t->type; + Jim_StackPush(&builder->stack, node); } - prevtt = t->type; } - /* Reduce any remaining subexpr */ - while (Jim_StackLen(&stack)) { - ParseToken *tt = Jim_StackPop(&stack); + if (builder->stack.len == exp_stacklen) { + builder->level--; + return JIM_OK; + } - if (tt->type == JIM_TT_SUBEXPR_START) { - ok = 0; - Jim_SetResultString(interp, "Missing close parenthesis", -1); - goto err; + if ((flags & EXPR_FUNC_ARGS)) { + Jim_SetResultFormatted(interp, "too %s arguments for math function", (builder->stack.len < exp_stacklen) ? "few" : "many"); + } + else { + if (builder->stack.len < exp_stacklen) { + if (builder->level == 0) { + Jim_SetResultFormatted(interp, "empty expression"); + } + else { + Jim_SetResultFormatted(interp, "syntax error in expression \"%#s\": premature end of expression", builder->exprObjPtr); + } } - if (ExprAddOperator(interp, expr, tt) != JIM_OK) { - ok = 0; - goto err; + else { + Jim_SetResultFormatted(interp, "extra terms after expression"); } } - if (have_ternary) { - if (ExprTernaryReorderExpression(interp, expr) != 0) { - ok = 0; - Jim_SetResultString(interp, "Invalid ternary expression", -1); + return JIM_ERR; +} + +static struct ExprTree *ExprTreeCreateTree(Jim_Interp *interp, const ParseTokenList *tokenlist, Jim_Obj *exprObjPtr, Jim_Obj *fileNameObj) +{ + struct ExprTree *expr; + struct ExprBuilder builder; + int rc; + struct JimExprNode *top; + + builder.parencount = 0; + builder.level = 0; + builder.token = builder.first_token = tokenlist->list; + builder.exprObjPtr = exprObjPtr; + builder.fileNameObj = fileNameObj; + /* The bytecode will never produce more nodes than there are tokens - 1 (for EOL)*/ + builder.nodes = malloc(sizeof(struct JimExprNode) * (tokenlist->count - 1)); + memset(builder.nodes, 0, sizeof(struct JimExprNode) * (tokenlist->count - 1)); + builder.next = builder.nodes; + Jim_InitStack(&builder.stack); + + rc = ExprTreeBuildTree(interp, &builder, 0, 0, 1); + + if (rc == JIM_OK) { + top = Jim_StackPop(&builder.stack); + + if (builder.parencount) { + Jim_SetResultString(interp, "missing close parenthesis", -1); + rc = JIM_ERR; } } - err: /* Free the stack used for the compilation. */ - Jim_FreeStack(&stack); - - for (i = 0; i < expr->len; i++) { - Jim_IncrRefCount(expr->token[i].objPtr); - } + Jim_FreeStack(&builder.stack); - if (!ok) { - ExprFreeByteCode(interp, expr); + if (rc != JIM_OK) { + ExprTreeFreeNodes(interp, builder.nodes, builder.next - builder.nodes); return NULL; } + expr = Jim_Alloc(sizeof(*expr)); + expr->inUse = 1; + expr->expr = top; + expr->nodes = builder.nodes; + expr->len = builder.next - builder.nodes; + + assert(expr->len <= tokenlist->count - 1); + return expr; } - /* This method takes the string representation of an expression - * and generates a program for the Expr's stack-based VM. */ + * and generates a program for the expr engine */ static int SetExprFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) { int exprTextLen; const char *exprText; struct JimParserCtx parser; - struct ExprByteCode *expr; + struct ExprTree *expr; ParseTokenList tokenlist; int line; Jim_Obj *fileNameObj; @@ -9351,7 +9071,7 @@ static int SetExprFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) } /* Now create the expression bytecode from the tokenlist */ - expr = ExprCreateByteCode(interp, &tokenlist, objPtr, fileNameObj); + expr = ExprTreeCreateTree(interp, &tokenlist, objPtr, fileNameObj); /* No longer need the token list */ ScriptTokenListFree(&tokenlist); @@ -9361,26 +9081,10 @@ static int SetExprFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) } #ifdef DEBUG_SHOW_EXPR - { - int i; - - printf("==== Expr ====\n"); - for (i = 0; i < expr->len; i++) { - ScriptToken *t = &expr->token[i]; - - printf("[%2d] %s '%s'\n", i, jim_tt_name(t->type), Jim_String(t->objPtr)); - } - } + printf("==== Expr ====\n"); + JimShowExprNode(expr->expr, 0); #endif - /* Check program correctness. */ - if (ExprCheckCorrectness(interp, objPtr, expr) != JIM_OK) { - /* ExprCheckCorrectness set an error in this case */ - ExprFreeByteCode(interp, expr); - expr = NULL; - goto err; - } - rc = JIM_OK; err: @@ -9392,25 +9096,25 @@ static int SetExprFromAny(Jim_Interp *interp, struct Jim_Obj *objPtr) return rc; } -static ExprByteCode *JimGetExpression(Jim_Interp *interp, Jim_Obj *objPtr) +static struct ExprTree *JimGetExpression(Jim_Interp *interp, Jim_Obj *objPtr) { if (objPtr->typePtr != &exprObjType) { if (SetExprFromAny(interp, objPtr) != JIM_OK) { return NULL; } } - return (ExprByteCode *) Jim_GetIntRepPtr(objPtr); + return (struct ExprTree *) Jim_GetIntRepPtr(objPtr); } #ifdef JIM_OPTIMIZATION -static Jim_Obj *JimExprIntValOrVar(Jim_Interp *interp, const ScriptToken *token) -{ - if (token->type == JIM_TT_EXPR_INT) - return token->objPtr; - else if (token->type == JIM_TT_VAR) - return Jim_GetVariable(interp, token->objPtr, JIM_NONE); - else if (token->type == JIM_TT_DICTSUGAR) - return JimExpandDictSugar(interp, token->objPtr); +static Jim_Obj *JimExprIntValOrVar(Jim_Interp *interp, struct JimExprNode *node) +{ + if (node->type == JIM_TT_EXPR_INT) + return node->objPtr; + else if (node->type == JIM_TT_VAR) + return Jim_GetVariable(interp, node->objPtr, JIM_NONE); + else if (node->type == JIM_TT_DICTSUGAR) + return JimExpandDictSugar(interp, node->objPtr); else return NULL; } @@ -9418,11 +9122,11 @@ static Jim_Obj *JimExprIntValOrVar(Jim_Interp *interp, const ScriptToken *token) /* ----------------------------------------------------------------------------- * Expressions evaluation. - * Jim uses a specialized stack-based virtual machine for expressions, + * Jim uses a recursive evaluation engine for expressions, * that takes advantage of the fact that expr's operators * can't be redefined. * - * Jim_EvalExpression() uses the bytecode compiled by + * Jim_EvalExpression() uses the expression tree compiled by * SetExprFromAny() method of the "expression" object. * * On success a Tcl Object containing the result of the evaluation @@ -9431,15 +9135,80 @@ static Jim_Obj *JimExprIntValOrVar(Jim_Interp *interp, const ScriptToken *token) * On error the function returns a retcode != to JIM_OK and set a suitable * error on the interp. * ---------------------------------------------------------------------------*/ -#define JIM_EE_STATICSTACK_LEN 10 -int Jim_EvalExpression(Jim_Interp *interp, Jim_Obj *exprObjPtr, Jim_Obj **exprResultPtrPtr) +static int JimExprEvalTermNode(Jim_Interp *interp, struct JimExprNode *node) { - ExprByteCode *expr; - Jim_Obj *staticStack[JIM_EE_STATICSTACK_LEN]; - int i; + if (TOKEN_IS_EXPR_OP(node->type)) { + const struct Jim_ExprOperator *op = JimExprOperatorInfoByOpcode(node->type); + return op->funcop(interp, node); + } + else { + Jim_Obj *objPtr; + + /* A term */ + switch (node->type) { + case JIM_TT_EXPR_INT: + case JIM_TT_EXPR_DOUBLE: + case JIM_TT_EXPR_BOOLEAN: + case JIM_TT_STR: + Jim_SetResult(interp, node->objPtr); + return JIM_OK; + + case JIM_TT_VAR: + objPtr = Jim_GetVariable(interp, node->objPtr, JIM_ERRMSG); + if (objPtr) { + Jim_SetResult(interp, objPtr); + return JIM_OK; + } + return JIM_ERR; + + case JIM_TT_DICTSUGAR: + objPtr = JimExpandDictSugar(interp, node->objPtr); + if (objPtr) { + Jim_SetResult(interp, objPtr); + return JIM_OK; + } + return JIM_ERR; + + case JIM_TT_ESC: + if (Jim_SubstObj(interp, node->objPtr, &objPtr, JIM_NONE) == JIM_OK) { + Jim_SetResult(interp, objPtr); + return JIM_OK; + } + return JIM_ERR; + + case JIM_TT_CMD: + return Jim_EvalObj(interp, node->objPtr); + + default: + /* Should never get here */ + return JIM_ERR; + } + } +} + +static Jim_Obj *JimExprGetTerm(Jim_Interp *interp, struct JimExprNode *node) +{ + if (JimExprEvalTermNode(interp, node) == JIM_OK) { + Jim_Obj *objPtr = Jim_GetResult(interp); + Jim_IncrRefCount(objPtr); + return objPtr; + } + return NULL; +} + +static int JimExprGetTermBoolean(Jim_Interp *interp, struct JimExprNode *node) +{ + if (JimExprEvalTermNode(interp, node) == JIM_OK) { + return ExprBool(interp, Jim_GetResult(interp)); + } + return -1; +} + +int Jim_EvalExpression(Jim_Interp *interp, Jim_Obj *exprObjPtr) +{ + struct ExprTree *expr; int retcode = JIM_OK; - struct JimExprState e; expr = JimGetExpression(interp, exprObjPtr); if (!expr) { @@ -9467,35 +9236,33 @@ int Jim_EvalExpression(Jim_Interp *interp, Jim_Obj *exprObjPtr, Jim_Obj **exprRe switch (expr->len) { case 1: - objPtr = JimExprIntValOrVar(interp, &expr->token[0]); + objPtr = JimExprIntValOrVar(interp, expr->expr); if (objPtr) { - Jim_IncrRefCount(objPtr); - *exprResultPtrPtr = objPtr; + Jim_SetResult(interp, objPtr); return JIM_OK; } break; case 2: - if (expr->token[1].type == JIM_EXPROP_NOT) { - objPtr = JimExprIntValOrVar(interp, &expr->token[0]); + if (expr->expr->type == JIM_EXPROP_NOT) { + objPtr = JimExprIntValOrVar(interp, expr->expr->left); if (objPtr && JimIsWide(objPtr)) { - *exprResultPtrPtr = JimWideValue(objPtr) ? interp->falseObj : interp->trueObj; - Jim_IncrRefCount(*exprResultPtrPtr); + Jim_SetResult(interp, JimWideValue(objPtr) ? interp->falseObj : interp->trueObj); return JIM_OK; } } break; case 3: - objPtr = JimExprIntValOrVar(interp, &expr->token[0]); + objPtr = JimExprIntValOrVar(interp, expr->expr->left); if (objPtr && JimIsWide(objPtr)) { - Jim_Obj *objPtr2 = JimExprIntValOrVar(interp, &expr->token[1]); + Jim_Obj *objPtr2 = JimExprIntValOrVar(interp, expr->expr->right); if (objPtr2 && JimIsWide(objPtr2)) { jim_wide wideValueA = JimWideValue(objPtr); jim_wide wideValueB = JimWideValue(objPtr2); int cmpRes; - switch (expr->token[2].type) { + switch (expr->expr->type) { case JIM_EXPROP_LT: cmpRes = wideValueA < wideValueB; break; @@ -9517,8 +9284,7 @@ int Jim_EvalExpression(Jim_Interp *interp, Jim_Obj *exprObjPtr, Jim_Obj **exprRe default: goto noopt; } - *exprResultPtrPtr = cmpRes ? interp->trueObj : interp->falseObj; - Jim_IncrRefCount(*exprResultPtrPtr); + Jim_SetResult(interp, cmpRes ? interp->trueObj : interp->falseObj); return JIM_OK; } } @@ -9528,105 +9294,25 @@ int Jim_EvalExpression(Jim_Interp *interp, Jim_Obj *exprObjPtr, Jim_Obj **exprRe noopt: #endif - /* In order to avoid that the internal repr gets freed due to + /* In order to avoid the internal repr being freed due to * shimmering of the exprObjPtr's object, we make the internal rep * shared. */ expr->inUse++; - /* The stack-based expr VM itself */ - - /* Stack allocation. Expr programs have the feature that - * a program of length N can't require a stack longer than - * N. */ - if (expr->len > JIM_EE_STATICSTACK_LEN) - e.stack = Jim_Alloc(sizeof(Jim_Obj *) * expr->len); - else - e.stack = staticStack; - - e.stacklen = 0; - - /* Execute every instruction */ - for (i = 0; i < expr->len && retcode == JIM_OK; i++) { - Jim_Obj *objPtr; - - switch (expr->token[i].type) { - case JIM_TT_EXPR_INT: - case JIM_TT_EXPR_DOUBLE: - case JIM_TT_EXPR_BOOLEAN: - case JIM_TT_STR: - ExprPush(&e, expr->token[i].objPtr); - break; - - case JIM_TT_VAR: - objPtr = Jim_GetVariable(interp, expr->token[i].objPtr, JIM_ERRMSG); - if (objPtr) { - ExprPush(&e, objPtr); - } - else { - retcode = JIM_ERR; - } - break; - - case JIM_TT_DICTSUGAR: - objPtr = JimExpandDictSugar(interp, expr->token[i].objPtr); - if (objPtr) { - ExprPush(&e, objPtr); - } - else { - retcode = JIM_ERR; - } - break; - - case JIM_TT_ESC: - retcode = Jim_SubstObj(interp, expr->token[i].objPtr, &objPtr, JIM_NONE); - if (retcode == JIM_OK) { - ExprPush(&e, objPtr); - } - break; - - case JIM_TT_CMD: - retcode = Jim_EvalObj(interp, expr->token[i].objPtr); - if (retcode == JIM_OK) { - ExprPush(&e, Jim_GetResult(interp)); - } - break; - - default:{ - /* Find and execute the operation */ - e.skip = 0; - e.opcode = expr->token[i].type; - - retcode = JimExprOperatorInfoByOpcode(e.opcode)->funcop(interp, &e); - /* Skip some opcodes if necessary */ - i += e.skip; - continue; - } - } - } + /* Evaluate with the recursive expr engine */ + retcode = JimExprEvalTermNode(interp, expr->expr); expr->inUse--; - if (retcode == JIM_OK) { - *exprResultPtrPtr = ExprPop(&e); - } - else { - for (i = 0; i < e.stacklen; i++) { - Jim_DecrRefCount(interp, e.stack[i]); - } - } - if (e.stack != staticStack) { - Jim_Free(e.stack); - } return retcode; } int Jim_GetBoolFromExpr(Jim_Interp *interp, Jim_Obj *exprObjPtr, int *boolPtr) { - Jim_Obj *exprResultPtr; - int retcode = Jim_EvalExpression(interp, exprObjPtr, &exprResultPtr); + int retcode = Jim_EvalExpression(interp, exprObjPtr); if (retcode == JIM_OK) { - switch (ExprBool(interp, exprResultPtr)) { + switch (ExprBool(interp, Jim_GetResult(interp))) { case 0: *boolPtr = 0; break; @@ -9639,7 +9325,6 @@ int Jim_GetBoolFromExpr(Jim_Interp *interp, Jim_Obj *exprObjPtr, int *boolPtr) retcode = JIM_ERR; break; } - Jim_DecrRefCount(interp, exprResultPtr); } return retcode; } @@ -11822,7 +11507,7 @@ static int Jim_ForCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *argv */ if (retval == JIM_OK && boolean) { ScriptObj *incrScript; - ExprByteCode *expr; + struct ExprTree *expr; jim_wide stop, currentVal; Jim_Obj *objPtr; int cmpOffset; @@ -11836,47 +11521,53 @@ static int Jim_ForCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *argv goto evalstart; } /* Ensure proper token types. */ - if (incrScript->token[1].type != JIM_TT_ESC || - expr->token[0].type != JIM_TT_VAR || - (expr->token[1].type != JIM_TT_EXPR_INT && expr->token[1].type != JIM_TT_VAR)) { + if (incrScript->token[1].type != JIM_TT_ESC) { goto evalstart; } - if (expr->token[2].type == JIM_EXPROP_LT) { + if (expr->expr->type == JIM_EXPROP_LT) { cmpOffset = 0; } - else if (expr->token[2].type == JIM_EXPROP_LTE) { + else if (expr->expr->type == JIM_EXPROP_LTE) { cmpOffset = 1; } else { goto evalstart; } + if (expr->expr->left->type != JIM_TT_VAR) { + goto evalstart; + } + + if (expr->expr->right->type != JIM_TT_VAR && expr->expr->right->type != JIM_TT_EXPR_INT) { + goto evalstart; + } + /* Update command must be incr */ if (!Jim_CompareStringImmediate(interp, incrScript->token[1].objPtr, "incr")) { goto evalstart; } /* incr, expression must be about the same variable */ - if (!Jim_StringEqObj(incrScript->token[2].objPtr, expr->token[0].objPtr)) { + if (!Jim_StringEqObj(incrScript->token[2].objPtr, expr->expr->left->objPtr)) { goto evalstart; } /* Get the stop condition (must be a variable or integer) */ - if (expr->token[1].type == JIM_TT_EXPR_INT) { - if (Jim_GetWide(interp, expr->token[1].objPtr, &stop) == JIM_ERR) { + if (expr->expr->right->type == JIM_TT_EXPR_INT) { + if (Jim_GetWide(interp, expr->expr->right->objPtr, &stop) == JIM_ERR) { goto evalstart; } } else { - stopVarNamePtr = expr->token[1].objPtr; + stopVarNamePtr = expr->expr->right->objPtr; Jim_IncrRefCount(stopVarNamePtr); /* Keep the compiler happy */ stop = 0; } /* Initialization */ - varNamePtr = expr->token[0].objPtr; + varNamePtr = expr->expr->left->objPtr; Jim_IncrRefCount(varNamePtr); objPtr = Jim_GetVariable(interp, varNamePtr, JIM_NONE); @@ -12876,6 +12567,33 @@ static int Jim_AppendCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *a return JIM_OK; } +#if defined(JIM_DEBUG_COMMAND) && !defined(JIM_BOOTSTRAP) +/** + * Returns a zero-refcount list describing the expression at 'node' + */ +static Jim_Obj *JimGetExprAsList(Jim_Interp *interp, struct JimExprNode *node) +{ + Jim_Obj *listObjPtr = Jim_NewListObj(interp, NULL, 0); + + Jim_ListAppendElement(interp, listObjPtr, Jim_NewStringObj(interp, jim_tt_name(node->type), -1)); + if (TOKEN_IS_EXPR_OP(node->type)) { + if (node->left) { + Jim_ListAppendElement(interp, listObjPtr, JimGetExprAsList(interp, node->left)); + } + if (node->right) { + Jim_ListAppendElement(interp, listObjPtr, JimGetExprAsList(interp, node->right)); + } + if (node->ternary) { + Jim_ListAppendElement(interp, listObjPtr, JimGetExprAsList(interp, node->ternary)); + } + } + else { + Jim_ListAppendElement(interp, listObjPtr, node->objPtr); + } + return listObjPtr; +} +#endif /* JIM_DEBUG_COMMAND && !JIM_BOOTSTRAP */ + /* [debug] */ static int Jim_DebugCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *argv) { @@ -13004,7 +12722,7 @@ static int Jim_DebugCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *ar return JIM_OK; } else if (option == OPT_EXPRLEN) { - ExprByteCode *expr; + struct ExprTree *expr; if (argc != 3) { Jim_WrongNumArgs(interp, 2, argv, "expression"); @@ -13017,9 +12735,7 @@ static int Jim_DebugCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *ar return JIM_OK; } else if (option == OPT_EXPRBC) { - Jim_Obj *objPtr; - ExprByteCode *expr; - int i; + struct ExprTree *expr; if (argc != 3) { Jim_WrongNumArgs(interp, 2, argv, "expression"); @@ -13028,55 +12744,7 @@ static int Jim_DebugCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *ar expr = JimGetExpression(interp, argv[2]); if (expr == NULL) return JIM_ERR; - objPtr = Jim_NewListObj(interp, NULL, 0); - for (i = 0; i < expr->len; i++) { - const char *type; - const Jim_ExprOperator *op; - Jim_Obj *obj = expr->token[i].objPtr; - - switch (expr->token[i].type) { - case JIM_TT_EXPR_INT: - type = "int"; - break; - case JIM_TT_EXPR_DOUBLE: - type = "double"; - break; - case JIM_TT_EXPR_BOOLEAN: - type = "boolean"; - break; - case JIM_TT_CMD: - type = "command"; - break; - case JIM_TT_VAR: - type = "variable"; - break; - case JIM_TT_DICTSUGAR: - type = "dictsugar"; - break; - case JIM_TT_EXPRSUGAR: - type = "exprsugar"; - break; - case JIM_TT_ESC: - type = "subst"; - break; - case JIM_TT_STR: - type = "string"; - break; - default: - op = JimExprOperatorInfoByOpcode(expr->token[i].type); - if (op == NULL) { - type = "private"; - } - else { - type = "operator"; - } - obj = Jim_NewStringObj(interp, op ? op->name : "", -1); - break; - } - Jim_ListAppendElement(interp, objPtr, Jim_NewStringObj(interp, type, -1)); - Jim_ListAppendElement(interp, objPtr, obj); - } - Jim_SetResult(interp, objPtr); + Jim_SetResult(interp, JimGetExprAsList(interp, expr->expr)); return JIM_OK; } else { @@ -13164,18 +12832,17 @@ static int Jim_UplevelCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const * /* [expr] */ static int Jim_ExprCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *argv) { - Jim_Obj *exprResultPtr; int retcode; if (argc == 2) { - retcode = Jim_EvalExpression(interp, argv[1], &exprResultPtr); + retcode = Jim_EvalExpression(interp, argv[1]); } else if (argc > 2) { Jim_Obj *objPtr; objPtr = Jim_ConcatObj(interp, argc - 1, argv + 1); Jim_IncrRefCount(objPtr); - retcode = Jim_EvalExpression(interp, objPtr, &exprResultPtr); + retcode = Jim_EvalExpression(interp, objPtr); Jim_DecrRefCount(interp, objPtr); } else { @@ -13184,8 +12851,6 @@ static int Jim_ExprCoreCommand(Jim_Interp *interp, int argc, Jim_Obj *const *arg } if (retcode != JIM_OK) return retcode; - Jim_SetResult(interp, exprResultPtr); - Jim_DecrRefCount(interp, exprResultPtr); return JIM_OK; } diff --git a/jim.h b/jim.h index 58e6e56..9338f86 100644 --- a/jim.h +++ b/jim.h @@ -816,7 +816,7 @@ JIM_EXPORT int Jim_GetReturnCode (Jim_Interp *interp, Jim_Obj *objPtr, /* expression object */ JIM_EXPORT int Jim_EvalExpression (Jim_Interp *interp, - Jim_Obj *exprObjPtr, Jim_Obj **exprResultPtrPtr); + Jim_Obj *exprObjPtr); JIM_EXPORT int Jim_GetBoolFromExpr (Jim_Interp *interp, Jim_Obj *exprObjPtr, int *boolPtr); diff --git a/regtest.tcl b/regtest.tcl index 854d96a..e3213b5 100644 --- a/regtest.tcl +++ b/regtest.tcl @@ -325,6 +325,11 @@ puts "TEST 45 PASSED" catch {scan $(1) $(1)} puts "TEST 46 PASSED" +# REGTEST 47 +# Invalid ternary expression +catch {set a $(99?9,99?9:*9:999)?9)} +puts "TEST 47 PASSED" + # TAKE THE FOLLOWING puts AS LAST LINE puts "--- ALL TESTS PASSED ---" diff --git a/tests/expr.test b/tests/expr.test index dbe84f5..b195d4a 100644 --- a/tests/expr.test +++ b/tests/expr.test @@ -99,6 +99,14 @@ test expr-2.4 "Ternary operator - missing question" -body { expr {1 : 2} } -returnCodes error -match glob -result * +test expr-2.5 "Ternary operator with -ve values" { + expr {-1?-2:-3} +} -2 + +test expr-2.6 "Ternary operator with -ve values" { + expr {0?-2:-3} +} -3 + test expr-3.1 "in, ni operators" { set l {a b c d} set c C -- 2.11.4.GIT