2 * Expression Abstract Syntax Tree Functions
4 * Copyright 2002 Ove Kaaven
5 * Copyright 2006-2008 Robert Shearman
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
38 static int is_integer_type(const type_t
*type
)
40 switch (type_get_type(type
))
45 switch (type_basic_get_type(type
))
48 case TYPE_BASIC_INT16
:
49 case TYPE_BASIC_INT32
:
50 case TYPE_BASIC_INT64
:
52 case TYPE_BASIC_INT3264
:
54 case TYPE_BASIC_HYPER
:
56 case TYPE_BASIC_WCHAR
:
57 case TYPE_BASIC_ERROR_STATUS_T
:
59 case TYPE_BASIC_FLOAT
:
60 case TYPE_BASIC_DOUBLE
:
61 case TYPE_BASIC_HANDLE
:
70 static int is_signed_integer_type(const type_t
*type
)
72 switch (type_get_type(type
))
77 switch (type_basic_get_type(type
))
80 case TYPE_BASIC_INT16
:
81 case TYPE_BASIC_INT32
:
82 case TYPE_BASIC_INT64
:
84 case TYPE_BASIC_INT3264
:
85 return type_basic_get_sign(type
) < 0;
88 case TYPE_BASIC_HYPER
:
90 case TYPE_BASIC_WCHAR
:
91 case TYPE_BASIC_ERROR_STATUS_T
:
92 case TYPE_BASIC_FLOAT
:
93 case TYPE_BASIC_DOUBLE
:
94 case TYPE_BASIC_HANDLE
:
103 static int is_float_type(const type_t
*type
)
105 return (type_get_type(type
) == TYPE_BASIC
&&
106 (type_basic_get_type(type
) == TYPE_BASIC_FLOAT
||
107 type_basic_get_type(type
) == TYPE_BASIC_DOUBLE
));
110 expr_t
*make_expr(enum expr_type type
)
112 expr_t
*e
= xmalloc(sizeof(expr_t
));
121 expr_t
*make_exprl(enum expr_type type
, int val
)
123 expr_t
*e
= xmalloc(sizeof(expr_t
));
128 /* check for numeric constant */
129 if (type
== EXPR_NUM
|| type
== EXPR_HEXNUM
|| type
== EXPR_TRUEFALSE
)
131 /* make sure true/false value is valid */
132 assert(type
!= EXPR_TRUEFALSE
|| val
== 0 || val
== 1);
139 expr_t
*make_exprd(enum expr_type type
, double val
)
141 expr_t
*e
= xmalloc(sizeof(expr_t
));
150 expr_t
*make_exprs(enum expr_type type
, char *val
)
153 e
= xmalloc(sizeof(expr_t
));
158 /* check for predefined constants */
161 case EXPR_IDENTIFIER
:
163 var_t
*c
= find_const(val
, 0);
169 e
->cval
= c
->eval
->cval
;
175 error_loc("empty character constant\n");
177 error_loc("multi-character constants are endian dependent\n");
190 expr_t
*make_exprt(enum expr_type type
, var_t
*var
, expr_t
*expr
)
195 if (var
->stgclass
!= STG_NONE
&& var
->stgclass
!= STG_REGISTER
)
196 error_loc("invalid storage class for type expression\n");
200 e
= xmalloc(sizeof(expr_t
));
205 if (type
== EXPR_SIZEOF
)
207 /* only do this for types that should be the same on all platforms */
208 if (is_integer_type(tref
) || is_float_type(tref
))
211 e
->cval
= type_memsize(tref
);
214 /* check for cast of constant expression */
215 if (type
== EXPR_CAST
&& expr
->is_const
)
217 if (is_integer_type(tref
))
219 unsigned int cast_type_bits
= type_memsize(tref
) * 8;
220 unsigned int cast_mask
;
223 if (is_signed_integer_type(tref
))
225 cast_mask
= (1u << (cast_type_bits
- 1)) - 1;
226 if (expr
->cval
& (1u << (cast_type_bits
- 1)))
227 e
->cval
= -((-expr
->cval
) & cast_mask
);
229 e
->cval
= expr
->cval
& cast_mask
;
233 /* calculate ((1 << cast_type_bits) - 1) avoiding overflow */
234 cast_mask
= ((1u << (cast_type_bits
- 1)) - 1) |
235 1u << (cast_type_bits
- 1);
236 e
->cval
= expr
->cval
& cast_mask
;
242 e
->cval
= expr
->cval
;
249 expr_t
*make_expr1(enum expr_type type
, expr_t
*expr
)
252 e
= xmalloc(sizeof(expr_t
));
257 /* check for compile-time optimization */
264 e
->cval
= !expr
->cval
;
267 e
->cval
= +expr
->cval
;
270 e
->cval
= -expr
->cval
;
273 e
->cval
= ~expr
->cval
;
283 expr_t
*make_expr2(enum expr_type type
, expr_t
*expr1
, expr_t
*expr2
)
286 e
= xmalloc(sizeof(expr_t
));
291 /* check for compile-time optimization */
292 if (expr1
->is_const
&& expr2
->is_const
)
298 e
->cval
= expr1
->cval
+ expr2
->cval
;
301 e
->cval
= expr1
->cval
- expr2
->cval
;
304 if (expr2
->cval
== 0)
306 error_loc("divide by zero in expression\n");
310 e
->cval
= expr1
->cval
% expr2
->cval
;
313 e
->cval
= expr1
->cval
* expr2
->cval
;
316 if (expr2
->cval
== 0)
318 error_loc("divide by zero in expression\n");
322 e
->cval
= expr1
->cval
/ expr2
->cval
;
325 e
->cval
= expr1
->cval
| expr2
->cval
;
328 e
->cval
= expr1
->cval
& expr2
->cval
;
331 e
->cval
= expr1
->cval
<< expr2
->cval
;
334 e
->cval
= expr1
->cval
>> expr2
->cval
;
337 e
->cval
= expr1
->cval
|| expr2
->cval
;
340 e
->cval
= expr1
->cval
&& expr2
->cval
;
343 e
->cval
= expr1
->cval
^ expr2
->cval
;
346 e
->cval
= expr1
->cval
== expr2
->cval
;
348 case EXPR_INEQUALITY
:
349 e
->cval
= expr1
->cval
!= expr2
->cval
;
352 e
->cval
= expr1
->cval
> expr2
->cval
;
355 e
->cval
= expr1
->cval
< expr2
->cval
;
358 e
->cval
= expr1
->cval
>= expr2
->cval
;
361 e
->cval
= expr1
->cval
<= expr2
->cval
;
371 expr_t
*make_expr3(enum expr_type type
, expr_t
*expr1
, expr_t
*expr2
, expr_t
*expr3
)
374 e
= xmalloc(sizeof(expr_t
));
380 /* check for compile-time optimization */
381 if (expr1
->is_const
&& expr2
->is_const
&& expr3
->is_const
)
387 e
->cval
= expr1
->cval
? expr2
->cval
: expr3
->cval
;
397 struct expression_type
399 int is_variable
; /* is the expression resolved to a variable? */
400 int is_temporary
; /* should the type be freed? */
404 static void check_scalar_type(const struct expr_loc
*expr_loc
,
405 const type_t
*cont_type
, const type_t
*type
)
407 if (!cont_type
|| (!is_integer_type(type
) && !is_ptr(type
) &&
408 !is_float_type(type
)))
409 error_loc_info(&expr_loc
->v
->loc_info
, "scalar type required in expression%s%s\n",
410 expr_loc
->attr
? " for attribute " : "",
411 expr_loc
->attr
? expr_loc
->attr
: "");
414 static void check_arithmetic_type(const struct expr_loc
*expr_loc
,
415 const type_t
*cont_type
, const type_t
*type
)
417 if (!cont_type
|| (!is_integer_type(type
) && !is_float_type(type
)))
418 error_loc_info(&expr_loc
->v
->loc_info
, "arithmetic type required in expression%s%s\n",
419 expr_loc
->attr
? " for attribute " : "",
420 expr_loc
->attr
? expr_loc
->attr
: "");
423 static void check_integer_type(const struct expr_loc
*expr_loc
,
424 const type_t
*cont_type
, const type_t
*type
)
426 if (!cont_type
|| !is_integer_type(type
))
427 error_loc_info(&expr_loc
->v
->loc_info
, "integer type required in expression%s%s\n",
428 expr_loc
->attr
? " for attribute " : "",
429 expr_loc
->attr
? expr_loc
->attr
: "");
432 static type_t
*find_identifier(const char *identifier
, const type_t
*cont_type
, int *found_in_cont_type
)
436 const var_list_t
*fields
= NULL
;
438 *found_in_cont_type
= 0;
442 switch (type_get_type(cont_type
))
445 fields
= type_function_get_args(cont_type
);
448 fields
= type_struct_get_fields(cont_type
);
451 case TYPE_ENCAPSULATED_UNION
:
452 fields
= type_union_get_cases(cont_type
);
466 /* shouldn't get here because of using type_get_type above */
472 if (fields
) LIST_FOR_EACH_ENTRY( field
, fields
, const var_t
, entry
)
473 if (field
->name
&& !strcmp(identifier
, field
->name
))
476 *found_in_cont_type
= 1;
482 var_t
*const_var
= find_const(identifier
, 0);
483 if (const_var
) type
= const_var
->type
;
489 static int is_valid_member_operand(const type_t
*type
)
491 switch (type_get_type(type
))
502 static struct expression_type
resolve_expression(const struct expr_loc
*expr_loc
,
503 const type_t
*cont_type
,
506 struct expression_type result
;
507 result
.is_variable
= FALSE
;
508 result
.is_temporary
= FALSE
;
517 result
.is_temporary
= FALSE
;
518 result
.type
= type_new_int(TYPE_BASIC_INT
, 0);
521 result
.is_temporary
= TRUE
;
522 result
.type
= type_new_pointer(FC_UP
, type_new_int(TYPE_BASIC_CHAR
, 0), NULL
);
525 result
.is_temporary
= TRUE
;
526 result
.type
= type_new_pointer(FC_UP
, type_new_int(TYPE_BASIC_WCHAR
, 0), NULL
);
529 result
.is_temporary
= TRUE
;
530 result
.type
= type_new_int(TYPE_BASIC_CHAR
, 0);
533 result
.is_temporary
= TRUE
;
534 result
.type
= type_new_basic(TYPE_BASIC_DOUBLE
);
536 case EXPR_IDENTIFIER
:
538 int found_in_cont_type
;
539 result
.is_variable
= TRUE
;
540 result
.is_temporary
= FALSE
;
541 result
.type
= find_identifier(e
->u
.sval
, cont_type
, &found_in_cont_type
);
544 error_loc_info(&expr_loc
->v
->loc_info
, "identifier %s cannot be resolved in expression%s%s\n",
545 e
->u
.sval
, expr_loc
->attr
? " for attribute " : "",
546 expr_loc
->attr
? expr_loc
->attr
: "");
551 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
552 check_scalar_type(expr_loc
, cont_type
, result
.type
);
553 result
.is_variable
= FALSE
;
554 result
.is_temporary
= FALSE
;
555 result
.type
= type_new_int(TYPE_BASIC_INT
, 0);
558 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
559 check_integer_type(expr_loc
, cont_type
, result
.type
);
560 result
.is_variable
= FALSE
;
564 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
565 check_arithmetic_type(expr_loc
, cont_type
, result
.type
);
566 result
.is_variable
= FALSE
;
569 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
570 if (!result
.is_variable
)
571 error_loc_info(&expr_loc
->v
->loc_info
, "address-of operator applied to non-variable type in expression%s%s\n",
572 expr_loc
->attr
? " for attribute " : "",
573 expr_loc
->attr
? expr_loc
->attr
: "");
574 result
.is_variable
= FALSE
;
575 result
.is_temporary
= TRUE
;
576 result
.type
= type_new_pointer(FC_UP
, result
.type
, NULL
);
579 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
580 if (result
.type
&& is_ptr(result
.type
))
581 result
.type
= type_pointer_get_ref(result
.type
);
582 else if(result
.type
&& is_array(result
.type
)
583 && type_array_is_decl_as_ptr(result
.type
))
584 result
.type
= type_array_get_element(result
.type
);
586 error_loc_info(&expr_loc
->v
->loc_info
, "dereference operator applied to non-pointer type in expression%s%s\n",
587 expr_loc
->attr
? " for attribute " : "",
588 expr_loc
->attr
? expr_loc
->attr
: "");
591 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
592 result
.type
= e
->u
.tref
;
595 result
.is_temporary
= FALSE
;
596 result
.type
= type_new_int(TYPE_BASIC_INT
, 0);
609 struct expression_type result_right
;
610 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
611 result
.is_variable
= FALSE
;
612 result_right
= resolve_expression(expr_loc
, cont_type
, e
->u
.ext
);
613 /* FIXME: these checks aren't strict enough for some of the operators */
614 check_scalar_type(expr_loc
, cont_type
, result
.type
);
615 check_scalar_type(expr_loc
, cont_type
, result_right
.type
);
621 case EXPR_INEQUALITY
:
627 struct expression_type result_left
, result_right
;
628 result_left
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
629 result_right
= resolve_expression(expr_loc
, cont_type
, e
->u
.ext
);
630 check_scalar_type(expr_loc
, cont_type
, result_left
.type
);
631 check_scalar_type(expr_loc
, cont_type
, result_right
.type
);
632 result
.is_temporary
= FALSE
;
633 result
.type
= type_new_int(TYPE_BASIC_INT
, 0);
637 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
638 if (result
.type
&& is_valid_member_operand(result
.type
))
639 result
= resolve_expression(expr_loc
, result
.type
, e
->u
.ext
);
641 error_loc_info(&expr_loc
->v
->loc_info
, "'.' or '->' operator applied to a type that isn't a structure, union or enumeration in expression%s%s\n",
642 expr_loc
->attr
? " for attribute " : "",
643 expr_loc
->attr
? expr_loc
->attr
: "");
647 struct expression_type result_first
, result_second
, result_third
;
648 result_first
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
649 check_scalar_type(expr_loc
, cont_type
, result_first
.type
);
650 result_second
= resolve_expression(expr_loc
, cont_type
, e
->u
.ext
);
651 result_third
= resolve_expression(expr_loc
, cont_type
, e
->ext2
);
652 check_scalar_type(expr_loc
, cont_type
, result_second
.type
);
653 check_scalar_type(expr_loc
, cont_type
, result_third
.type
);
654 if (!is_ptr(result_second
.type
) ^ !is_ptr(result_third
.type
))
655 error_loc_info(&expr_loc
->v
->loc_info
, "type mismatch in ?: expression\n" );
656 /* FIXME: determine the correct return type */
657 result
= result_second
;
658 result
.is_variable
= FALSE
;
662 result
= resolve_expression(expr_loc
, cont_type
, e
->ref
);
663 if (result
.type
&& is_array(result
.type
))
665 struct expression_type index_result
;
666 result
.type
= type_array_get_element(result
.type
);
667 index_result
= resolve_expression(expr_loc
, cont_type
/* FIXME */, e
->u
.ext
);
668 if (!index_result
.type
|| !is_integer_type(index_result
.type
))
669 error_loc_info(&expr_loc
->v
->loc_info
, "array subscript not of integral type in expression%s%s\n",
670 expr_loc
->attr
? " for attribute " : "",
671 expr_loc
->attr
? expr_loc
->attr
: "");
674 error_loc_info(&expr_loc
->v
->loc_info
, "array subscript operator applied to non-array type in expression%s%s\n",
675 expr_loc
->attr
? " for attribute " : "",
676 expr_loc
->attr
? expr_loc
->attr
: "");
682 const type_t
*expr_resolve_type(const struct expr_loc
*expr_loc
, const type_t
*cont_type
, const expr_t
*expr
)
684 struct expression_type expr_type
;
685 expr_type
= resolve_expression(expr_loc
, cont_type
, expr
);
686 return expr_type
.type
;
689 void write_expr(FILE *h
, const expr_t
*e
, int brackets
,
690 int toplevel
, const char *toplevel_prefix
,
691 const type_t
*cont_type
, const char *local_var_prefix
)
698 fprintf(h
, "%u", e
->u
.lval
);
701 fprintf(h
, "0x%x", e
->u
.lval
);
704 fprintf(h
, "%#.15g", e
->u
.dval
);
712 case EXPR_IDENTIFIER
:
713 if (toplevel
&& toplevel_prefix
&& cont_type
)
715 int found_in_cont_type
;
716 find_identifier(e
->u
.sval
, cont_type
, &found_in_cont_type
);
717 if (found_in_cont_type
)
719 fprintf(h
, "%s%s", toplevel_prefix
, e
->u
.sval
);
723 fprintf(h
, "%s%s", local_var_prefix
, e
->u
.sval
);
726 fprintf(h
, "\"%s\"", e
->u
.sval
);
729 fprintf(h
, "L\"%s\"", e
->u
.sval
);
732 fprintf(h
, "'%s'", e
->u
.sval
);
736 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
740 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
744 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
748 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
752 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
756 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
760 write_type_decl(h
, e
->u
.tref
, NULL
);
762 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
765 fprintf(h
, "sizeof(");
766 write_type_decl(h
, e
->u
.tref
, NULL
);
782 case EXPR_INEQUALITY
:
787 if (brackets
) fprintf(h
, "(");
788 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
791 case EXPR_SHL
: fprintf(h
, " << "); break;
792 case EXPR_SHR
: fprintf(h
, " >> "); break;
793 case EXPR_MOD
: fprintf(h
, " %% "); break;
794 case EXPR_MUL
: fprintf(h
, " * "); break;
795 case EXPR_DIV
: fprintf(h
, " / "); break;
796 case EXPR_ADD
: fprintf(h
, " + "); break;
797 case EXPR_SUB
: fprintf(h
, " - "); break;
798 case EXPR_AND
: fprintf(h
, " & "); break;
799 case EXPR_OR
: fprintf(h
, " | "); break;
800 case EXPR_LOGOR
: fprintf(h
, " || "); break;
801 case EXPR_LOGAND
: fprintf(h
, " && "); break;
802 case EXPR_XOR
: fprintf(h
, " ^ "); break;
803 case EXPR_EQUALITY
: fprintf(h
, " == "); break;
804 case EXPR_INEQUALITY
: fprintf(h
, " != "); break;
805 case EXPR_GTR
: fprintf(h
, " > "); break;
806 case EXPR_LESS
: fprintf(h
, " < "); break;
807 case EXPR_GTREQL
: fprintf(h
, " >= "); break;
808 case EXPR_LESSEQL
: fprintf(h
, " <= "); break;
811 write_expr(h
, e
->u
.ext
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
812 if (brackets
) fprintf(h
, ")");
815 if (brackets
) fprintf(h
, "(");
816 if (e
->ref
->type
== EXPR_PPTR
)
818 write_expr(h
, e
->ref
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
823 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
826 write_expr(h
, e
->u
.ext
, 1, 0, toplevel_prefix
, cont_type
, "");
827 if (brackets
) fprintf(h
, ")");
830 if (brackets
) fprintf(h
, "(");
831 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
833 write_expr(h
, e
->u
.ext
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
835 write_expr(h
, e
->ext2
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
836 if (brackets
) fprintf(h
, ")");
839 if (brackets
) fprintf(h
, "(");
840 write_expr(h
, e
->ref
, 1, toplevel
, toplevel_prefix
, cont_type
, local_var_prefix
);
842 write_expr(h
, e
->u
.ext
, 1, 1, toplevel_prefix
, cont_type
, local_var_prefix
);
844 if (brackets
) fprintf(h
, ")");
849 /* This is actually fairly involved to implement precisely, due to the
850 effects attributes may have and things like that. Right now this is
851 only used for optimization, so just check for a very small set of
852 criteria that guarantee the types are equivalent; assume every thing
853 else is different. */
854 static int compare_type(const type_t
*a
, const type_t
*b
)
859 && strcmp(a
->name
, b
->name
) == 0))
861 /* Ordering doesn't need to be implemented yet. */
865 int compare_expr(const expr_t
*a
, const expr_t
*b
)
869 if (a
->type
!= b
->type
)
870 return a
->type
- b
->type
;
877 return a
->u
.lval
- b
->u
.lval
;
879 return a
->u
.dval
- b
->u
.dval
;
880 case EXPR_IDENTIFIER
:
884 return strcmp(a
->u
.sval
, b
->u
.sval
);
886 ret
= compare_expr(a
->ref
, b
->ref
);
889 ret
= compare_expr(a
->u
.ext
, b
->u
.ext
);
892 return compare_expr(a
->ext2
, b
->ext2
);
908 case EXPR_INEQUALITY
:
913 ret
= compare_expr(a
->ref
, b
->ref
);
916 return compare_expr(a
->u
.ext
, b
->u
.ext
);
918 ret
= compare_type(a
->u
.tref
, b
->u
.tref
);
928 return compare_expr(a
->ref
, b
->ref
);
930 return compare_type(a
->u
.tref
, b
->u
.tref
);