doxygen: add newline after \file
[blender.git] / source / blender / blenlib / intern / expr_pylike_eval.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2018 Blender Foundation, Alexander Gavrilov
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bli
22  *
23  * Simple evaluator for a subset of Python expressions that can be
24  * computed using purely double precision floating point values.
25  *
26  * Supported subset:
27  *
28  *  - Identifiers use only ASCII characters.
29  *  - Literals:
30  *      floating point and decimal integer.
31  *  - Constants:
32  *      pi, True, False
33  *  - Operators:
34  *      +, -, *, /, ==, !=, <, <=, >, >=, and, or, not, ternary if
35  *  - Functions:
36  *      min, max, radians, degrees,
37  *      abs, fabs, floor, ceil, trunc, int,
38  *      sin, cos, tan, asin, acos, atan, atan2,
39  *      exp, log, sqrt, pow, fmod
40  *
41  * The implementation has no global state and can be used multithreaded.
42  */
43
44 #include <math.h>
45 #include <stdio.h>
46 #include <stddef.h>
47 #include <string.h>
48 #include <float.h>
49 #include <ctype.h>
50 #include <stdlib.h>
51 #include <fenv.h>
52
53 #include "MEM_guardedalloc.h"
54
55 #include "BLI_expr_pylike_eval.h"
56 #include "BLI_utildefines.h"
57 #include "BLI_math_base.h"
58 #include "BLI_alloca.h"
59
60 #ifdef _MSC_VER
61 #pragma fenv_access (on)
62 #endif
63
64 /* -------------------------------------------------------------------- */
65 /** \name Internal Types
66  * \{ */
67
68 typedef enum eOpCode {
69         /* Double constant: (-> dval) */
70         OPCODE_CONST,
71         /* 1 argument function call: (a -> func1(a)) */
72         OPCODE_FUNC1,
73         /* 2 argument function call: (a b -> func2(a,b)) */
74         OPCODE_FUNC2,
75         /* Parameter access: (-> params[ival]) */
76         OPCODE_PARAMETER,
77         /* Minimum of multiple inputs: (a b c... -> min); ival = arg count */
78         OPCODE_MIN,
79         /* Maximum of multiple inputs: (a b c... -> max); ival = arg count */
80         OPCODE_MAX,
81         /* Jump (pc += jmp_offset) */
82         OPCODE_JMP,
83         /* Pop and jump if zero: (a -> ); JUMP IF NOT a */
84         OPCODE_JMP_ELSE,
85         /* Jump if nonzero, or pop: (a -> a JUMP) IF a ELSE (a -> ) */
86         OPCODE_JMP_OR,
87         /* Jump if zero, or pop: (a -> a JUMP) IF NOT a ELSE (a -> )  */
88         OPCODE_JMP_AND,
89         /* For comparison chaining: (a b -> 0 JUMP) IF NOT func2(a,b) ELSE (a b -> b) */
90         OPCODE_CMP_CHAIN,
91 } eOpCode;
92
93 typedef double (*UnaryOpFunc)(double);
94 typedef double (*BinaryOpFunc)(double, double);
95
96 typedef struct ExprOp {
97         eOpCode opcode;
98
99         int jmp_offset;
100
101         union {
102                 int ival;
103                 double dval;
104                 void *ptr;
105                 UnaryOpFunc func1;
106                 BinaryOpFunc func2;
107         } arg;
108 } ExprOp;
109
110 struct ExprPyLike_Parsed {
111         int ops_count;
112         int max_stack;
113
114         ExprOp ops[];
115 };
116
117 /** \} */
118
119 /* -------------------------------------------------------------------- */
120 /** \name Public API
121  * \{ */
122
123 /** Free the parsed data; NULL argument is ok. */
124 void BLI_expr_pylike_free(ExprPyLike_Parsed *expr)
125 {
126         if (expr != NULL) {
127                 MEM_freeN(expr);
128         }
129 }
130
131 /** Check if the parsing result is valid for evaluation. */
132 bool BLI_expr_pylike_is_valid(ExprPyLike_Parsed *expr)
133 {
134         return expr != NULL && expr->ops_count > 0;
135 }
136
137 /** Check if the parsed expression always evaluates to the same value. */
138 bool BLI_expr_pylike_is_constant(ExprPyLike_Parsed *expr)
139 {
140         return expr != NULL && expr->ops_count == 1 && expr->ops[0].opcode == OPCODE_CONST;
141 }
142
143 /** \} */
144
145 /* -------------------------------------------------------------------- */
146 /** \name Stack Machine Evaluation
147  * \{ */
148
149 /**
150  * Evaluate the expression with the given parameters.
151  * The order and number of parameters must match the names given to parse.
152  */
153 eExprPyLike_EvalStatus BLI_expr_pylike_eval(
154         ExprPyLike_Parsed *expr,
155         const double *param_values, int param_values_len,
156         double *r_result)
157 {
158         *r_result = 0.0;
159
160         if (!BLI_expr_pylike_is_valid(expr)) {
161                 return EXPR_PYLIKE_INVALID;
162         }
163
164 #define FAIL_IF(condition) if (condition) { return EXPR_PYLIKE_FATAL_ERROR; }
165
166         /* Check the stack requirement is at least remotely sane and allocate on the actual stack. */
167         FAIL_IF(expr->max_stack <= 0 || expr->max_stack > 1000);
168
169         double *stack = BLI_array_alloca(stack, expr->max_stack);
170
171         /* Evaluate expression. */
172         ExprOp *ops = expr->ops;
173         int sp = 0, pc;
174
175         feclearexcept(FE_ALL_EXCEPT);
176
177         for (pc = 0; pc >= 0 && pc < expr->ops_count; pc++) {
178                 switch (ops[pc].opcode) {
179                         /* Arithmetic */
180                         case OPCODE_CONST:
181                                 FAIL_IF(sp >= expr->max_stack);
182                                 stack[sp++] = ops[pc].arg.dval;
183                                 break;
184                         case OPCODE_PARAMETER:
185                                 FAIL_IF(sp >= expr->max_stack || ops[pc].arg.ival >= param_values_len);
186                                 stack[sp++] = param_values[ops[pc].arg.ival];
187                                 break;
188                         case OPCODE_FUNC1:
189                                 FAIL_IF(sp < 1);
190                                 stack[sp - 1] = ops[pc].arg.func1(stack[sp - 1]);
191                                 break;
192                         case OPCODE_FUNC2:
193                                 FAIL_IF(sp < 2);
194                                 stack[sp - 2] = ops[pc].arg.func2(stack[sp - 2], stack[sp - 1]);
195                                 sp--;
196                                 break;
197                         case OPCODE_MIN:
198                                 FAIL_IF(sp < ops[pc].arg.ival);
199                                 for (int j = 1; j < ops[pc].arg.ival; j++, sp--) {
200                                         CLAMP_MAX(stack[sp - 2], stack[sp - 1]);
201                                 }
202                                 break;
203                         case OPCODE_MAX:
204                                 FAIL_IF(sp < ops[pc].arg.ival);
205                                 for (int j = 1; j < ops[pc].arg.ival; j++, sp--) {
206                                         CLAMP_MIN(stack[sp - 2], stack[sp - 1]);
207                                 }
208                                 break;
209
210                         /* Jumps */
211                         case OPCODE_JMP:
212                                 pc += ops[pc].jmp_offset;
213                                 break;
214                         case OPCODE_JMP_ELSE:
215                                 FAIL_IF(sp < 1);
216                                 if (!stack[--sp]) {
217                                         pc += ops[pc].jmp_offset;
218                                 }
219                                 break;
220                         case OPCODE_JMP_OR:
221                         case OPCODE_JMP_AND:
222                                 FAIL_IF(sp < 1);
223                                 if (!stack[sp - 1] == !(ops[pc].opcode == OPCODE_JMP_OR)) {
224                                         pc += ops[pc].jmp_offset;
225                                 }
226                                 else {
227                                         sp--;
228                                 }
229                                 break;
230
231                         /* For chaining comparisons, i.e. "a < b < c" as "a < b and b < c" */
232                         case OPCODE_CMP_CHAIN:
233                                 FAIL_IF(sp < 2);
234                                 /* If comparison fails, return 0 and jump to end. */
235                                 if (!ops[pc].arg.func2(stack[sp - 2], stack[sp - 1])) {
236                                         stack[sp - 2] = 0.0;
237                                         pc += ops[pc].jmp_offset;
238                                 }
239                                 /* Otherwise keep b on the stack and proceed. */
240                                 else {
241                                         stack[sp - 2] = stack[sp - 1];
242                                 }
243                                 sp--;
244                                 break;
245
246                         default:
247                                 return EXPR_PYLIKE_FATAL_ERROR;
248                 }
249         }
250
251         FAIL_IF(sp != 1 || pc != expr->ops_count);
252
253 #undef FAIL_IF
254
255         *r_result = stack[0];
256
257         /* Detect floating point evaluation errors. */
258         int flags = fetestexcept(FE_DIVBYZERO | FE_INVALID);
259         if (flags) {
260                 return (flags & FE_INVALID) ? EXPR_PYLIKE_MATH_ERROR : EXPR_PYLIKE_DIV_BY_ZERO;
261         }
262
263         return EXPR_PYLIKE_SUCCESS;
264 }
265
266 /** \} */
267
268 /* -------------------------------------------------------------------- */
269 /** \name Built-In Operations
270  * \{ */
271
272 static double op_negate(double arg)
273 {
274         return -arg;
275 }
276
277 static double op_mul(double a, double b)
278 {
279         return a * b;
280 }
281
282 static double op_div(double a, double b)
283 {
284         return a / b;
285 }
286
287 static double op_add(double a, double b)
288 {
289         return a + b;
290 }
291
292 static double op_sub(double a, double b)
293 {
294         return a - b;
295 }
296
297 static double op_radians(double arg)
298 {
299         return arg * M_PI / 180.0;
300 }
301
302 static double op_degrees(double arg)
303 {
304         return arg * 180.0 / M_PI;
305 }
306
307 static double op_not(double a)
308 {
309         return a ? 0.0 : 1.0;
310 }
311
312 static double op_eq(double a, double b)
313 {
314         return a == b ? 1.0 : 0.0;
315 }
316
317 static double op_ne(double a, double b)
318 {
319         return a != b ? 1.0 : 0.0;
320 }
321
322 static double op_lt(double a, double b)
323 {
324         return a < b ? 1.0 : 0.0;
325 }
326
327 static double op_le(double a, double b)
328 {
329         return a <= b ? 1.0 : 0.0;
330 }
331
332 static double op_gt(double a, double b)
333 {
334         return a > b ? 1.0 : 0.0;
335 }
336
337 static double op_ge(double a, double b)
338 {
339         return a >= b ? 1.0 : 0.0;
340 }
341
342 typedef struct BuiltinConstDef {
343         const char *name;
344         double value;
345 } BuiltinConstDef;
346
347 static BuiltinConstDef builtin_consts[] = {
348         { "pi", M_PI },
349         { "True", 1.0 },
350         { "False", 0.0 },
351         { NULL, 0.0 }
352 };
353
354 typedef struct BuiltinOpDef {
355         const char *name;
356         eOpCode op;
357         void *funcptr;
358 } BuiltinOpDef;
359
360 static BuiltinOpDef builtin_ops[] = {
361         { "radians", OPCODE_FUNC1, op_radians },
362         { "degrees", OPCODE_FUNC1, op_degrees },
363         { "abs", OPCODE_FUNC1, abs },
364         { "fabs", OPCODE_FUNC1, abs },
365         { "floor", OPCODE_FUNC1, floor },
366         { "ceil", OPCODE_FUNC1, ceil },
367         { "trunc", OPCODE_FUNC1, trunc },
368         { "int", OPCODE_FUNC1, trunc },
369         { "sin", OPCODE_FUNC1, sin },
370         { "cos", OPCODE_FUNC1, cos },
371         { "tan", OPCODE_FUNC1, tan },
372         { "asin", OPCODE_FUNC1, asin },
373         { "acos", OPCODE_FUNC1, acos },
374         { "atan", OPCODE_FUNC1, atan },
375         { "atan2", OPCODE_FUNC2, atan2 },
376         { "exp", OPCODE_FUNC1, exp },
377         { "log", OPCODE_FUNC1, log },
378         { "sqrt", OPCODE_FUNC1, sqrt },
379         { "pow", OPCODE_FUNC2, pow },
380         { "fmod", OPCODE_FUNC2, fmod },
381         { NULL, OPCODE_CONST, NULL }
382 };
383
384 /** \} */
385
386 /* -------------------------------------------------------------------- */
387 /** \name Expression Parser State
388  * \{ */
389
390 #define MAKE_CHAR2(a, b) (((a) << 8) | (b))
391
392 #define CHECK_ERROR(condition) if (!(condition)) { return false; }
393
394 /* For simplicity simple token types are represented by their own character;
395  * these are special identifiers for multi-character tokens. */
396 #define TOKEN_ID        MAKE_CHAR2('I', 'D')
397 #define TOKEN_NUMBER    MAKE_CHAR2('0', '0')
398 #define TOKEN_GE        MAKE_CHAR2('>', '=')
399 #define TOKEN_LE        MAKE_CHAR2('<', '=')
400 #define TOKEN_NE        MAKE_CHAR2('!', '=')
401 #define TOKEN_EQ        MAKE_CHAR2('=', '=')
402 #define TOKEN_AND       MAKE_CHAR2('A', 'N')
403 #define TOKEN_OR        MAKE_CHAR2('O', 'R')
404 #define TOKEN_NOT       MAKE_CHAR2('N', 'O')
405 #define TOKEN_IF        MAKE_CHAR2('I', 'F')
406 #define TOKEN_ELSE      MAKE_CHAR2('E', 'L')
407
408 static const char *token_eq_characters = "!=><";
409 static const char *token_characters = "~`!@#$%^&*+-=/\\?:;<>(){}[]|.,\"'";
410
411 typedef struct KeywordTokenDef {
412         const char *name;
413         short token;
414 } KeywordTokenDef;
415
416 static KeywordTokenDef keyword_list[] = {
417     { "and", TOKEN_AND },
418     { "or", TOKEN_OR },
419     { "not", TOKEN_NOT },
420     { "if", TOKEN_IF },
421     { "else", TOKEN_ELSE },
422     { NULL, TOKEN_ID }
423 };
424
425 typedef struct ExprParseState {
426         int param_names_len;
427         const char **param_names;
428
429         /* Original expression */
430         const char *expr;
431         const char *cur;
432
433         /* Current token */
434         short token;
435         char *tokenbuf;
436         double tokenval;
437
438         /* Opcode buffer */
439         int ops_count, max_ops, last_jmp;
440         ExprOp *ops;
441
442         /* Stack space requirement tracking */
443         int stack_ptr, max_stack;
444 } ExprParseState;
445
446 /* Reserve space for the specified number of operations in the buffer. */
447 static ExprOp *parse_alloc_ops(ExprParseState *state, int count)
448 {
449         if (state->ops_count + count > state->max_ops) {
450                 state->max_ops = power_of_2_max_i(state->ops_count + count);
451                 state->ops = MEM_reallocN(state->ops, state->max_ops * sizeof(ExprOp));
452         }
453
454         ExprOp *op = &state->ops[state->ops_count];
455         state->ops_count += count;
456         return op;
457 }
458
459 /* Add one operation and track stack usage. */
460 static ExprOp *parse_add_op(ExprParseState *state, eOpCode code, int stack_delta)
461 {
462         /* track evaluation stack depth */
463         state->stack_ptr += stack_delta;
464         CLAMP_MIN(state->stack_ptr, 0);
465         CLAMP_MIN(state->max_stack, state->stack_ptr);
466
467         /* allocate the new instruction */
468         ExprOp *op = parse_alloc_ops(state, 1);
469         memset(op, 0, sizeof(ExprOp));
470         op->opcode = code;
471         return op;
472 }
473
474 /* Add one jump operation and return an index for parse_set_jump. */
475 static int parse_add_jump(ExprParseState *state, eOpCode code)
476 {
477         parse_add_op(state, code, -1);
478         return state->last_jmp = state->ops_count;
479 }
480
481 /* Set the jump offset in a previously added jump operation. */
482 static void parse_set_jump(ExprParseState *state, int jump)
483 {
484         state->last_jmp = state->ops_count;
485         state->ops[jump - 1].jmp_offset = state->ops_count - jump;
486 }
487
488 /* Add a function call operation, applying constant folding when possible. */
489 static bool parse_add_func(ExprParseState *state, eOpCode code, int args, void *funcptr)
490 {
491         ExprOp *prev_ops = &state->ops[state->ops_count];
492         int jmp_gap = state->ops_count - state->last_jmp;
493
494         feclearexcept(FE_ALL_EXCEPT);
495
496         switch (code) {
497                 case OPCODE_FUNC1:
498                         CHECK_ERROR(args == 1);
499
500                         if (jmp_gap >= 1 && prev_ops[-1].opcode == OPCODE_CONST) {
501                                 UnaryOpFunc func = funcptr;
502
503                                 double result = func(prev_ops[-1].arg.dval);
504
505                                 if (fetestexcept(FE_DIVBYZERO | FE_INVALID) == 0) {
506                                         prev_ops[-1].arg.dval = result;
507                                         return true;
508                                 }
509                         }
510                         break;
511
512                 case OPCODE_FUNC2:
513                         CHECK_ERROR(args == 2);
514
515                         if (jmp_gap >= 2 && prev_ops[-2].opcode == OPCODE_CONST && prev_ops[-1].opcode == OPCODE_CONST) {
516                                 BinaryOpFunc func = funcptr;
517
518                                 double result = func(prev_ops[-2].arg.dval, prev_ops[-1].arg.dval);
519
520                                 if (fetestexcept(FE_DIVBYZERO | FE_INVALID) == 0) {
521                                         prev_ops[-2].arg.dval = result;
522                                         state->ops_count--;
523                                         state->stack_ptr--;
524                                         return true;
525                                 }
526                         }
527                         break;
528
529                 default:
530                         BLI_assert(false);
531                         return false;
532         }
533
534         parse_add_op(state, code, 1 - args)->arg.ptr = funcptr;
535         return true;
536 }
537
538 /* Extract the next token from raw characters. */
539 static bool parse_next_token(ExprParseState *state)
540 {
541         /* Skip whitespace. */
542         while (isspace(*state->cur)) {
543                 state->cur++;
544         }
545
546         /* End of string. */
547         if (*state->cur == 0) {
548                 state->token = 0;
549                 return true;
550         }
551
552         /* Floating point numbers. */
553         if (isdigit(*state->cur) || (state->cur[0] == '.' && isdigit(state->cur[1]))) {
554                 char *end, *out = state->tokenbuf;
555                 bool is_float = false;
556
557                 while (isdigit(*state->cur))
558                         *out++ = *state->cur++;
559
560                 if (*state->cur == '.') {
561                         is_float = true;
562                         *out++ = *state->cur++;
563
564                         while (isdigit(*state->cur))
565                                 *out++ = *state->cur++;
566                 }
567
568                 if (ELEM(*state->cur, 'e', 'E')) {
569                         is_float = true;
570                         *out++ = *state->cur++;
571
572                         if (ELEM(*state->cur, '+', '-'))
573                                 *out++ = *state->cur++;
574
575                         CHECK_ERROR(isdigit(*state->cur));
576
577                         while (isdigit(*state->cur))
578                                 *out++ = *state->cur++;
579                 }
580
581                 *out = 0;
582
583                 /* Forbid C-style octal constants. */
584                 if (!is_float && state->tokenbuf[0] == '0') {
585                         for (char *p = state->tokenbuf + 1; *p; p++) {
586                                 if (*p != '0') {
587                                         return false;
588                                 }
589                         }
590                 }
591
592                 state->token = TOKEN_NUMBER;
593                 state->tokenval = strtod(state->tokenbuf, &end);
594                 return (end == out);
595         }
596
597         /* ?= tokens */
598         if (state->cur[1] == '=' && strchr(token_eq_characters, state->cur[0])) {
599                 state->token = MAKE_CHAR2(state->cur[0], state->cur[1]);
600                 state->cur += 2;
601                 return true;
602         }
603
604         /* Special characters (single character tokens) */
605         if (strchr(token_characters, *state->cur)) {
606                 state->token = *state->cur++;
607                 return true;
608         }
609
610         /* Identifiers */
611         if (isalpha(*state->cur) || ELEM(*state->cur, '_')) {
612                 char *out = state->tokenbuf;
613
614                 while (isalnum(*state->cur) || ELEM(*state->cur, '_'))
615                         *out++ = *state->cur++;
616
617                 *out = 0;
618
619                 for (int i = 0; keyword_list[i].name; i++) {
620                         if (STREQ(state->tokenbuf, keyword_list[i].name)) {
621                                 state->token = keyword_list[i].token;
622                                 return true;
623                         }
624                 }
625
626                 state->token = TOKEN_ID;
627                 return true;
628         }
629
630         return false;
631 }
632
633 /** \} */
634
635 /* -------------------------------------------------------------------- */
636 /** \name Recursive Descent Parser
637  * \{ */
638
639 static bool parse_expr(ExprParseState *state);
640
641 static int parse_function_args(ExprParseState *state)
642 {
643         if (!parse_next_token(state) || state->token != '(' || !parse_next_token(state)) {
644                 return -1;
645         }
646
647         int arg_count = 0;
648
649         for (;;) {
650                 if (!parse_expr(state)) {
651                         return -1;
652                 }
653
654                 arg_count++;
655
656                 switch (state->token) {
657                         case ',':
658                                 if (!parse_next_token(state)) {
659                                         return -1;
660                                 }
661                                 break;
662
663                         case ')':
664                                 if (!parse_next_token(state)) {
665                                         return -1;
666                                 }
667                                 return arg_count;
668
669                         default:
670                                 return -1;
671                 }
672         }
673 }
674
675 static bool parse_unary(ExprParseState *state)
676 {
677         int i;
678
679         switch (state->token) {
680                 case '+':
681                         return parse_next_token(state) && parse_unary(state);
682
683                 case '-':
684                         CHECK_ERROR(parse_next_token(state) && parse_unary(state));
685                         parse_add_func(state, OPCODE_FUNC1, 1, op_negate);
686                         return true;
687
688                 case '(':
689                         return parse_next_token(state) &&
690                                parse_expr(state) &&
691                                state->token == ')' &&
692                                parse_next_token(state);
693
694                 case TOKEN_NUMBER:
695                         parse_add_op(state, OPCODE_CONST, 1)->arg.dval = state->tokenval;
696                         return parse_next_token(state);
697
698                 case TOKEN_ID:
699                         /* Parameters: search in reverse order in case of duplicate names -
700                          * the last one should win. */
701                         for (i = state->param_names_len - 1; i >= 0; i--) {
702                                 if (STREQ(state->tokenbuf, state->param_names[i])) {
703                                         parse_add_op(state, OPCODE_PARAMETER, 1)->arg.ival = i;
704                                         return parse_next_token(state);
705                                 }
706                         }
707
708                         /* Ordinary builtin constants. */
709                         for (i = 0; builtin_consts[i].name; i++) {
710                                 if (STREQ(state->tokenbuf, builtin_consts[i].name)) {
711                                         parse_add_op(state, OPCODE_CONST, 1)->arg.dval = builtin_consts[i].value;
712                                         return parse_next_token(state);
713                                 }
714                         }
715
716                         /* Ordinary builtin functions. */
717                         for (i = 0; builtin_ops[i].name; i++) {
718                                 if (STREQ(state->tokenbuf, builtin_ops[i].name)) {
719                                         int args = parse_function_args(state);
720
721                                         return parse_add_func(state, builtin_ops[i].op, args, builtin_ops[i].funcptr);
722                                 }
723                         }
724
725                         /* Specially supported functions. */
726                         if (STREQ(state->tokenbuf, "min")) {
727                                 int cnt = parse_function_args(state);
728                                 CHECK_ERROR(cnt > 0);
729
730                                 parse_add_op(state, OPCODE_MIN, 1 - cnt)->arg.ival = cnt;
731                                 return true;
732                         }
733
734                         if (STREQ(state->tokenbuf, "max")) {
735                                 int cnt = parse_function_args(state);
736                                 CHECK_ERROR(cnt > 0);
737
738                                 parse_add_op(state, OPCODE_MAX, 1 - cnt)->arg.ival = cnt;
739                                 return true;
740                         }
741
742                         return false;
743
744                 default:
745                         return false;
746         }
747 }
748
749 static bool parse_mul(ExprParseState *state)
750 {
751         CHECK_ERROR(parse_unary(state));
752
753         for (;;) {
754                 switch (state->token) {
755                         case '*':
756                                 CHECK_ERROR(parse_next_token(state) && parse_unary(state));
757                                 parse_add_func(state, OPCODE_FUNC2, 2, op_mul);
758                                 break;
759
760                         case '/':
761                                 CHECK_ERROR(parse_next_token(state) && parse_unary(state));
762                                 parse_add_func(state, OPCODE_FUNC2, 2, op_div);
763                                 break;
764
765                         default:
766                                 return true;
767                 }
768         }
769 }
770
771 static bool parse_add(ExprParseState *state)
772 {
773         CHECK_ERROR(parse_mul(state));
774
775         for (;;) {
776                 switch (state->token) {
777                         case '+':
778                                 CHECK_ERROR(parse_next_token(state) && parse_mul(state));
779                                 parse_add_func(state, OPCODE_FUNC2, 2, op_add);
780                                 break;
781
782                         case '-':
783                                 CHECK_ERROR(parse_next_token(state) && parse_mul(state));
784                                 parse_add_func(state, OPCODE_FUNC2, 2, op_sub);
785                                 break;
786
787                         default:
788                                 return true;
789                 }
790         }
791 }
792
793 static BinaryOpFunc parse_get_cmp_func(short token)
794 {
795         switch (token) {
796                 case TOKEN_EQ:
797                         return op_eq;
798                 case TOKEN_NE:
799                         return op_ne;
800                 case '>':
801                         return op_gt;
802                 case TOKEN_GE:
803                         return op_ge;
804                 case '<':
805                         return op_lt;
806                 case TOKEN_LE:
807                         return op_le;
808                 default:
809                         return NULL;
810         }
811 }
812
813 static bool parse_cmp_chain(ExprParseState *state, BinaryOpFunc cur_func)
814 {
815         BinaryOpFunc next_func = parse_get_cmp_func(state->token);
816
817         if (next_func) {
818                 parse_add_op(state, OPCODE_CMP_CHAIN, -1)->arg.func2 = cur_func;
819                 int jump = state->last_jmp = state->ops_count;
820
821                 CHECK_ERROR(parse_next_token(state) && parse_add(state));
822                 CHECK_ERROR(parse_cmp_chain(state, next_func));
823
824                 parse_set_jump(state, jump);
825         }
826         else {
827                 parse_add_func(state, OPCODE_FUNC2, 2, cur_func);
828         }
829
830         return true;
831 }
832
833 static bool parse_cmp(ExprParseState *state)
834 {
835         CHECK_ERROR(parse_add(state));
836
837         BinaryOpFunc func = parse_get_cmp_func(state->token);
838
839         if (func) {
840                 CHECK_ERROR(parse_next_token(state) && parse_add(state));
841
842                 return parse_cmp_chain(state, func);
843         }
844
845         return true;
846 }
847
848 static bool parse_not(ExprParseState *state)
849 {
850         if (state->token == TOKEN_NOT) {
851                 CHECK_ERROR(parse_next_token(state) && parse_not(state));
852                 parse_add_func(state, OPCODE_FUNC1, 1, op_not);
853                 return true;
854         }
855
856         return parse_cmp(state);
857 }
858
859 static bool parse_and(ExprParseState *state)
860 {
861         CHECK_ERROR(parse_not(state));
862
863         if (state->token == TOKEN_AND) {
864                 int jump = parse_add_jump(state, OPCODE_JMP_AND);
865
866                 CHECK_ERROR(parse_next_token(state) && parse_and(state));
867
868                 parse_set_jump(state, jump);
869         }
870
871         return true;
872 }
873
874 static bool parse_or(ExprParseState *state)
875 {
876         CHECK_ERROR(parse_and(state));
877
878         if (state->token == TOKEN_OR) {
879                 int jump = parse_add_jump(state, OPCODE_JMP_OR);
880
881                 CHECK_ERROR(parse_next_token(state) && parse_or(state));
882
883                 parse_set_jump(state, jump);
884         }
885
886         return true;
887 }
888
889 static bool parse_expr(ExprParseState *state)
890 {
891         /* Temporarily set the constant expression evaluation barrier */
892         int prev_last_jmp = state->last_jmp;
893         int start = state->last_jmp = state->ops_count;
894
895         CHECK_ERROR(parse_or(state));
896
897         if (state->token == TOKEN_IF) {
898                 /* Ternary IF expression in python requires swapping the
899                  * main body with condition, so stash the body opcodes. */
900                 int size = state->ops_count - start;
901                 int bytes = size * sizeof(ExprOp);
902
903                 ExprOp *body = MEM_mallocN(bytes, "driver if body");
904                 memcpy(body, state->ops + start, bytes);
905
906                 state->last_jmp = state->ops_count = start;
907                 state->stack_ptr--;
908
909                 /* Parse condition. */
910                 if (!parse_next_token(state) || !parse_or(state) ||
911                     state->token != TOKEN_ELSE || !parse_next_token(state))
912                 {
913                         MEM_freeN(body);
914                         return false;
915                 }
916
917                 int jmp_else = parse_add_jump(state, OPCODE_JMP_ELSE);
918
919                 /* Add body back. */
920                 memcpy(parse_alloc_ops(state, size), body, bytes);
921                 MEM_freeN(body);
922
923                 state->stack_ptr++;
924
925                 int jmp_end = parse_add_jump(state, OPCODE_JMP);
926
927                 /* Parse the else block. */
928                 parse_set_jump(state, jmp_else);
929
930                 CHECK_ERROR(parse_expr(state));
931
932                 parse_set_jump(state, jmp_end);
933         }
934         /* If no actual jumps happened, restore previous barrier */
935         else if (state->last_jmp == start) {
936                 state->last_jmp = prev_last_jmp;
937         }
938
939         return true;
940 }
941
942 /** \} */
943
944 /* -------------------------------------------------------------------- */
945 /** \name Main Parsing Function
946  * \{ */
947
948 /**
949  * Compile the expression and return the result.
950  *
951  * Parse the expression for evaluation later.
952  * Returns non-NULL even on failure; use is_valid to check.
953  */
954 ExprPyLike_Parsed *BLI_expr_pylike_parse(const char *expression, const char **param_names, int param_names_len)
955 {
956         /* Prepare the parser state. */
957         ExprParseState state;
958         memset(&state, 0, sizeof(state));
959
960         state.cur = state.expr = expression;
961
962         state.param_names_len = param_names_len;
963         state.param_names = param_names;
964
965         state.tokenbuf = MEM_mallocN(strlen(expression) + 1, __func__);
966
967         state.max_ops = 16;
968         state.ops = MEM_mallocN(state.max_ops * sizeof(ExprOp), __func__);
969
970         /* Parse the expression. */
971         ExprPyLike_Parsed *expr;
972
973         if (parse_next_token(&state) && parse_expr(&state) && state.token == 0) {
974                 BLI_assert(state.stack_ptr == 1);
975
976                 int bytesize = sizeof(ExprPyLike_Parsed) + state.ops_count * sizeof(ExprOp);
977
978                 expr = MEM_mallocN(bytesize, "ExprPyLike_Parsed");
979                 expr->ops_count = state.ops_count;
980                 expr->max_stack = state.max_stack;
981
982                 memcpy(expr->ops, state.ops, state.ops_count * sizeof(ExprOp));
983         }
984         else {
985                 /* Always return a non-NULL object so that parse failure can be cached. */
986                 expr = MEM_callocN(sizeof(ExprPyLike_Parsed), "ExprPyLike_Parsed(empty)");
987         }
988
989         MEM_freeN(state.tokenbuf);
990         MEM_freeN(state.ops);
991         return expr;
992 }
993
994 /** \} */