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

1 files changed, 131 insertions, 12 deletions

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: