4 * Copyright (C) 2003 Transmeta Corp.
5 * 2003-2004 Linus Torvalds
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 * This is the expression parsing part of parsing C.
43 #include "expression.h"
47 static int match_oplist(int op
, ...)
54 nextop
= va_arg(args
, int);
55 } while (nextop
!= 0 && nextop
!= op
);
61 static struct token
*comma_expression(struct token
*, struct expression
**);
63 struct token
*parens_expression(struct token
*token
, struct expression
**expr
, const char *where
)
65 token
= expect(token
, '(', where
);
66 if (match_op(token
, '{')) {
67 struct expression
*e
= alloc_expression(token
->pos
, EXPR_STATEMENT
);
68 struct statement
*stmt
= alloc_statement(token
->pos
, STMT_COMPOUND
);
71 start_symbol_scope(e
->pos
);
72 token
= compound_statement(token
->next
, stmt
);
74 token
= expect(token
, '}', "at end of statement expression");
76 token
= parse_expression(token
, expr
);
77 return expect(token
, ')', where
);
81 * Handle __func__, __FUNCTION__ and __PRETTY_FUNCTION__ token
84 static struct symbol
*handle_func(struct token
*token
)
86 struct ident
*ident
= token
->ident
;
87 struct symbol
*decl
, *array
;
88 struct string
*string
;
91 if (ident
!= &__func___ident
&&
92 ident
!= &__FUNCTION___ident
&&
93 ident
!= &__PRETTY_FUNCTION___ident
)
96 if (!current_fn
|| !current_fn
->ident
)
99 /* OK, it's one of ours */
100 array
= alloc_symbol(token
->pos
, SYM_ARRAY
);
101 array
->ctype
.base_type
= &char_ctype
;
102 array
->ctype
.alignment
= 1;
103 array
->endpos
= token
->pos
;
104 decl
= alloc_symbol(token
->pos
, SYM_NODE
);
105 decl
->ctype
.base_type
= array
;
106 decl
->ctype
.alignment
= 1;
107 decl
->ctype
.modifiers
= MOD_STATIC
;
108 decl
->endpos
= token
->pos
;
110 /* function-scope, but in NS_SYMBOL */
111 bind_symbol(decl
, ident
, NS_LABEL
);
112 decl
->namespace = NS_SYMBOL
;
114 len
= current_fn
->ident
->len
;
115 string
= __alloc_string(len
+ 1);
116 memcpy(string
->data
, current_fn
->ident
->name
, len
);
117 string
->data
[len
] = 0;
118 string
->length
= len
+ 1;
120 decl
->initializer
= alloc_expression(token
->pos
, EXPR_STRING
);
121 decl
->initializer
->string
= string
;
122 decl
->initializer
->ctype
= decl
;
123 decl
->array_size
= alloc_const_expression(token
->pos
, len
+ 1);
124 array
->array_size
= decl
->array_size
;
125 decl
->bit_size
= array
->bit_size
= bytes_to_bits(len
+ 1);
130 static struct token
*parse_type(struct token
*token
, struct expression
**tree
)
133 *tree
= alloc_expression(token
->pos
, EXPR_TYPE
);
134 token
= typename(token
, &sym
, NULL
);
136 sparse_error(token
->pos
,
137 "type expression should not include identifier "
138 "\"%s\"", sym
->ident
->name
);
139 (*tree
)->symbol
= sym
;
143 static struct token
*builtin_types_compatible_p_expr(struct token
*token
,
144 struct expression
**tree
)
146 struct expression
*expr
= alloc_expression(
147 token
->pos
, EXPR_COMPARE
);
148 expr
->op
= SPECIAL_EQUAL
;
150 if (!match_op(token
, '('))
151 return expect(token
, '(',
152 "after __builtin_types_compatible_p");
154 token
= parse_type(token
, &expr
->left
);
155 if (!match_op(token
, ','))
156 return expect(token
, ',',
157 "in __builtin_types_compatible_p");
159 token
= parse_type(token
, &expr
->right
);
160 if (!match_op(token
, ')'))
161 return expect(token
, ')',
162 "at end of __builtin_types_compatible_p");
169 static struct token
*builtin_offsetof_expr(struct token
*token
,
170 struct expression
**tree
)
172 struct expression
*expr
= NULL
;
173 struct expression
**p
= &expr
;
178 if (!match_op(token
, '('))
179 return expect(token
, '(', "after __builtin_offset");
182 token
= typename(token
, &sym
, NULL
);
184 sparse_error(token
->pos
,
185 "type expression should not include identifier "
186 "\"%s\"", sym
->ident
->name
);
188 if (!match_op(token
, ','))
189 return expect(token
, ',', "in __builtin_offset");
192 struct expression
*e
;
198 return expect(token
, ')', "at end of __builtin_offset");
199 case SPECIAL_DEREFERENCE
:
200 e
= alloc_expression(token
->pos
, EXPR_OFFSETOF
);
207 e
= alloc_expression(token
->pos
, EXPR_OFFSETOF
);
209 if (token_type(token
) != TOKEN_IDENT
) {
210 sparse_error(token
->pos
, "Expected member name");
213 e
->ident
= token
->ident
;
218 e
= alloc_expression(token
->pos
, EXPR_OFFSETOF
);
220 token
= parse_expression(token
, &e
->index
);
221 token
= expect(token
, ']',
222 "at end of array dereference");
228 op
= token_type(token
) == TOKEN_SPECIAL
? token
->special
: 0;
233 #define ULLONG_MAX (~0ULL)
236 static unsigned long long parse_num(const char *nptr
, char **end
)
238 if (nptr
[0] == '0' && tolower((unsigned char)nptr
[1]) == 'b')
239 return strtoull(&nptr
[2], end
, 2);
240 return strtoull(nptr
, end
, 0);
243 static void get_number_value(struct expression
*expr
, struct token
*token
)
245 const char *str
= token
->number
;
246 unsigned long long value
;
248 int size
= 0, want_unsigned
= 0;
249 int overflow
= 0, do_warn
= 0;
250 int try_unsigned
= 1;
254 value
= parse_num(str
, &end
);
257 if (value
== ULLONG_MAX
&& errno
== ERANGE
)
263 } else if (c
== 'u' || c
== 'U') {
267 } else if (c
== 'l' || c
== 'L') {
280 /* OK, it's a valid integer */
281 /* decimals can be unsigned only if directly specified as such */
282 if (str
[0] != '0' && !want_unsigned
)
285 bits
= bits_in_int
- 1;
286 if (!(value
& (~1ULL << bits
))) {
287 if (!(value
& (1ULL << bits
))) {
289 } else if (try_unsigned
) {
298 bits
= bits_in_long
- 1;
299 if (!(value
& (~1ULL << bits
))) {
300 if (!(value
& (1ULL << bits
))) {
302 } else if (try_unsigned
) {
311 bits
= bits_in_longlong
- 1;
312 if (value
& (~1ULL << bits
))
314 if (!(value
& (1ULL << bits
)))
317 warning(expr
->pos
, "decimal constant %s is too big for long long",
325 warning(expr
->pos
, "constant %s is so big it is%s%s%s",
327 want_unsigned
? " unsigned":"",
328 size
> 0 ? " long":"",
329 size
> 1 ? " long":"");
332 "decimal constant %s is between LONG_MAX and ULONG_MAX."
333 " For C99 that means long long, C90 compilers are very "
334 "likely to produce unsigned long (and a warning) here",
336 expr
->type
= EXPR_VALUE
;
337 expr
->flags
= CEF_SET_INT
;
338 expr
->ctype
= ctype_integer(size
, want_unsigned
);
342 error_die(expr
->pos
, "constant %s is too big even for unsigned long long",
346 expr
->fvalue
= string_to_ld(str
, &end
);
353 if (*end
== 'f' || *end
== 'F')
354 expr
->ctype
= &float_ctype
;
355 else if (*end
== 'l' || *end
== 'L')
356 expr
->ctype
= &ldouble_ctype
;
358 expr
->ctype
= &double_ctype
;
362 expr
->flags
= CEF_SET_FLOAT
;
363 expr
->type
= EXPR_FVALUE
;
367 error_die(expr
->pos
, "constant %s is not a valid number", show_token(token
));
370 struct token
*primary_expression(struct token
*token
, struct expression
**tree
)
372 struct expression
*expr
= NULL
;
374 switch (token_type(token
)) {
375 case TOKEN_CHAR
... TOKEN_WIDE_CHAR_EMBEDDED_3
:
376 expr
= alloc_expression(token
->pos
, EXPR_VALUE
);
377 expr
->flags
= CEF_SET_CHAR
;
378 expr
->ctype
= token_type(token
) < TOKEN_WIDE_CHAR
? &int_ctype
: &long_ctype
;
379 get_char_constant(token
, &expr
->value
);
384 expr
= alloc_expression(token
->pos
, EXPR_VALUE
);
385 get_number_value(expr
, token
); /* will see if it's an integer */
389 case TOKEN_ZERO_IDENT
: {
390 expr
= alloc_expression(token
->pos
, EXPR_SYMBOL
);
391 expr
->flags
= CEF_SET_INT
;
392 expr
->ctype
= &int_ctype
;
393 expr
->symbol
= &zero_int
;
394 expr
->symbol_name
= token
->ident
;
400 struct symbol
*sym
= lookup_symbol(token
->ident
, NS_SYMBOL
| NS_TYPEDEF
);
401 struct token
*next
= token
->next
;
404 sym
= handle_func(token
);
405 if (token
->ident
== &__builtin_types_compatible_p_ident
) {
406 token
= builtin_types_compatible_p_expr(token
, &expr
);
409 if (token
->ident
== &__builtin_offsetof_ident
) {
410 token
= builtin_offsetof_expr(token
, &expr
);
413 } else if (sym
->enum_member
) {
414 expr
= alloc_expression(token
->pos
, EXPR_VALUE
);
415 *expr
= *sym
->initializer
;
416 /* we want the right position reported, thus the copy */
417 expr
->pos
= token
->pos
;
418 expr
->flags
= CEF_SET_ENUM
;
423 expr
= alloc_expression(token
->pos
, EXPR_SYMBOL
);
426 * We support types as real first-class citizens, with type
429 * if (typeof(a) == int) ..
431 if (sym
&& sym
->namespace == NS_TYPEDEF
) {
432 sparse_error(token
->pos
, "typename in expression");
435 expr
->symbol_name
= token
->ident
;
439 * A pointer to an lvalue designating a static storage
440 * duration object is an address constant [6.6(9)].
442 if (sym
&& (sym
->ctype
.modifiers
& (MOD_TOPLEVEL
| MOD_STATIC
)))
443 expr
->flags
= CEF_ADDR
;
450 case TOKEN_WIDE_STRING
:
451 expr
= alloc_expression(token
->pos
, EXPR_STRING
);
452 token
= get_string_constant(token
, expr
);
456 if (token
->special
== '(') {
457 expr
= alloc_expression(token
->pos
, EXPR_PREOP
);
459 token
= parens_expression(token
, &expr
->unop
, "in expression");
462 if (token
->special
== '[' && lookup_type(token
->next
)) {
463 expr
= alloc_expression(token
->pos
, EXPR_TYPE
);
464 token
= typename(token
->next
, &expr
->symbol
, NULL
);
465 token
= expect(token
, ']', "in type expression");
476 static struct token
*expression_list(struct token
*token
, struct expression_list
**list
)
478 while (!match_op(token
, ')')) {
479 struct expression
*expr
= NULL
;
480 token
= assignment_expression(token
, &expr
);
483 add_expression(list
, expr
);
484 if (!match_op(token
, ','))
492 * extend to deal with the ambiguous C grammar for parsing
493 * a cast expressions followed by an initializer.
495 static struct token
*postfix_expression(struct token
*token
, struct expression
**tree
, struct expression
*cast_init_expr
)
497 struct expression
*expr
= cast_init_expr
;
500 token
= primary_expression(token
, &expr
);
502 while (expr
&& token_type(token
) == TOKEN_SPECIAL
) {
503 switch (token
->special
) {
504 case '[': { /* Array dereference */
505 struct expression
*deref
= alloc_expression(token
->pos
, EXPR_PREOP
);
506 struct expression
*add
= alloc_expression(token
->pos
, EXPR_BINOP
);
513 token
= parse_expression(token
->next
, &add
->right
);
514 token
= expect(token
, ']', "at end of array dereference");
518 case SPECIAL_INCREMENT
: /* Post-increment */
519 case SPECIAL_DECREMENT
: { /* Post-decrement */
520 struct expression
*post
= alloc_expression(token
->pos
, EXPR_POSTOP
);
521 post
->op
= token
->special
;
527 case SPECIAL_DEREFERENCE
: { /* Structure pointer member dereference */
528 /* "x->y" is just shorthand for "(*x).y" */
529 struct expression
*inner
= alloc_expression(token
->pos
, EXPR_PREOP
);
535 case '.': { /* Structure member dereference */
536 struct expression
*deref
= alloc_expression(token
->pos
, EXPR_DEREF
);
540 if (token_type(token
) != TOKEN_IDENT
) {
541 sparse_error(token
->pos
, "Expected member name");
544 deref
->member
= token
->ident
;
545 deref
->member_offset
= -1;
551 case '(': { /* Function call */
552 struct expression
*call
= alloc_expression(token
->pos
, EXPR_CALL
);
555 token
= expression_list(token
->next
, &call
->args
);
556 token
= expect(token
, ')', "in function call");
570 static struct token
*cast_expression(struct token
*token
, struct expression
**tree
);
571 static struct token
*unary_expression(struct token
*token
, struct expression
**tree
);
573 static struct token
*type_info_expression(struct token
*token
,
574 struct expression
**tree
, int type
)
576 struct expression
*expr
= alloc_expression(token
->pos
, type
);
580 expr
->flags
= CEF_SET_ICE
; /* XXX: VLA support will need that changed */
582 if (!match_op(token
, '(') || !lookup_type(token
->next
))
583 return unary_expression(token
, &expr
->cast_expression
);
585 token
= typename(token
->next
, &expr
->cast_type
, NULL
);
587 if (!match_op(token
, ')')) {
588 static const char * error
[] = {
589 [EXPR_SIZEOF
] = "at end of sizeof",
590 [EXPR_ALIGNOF
] = "at end of __alignof__",
591 [EXPR_PTRSIZEOF
] = "at end of __sizeof_ptr__"
593 return expect(token
, ')', error
[type
]);
598 * C99 ambiguity: the typename might have been the beginning
599 * of a typed initializer expression..
601 if (match_op(token
, '{')) {
602 struct expression
*cast
= alloc_expression(p
->pos
, EXPR_CAST
);
603 cast
->cast_type
= expr
->cast_type
;
604 expr
->cast_type
= NULL
;
605 expr
->cast_expression
= cast
;
606 token
= initializer(&cast
->cast_expression
, token
);
607 token
= postfix_expression(token
, &expr
->cast_expression
, cast
);
612 static struct token
*unary_expression(struct token
*token
, struct expression
**tree
)
614 if (token_type(token
) == TOKEN_IDENT
) {
615 struct ident
*ident
= token
->ident
;
616 if (ident
->reserved
) {
617 static const struct {
620 } type_information
[] = {
621 { &sizeof_ident
, EXPR_SIZEOF
},
622 { &__alignof___ident
, EXPR_ALIGNOF
},
623 { &__alignof_ident
, EXPR_ALIGNOF
},
624 { &_Alignof_ident
, EXPR_ALIGNOF
},
625 { &__sizeof_ptr___ident
, EXPR_PTRSIZEOF
},
628 for (i
= 0; i
< ARRAY_SIZE(type_information
); i
++) {
629 if (ident
== type_information
[i
].id
)
630 return type_info_expression(token
, tree
, type_information
[i
].type
);
635 if (token_type(token
) == TOKEN_SPECIAL
) {
636 if (match_oplist(token
->special
,
637 SPECIAL_INCREMENT
, SPECIAL_DECREMENT
,
639 struct expression
*unop
;
640 struct expression
*unary
;
643 next
= cast_expression(token
->next
, &unop
);
645 sparse_error(token
->pos
, "Syntax error in unary expression");
649 unary
= alloc_expression(token
->pos
, EXPR_PREOP
);
650 unary
->op
= token
->special
;
655 /* possibly constant ones */
656 if (match_oplist(token
->special
, '+', '-', '~', '!', 0)) {
657 struct expression
*unop
;
658 struct expression
*unary
;
661 next
= cast_expression(token
->next
, &unop
);
663 sparse_error(token
->pos
, "Syntax error in unary expression");
667 unary
= alloc_expression(token
->pos
, EXPR_PREOP
);
668 unary
->op
= token
->special
;
673 /* Gcc extension: &&label gives the address of a label */
674 if (match_op(token
, SPECIAL_LOGICAL_AND
) &&
675 token_type(token
->next
) == TOKEN_IDENT
) {
676 struct expression
*label
= alloc_expression(token
->pos
, EXPR_LABEL
);
677 struct symbol
*sym
= label_symbol(token
->next
);
678 if (!(sym
->ctype
.modifiers
& MOD_ADDRESSABLE
)) {
679 sym
->ctype
.modifiers
|= MOD_ADDRESSABLE
;
680 add_symbol(&function_computed_target_list
, sym
);
682 label
->flags
= CEF_ADDR
;
683 label
->label_symbol
= sym
;
685 return token
->next
->next
;
690 return postfix_expression(token
, tree
, NULL
);
694 * Ambiguity: a '(' can be either a cast-expression or
695 * a primary-expression depending on whether it is followed
698 * additional ambiguity: a "cast expression" followed by
699 * an initializer is really a postfix-expression.
701 static struct token
*cast_expression(struct token
*token
, struct expression
**tree
)
703 if (match_op(token
, '(')) {
704 struct token
*next
= token
->next
;
705 if (lookup_type(next
)) {
706 struct expression
*cast
= alloc_expression(next
->pos
, EXPR_CAST
);
707 struct expression
*v
;
711 token
= typename(next
, &sym
, &is_force
);
712 cast
->cast_type
= sym
;
713 token
= expect(token
, ')', "at end of cast operator");
714 if (match_op(token
, '{')) {
715 if (toplevel(block_scope
))
716 sym
->ctype
.modifiers
|= MOD_TOPLEVEL
;
719 "[force] in compound literal");
720 token
= initializer(&cast
->cast_expression
, token
);
721 return postfix_expression(token
, tree
, cast
);
725 cast
->type
= EXPR_FORCE_CAST
;
726 token
= cast_expression(token
, &v
);
729 cast
->cast_expression
= v
;
733 return unary_expression(token
, tree
);
737 * Generic left-to-right binop parsing
739 * This _really_ needs to be inlined, because that makes the inner
740 * function call statically deterministic rather than a totally
741 * unpredictable indirect call. But gcc-3 is so "clever" that it
742 * doesn't do so by default even when you tell it to inline it.
744 * Making it a macro avoids the inlining problem, and also means
745 * that we can pass in the op-comparison as an expression rather
746 * than create a data structure for it.
749 #define LR_BINOP_EXPRESSION(__token, tree, type, inner, compare) \
750 struct expression *left = NULL; \
751 struct token * next = inner(__token, &left); \
754 while (token_type(next) == TOKEN_SPECIAL) { \
755 struct expression *top, *right = NULL; \
756 int op = next->special; \
760 top = alloc_expression(next->pos, type); \
761 next = inner(next->next, &right); \
763 sparse_error(next->pos, "No right hand side of '%s'-expression", show_special(op)); \
768 top->right = right; \
776 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
779 token
, tree
, EXPR_BINOP
, cast_expression
,
780 (op
== '*') || (op
== '/') || (op
== '%')
784 static struct token
*additive_expression(struct token
*token
, struct expression
**tree
)
787 token
, tree
, EXPR_BINOP
, multiplicative_expression
,
788 (op
== '+') || (op
== '-')
792 static struct token
*shift_expression(struct token
*token
, struct expression
**tree
)
795 token
, tree
, EXPR_BINOP
, additive_expression
,
796 (op
== SPECIAL_LEFTSHIFT
) || (op
== SPECIAL_RIGHTSHIFT
)
800 static struct token
*relational_expression(struct token
*token
, struct expression
**tree
)
803 token
, tree
, EXPR_COMPARE
, shift_expression
,
804 (op
== '<') || (op
== '>') ||
805 (op
== SPECIAL_LTE
) || (op
== SPECIAL_GTE
)
809 static struct token
*equality_expression(struct token
*token
, struct expression
**tree
)
812 token
, tree
, EXPR_COMPARE
, relational_expression
,
813 (op
== SPECIAL_EQUAL
) || (op
== SPECIAL_NOTEQUAL
)
817 static struct token
*bitwise_and_expression(struct token
*token
, struct expression
**tree
)
820 token
, tree
, EXPR_BINOP
, equality_expression
,
825 static struct token
*bitwise_xor_expression(struct token
*token
, struct expression
**tree
)
828 token
, tree
, EXPR_BINOP
, bitwise_and_expression
,
833 static struct token
*bitwise_or_expression(struct token
*token
, struct expression
**tree
)
836 token
, tree
, EXPR_BINOP
, bitwise_xor_expression
,
841 static struct token
*logical_and_expression(struct token
*token
, struct expression
**tree
)
844 token
, tree
, EXPR_LOGICAL
, bitwise_or_expression
,
845 (op
== SPECIAL_LOGICAL_AND
)
849 static struct token
*logical_or_expression(struct token
*token
, struct expression
**tree
)
852 token
, tree
, EXPR_LOGICAL
, logical_and_expression
,
853 (op
== SPECIAL_LOGICAL_OR
)
857 struct token
*conditional_expression(struct token
*token
, struct expression
**tree
)
859 token
= logical_or_expression(token
, tree
);
860 if (*tree
&& match_op(token
, '?')) {
861 struct expression
*expr
= alloc_expression(token
->pos
, EXPR_CONDITIONAL
);
862 expr
->op
= token
->special
;
865 token
= parse_expression(token
->next
, &expr
->cond_true
);
866 token
= expect(token
, ':', "in conditional expression");
867 token
= conditional_expression(token
, &expr
->cond_false
);
872 struct token
*assignment_expression(struct token
*token
, struct expression
**tree
)
874 token
= conditional_expression(token
, tree
);
875 if (*tree
&& token_type(token
) == TOKEN_SPECIAL
) {
876 static const int assignments
[] = {
878 SPECIAL_ADD_ASSIGN
, SPECIAL_SUB_ASSIGN
,
879 SPECIAL_MUL_ASSIGN
, SPECIAL_DIV_ASSIGN
,
880 SPECIAL_MOD_ASSIGN
, SPECIAL_SHL_ASSIGN
,
881 SPECIAL_SHR_ASSIGN
, SPECIAL_AND_ASSIGN
,
882 SPECIAL_OR_ASSIGN
, SPECIAL_XOR_ASSIGN
};
883 int i
, op
= token
->special
;
884 for (i
= 0; i
< ARRAY_SIZE(assignments
); i
++)
885 if (assignments
[i
] == op
) {
886 struct expression
* expr
= alloc_expression(token
->pos
, EXPR_ASSIGNMENT
);
890 return assignment_expression(token
->next
, &expr
->right
);
896 static struct token
*comma_expression(struct token
*token
, struct expression
**tree
)
899 token
, tree
, EXPR_COMMA
, assignment_expression
,
904 struct token
*parse_expression(struct token
*token
, struct expression
**tree
)
906 return comma_expression(token
,tree
);