1 /****************************************************************************
2 * fnsyntax.cpp
3 *
4 * This module implements the the function type used by iso surfaces and
5 * the function pattern.
6 *
7 * This module is inspired by code by D. Skarda, T. Bily and R. Suzuki.
8 *
9 * from Persistence of Vision(tm) Ray Tracer version 3.6.
10 * Copyright 1991-2003 Persistence of Vision Team
11 * Copyright 2003-2004 Persistence of Vision Raytracer Pty. Ltd.
12 *---------------------------------------------------------------------------
13 * NOTICE: This source code file is provided so that users may experiment
14 * with enhancements to POV-Ray and to port the software to platforms other
15 * than those supported by the POV-Ray developers. There are strict rules
16 * regarding how you are permitted to use this file. These rules are contained
17 * in the distribution and derivative versions licenses which should have been
18 * provided with this file.
19 *
20 * These licences may be found online, linked from the end-user license
21 * agreement that is located at http://www.povray.org/povlegal.html
22 *---------------------------------------------------------------------------
23 * This program is based on the popular DKB raytracer version 2.12.
24 * DKBTrace was originally written by David K. Buck.
25 * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
26 *---------------------------------------------------------------------------
27 *
28 *===========================================================================
29 * This file is part of MegaPOV, a modified and unofficial version of POV-Ray
30 * For more information on MegaPOV visit our website:
31 * http://megapov.inetart.net/
32 *===========================================================================
33 *
34 * $RCSfile: fnsyntax.cpp,v $
35 * $Revision: 1.14 $
36 * $Author: chris $
37 *
38 *****************************************************************************/
39
40 #include <limits.h>
41
42 #include "frame.h"
43 #include "parse.h"
44 #include "povray.h"
45 #include "tokenize.h"
46 #include "vector.h"
47 #include "function.h"
48 #include "fnsyntax.h"
49 #include "fnpovfpu.h"
50 #include "mathutil.h"
51
52 BEGIN_POV_NAMESPACE
53
54 /*****************************************************************************
55 * Static functions
56 ******************************************************************************/
57
58 ExprNode *parse_expr();
59 TOKEN expr_get_token();
60 ExprNode *new_expr_node(int stage, int op);
61
62 bool expr_noop(ExprNode *¤t, int stage, int op);
63 bool expr_grow(ExprNode *¤t, int stage, int op);
64 bool expr_call(ExprNode *¤t, int stage, int op);
65 bool expr_put(ExprNode *¤t, int stage, int op);
66 bool expr_new(ExprNode *¤t, int stage, int op);
67 bool expr_ret(ExprNode *¤t, int stage, int op);
68 bool expr_err(ExprNode *¤t, int stage, int op);
69 void optimise_expr(ExprNode *node);
70 void optimise_call(ExprNode *node);
71 bool right_subtree_has_variable_expr(ExprNode *node);
72 bool left_subtree_has_variable_expr(ExprNode *node);
73 void dump_expr(FILE *f, ExprNode *node);
74
75
76 /*****************************************************************************
77 * Local typedefs
78 ******************************************************************************/
79
80 typedef struct
81 {
82 int stage;
83 TOKEN token;
84 bool (*operation)(ExprNode *&, int, int);
85 int next;
86 int op;
87 } ExprParserTableEntry;
88
89 typedef struct
90 {
91 int stage;
92 char *expected;
93 } ExprParserErrorEntry;
94
95
96 /*****************************************************************************
97 * Local variables
98 ******************************************************************************/
99
100 const ExprParserErrorEntry expr_parser_error_table[] =
101 {
102 { 35, "operator" },
103 { 45, "." },
104 { 40, "sign or operand" },
105 { 50, "operand" },
106 { 55, ")" },
107 { 60, "color or vector member" },
108 { -1, NULL }
109 };
110
111 const ExprParserTableEntry expr_parser_table[] =
112 {
113 // logical or
114 { 5, BAR_TOKEN, expr_grow, 40, OP_OR }, // 0
115 // logical and
116 { 10, AMPERSAND_TOKEN, expr_grow, 40, OP_AND }, // 1
117 // equal, not equal
118 { 15, EQUALS_TOKEN, expr_grow, 40, OP_CMP_EQ }, // 2
119 { 15, REL_NE_TOKEN, expr_grow, 40, OP_CMP_NE }, // 3
120 // smaller and/or equal, greater and/or equal
121 { 15, LEFT_ANGLE_TOKEN, expr_grow, 40, OP_CMP_LT }, // 4
122 { 15, REL_LE_TOKEN, expr_grow, 40, OP_CMP_LE }, // 5
123 { 15, RIGHT_ANGLE_TOKEN, expr_grow, 40, OP_CMP_GT }, // 6
124 { 15, REL_GE_TOKEN, expr_grow, 40, OP_CMP_GE }, // 7
125 // plus, minus
126 { 20, PLUS_TOKEN, expr_grow, 40, OP_ADD }, // 8
127 { 20, DASH_TOKEN, expr_grow, 40, OP_SUB }, // 9
128 // multiply, divide
129 { 25, STAR_TOKEN, expr_grow, 40, OP_MUL }, // 10
130 { 25, SLASH_TOKEN, expr_grow, 40, OP_DIV }, // 11
131 // ')', '}' or ',' - end of function
132 { 35, RIGHT_PAREN_TOKEN, expr_ret, -1, OP_NONE }, // 12
133 { 35, RIGHT_CURLY_TOKEN, expr_ret, -1, OP_NONE }, // 13
134 { 35, COMMA_TOKEN, expr_ret, -1, OP_NONE }, // 14
135 { 35, LAST_TOKEN, expr_err, -1, OP_NONE }, // 15
136 // vector/color member access
137 { 45, PERIOD_TOKEN, expr_grow, 60, OP_DOT }, // 16
138 { 45, LAST_TOKEN, expr_err, -1, OP_NONE }, // 17
139 // unary plus, unary minus, (logical not - disabled)
140 { 40, PLUS_TOKEN, expr_noop, 50, OP_NONE }, // 18
141 { 40, DASH_TOKEN, expr_grow, 50, OP_NEG }, // 19
142 { 40, EXCLAMATION_TOKEN, expr_err, -1, OP_NOT }, // 20
143 // constant, variable, (expression), function
144 { 50, FLOAT_TOKEN, expr_put, 5, OP_CONSTANT }, // 21
145 { 50, FLOAT_ID_TOKEN, expr_put, 5, OP_VARIABLE }, // 22
146 { 50, FUNCT_ID_TOKEN, expr_call, 5, OP_CALL }, // 23
147 { 50, VECTFUNCT_ID_TOKEN,expr_call, 45, OP_CALL }, // 24
148 { 50, LEFT_PAREN_TOKEN, expr_new, 55, OP_FIRST }, // 25
149 { 50, LAST_TOKEN, expr_err, -1, OP_NONE }, // 26
150 // (expression)
151 { 55, RIGHT_PAREN_TOKEN, expr_noop, 5, OP_NONE }, // 27
152 { 55, LAST_TOKEN, expr_err, -1, OP_NONE }, // 28
153 // vector/color members
154 { 60, FLOAT_ID_TOKEN, expr_put, 5, OP_MEMBER }, // 29
155 { 60, T_TOKEN, expr_put, 5, OP_MEMBER }, // 30
156 { 60, RED_TOKEN, expr_put, 5, OP_MEMBER }, // 31
157 { 60, GREEN_TOKEN, expr_put, 5, OP_MEMBER }, // 32
158 { 60, BLUE_TOKEN, expr_put, 5, OP_MEMBER }, // 33
159 { 60, FILTER_TOKEN, expr_put, 5, OP_MEMBER }, // 34
160 { 60, TRANSMIT_TOKEN, expr_put, 5, OP_MEMBER }, // 35
161 { 60, GRAY_TOKEN, expr_put, 5, OP_MEMBER }, // 36
162 { 60, LAST_TOKEN, expr_err, -1, OP_NONE } // 37
163 };
164
165 // parse_expr has to start with first unary operator [trf]
166 const int START_LEFTMOST_PARSE_INDEX = 18;
167
168 /*****************************************************************************
169 *
170 * FUNCTION
171 *
172 * FNSyntax_ParseExpression
173 *
174 * INPUT
175 *
176 * OUTPUT
177 *
178 * RETURNS
179 *
180 * ExprNode - parsed expression root pointer
181 *
182 * AUTHOR
183 *
184 * Thorsten Froehlich
185 *
186 * DESCRIPTION
187 *
188 * Parse and optimise an expression.
189 *
190 * CHANGES
191 *
192 * -
193 *
194 ******************************************************************************/
195
FNSyntax_ParseExpression()196 ExprNode *FNSyntax_ParseExpression()
197 {
198 ExprNode *expression = NULL;
199
200 expression = parse_expr();
201 optimise_expr(expression);
202
203 return expression;
204 }
205
206
207 /*****************************************************************************
208 *
209 * FUNCTION
210 *
211 * FNSyntax_GetTrapExpression
212 *
213 * INPUT
214 *
215 * trap - number of the trap
216 *
217 * OUTPUT
218 *
219 * RETURNS
220 *
221 * ExprNode - expression root pointer
222 *
223 * AUTHOR
224 *
225 * Thorsten Froehlich
226 *
227 * DESCRIPTION
228 *
229 * Generate an expression which only contains a trap.
230 *
231 * CHANGES
232 *
233 * -
234 *
235 ******************************************************************************/
236
FNSyntax_GetTrapExpression(unsigned int trap)237 ExprNode *FNSyntax_GetTrapExpression(unsigned int trap)
238 {
239 ExprNode *expression = NULL;
240
241 expression = new_expr_node(0, OP_TRAP);
242 expression->trap = trap;
243
244 return expression;
245 }
246
247
248 /*****************************************************************************
249 *
250 * FUNCTION
251 *
252 * FNSyntax_DeleteExpression
253 *
254 * INPUT
255 *
256 * node - root node of the (sub-) tree to delete
257 *
258 * OUTPUT
259 *
260 * RETURNS
261 *
262 * AUTHOR
263 *
264 * Thorsten Froehlich
265 *
266 * DESCRIPTION
267 *
268 * Delete an expression (sub-) tree.
269 *
270 * CHANGES
271 *
272 * -
273 *
274 ******************************************************************************/
275
FNSyntax_DeleteExpression(ExprNode * node)276 void FNSyntax_DeleteExpression(ExprNode *node)
277 {
278 ExprNode *temp = NULL;
279
280 for(ExprNode *i = node; i != NULL; i = i->next)
281 {
282 if(temp != NULL)
283 {
284 POV_FREE(temp);
285 }
286
287 FNSyntax_DeleteExpression(i->child);
288
289 if((i->op == OP_VARIABLE) || (i->op == OP_MEMBER))
290 {
291 POV_FREE(i->variable);
292 }
293 else if(i->op == OP_CALL)
294 {
295 if((i->call.token == FUNCT_ID_TOKEN) || (i->call.token == VECTFUNCT_ID_TOKEN))
296 POVFPU_RemoveFunction(i->call.fn);
297 POV_FREE(i->call.name);
298 }
299
300 temp = i;
301 }
302
303 if(temp != NULL)
304 {
305 POV_FREE(temp);
306 }
307 }
308
309
310 /*****************************************************************************
311 *
312 * FUNCTION
313 *
314 * parse_expr
315 *
316 * INPUT
317 *
318 * OUTPUT
319 *
320 * RETURNS
321 *
322 * ExprNode - parsed expression root pointer
323 *
324 * AUTHOR
325 *
326 * Thorsten Froehlich
327 *
328 * DESCRIPTION
329 *
330 * Parse an expression or subexpression.
331 *
332 * CHANGES
333 *
334 * -
335 *
336 ******************************************************************************/
337
parse_expr()338 ExprNode *parse_expr()
339 {
340 ExprNode *current = NULL;
341 ExprNode *node = NULL;
342 TOKEN token;
343 int start_index;
344 int i;
345
346 current = node = new_expr_node(0, OP_FIRST);
347
348 start_index = START_LEFTMOST_PARSE_INDEX;
349 token = expr_get_token();
350
351 while(true)
352 {
353 // search for matching token
354 for(i = start_index; ; i++)
355 {
356 if((expr_parser_table[i].token == token) ||
357 (expr_parser_table[i].token == LAST_TOKEN))
358 break;
359 }
360
361 // execute operation
362 if(expr_parser_table[i].operation(current, expr_parser_table[i].stage, expr_parser_table[i].op) == false)
363 break;
364
365 // find next index start
366 if(expr_parser_table[i].next >= 0)
367 {
368 if(expr_parser_table[i].next < expr_parser_table[i].stage)
369 start_index = 0;
370 // searching the whole table allows forward references
371 // to stages with a lower stage number [trf]
372 while(expr_parser_table[start_index].stage != expr_parser_table[i].next)
373 start_index++;
374 }
375
376 token = expr_get_token();
377 }
378
379 return node;
380 }
381
382
383 /*****************************************************************************
384 *
385 * FUNCTION
386 *
387 * expr_get_token
388 *
389 * INPUT
390 *
391 * OUTPUT
392 *
393 * RETURNS
394 *
395 * TOKEN - simplified token from Get_Token
396 *
397 * AUTHOR
398 *
399 * Thorsten Froehlich
400 *
401 * DESCRIPTION
402 *
403 * Gets a token and simplifies it for use by the expression parser.
404 *
405 * CHANGES
406 *
407 * -
408 *
409 ******************************************************************************/
410
expr_get_token()411 TOKEN expr_get_token()
412 {
413 Get_Token();
414
415 if(Token.Function_Id == X_TOKEN)
416 return FLOAT_ID_TOKEN;
417 else if(Token.Function_Id == Y_TOKEN)
418 return FLOAT_ID_TOKEN;
419 else if(Token.Function_Id == Z_TOKEN)
420 return FLOAT_ID_TOKEN;
421 else if(Token.Function_Id == U_TOKEN)
422 return FLOAT_ID_TOKEN;
423 else if(Token.Function_Id == V_TOKEN)
424 return FLOAT_ID_TOKEN;
425 else if(Token.Function_Id == IDENTIFIER_TOKEN)
426 return FLOAT_ID_TOKEN;
427 #ifdef MISSED_FLOAT_CONSTANTS_RECOGNITION_PATCH
428 else if(Token.Function_Id == CLOCK_DELTA_TOKEN)
429 {
430 Token.Token_Float = Clock_Delta;
431 return FLOAT_TOKEN;
432 }
433 else if(Token.Function_Id == CLOCK_ON_TOKEN)
434 {
435 Token.Token_Float = (DBL) ( opts.FrameSeq.FrameType == FT_MULTIPLE_FRAME );
436 return FLOAT_TOKEN;
437 }
438 else if(Token.Function_Id == FALSE_TOKEN)
439 {
440 Token.Token_Float = 0.0;
441 return FLOAT_TOKEN;
442 }
443 else if(Token.Function_Id == FINALCLOCK_TOKEN)
444 {
445 Token.Token_Float = opts.FrameSeq.FinalClock;
446 return FLOAT_TOKEN;
447 }
448 else if(Token.Function_Id == FINALFRAME_TOKEN)
449 {
450 Token.Token_Float = opts.FrameSeq.FinalFrame;
451 return FLOAT_TOKEN;
452 }
453 else if(Token.Function_Id == FRAMENUMBER_TOKEN)
454 {
455 Token.Token_Float = opts.FrameSeq.FrameNumber;
456 return FLOAT_TOKEN;
457 }
458 else if(Token.Function_Id == INITIALCLOCK_TOKEN)
459 {
460 Token.Token_Float = opts.FrameSeq.InitialClock;
461 return FLOAT_TOKEN;
462 }
463 else if(Token.Function_Id == INITIALFRAME_TOKEN)
464 {
465 Token.Token_Float = opts.FrameSeq.InitialFrame;
466 return FLOAT_TOKEN;
467 }
468 else if(Token.Function_Id == IMAGE_WIDTH_TOKEN)
469 {
470 Token.Token_Float = Frame.Screen_Width;
471 return FLOAT_TOKEN;
472 }
473 else if(Token.Function_Id == IMAGE_HEIGHT_TOKEN)
474 {
475 Token.Token_Float = Frame.Screen_Height;
476 return FLOAT_TOKEN;
477 }
478 else if(Token.Function_Id == NO_TOKEN)
479 {
480 Token.Token_Float = 0.0;
481 return FLOAT_TOKEN;
482 }
483 else if(Token.Function_Id == OFF_TOKEN)
484 {
485 Token.Token_Float = 0.0;
486 return FLOAT_TOKEN;
487 }
488 else if(Token.Function_Id == ON_TOKEN)
489 {
490 Token.Token_Float = 1.0;
491 return FLOAT_TOKEN;
492 }
493 else if(Token.Function_Id == TRUE_TOKEN)
494 {
495 Token.Token_Float = 1.0;
496 return FLOAT_TOKEN;
497 }
498 else if(Token.Function_Id == VERSION_TOKEN)
499 {
500 Token.Token_Float = opts.Language_Version / 100.0;
501 return FLOAT_TOKEN;
502 }
503 else if(Token.Function_Id == YES_TOKEN)
504 {
505 Token.Token_Float = 1.0;
506 return FLOAT_TOKEN;
507 }
508 #endif
509 #ifdef FRAME_STEP_PATCH
510 else if(Token.Function_Id == FRAME_STEP_TOKEN)
511 {
512 Token.Token_Float = opts.FrameSeq.FrameStep;
513 return FLOAT_TOKEN;
514 }
515 #endif
516 else if(Token.Function_Id == CLOCK_TOKEN)
517 {
518 Token.Token_Float = opts.FrameSeq.Clock_Value;
519 return FLOAT_TOKEN;
520 }
521 else if(Token.Function_Id == PI_TOKEN)
522 {
523 Token.Token_Float = M_PI;
524 return FLOAT_TOKEN;
525 }
526 else if(Token.Function_Id == RED_TOKEN)
527 return RED_TOKEN;
528 else if(Token.Function_Id == GREEN_TOKEN)
529 return GREEN_TOKEN;
530 else if(Token.Function_Id == BLUE_TOKEN)
531 return BLUE_TOKEN;
532 else if(Token.Function_Id == FILTER_TOKEN)
533 return FILTER_TOKEN;
534 else if(Token.Function_Id == TRANSMIT_TOKEN)
535 return TRANSMIT_TOKEN;
536 else if(Token.Function_Id == T_TOKEN)
537 return T_TOKEN;
538 else if(Token.Function_Id == GRAY_TOKEN)
539 return GRAY_TOKEN;
540
541 if(Token.Token_Id == FLOAT_FUNCT_TOKEN)
542 {
543 if(Token.Function_Id == FLOAT_TOKEN)
544 return FLOAT_TOKEN;
545 else if(Token.Function_Id == FLOAT_ID_TOKEN)
546 {
547 Token.Token_Float = *((DBL *)Token.Data);
548 return FLOAT_TOKEN;
549 }
550
551 return FUNCT_ID_TOKEN;
552 }
553
554 return Token.Token_Id;
555 }
556
557
558 /*****************************************************************************
559 *
560 * FUNCTION
561 *
562 * new_expr_node
563 *
564 * INPUT
565 *
566 * stage - stage/precedence of new node
567 * op - operation of new node
568 *
569 * OUTPUT
570 *
571 * RETURNS
572 *
573 * ExprNode - new expression node structure
574 *
575 * AUTHOR
576 *
577 * Thorsten Froehlich
578 *
579 * DESCRIPTION
580 *
581 * Creates a new expression node structure.
582 *
583 * CHANGES
584 *
585 * -
586 *
587 ******************************************************************************/
588
new_expr_node(int stage,int op)589 ExprNode *new_expr_node(int stage, int op)
590 {
591 ExprNode *node = NULL;
592
593 node = (ExprNode *)POV_MALLOC(sizeof(ExprNode), "ExprNode");
594 node->parent = NULL;
595 node->child = NULL;
596 node->prev = NULL;
597 node->next = NULL;
598 node->stage = stage;
599 node->op = op;
600
601 return node;
602 }
603
604
605 /*****************************************************************************
606 *
607 * FUNCTION
608 *
609 * expr_noop
610 *
611 * INPUT
612 *
613 * current - current poistion in expression tree
614 * stage - stage/precedence of operation
615 * op - operation
616 *
617 * OUTPUT
618 *
619 * RETURNS
620 *
621 * bool - continue to parse expression?
622 *
623 * AUTHOR
624 *
625 * Thorsten Froehlich
626 *
627 * DESCRIPTION
628 *
629 * Expression parser manipulation function that does nothing.
630 *
631 * CHANGES
632 *
633 * -
634 *
635 ******************************************************************************/
636
expr_noop(ExprNode * &,int,int)637 bool expr_noop(ExprNode *&, int, int)
638 {
639 return true;
640 }
641
642
643 /*****************************************************************************
644 *
645 * FUNCTION
646 *
647 * expr_grow
648 *
649 * INPUT
650 *
651 * current - current poistion in expression tree
652 * stage - stage/precedence of operation
653 * op - operation
654 *
655 * OUTPUT
656 *
657 * RETURNS
658 *
659 * bool - continue to parse expression?
660 *
661 * AUTHOR
662 *
663 * Thorsten Froehlich
664 *
665 * DESCRIPTION
666 *
667 * Expression parser manipulation function that grows the tree in the
668 * correct place based on the stage/level of the other nodes in the tree.
669 *
670 * CHANGES
671 *
672 * -
673 *
674 ******************************************************************************/
675
expr_grow(ExprNode * & current,int stage,int op)676 bool expr_grow(ExprNode *¤t, int stage, int op)
677 {
678 ExprNode *node = NULL;
679
680 if(current == NULL)
681 return false;
682
683 // the idea is this order: current, node, current->child
684 if(current->stage < stage)
685 {
686 while(current->child != NULL)
687 {
688 if(current->child->stage > stage)
689 break;
690
691 current = current->child;
692
693 if(current->stage == stage)
694 break;
695 }
696 }
697 else if(current->stage > stage)
698 {
699 while(current->parent != NULL)
700 {
701 current = current->parent;
702
703 if(current->stage <= stage)
704 break;
705 }
706 }
707
708 if(current->stage == stage)
709 {
710 while(current->next != NULL)
711 current = current->next;
712
713 node = new_expr_node(stage, op);
714
715 node->parent = current->parent;
716 node->prev = current;
717 current->next = node;
718
719 current = node;
720 }
721 else
722 {
723 node = new_expr_node(stage, OP_LEFTMOST);
724
725 node->parent = current;
726 node->child = current->child;
727 current->child = node;
728 for(ExprNode *ptr = node->child; ptr != NULL; ptr = ptr->next)
729 ptr->parent = node;
730
731 current = new_expr_node(stage, op);
732 current->prev = node;
733 node->next = current;
734 current->parent = node->parent;
735 }
736
737 return true;
738 }
739
740
741 /*****************************************************************************
742 *
743 * FUNCTION
744 *
745 * expr_call
746 *
747 * INPUT
748 *
749 * current - current poistion in expression tree
750 * stage - stage/precedence of operation
751 * op - operation
752 *
753 * OUTPUT
754 *
755 * RETURNS
756 *
757 * bool - continue to parse expression?
758 *
759 * AUTHOR
760 *
761 * Thorsten Froehlich
762 *
763 * DESCRIPTION
764 *
765 * Expression parser manipulation function that handles a function call.
766 *
767 * CHANGES
768 *
769 * -
770 *
771 ******************************************************************************/
772
expr_call(ExprNode * & current,int stage,int op)773 bool expr_call(ExprNode *¤t, int stage, int op)
774 {
775 ExprNode *node = NULL;
776
777 if(current == NULL)
778 return false;
779
780 node = new_expr_node(stage, op);
781
782 if(Token.Data != NULL)
783 {
784 node->call.fn = *((FUNCTION_PTR)Token.Data);
785 (void)POVFPU_GetFunctionAndReference(node->call.fn);
786 }
787 else
788 node->call.fn = 0;
789 node->call.token = Token.Function_Id;
790 node->call.name = POV_STRDUP(Token.Token_String);
791 while(current->child != NULL)
792 current = current->child;
793
794 current->child = node;
795 node->parent = current;
796 current = node;
797
798 if(expr_get_token() != LEFT_PAREN_TOKEN)
799 Expectation_Error("(");
800
801 current->child = node = parse_expr();
802 while(expr_get_token() == COMMA_TOKEN)
803 {
804 node->next = parse_expr();
805 node->next->parent = node->parent;
806 node = node->next;
807 }
808
809 if(Token.Token_Id != RIGHT_PAREN_TOKEN)
810 Expectation_Error(")");
811
812 return true;
813 }
814
815
816 /*****************************************************************************
817 *
818 * FUNCTION
819 *
820 * expr_put
821 *
822 * INPUT
823 *
824 * current - current poistion in expression tree
825 * stage - stage/precedence of operation
826 * op - operation
827 *
828 * OUTPUT
829 *
830 * RETURNS
831 *
832 * bool - continue to parse expression?
833 *
834 * AUTHOR
835 *
836 * Thorsten Froehlich
837 *
838 * DESCRIPTION
839 *
840 * Expression parser manipulation function that adds a new node in the
841 * current location in the tree.
842 *
843 * CHANGES
844 *
845 * -
846 *
847 ******************************************************************************/
848
expr_put(ExprNode * & current,int stage,int op)849 bool expr_put(ExprNode *¤t, int stage, int op)
850 {
851 ExprNode *node = NULL;
852
853 if(current == NULL)
854 return false;
855
856 node = new_expr_node(stage, op);
857
858 if(op == OP_CONSTANT)
859 {
860 node->number = Token.Token_Float;
861 }
862 else
863 {
864 node->variable = POV_STRDUP(Token.Token_String);
865 }
866
867 if(current->child != NULL)
868 return false;
869
870 current->child = node;
871 node->parent = current;
872
873 return true;
874 }
875
876
877 /*****************************************************************************
878 *
879 * FUNCTION
880 *
881 * expr_new
882 *
883 * INPUT
884 *
885 * current - current poistion in expression tree
886 * stage - stage/precedence of operation
887 * op - operation
888 *
889 * OUTPUT
890 *
891 * RETURNS
892 *
893 * bool - continue to parse expression?
894 *
895 * AUTHOR
896 *
897 * Thorsten Froehlich
898 *
899 * DESCRIPTION
900 *
901 * Expression parser manipulation function that creates a new expression
902 * or subexpression.
903 *
904 * CHANGES
905 *
906 * -
907 *
908 ******************************************************************************/
909
expr_new(ExprNode * & current,int,int)910 bool expr_new(ExprNode *¤t, int /*stage*/, int /*op*/)
911 {
912 ExprNode *node = NULL;
913
914 node = parse_expr();
915 if(node == NULL)
916 return false;
917
918 current->child = node;
919 node->parent = current;
920 node->stage = 10000; // needs to be higher than any other stage for expr_grow to work [trf]
921
922 return true;
923 }
924
925
926 /*****************************************************************************
927 *
928 * FUNCTION
929 *
930 * expr_ret
931 *
932 * INPUT
933 *
934 * current - current poistion in expression tree
935 * stage - stage/precedence of operation
936 * op - operation
937 *
938 * OUTPUT
939 *
940 * RETURNS
941 *
942 * bool - continue to parse expression?
943 *
944 * AUTHOR
945 *
946 * Thorsten Froehlich
947 *
948 * DESCRIPTION
949 *
950 * Expression parser manipulation function that marks the end of parsing
951 * a expression or subexpression.
952 *
953 * CHANGES
954 *
955 * -
956 *
957 ******************************************************************************/
958
expr_ret(ExprNode * &,int,int)959 bool expr_ret(ExprNode *&, int, int)
960 {
961 Unget_Token();
962
963 return false;
964 }
965
966
967 /*****************************************************************************
968 *
969 * FUNCTION
970 *
971 * expr_err
972 *
973 * INPUT
974 *
975 * current - current poistion in expression tree
976 * stage - stage/precedence of operation
977 * op - operation
978 *
979 * OUTPUT
980 *
981 * RETURNS
982 *
983 * bool - continue to parse expression?
984 *
985 * AUTHOR
986 *
987 * Thorsten Froehlich
988 *
989 * DESCRIPTION
990 *
991 * Expression parser manipulation function that terminates all parsing
992 * and outputs a parse error message.
993 *
994 * CHANGES
995 *
996 * -
997 *
998 ******************************************************************************/
999
expr_err(ExprNode * &,int stage,int)1000 bool expr_err(ExprNode *&, int stage, int)
1001 {
1002 int i;
1003
1004 if(stage == 35)
1005 PossibleError("Suspicious identifier found in function!\n"
1006 "If you want to call a function make sure the function you call has been declared.\n"
1007 "If you call an internal function, make sure you have included 'function.inc'.");
1008
1009 for(i = 0; (expr_parser_error_table[i].stage >= 0) && (expr_parser_error_table[i].expected != NULL); i++)
1010 {
1011 if(expr_parser_error_table[i].stage == stage)
1012 Expectation_Error(expr_parser_error_table[i].expected);
1013 }
1014
1015 Expectation_Error("valid function expression");
1016
1017 // unreachable, Expectation_Error stops parsing
1018 return false;
1019 }
1020
1021
1022 /*****************************************************************************
1023 *
1024 * FUNCTION
1025 *
1026 * optimise_expr
1027 *
1028 * INPUT
1029 *
1030 * node - root node of the expression (sub-) tree to optimise
1031 *
1032 * OUTPUT
1033 *
1034 * RETURNS
1035 *
1036 * AUTHOR
1037 *
1038 * Thorsten Froehlich
1039 *
1040 * DESCRIPTION
1041 *
1042 * Optimised an expression (sub-) tree. Currently it only combines
1043 * constants next to each other. Other optimisations are still waiting
1044 * to be implemented.
1045 *
1046 * CHANGES
1047 *
1048 * -
1049 *
1050 ******************************************************************************/
1051
optimise_expr(ExprNode * node)1052 void optimise_expr(ExprNode *node)
1053 {
1054 #ifdef AVOID_MIGHT_BE_USED_UNINITIALIZED_WARNINGS_PATCH
1055 ExprNode *left=NULL,*right,*ptr,*temp;
1056 DBL result=0.0;
1057 #else
1058 ExprNode *left,*right,*ptr,*temp;
1059 DBL result;
1060 #endif
1061 bool have_result;
1062 int op,cnt;
1063
1064 if(node == NULL)
1065 return;
1066
1067 if(node->op == OP_CALL)
1068 {
1069 if(node->call.token == POW_TOKEN)
1070 {
1071 node->op = OP_FIRST;
1072 POV_FREE(node->call.name);
1073 if(node->child != NULL)
1074 {
1075 node->child->op = OP_LEFTMOST;
1076 if(node->child->next != NULL)
1077 {
1078 node->child->next->op = OP_POW;
1079 node->child->next->prev = node->child;
1080 }
1081 }
1082 }
1083 }
1084
1085 if(node->op < OP_FIRST) // using switch statement might be better [trf]
1086 {
1087 ptr = node->next;
1088 if(ptr != NULL)
1089 {
1090 if(ptr->op == OP_NEG)
1091 {
1092 op = ptr->op;
1093 cnt = 0;
1094 for(ptr = node->next; ptr != NULL; ptr = ptr->next)
1095 {
1096 cnt++;
1097 if(ptr->child != NULL)
1098 break;
1099 }
1100
1101 if(ptr != NULL)
1102 {
1103 optimise_expr(ptr->child);
1104 if(ptr->child != NULL)
1105 {
1106 left = ptr->child;
1107 if(left->op == OP_CONSTANT)
1108 {
1109 ptr->child = NULL;
1110
1111 if(node->next != NULL)
1112 FNSyntax_DeleteExpression(node->next);
1113
1114 if(op == OP_NEG)
1115 {
1116 if((cnt % 2) == 0)
1117 node->number = (left->number);
1118 else
1119 node->number = -(left->number);
1120 }
1121 POV_FREE(left);
1122 node->op = OP_CONSTANT;
1123 node->child = NULL;
1124 node->prev = NULL;
1125 node->next = NULL;
1126 return; // early exit
1127 }
1128 }
1129 }
1130 }
1131 }
1132
1133 optimise_expr(node->child);
1134 for(ptr = node->next; ptr != NULL; ptr = ptr->next)
1135 {
1136 left = ptr->prev->child;
1137 right = ptr->child;
1138
1139 if((right != NULL) && (ptr->op == OP_SUB))
1140 {
1141 if(right->op == OP_CONSTANT)
1142 {
1143 ptr->op = OP_ADD;
1144 right->number = -right->number;
1145 }
1146 }
1147
1148 optimise_expr(right);
1149
1150 if((left != NULL) && (right != NULL) &&
1151 (((ptr->op != OP_MUL) && (ptr->op != OP_DIV)) ||
1152 !left_subtree_has_variable_expr(ptr)))
1153 {
1154 if((left->op == OP_CONSTANT) && (right->op == OP_CONSTANT))
1155 {
1156 have_result = true;
1157
1158 switch(ptr->op)
1159 {
1160 case OP_CMP_EQ:
1161 result = (left->number == right->number);
1162 break;
1163 case OP_CMP_NE:
1164 result = (left->number != right->number);
1165 break;
1166 case OP_CMP_LT:
1167 result = (left->number < right->number);
1168 break;
1169 case OP_CMP_LE:
1170 result = (left->number <= right->number);
1171 break;
1172 case OP_CMP_GT:
1173 result = (left->number > right->number);
1174 break;
1175 case OP_CMP_GE:
1176 result = (left->number >= right->number);
1177 break;
1178 case OP_ADD:
1179 result = (left->number + right->number);
1180 break;
1181 case OP_SUB:
1182 result = (left->number - right->number);
1183 break;
1184 case OP_OR:
1185 result = (DBL)(((DBL)((((DBL)(left->number != 0)) + ((DBL)(right->number != 0))))) != 0); // match VM code
1186 break;
1187 case OP_MUL:
1188 result = (left->number * right->number);
1189 break;
1190 case OP_DIV:
1191 result = (left->number / right->number);
1192 break;
1193 case OP_AND:
1194 result = (DBL)((((DBL)(left->number != 0)) * ((DBL)(right->number != 0)))); // match VM code
1195 break;
1196 case OP_POW:
1197 result = pow(left->number, right->number);
1198 break;
1199 default:
1200 have_result = false;
1201 break;
1202 }
1203
1204 if(have_result == true)
1205 {
1206 temp = ptr;
1207 ptr->prev->next = ptr->next;
1208 if(ptr->next != NULL)
1209 ptr->next->prev = ptr->prev;
1210 ptr = ptr->prev;
1211 POV_FREE(temp->child);
1212 POV_FREE(temp);
1213 left->number = result;
1214 }
1215 }
1216 }
1217 }
1218 if((node->next == NULL) && (node->child != NULL) && (node->op < OP_FIRST))
1219 {
1220 if((node->child->op == OP_CONSTANT) && (node->child->next == NULL))
1221 {
1222 node->number = left->number;
1223 node->op = OP_CONSTANT;
1224 POV_FREE(node->child);
1225 node->child = NULL;
1226 }
1227 }
1228 }
1229 else
1230 {
1231 optimise_expr(node->child);
1232
1233 optimise_call(node);
1234
1235 if((node->child != NULL) && (node->op < OP_FIRST))
1236 {
1237 if((node->child->op == OP_CONSTANT) && (node->child->next == NULL))
1238 {
1239 node->number = node->child->number;
1240 POV_FREE(node->child);
1241 node->child = NULL;
1242 node->op = OP_CONSTANT;
1243 }
1244 }
1245 }
1246 }
1247
1248
1249 /*****************************************************************************
1250 *
1251 * FUNCTION
1252 *
1253 * optimise_call
1254 *
1255 * INPUT
1256 *
1257 * node - node of a function call
1258 *
1259 * OUTPUT
1260 *
1261 * RETURNS
1262 *
1263 * AUTHOR
1264 *
1265 * Thorsten Froehlich
1266 *
1267 * DESCRIPTION
1268 *
1269 * Optimises a function call if it has only constant arguments
1270 *
1271 * CHANGES
1272 *
1273 * -
1274 *
1275 ******************************************************************************/
1276
optimise_call(ExprNode * node)1277 void optimise_call(ExprNode *node)
1278 {
1279 DBL result = 0.0;
1280 bool have_result = true;;
1281
1282 if(node->op != OP_CALL)
1283 return;
1284 if(node->child == NULL)
1285 return;
1286 if(node->child->op != OP_CONSTANT)
1287 return;
1288
1289 switch(node->call.token)
1290 {
1291 case SIN_TOKEN:
1292 result = sin(node->child->number);
1293 break;
1294 case COS_TOKEN:
1295 result = cos(node->child->number);
1296 break;
1297 case TAN_TOKEN:
1298 result = tan(node->child->number);
1299 break;
1300 case ASIN_TOKEN:
1301 result = asin(node->child->number);
1302 break;
1303 case ACOS_TOKEN:
1304 result = acos(node->child->number);
1305 break;
1306 case ATAN_TOKEN:
1307 result = atan(node->child->number);
1308 break;
1309 case SINH_TOKEN:
1310 result = sinh(node->child->number);
1311 break;
1312 case COSH_TOKEN:
1313 result = cosh(node->child->number);
1314 break;
1315 case TANH_TOKEN:
1316 result = tanh(node->child->number);
1317 break;
1318 case ASINH_TOKEN:
1319 result = asinh(node->child->number);
1320 break;
1321 case ACOSH_TOKEN:
1322 result = acosh(node->child->number);
1323 break;
1324 case ATANH_TOKEN:
1325 result = atanh(node->child->number);
1326 break;
1327 case ABS_TOKEN:
1328 result = fabs(node->child->number);
1329 break;
1330 case RADIANS_TOKEN:
1331 result = node->child->number * M_PI / 180.0;
1332 break;
1333 case DEGREES_TOKEN:
1334 result = node->child->number * 180.0 / M_PI;
1335 break;
1336 case FLOOR_TOKEN:
1337 result = floor(node->child->number);
1338 break;
1339 case INT_TOKEN:
1340 result = (int)(node->child->number);
1341 break;
1342 case CEIL_TOKEN:
1343 result = ceil(node->child->number);
1344 break;
1345 case SQRT_TOKEN:
1346 result = sqrt(node->child->number);
1347 break;
1348 case EXP_TOKEN:
1349 result = exp(node->child->number);
1350 break;
1351 case LN_TOKEN:
1352 if(node->child->number > 0.0)
1353 result = log(node->child->number);
1354 else
1355 Error("Domain error in 'ln'.");
1356 break;
1357 case LOG_TOKEN:
1358 if(node->child->number > 0.0)
1359 result = log10(node->child->number);
1360 else
1361 Error("Domain error in 'log'.");
1362 break;
1363 case MIN_TOKEN:
1364 have_result = false;
1365 break;
1366 case MAX_TOKEN:
1367 have_result = false;
1368 break;
1369 case ATAN2_TOKEN:
1370 have_result = false;
1371 break;
1372 case POW_TOKEN:
1373 have_result = false;
1374 break;
1375 case MOD_TOKEN:
1376 have_result = false;
1377 break;
1378 case SELECT_TOKEN:
1379 have_result = false;
1380 break;
1381 case FUNCT_ID_TOKEN:
1382 have_result = false;
1383 break;
1384 case VECTFUNCT_ID_TOKEN:
1385 have_result = false;
1386 break;
1387 default:
1388 have_result = false;
1389 break;
1390 }
1391
1392 if(have_result == true)
1393 {
1394 POV_FREE(node->call.name);
1395 node->number = result;
1396 node->op = OP_CONSTANT;
1397 POV_FREE(node->child);
1398 node->child = NULL;
1399 }
1400 }
1401
1402
1403 /*****************************************************************************
1404 *
1405 * FUNCTION
1406 *
1407 * right_subtree_has_variable_expr
1408 *
1409 * INPUT
1410 *
1411 * node - root node of the (sub-) tree to search for variables
1412 *
1413 * OUTPUT
1414 *
1415 * RETURNS
1416 *
1417 * AUTHOR
1418 *
1419 * Thorsten Froehlich
1420 *
1421 * DESCRIPTION
1422 *
1423 * Searches an expression tree to determine if it contains any variables
1424 *
1425 * CHANGES
1426 *
1427 * -
1428 *
1429 ******************************************************************************/
1430
right_subtree_has_variable_expr(ExprNode * node)1431 bool right_subtree_has_variable_expr(ExprNode *node)
1432 {
1433 if(node == NULL)
1434 return false;
1435
1436 for(ExprNode *i = node; i != NULL; i = i->next)
1437 {
1438 if(i->op == OP_VARIABLE)
1439 return true;
1440
1441 if(i->child != NULL)
1442 {
1443 if(right_subtree_has_variable_expr(i->child) == true)
1444 return true;
1445 }
1446 }
1447
1448 return false;
1449 }
1450
1451
1452 /*****************************************************************************
1453 *
1454 * FUNCTION
1455 *
1456 * left_subtree_has_variable_expr
1457 *
1458 * INPUT
1459 *
1460 * node - root node of the (sub-) tree to search for variables
1461 *
1462 * OUTPUT
1463 *
1464 * RETURNS
1465 *
1466 * AUTHOR
1467 *
1468 * Thorsten Froehlich
1469 *
1470 * DESCRIPTION
1471 *
1472 * Searches an expression tree to determine if it contains any variables
1473 *
1474 * CHANGES
1475 *
1476 * -
1477 *
1478 ******************************************************************************/
1479
left_subtree_has_variable_expr(ExprNode * node)1480 bool left_subtree_has_variable_expr(ExprNode *node)
1481 {
1482 if(node == NULL)
1483 return false;
1484
1485 for(ExprNode *i = node; i != NULL; i = i->prev)
1486 {
1487 if(i->op == OP_VARIABLE)
1488 return true;
1489
1490 if(i->child != NULL)
1491 {
1492 if(right_subtree_has_variable_expr(i->child) == true)
1493 return true;
1494 }
1495 }
1496
1497 return false;
1498 }
1499
1500
1501 /*****************************************************************************
1502 *
1503 * FUNCTION
1504 *
1505 * dump_expr
1506 *
1507 * INPUT
1508 *
1509 * f - file to dump to
1510 * node - root node of the (sub-) tree to write to file
1511 *
1512 * OUTPUT
1513 *
1514 * RETURNS
1515 *
1516 * AUTHOR
1517 *
1518 * Thorsten Froehlich
1519 *
1520 * DESCRIPTION
1521 *
1522 * Write an expression tree in inorder notation to a file. Useful for
1523 * debugging the function parser.
1524 *
1525 * CHANGES
1526 *
1527 * -
1528 *
1529 ******************************************************************************/
1530
dump_expr(FILE * f,ExprNode * node)1531 void dump_expr(FILE *f, ExprNode *node)
1532 {
1533 if(node->op == OP_FIRST)
1534 fprintf(f, "[");
1535 else
1536 fprintf(f, "(");
1537
1538 fflush(f);
1539
1540 for(ExprNode *i = node; i != NULL; i = i->next)
1541 {
1542 switch(i->op)
1543 {
1544 case OP_CONSTANT:
1545 fprintf(f, "%f", (float)(i->number));
1546 break;
1547 case OP_VARIABLE:
1548 fprintf(f, "%s", i->variable);
1549 break;
1550 case OP_DOT:
1551 fprintf(f, ".");
1552 break;
1553 case OP_MEMBER:
1554 fprintf(f, "%s", i->variable);
1555 break;
1556 case OP_CALL:
1557 fprintf(f, "fn%d", (int)(i->call.fn));
1558 break;
1559 case OP_CMP_EQ:
1560 fprintf(f, " == ");
1561 break;
1562 case OP_CMP_NE:
1563 fprintf(f, " != ");
1564 break;
1565 case OP_CMP_LT:
1566 fprintf(f, " < ");
1567 break;
1568 case OP_CMP_LE:
1569 fprintf(f, " <= ");
1570 break;
1571 case OP_CMP_GT:
1572 fprintf(f, " > ");
1573 break;
1574 case OP_CMP_GE:
1575 fprintf(f, " >= ");
1576 break;
1577 case OP_ADD:
1578 fprintf(f, " + ");
1579 break;
1580 case OP_SUB:
1581 fprintf(f, " - ");
1582 break;
1583 case OP_OR:
1584 fprintf(f, " | ");
1585 break;
1586 case OP_MUL:
1587 fprintf(f, " * ");
1588 break;
1589 case OP_DIV:
1590 fprintf(f, " / ");
1591 break;
1592 case OP_AND:
1593 fprintf(f, " & ");
1594 break;
1595 case OP_POW:
1596 fprintf(f, " ^ ");
1597 break;
1598 case OP_NEG:
1599 fprintf(f, " -");
1600 break;
1601 case OP_NOT:
1602 fprintf(f, " !");
1603 break;
1604 default:
1605 break;
1606 }
1607
1608 fflush(f);
1609
1610 if(i->child != NULL)
1611 dump_expr(f, i->child);
1612 }
1613
1614 if(node->op == OP_FIRST)
1615 fprintf(f, "]");
1616 else
1617 fprintf(f, ")");
1618
1619 fflush(f);
1620 }
1621
1622 END_POV_NAMESPACE
1623