From bf2a54b0584c1e568af7ecf67ae2a623bc5263fe Mon Sep 17 00:00:00 2001 From: Alexander Gavrilov Date: Sat, 15 Sep 2018 15:32:40 +0300 Subject: Support evaluating simple driver expressions without Python interpreter. Recently @sergey found that hard-coding evaluation of certain very common driver expressions without calling the Python interpreter produces a 30-40% performance improvement. Since hard-coding is obviously not suitable for production, I implemented a proper parser and interpreter for simple arithmetic expressions in C. The evaluator supports +, -, *, /, (), ==, !=, <, <=, >, >=, and, or, not, ternary if; driver variables, frame, pi, True, False, and a subset of standard math functions that seem most useful. Booleans are represented as numbers, since within the supported operation set it seems to be impossible to distinguish True/False from 1.0/0.0. Boolean operations properly implement lazy evaluation with jumps, and comparisons support chaining like 'a < b < c...'. Expressions are parsed into a very simple stack machine program that can then be safely evaluated in multiple threads. Reviewers: sergey, campbellbarton Differential Revision: https://developer.blender.org/D3698 --- source/blender/blenkernel/BKE_fcurve.h | 3 + source/blender/blenkernel/intern/fcurve.c | 143 +++- source/blender/blenlib/BLI_simple_expr.h | 96 +++ source/blender/blenlib/CMakeLists.txt | 1 + source/blender/blenlib/intern/simple_expr.c | 924 +++++++++++++++++++++ source/blender/blenloader/intern/readfile.c | 1 + source/blender/editors/animation/drivers.c | 5 +- source/blender/editors/interface/interface_anim.c | 4 +- source/blender/editors/space_graph/graph_buttons.c | 15 +- source/blender/makesdna/DNA_anim_types.h | 2 + source/blender/makesrna/intern/rna_fcurve.c | 16 +- tests/gtests/blenlib/BLI_simple_expr_test.cc | 310 +++++++ tests/gtests/blenlib/CMakeLists.txt | 1 + 13 files changed, 1495 insertions(+), 26 deletions(-) create mode 100644 source/blender/blenlib/BLI_simple_expr.h create mode 100644 source/blender/blenlib/intern/simple_expr.c create mode 100644 tests/gtests/blenlib/BLI_simple_expr_test.cc diff --git a/source/blender/blenkernel/BKE_fcurve.h b/source/blender/blenkernel/BKE_fcurve.h index c0bbf146afd..3ae7ebf5d80 100644 --- a/source/blender/blenkernel/BKE_fcurve.h +++ b/source/blender/blenkernel/BKE_fcurve.h @@ -108,6 +108,9 @@ bool driver_get_variable_property( struct ChannelDriver *driver, struct DriverTarget *dtar, struct PointerRNA *r_ptr, struct PropertyRNA **r_prop, int *r_index); +bool BKE_driver_has_simple_expression(struct ChannelDriver *driver); +void BKE_driver_invalidate_expression(struct ChannelDriver *driver, bool expr_changed, bool varname_changed); + float evaluate_driver(struct PathResolvedRNA *anim_rna, struct ChannelDriver *driver, struct ChannelDriver *driver_orig, const float evaltime); diff --git a/source/blender/blenkernel/intern/fcurve.c b/source/blender/blenkernel/intern/fcurve.c index bf516a6b739..629307d6cc2 100644 --- a/source/blender/blenkernel/intern/fcurve.c +++ b/source/blender/blenkernel/intern/fcurve.c @@ -49,6 +49,8 @@ #include "BLI_threads.h" #include "BLI_string_utils.h" #include "BLI_utildefines.h" +#include "BLI_simple_expr.h" +#include "BLI_alloca.h" #include "BLT_translation.h" @@ -65,6 +67,8 @@ #include "RNA_access.h" +#include "atomic_ops.h" + #ifdef WITH_PYTHON #include "BPY_extern.h" #endif @@ -1694,11 +1698,8 @@ void driver_free_variable_ex(ChannelDriver *driver, DriverVar *dvar) /* remove and free the driver variable */ driver_free_variable(&driver->variables, dvar); -#ifdef WITH_PYTHON /* since driver variables are cached, the expression needs re-compiling too */ - if (driver->type == DRIVER_TYPE_PYTHON) - driver->flag |= DRIVER_FLAG_RENAMEVAR; -#endif + BKE_driver_invalidate_expression(driver, false, true); } /* Copy driver variables from src_vars list to dst_vars list */ @@ -1835,11 +1836,8 @@ DriverVar *driver_add_new_variable(ChannelDriver *driver) /* set the default type to 'single prop' */ driver_change_variable_type(dvar, DVAR_TYPE_SINGLE_PROP); -#ifdef WITH_PYTHON /* since driver variables are cached, the expression needs re-compiling too */ - if (driver->type == DRIVER_TYPE_PYTHON) - driver->flag |= DRIVER_FLAG_RENAMEVAR; -#endif + BKE_driver_invalidate_expression(driver, false, true); /* return the target */ return dvar; @@ -1868,6 +1866,8 @@ void fcurve_free_driver(FCurve *fcu) BPY_DECREF(driver->expr_comp); #endif + BLI_simple_expr_free(driver->expr_simple); + /* free driver itself, then set F-Curve's point to this to NULL (as the curve may still be used) */ MEM_freeN(driver); fcu->driver = NULL; @@ -1885,6 +1885,7 @@ ChannelDriver *fcurve_copy_driver(const ChannelDriver *driver) /* copy all data */ ndriver = MEM_dupallocN(driver); ndriver->expr_comp = NULL; + ndriver->expr_simple = NULL; /* copy variables */ BLI_listbase_clear(&ndriver->variables); /* to get rid of refs to non-copied data (that's still used on original) */ @@ -1894,6 +1895,124 @@ ChannelDriver *fcurve_copy_driver(const ChannelDriver *driver) return ndriver; } +/* Driver Expression Evaluation --------------- */ + +static ParsedSimpleExpr *driver_compile_simple_expr_impl(ChannelDriver *driver) +{ + /* Prepare parameter names. */ + int num_vars = BLI_listbase_count(&driver->variables); + const char **names = BLI_array_alloca(names, num_vars + 1); + int i = 0; + + names[i++] = "frame"; + + for (DriverVar *dvar = driver->variables.first; dvar; dvar = dvar->next) { + names[i++] = dvar->name; + } + + return BLI_simple_expr_parse(driver->expression, num_vars + 1, names); +} + +static bool driver_evaluate_simple_expr(ChannelDriver *driver, ParsedSimpleExpr *expr, float *result, float time) +{ + /* Prepare parameter values. */ + int num_vars = BLI_listbase_count(&driver->variables); + double *vars = BLI_array_alloca(vars, num_vars + 1); + int i = 0; + + vars[i++] = time; + + for (DriverVar *dvar = driver->variables.first; dvar; dvar = dvar->next) { + vars[i++] = driver_get_variable_value(driver, dvar); + } + + /* Evaluate expression. */ + double result_val; + eSimpleExpr_EvalStatus status = BLI_simple_expr_evaluate(expr, &result_val, num_vars + 1, vars); + const char *message; + + switch (status) { + case SIMPLE_EXPR_SUCCESS: + if (isfinite(result_val)) { + *result = (float)result_val; + } + return true; + + case SIMPLE_EXPR_DIV_BY_ZERO: + case SIMPLE_EXPR_MATH_ERROR: + message = (status == SIMPLE_EXPR_DIV_BY_ZERO) ? "Division by Zero" : "Math Domain Error"; + fprintf(stderr, "\n%s in Driver: '%s'\n", message, driver->expression); + + driver->flag |= DRIVER_FLAG_INVALID; + return true; + + default: + /* arriving here means a bug, not user error */ + printf("Error: simple driver expression evaluation failed: '%s'\n", driver->expression); + return false; + } +} + +/* Compile and cache the driver expression if necessary, with thread safety. */ +static bool driver_compile_simple_expr(ChannelDriver *driver) +{ + if (driver->expr_simple != NULL) { + return true; + } + + if (driver->type != DRIVER_TYPE_PYTHON) { + return false; + } + + /* It's safe to parse in multiple threads; at worst it'll + * waste some effort, but in return avoids mutex contention. */ + ParsedSimpleExpr *expr = driver_compile_simple_expr_impl(driver); + + /* Store the result if the field is still NULL, or discard + * it if another thread got here first. */ + if (atomic_cas_ptr((void**)&driver->expr_simple, NULL, expr) != NULL) { + BLI_simple_expr_free(expr); + } + + return true; +} + +/* Try using the simple expression evaluator to compute the result of the driver. + * On success, stores the result and returns true; on failure result is set to 0. */ +static bool driver_try_evaluate_simple_expr(ChannelDriver *driver, ChannelDriver *driver_orig, float *result, float time) +{ + *result = 0.0f; + + return driver_compile_simple_expr(driver_orig) && + BLI_simple_expr_is_valid(driver_orig->expr_simple) && + driver_evaluate_simple_expr(driver, driver_orig->expr_simple, result, time); +} + +/* Check if the expression in the driver conforms to the simple subset. */ +bool BKE_driver_has_simple_expression(ChannelDriver *driver) +{ + return driver_compile_simple_expr(driver) && BLI_simple_expr_is_valid(driver->expr_simple); +} + +/* Reset cached compiled expression data */ +void BKE_driver_invalidate_expression(ChannelDriver *driver, bool expr_changed, bool varname_changed) +{ + if (expr_changed || varname_changed) { + BLI_simple_expr_free(driver->expr_simple); + driver->expr_simple = NULL; + } + +#ifdef WITH_PYTHON + if (expr_changed) { + driver->flag |= DRIVER_FLAG_RECOMPILE; + } + + if (varname_changed) { + driver->flag |= DRIVER_FLAG_RENAMEVAR; + } +#endif +} + /* Driver Evaluation -------------------------- */ /* Evaluate a Driver Variable to get a value that contributes to the final */ @@ -1997,14 +2116,14 @@ float evaluate_driver(PathResolvedRNA *anim_rna, ChannelDriver *driver, ChannelD } case DRIVER_TYPE_PYTHON: /* expression */ { -#ifdef WITH_PYTHON /* check for empty or invalid expression */ if ( (driver_orig->expression[0] == '\0') || (driver_orig->flag & DRIVER_FLAG_INVALID) ) { driver->curval = 0.0f; } - else { + else if (!driver_try_evaluate_simple_expr(driver, driver_orig, &driver->curval, evaltime)) { +#ifdef WITH_PYTHON /* this evaluates the expression using Python, and returns its result: * - on errors it reports, then returns 0.0f */ @@ -2013,10 +2132,10 @@ float evaluate_driver(PathResolvedRNA *anim_rna, ChannelDriver *driver, ChannelD driver->curval = BPY_driver_exec(anim_rna, driver, driver_orig, evaltime); BLI_mutex_unlock(&python_driver_lock); - } #else /* WITH_PYTHON*/ - UNUSED_VARS(anim_rna, evaltime); + UNUSED_VARS(anim_rna, evaltime); #endif /* WITH_PYTHON*/ + } break; } default: diff --git a/source/blender/blenlib/BLI_simple_expr.h b/source/blender/blenlib/BLI_simple_expr.h new file mode 100644 index 00000000000..8498f1a02e7 --- /dev/null +++ b/source/blender/blenlib/BLI_simple_expr.h @@ -0,0 +1,96 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2018 Blender Foundation, Alexander Gavrilov + * All rights reserved. + * + * Contributor(s): Alexander Gavrilov + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_SIMPLE_EXPR_H__ +#define __BLI_SIMPLE_EXPR_H__ + +/** \file BLI_simple_expr.h + * \ingroup bli + * \author Alexander Gavrilov + * \since 2018 + * + * Simple evaluator for a subset of Python expressions that can be + * computed using purely double precision floating point values. + * + * Supported subset: + * + * - Identifiers use only ASCII characters. + * - Literals: + * floating point and decimal integer. + * - Constants: + * pi, True, False + * - Operators: + * +, -, *, /, ==, !=, <, <=, >, >=, and, or, not, ternary if + * - Functions: + * radians, degrees, + * abs, fabs, floor, ceil, trunc, int, + * sin, cos, tan, asin, acos, atan, atan2, + * exp, log, sqrt, pow, fmod + * + * The implementation has no global state and can be used multithreaded. + */ + +#ifdef __cplusplus +extern "C" { +#endif + +/** Opaque structure containing pre-parsed data for evaluation. */ +typedef struct ParsedSimpleExpr ParsedSimpleExpr; + +/** Simple expression evaluation return code. */ +typedef enum eSimpleExpr_EvalStatus { + SIMPLE_EXPR_SUCCESS = 0, + /* Computation errors; result is still set, but may be NaN */ + SIMPLE_EXPR_DIV_BY_ZERO, + SIMPLE_EXPR_MATH_ERROR, + /* Expression dependent errors or bugs; result is 0 */ + SIMPLE_EXPR_INVALID, + SIMPLE_EXPR_FATAL_ERROR, +} eSimpleExpr_EvalStatus; + +/** Free the parsed data; NULL argument is ok. */ +void BLI_simple_expr_free(struct ParsedSimpleExpr *expr); + +/** Check if the parsing result is valid for evaluation. */ +bool BLI_simple_expr_is_valid(struct ParsedSimpleExpr *expr); + +/** Check if the parsed expression always evaluates to the same value. */ +bool BLI_simple_expr_is_constant(struct ParsedSimpleExpr *expr); + +/** Parse the expression for evaluation later. + * Returns non-NULL even on failure; use is_valid to check. + */ +ParsedSimpleExpr *BLI_simple_expr_parse(const char *expression, int num_params, const char **param_names); + +/** Evaluate the expression with the given parameters. + * The order and number of parameters must match the names given to parse. + */ +eSimpleExpr_EvalStatus BLI_simple_expr_evaluate(struct ParsedSimpleExpr *expr, double *result, int num_params, const double *params); + +#ifdef __cplusplus +} +#endif + +#endif /* __BLI_SIMPLE_EXPR_H__*/ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 9621a759f3c..9dd89834bbd 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -104,6 +104,7 @@ set(SRC intern/rct.c intern/scanfill.c intern/scanfill_utils.c + intern/simple_expr.c intern/smallhash.c intern/sort.c intern/sort_utils.c diff --git a/source/blender/blenlib/intern/simple_expr.c b/source/blender/blenlib/intern/simple_expr.c new file mode 100644 index 00000000000..4dc4e7615cf --- /dev/null +++ b/source/blender/blenlib/intern/simple_expr.c @@ -0,0 +1,924 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2018 Blender Foundation, Alexander Gavrilov + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Alexander Gavrilov + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/blenlib/intern/simple_expr.c + * \ingroup bli + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include "MEM_guardedalloc.h" + +#include "BLI_simple_expr.h" +#include "BLI_blenlib.h" +#include "BLI_math.h" +#include "BLI_string_utils.h" +#include "BLI_utildefines.h" +#include "BLI_alloca.h" + +#ifdef _MSC_VER +#pragma fenv_access (on) +#endif + +/* Simple Expression Stack Machine ------------------------- */ + +typedef enum eSimpleExpr_Opcode { + /* Double constant: (-> dval) */ + OPCODE_CONST, + /* 1 argument function call: (a -> func1(a)) */ + OPCODE_FUNC1, + /* 2 argument function call: (a b -> func2(a,b)) */ + OPCODE_FUNC2, + /* Parameter access: (-> params[ival]) */ + OPCODE_PARAMETER, + /* Minimum of multiple inputs: (a b c... -> min); ival = arg count */ + OPCODE_MIN, + /* Maximum of multiple inputs: (a b c... -> max); ival = arg count */ + OPCODE_MAX, + /* Jump (pc += jmp_offset) */ + OPCODE_JMP, + /* Pop and jump if zero: (a -> ); JUMP IF NOT a */ + OPCODE_JMP_ELSE, + /* Jump if nonzero, or pop: (a -> a JUMP) IF a ELSE (a -> ) */ + OPCODE_JMP_OR, + /* Jump if zero, or pop: (a -> a JUMP) IF NOT a ELSE (a -> ) */ + OPCODE_JMP_AND, + /* For comparison chaining: (a b -> 0 JUMP) IF NOT func2(a,b) ELSE (a b -> b) */ + OPCODE_CMP_CHAIN, +} eSimpleExpr_Opcode; + +typedef double (*UnaryOpFunc)(double); +typedef double (*BinaryOpFunc)(double, double); + +typedef struct SimpleExprOp { + eSimpleExpr_Opcode opcode; + + int jmp_offset; + + union { + int ival; + double dval; + void *ptr; + UnaryOpFunc func1; + BinaryOpFunc func2; + } arg; +} SimpleExprOp; + +struct ParsedSimpleExpr { + int ops_count; + int max_stack; + + SimpleExprOp ops[]; +}; + +void BLI_simple_expr_free(ParsedSimpleExpr *expr) +{ + if (expr != NULL) { + MEM_freeN(expr); + } +} + +bool BLI_simple_expr_is_valid(ParsedSimpleExpr *expr) +{ + return expr != NULL && expr->ops_count > 0; +} + +bool BLI_simple_expr_is_constant(ParsedSimpleExpr *expr) +{ + return expr != NULL && expr->ops_count == 1 && expr->ops[0].opcode == OPCODE_CONST; +} + +/* Stack Machine Evaluation -------------------------------- */ + +eSimpleExpr_EvalStatus BLI_simple_expr_evaluate(ParsedSimpleExpr *expr, double *result, int num_params, const double *params) +{ + *result = 0.0; + + if (!BLI_simple_expr_is_valid(expr)) { + return SIMPLE_EXPR_INVALID; + } + +#define FAIL_IF(condition) if (condition) { return SIMPLE_EXPR_FATAL_ERROR; } + + /* Check the stack requirement is at least remotely sane and allocate on the actual stack. */ + FAIL_IF(expr->max_stack <= 0 || expr->max_stack > 1000); + + double *stack = BLI_array_alloca(stack, expr->max_stack); + + /* Evaluate expression. */ + SimpleExprOp *ops = expr->ops; + int sp = 0, pc; + + feclearexcept(FE_ALL_EXCEPT); + + for (pc = 0; pc >= 0 && pc < expr->ops_count; pc++) { + switch (ops[pc].opcode) { + /* Arithmetic */ + case OPCODE_CONST: + FAIL_IF(sp >= expr->max_stack); + stack[sp++] = ops[pc].arg.dval; + break; + case OPCODE_PARAMETER: + FAIL_IF(sp >= expr->max_stack || ops[pc].arg.ival >= num_params); + stack[sp++] = params[ops[pc].arg.ival]; + break; + case OPCODE_FUNC1: + FAIL_IF(sp < 1); + stack[sp - 1] = ops[pc].arg.func1(stack[sp - 1]); + break; + case OPCODE_FUNC2: + FAIL_IF(sp < 2); + stack[sp - 2] = ops[pc].arg.func2(stack[sp - 2], stack[sp - 1]); + sp--; + break; + case OPCODE_MIN: + FAIL_IF(sp < ops[pc].arg.ival); + for (int j = 1; j < ops[pc].arg.ival; j++, sp--) { + CLAMP_MAX(stack[sp - 2], stack[sp - 1]); + } + break; + case OPCODE_MAX: + FAIL_IF(sp < ops[pc].arg.ival); + for (int j = 1; j < ops[pc].arg.ival; j++, sp--) { + CLAMP_MIN(stack[sp - 2], stack[sp - 1]); + } + break; + + /* Jumps */ + case OPCODE_JMP: + pc += ops[pc].jmp_offset; + break; + case OPCODE_JMP_ELSE: + FAIL_IF(sp < 1); + if (!stack[--sp]) { + pc += ops[pc].jmp_offset; + } + break; + case OPCODE_JMP_OR: + case OPCODE_JMP_AND: + FAIL_IF(sp < 1); + if (!stack[sp - 1] == !(ops[pc].opcode == OPCODE_JMP_OR)) { + pc += ops[pc].jmp_offset; + } + else { + sp--; + } + break; + + /* For chaining comparisons, i.e. "a < b < c" as "a < b and b < c" */ + case OPCODE_CMP_CHAIN: + FAIL_IF(sp < 2); + /* If comparison fails, return 0 and jump to end. */ + if (!ops[pc].arg.func2(stack[sp - 2], stack[sp - 1])) { + stack[sp - 2] = 0.0; + pc += ops[pc].jmp_offset; + } + /* Otherwise keep b on the stack and proceed. */ + else { + stack[sp - 2] = stack[sp - 1]; + } + sp--; + break; + + default: + return SIMPLE_EXPR_FATAL_ERROR; + } + } + + FAIL_IF(sp != 1 || pc != expr->ops_count); + +#undef FAIL_IF + + *result = stack[0]; + + /* Detect floating point evaluation errors. */ + int flags = fetestexcept(FE_DIVBYZERO | FE_INVALID); + if (flags) { + return (flags & FE_INVALID) ? SIMPLE_EXPR_MATH_ERROR : SIMPLE_EXPR_DIV_BY_ZERO; + } + + return SIMPLE_EXPR_SUCCESS; +} + +/* Simple Expression Built-In Operations ------------------- */ + +static double op_negate(double arg) { + return -arg; +} + +static double op_mul(double a, double b) { + return a * b; +} + +static double op_div(double a, double b) { + return a / b; +} + +static double op_add(double a, double b) { + return a + b; +} + +static double op_sub(double a, double b) { + return a - b; +} + +static double op_radians(double arg) { + return arg * M_PI / 180.0; +} + +static double op_degrees(double arg) { + return arg * 180.0 / M_PI; +} + +static double op_not(double a) { + return a ? 0.0 : 1.0; +} + +static double op_eq(double a, double b) { + return a == b ? 1.0 : 0.0; +} + +static double op_ne(double a, double b) { + return a != b ? 1.0 : 0.0; +} + +static double op_lt(double a, double b) { + return a < b ? 1.0 : 0.0; +} + +static double op_le(double a, double b) { + return a <= b ? 1.0 : 0.0; +} + +static double op_gt(double a, double b) { + return a > b ? 1.0 : 0.0; +} + +static double op_ge(double a, double b) { + return a >= b ? 1.0 : 0.0; +} + +typedef struct BuiltinConstDef { + const char *name; + double value; +} BuiltinConstDef; + +static BuiltinConstDef builtin_consts[] = { + { "pi", M_PI }, + { "True", 1.0 }, + { "False", 0.0 }, + { NULL, 0.0 } +}; + +typedef struct BuiltinOpDef { + const char *name; + eSimpleExpr_Opcode op; + void *funcptr; +} BuiltinOpDef; + +static BuiltinOpDef builtin_ops[] = { + { "radians", OPCODE_FUNC1, op_radians }, + { "degrees", OPCODE_FUNC1, op_degrees }, + { "abs", OPCODE_FUNC1, abs }, + { "fabs", OPCODE_FUNC1, abs }, + { "floor", OPCODE_FUNC1, floor }, + { "ceil", OPCODE_FUNC1, ceil }, + { "trunc", OPCODE_FUNC1, trunc }, + { "int", OPCODE_FUNC1, trunc }, + { "sin", OPCODE_FUNC1, sin }, + { "cos", OPCODE_FUNC1, cos }, + { "tan", OPCODE_FUNC1, tan }, + { "asin", OPCODE_FUNC1, asin }, + { "acos", OPCODE_FUNC1, acos }, + { "atan", OPCODE_FUNC1, atan }, + { "atan2", OPCODE_FUNC2, atan2 }, + { "exp", OPCODE_FUNC1, exp }, + { "log", OPCODE_FUNC1, log }, + { "sqrt", OPCODE_FUNC1, sqrt }, + { "pow", OPCODE_FUNC2, pow }, + { "fmod", OPCODE_FUNC2, fmod }, + { NULL, OPCODE_CONST, NULL } +}; + +/* Simple Expression Parser State -------------------------- */ + +#define MAKE_CHAR2(a, b) (((a) << 8) | (b)) + +#define CHECK_ERROR(condition) if (!(condition)) { return false; } + +/* For simplicity simple token types are represented by their own character; + * these are special identifiers for multi-character tokens. */ +#define TOKEN_ID MAKE_CHAR2('I', 'D') +#define TOKEN_NUMBER MAKE_CHAR2('0', '0') +#define TOKEN_GE MAKE_CHAR2('>', '=') +#define TOKEN_LE MAKE_CHAR2('<', '=') +#define TOKEN_NE MAKE_CHAR2('!', '=') +#define TOKEN_EQ MAKE_CHAR2('=', '=') +#define TOKEN_AND MAKE_CHAR2('A', 'N') +#define TOKEN_OR MAKE_CHAR2('O', 'R') +#define TOKEN_NOT MAKE_CHAR2('N', 'O') +#define TOKEN_IF MAKE_CHAR2('I', 'F') +#define TOKEN_ELSE MAKE_CHAR2('E', 'L') + +static const char *token_eq_characters = "!=><"; +static const char *token_characters = "~`!@#$%^&*+-=/\\?:;<>(){}[]|.,\"'"; + +typedef struct KeywordTokenDef { + const char *name; + short token; +} KeywordTokenDef; + +static KeywordTokenDef keyword_list[] = { + { "and", TOKEN_AND }, + { "or", TOKEN_OR }, + { "not", TOKEN_NOT }, + { "if", TOKEN_IF }, + { "else", TOKEN_ELSE }, + { NULL, TOKEN_ID } +}; + +typedef struct SimpleExprParseState { + int param_count; + const char **param_names; + + /* Original expression */ + const char *expr; + const char *cur; + + /* Current token */ + short token; + char *tokenbuf; + double tokenval; + + /* Opcode buffer */ + int ops_count, max_ops, last_jmp; + SimpleExprOp *ops; + + /* Stack space requirement tracking */ + int stack_ptr, max_stack; +} SimpleExprParseState; + +/* Reserve space for the specified number of operations in the buffer. */ +static SimpleExprOp* parse_alloc_ops(SimpleExprParseState *state, int count) +{ + if (state->ops_count + count > state->max_ops) { + state->max_ops = power_of_2_max_i(state->ops_count + count); + state->ops = MEM_reallocN(state->ops, state->max_ops * sizeof(SimpleExprOp)); + } + + SimpleExprOp *op = &state->ops[state->ops_count]; + state->ops_count += count; + return op; +} + +/* Add one operation and track stack usage. */ +static SimpleExprOp* parse_add_op(SimpleExprParseState *state, eSimpleExpr_Opcode code, int stack_delta) +{ + /* track evaluation stack depth */ + state->stack_ptr += stack_delta; + CLAMP_MIN(state->stack_ptr, 0); + CLAMP_MIN(state->max_stack, state->stack_ptr); + + /* allocate the new instruction */ + SimpleExprOp *op = parse_alloc_ops(state, 1); + memset(op, 0, sizeof(SimpleExprOp)); + op->opcode = code; + return op; +} + +/* Add one jump operation and return an index for parse_set_jump. */ +static int parse_add_jump(SimpleExprParseState *state, eSimpleExpr_Opcode code) +{ + parse_add_op(state, code, -1); + return state->last_jmp = state->ops_count; +} + +/* Set the jump offset in a previously added jump operation. */ +static void parse_set_jump(SimpleExprParseState *state, int jump) +{ + state->last_jmp = state->ops_count; + state->ops[jump - 1].jmp_offset = state->ops_count - jump; +} + +/* Add a function call operation, applying constant folding when possible. */ +static bool parse_add_func(SimpleExprParseState *state, eSimpleExpr_Opcode code, int args, void *funcptr) +{ + SimpleExprOp *prev_ops = &state->ops[state->ops_count]; + int jmp_gap = state->ops_count - state->last_jmp; + + feclearexcept(FE_ALL_EXCEPT); + + switch (code) { + case OPCODE_FUNC1: + CHECK_ERROR(args == 1); + + if (jmp_gap >= 1 && prev_ops[-1].opcode == OPCODE_CONST) { + UnaryOpFunc func = funcptr; + + double result = func(prev_ops[-1].arg.dval); + + if (fetestexcept(FE_DIVBYZERO | FE_INVALID) == 0) { + prev_ops[-1].arg.dval = result; + return true; + } + } + break; + + case OPCODE_FUNC2: + CHECK_ERROR(args == 2); + + if (jmp_gap >= 2 && prev_ops[-2].opcode == OPCODE_CONST && prev_ops[-1].opcode == OPCODE_CONST) { + BinaryOpFunc func = funcptr; + + double result = func(prev_ops[-2].arg.dval, prev_ops[-1].arg.dval); + + if (fetestexcept(FE_DIVBYZERO | FE_INVALID) == 0) { + prev_ops[-2].arg.dval = result; + state->ops_count--; + state->stack_ptr--; + return true; + } + } + break; + + default: + BLI_assert(false); + return false; + } + + parse_add_op(state, code, 1-args)->arg.ptr = funcptr; + return true; +} + +/* Extract the next token from raw characters. */ +static bool parse_next_token(SimpleExprParseState *state) +{ + /* Skip whitespace. */ + while (isspace(*state->cur)) { + state->cur++; + } + + /* End of string. */ + if (*state->cur == 0) { + state->token = 0; + return true; + } + + /* Floating point numbers. */ + if (isdigit(*state->cur) || (state->cur[0] == '.' && isdigit(state->cur[1]))) { + char *end, *out = state->tokenbuf; + bool is_float = false; + + while (isdigit(*state->cur)) + *out++ = *state->cur++; + + if (*state->cur == '.') { + is_float = true; + *out++ = *state->cur++; + + while (isdigit(*state->cur)) + *out++ = *state->cur++; + } + + if (ELEM(*state->cur, 'e', 'E')) { + is_float = true; + *out++ = *state->cur++; + + if (ELEM(*state->cur, '+', '-')) + *out++ = *state->cur++; + + CHECK_ERROR(isdigit(*state->cur)); + + while (isdigit(*state->cur)) + *out++ = *state->cur++; + } + + *out = 0; + + /* Forbid C-style octal constants. */ + if (!is_float && state->tokenbuf[0] == '0') { + for (char *p = state->tokenbuf+1; *p; p++) { + if (*p != '0') { + return false; + } + } + } + + state->token = TOKEN_NUMBER; + state->tokenval = strtod(state->tokenbuf, &end); + return (end == out); + } + + /* ?= tokens */ + if (state->cur[1] == '=' && strchr(token_eq_characters, state->cur[0])) { + state->token = MAKE_CHAR2(state->cur[0], state->cur[1]); + state->cur += 2; + return true; + } + + /* Special characters (single character tokens) */ + if (strchr(token_characters, *state->cur)) { + state->token = *state->cur++; + return true; + } + + /* Identifiers */ + if (isalpha(*state->cur) || ELEM(*state->cur, '_')) { + char *out = state->tokenbuf; + + while (isalnum(*state->cur) || ELEM(*state->cur, '_')) + *out++ = *state->cur++; + + *out = 0; + + for (int i = 0; keyword_list[i].name; i++) { + if (STREQ(state->tokenbuf, keyword_list[i].name)) { + state->token = keyword_list[i].token; + return true; + } + } + + state->token = TOKEN_ID; + return true; + } + + return false; +} + +/* Recursive Descent Parser -------------------------------- */ + +static bool parse_expr(SimpleExprParseState *state); + +static int parse_function_args(SimpleExprParseState *state) +{ + if (!parse_next_token(state) || state->token != '(' || !parse_next_token(state)) { + return -1; + } + + int arg_count = 0; + + for(;;) { + if (!parse_expr(state)) { + return -1; + } + + arg_count++; + + switch (state->token) { + case ',': + if (!parse_next_token(state)) { + return -1; + } + break; + + case ')': + if (!parse_next_token(state)) { + return -1; + } + return arg_count; + + default: + return -1; + } + } +} + +static bool parse_unary(SimpleExprParseState *state) +{ + int i; + + switch (state->token) { + case '+': + return parse_next_token(state) && parse_unary(state); + + case '-': + CHECK_ERROR(parse_next_token(state) && parse_unary(state)); + parse_add_func(state, OPCODE_FUNC1, 1, op_negate); + return true; + + case '(': + return parse_next_token(state) && + parse_expr(state) && + state->token == ')' && + parse_next_token(state); + + case TOKEN_NUMBER: + parse_add_op(state, OPCODE_CONST, 1)->arg.dval = state->tokenval; + return parse_next_token(state); + + case TOKEN_ID: + /* Parameters: search in reverse order in case of duplicate names - the last one should win. */ + for (i = state->param_count - 1; i >= 0; i--) { + if (STREQ(state->tokenbuf, state->param_names[i])) { + parse_add_op(state, OPCODE_PARAMETER, 1)->arg.ival = i; + return parse_next_token(state); + } + } + + /* Ordinary builtin constants. */ + for (i = 0; builtin_consts[i].name; i++) { + if (STREQ(state->tokenbuf, builtin_consts[i].name)) { + parse_add_op(state, OPCODE_CONST, 1)->arg.dval = builtin_consts[i].value; + return parse_next_token(state); + } + } + + /* Ordinary builtin functions. */ + for (i = 0; builtin_ops[i].name; i++) { + if (STREQ(state->tokenbuf, builtin_ops[i].name)) { + int args = parse_function_args(state); + + return parse_add_func(state, builtin_ops[i].op, args, builtin_ops[i].funcptr); + } + } + + /* Specially supported functions. */ + if (STREQ(state->tokenbuf, "min")) { + int cnt = parse_function_args(state); + CHECK_ERROR(cnt > 0); + + parse_add_op(state, OPCODE_MIN, 1-cnt)->arg.ival = cnt; + return true; + } + + if (STREQ(state->tokenbuf, "max")) { + int cnt = parse_function_args(state); + CHECK_ERROR(cnt > 0); + + parse_add_op(state, OPCODE_MAX, 1-cnt)->arg.ival = cnt; + return true; + } + + return false; + + default: + return false; + } +} + +static bool parse_mul(SimpleExprParseState *state) +{ + CHECK_ERROR(parse_unary(state)); + + for (;;) { + switch (state->token) { + case '*': + CHECK_ERROR(parse_next_token(state) && parse_unary(state)); + parse_add_func(state, OPCODE_FUNC2, 2, op_mul); + break; + + case '/': + CHECK_ERROR(parse_next_token(state) && parse_unary(state)); + parse_add_func(state, OPCODE_FUNC2, 2, op_div); + break; + + default: + return true; + } + } +} + +static bool parse_add(SimpleExprParseState *state) +{ + CHECK_ERROR(parse_mul(state)); + + for (;;) { + switch (state->token) { + case '+': + CHECK_ERROR(parse_next_token(state) && parse_mul(state)); + parse_add_func(state, OPCODE_FUNC2, 2, op_add); + break; + + case '-': + CHECK_ERROR(parse_next_token(state) && parse_mul(state)); + parse_add_func(state, OPCODE_FUNC2, 2, op_sub); + break; + + default: + return true; + } + } +} + +static BinaryOpFunc parse_get_cmp_func(short token) +{ + switch (token) { + case TOKEN_EQ: + return op_eq; + case TOKEN_NE: + return op_ne; + case '>': + return op_gt; + case TOKEN_GE: + return op_ge; + case '<': + return op_lt; + case TOKEN_LE: + return op_le; + default: + return NULL; + } +} + +static bool parse_cmp_chain(SimpleExprParseState *state, BinaryOpFunc cur_func) +{ + BinaryOpFunc next_func = parse_get_cmp_func(state->token); + + if (next_func) { + parse_add_op(state, OPCODE_CMP_CHAIN, -1)->arg.func2 = cur_func; + int jump = state->last_jmp = state->ops_count; + + CHECK_ERROR(parse_next_token(state) && parse_add(state)); + CHECK_ERROR(parse_cmp_chain(state, next_func)); + + parse_set_jump(state, jump); + } + else { + parse_add_func(state, OPCODE_FUNC2, 2, cur_func); + } + + return true; +} + +static bool parse_cmp(SimpleExprParseState *state) +{ + CHECK_ERROR(parse_add(state)); + + BinaryOpFunc func = parse_get_cmp_func(state->token); + + if (func) { + CHECK_ERROR(parse_next_token(state) && parse_add(state)); + + return parse_cmp_chain(state, func); + } + + return true; +} + +static bool parse_not(SimpleExprParseState *state) +{ + if (state->token == TOKEN_NOT) { + CHECK_ERROR(parse_next_token(state) && parse_not(state)); + parse_add_func(state, OPCODE_FUNC1, 1, op_not); + return true; + } + + return parse_cmp(state); +} + +static bool parse_and(SimpleExprParseState *state) +{ + CHECK_ERROR(parse_not(state)); + + if (state->token == TOKEN_AND) { + int jump = parse_add_jump(state, OPCODE_JMP_AND); + + CHECK_ERROR(parse_next_token(state) && parse_and(state)); + + parse_set_jump(state, jump); + } + + return true; +} + +static bool parse_or(SimpleExprParseState *state) +{ + CHECK_ERROR(parse_and(state)); + + if (state->token == TOKEN_OR) { + int jump = parse_add_jump(state, OPCODE_JMP_OR); + + CHECK_ERROR(parse_next_token(state) && parse_or(state)); + + parse_set_jump(state, jump); + } + + return true; +} + +static bool parse_expr(SimpleExprParseState *state) +{ + /* Temporarily set the constant expression evaluation barrier */ + int prev_last_jmp = state->last_jmp; + int start = state->last_jmp = state->ops_count; + + CHECK_ERROR(parse_or(state)); + + if (state->token == TOKEN_IF) { + /* Ternary IF expression in python requires swapping the + * main body with condition, so stash the body opcodes. */ + int size = state->ops_count - start; + int bytes = size * sizeof(SimpleExprOp); + + SimpleExprOp *body = MEM_mallocN(bytes, "driver if body"); + memcpy(body, state->ops + start, bytes); + + state->last_jmp = state->ops_count = start; + state->stack_ptr--; + + /* Parse condition. */ + if (!parse_next_token(state) || !parse_or(state) || + state->token != TOKEN_ELSE || !parse_next_token(state)) + { + MEM_freeN(body); + return false; + } + + int jmp_else = parse_add_jump(state, OPCODE_JMP_ELSE); + + /* Add body back. */ + memcpy(parse_alloc_ops(state, size), body, bytes); + MEM_freeN(body); + + state->stack_ptr++; + + int jmp_end = parse_add_jump(state, OPCODE_JMP); + + /* Parse the else block. */ + parse_set_jump(state, jmp_else); + + CHECK_ERROR(parse_expr(state)); + + parse_set_jump(state, jmp_end); + } + /* If no actual jumps happened, restore previous barrier */ + else if (state->last_jmp == start) { + state->last_jmp = prev_last_jmp; + } + + return true; +} + +/* Main Parsing Function ----------------------------------- */ + +/* Compile the expression and return the result. */ +ParsedSimpleExpr *BLI_simple_expr_parse(const char *expression, int num_params, const char **param_names) +{ + /* Prepare the parser state. */ + SimpleExprParseState state; + memset(&state, 0, sizeof(state)); + + state.cur = state.expr = expression; + + state.param_count = num_params; + state.param_names = param_names; + + state.tokenbuf = MEM_mallocN(strlen(expression) + 1, __func__); + + state.max_ops = 16; + state.ops = MEM_mallocN(state.max_ops * sizeof(SimpleExprOp), __func__); + + /* Parse the expression. */ + ParsedSimpleExpr *expr; + + if (parse_next_token(&state) && parse_expr(&state) && state.token == 0) { + BLI_assert(state.stack_ptr == 1); + + int bytesize = sizeof(ParsedSimpleExpr) + state.ops_count * sizeof(SimpleExprOp); + + expr = MEM_mallocN(bytesize, "ParsedSimpleExpr"); + expr->ops_count = state.ops_count; + expr->max_stack = state.max_stack; + + memcpy(expr->ops, state.ops, state.ops_count * sizeof(SimpleExprOp)); + } + else { + /* Always return a non-NULL object so that parse failure can be cached. */ + expr = MEM_callocN(sizeof(ParsedSimpleExpr), "ParsedSimpleExpr(empty)"); + } + + MEM_freeN(state.tokenbuf); + MEM_freeN(state.ops); + return expr; +} diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c index b774bb8d1f6..db6dacd2064 100644 --- a/source/blender/blenloader/intern/readfile.c +++ b/source/blender/blenloader/intern/readfile.c @@ -2675,6 +2675,7 @@ static void direct_link_fcurves(FileData *fd, ListBase *list) /* compiled expression data will need to be regenerated (old pointer may still be set here) */ driver->expr_comp = NULL; + driver->expr_simple = NULL; /* give the driver a fresh chance - the operating environment may be different now * (addons, etc. may be different) so the driver namespace may be sane now [#32155] diff --git a/source/blender/editors/animation/drivers.c b/source/blender/editors/animation/drivers.c index 43ee1133ea0..97a600f1301 100644 --- a/source/blender/editors/animation/drivers.c +++ b/source/blender/editors/animation/drivers.c @@ -745,11 +745,8 @@ bool ANIM_driver_vars_paste(ReportList *reports, FCurve *fcu, bool replace) driver->variables.last = tmp_list.last; } -#ifdef WITH_PYTHON /* since driver variables are cached, the expression needs re-compiling too */ - if (driver->type == DRIVER_TYPE_PYTHON) - driver->flag |= DRIVER_FLAG_RENAMEVAR; -#endif + BKE_driver_invalidate_expression(driver, false, true); return true; } diff --git a/source/blender/editors/interface/interface_anim.c b/source/blender/editors/interface/interface_anim.c index d2a5ab80148..4fe555615c2 100644 --- a/source/blender/editors/interface/interface_anim.c +++ b/source/blender/editors/interface/interface_anim.c @@ -168,7 +168,7 @@ bool ui_but_anim_expression_set(uiBut *but, const char *str) BLI_strncpy_utf8(driver->expression, str, sizeof(driver->expression)); /* tag driver as needing to be recompiled */ - driver->flag |= DRIVER_FLAG_RECOMPILE; + BKE_driver_invalidate_expression(driver, true, false); /* clear invalid flags which may prevent this from working */ driver->flag &= ~DRIVER_FLAG_INVALID; @@ -237,7 +237,7 @@ bool ui_but_anim_expression_create(uiBut *but, const char *str) BLI_strncpy_utf8(driver->expression, str, sizeof(driver->expression)); /* updates */ - driver->flag |= DRIVER_FLAG_RECOMPILE; + BKE_driver_invalidate_expression(driver, true, false); DEG_relations_tag_update(CTX_data_main(C)); WM_event_add_notifier(C, NC_ANIMATION | ND_KEYFRAME, NULL); ok = true; diff --git a/source/blender/editors/space_graph/graph_buttons.c b/source/blender/editors/space_graph/graph_buttons.c index 642e8e074fa..1dc57a0da7d 100644 --- a/source/blender/editors/space_graph/graph_buttons.c +++ b/source/blender/editors/space_graph/graph_buttons.c @@ -817,13 +817,18 @@ static void graph_draw_driver_settings_panel(uiLayout *layout, ID *id, FCurve *f col = uiLayoutColumn(layout, true); block = uiLayoutGetBlock(col); - if ((G.f & G_SCRIPT_AUTOEXEC) == 0) { - /* TODO: Add button to enable? */ - uiItemL(col, IFACE_("WARNING: Python expressions limited for security"), ICON_ERROR); - } - else if (driver->flag & DRIVER_FLAG_INVALID) { + if (driver->flag & DRIVER_FLAG_INVALID) { uiItemL(col, IFACE_("ERROR: Invalid Python expression"), ICON_CANCEL); } + else if (!BKE_driver_has_simple_expression(driver)) { + if ((G.f & G_SCRIPT_AUTOEXEC) == 0) { + /* TODO: Add button to enable? */ + uiItemL(col, IFACE_("WARNING: Python expressions limited for security"), ICON_ERROR); + } + else { + uiItemL(col, IFACE_("Slow Python expression"), ICON_INFO); + } + } /* Explicit bpy-references are evil. Warn about these to prevent errors */ /* TODO: put these in a box? */ diff --git a/source/blender/makesdna/DNA_anim_types.h b/source/blender/makesdna/DNA_anim_types.h index 22067b87ff8..edf137ca386 100644 --- a/source/blender/makesdna/DNA_anim_types.h +++ b/source/blender/makesdna/DNA_anim_types.h @@ -415,6 +415,8 @@ typedef struct ChannelDriver { char expression[256]; /* expression to compile for evaluation */ void *expr_comp; /* PyObject - compiled expression, don't save this */ + struct ParsedSimpleExpr *expr_simple; /* compiled simple arithmetic expression */ + float curval; /* result of previous evaluation */ float influence; /* influence of driver on result */ // XXX to be implemented... this is like the constraint influence setting diff --git a/source/blender/makesrna/intern/rna_fcurve.c b/source/blender/makesrna/intern/rna_fcurve.c index 3141e788d8d..efd571d2b18 100644 --- a/source/blender/makesrna/intern/rna_fcurve.c +++ b/source/blender/makesrna/intern/rna_fcurve.c @@ -132,6 +132,13 @@ static StructRNA *rna_FModifierType_refine(struct PointerRNA *ptr) #include "DEG_depsgraph.h" #include "DEG_depsgraph_build.h" +static bool rna_ChannelDriver_is_simple_expression_get(PointerRNA *ptr) +{ + ChannelDriver *driver = ptr->data; + + return BKE_driver_has_simple_expression(driver); +} + static void rna_ChannelDriver_update_data(Main *bmain, Scene *scene, PointerRNA *ptr) { ID *id = ptr->id.data; @@ -151,7 +158,7 @@ static void rna_ChannelDriver_update_expr(Main *bmain, Scene *scene, PointerRNA ChannelDriver *driver = ptr->data; /* tag driver as needing to be recompiled */ - driver->flag |= DRIVER_FLAG_RECOMPILE; + BKE_driver_invalidate_expression(driver, true, false); /* update_data() clears invalid flag and schedules for updates */ rna_ChannelDriver_update_data(bmain, scene, ptr); @@ -184,8 +191,7 @@ static void rna_DriverTarget_update_name(Main *bmain, Scene *scene, PointerRNA * ChannelDriver *driver = ptr->data; rna_DriverTarget_update_data(bmain, scene, ptr); - driver->flag |= DRIVER_FLAG_RENAMEVAR; - + BKE_driver_invalidate_expression(driver, false, true); } /* ----------- */ @@ -1675,6 +1681,10 @@ static void rna_def_channeldriver(BlenderRNA *brna) RNA_def_property_boolean_negative_sdna(prop, NULL, "flag", DRIVER_FLAG_INVALID); RNA_def_property_ui_text(prop, "Invalid", "Driver could not be evaluated in past, so should be skipped"); + prop = RNA_def_property(srna, "is_simple_expression", PROP_BOOLEAN, PROP_NONE); + RNA_def_property_clear_flag(prop, PROP_EDITABLE); + RNA_def_property_boolean_funcs(prop, "rna_ChannelDriver_is_simple_expression_get", NULL); + RNA_def_property_ui_text(prop, "Simple Expression", "The scripted expression can be evaluated without using the full python interpreter"); /* Functions */ RNA_api_drivers(srna); diff --git a/tests/gtests/blenlib/BLI_simple_expr_test.cc b/tests/gtests/blenlib/BLI_simple_expr_test.cc new file mode 100644 index 00000000000..58b33e85a5f --- /dev/null +++ b/tests/gtests/blenlib/BLI_simple_expr_test.cc @@ -0,0 +1,310 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include + +extern "C" { +#include "BLI_simple_expr.h" +#include "BLI_math.h" +}; + +#define TRUE_VAL 1.0 +#define FALSE_VAL 0.0 + +static void simple_expr_parse_fail_test(const char *str) +{ + ParsedSimpleExpr *expr = BLI_simple_expr_parse(str, 0, NULL); + + EXPECT_FALSE(BLI_simple_expr_is_valid(expr)); + + BLI_simple_expr_free(expr); +} + +static void simple_expr_const_test(const char *str, double value, bool force_const) +{ + ParsedSimpleExpr *expr = BLI_simple_expr_parse(str, 0, NULL); + + if (force_const) { + EXPECT_TRUE(BLI_simple_expr_is_constant(expr)); + } + else { + EXPECT_TRUE(BLI_simple_expr_is_valid(expr)); + EXPECT_FALSE(BLI_simple_expr_is_constant(expr)); + } + + double result; + eSimpleExpr_EvalStatus status = BLI_simple_expr_evaluate(expr, &result, 0, NULL); + + EXPECT_EQ(status, SIMPLE_EXPR_SUCCESS); + EXPECT_EQ(result, value); + + BLI_simple_expr_free(expr); +} + +static ParsedSimpleExpr *parse_for_eval(const char *str, bool nonconst) +{ + const char *names[1] = { "x" }; + ParsedSimpleExpr *expr = BLI_simple_expr_parse(str, 1, names); + + EXPECT_TRUE(BLI_simple_expr_is_valid(expr)); + + if (nonconst) { + EXPECT_FALSE(BLI_simple_expr_is_constant(expr)); + } + + return expr; +} + +static void verify_eval_result(ParsedSimpleExpr *expr, double x, double value) +{ + double result; + eSimpleExpr_EvalStatus status = BLI_simple_expr_evaluate(expr, &result, 1, &x); + + EXPECT_EQ(status, SIMPLE_EXPR_SUCCESS); + EXPECT_EQ(result, value); +} + +static void simple_expr_eval_test(const char *str, double x, double value) +{ + ParsedSimpleExpr *expr = parse_for_eval(str, true); + verify_eval_result(expr, x, value); + BLI_simple_expr_free(expr); +} + +static void simple_expr_error_test(const char *str, double x, eSimpleExpr_EvalStatus error) +{ + ParsedSimpleExpr *expr = parse_for_eval(str, false); + + double result; + eSimpleExpr_EvalStatus status = BLI_simple_expr_evaluate(expr, &result, 1, &x); + + EXPECT_EQ(status, error); + + BLI_simple_expr_free(expr); +} + +#define TEST_PARSE_FAIL(name, str) \ + TEST(simple_expr, ParseFail_##name) { simple_expr_parse_fail_test(str); } + +TEST_PARSE_FAIL(Empty, "") +TEST_PARSE_FAIL(ConstHex, "0x0") +TEST_PARSE_FAIL(ConstOctal, "01") +TEST_PARSE_FAIL(Tail, "0 0") +TEST_PARSE_FAIL(ConstFloatExp, "0.5e+") +TEST_PARSE_FAIL(BadId, "Pi") +TEST_PARSE_FAIL(BadArgCount0, "sqrt") +TEST_PARSE_FAIL(BadArgCount1, "sqrt()") +TEST_PARSE_FAIL(BadArgCount2, "sqrt(1,2)") +TEST_PARSE_FAIL(BadArgCount3, "pi()") +TEST_PARSE_FAIL(BadArgCount4, "max()") +TEST_PARSE_FAIL(BadArgCount5, "min()") + +TEST_PARSE_FAIL(Truncated1, "(1+2") +TEST_PARSE_FAIL(Truncated2, "1 if 2") +TEST_PARSE_FAIL(Truncated3, "1 if 2 else") +TEST_PARSE_FAIL(Truncated4, "1 < 2 <") +TEST_PARSE_FAIL(Truncated5, "1 +") +TEST_PARSE_FAIL(Truncated6, "1 *") +TEST_PARSE_FAIL(Truncated7, "1 and") +TEST_PARSE_FAIL(Truncated8, "1 or") +TEST_PARSE_FAIL(Truncated9, "sqrt(1") +TEST_PARSE_FAIL(Truncated10, "fmod(1,") + +/* Constant expression with working constant folding */ +#define TEST_CONST(name, str, value) \ + TEST(simple_expr, Const_##name) { simple_expr_const_test(str, value, true); } + +/* Constant expression but constant folding is not supported */ +#define TEST_RESULT(name, str, value) \ + TEST(simple_expr, Result_##name) { simple_expr_const_test(str, value, false); } + +/* Expression with an argument */ +#define TEST_EVAL(name, str, x, value) \ + TEST(simple_expr, Eval_##name) { simple_expr_eval_test(str, x, value); } + +TEST_CONST(Zero, "0", 0.0) +TEST_CONST(Zero2, "00", 0.0) +TEST_CONST(One, "1", 1.0) +TEST_CONST(OneF, "1.0", 1.0) +TEST_CONST(OneF2, "1.", 1.0) +TEST_CONST(OneE, "1e0", 1.0) +TEST_CONST(TenE, "1.e+1", 10.0) +TEST_CONST(Half, ".5", 0.5) + +TEST_CONST(Pi, "pi", M_PI) +TEST_CONST(True, "True", TRUE_VAL) +TEST_CONST(False, "False", FALSE_VAL) + +TEST_CONST(Sqrt, "sqrt(4)", 2.0) +TEST_EVAL(Sqrt, "sqrt(x)", 4.0, 2.0) + +TEST_CONST(FMod, "fmod(3.5, 2)", 1.5) +TEST_EVAL(FMod, "fmod(x, 2)", 3.5, 1.5) + +TEST_CONST(Pow, "pow(4, 0.5)", 2.0) +TEST_EVAL(Pow, "pow(4, x)", 0.5, 2.0) + +TEST_RESULT(Min1, "min(3,1,2)", 1.0) +TEST_RESULT(Max1, "max(3,1,2)", 3.0) +TEST_RESULT(Min2, "min(1,2,3)", 1.0) +TEST_RESULT(Max2, "max(1,2,3)", 3.0) +TEST_RESULT(Min3, "min(2,3,1)", 1.0) +TEST_RESULT(Max3, "max(2,3,1)", 3.0) + +TEST_CONST(UnaryPlus, "+1", 1.0) + +TEST_CONST(UnaryMinus, "-1", -1.0) +TEST_EVAL(UnaryMinus, "-x", 1.0, -1.0) + +TEST_CONST(BinaryPlus, "1+2", 3.0) +TEST_EVAL(BinaryPlus, "x+2", 1, 3.0) + +TEST_CONST(BinaryMinus, "1-2", -1.0) +TEST_EVAL(BinaryMinus, "1-x", 2, -1.0) + +TEST_CONST(BinaryMul, "2*3", 6.0) +TEST_EVAL(BinaryMul, "x*3", 2, 6.0) + +TEST_CONST(BinaryDiv, "3/2", 1.5) +TEST_EVAL(BinaryDiv, "3/x", 2, 1.5) + +TEST_CONST(Arith1, "1 + -2 * 3", -5.0) +TEST_CONST(Arith2, "(1 + -2) * 3", -3.0) +TEST_CONST(Arith3, "-1 + 2 * 3", 5.0) +TEST_CONST(Arith4, "3 * (-2 + 1)", -3.0) + +TEST_EVAL(Arith1, "1 + -x * 3", 2, -5.0) + +TEST_CONST(Eq1, "1 == 1.0", TRUE_VAL) +TEST_CONST(Eq2, "1 == 2.0", FALSE_VAL) +TEST_CONST(Eq3, "True == 1", TRUE_VAL) +TEST_CONST(Eq4, "False == 0", TRUE_VAL) + +TEST_EVAL(Eq1, "1 == x", 1.0, TRUE_VAL) +TEST_EVAL(Eq2, "1 == x", 2.0, FALSE_VAL) + +TEST_CONST(NEq1, "1 != 1.0", FALSE_VAL) +TEST_CONST(NEq2, "1 != 2.0", TRUE_VAL) + +TEST_EVAL(NEq1, "1 != x", 1.0, FALSE_VAL) +TEST_EVAL(NEq2, "1 != x", 2.0, TRUE_VAL) + +TEST_CONST(Lt1, "1 < 1", FALSE_VAL) +TEST_CONST(Lt2, "1 < 2", TRUE_VAL) +TEST_CONST(Lt3, "2 < 1", FALSE_VAL) + +TEST_CONST(Le1, "1 <= 1", TRUE_VAL) +TEST_CONST(Le2, "1 <= 2", TRUE_VAL) +TEST_CONST(Le3, "2 <= 1", FALSE_VAL) + +TEST_CONST(Gt1, "1 > 1", FALSE_VAL) +TEST_CONST(Gt2, "1 > 2", FALSE_VAL) +TEST_CONST(Gt3, "2 > 1", TRUE_VAL) + +TEST_CONST(Ge1, "1 >= 1", TRUE_VAL) +TEST_CONST(Ge2, "1 >= 2", FALSE_VAL) +TEST_CONST(Ge3, "2 >= 1", TRUE_VAL) + +TEST_CONST(Cmp1, "3 == 1 + 2", TRUE_VAL) + +TEST_EVAL(Cmp1, "3 == x + 2", 1, TRUE_VAL) +TEST_EVAL(Cmp1b, "3 == x + 2", 1.5, FALSE_VAL) + +TEST_RESULT(CmpChain1, "1 < 2 < 3", TRUE_VAL) +TEST_RESULT(CmpChain2, "1 < 2 == 2", TRUE_VAL) +TEST_RESULT(CmpChain3, "1 < 2 > -1", TRUE_VAL) +TEST_RESULT(CmpChain4, "1 < 2 < 2 < 3", FALSE_VAL) +TEST_RESULT(CmpChain5, "1 < 2 <= 2 < 3", TRUE_VAL) + +TEST_EVAL(CmpChain1a, "1 < x < 3", 2, TRUE_VAL) +TEST_EVAL(CmpChain1b, "1 < x < 3", 1, FALSE_VAL) +TEST_EVAL(CmpChain1c, "1 < x < 3", 3, FALSE_VAL) + +TEST_CONST(Not1, "not 2", FALSE_VAL) +TEST_CONST(Not2, "not 0", TRUE_VAL) +TEST_CONST(Not3, "not not 2", TRUE_VAL) + +TEST_EVAL(Not1, "not x", 2, FALSE_VAL) +TEST_EVAL(Not2, "not x", 0, TRUE_VAL) + +TEST_RESULT(And1, "2 and 3", 3.0) +TEST_RESULT(And2, "0 and 3", 0.0) + +TEST_RESULT(Or1, "2 or 3", 2.0) +TEST_RESULT(Or2, "0 or 3", 3.0) + +TEST_RESULT(Bool1, "2 or 3 and 4", 2.0) +TEST_RESULT(Bool2, "not 2 or 3 and 4", 4.0) + +TEST(simple_expr, Eval_Ternary1) +{ + ParsedSimpleExpr *expr = parse_for_eval("x / 2 if x < 4 else x - 2 if x < 8 else x*2 - 12", true); + + for (int i = 0; i <= 10; i++) { + double x = i; + double v = (x < 4) ? (x / 2) : (x < 8) ? (x - 2) : (x*2 - 12); + + verify_eval_result(expr, x, v); + } + + BLI_simple_expr_free(expr); +} + +TEST(simple_expr, MultipleArgs) +{ + const char* names[3] = { "x", "y", "x" }; + double values[3] = { 1.0, 2.0, 3.0 }; + + ParsedSimpleExpr *expr = BLI_simple_expr_parse("x*10 + y", 3, names); + + EXPECT_TRUE(BLI_simple_expr_is_valid(expr)); + + double result; + eSimpleExpr_EvalStatus status = BLI_simple_expr_evaluate(expr, &result, 3, values); + + EXPECT_EQ(status, SIMPLE_EXPR_SUCCESS); + EXPECT_EQ(result, 32.0); + + BLI_simple_expr_free(expr); +} + +#define TEST_ERROR(name, str, x, code) \ + TEST(simple_expr, Error_##name) { simple_expr_error_test(str, x, code); } + +TEST_ERROR(DivZero1, "0 / 0", 0.0, SIMPLE_EXPR_MATH_ERROR) +TEST_ERROR(DivZero2, "1 / 0", 0.0, SIMPLE_EXPR_DIV_BY_ZERO) +TEST_ERROR(DivZero3, "1 / x", 0.0, SIMPLE_EXPR_DIV_BY_ZERO) +TEST_ERROR(DivZero4, "1 / x", 1.0, SIMPLE_EXPR_SUCCESS) + +TEST_ERROR(SqrtDomain1, "sqrt(-1)", 0.0, SIMPLE_EXPR_MATH_ERROR) +TEST_ERROR(SqrtDomain2, "sqrt(x)", -1.0, SIMPLE_EXPR_MATH_ERROR) +TEST_ERROR(SqrtDomain3, "sqrt(x)", 0.0, SIMPLE_EXPR_SUCCESS) + +TEST_ERROR(PowDomain1, "pow(-1, 0.5)", 0.0, SIMPLE_EXPR_MATH_ERROR) +TEST_ERROR(PowDomain2, "pow(-1, x)", 0.5, SIMPLE_EXPR_MATH_ERROR) +TEST_ERROR(PowDomain3, "pow(-1, x)", 2.0, SIMPLE_EXPR_SUCCESS) + +TEST_ERROR(Mixed1, "sqrt(x) + 1 / max(0, x)", -1.0, SIMPLE_EXPR_MATH_ERROR) +TEST_ERROR(Mixed2, "sqrt(x) + 1 / max(0, x)", 0.0, SIMPLE_EXPR_DIV_BY_ZERO) +TEST_ERROR(Mixed3, "sqrt(x) + 1 / max(0, x)", 1.0, SIMPLE_EXPR_SUCCESS) + +TEST(simple_expr, Error_Invalid) +{ + ParsedSimpleExpr *expr = BLI_simple_expr_parse("", 0, NULL); + double result; + + EXPECT_EQ(BLI_simple_expr_evaluate(expr, &result, 0, NULL), SIMPLE_EXPR_INVALID); + + BLI_simple_expr_free(expr); +} + +TEST(simple_expr, Error_ArgumentCount) +{ + ParsedSimpleExpr *expr = parse_for_eval("x", false); + double result; + + EXPECT_EQ(BLI_simple_expr_evaluate(expr, &result, 0, NULL), SIMPLE_EXPR_FATAL_ERROR); + + BLI_simple_expr_free(expr); +} diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index 7be18330ac3..1db7949d3a5 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -55,6 +55,7 @@ BLENDER_TEST(BLI_math_geom "bf_blenlib") BLENDER_TEST(BLI_memiter "bf_blenlib") BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}") BLENDER_TEST(BLI_polyfill_2d "bf_blenlib") +BLENDER_TEST(BLI_simple_expr "bf_blenlib") BLENDER_TEST(BLI_stack "bf_blenlib") BLENDER_TEST(BLI_string "bf_blenlib") BLENDER_TEST(BLI_string_utf8 "bf_blenlib") -- cgit v1.2.3