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