1/**************************************************************************/
2/* expression.cpp */
3/**************************************************************************/
4/* This file is part of: */
5/* GODOT ENGINE */
6/* https://godotengine.org */
7/**************************************************************************/
8/* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
9/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
10/* */
11/* Permission is hereby granted, free of charge, to any person obtaining */
12/* a copy of this software and associated documentation files (the */
13/* "Software"), to deal in the Software without restriction, including */
14/* without limitation the rights to use, copy, modify, merge, publish, */
15/* distribute, sublicense, and/or sell copies of the Software, and to */
16/* permit persons to whom the Software is furnished to do so, subject to */
17/* the following conditions: */
18/* */
19/* The above copyright notice and this permission notice shall be */
20/* included in all copies or substantial portions of the Software. */
21/* */
22/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
23/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
24/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
25/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
26/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
27/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
28/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
29/**************************************************************************/
30
31#include "expression.h"
32
33#include "core/io/marshalls.h"
34#include "core/math/math_funcs.h"
35#include "core/object/class_db.h"
36#include "core/object/ref_counted.h"
37#include "core/os/os.h"
38#include "core/variant/variant_parser.h"
39
40Error Expression::_get_token(Token &r_token) {
41 while (true) {
42#define GET_CHAR() (str_ofs >= expression.length() ? 0 : expression[str_ofs++])
43
44 char32_t cchar = GET_CHAR();
45
46 switch (cchar) {
47 case 0: {
48 r_token.type = TK_EOF;
49 return OK;
50 }
51 case '{': {
52 r_token.type = TK_CURLY_BRACKET_OPEN;
53 return OK;
54 }
55 case '}': {
56 r_token.type = TK_CURLY_BRACKET_CLOSE;
57 return OK;
58 }
59 case '[': {
60 r_token.type = TK_BRACKET_OPEN;
61 return OK;
62 }
63 case ']': {
64 r_token.type = TK_BRACKET_CLOSE;
65 return OK;
66 }
67 case '(': {
68 r_token.type = TK_PARENTHESIS_OPEN;
69 return OK;
70 }
71 case ')': {
72 r_token.type = TK_PARENTHESIS_CLOSE;
73 return OK;
74 }
75 case ',': {
76 r_token.type = TK_COMMA;
77 return OK;
78 }
79 case ':': {
80 r_token.type = TK_COLON;
81 return OK;
82 }
83 case '$': {
84 r_token.type = TK_INPUT;
85 int index = 0;
86 do {
87 if (!is_digit(expression[str_ofs])) {
88 _set_error("Expected number after '$'");
89 r_token.type = TK_ERROR;
90 return ERR_PARSE_ERROR;
91 }
92 index *= 10;
93 index += expression[str_ofs] - '0';
94 str_ofs++;
95
96 } while (is_digit(expression[str_ofs]));
97
98 r_token.value = index;
99 return OK;
100 }
101 case '=': {
102 cchar = GET_CHAR();
103 if (cchar == '=') {
104 r_token.type = TK_OP_EQUAL;
105 } else {
106 _set_error("Expected '='");
107 r_token.type = TK_ERROR;
108 return ERR_PARSE_ERROR;
109 }
110 return OK;
111 }
112 case '!': {
113 if (expression[str_ofs] == '=') {
114 r_token.type = TK_OP_NOT_EQUAL;
115 str_ofs++;
116 } else {
117 r_token.type = TK_OP_NOT;
118 }
119 return OK;
120 }
121 case '>': {
122 if (expression[str_ofs] == '=') {
123 r_token.type = TK_OP_GREATER_EQUAL;
124 str_ofs++;
125 } else if (expression[str_ofs] == '>') {
126 r_token.type = TK_OP_SHIFT_RIGHT;
127 str_ofs++;
128 } else {
129 r_token.type = TK_OP_GREATER;
130 }
131 return OK;
132 }
133 case '<': {
134 if (expression[str_ofs] == '=') {
135 r_token.type = TK_OP_LESS_EQUAL;
136 str_ofs++;
137 } else if (expression[str_ofs] == '<') {
138 r_token.type = TK_OP_SHIFT_LEFT;
139 str_ofs++;
140 } else {
141 r_token.type = TK_OP_LESS;
142 }
143 return OK;
144 }
145 case '+': {
146 r_token.type = TK_OP_ADD;
147 return OK;
148 }
149 case '-': {
150 r_token.type = TK_OP_SUB;
151 return OK;
152 }
153 case '/': {
154 r_token.type = TK_OP_DIV;
155 return OK;
156 }
157 case '*': {
158 if (expression[str_ofs] == '*') {
159 r_token.type = TK_OP_POW;
160 str_ofs++;
161 } else {
162 r_token.type = TK_OP_MUL;
163 }
164 return OK;
165 }
166 case '%': {
167 r_token.type = TK_OP_MOD;
168 return OK;
169 }
170 case '&': {
171 if (expression[str_ofs] == '&') {
172 r_token.type = TK_OP_AND;
173 str_ofs++;
174 } else {
175 r_token.type = TK_OP_BIT_AND;
176 }
177 return OK;
178 }
179 case '|': {
180 if (expression[str_ofs] == '|') {
181 r_token.type = TK_OP_OR;
182 str_ofs++;
183 } else {
184 r_token.type = TK_OP_BIT_OR;
185 }
186 return OK;
187 }
188 case '^': {
189 r_token.type = TK_OP_BIT_XOR;
190
191 return OK;
192 }
193 case '~': {
194 r_token.type = TK_OP_BIT_INVERT;
195
196 return OK;
197 }
198 case '\'':
199 case '"': {
200 String str;
201 char32_t prev = 0;
202 while (true) {
203 char32_t ch = GET_CHAR();
204
205 if (ch == 0) {
206 _set_error("Unterminated String");
207 r_token.type = TK_ERROR;
208 return ERR_PARSE_ERROR;
209 } else if (ch == cchar) {
210 // cchar contain a corresponding quote symbol
211 break;
212 } else if (ch == '\\') {
213 //escaped characters...
214
215 char32_t next = GET_CHAR();
216 if (next == 0) {
217 _set_error("Unterminated String");
218 r_token.type = TK_ERROR;
219 return ERR_PARSE_ERROR;
220 }
221 char32_t res = 0;
222
223 switch (next) {
224 case 'b':
225 res = 8;
226 break;
227 case 't':
228 res = 9;
229 break;
230 case 'n':
231 res = 10;
232 break;
233 case 'f':
234 res = 12;
235 break;
236 case 'r':
237 res = 13;
238 break;
239 case 'U':
240 case 'u': {
241 // Hexadecimal sequence.
242 int hex_len = (next == 'U') ? 6 : 4;
243 for (int j = 0; j < hex_len; j++) {
244 char32_t c = GET_CHAR();
245
246 if (c == 0) {
247 _set_error("Unterminated String");
248 r_token.type = TK_ERROR;
249 return ERR_PARSE_ERROR;
250 }
251 if (!is_hex_digit(c)) {
252 _set_error("Malformed hex constant in string");
253 r_token.type = TK_ERROR;
254 return ERR_PARSE_ERROR;
255 }
256 char32_t v;
257 if (is_digit(c)) {
258 v = c - '0';
259 } else if (c >= 'a' && c <= 'f') {
260 v = c - 'a';
261 v += 10;
262 } else if (c >= 'A' && c <= 'F') {
263 v = c - 'A';
264 v += 10;
265 } else {
266 ERR_PRINT("Bug parsing hex constant.");
267 v = 0;
268 }
269
270 res <<= 4;
271 res |= v;
272 }
273
274 } break;
275 default: {
276 res = next;
277 } break;
278 }
279
280 // Parse UTF-16 pair.
281 if ((res & 0xfffffc00) == 0xd800) {
282 if (prev == 0) {
283 prev = res;
284 continue;
285 } else {
286 _set_error("Invalid UTF-16 sequence in string, unpaired lead surrogate");
287 r_token.type = TK_ERROR;
288 return ERR_PARSE_ERROR;
289 }
290 } else if ((res & 0xfffffc00) == 0xdc00) {
291 if (prev == 0) {
292 _set_error("Invalid UTF-16 sequence in string, unpaired trail surrogate");
293 r_token.type = TK_ERROR;
294 return ERR_PARSE_ERROR;
295 } else {
296 res = (prev << 10UL) + res - ((0xd800 << 10UL) + 0xdc00 - 0x10000);
297 prev = 0;
298 }
299 }
300 if (prev != 0) {
301 _set_error("Invalid UTF-16 sequence in string, unpaired lead surrogate");
302 r_token.type = TK_ERROR;
303 return ERR_PARSE_ERROR;
304 }
305 str += res;
306 } else {
307 if (prev != 0) {
308 _set_error("Invalid UTF-16 sequence in string, unpaired lead surrogate");
309 r_token.type = TK_ERROR;
310 return ERR_PARSE_ERROR;
311 }
312 str += ch;
313 }
314 }
315 if (prev != 0) {
316 _set_error("Invalid UTF-16 sequence in string, unpaired lead surrogate");
317 r_token.type = TK_ERROR;
318 return ERR_PARSE_ERROR;
319 }
320
321 r_token.type = TK_CONSTANT;
322 r_token.value = str;
323 return OK;
324
325 } break;
326 default: {
327 if (cchar <= 32) {
328 break;
329 }
330
331 char32_t next_char = (str_ofs >= expression.length()) ? 0 : expression[str_ofs];
332 if (is_digit(cchar) || (cchar == '.' && is_digit(next_char))) {
333 //a number
334
335 String num;
336#define READING_SIGN 0
337#define READING_INT 1
338#define READING_HEX 2
339#define READING_BIN 3
340#define READING_DEC 4
341#define READING_EXP 5
342#define READING_DONE 6
343 int reading = READING_INT;
344
345 char32_t c = cchar;
346 bool exp_sign = false;
347 bool exp_beg = false;
348 bool bin_beg = false;
349 bool hex_beg = false;
350 bool is_float = false;
351 bool is_first_char = true;
352
353 while (true) {
354 switch (reading) {
355 case READING_INT: {
356 if (is_digit(c)) {
357 if (is_first_char && c == '0') {
358 if (next_char == 'b') {
359 reading = READING_BIN;
360 } else if (next_char == 'x') {
361 reading = READING_HEX;
362 }
363 }
364 } else if (c == '.') {
365 reading = READING_DEC;
366 is_float = true;
367 } else if (c == 'e') {
368 reading = READING_EXP;
369 is_float = true;
370 } else {
371 reading = READING_DONE;
372 }
373
374 } break;
375 case READING_BIN: {
376 if (bin_beg && !is_binary_digit(c)) {
377 reading = READING_DONE;
378 } else if (c == 'b') {
379 bin_beg = true;
380 }
381
382 } break;
383 case READING_HEX: {
384 if (hex_beg && !is_hex_digit(c)) {
385 reading = READING_DONE;
386 } else if (c == 'x') {
387 hex_beg = true;
388 }
389
390 } break;
391 case READING_DEC: {
392 if (is_digit(c)) {
393 } else if (c == 'e') {
394 reading = READING_EXP;
395
396 } else {
397 reading = READING_DONE;
398 }
399
400 } break;
401 case READING_EXP: {
402 if (is_digit(c)) {
403 exp_beg = true;
404
405 } else if ((c == '-' || c == '+') && !exp_sign && !exp_beg) {
406 exp_sign = true;
407
408 } else {
409 reading = READING_DONE;
410 }
411 } break;
412 }
413
414 if (reading == READING_DONE) {
415 break;
416 }
417 num += String::chr(c);
418 c = GET_CHAR();
419 is_first_char = false;
420 }
421
422 str_ofs--;
423
424 r_token.type = TK_CONSTANT;
425
426 if (is_float) {
427 r_token.value = num.to_float();
428 } else if (bin_beg) {
429 r_token.value = num.bin_to_int();
430 } else if (hex_beg) {
431 r_token.value = num.hex_to_int();
432 } else {
433 r_token.value = num.to_int();
434 }
435 return OK;
436
437 } else if (is_unicode_identifier_start(cchar)) {
438 String id = String::chr(cchar);
439 cchar = GET_CHAR();
440
441 while (is_unicode_identifier_continue(cchar)) {
442 id += String::chr(cchar);
443 cchar = GET_CHAR();
444 }
445
446 str_ofs--; //go back one
447
448 if (id == "in") {
449 r_token.type = TK_OP_IN;
450 } else if (id == "null") {
451 r_token.type = TK_CONSTANT;
452 r_token.value = Variant();
453 } else if (id == "true") {
454 r_token.type = TK_CONSTANT;
455 r_token.value = true;
456 } else if (id == "false") {
457 r_token.type = TK_CONSTANT;
458 r_token.value = false;
459 } else if (id == "PI") {
460 r_token.type = TK_CONSTANT;
461 r_token.value = Math_PI;
462 } else if (id == "TAU") {
463 r_token.type = TK_CONSTANT;
464 r_token.value = Math_TAU;
465 } else if (id == "INF") {
466 r_token.type = TK_CONSTANT;
467 r_token.value = INFINITY;
468 } else if (id == "NAN") {
469 r_token.type = TK_CONSTANT;
470 r_token.value = NAN;
471 } else if (id == "not") {
472 r_token.type = TK_OP_NOT;
473 } else if (id == "or") {
474 r_token.type = TK_OP_OR;
475 } else if (id == "and") {
476 r_token.type = TK_OP_AND;
477 } else if (id == "self") {
478 r_token.type = TK_SELF;
479 } else {
480 for (int i = 0; i < Variant::VARIANT_MAX; i++) {
481 if (id == Variant::get_type_name(Variant::Type(i))) {
482 r_token.type = TK_BASIC_TYPE;
483 r_token.value = i;
484 return OK;
485 }
486 }
487
488 if (Variant::has_utility_function(id)) {
489 r_token.type = TK_BUILTIN_FUNC;
490 r_token.value = id;
491 return OK;
492 }
493
494 r_token.type = TK_IDENTIFIER;
495 r_token.value = id;
496 }
497
498 return OK;
499
500 } else if (cchar == '.') {
501 // Handled down there as we support '.[0-9]' as numbers above
502 r_token.type = TK_PERIOD;
503 return OK;
504
505 } else {
506 _set_error("Unexpected character.");
507 r_token.type = TK_ERROR;
508 return ERR_PARSE_ERROR;
509 }
510 }
511 }
512#undef GET_CHAR
513 }
514
515 r_token.type = TK_ERROR;
516 return ERR_PARSE_ERROR;
517}
518
519const char *Expression::token_name[TK_MAX] = {
520 "CURLY BRACKET OPEN",
521 "CURLY BRACKET CLOSE",
522 "BRACKET OPEN",
523 "BRACKET CLOSE",
524 "PARENTHESIS OPEN",
525 "PARENTHESIS CLOSE",
526 "IDENTIFIER",
527 "BUILTIN FUNC",
528 "SELF",
529 "CONSTANT",
530 "BASIC TYPE",
531 "COLON",
532 "COMMA",
533 "PERIOD",
534 "OP IN",
535 "OP EQUAL",
536 "OP NOT EQUAL",
537 "OP LESS",
538 "OP LESS EQUAL",
539 "OP GREATER",
540 "OP GREATER EQUAL",
541 "OP AND",
542 "OP OR",
543 "OP NOT",
544 "OP ADD",
545 "OP SUB",
546 "OP MUL",
547 "OP DIV",
548 "OP MOD",
549 "OP POW",
550 "OP SHIFT LEFT",
551 "OP SHIFT RIGHT",
552 "OP BIT AND",
553 "OP BIT OR",
554 "OP BIT XOR",
555 "OP BIT INVERT",
556 "OP INPUT",
557 "EOF",
558 "ERROR"
559};
560
561Expression::ENode *Expression::_parse_expression() {
562 Vector<ExpressionNode> expression_nodes;
563
564 while (true) {
565 //keep appending stuff to expression
566 ENode *expr = nullptr;
567
568 Token tk;
569 _get_token(tk);
570 if (error_set) {
571 return nullptr;
572 }
573
574 switch (tk.type) {
575 case TK_CURLY_BRACKET_OPEN: {
576 //a dictionary
577 DictionaryNode *dn = alloc_node<DictionaryNode>();
578
579 while (true) {
580 int cofs = str_ofs;
581 _get_token(tk);
582 if (tk.type == TK_CURLY_BRACKET_CLOSE) {
583 break;
584 }
585 str_ofs = cofs; //revert
586 //parse an expression
587 ENode *subexpr = _parse_expression();
588 if (!subexpr) {
589 return nullptr;
590 }
591 dn->dict.push_back(subexpr);
592
593 _get_token(tk);
594 if (tk.type != TK_COLON) {
595 _set_error("Expected ':'");
596 return nullptr;
597 }
598
599 subexpr = _parse_expression();
600 if (!subexpr) {
601 return nullptr;
602 }
603
604 dn->dict.push_back(subexpr);
605
606 cofs = str_ofs;
607 _get_token(tk);
608 if (tk.type == TK_COMMA) {
609 //all good
610 } else if (tk.type == TK_CURLY_BRACKET_CLOSE) {
611 str_ofs = cofs;
612 } else {
613 _set_error("Expected ',' or '}'");
614 }
615 }
616
617 expr = dn;
618 } break;
619 case TK_BRACKET_OPEN: {
620 //an array
621
622 ArrayNode *an = alloc_node<ArrayNode>();
623
624 while (true) {
625 int cofs = str_ofs;
626 _get_token(tk);
627 if (tk.type == TK_BRACKET_CLOSE) {
628 break;
629 }
630 str_ofs = cofs; //revert
631 //parse an expression
632 ENode *subexpr = _parse_expression();
633 if (!subexpr) {
634 return nullptr;
635 }
636 an->array.push_back(subexpr);
637
638 cofs = str_ofs;
639 _get_token(tk);
640 if (tk.type == TK_COMMA) {
641 //all good
642 } else if (tk.type == TK_BRACKET_CLOSE) {
643 str_ofs = cofs;
644 } else {
645 _set_error("Expected ',' or ']'");
646 }
647 }
648
649 expr = an;
650 } break;
651 case TK_PARENTHESIS_OPEN: {
652 //a suexpression
653 ENode *e = _parse_expression();
654 if (error_set) {
655 return nullptr;
656 }
657 _get_token(tk);
658 if (tk.type != TK_PARENTHESIS_CLOSE) {
659 _set_error("Expected ')'");
660 return nullptr;
661 }
662
663 expr = e;
664
665 } break;
666 case TK_IDENTIFIER: {
667 String identifier = tk.value;
668
669 int cofs = str_ofs;
670 _get_token(tk);
671 if (tk.type == TK_PARENTHESIS_OPEN) {
672 //function call
673 CallNode *func_call = alloc_node<CallNode>();
674 func_call->method = identifier;
675 SelfNode *self_node = alloc_node<SelfNode>();
676 func_call->base = self_node;
677
678 while (true) {
679 int cofs2 = str_ofs;
680 _get_token(tk);
681 if (tk.type == TK_PARENTHESIS_CLOSE) {
682 break;
683 }
684 str_ofs = cofs2; //revert
685 //parse an expression
686 ENode *subexpr = _parse_expression();
687 if (!subexpr) {
688 return nullptr;
689 }
690
691 func_call->arguments.push_back(subexpr);
692
693 cofs2 = str_ofs;
694 _get_token(tk);
695 if (tk.type == TK_COMMA) {
696 //all good
697 } else if (tk.type == TK_PARENTHESIS_CLOSE) {
698 str_ofs = cofs2;
699 } else {
700 _set_error("Expected ',' or ')'");
701 }
702 }
703
704 expr = func_call;
705 } else {
706 //named indexing
707 str_ofs = cofs;
708
709 int input_index = -1;
710 for (int i = 0; i < input_names.size(); i++) {
711 if (input_names[i] == identifier) {
712 input_index = i;
713 break;
714 }
715 }
716
717 if (input_index != -1) {
718 InputNode *input = alloc_node<InputNode>();
719 input->index = input_index;
720 expr = input;
721 } else {
722 NamedIndexNode *index = alloc_node<NamedIndexNode>();
723 SelfNode *self_node = alloc_node<SelfNode>();
724 index->base = self_node;
725 index->name = identifier;
726 expr = index;
727 }
728 }
729 } break;
730 case TK_INPUT: {
731 InputNode *input = alloc_node<InputNode>();
732 input->index = tk.value;
733 expr = input;
734 } break;
735 case TK_SELF: {
736 SelfNode *self = alloc_node<SelfNode>();
737 expr = self;
738 } break;
739 case TK_CONSTANT: {
740 ConstantNode *constant = alloc_node<ConstantNode>();
741 constant->value = tk.value;
742 expr = constant;
743 } break;
744 case TK_BASIC_TYPE: {
745 //constructor..
746
747 Variant::Type bt = Variant::Type(int(tk.value));
748 _get_token(tk);
749 if (tk.type != TK_PARENTHESIS_OPEN) {
750 _set_error("Expected '('");
751 return nullptr;
752 }
753
754 ConstructorNode *constructor = alloc_node<ConstructorNode>();
755 constructor->data_type = bt;
756
757 while (true) {
758 int cofs = str_ofs;
759 _get_token(tk);
760 if (tk.type == TK_PARENTHESIS_CLOSE) {
761 break;
762 }
763 str_ofs = cofs; //revert
764 //parse an expression
765 ENode *subexpr = _parse_expression();
766 if (!subexpr) {
767 return nullptr;
768 }
769
770 constructor->arguments.push_back(subexpr);
771
772 cofs = str_ofs;
773 _get_token(tk);
774 if (tk.type == TK_COMMA) {
775 //all good
776 } else if (tk.type == TK_PARENTHESIS_CLOSE) {
777 str_ofs = cofs;
778 } else {
779 _set_error("Expected ',' or ')'");
780 }
781 }
782
783 expr = constructor;
784
785 } break;
786 case TK_BUILTIN_FUNC: {
787 //builtin function
788
789 StringName func = tk.value;
790
791 _get_token(tk);
792 if (tk.type != TK_PARENTHESIS_OPEN) {
793 _set_error("Expected '('");
794 return nullptr;
795 }
796
797 BuiltinFuncNode *bifunc = alloc_node<BuiltinFuncNode>();
798 bifunc->func = func;
799
800 while (true) {
801 int cofs = str_ofs;
802 _get_token(tk);
803 if (tk.type == TK_PARENTHESIS_CLOSE) {
804 break;
805 }
806 str_ofs = cofs; //revert
807 //parse an expression
808 ENode *subexpr = _parse_expression();
809 if (!subexpr) {
810 return nullptr;
811 }
812
813 bifunc->arguments.push_back(subexpr);
814
815 cofs = str_ofs;
816 _get_token(tk);
817 if (tk.type == TK_COMMA) {
818 //all good
819 } else if (tk.type == TK_PARENTHESIS_CLOSE) {
820 str_ofs = cofs;
821 } else {
822 _set_error("Expected ',' or ')'");
823 }
824 }
825
826 if (!Variant::is_utility_function_vararg(bifunc->func)) {
827 int expected_args = Variant::get_utility_function_argument_count(bifunc->func);
828 if (expected_args != bifunc->arguments.size()) {
829 _set_error("Builtin func '" + String(bifunc->func) + "' expects " + itos(expected_args) + " arguments.");
830 }
831 }
832
833 expr = bifunc;
834
835 } break;
836 case TK_OP_SUB: {
837 ExpressionNode e;
838 e.is_op = true;
839 e.op = Variant::OP_NEGATE;
840 expression_nodes.push_back(e);
841 continue;
842 } break;
843 case TK_OP_NOT: {
844 ExpressionNode e;
845 e.is_op = true;
846 e.op = Variant::OP_NOT;
847 expression_nodes.push_back(e);
848 continue;
849 } break;
850
851 default: {
852 _set_error("Expected expression.");
853 return nullptr;
854 } break;
855 }
856
857 //before going to operators, must check indexing!
858
859 while (true) {
860 int cofs2 = str_ofs;
861 _get_token(tk);
862 if (error_set) {
863 return nullptr;
864 }
865
866 bool done = false;
867
868 switch (tk.type) {
869 case TK_BRACKET_OPEN: {
870 //value indexing
871
872 IndexNode *index = alloc_node<IndexNode>();
873 index->base = expr;
874
875 ENode *what = _parse_expression();
876 if (!what) {
877 return nullptr;
878 }
879
880 index->index = what;
881
882 _get_token(tk);
883 if (tk.type != TK_BRACKET_CLOSE) {
884 _set_error("Expected ']' at end of index.");
885 return nullptr;
886 }
887 expr = index;
888
889 } break;
890 case TK_PERIOD: {
891 //named indexing or function call
892 _get_token(tk);
893 if (tk.type != TK_IDENTIFIER && tk.type != TK_BUILTIN_FUNC) {
894 _set_error("Expected identifier after '.'");
895 return nullptr;
896 }
897
898 StringName identifier = tk.value;
899
900 int cofs = str_ofs;
901 _get_token(tk);
902 if (tk.type == TK_PARENTHESIS_OPEN) {
903 //function call
904 CallNode *func_call = alloc_node<CallNode>();
905 func_call->method = identifier;
906 func_call->base = expr;
907
908 while (true) {
909 int cofs3 = str_ofs;
910 _get_token(tk);
911 if (tk.type == TK_PARENTHESIS_CLOSE) {
912 break;
913 }
914 str_ofs = cofs3; //revert
915 //parse an expression
916 ENode *subexpr = _parse_expression();
917 if (!subexpr) {
918 return nullptr;
919 }
920
921 func_call->arguments.push_back(subexpr);
922
923 cofs3 = str_ofs;
924 _get_token(tk);
925 if (tk.type == TK_COMMA) {
926 //all good
927 } else if (tk.type == TK_PARENTHESIS_CLOSE) {
928 str_ofs = cofs3;
929 } else {
930 _set_error("Expected ',' or ')'");
931 }
932 }
933
934 expr = func_call;
935 } else {
936 //named indexing
937 str_ofs = cofs;
938
939 NamedIndexNode *index = alloc_node<NamedIndexNode>();
940 index->base = expr;
941 index->name = identifier;
942 expr = index;
943 }
944
945 } break;
946 default: {
947 str_ofs = cofs2;
948 done = true;
949 } break;
950 }
951
952 if (done) {
953 break;
954 }
955 }
956
957 //push expression
958 {
959 ExpressionNode e;
960 e.is_op = false;
961 e.node = expr;
962 expression_nodes.push_back(e);
963 }
964
965 //ok finally look for an operator
966
967 int cofs = str_ofs;
968 _get_token(tk);
969 if (error_set) {
970 return nullptr;
971 }
972
973 Variant::Operator op = Variant::OP_MAX;
974
975 switch (tk.type) {
976 case TK_OP_IN:
977 op = Variant::OP_IN;
978 break;
979 case TK_OP_EQUAL:
980 op = Variant::OP_EQUAL;
981 break;
982 case TK_OP_NOT_EQUAL:
983 op = Variant::OP_NOT_EQUAL;
984 break;
985 case TK_OP_LESS:
986 op = Variant::OP_LESS;
987 break;
988 case TK_OP_LESS_EQUAL:
989 op = Variant::OP_LESS_EQUAL;
990 break;
991 case TK_OP_GREATER:
992 op = Variant::OP_GREATER;
993 break;
994 case TK_OP_GREATER_EQUAL:
995 op = Variant::OP_GREATER_EQUAL;
996 break;
997 case TK_OP_AND:
998 op = Variant::OP_AND;
999 break;
1000 case TK_OP_OR:
1001 op = Variant::OP_OR;
1002 break;
1003 case TK_OP_NOT:
1004 op = Variant::OP_NOT;
1005 break;
1006 case TK_OP_ADD:
1007 op = Variant::OP_ADD;
1008 break;
1009 case TK_OP_SUB:
1010 op = Variant::OP_SUBTRACT;
1011 break;
1012 case TK_OP_MUL:
1013 op = Variant::OP_MULTIPLY;
1014 break;
1015 case TK_OP_DIV:
1016 op = Variant::OP_DIVIDE;
1017 break;
1018 case TK_OP_MOD:
1019 op = Variant::OP_MODULE;
1020 break;
1021 case TK_OP_POW:
1022 op = Variant::OP_POWER;
1023 break;
1024 case TK_OP_SHIFT_LEFT:
1025 op = Variant::OP_SHIFT_LEFT;
1026 break;
1027 case TK_OP_SHIFT_RIGHT:
1028 op = Variant::OP_SHIFT_RIGHT;
1029 break;
1030 case TK_OP_BIT_AND:
1031 op = Variant::OP_BIT_AND;
1032 break;
1033 case TK_OP_BIT_OR:
1034 op = Variant::OP_BIT_OR;
1035 break;
1036 case TK_OP_BIT_XOR:
1037 op = Variant::OP_BIT_XOR;
1038 break;
1039 case TK_OP_BIT_INVERT:
1040 op = Variant::OP_BIT_NEGATE;
1041 break;
1042 default: {
1043 }
1044 }
1045
1046 if (op == Variant::OP_MAX) { //stop appending stuff
1047 str_ofs = cofs;
1048 break;
1049 }
1050
1051 //push operator and go on
1052 {
1053 ExpressionNode e;
1054 e.is_op = true;
1055 e.op = op;
1056 expression_nodes.push_back(e);
1057 }
1058 }
1059
1060 /* Reduce the set of expressions and place them in an operator tree, respecting precedence */
1061
1062 while (expression_nodes.size() > 1) {
1063 int next_op = -1;
1064 int min_priority = 0xFFFFF;
1065 bool is_unary = false;
1066
1067 for (int i = 0; i < expression_nodes.size(); i++) {
1068 if (!expression_nodes[i].is_op) {
1069 continue;
1070 }
1071
1072 int priority;
1073
1074 bool unary = false;
1075
1076 switch (expression_nodes[i].op) {
1077 case Variant::OP_POWER:
1078 priority = 0;
1079 break;
1080 case Variant::OP_BIT_NEGATE:
1081 priority = 1;
1082 unary = true;
1083 break;
1084 case Variant::OP_NEGATE:
1085 priority = 2;
1086 unary = true;
1087 break;
1088 case Variant::OP_MULTIPLY:
1089 case Variant::OP_DIVIDE:
1090 case Variant::OP_MODULE:
1091 priority = 3;
1092 break;
1093 case Variant::OP_ADD:
1094 case Variant::OP_SUBTRACT:
1095 priority = 4;
1096 break;
1097 case Variant::OP_SHIFT_LEFT:
1098 case Variant::OP_SHIFT_RIGHT:
1099 priority = 5;
1100 break;
1101 case Variant::OP_BIT_AND:
1102 priority = 6;
1103 break;
1104 case Variant::OP_BIT_XOR:
1105 priority = 7;
1106 break;
1107 case Variant::OP_BIT_OR:
1108 priority = 8;
1109 break;
1110 case Variant::OP_LESS:
1111 case Variant::OP_LESS_EQUAL:
1112 case Variant::OP_GREATER:
1113 case Variant::OP_GREATER_EQUAL:
1114 case Variant::OP_EQUAL:
1115 case Variant::OP_NOT_EQUAL:
1116 priority = 9;
1117 break;
1118 case Variant::OP_IN:
1119 priority = 11;
1120 break;
1121 case Variant::OP_NOT:
1122 priority = 12;
1123 unary = true;
1124 break;
1125 case Variant::OP_AND:
1126 priority = 13;
1127 break;
1128 case Variant::OP_OR:
1129 priority = 14;
1130 break;
1131 default: {
1132 _set_error("Parser bug, invalid operator in expression: " + itos(expression_nodes[i].op));
1133 return nullptr;
1134 }
1135 }
1136
1137 if (priority < min_priority) {
1138 // < is used for left to right (default)
1139 // <= is used for right to left
1140
1141 next_op = i;
1142 min_priority = priority;
1143 is_unary = unary;
1144 }
1145 }
1146
1147 if (next_op == -1) {
1148 _set_error("Yet another parser bug....");
1149 ERR_FAIL_V(nullptr);
1150 }
1151
1152 // OK! create operator..
1153 if (is_unary) {
1154 int expr_pos = next_op;
1155 while (expression_nodes[expr_pos].is_op) {
1156 expr_pos++;
1157 if (expr_pos == expression_nodes.size()) {
1158 //can happen..
1159 _set_error("Unexpected end of expression...");
1160 return nullptr;
1161 }
1162 }
1163
1164 //consecutively do unary operators
1165 for (int i = expr_pos - 1; i >= next_op; i--) {
1166 OperatorNode *op = alloc_node<OperatorNode>();
1167 op->op = expression_nodes[i].op;
1168 op->nodes[0] = expression_nodes[i + 1].node;
1169 op->nodes[1] = nullptr;
1170 expression_nodes.write[i].is_op = false;
1171 expression_nodes.write[i].node = op;
1172 expression_nodes.remove_at(i + 1);
1173 }
1174
1175 } else {
1176 if (next_op < 1 || next_op >= (expression_nodes.size() - 1)) {
1177 _set_error("Parser bug...");
1178 ERR_FAIL_V(nullptr);
1179 }
1180
1181 OperatorNode *op = alloc_node<OperatorNode>();
1182 op->op = expression_nodes[next_op].op;
1183
1184 if (expression_nodes[next_op - 1].is_op) {
1185 _set_error("Parser bug...");
1186 ERR_FAIL_V(nullptr);
1187 }
1188
1189 if (expression_nodes[next_op + 1].is_op) {
1190 // this is not invalid and can really appear
1191 // but it becomes invalid anyway because no binary op
1192 // can be followed by a unary op in a valid combination,
1193 // due to how precedence works, unaries will always disappear first
1194
1195 _set_error("Unexpected two consecutive operators.");
1196 return nullptr;
1197 }
1198
1199 op->nodes[0] = expression_nodes[next_op - 1].node; //expression goes as left
1200 op->nodes[1] = expression_nodes[next_op + 1].node; //next expression goes as right
1201
1202 //replace all 3 nodes by this operator and make it an expression
1203 expression_nodes.write[next_op - 1].node = op;
1204 expression_nodes.remove_at(next_op);
1205 expression_nodes.remove_at(next_op);
1206 }
1207 }
1208
1209 return expression_nodes[0].node;
1210}
1211
1212bool Expression::_compile_expression() {
1213 if (!expression_dirty) {
1214 return error_set;
1215 }
1216
1217 if (nodes) {
1218 memdelete(nodes);
1219 nodes = nullptr;
1220 root = nullptr;
1221 }
1222
1223 error_str = String();
1224 error_set = false;
1225 str_ofs = 0;
1226
1227 root = _parse_expression();
1228
1229 if (error_set) {
1230 root = nullptr;
1231 if (nodes) {
1232 memdelete(nodes);
1233 }
1234 nodes = nullptr;
1235 return true;
1236 }
1237
1238 expression_dirty = false;
1239 return false;
1240}
1241
1242bool Expression::_execute(const Array &p_inputs, Object *p_instance, Expression::ENode *p_node, Variant &r_ret, bool p_const_calls_only, String &r_error_str) {
1243 switch (p_node->type) {
1244 case Expression::ENode::TYPE_INPUT: {
1245 const Expression::InputNode *in = static_cast<const Expression::InputNode *>(p_node);
1246 if (in->index < 0 || in->index >= p_inputs.size()) {
1247 r_error_str = vformat(RTR("Invalid input %d (not passed) in expression"), in->index);
1248 return true;
1249 }
1250 r_ret = p_inputs[in->index];
1251 } break;
1252 case Expression::ENode::TYPE_CONSTANT: {
1253 const Expression::ConstantNode *c = static_cast<const Expression::ConstantNode *>(p_node);
1254 r_ret = c->value;
1255
1256 } break;
1257 case Expression::ENode::TYPE_SELF: {
1258 if (!p_instance) {
1259 r_error_str = RTR("self can't be used because instance is null (not passed)");
1260 return true;
1261 }
1262 r_ret = p_instance;
1263 } break;
1264 case Expression::ENode::TYPE_OPERATOR: {
1265 const Expression::OperatorNode *op = static_cast<const Expression::OperatorNode *>(p_node);
1266
1267 Variant a;
1268 bool ret = _execute(p_inputs, p_instance, op->nodes[0], a, p_const_calls_only, r_error_str);
1269 if (ret) {
1270 return true;
1271 }
1272
1273 Variant b;
1274
1275 if (op->nodes[1]) {
1276 ret = _execute(p_inputs, p_instance, op->nodes[1], b, p_const_calls_only, r_error_str);
1277 if (ret) {
1278 return true;
1279 }
1280 }
1281
1282 bool valid = true;
1283 Variant::evaluate(op->op, a, b, r_ret, valid);
1284 if (!valid) {
1285 r_error_str = vformat(RTR("Invalid operands to operator %s, %s and %s."), Variant::get_operator_name(op->op), Variant::get_type_name(a.get_type()), Variant::get_type_name(b.get_type()));
1286 return true;
1287 }
1288
1289 } break;
1290 case Expression::ENode::TYPE_INDEX: {
1291 const Expression::IndexNode *index = static_cast<const Expression::IndexNode *>(p_node);
1292
1293 Variant base;
1294 bool ret = _execute(p_inputs, p_instance, index->base, base, p_const_calls_only, r_error_str);
1295 if (ret) {
1296 return true;
1297 }
1298
1299 Variant idx;
1300
1301 ret = _execute(p_inputs, p_instance, index->index, idx, p_const_calls_only, r_error_str);
1302 if (ret) {
1303 return true;
1304 }
1305
1306 bool valid;
1307 r_ret = base.get(idx, &valid);
1308 if (!valid) {
1309 r_error_str = vformat(RTR("Invalid index of type %s for base type %s"), Variant::get_type_name(idx.get_type()), Variant::get_type_name(base.get_type()));
1310 return true;
1311 }
1312
1313 } break;
1314 case Expression::ENode::TYPE_NAMED_INDEX: {
1315 const Expression::NamedIndexNode *index = static_cast<const Expression::NamedIndexNode *>(p_node);
1316
1317 Variant base;
1318 bool ret = _execute(p_inputs, p_instance, index->base, base, p_const_calls_only, r_error_str);
1319 if (ret) {
1320 return true;
1321 }
1322
1323 bool valid;
1324 r_ret = base.get_named(index->name, valid);
1325 if (!valid) {
1326 r_error_str = vformat(RTR("Invalid named index '%s' for base type %s"), String(index->name), Variant::get_type_name(base.get_type()));
1327 return true;
1328 }
1329
1330 } break;
1331 case Expression::ENode::TYPE_ARRAY: {
1332 const Expression::ArrayNode *array = static_cast<const Expression::ArrayNode *>(p_node);
1333
1334 Array arr;
1335 arr.resize(array->array.size());
1336 for (int i = 0; i < array->array.size(); i++) {
1337 Variant value;
1338 bool ret = _execute(p_inputs, p_instance, array->array[i], value, p_const_calls_only, r_error_str);
1339
1340 if (ret) {
1341 return true;
1342 }
1343 arr[i] = value;
1344 }
1345
1346 r_ret = arr;
1347
1348 } break;
1349 case Expression::ENode::TYPE_DICTIONARY: {
1350 const Expression::DictionaryNode *dictionary = static_cast<const Expression::DictionaryNode *>(p_node);
1351
1352 Dictionary d;
1353 for (int i = 0; i < dictionary->dict.size(); i += 2) {
1354 Variant key;
1355 bool ret = _execute(p_inputs, p_instance, dictionary->dict[i + 0], key, p_const_calls_only, r_error_str);
1356
1357 if (ret) {
1358 return true;
1359 }
1360
1361 Variant value;
1362 ret = _execute(p_inputs, p_instance, dictionary->dict[i + 1], value, p_const_calls_only, r_error_str);
1363 if (ret) {
1364 return true;
1365 }
1366
1367 d[key] = value;
1368 }
1369
1370 r_ret = d;
1371 } break;
1372 case Expression::ENode::TYPE_CONSTRUCTOR: {
1373 const Expression::ConstructorNode *constructor = static_cast<const Expression::ConstructorNode *>(p_node);
1374
1375 Vector<Variant> arr;
1376 Vector<const Variant *> argp;
1377 arr.resize(constructor->arguments.size());
1378 argp.resize(constructor->arguments.size());
1379
1380 for (int i = 0; i < constructor->arguments.size(); i++) {
1381 Variant value;
1382 bool ret = _execute(p_inputs, p_instance, constructor->arguments[i], value, p_const_calls_only, r_error_str);
1383
1384 if (ret) {
1385 return true;
1386 }
1387 arr.write[i] = value;
1388 argp.write[i] = &arr[i];
1389 }
1390
1391 Callable::CallError ce;
1392 Variant::construct(constructor->data_type, r_ret, (const Variant **)argp.ptr(), argp.size(), ce);
1393
1394 if (ce.error != Callable::CallError::CALL_OK) {
1395 r_error_str = vformat(RTR("Invalid arguments to construct '%s'"), Variant::get_type_name(constructor->data_type));
1396 return true;
1397 }
1398
1399 } break;
1400 case Expression::ENode::TYPE_BUILTIN_FUNC: {
1401 const Expression::BuiltinFuncNode *bifunc = static_cast<const Expression::BuiltinFuncNode *>(p_node);
1402
1403 Vector<Variant> arr;
1404 Vector<const Variant *> argp;
1405 arr.resize(bifunc->arguments.size());
1406 argp.resize(bifunc->arguments.size());
1407
1408 for (int i = 0; i < bifunc->arguments.size(); i++) {
1409 Variant value;
1410 bool ret = _execute(p_inputs, p_instance, bifunc->arguments[i], value, p_const_calls_only, r_error_str);
1411 if (ret) {
1412 return true;
1413 }
1414 arr.write[i] = value;
1415 argp.write[i] = &arr[i];
1416 }
1417
1418 r_ret = Variant(); //may not return anything
1419 Callable::CallError ce;
1420 Variant::call_utility_function(bifunc->func, &r_ret, (const Variant **)argp.ptr(), argp.size(), ce);
1421 if (ce.error != Callable::CallError::CALL_OK) {
1422 r_error_str = "Builtin call failed: " + Variant::get_call_error_text(bifunc->func, (const Variant **)argp.ptr(), argp.size(), ce);
1423 return true;
1424 }
1425
1426 } break;
1427 case Expression::ENode::TYPE_CALL: {
1428 const Expression::CallNode *call = static_cast<const Expression::CallNode *>(p_node);
1429
1430 Variant base;
1431 bool ret = _execute(p_inputs, p_instance, call->base, base, p_const_calls_only, r_error_str);
1432
1433 if (ret) {
1434 return true;
1435 }
1436
1437 Vector<Variant> arr;
1438 Vector<const Variant *> argp;
1439 arr.resize(call->arguments.size());
1440 argp.resize(call->arguments.size());
1441
1442 for (int i = 0; i < call->arguments.size(); i++) {
1443 Variant value;
1444 ret = _execute(p_inputs, p_instance, call->arguments[i], value, p_const_calls_only, r_error_str);
1445
1446 if (ret) {
1447 return true;
1448 }
1449 arr.write[i] = value;
1450 argp.write[i] = &arr[i];
1451 }
1452
1453 Callable::CallError ce;
1454 if (p_const_calls_only) {
1455 base.call_const(call->method, (const Variant **)argp.ptr(), argp.size(), r_ret, ce);
1456 } else {
1457 base.callp(call->method, (const Variant **)argp.ptr(), argp.size(), r_ret, ce);
1458 }
1459
1460 if (ce.error != Callable::CallError::CALL_OK) {
1461 r_error_str = vformat(RTR("On call to '%s':"), String(call->method));
1462 return true;
1463 }
1464
1465 } break;
1466 }
1467 return false;
1468}
1469
1470Error Expression::parse(const String &p_expression, const Vector<String> &p_input_names) {
1471 if (nodes) {
1472 memdelete(nodes);
1473 nodes = nullptr;
1474 root = nullptr;
1475 }
1476
1477 error_str = String();
1478 error_set = false;
1479 str_ofs = 0;
1480 input_names = p_input_names;
1481
1482 expression = p_expression;
1483 root = _parse_expression();
1484
1485 if (error_set) {
1486 root = nullptr;
1487 if (nodes) {
1488 memdelete(nodes);
1489 }
1490 nodes = nullptr;
1491 return ERR_INVALID_PARAMETER;
1492 }
1493
1494 return OK;
1495}
1496
1497Variant Expression::execute(Array p_inputs, Object *p_base, bool p_show_error, bool p_const_calls_only) {
1498 ERR_FAIL_COND_V_MSG(error_set, Variant(), "There was previously a parse error: " + error_str + ".");
1499
1500 execution_error = false;
1501 Variant output;
1502 String error_txt;
1503 bool err = _execute(p_inputs, p_base, root, output, p_const_calls_only, error_txt);
1504 if (err) {
1505 execution_error = true;
1506 error_str = error_txt;
1507 ERR_FAIL_COND_V_MSG(p_show_error, Variant(), error_str);
1508 }
1509
1510 return output;
1511}
1512
1513bool Expression::has_execute_failed() const {
1514 return execution_error;
1515}
1516
1517String Expression::get_error_text() const {
1518 return error_str;
1519}
1520
1521void Expression::_bind_methods() {
1522 ClassDB::bind_method(D_METHOD("parse", "expression", "input_names"), &Expression::parse, DEFVAL(Vector<String>()));
1523 ClassDB::bind_method(D_METHOD("execute", "inputs", "base_instance", "show_error", "const_calls_only"), &Expression::execute, DEFVAL(Array()), DEFVAL(Variant()), DEFVAL(true), DEFVAL(false));
1524 ClassDB::bind_method(D_METHOD("has_execute_failed"), &Expression::has_execute_failed);
1525 ClassDB::bind_method(D_METHOD("get_error_text"), &Expression::get_error_text);
1526}
1527
1528Expression::~Expression() {
1529 if (nodes) {
1530 memdelete(nodes);
1531 }
1532}
1533