ParseExpr.cpp revision 85bb3dad385e9c2a57cf5aa2d2116d8381953a5a 
1//===--- ParseExpr.cpp - Expression Parsing -------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the Expression parsing implementation.  Expressions in
11// C99 basically consist of a bunch of binary operators with unary operators and
12// other random stuff at the leaves.
13//
14// In the C99 grammar, these unary operators bind tightest and are represented
15// as the 'cast-expression' production.  Everything else is either a binary
16// operator (e.g. '/') or a ternary operator ("?:").  The unary leaves are
17// handled by ParseCastExpression, the higher level pieces are handled by
18// ParseBinaryExpression.
19//
20//===----------------------------------------------------------------------===//
21
22#include "clang/Parse/Parser.h"
23#include "clang/Parse/DeclSpec.h"
24#include "clang/Parse/Scope.h"
25#include "ExtensionRAIIObject.h"
26#include "llvm/ADT/SmallVector.h"
27#include "llvm/ADT/SmallString.h"
28using namespace clang;
29
30/// PrecedenceLevels - These are precedences for the binary/ternary operators in
31/// the C99 grammar.  These have been named to relate with the C99 grammar
32/// productions.  Low precedences numbers bind more weakly than high numbers.
33namespace prec {
34  enum Level {
35    Unknown        = 0,    // Not binary operator.
36    Comma          = 1,    // ,
37    Assignment     = 2,    // =, *=, /=, %=, +=, -=, <<=, >>=, &=, ^=, |=
38    Conditional    = 3,    // ?
39    LogicalOr      = 4,    // ||
40    LogicalAnd     = 5,    // &&
41    InclusiveOr    = 6,    // |
42    ExclusiveOr    = 7,    // ^
43    And            = 8,    // &
44    Equality       = 9,    // ==, !=
45    Relational     = 10,   //  >=, <=, >, <
46    Shift          = 11,   // <<, >>
47    Additive       = 12,   // -, +
48    Multiplicative = 13    // *, /, %
49  };
50}
51
52
53/// getBinOpPrecedence - Return the precedence of the specified binary operator
54/// token.  This returns:
55///
56static prec::Level getBinOpPrecedence(tok::TokenKind Kind) {
57  switch (Kind) {
58  default:                        return prec::Unknown;
59  case tok::comma:                return prec::Comma;
60  case tok::equal:
61  case tok::starequal:
62  case tok::slashequal:
63  case tok::percentequal:
64  case tok::plusequal:
65  case tok::minusequal:
66  case tok::lesslessequal:
67  case tok::greatergreaterequal:
68  case tok::ampequal:
69  case tok::caretequal:
70  case tok::pipeequal:            return prec::Assignment;
71  case tok::question:             return prec::Conditional;
72  case tok::pipepipe:             return prec::LogicalOr;
73  case tok::ampamp:               return prec::LogicalAnd;
74  case tok::pipe:                 return prec::InclusiveOr;
75  case tok::caret:                return prec::ExclusiveOr;
76  case tok::amp:                  return prec::And;
77  case tok::exclaimequal:
78  case tok::equalequal:           return prec::Equality;
79  case tok::lessequal:
80  case tok::less:
81  case tok::greaterequal:
82  case tok::greater:              return prec::Relational;
83  case tok::lessless:
84  case tok::greatergreater:       return prec::Shift;
85  case tok::plus:
86  case tok::minus:                return prec::Additive;
87  case tok::percent:
88  case tok::slash:
89  case tok::star:                 return prec::Multiplicative;
90  }
91}
92
93
94/// ParseExpression - Simple precedence-based parser for binary/ternary
95/// operators.
96///
97/// Note: we diverge from the C99 grammar when parsing the assignment-expression
98/// production.  C99 specifies that the LHS of an assignment operator should be
99/// parsed as a unary-expression, but consistency dictates that it be a
100/// conditional-expession.  In practice, the important thing here is that the
101/// LHS of an assignment has to be an l-value, which productions between
102/// unary-expression and conditional-expression don't produce.  Because we want
103/// consistency, we parse the LHS as a conditional-expression, then check for
104/// l-value-ness in semantic analysis stages.
105///
106///       multiplicative-expression: [C99 6.5.5]
107///         cast-expression
108///         multiplicative-expression '*' cast-expression
109///         multiplicative-expression '/' cast-expression
110///         multiplicative-expression '%' cast-expression
111///
112///       additive-expression: [C99 6.5.6]
113///         multiplicative-expression
114///         additive-expression '+' multiplicative-expression
115///         additive-expression '-' multiplicative-expression
116///
117///       shift-expression: [C99 6.5.7]
118///         additive-expression
119///         shift-expression '<<' additive-expression
120///         shift-expression '>>' additive-expression
121///
122///       relational-expression: [C99 6.5.8]
123///         shift-expression
124///         relational-expression '<' shift-expression
125///         relational-expression '>' shift-expression
126///         relational-expression '<=' shift-expression
127///         relational-expression '>=' shift-expression
128///
129///       equality-expression: [C99 6.5.9]
130///         relational-expression
131///         equality-expression '==' relational-expression
132///         equality-expression '!=' relational-expression
133///
134///       AND-expression: [C99 6.5.10]
135///         equality-expression
136///         AND-expression '&' equality-expression
137///
138///       exclusive-OR-expression: [C99 6.5.11]
139///         AND-expression
140///         exclusive-OR-expression '^' AND-expression
141///
142///       inclusive-OR-expression: [C99 6.5.12]
143///         exclusive-OR-expression
144///         inclusive-OR-expression '|' exclusive-OR-expression
145///
146///       logical-AND-expression: [C99 6.5.13]
147///         inclusive-OR-expression
148///         logical-AND-expression '&&' inclusive-OR-expression
149///
150///       logical-OR-expression: [C99 6.5.14]
151///         logical-AND-expression
152///         logical-OR-expression '||' logical-AND-expression
153///
154///       conditional-expression: [C99 6.5.15]
155///         logical-OR-expression
156///         logical-OR-expression '?' expression ':' conditional-expression
157/// [GNU]   logical-OR-expression '?' ':' conditional-expression
158///
159///       assignment-expression: [C99 6.5.16]
160///         conditional-expression
161///         unary-expression assignment-operator assignment-expression
162/// [C++]   throw-expression [C++ 15]
163///
164///       assignment-operator: one of
165///         = *= /= %= += -= <<= >>= &= ^= |=
166///
167///       expression: [C99 6.5.17]
168///         assignment-expression
169///         expression ',' assignment-expression
170///
171Parser::ExprResult Parser::ParseExpression() {
172  if (Tok.is(tok::kw_throw))
173    return ParseThrowExpression();
174
175  ExprResult LHS = ParseCastExpression(false);
176  if (LHS.isInvalid) return LHS;
177
178  return ParseRHSOfBinaryExpression(LHS, prec::Comma);
179}
180
181/// This routine is called when the '@' is seen and consumed.
182/// Current token is an Identifier and is not a 'try'. This
183/// routine is necessary to disambiguate @try-statement from,
184/// for example, @encode-expression.
185///
186Parser::ExprResult Parser::ParseExpressionWithLeadingAt(SourceLocation AtLoc) {
187  ExprResult LHS = ParseObjCAtExpression(AtLoc);
188  if (LHS.isInvalid) return LHS;
189
190  return ParseRHSOfBinaryExpression(LHS, prec::Comma);
191}
192
193/// ParseAssignmentExpression - Parse an expr that doesn't include commas.
194///
195Parser::ExprResult Parser::ParseAssignmentExpression() {
196  if (Tok.is(tok::kw_throw))
197    return ParseThrowExpression();
198
199  ExprResult LHS = ParseCastExpression(false);
200  if (LHS.isInvalid) return LHS;
201
202  return ParseRHSOfBinaryExpression(LHS, prec::Assignment);
203}
204
205/// ParseAssignmentExprWithObjCMessageExprStart - Parse an assignment expression
206/// where part of an objc message send has already been parsed.  In this case
207/// LBracLoc indicates the location of the '[' of the message send, and either
208/// ReceiverName or ReceiverExpr is non-null indicating the receiver of the
209/// message.
210///
211/// Since this handles full assignment-expression's, it handles postfix
212/// expressions and other binary operators for these expressions as well.
213Parser::ExprResult
214Parser::ParseAssignmentExprWithObjCMessageExprStart(SourceLocation LBracLoc,
215                                                   IdentifierInfo *ReceiverName,
216                                                    ExprTy *ReceiverExpr) {
217  ExprResult R = ParseObjCMessageExpressionBody(LBracLoc, ReceiverName,
218                                                ReceiverExpr);
219  if (R.isInvalid) return R;
220  R = ParsePostfixExpressionSuffix(R);
221  if (R.isInvalid) return R;
222  return ParseRHSOfBinaryExpression(R, 2);
223}
224
225
226Parser::ExprResult Parser::ParseConstantExpression() {
227  ExprResult LHS = ParseCastExpression(false);
228  if (LHS.isInvalid) return LHS;
229
230  return ParseRHSOfBinaryExpression(LHS, prec::Conditional);
231}
232
233/// ParseRHSOfBinaryExpression - Parse a binary expression that starts with
234/// LHS and has a precedence of at least MinPrec.
235Parser::ExprResult
236Parser::ParseRHSOfBinaryExpression(ExprResult LHS, unsigned MinPrec) {
237  unsigned NextTokPrec = getBinOpPrecedence(Tok.getKind());
238  SourceLocation ColonLoc;
239
240  while (1) {
241    // If this token has a lower precedence than we are allowed to parse (e.g.
242    // because we are called recursively, or because the token is not a binop),
243    // then we are done!
244    if (NextTokPrec < MinPrec)
245      return LHS;
246
247    // Consume the operator, saving the operator token for error reporting.
248    Token OpToken = Tok;
249    ConsumeToken();
250
251    // Special case handling for the ternary operator.
252    ExprResult TernaryMiddle(true);
253    if (NextTokPrec == prec::Conditional) {
254      if (Tok.isNot(tok::colon)) {
255        // Handle this production specially:
256        //   logical-OR-expression '?' expression ':' conditional-expression
257        // In particular, the RHS of the '?' is 'expression', not
258        // 'logical-OR-expression' as we might expect.
259        TernaryMiddle = ParseExpression();
260        if (TernaryMiddle.isInvalid) {
261          Actions.DeleteExpr(LHS.Val);
262          return TernaryMiddle;
263        }
264      } else {
265        // Special case handling of "X ? Y : Z" where Y is empty:
266        //   logical-OR-expression '?' ':' conditional-expression   [GNU]
267        TernaryMiddle = ExprResult(false);
268        Diag(Tok, diag::ext_gnu_conditional_expr);
269      }
270
271      if (Tok.isNot(tok::colon)) {
272        Diag(Tok, diag::err_expected_colon);
273        Diag(OpToken, diag::err_matching, "?");
274        Actions.DeleteExpr(LHS.Val);
275        Actions.DeleteExpr(TernaryMiddle.Val);
276        return ExprResult(true);
277      }
278
279      // Eat the colon.
280      ColonLoc = ConsumeToken();
281    }
282
283    // Parse another leaf here for the RHS of the operator.
284    ExprResult RHS = ParseCastExpression(false);
285    if (RHS.isInvalid) {
286      Actions.DeleteExpr(LHS.Val);
287      Actions.DeleteExpr(TernaryMiddle.Val);
288      return RHS;
289    }
290
291    // Remember the precedence of this operator and get the precedence of the
292    // operator immediately to the right of the RHS.
293    unsigned ThisPrec = NextTokPrec;
294    NextTokPrec = getBinOpPrecedence(Tok.getKind());
295
296    // Assignment and conditional expressions are right-associative.
297    bool isRightAssoc = ThisPrec == prec::Conditional ||
298                        ThisPrec == prec::Assignment;
299
300    // Get the precedence of the operator to the right of the RHS.  If it binds
301    // more tightly with RHS than we do, evaluate it completely first.
302    if (ThisPrec < NextTokPrec ||
303        (ThisPrec == NextTokPrec && isRightAssoc)) {
304      // If this is left-associative, only parse things on the RHS that bind
305      // more tightly than the current operator.  If it is left-associative, it
306      // is okay, to bind exactly as tightly.  For example, compile A=B=C=D as
307      // A=(B=(C=D)), where each paren is a level of recursion here.
308      RHS = ParseRHSOfBinaryExpression(RHS, ThisPrec + !isRightAssoc);
309      if (RHS.isInvalid) {
310        Actions.DeleteExpr(LHS.Val);
311        Actions.DeleteExpr(TernaryMiddle.Val);
312        return RHS;
313      }
314
315      NextTokPrec = getBinOpPrecedence(Tok.getKind());
316    }
317    assert(NextTokPrec <= ThisPrec && "Recursion didn't work!");
318
319    if (!LHS.isInvalid) {
320      // Combine the LHS and RHS into the LHS (e.g. build AST).
321      if (TernaryMiddle.isInvalid)
322        LHS = Actions.ActOnBinOp(OpToken.getLocation(), OpToken.getKind(),
323                                 LHS.Val, RHS.Val);
324      else
325        LHS = Actions.ActOnConditionalOp(OpToken.getLocation(), ColonLoc,
326                                         LHS.Val, TernaryMiddle.Val, RHS.Val);
327    } else {
328      // We had a semantic error on the LHS.  Just free the RHS and continue.
329      Actions.DeleteExpr(TernaryMiddle.Val);
330      Actions.DeleteExpr(RHS.Val);
331    }
332  }
333}
334
335/// ParseCastExpression - Parse a cast-expression, or, if isUnaryExpression is
336/// true, parse a unary-expression.
337///
338///       cast-expression: [C99 6.5.4]
339///         unary-expression
340///         '(' type-name ')' cast-expression
341///
342///       unary-expression:  [C99 6.5.3]
343///         postfix-expression
344///         '++' unary-expression
345///         '--' unary-expression
346///         unary-operator cast-expression
347///         'sizeof' unary-expression
348///         'sizeof' '(' type-name ')'
349/// [GNU]   '__alignof' unary-expression
350/// [GNU]   '__alignof' '(' type-name ')'
351/// [C++0x] 'alignof' '(' type-id ')'
352/// [GNU]   '&&' identifier
353///
354///       unary-operator: one of
355///         '&'  '*'  '+'  '-'  '~'  '!'
356/// [GNU]   '__extension__'  '__real'  '__imag'
357///
358///       primary-expression: [C99 6.5.1]
359///         identifier
360///         constant
361///         string-literal
362/// [C++]   boolean-literal  [C++ 2.13.5]
363///         '(' expression ')'
364///         '__func__'        [C99 6.4.2.2]
365/// [GNU]   '__FUNCTION__'
366/// [GNU]   '__PRETTY_FUNCTION__'
367/// [GNU]   '(' compound-statement ')'
368/// [GNU]   '__builtin_va_arg' '(' assignment-expression ',' type-name ')'
369/// [GNU]   '__builtin_offsetof' '(' type-name ',' offsetof-member-designator')'
370/// [GNU]   '__builtin_choose_expr' '(' assign-expr ',' assign-expr ','
371///                                     assign-expr ')'
372/// [GNU]   '__builtin_types_compatible_p' '(' type-name ',' type-name ')'
373/// [OBJC]  '[' objc-message-expr ']'
374/// [OBJC]  '@selector' '(' objc-selector-arg ')'
375/// [OBJC]  '@protocol' '(' identifier ')'
376/// [OBJC]  '@encode' '(' type-name ')'
377/// [OBJC]  objc-string-literal
378/// [C++]   simple-type-specifier '(' expression-list[opt] ')'      [C++ 5.2.3]
379/// [C++]   typename-specifier '(' expression-list[opt] ')'         [TODO]
380/// [C++]   'const_cast' '<' type-name '>' '(' expression ')'       [C++ 5.2p1]
381/// [C++]   'dynamic_cast' '<' type-name '>' '(' expression ')'     [C++ 5.2p1]
382/// [C++]   'reinterpret_cast' '<' type-name '>' '(' expression ')' [C++ 5.2p1]
383/// [C++]   'static_cast' '<' type-name '>' '(' expression ')'      [C++ 5.2p1]
384/// [C++]   'this'          [C++ 9.3.2]
385/// [clang] '^' block-literal
386///
387///       constant: [C99 6.4.4]
388///         integer-constant
389///         floating-constant
390///         enumeration-constant -> identifier
391///         character-constant
392///
393Parser::ExprResult Parser::ParseCastExpression(bool isUnaryExpression) {
394  ExprResult Res;
395  tok::TokenKind SavedKind = Tok.getKind();
396
397  // This handles all of cast-expression, unary-expression, postfix-expression,
398  // and primary-expression.  We handle them together like this for efficiency
399  // and to simplify handling of an expression starting with a '(' token: which
400  // may be one of a parenthesized expression, cast-expression, compound literal
401  // expression, or statement expression.
402  //
403  // If the parsed tokens consist of a primary-expression, the cases below
404  // call ParsePostfixExpressionSuffix to handle the postfix expression
405  // suffixes.  Cases that cannot be followed by postfix exprs should
406  // return without invoking ParsePostfixExpressionSuffix.
407  switch (SavedKind) {
408  case tok::l_paren: {
409    // If this expression is limited to being a unary-expression, the parent can
410    // not start a cast expression.
411    ParenParseOption ParenExprType =
412      isUnaryExpression ? CompoundLiteral : CastExpr;
413    TypeTy *CastTy;
414    SourceLocation LParenLoc = Tok.getLocation();
415    SourceLocation RParenLoc;
416    Res = ParseParenExpression(ParenExprType, CastTy, RParenLoc);
417    if (Res.isInvalid) return Res;
418
419    switch (ParenExprType) {
420    case SimpleExpr:   break;    // Nothing else to do.
421    case CompoundStmt: break;  // Nothing else to do.
422    case CompoundLiteral:
423      // We parsed '(' type-name ')' '{' ... '}'.  If any suffixes of
424      // postfix-expression exist, parse them now.
425      break;
426    case CastExpr:
427      // We parsed '(' type-name ')' and the thing after it wasn't a '{'.  Parse
428      // the cast-expression that follows it next.
429      // TODO: For cast expression with CastTy.
430      Res = ParseCastExpression(false);
431      if (!Res.isInvalid)
432        Res = Actions.ActOnCastExpr(LParenLoc, CastTy, RParenLoc, Res.Val);
433      return Res;
434    }
435
436    // These can be followed by postfix-expr pieces.
437    return ParsePostfixExpressionSuffix(Res);
438  }
439
440    // primary-expression
441  case tok::numeric_constant:
442    // constant: integer-constant
443    // constant: floating-constant
444
445    Res = Actions.ActOnNumericConstant(Tok);
446    ConsumeToken();
447
448    // These can be followed by postfix-expr pieces.
449    return ParsePostfixExpressionSuffix(Res);
450
451  case tok::kw_true:
452  case tok::kw_false:
453    return ParseCXXBoolLiteral();
454
455  case tok::identifier: {
456    if (getLang().CPlusPlus &&
457        Actions.isTypeName(*Tok.getIdentifierInfo(), CurScope)) {
458      // Handle C++ function-style cast, e.g. "T(4.5)" where T is a typedef for
459      // double.
460      goto HandleType;
461    }
462
463    // primary-expression: identifier
464    // constant: enumeration-constant
465
466    // Consume the identifier so that we can see if it is followed by a '('.
467    // Function designators are allowed to be undeclared (C99 6.5.1p2), so we
468    // need to know whether or not this identifier is a function designator or
469    // not.
470    IdentifierInfo &II = *Tok.getIdentifierInfo();
471    SourceLocation L = ConsumeToken();
472    Res = Actions.ActOnIdentifierExpr(CurScope, L, II, Tok.is(tok::l_paren));
473    // These can be followed by postfix-expr pieces.
474    return ParsePostfixExpressionSuffix(Res);
475  }
476  case tok::char_constant:     // constant: character-constant
477    Res = Actions.ActOnCharacterConstant(Tok);
478    ConsumeToken();
479    // These can be followed by postfix-expr pieces.
480    return ParsePostfixExpressionSuffix(Res);
481  case tok::kw___func__:       // primary-expression: __func__ [C99 6.4.2.2]
482  case tok::kw___FUNCTION__:   // primary-expression: __FUNCTION__ [GNU]
483  case tok::kw___PRETTY_FUNCTION__:  // primary-expression: __P..Y_F..N__ [GNU]
484    Res = Actions.ActOnPredefinedExpr(Tok.getLocation(), SavedKind);
485    ConsumeToken();
486    // These can be followed by postfix-expr pieces.
487    return ParsePostfixExpressionSuffix(Res);
488  case tok::string_literal:    // primary-expression: string-literal
489  case tok::wide_string_literal:
490    Res = ParseStringLiteralExpression();
491    if (Res.isInvalid) return Res;
492    // This can be followed by postfix-expr pieces (e.g. "foo"[1]).
493    return ParsePostfixExpressionSuffix(Res);
494  case tok::kw___builtin_va_arg:
495  case tok::kw___builtin_offsetof:
496  case tok::kw___builtin_choose_expr:
497  case tok::kw___builtin_overload:
498  case tok::kw___builtin_types_compatible_p:
499    return ParseBuiltinPrimaryExpression();
500  case tok::plusplus:      // unary-expression: '++' unary-expression
501  case tok::minusminus: {  // unary-expression: '--' unary-expression
502    SourceLocation SavedLoc = ConsumeToken();
503    Res = ParseCastExpression(true);
504    if (!Res.isInvalid)
505      Res = Actions.ActOnUnaryOp(SavedLoc, SavedKind, Res.Val);
506    return Res;
507  }
508  case tok::amp:           // unary-expression: '&' cast-expression
509  case tok::star:          // unary-expression: '*' cast-expression
510  case tok::plus:          // unary-expression: '+' cast-expression
511  case tok::minus:         // unary-expression: '-' cast-expression
512  case tok::tilde:         // unary-expression: '~' cast-expression
513  case tok::exclaim:       // unary-expression: '!' cast-expression
514  case tok::kw___real:     // unary-expression: '__real' cast-expression [GNU]
515  case tok::kw___imag: {   // unary-expression: '__imag' cast-expression [GNU]
516    SourceLocation SavedLoc = ConsumeToken();
517    Res = ParseCastExpression(false);
518    if (!Res.isInvalid)
519      Res = Actions.ActOnUnaryOp(SavedLoc, SavedKind, Res.Val);
520    return Res;
521  }
522
523  case tok::kw___extension__:{//unary-expression:'__extension__' cast-expr [GNU]
524    // __extension__ silences extension warnings in the subexpression.
525    ExtensionRAIIObject O(Diags);  // Use RAII to do this.
526    SourceLocation SavedLoc = ConsumeToken();
527    Res = ParseCastExpression(false);
528    if (!Res.isInvalid)
529      Res = Actions.ActOnUnaryOp(SavedLoc, SavedKind, Res.Val);
530    return Res;
531  }
532  case tok::kw_sizeof:     // unary-expression: 'sizeof' unary-expression
533                           // unary-expression: 'sizeof' '(' type-name ')'
534  case tok::kw_alignof:
535  case tok::kw___alignof:  // unary-expression: '__alignof' unary-expression
536                           // unary-expression: '__alignof' '(' type-name ')'
537                           // unary-expression: 'alignof' '(' type-id ')'
538    return ParseSizeofAlignofExpression();
539  case tok::ampamp: {      // unary-expression: '&&' identifier
540    SourceLocation AmpAmpLoc = ConsumeToken();
541    if (Tok.isNot(tok::identifier)) {
542      Diag(Tok, diag::err_expected_ident);
543      return ExprResult(true);
544    }
545
546    Diag(AmpAmpLoc, diag::ext_gnu_address_of_label);
547    Res = Actions.ActOnAddrLabel(AmpAmpLoc, Tok.getLocation(),
548                                 Tok.getIdentifierInfo());
549    ConsumeToken();
550    return Res;
551  }
552  case tok::kw_const_cast:
553  case tok::kw_dynamic_cast:
554  case tok::kw_reinterpret_cast:
555  case tok::kw_static_cast:
556    Res = ParseCXXCasts();
557    // These can be followed by postfix-expr pieces.
558    return ParsePostfixExpressionSuffix(Res);
559  case tok::kw_this:
560    Res = ParseCXXThis();
561    // This can be followed by postfix-expr pieces.
562    return ParsePostfixExpressionSuffix(Res);
563
564  case tok::kw_char:
565  case tok::kw_wchar_t:
566  case tok::kw_bool:
567  case tok::kw_short:
568  case tok::kw_int:
569  case tok::kw_long:
570  case tok::kw_signed:
571  case tok::kw_unsigned:
572  case tok::kw_float:
573  case tok::kw_double:
574  case tok::kw_void:
575  case tok::kw_typeof: {
576    if (!getLang().CPlusPlus)
577      goto UnhandledToken;
578  HandleType:
579    // postfix-expression: simple-type-specifier '(' expression-list[opt] ')'
580    //
581    DeclSpec DS;
582    ParseCXXSimpleTypeSpecifier(DS);
583    if (Tok.isNot(tok::l_paren))
584      return Diag(Tok.getLocation(), diag::err_expected_lparen_after_type,
585                  DS.getSourceRange());
586
587    Res = ParseCXXTypeConstructExpression(DS);
588    // This can be followed by postfix-expr pieces.
589    return ParsePostfixExpressionSuffix(Res);
590  }
591
592  case tok::at: {
593    SourceLocation AtLoc = ConsumeToken();
594    return ParseObjCAtExpression(AtLoc);
595  }
596  case tok::l_square:
597    // These can be followed by postfix-expr pieces.
598    if (getLang().ObjC1)
599      return ParsePostfixExpressionSuffix(ParseObjCMessageExpression());
600    // FALL THROUGH.
601  case tok::caret:
602    if (getLang().Blocks)
603      return ParsePostfixExpressionSuffix(ParseBlockLiteralExpression());
604    Diag(Tok, diag::err_expected_expression);
605    return ExprResult(true);
606  default:
607  UnhandledToken:
608    Diag(Tok, diag::err_expected_expression);
609    return ExprResult(true);
610  }
611
612  // unreachable.
613  abort();
614}
615
616/// ParsePostfixExpressionSuffix - Once the leading part of a postfix-expression
617/// is parsed, this method parses any suffixes that apply.
618///
619///       postfix-expression: [C99 6.5.2]
620///         primary-expression
621///         postfix-expression '[' expression ']'
622///         postfix-expression '(' argument-expression-list[opt] ')'
623///         postfix-expression '.' identifier
624///         postfix-expression '->' identifier
625///         postfix-expression '++'
626///         postfix-expression '--'
627///         '(' type-name ')' '{' initializer-list '}'
628///         '(' type-name ')' '{' initializer-list ',' '}'
629///
630///       argument-expression-list: [C99 6.5.2]
631///         argument-expression
632///         argument-expression-list ',' assignment-expression
633///
634Parser::ExprResult Parser::ParsePostfixExpressionSuffix(ExprResult LHS) {
635
636  // Now that the primary-expression piece of the postfix-expression has been
637  // parsed, see if there are any postfix-expression pieces here.
638  SourceLocation Loc;
639  while (1) {
640    switch (Tok.getKind()) {
641    default:  // Not a postfix-expression suffix.
642      return LHS;
643    case tok::l_square: {  // postfix-expression: p-e '[' expression ']'
644      Loc = ConsumeBracket();
645      ExprResult Idx = ParseExpression();
646
647      SourceLocation RLoc = Tok.getLocation();
648
649      if (!LHS.isInvalid && !Idx.isInvalid && Tok.is(tok::r_square))
650        LHS = Actions.ActOnArraySubscriptExpr(LHS.Val, Loc, Idx.Val, RLoc);
651      else
652        LHS = ExprResult(true);
653
654      // Match the ']'.
655      MatchRHSPunctuation(tok::r_square, Loc);
656      break;
657    }
658
659    case tok::l_paren: {   // p-e: p-e '(' argument-expression-list[opt] ')'
660      ExprListTy ArgExprs;
661      CommaLocsTy CommaLocs;
662
663      Loc = ConsumeParen();
664
665      if (Tok.isNot(tok::r_paren)) {
666        if (ParseExpressionList(ArgExprs, CommaLocs)) {
667          SkipUntil(tok::r_paren);
668          return ExprResult(true);
669        }
670      }
671
672      // Match the ')'.
673      if (!LHS.isInvalid && Tok.is(tok::r_paren)) {
674        assert((ArgExprs.size() == 0 || ArgExprs.size()-1 == CommaLocs.size())&&
675               "Unexpected number of commas!");
676        LHS = Actions.ActOnCallExpr(LHS.Val, Loc, &ArgExprs[0], ArgExprs.size(),
677                                    &CommaLocs[0], Tok.getLocation());
678      }
679
680      MatchRHSPunctuation(tok::r_paren, Loc);
681      break;
682    }
683    case tok::arrow:       // postfix-expression: p-e '->' identifier
684    case tok::period: {    // postfix-expression: p-e '.' identifier
685      tok::TokenKind OpKind = Tok.getKind();
686      SourceLocation OpLoc = ConsumeToken();  // Eat the "." or "->" token.
687
688      if (Tok.isNot(tok::identifier)) {
689        Diag(Tok, diag::err_expected_ident);
690        return ExprResult(true);
691      }
692
693      if (!LHS.isInvalid)
694        LHS = Actions.ActOnMemberReferenceExpr(LHS.Val, OpLoc, OpKind,
695                                               Tok.getLocation(),
696                                               *Tok.getIdentifierInfo());
697      ConsumeToken();
698      break;
699    }
700    case tok::plusplus:    // postfix-expression: postfix-expression '++'
701    case tok::minusminus:  // postfix-expression: postfix-expression '--'
702      if (!LHS.isInvalid)
703        LHS = Actions.ActOnPostfixUnaryOp(Tok.getLocation(), Tok.getKind(),
704                                          LHS.Val);
705      ConsumeToken();
706      break;
707    }
708  }
709}
710
711
712/// ParseSizeofAlignofExpression - Parse a sizeof or alignof expression.
713///       unary-expression:  [C99 6.5.3]
714///         'sizeof' unary-expression
715///         'sizeof' '(' type-name ')'
716/// [GNU]   '__alignof' unary-expression
717/// [GNU]   '__alignof' '(' type-name ')'
718/// [C++0x] 'alignof' '(' type-id ')'
719Parser::ExprResult Parser::ParseSizeofAlignofExpression() {
720  assert((Tok.is(tok::kw_sizeof) || Tok.is(tok::kw___alignof)
721          || Tok.is(tok::kw_alignof)) &&
722         "Not a sizeof/alignof expression!");
723  Token OpTok = Tok;
724  ConsumeToken();
725
726  // If the operand doesn't start with an '(', it must be an expression.
727  ExprResult Operand;
728  if (Tok.isNot(tok::l_paren)) {
729    Operand = ParseCastExpression(true);
730  } else {
731    // If it starts with a '(', we know that it is either a parenthesized
732    // type-name, or it is a unary-expression that starts with a compound
733    // literal, or starts with a primary-expression that is a parenthesized
734    // expression.
735    ParenParseOption ExprType = CastExpr;
736    TypeTy *CastTy;
737    SourceLocation LParenLoc = Tok.getLocation(), RParenLoc;
738    Operand = ParseParenExpression(ExprType, CastTy, RParenLoc);
739
740    // If ParseParenExpression parsed a '(typename)' sequence only, the this is
741    // sizeof/alignof a type.  Otherwise, it is sizeof/alignof an expression.
742    if (ExprType == CastExpr)
743      return Actions.ActOnSizeOfAlignOfTypeExpr(OpTok.getLocation(),
744                                                OpTok.is(tok::kw_sizeof),
745                                                LParenLoc, CastTy, RParenLoc);
746
747    // If this is a parenthesized expression, it is the start of a
748    // unary-expression, but doesn't include any postfix pieces.  Parse these
749    // now if present.
750    Operand = ParsePostfixExpressionSuffix(Operand);
751  }
752
753  // If we get here, the operand to the sizeof/alignof was an expresion.
754  if (!Operand.isInvalid)
755    Operand = Actions.ActOnUnaryOp(OpTok.getLocation(), OpTok.getKind(),
756                                   Operand.Val);
757  return Operand;
758}
759
760/// ParseBuiltinPrimaryExpression
761///
762///       primary-expression: [C99 6.5.1]
763/// [GNU]   '__builtin_va_arg' '(' assignment-expression ',' type-name ')'
764/// [GNU]   '__builtin_offsetof' '(' type-name ',' offsetof-member-designator')'
765/// [GNU]   '__builtin_choose_expr' '(' assign-expr ',' assign-expr ','
766///                                     assign-expr ')'
767/// [GNU]   '__builtin_types_compatible_p' '(' type-name ',' type-name ')'
768/// [CLANG] '__builtin_overload' '(' expr (',' expr)* ')'
769///
770/// [GNU] offsetof-member-designator:
771/// [GNU]   identifier
772/// [GNU]   offsetof-member-designator '.' identifier
773/// [GNU]   offsetof-member-designator '[' expression ']'
774///
775Parser::ExprResult Parser::ParseBuiltinPrimaryExpression() {
776  ExprResult Res(false);
777  const IdentifierInfo *BuiltinII = Tok.getIdentifierInfo();
778
779  tok::TokenKind T = Tok.getKind();
780  SourceLocation StartLoc = ConsumeToken();   // Eat the builtin identifier.
781
782  // All of these start with an open paren.
783  if (Tok.isNot(tok::l_paren)) {
784    Diag(Tok, diag::err_expected_lparen_after, BuiltinII->getName());
785    return ExprResult(true);
786  }
787
788  SourceLocation LParenLoc = ConsumeParen();
789  // TODO: Build AST.
790
791  switch (T) {
792  default: assert(0 && "Not a builtin primary expression!");
793  case tok::kw___builtin_va_arg: {
794    ExprResult Expr = ParseAssignmentExpression();
795    if (Expr.isInvalid) {
796      SkipUntil(tok::r_paren);
797      return ExprResult(true);
798    }
799
800    if (ExpectAndConsume(tok::comma, diag::err_expected_comma, "",tok::r_paren))
801      return ExprResult(true);
802
803    TypeTy *Ty = ParseTypeName();
804
805    if (Tok.isNot(tok::r_paren)) {
806      Diag(Tok, diag::err_expected_rparen);
807      return ExprResult(true);
808    }
809    Res = Actions.ActOnVAArg(StartLoc, Expr.Val, Ty, ConsumeParen());
810    break;
811  }
812  case tok::kw___builtin_offsetof: {
813    SourceLocation TypeLoc = Tok.getLocation();
814    TypeTy *Ty = ParseTypeName();
815
816    if (ExpectAndConsume(tok::comma, diag::err_expected_comma, "",tok::r_paren))
817      return ExprResult(true);
818
819    // We must have at least one identifier here.
820    if (Tok.isNot(tok::identifier)) {
821      Diag(Tok, diag::err_expected_ident);
822      SkipUntil(tok::r_paren);
823      return true;
824    }
825
826    // Keep track of the various subcomponents we see.
827    llvm::SmallVector<Action::OffsetOfComponent, 4> Comps;
828
829    Comps.push_back(Action::OffsetOfComponent());
830    Comps.back().isBrackets = false;
831    Comps.back().U.IdentInfo = Tok.getIdentifierInfo();
832    Comps.back().LocStart = Comps.back().LocEnd = ConsumeToken();
833
834    while (1) {
835      if (Tok.is(tok::period)) {
836        // offsetof-member-designator: offsetof-member-designator '.' identifier
837        Comps.push_back(Action::OffsetOfComponent());
838        Comps.back().isBrackets = false;
839        Comps.back().LocStart = ConsumeToken();
840
841        if (Tok.isNot(tok::identifier)) {
842          Diag(Tok, diag::err_expected_ident);
843          SkipUntil(tok::r_paren);
844          return true;
845        }
846        Comps.back().U.IdentInfo = Tok.getIdentifierInfo();
847        Comps.back().LocEnd = ConsumeToken();
848
849      } else if (Tok.is(tok::l_square)) {
850        // offsetof-member-designator: offsetof-member-design '[' expression ']'
851        Comps.push_back(Action::OffsetOfComponent());
852        Comps.back().isBrackets = true;
853        Comps.back().LocStart = ConsumeBracket();
854        Res = ParseExpression();
855        if (Res.isInvalid) {
856          SkipUntil(tok::r_paren);
857          return Res;
858        }
859        Comps.back().U.E = Res.Val;
860
861        Comps.back().LocEnd =
862          MatchRHSPunctuation(tok::r_square, Comps.back().LocStart);
863      } else if (Tok.is(tok::r_paren)) {
864        Res = Actions.ActOnBuiltinOffsetOf(StartLoc, TypeLoc, Ty, &Comps[0],
865                                           Comps.size(), ConsumeParen());
866        break;
867      } else {
868        // Error occurred.
869        return ExprResult(true);
870      }
871    }
872    break;
873  }
874  case tok::kw___builtin_choose_expr: {
875    ExprResult Cond = ParseAssignmentExpression();
876    if (Cond.isInvalid) {
877      SkipUntil(tok::r_paren);
878      return Cond;
879    }
880    if (ExpectAndConsume(tok::comma, diag::err_expected_comma, "",tok::r_paren))
881      return ExprResult(true);
882
883    ExprResult Expr1 = ParseAssignmentExpression();
884    if (Expr1.isInvalid) {
885      SkipUntil(tok::r_paren);
886      return Expr1;
887    }
888    if (ExpectAndConsume(tok::comma, diag::err_expected_comma, "",tok::r_paren))
889      return ExprResult(true);
890
891    ExprResult Expr2 = ParseAssignmentExpression();
892    if (Expr2.isInvalid) {
893      SkipUntil(tok::r_paren);
894      return Expr2;
895    }
896    if (Tok.isNot(tok::r_paren)) {
897      Diag(Tok, diag::err_expected_rparen);
898      return ExprResult(true);
899    }
900    Res = Actions.ActOnChooseExpr(StartLoc, Cond.Val, Expr1.Val, Expr2.Val,
901                                  ConsumeParen());
902    break;
903  }
904  case tok::kw___builtin_overload: {
905    llvm::SmallVector<ExprTy*, 8> ArgExprs;
906    llvm::SmallVector<SourceLocation, 8> CommaLocs;
907
908    // For each iteration through the loop look for assign-expr followed by a
909    // comma.  If there is no comma, break and attempt to match r-paren.
910    if (Tok.isNot(tok::r_paren)) {
911      while (1) {
912        ExprResult ArgExpr = ParseAssignmentExpression();
913        if (ArgExpr.isInvalid) {
914          SkipUntil(tok::r_paren);
915          return ExprResult(true);
916        } else
917          ArgExprs.push_back(ArgExpr.Val);
918
919        if (Tok.isNot(tok::comma))
920          break;
921        // Move to the next argument, remember where the comma was.
922        CommaLocs.push_back(ConsumeToken());
923      }
924    }
925
926    // Attempt to consume the r-paren
927    if (Tok.isNot(tok::r_paren)) {
928      Diag(Tok, diag::err_expected_rparen);
929      SkipUntil(tok::r_paren);
930      return ExprResult(true);
931    }
932    Res = Actions.ActOnOverloadExpr(&ArgExprs[0], ArgExprs.size(),
933                                    &CommaLocs[0], StartLoc, ConsumeParen());
934    break;
935  }
936  case tok::kw___builtin_types_compatible_p:
937    TypeTy *Ty1 = ParseTypeName();
938
939    if (ExpectAndConsume(tok::comma, diag::err_expected_comma, "",tok::r_paren))
940      return ExprResult(true);
941
942    TypeTy *Ty2 = ParseTypeName();
943
944    if (Tok.isNot(tok::r_paren)) {
945      Diag(Tok, diag::err_expected_rparen);
946      return ExprResult(true);
947    }
948    Res = Actions.ActOnTypesCompatibleExpr(StartLoc, Ty1, Ty2, ConsumeParen());
949    break;
950  }
951
952  // These can be followed by postfix-expr pieces because they are
953  // primary-expressions.
954  return ParsePostfixExpressionSuffix(Res);
955}
956
957/// ParseParenExpression - This parses the unit that starts with a '(' token,
958/// based on what is allowed by ExprType.  The actual thing parsed is returned
959/// in ExprType.
960///
961///       primary-expression: [C99 6.5.1]
962///         '(' expression ')'
963/// [GNU]   '(' compound-statement ')'      (if !ParenExprOnly)
964///       postfix-expression: [C99 6.5.2]
965///         '(' type-name ')' '{' initializer-list '}'
966///         '(' type-name ')' '{' initializer-list ',' '}'
967///       cast-expression: [C99 6.5.4]
968///         '(' type-name ')' cast-expression
969///
970Parser::ExprResult Parser::ParseParenExpression(ParenParseOption &ExprType,
971                                                TypeTy *&CastTy,
972                                                SourceLocation &RParenLoc) {
973  assert(Tok.is(tok::l_paren) && "Not a paren expr!");
974  SourceLocation OpenLoc = ConsumeParen();
975  ExprResult Result(true);
976  CastTy = 0;
977
978  if (ExprType >= CompoundStmt && Tok.is(tok::l_brace)) {
979    Diag(Tok, diag::ext_gnu_statement_expr);
980    Parser::StmtResult Stmt = ParseCompoundStatement(true);
981    ExprType = CompoundStmt;
982
983    // If the substmt parsed correctly, build the AST node.
984    if (!Stmt.isInvalid && Tok.is(tok::r_paren))
985      Result = Actions.ActOnStmtExpr(OpenLoc, Stmt.Val, Tok.getLocation());
986
987  } else if (ExprType >= CompoundLiteral && isTypeIdInParens()) {
988    // Otherwise, this is a compound literal expression or cast expression.
989    TypeTy *Ty = ParseTypeName();
990
991    // Match the ')'.
992    if (Tok.is(tok::r_paren))
993      RParenLoc = ConsumeParen();
994    else
995      MatchRHSPunctuation(tok::r_paren, OpenLoc);
996
997    if (Tok.is(tok::l_brace)) {
998      if (!getLang().C99)   // Compound literals don't exist in C90.
999        Diag(OpenLoc, diag::ext_c99_compound_literal);
1000      Result = ParseInitializer();
1001      ExprType = CompoundLiteral;
1002      if (!Result.isInvalid)
1003        return Actions.ActOnCompoundLiteral(OpenLoc, Ty, RParenLoc, Result.Val);
1004    } else if (ExprType == CastExpr) {
1005      // Note that this doesn't parse the subsequence cast-expression, it just
1006      // returns the parsed type to the callee.
1007      ExprType = CastExpr;
1008      CastTy = Ty;
1009      return ExprResult(false);
1010    } else {
1011      Diag(Tok, diag::err_expected_lbrace_in_compound_literal);
1012      return ExprResult(true);
1013    }
1014    return Result;
1015  } else {
1016    Result = ParseExpression();
1017    ExprType = SimpleExpr;
1018    if (!Result.isInvalid && Tok.is(tok::r_paren))
1019      Result = Actions.ActOnParenExpr(OpenLoc, Tok.getLocation(), Result.Val);
1020  }
1021
1022  // Match the ')'.
1023  if (Result.isInvalid)
1024    SkipUntil(tok::r_paren);
1025  else {
1026    if (Tok.is(tok::r_paren))
1027      RParenLoc = ConsumeParen();
1028    else
1029      MatchRHSPunctuation(tok::r_paren, OpenLoc);
1030  }
1031
1032  return Result;
1033}
1034
1035/// ParseStringLiteralExpression - This handles the various token types that
1036/// form string literals, and also handles string concatenation [C99 5.1.1.2,
1037/// translation phase #6].
1038///
1039///       primary-expression: [C99 6.5.1]
1040///         string-literal
1041Parser::ExprResult Parser::ParseStringLiteralExpression() {
1042  assert(isTokenStringLiteral() && "Not a string literal!");
1043
1044  // String concat.  Note that keywords like __func__ and __FUNCTION__ are not
1045  // considered to be strings for concatenation purposes.
1046  llvm::SmallVector<Token, 4> StringToks;
1047
1048  do {
1049    StringToks.push_back(Tok);
1050    ConsumeStringToken();
1051  } while (isTokenStringLiteral());
1052
1053  // Pass the set of string tokens, ready for concatenation, to the actions.
1054  return Actions.ActOnStringLiteral(&StringToks[0], StringToks.size());
1055}
1056
1057/// ParseExpressionList - Used for C/C++ (argument-)expression-list.
1058///
1059///       argument-expression-list:
1060///         assignment-expression
1061///         argument-expression-list , assignment-expression
1062///
1063/// [C++] expression-list:
1064/// [C++]   assignment-expression
1065/// [C++]   expression-list , assignment-expression
1066///
1067bool Parser::ParseExpressionList(ExprListTy &Exprs, CommaLocsTy &CommaLocs) {
1068  while (1) {
1069    ExprResult Expr = ParseAssignmentExpression();
1070    if (Expr.isInvalid)
1071      return true;
1072
1073    Exprs.push_back(Expr.Val);
1074
1075    if (Tok.isNot(tok::comma))
1076      return false;
1077    // Move to the next argument, remember where the comma was.
1078    CommaLocs.push_back(ConsumeToken());
1079  }
1080}
1081
1082/// ParseBlockLiteralExpression - Parse a block literal, which roughly looks
1083/// like ^(int x){ return x+1; }
1084///
1085///         block-literal:
1086/// [clang]   '^' block-args[opt] compound-statement
1087/// [clang] block-args:
1088/// [clang]   '(' parameter-list ')'
1089///
1090Parser::ExprResult Parser::ParseBlockLiteralExpression() {
1091  assert(Tok.is(tok::caret) && "block literal starts with ^");
1092  SourceLocation CaretLoc = ConsumeToken();
1093
1094  // Enter a scope to hold everything within the block.  This includes the
1095  // argument decls, decls within the compound expression, etc.  This also
1096  // allows determining whether a variable reference inside the block is
1097  // within or outside of the block.
1098  EnterScope(Scope::BlockScope|Scope::FnScope|Scope::BreakScope|
1099             Scope::ContinueScope|Scope::DeclScope);
1100
1101  // Inform sema that we are starting a block.
1102  Actions.ActOnBlockStart(CaretLoc, CurScope);
1103
1104  // Parse the return type if present.
1105  DeclSpec DS;
1106  Declarator ParamInfo(DS, Declarator::PrototypeContext);
1107
1108  // If this block has arguments, parse them.  There is no ambiguity here with
1109  // the expression case, because the expression case requires a parameter list.
1110  if (Tok.is(tok::l_paren)) {
1111    ParseParenDeclarator(ParamInfo);
1112    // Parse the pieces after the identifier as if we had "int(...)".
1113    ParamInfo.SetIdentifier(0, CaretLoc);
1114    if (ParamInfo.getInvalidType()) {
1115      // If there was an error parsing the arguments, they may have tried to use
1116      // ^(x+y) which requires an argument list.  Just skip the whole block
1117      // literal.
1118      ExitScope();
1119      return true;
1120    }
1121  } else {
1122    // Otherwise, pretend we saw (void).
1123    ParamInfo.AddTypeInfo(DeclaratorChunk::getFunction(true, false,
1124                                                       0, 0, 0, CaretLoc));
1125  }
1126
1127  // Inform sema that we are starting a block.
1128  Actions.ActOnBlockArguments(ParamInfo);
1129
1130  ExprResult Result = true;
1131  if (Tok.is(tok::l_brace)) {
1132    StmtResult Stmt = ParseCompoundStatementBody();
1133    if (!Stmt.isInvalid) {
1134      Result = Actions.ActOnBlockStmtExpr(CaretLoc, Stmt.Val, CurScope);
1135    } else {
1136      Actions.ActOnBlockError(CaretLoc, CurScope);
1137    }
1138  }
1139  ExitScope();
1140  return Result;
1141}
1142
1143