Expr.cpp revision 190d6a25393995b42e32086949a68285ee423fb9 
1//===--- Expr.cpp - Expression AST Node Implementation --------------------===//
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 Expr class and subclasses.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/AST/Expr.h"
15#include "clang/AST/APValue.h"
16#include "clang/AST/ASTContext.h"
17#include "clang/AST/DeclObjC.h"
18#include "clang/AST/DeclCXX.h"
19#include "clang/AST/RecordLayout.h"
20#include "clang/AST/StmtVisitor.h"
21#include "clang/Basic/TargetInfo.h"
22using namespace clang;
23
24//===----------------------------------------------------------------------===//
25// Primary Expressions.
26//===----------------------------------------------------------------------===//
27
28/// getValueAsApproximateDouble - This returns the value as an inaccurate
29/// double.  Note that this may cause loss of precision, but is useful for
30/// debugging dumps, etc.
31double FloatingLiteral::getValueAsApproximateDouble() const {
32  llvm::APFloat V = getValue();
33  bool ignored;
34  V.convert(llvm::APFloat::IEEEdouble, llvm::APFloat::rmNearestTiesToEven,
35            &ignored);
36  return V.convertToDouble();
37}
38
39
40StringLiteral::StringLiteral(const char *strData, unsigned byteLength,
41                             bool Wide, QualType t, SourceLocation firstLoc,
42                             SourceLocation lastLoc) :
43  Expr(StringLiteralClass, t) {
44  // OPTIMIZE: could allocate this appended to the StringLiteral.
45  char *AStrData = new char[byteLength];
46  memcpy(AStrData, strData, byteLength);
47  StrData = AStrData;
48  ByteLength = byteLength;
49  IsWide = Wide;
50  firstTokLoc = firstLoc;
51  lastTokLoc = lastLoc;
52}
53
54StringLiteral::~StringLiteral() {
55  delete[] StrData;
56}
57
58bool UnaryOperator::isPostfix(Opcode Op) {
59  switch (Op) {
60  case PostInc:
61  case PostDec:
62    return true;
63  default:
64    return false;
65  }
66}
67
68bool UnaryOperator::isPrefix(Opcode Op) {
69  switch (Op) {
70    case PreInc:
71    case PreDec:
72      return true;
73    default:
74      return false;
75  }
76}
77
78/// getOpcodeStr - Turn an Opcode enum value into the punctuation char it
79/// corresponds to, e.g. "sizeof" or "[pre]++".
80const char *UnaryOperator::getOpcodeStr(Opcode Op) {
81  switch (Op) {
82  default: assert(0 && "Unknown unary operator");
83  case PostInc: return "++";
84  case PostDec: return "--";
85  case PreInc:  return "++";
86  case PreDec:  return "--";
87  case AddrOf:  return "&";
88  case Deref:   return "*";
89  case Plus:    return "+";
90  case Minus:   return "-";
91  case Not:     return "~";
92  case LNot:    return "!";
93  case Real:    return "__real";
94  case Imag:    return "__imag";
95  case Extension: return "__extension__";
96  case OffsetOf: return "__builtin_offsetof";
97  }
98}
99
100//===----------------------------------------------------------------------===//
101// Postfix Operators.
102//===----------------------------------------------------------------------===//
103
104CallExpr::CallExpr(StmtClass SC, Expr *fn, Expr **args, unsigned numargs,
105                   QualType t, SourceLocation rparenloc)
106  : Expr(SC, t,
107         fn->isTypeDependent() || hasAnyTypeDependentArguments(args, numargs),
108         fn->isValueDependent() || hasAnyValueDependentArguments(args, numargs)),
109    NumArgs(numargs) {
110  SubExprs = new Stmt*[numargs+1];
111  SubExprs[FN] = fn;
112  for (unsigned i = 0; i != numargs; ++i)
113    SubExprs[i+ARGS_START] = args[i];
114  RParenLoc = rparenloc;
115}
116
117CallExpr::CallExpr(Expr *fn, Expr **args, unsigned numargs, QualType t,
118                   SourceLocation rparenloc)
119  : Expr(CallExprClass, t,
120         fn->isTypeDependent() || hasAnyTypeDependentArguments(args, numargs),
121         fn->isValueDependent() || hasAnyValueDependentArguments(args, numargs)),
122    NumArgs(numargs) {
123  SubExprs = new Stmt*[numargs+1];
124  SubExprs[FN] = fn;
125  for (unsigned i = 0; i != numargs; ++i)
126    SubExprs[i+ARGS_START] = args[i];
127  RParenLoc = rparenloc;
128}
129
130/// setNumArgs - This changes the number of arguments present in this call.
131/// Any orphaned expressions are deleted by this, and any new operands are set
132/// to null.
133void CallExpr::setNumArgs(unsigned NumArgs) {
134  // No change, just return.
135  if (NumArgs == getNumArgs()) return;
136
137  // If shrinking # arguments, just delete the extras and forgot them.
138  if (NumArgs < getNumArgs()) {
139    for (unsigned i = NumArgs, e = getNumArgs(); i != e; ++i)
140      delete getArg(i);
141    this->NumArgs = NumArgs;
142    return;
143  }
144
145  // Otherwise, we are growing the # arguments.  New an bigger argument array.
146  Stmt **NewSubExprs = new Stmt*[NumArgs+1];
147  // Copy over args.
148  for (unsigned i = 0; i != getNumArgs()+ARGS_START; ++i)
149    NewSubExprs[i] = SubExprs[i];
150  // Null out new args.
151  for (unsigned i = getNumArgs()+ARGS_START; i != NumArgs+ARGS_START; ++i)
152    NewSubExprs[i] = 0;
153
154  delete[] SubExprs;
155  SubExprs = NewSubExprs;
156  this->NumArgs = NumArgs;
157}
158
159/// isBuiltinCall - If this is a call to a builtin, return the builtin ID.  If
160/// not, return 0.
161unsigned CallExpr::isBuiltinCall() const {
162  // All simple function calls (e.g. func()) are implicitly cast to pointer to
163  // function. As a result, we try and obtain the DeclRefExpr from the
164  // ImplicitCastExpr.
165  const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(getCallee());
166  if (!ICE) // FIXME: deal with more complex calls (e.g. (func)(), (*func)()).
167    return 0;
168
169  const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ICE->getSubExpr());
170  if (!DRE)
171    return 0;
172
173  const FunctionDecl *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl());
174  if (!FDecl)
175    return 0;
176
177  if (!FDecl->getIdentifier())
178    return 0;
179
180  return FDecl->getIdentifier()->getBuiltinID();
181}
182
183
184/// getOpcodeStr - Turn an Opcode enum value into the punctuation char it
185/// corresponds to, e.g. "<<=".
186const char *BinaryOperator::getOpcodeStr(Opcode Op) {
187  switch (Op) {
188  default: assert(0 && "Unknown binary operator");
189  case Mul:       return "*";
190  case Div:       return "/";
191  case Rem:       return "%";
192  case Add:       return "+";
193  case Sub:       return "-";
194  case Shl:       return "<<";
195  case Shr:       return ">>";
196  case LT:        return "<";
197  case GT:        return ">";
198  case LE:        return "<=";
199  case GE:        return ">=";
200  case EQ:        return "==";
201  case NE:        return "!=";
202  case And:       return "&";
203  case Xor:       return "^";
204  case Or:        return "|";
205  case LAnd:      return "&&";
206  case LOr:       return "||";
207  case Assign:    return "=";
208  case MulAssign: return "*=";
209  case DivAssign: return "/=";
210  case RemAssign: return "%=";
211  case AddAssign: return "+=";
212  case SubAssign: return "-=";
213  case ShlAssign: return "<<=";
214  case ShrAssign: return ">>=";
215  case AndAssign: return "&=";
216  case XorAssign: return "^=";
217  case OrAssign:  return "|=";
218  case Comma:     return ",";
219  }
220}
221
222InitListExpr::InitListExpr(SourceLocation lbraceloc,
223                           Expr **initExprs, unsigned numInits,
224                           SourceLocation rbraceloc, bool hadDesignators)
225  : Expr(InitListExprClass, QualType()),
226    LBraceLoc(lbraceloc), RBraceLoc(rbraceloc), HadDesignators(hadDesignators) {
227
228  InitExprs.insert(InitExprs.end(), initExprs, initExprs+numInits);
229}
230
231/// getFunctionType - Return the underlying function type for this block.
232///
233const FunctionType *BlockExpr::getFunctionType() const {
234  return getType()->getAsBlockPointerType()->
235                    getPointeeType()->getAsFunctionType();
236}
237
238SourceLocation BlockExpr::getCaretLocation() const {
239  return TheBlock->getCaretLocation();
240}
241const Stmt *BlockExpr::getBody() const { return TheBlock->getBody(); }
242Stmt *BlockExpr::getBody() { return TheBlock->getBody(); }
243
244
245//===----------------------------------------------------------------------===//
246// Generic Expression Routines
247//===----------------------------------------------------------------------===//
248
249/// hasLocalSideEffect - Return true if this immediate expression has side
250/// effects, not counting any sub-expressions.
251bool Expr::hasLocalSideEffect() const {
252  switch (getStmtClass()) {
253  default:
254    return false;
255  case ParenExprClass:
256    return cast<ParenExpr>(this)->getSubExpr()->hasLocalSideEffect();
257  case UnaryOperatorClass: {
258    const UnaryOperator *UO = cast<UnaryOperator>(this);
259
260    switch (UO->getOpcode()) {
261    default: return false;
262    case UnaryOperator::PostInc:
263    case UnaryOperator::PostDec:
264    case UnaryOperator::PreInc:
265    case UnaryOperator::PreDec:
266      return true;                     // ++/--
267
268    case UnaryOperator::Deref:
269      // Dereferencing a volatile pointer is a side-effect.
270      return getType().isVolatileQualified();
271    case UnaryOperator::Real:
272    case UnaryOperator::Imag:
273      // accessing a piece of a volatile complex is a side-effect.
274      return UO->getSubExpr()->getType().isVolatileQualified();
275
276    case UnaryOperator::Extension:
277      return UO->getSubExpr()->hasLocalSideEffect();
278    }
279  }
280  case BinaryOperatorClass: {
281    const BinaryOperator *BinOp = cast<BinaryOperator>(this);
282    // Consider comma to have side effects if the LHS and RHS both do.
283    if (BinOp->getOpcode() == BinaryOperator::Comma)
284      return BinOp->getLHS()->hasLocalSideEffect() &&
285             BinOp->getRHS()->hasLocalSideEffect();
286
287    return BinOp->isAssignmentOp();
288  }
289  case CompoundAssignOperatorClass:
290    return true;
291
292  case ConditionalOperatorClass: {
293    const ConditionalOperator *Exp = cast<ConditionalOperator>(this);
294    return Exp->getCond()->hasLocalSideEffect()
295           || (Exp->getLHS() && Exp->getLHS()->hasLocalSideEffect())
296           || (Exp->getRHS() && Exp->getRHS()->hasLocalSideEffect());
297  }
298
299  case MemberExprClass:
300  case ArraySubscriptExprClass:
301    // If the base pointer or element is to a volatile pointer/field, accessing
302    // if is a side effect.
303    return getType().isVolatileQualified();
304
305  case CallExprClass:
306  case CXXOperatorCallExprClass:
307    // TODO: check attributes for pure/const.   "void foo() { strlen("bar"); }"
308    // should warn.
309    return true;
310  case ObjCMessageExprClass:
311    return true;
312  case StmtExprClass: {
313    // Statement exprs don't logically have side effects themselves, but are
314    // sometimes used in macros in ways that give them a type that is unused.
315    // For example ({ blah; foo(); }) will end up with a type if foo has a type.
316    // however, if the result of the stmt expr is dead, we don't want to emit a
317    // warning.
318    const CompoundStmt *CS = cast<StmtExpr>(this)->getSubStmt();
319    if (!CS->body_empty())
320      if (const Expr *E = dyn_cast<Expr>(CS->body_back()))
321        return E->hasLocalSideEffect();
322    return false;
323  }
324  case CStyleCastExprClass:
325  case CXXFunctionalCastExprClass:
326    // If this is a cast to void, check the operand.  Otherwise, the result of
327    // the cast is unused.
328    if (getType()->isVoidType())
329      return cast<CastExpr>(this)->getSubExpr()->hasLocalSideEffect();
330    return false;
331
332  case ImplicitCastExprClass:
333    // Check the operand, since implicit casts are inserted by Sema
334    return cast<ImplicitCastExpr>(this)->getSubExpr()->hasLocalSideEffect();
335
336  case CXXDefaultArgExprClass:
337    return cast<CXXDefaultArgExpr>(this)->getExpr()->hasLocalSideEffect();
338
339  case CXXNewExprClass:
340    // FIXME: In theory, there might be new expressions that don't have side
341    // effects (e.g. a placement new with an uninitialized POD).
342  case CXXDeleteExprClass:
343    return true;
344  }
345}
346
347/// DeclCanBeLvalue - Determine whether the given declaration can be
348/// an lvalue. This is a helper routine for isLvalue.
349static bool DeclCanBeLvalue(const NamedDecl *Decl, ASTContext &Ctx) {
350  // C++ [temp.param]p6:
351  //   A non-type non-reference template-parameter is not an lvalue.
352  if (const NonTypeTemplateParmDecl *NTTParm
353        = dyn_cast<NonTypeTemplateParmDecl>(Decl))
354    return NTTParm->getType()->isReferenceType();
355
356  return isa<VarDecl>(Decl) || isa<FieldDecl>(Decl) ||
357    // C++ 3.10p2: An lvalue refers to an object or function.
358    (Ctx.getLangOptions().CPlusPlus &&
359     (isa<FunctionDecl>(Decl) || isa<OverloadedFunctionDecl>(Decl)));
360}
361
362/// isLvalue - C99 6.3.2.1: an lvalue is an expression with an object type or an
363/// incomplete type other than void. Nonarray expressions that can be lvalues:
364///  - name, where name must be a variable
365///  - e[i]
366///  - (e), where e must be an lvalue
367///  - e.name, where e must be an lvalue
368///  - e->name
369///  - *e, the type of e cannot be a function type
370///  - string-constant
371///  - (__real__ e) and (__imag__ e) where e is an lvalue  [GNU extension]
372///  - reference type [C++ [expr]]
373///
374Expr::isLvalueResult Expr::isLvalue(ASTContext &Ctx) const {
375  // first, check the type (C99 6.3.2.1). Expressions with function
376  // type in C are not lvalues, but they can be lvalues in C++.
377  if (!Ctx.getLangOptions().CPlusPlus && TR->isFunctionType())
378    return LV_NotObjectType;
379
380  // Allow qualified void which is an incomplete type other than void (yuck).
381  if (TR->isVoidType() && !Ctx.getCanonicalType(TR).getCVRQualifiers())
382    return LV_IncompleteVoidType;
383
384  /// FIXME: Expressions can't have reference type, so the following
385  /// isn't needed.
386  if (TR->isReferenceType()) // C++ [expr]
387    return LV_Valid;
388
389  // the type looks fine, now check the expression
390  switch (getStmtClass()) {
391  case StringLiteralClass: // C99 6.5.1p4
392    return LV_Valid;
393  case ArraySubscriptExprClass: // C99 6.5.3p4 (e1[e2] == (*((e1)+(e2))))
394    // For vectors, make sure base is an lvalue (i.e. not a function call).
395    if (cast<ArraySubscriptExpr>(this)->getBase()->getType()->isVectorType())
396      return cast<ArraySubscriptExpr>(this)->getBase()->isLvalue(Ctx);
397    return LV_Valid;
398  case DeclRefExprClass:
399  case QualifiedDeclRefExprClass: { // C99 6.5.1p2
400    const NamedDecl *RefdDecl = cast<DeclRefExpr>(this)->getDecl();
401    if (DeclCanBeLvalue(RefdDecl, Ctx))
402      return LV_Valid;
403    break;
404  }
405  case BlockDeclRefExprClass: {
406    const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(this);
407    if (isa<VarDecl>(BDR->getDecl()))
408      return LV_Valid;
409    break;
410  }
411  case MemberExprClass: {
412    const MemberExpr *m = cast<MemberExpr>(this);
413    if (Ctx.getLangOptions().CPlusPlus) { // C++ [expr.ref]p4:
414      NamedDecl *Member = m->getMemberDecl();
415      // C++ [expr.ref]p4:
416      //   If E2 is declared to have type "reference to T", then E1.E2
417      //   is an lvalue.
418      if (ValueDecl *Value = dyn_cast<ValueDecl>(Member))
419        if (Value->getType()->isReferenceType())
420          return LV_Valid;
421
422      //   -- If E2 is a static data member [...] then E1.E2 is an lvalue.
423      if (isa<CXXClassVarDecl>(Member))
424        return LV_Valid;
425
426      //   -- If E2 is a non-static data member [...]. If E1 is an
427      //      lvalue, then E1.E2 is an lvalue.
428      if (isa<FieldDecl>(Member))
429        return m->isArrow() ? LV_Valid : m->getBase()->isLvalue(Ctx);
430
431      //   -- If it refers to a static member function [...], then
432      //      E1.E2 is an lvalue.
433      //   -- Otherwise, if E1.E2 refers to a non-static member
434      //      function [...], then E1.E2 is not an lvalue.
435      if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Member))
436        return Method->isStatic()? LV_Valid : LV_MemberFunction;
437
438      //   -- If E2 is a member enumerator [...], the expression E1.E2
439      //      is not an lvalue.
440      if (isa<EnumConstantDecl>(Member))
441        return LV_InvalidExpression;
442
443        // Not an lvalue.
444      return LV_InvalidExpression;
445    }
446
447    // C99 6.5.2.3p4
448    return m->isArrow() ? LV_Valid : m->getBase()->isLvalue(Ctx);
449  }
450  case UnaryOperatorClass:
451    if (cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::Deref)
452      return LV_Valid; // C99 6.5.3p4
453
454    if (cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::Real ||
455        cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::Imag ||
456        cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::Extension)
457      return cast<UnaryOperator>(this)->getSubExpr()->isLvalue(Ctx);  // GNU.
458
459    if (Ctx.getLangOptions().CPlusPlus && // C++ [expr.pre.incr]p1
460        (cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::PreInc ||
461         cast<UnaryOperator>(this)->getOpcode() == UnaryOperator::PreDec))
462      return LV_Valid;
463    break;
464  case ImplicitCastExprClass:
465    return cast<ImplicitCastExpr>(this)->isLvalueCast()? LV_Valid
466                                                       : LV_InvalidExpression;
467  case ParenExprClass: // C99 6.5.1p5
468    return cast<ParenExpr>(this)->getSubExpr()->isLvalue(Ctx);
469  case BinaryOperatorClass:
470  case CompoundAssignOperatorClass: {
471    const BinaryOperator *BinOp = cast<BinaryOperator>(this);
472
473    if (Ctx.getLangOptions().CPlusPlus && // C++ [expr.comma]p1
474        BinOp->getOpcode() == BinaryOperator::Comma)
475      return BinOp->getRHS()->isLvalue(Ctx);
476
477    if (!BinOp->isAssignmentOp())
478      return LV_InvalidExpression;
479
480    if (Ctx.getLangOptions().CPlusPlus)
481      // C++ [expr.ass]p1:
482      //   The result of an assignment operation [...] is an lvalue.
483      return LV_Valid;
484
485
486    // C99 6.5.16:
487    //   An assignment expression [...] is not an lvalue.
488    return LV_InvalidExpression;
489  }
490  case CallExprClass:
491  case CXXOperatorCallExprClass:
492  case CXXMemberCallExprClass: {
493    // C++ [expr.call]p10:
494    //   A function call is an lvalue if and only if the result type
495    //   is a reference.
496    QualType CalleeType = cast<CallExpr>(this)->getCallee()->getType();
497    if (const PointerType *FnTypePtr = CalleeType->getAsPointerType())
498      CalleeType = FnTypePtr->getPointeeType();
499    if (const FunctionType *FnType = CalleeType->getAsFunctionType())
500      if (FnType->getResultType()->isReferenceType())
501        return LV_Valid;
502
503    break;
504  }
505  case CompoundLiteralExprClass: // C99 6.5.2.5p5
506    return LV_Valid;
507  case ChooseExprClass:
508    // __builtin_choose_expr is an lvalue if the selected operand is.
509    if (cast<ChooseExpr>(this)->isConditionTrue(Ctx))
510      return cast<ChooseExpr>(this)->getLHS()->isLvalue(Ctx);
511    else
512      return cast<ChooseExpr>(this)->getRHS()->isLvalue(Ctx);
513
514  case ExtVectorElementExprClass:
515    if (cast<ExtVectorElementExpr>(this)->containsDuplicateElements())
516      return LV_DuplicateVectorComponents;
517    return LV_Valid;
518  case ObjCIvarRefExprClass: // ObjC instance variables are lvalues.
519    return LV_Valid;
520  case ObjCPropertyRefExprClass: // FIXME: check if read-only property.
521    return LV_Valid;
522  case ObjCKVCRefExprClass: // FIXME: check if read-only property.
523    return LV_Valid;
524  case PredefinedExprClass:
525    return LV_Valid;
526  case VAArgExprClass:
527    return LV_Valid;
528  case CXXDefaultArgExprClass:
529    return cast<CXXDefaultArgExpr>(this)->getExpr()->isLvalue(Ctx);
530  case CXXConditionDeclExprClass:
531    return LV_Valid;
532  case CStyleCastExprClass:
533  case CXXFunctionalCastExprClass:
534  case CXXStaticCastExprClass:
535  case CXXDynamicCastExprClass:
536  case CXXReinterpretCastExprClass:
537  case CXXConstCastExprClass:
538    // The result of an explicit cast is an lvalue if the type we are
539    // casting to is a reference type. See C++ [expr.cast]p1,
540    // C++ [expr.static.cast]p2, C++ [expr.dynamic.cast]p2,
541    // C++ [expr.reinterpret.cast]p1, C++ [expr.const.cast]p1.
542    if (cast<ExplicitCastExpr>(this)->getTypeAsWritten()->isReferenceType())
543      return LV_Valid;
544    break;
545  case CXXTypeidExprClass:
546    // C++ 5.2.8p1: The result of a typeid expression is an lvalue of ...
547    return LV_Valid;
548  default:
549    break;
550  }
551  return LV_InvalidExpression;
552}
553
554/// isModifiableLvalue - C99 6.3.2.1: an lvalue that does not have array type,
555/// does not have an incomplete type, does not have a const-qualified type, and
556/// if it is a structure or union, does not have any member (including,
557/// recursively, any member or element of all contained aggregates or unions)
558/// with a const-qualified type.
559Expr::isModifiableLvalueResult Expr::isModifiableLvalue(ASTContext &Ctx) const {
560  isLvalueResult lvalResult = isLvalue(Ctx);
561
562  switch (lvalResult) {
563  case LV_Valid:
564    // C++ 3.10p11: Functions cannot be modified, but pointers to
565    // functions can be modifiable.
566    if (Ctx.getLangOptions().CPlusPlus && TR->isFunctionType())
567      return MLV_NotObjectType;
568    break;
569
570  case LV_NotObjectType: return MLV_NotObjectType;
571  case LV_IncompleteVoidType: return MLV_IncompleteVoidType;
572  case LV_DuplicateVectorComponents: return MLV_DuplicateVectorComponents;
573  case LV_InvalidExpression:
574    // If the top level is a C-style cast, and the subexpression is a valid
575    // lvalue, then this is probably a use of the old-school "cast as lvalue"
576    // GCC extension.  We don't support it, but we want to produce good
577    // diagnostics when it happens so that the user knows why.
578    if (const CStyleCastExpr *CE = dyn_cast<CStyleCastExpr>(this))
579      if (CE->getSubExpr()->isLvalue(Ctx) == LV_Valid)
580        return MLV_LValueCast;
581    return MLV_InvalidExpression;
582  case LV_MemberFunction: return MLV_MemberFunction;
583  }
584
585  QualType CT = Ctx.getCanonicalType(getType());
586
587  if (CT.isConstQualified())
588    return MLV_ConstQualified;
589  if (CT->isArrayType())
590    return MLV_ArrayType;
591  if (CT->isIncompleteType())
592    return MLV_IncompleteType;
593
594  if (const RecordType *r = CT->getAsRecordType()) {
595    if (r->hasConstFields())
596      return MLV_ConstQualified;
597  }
598  // The following is illegal:
599  //   void takeclosure(void (^C)(void));
600  //   void func() { int x = 1; takeclosure(^{ x = 7 }); }
601  //
602  if (getStmtClass() == BlockDeclRefExprClass) {
603    const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(this);
604    if (!BDR->isByRef() && isa<VarDecl>(BDR->getDecl()))
605      return MLV_NotBlockQualified;
606  }
607
608  // Assigning to an 'implicit' property?
609  else if (getStmtClass() == ObjCKVCRefExprClass) {
610    const ObjCKVCRefExpr* KVCExpr = cast<ObjCKVCRefExpr>(this);
611    if (KVCExpr->getSetterMethod() == 0)
612      return MLV_NoSetterProperty;
613  }
614  return MLV_Valid;
615}
616
617/// hasGlobalStorage - Return true if this expression has static storage
618/// duration.  This means that the address of this expression is a link-time
619/// constant.
620bool Expr::hasGlobalStorage() const {
621  switch (getStmtClass()) {
622  default:
623    return false;
624  case ParenExprClass:
625    return cast<ParenExpr>(this)->getSubExpr()->hasGlobalStorage();
626  case ImplicitCastExprClass:
627    return cast<ImplicitCastExpr>(this)->getSubExpr()->hasGlobalStorage();
628  case CompoundLiteralExprClass:
629    return cast<CompoundLiteralExpr>(this)->isFileScope();
630  case DeclRefExprClass:
631  case QualifiedDeclRefExprClass: {
632    const Decl *D = cast<DeclRefExpr>(this)->getDecl();
633    if (const VarDecl *VD = dyn_cast<VarDecl>(D))
634      return VD->hasGlobalStorage();
635    if (isa<FunctionDecl>(D))
636      return true;
637    return false;
638  }
639  case MemberExprClass: {
640    const MemberExpr *M = cast<MemberExpr>(this);
641    return !M->isArrow() && M->getBase()->hasGlobalStorage();
642  }
643  case ArraySubscriptExprClass:
644    return cast<ArraySubscriptExpr>(this)->getBase()->hasGlobalStorage();
645  case PredefinedExprClass:
646    return true;
647  case CXXDefaultArgExprClass:
648    return cast<CXXDefaultArgExpr>(this)->getExpr()->hasGlobalStorage();
649  }
650}
651
652Expr* Expr::IgnoreParens() {
653  Expr* E = this;
654  while (ParenExpr* P = dyn_cast<ParenExpr>(E))
655    E = P->getSubExpr();
656
657  return E;
658}
659
660/// IgnoreParenCasts - Ignore parentheses and casts.  Strip off any ParenExpr
661/// or CastExprs or ImplicitCastExprs, returning their operand.
662Expr *Expr::IgnoreParenCasts() {
663  Expr *E = this;
664  while (true) {
665    if (ParenExpr *P = dyn_cast<ParenExpr>(E))
666      E = P->getSubExpr();
667    else if (CastExpr *P = dyn_cast<CastExpr>(E))
668      E = P->getSubExpr();
669    else
670      return E;
671  }
672}
673
674/// hasAnyTypeDependentArguments - Determines if any of the expressions
675/// in Exprs is type-dependent.
676bool Expr::hasAnyTypeDependentArguments(Expr** Exprs, unsigned NumExprs) {
677  for (unsigned I = 0; I < NumExprs; ++I)
678    if (Exprs[I]->isTypeDependent())
679      return true;
680
681  return false;
682}
683
684/// hasAnyValueDependentArguments - Determines if any of the expressions
685/// in Exprs is value-dependent.
686bool Expr::hasAnyValueDependentArguments(Expr** Exprs, unsigned NumExprs) {
687  for (unsigned I = 0; I < NumExprs; ++I)
688    if (Exprs[I]->isValueDependent())
689      return true;
690
691  return false;
692}
693
694bool Expr::isConstantExpr(ASTContext &Ctx, SourceLocation *Loc) const {
695  switch (getStmtClass()) {
696  default:
697    if (!isEvaluatable(Ctx)) {
698      if (Loc) *Loc = getLocStart();
699      return false;
700    }
701    break;
702  case StringLiteralClass:
703    return true;
704  case InitListExprClass: {
705    const InitListExpr *Exp = cast<InitListExpr>(this);
706    unsigned numInits = Exp->getNumInits();
707    for (unsigned i = 0; i < numInits; i++) {
708      if (!Exp->getInit(i)->isConstantExpr(Ctx, Loc))
709        return false;
710    }
711  }
712  }
713
714  return true;
715}
716
717/// isIntegerConstantExpr - this recursive routine will test if an expression is
718/// an integer constant expression. Note: With the introduction of VLA's in
719/// C99 the result of the sizeof operator is no longer always a constant
720/// expression. The generalization of the wording to include any subexpression
721/// that is not evaluated (C99 6.6p3) means that nonconstant subexpressions
722/// can appear as operands to other operators (e.g. &&, ||, ?:). For instance,
723/// "0 || f()" can be treated as a constant expression. In C90 this expression,
724/// occurring in a context requiring a constant, would have been a constraint
725/// violation. FIXME: This routine currently implements C90 semantics.
726/// To properly implement C99 semantics this routine will need to evaluate
727/// expressions involving operators previously mentioned.
728
729/// FIXME: Pass up a reason why! Invalid operation in i-c-e, division by zero,
730/// comma, etc
731///
732/// FIXME: This should ext-warn on overflow during evaluation!  ISO C does not
733/// permit this.  This includes things like (int)1e1000
734///
735/// FIXME: Handle offsetof.  Two things to do:  Handle GCC's __builtin_offsetof
736/// to support gcc 4.0+  and handle the idiom GCC recognizes with a null pointer
737/// cast+dereference.
738bool Expr::isIntegerConstantExpr(llvm::APSInt &Result, ASTContext &Ctx,
739                                 SourceLocation *Loc, bool isEvaluated) const {
740  // Pretest for integral type; some parts of the code crash for types that
741  // can't be sized.
742  if (!getType()->isIntegralType()) {
743    if (Loc) *Loc = getLocStart();
744    return false;
745  }
746  switch (getStmtClass()) {
747  default:
748    if (Loc) *Loc = getLocStart();
749    return false;
750  case ParenExprClass:
751    return cast<ParenExpr>(this)->getSubExpr()->
752                     isIntegerConstantExpr(Result, Ctx, Loc, isEvaluated);
753  case IntegerLiteralClass:
754    Result = cast<IntegerLiteral>(this)->getValue();
755    break;
756  case CharacterLiteralClass: {
757    const CharacterLiteral *CL = cast<CharacterLiteral>(this);
758    Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
759    Result = CL->getValue();
760    Result.setIsUnsigned(!getType()->isSignedIntegerType());
761    break;
762  }
763  case CXXBoolLiteralExprClass: {
764    const CXXBoolLiteralExpr *BL = cast<CXXBoolLiteralExpr>(this);
765    Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
766    Result = BL->getValue();
767    Result.setIsUnsigned(!getType()->isSignedIntegerType());
768    break;
769  }
770  case CXXZeroInitValueExprClass:
771    Result.clear();
772    break;
773  case TypesCompatibleExprClass: {
774    const TypesCompatibleExpr *TCE = cast<TypesCompatibleExpr>(this);
775    Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
776    // Per gcc docs "this built-in function ignores top level
777    // qualifiers".  We need to use the canonical version to properly
778    // be able to strip CRV qualifiers from the type.
779    QualType T0 = Ctx.getCanonicalType(TCE->getArgType1());
780    QualType T1 = Ctx.getCanonicalType(TCE->getArgType2());
781    Result = Ctx.typesAreCompatible(T0.getUnqualifiedType(),
782                                    T1.getUnqualifiedType());
783    break;
784  }
785  case CallExprClass:
786  case CXXOperatorCallExprClass: {
787    const CallExpr *CE = cast<CallExpr>(this);
788    Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
789
790    // If this is a call to a builtin function, constant fold it otherwise
791    // reject it.
792    if (CE->isBuiltinCall()) {
793      EvalResult EvalResult;
794      if (CE->Evaluate(EvalResult, Ctx)) {
795        assert(!EvalResult.HasSideEffects &&
796               "Foldable builtin call should not have side effects!");
797        Result = EvalResult.Val.getInt();
798        break;  // It is a constant, expand it.
799      }
800    }
801
802    if (Loc) *Loc = getLocStart();
803    return false;
804  }
805  case DeclRefExprClass:
806  case QualifiedDeclRefExprClass:
807    if (const EnumConstantDecl *D =
808          dyn_cast<EnumConstantDecl>(cast<DeclRefExpr>(this)->getDecl())) {
809      Result = D->getInitVal();
810      break;
811    }
812    if (Loc) *Loc = getLocStart();
813    return false;
814  case UnaryOperatorClass: {
815    const UnaryOperator *Exp = cast<UnaryOperator>(this);
816
817    // Get the operand value.  If this is offsetof, do not evalute the
818    // operand.  This affects C99 6.6p3.
819    if (!Exp->isOffsetOfOp() && !Exp->getSubExpr()->
820                        isIntegerConstantExpr(Result, Ctx, Loc, isEvaluated))
821      return false;
822
823    switch (Exp->getOpcode()) {
824    // Address, indirect, pre/post inc/dec, etc are not valid constant exprs.
825    // See C99 6.6p3.
826    default:
827      if (Loc) *Loc = Exp->getOperatorLoc();
828      return false;
829    case UnaryOperator::Extension:
830      return true;  // FIXME: this is wrong.
831    case UnaryOperator::LNot: {
832      bool Val = Result == 0;
833      Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
834      Result = Val;
835      break;
836    }
837    case UnaryOperator::Plus:
838      break;
839    case UnaryOperator::Minus:
840      Result = -Result;
841      break;
842    case UnaryOperator::Not:
843      Result = ~Result;
844      break;
845    case UnaryOperator::OffsetOf:
846      Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
847      Result = Exp->evaluateOffsetOf(Ctx);
848    }
849    break;
850  }
851  case SizeOfAlignOfExprClass: {
852    const SizeOfAlignOfExpr *Exp = cast<SizeOfAlignOfExpr>(this);
853
854    // Return the result in the right width.
855    Result.zextOrTrunc(static_cast<uint32_t>(Ctx.getTypeSize(getType())));
856
857    QualType ArgTy = Exp->getTypeOfArgument();
858    // sizeof(void) and __alignof__(void) = 1 as a gcc extension.
859    if (ArgTy->isVoidType()) {
860      Result = 1;
861      break;
862    }
863
864    // alignof always evaluates to a constant, sizeof does if arg is not VLA.
865    if (Exp->isSizeOf() && !ArgTy->isConstantSizeType()) {
866      if (Loc) *Loc = Exp->getOperatorLoc();
867      return false;
868    }
869
870    // Get information about the size or align.
871    if (ArgTy->isFunctionType()) {
872      // GCC extension: sizeof(function) = 1.
873      Result = Exp->isSizeOf() ? 1 : 4;
874    } else {
875      unsigned CharSize = Ctx.Target.getCharWidth();
876      if (Exp->isSizeOf())
877        Result = Ctx.getTypeSize(ArgTy) / CharSize;
878      else
879        Result = Ctx.getTypeAlign(ArgTy) / CharSize;
880    }
881    break;
882  }
883  case BinaryOperatorClass: {
884    const BinaryOperator *Exp = cast<BinaryOperator>(this);
885    llvm::APSInt LHS, RHS;
886
887    // Initialize result to have correct signedness and width.
888    Result = llvm::APSInt(static_cast<uint32_t>(Ctx.getTypeSize(getType())),
889                          !getType()->isSignedIntegerType());
890
891    // The LHS of a constant expr is always evaluated and needed.
892    if (!Exp->getLHS()->isIntegerConstantExpr(LHS, Ctx, Loc, isEvaluated))
893      return false;
894
895    // The short-circuiting &&/|| operators don't necessarily evaluate their
896    // RHS.  Make sure to pass isEvaluated down correctly.
897    if (Exp->isLogicalOp()) {
898      bool RHSEval;
899      if (Exp->getOpcode() == BinaryOperator::LAnd)
900        RHSEval = LHS != 0;
901      else {
902        assert(Exp->getOpcode() == BinaryOperator::LOr &&"Unexpected logical");
903        RHSEval = LHS == 0;
904      }
905
906      if (!Exp->getRHS()->isIntegerConstantExpr(RHS, Ctx, Loc,
907                                                isEvaluated & RHSEval))
908        return false;
909    } else {
910      if (!Exp->getRHS()->isIntegerConstantExpr(RHS, Ctx, Loc, isEvaluated))
911        return false;
912    }
913
914    switch (Exp->getOpcode()) {
915    default:
916      if (Loc) *Loc = getLocStart();
917      return false;
918    case BinaryOperator::Mul:
919      Result = LHS * RHS;
920      break;
921    case BinaryOperator::Div:
922      if (RHS == 0) {
923        if (!isEvaluated) break;
924        if (Loc) *Loc = getLocStart();
925        return false;
926      }
927      Result = LHS / RHS;
928      break;
929    case BinaryOperator::Rem:
930      if (RHS == 0) {
931        if (!isEvaluated) break;
932        if (Loc) *Loc = getLocStart();
933        return false;
934      }
935      Result = LHS % RHS;
936      break;
937    case BinaryOperator::Add: Result = LHS + RHS; break;
938    case BinaryOperator::Sub: Result = LHS - RHS; break;
939    case BinaryOperator::Shl:
940      Result = LHS <<
941        static_cast<uint32_t>(RHS.getLimitedValue(LHS.getBitWidth()-1));
942    break;
943    case BinaryOperator::Shr:
944      Result = LHS >>
945        static_cast<uint32_t>(RHS.getLimitedValue(LHS.getBitWidth()-1));
946      break;
947    case BinaryOperator::LT:  Result = LHS < RHS; break;
948    case BinaryOperator::GT:  Result = LHS > RHS; break;
949    case BinaryOperator::LE:  Result = LHS <= RHS; break;
950    case BinaryOperator::GE:  Result = LHS >= RHS; break;
951    case BinaryOperator::EQ:  Result = LHS == RHS; break;
952    case BinaryOperator::NE:  Result = LHS != RHS; break;
953    case BinaryOperator::And: Result = LHS & RHS; break;
954    case BinaryOperator::Xor: Result = LHS ^ RHS; break;
955    case BinaryOperator::Or:  Result = LHS | RHS; break;
956    case BinaryOperator::LAnd:
957      Result = LHS != 0 && RHS != 0;
958      break;
959    case BinaryOperator::LOr:
960      Result = LHS != 0 || RHS != 0;
961      break;
962
963    case BinaryOperator::Comma:
964      // C99 6.6p3: "shall not contain assignment, ..., or comma operators,
965      // *except* when they are contained within a subexpression that is not
966      // evaluated".  Note that Assignment can never happen due to constraints
967      // on the LHS subexpr, so we don't need to check it here.
968      if (isEvaluated) {
969        if (Loc) *Loc = getLocStart();
970        return false;
971      }
972
973      // The result of the constant expr is the RHS.
974      Result = RHS;
975      return true;
976    }
977
978    assert(!Exp->isAssignmentOp() && "LHS can't be a constant expr!");
979    break;
980  }
981  case ImplicitCastExprClass:
982  case CStyleCastExprClass:
983  case CXXFunctionalCastExprClass: {
984    const Expr *SubExpr = cast<CastExpr>(this)->getSubExpr();
985    SourceLocation CastLoc = getLocStart();
986
987    // C99 6.6p6: shall only convert arithmetic types to integer types.
988    if (!SubExpr->getType()->isArithmeticType() ||
989        !getType()->isIntegerType()) {
990      if (Loc) *Loc = SubExpr->getLocStart();
991      return false;
992    }
993
994    uint32_t DestWidth = static_cast<uint32_t>(Ctx.getTypeSize(getType()));
995
996    // Handle simple integer->integer casts.
997    if (SubExpr->getType()->isIntegerType()) {
998      if (!SubExpr->isIntegerConstantExpr(Result, Ctx, Loc, isEvaluated))
999        return false;
1000
1001      // Figure out if this is a truncate, extend or noop cast.
1002      // If the input is signed, do a sign extend, noop, or truncate.
1003      if (getType()->isBooleanType()) {
1004        // Conversion to bool compares against zero.
1005        Result = Result != 0;
1006        Result.zextOrTrunc(DestWidth);
1007      } else if (SubExpr->getType()->isSignedIntegerType())
1008        Result.sextOrTrunc(DestWidth);
1009      else  // If the input is unsigned, do a zero extend, noop, or truncate.
1010        Result.zextOrTrunc(DestWidth);
1011      break;
1012    }
1013
1014    // Allow floating constants that are the immediate operands of casts or that
1015    // are parenthesized.
1016    const Expr *Operand = SubExpr;
1017    while (const ParenExpr *PE = dyn_cast<ParenExpr>(Operand))
1018      Operand = PE->getSubExpr();
1019
1020    // If this isn't a floating literal, we can't handle it.
1021    const FloatingLiteral *FL = dyn_cast<FloatingLiteral>(Operand);
1022    if (!FL) {
1023      if (Loc) *Loc = Operand->getLocStart();
1024      return false;
1025    }
1026
1027    // If the destination is boolean, compare against zero.
1028    if (getType()->isBooleanType()) {
1029      Result = !FL->getValue().isZero();
1030      Result.zextOrTrunc(DestWidth);
1031      break;
1032    }
1033
1034    // Determine whether we are converting to unsigned or signed.
1035    bool DestSigned = getType()->isSignedIntegerType();
1036
1037    // TODO: Warn on overflow, but probably not here: isIntegerConstantExpr can
1038    // be called multiple times per AST.
1039    uint64_t Space[4];
1040    bool ignored;
1041    (void)FL->getValue().convertToInteger(Space, DestWidth, DestSigned,
1042                                          llvm::APFloat::rmTowardZero,
1043                                          &ignored);
1044    Result = llvm::APInt(DestWidth, 4, Space);
1045    break;
1046  }
1047  case ConditionalOperatorClass: {
1048    const ConditionalOperator *Exp = cast<ConditionalOperator>(this);
1049
1050    const Expr *Cond = Exp->getCond();
1051
1052    if (!Cond->isIntegerConstantExpr(Result, Ctx, Loc, isEvaluated))
1053      return false;
1054
1055    const Expr *TrueExp  = Exp->getLHS();
1056    const Expr *FalseExp = Exp->getRHS();
1057    if (Result == 0) std::swap(TrueExp, FalseExp);
1058
1059    // If the condition (ignoring parens) is a __builtin_constant_p call,
1060    // then only the true side is actually considered in an integer constant
1061    // expression, and it is fully evaluated.  This is an important GNU
1062    // extension.  See GCC PR38377 for discussion.
1063    if (const CallExpr *CallCE = dyn_cast<CallExpr>(Cond->IgnoreParenCasts()))
1064      if (CallCE->isBuiltinCall() == Builtin::BI__builtin_constant_p) {
1065        EvalResult EVResult;
1066        if (!Evaluate(EVResult, Ctx) || EVResult.HasSideEffects)
1067          return false;
1068        assert(EVResult.Val.isInt() && "FP conditional expr not expected");
1069        Result = EVResult.Val.getInt();
1070        if (Loc) *Loc = EVResult.DiagLoc;
1071        return true;
1072      }
1073
1074    // Evaluate the false one first, discard the result.
1075    if (FalseExp && !FalseExp->isIntegerConstantExpr(Result, Ctx, Loc, false))
1076      return false;
1077    // Evalute the true one, capture the result.
1078    if (TrueExp &&
1079        !TrueExp->isIntegerConstantExpr(Result, Ctx, Loc, isEvaluated))
1080      return false;
1081    break;
1082  }
1083  case CXXDefaultArgExprClass:
1084    return cast<CXXDefaultArgExpr>(this)
1085             ->isIntegerConstantExpr(Result, Ctx, Loc, isEvaluated);
1086
1087  case UnaryTypeTraitExprClass:
1088    Result = cast<UnaryTypeTraitExpr>(this)->Evaluate();
1089    return true;
1090  }
1091
1092  // Cases that are valid constant exprs fall through to here.
1093  Result.setIsUnsigned(getType()->isUnsignedIntegerType());
1094  return true;
1095}
1096
1097/// isNullPointerConstant - C99 6.3.2.3p3 -  Return true if this is either an
1098/// integer constant expression with the value zero, or if this is one that is
1099/// cast to void*.
1100bool Expr::isNullPointerConstant(ASTContext &Ctx) const
1101{
1102  // Strip off a cast to void*, if it exists. Except in C++.
1103  if (const ExplicitCastExpr *CE = dyn_cast<ExplicitCastExpr>(this)) {
1104    if (!Ctx.getLangOptions().CPlusPlus) {
1105      // Check that it is a cast to void*.
1106      if (const PointerType *PT = CE->getType()->getAsPointerType()) {
1107        QualType Pointee = PT->getPointeeType();
1108        if (Pointee.getCVRQualifiers() == 0 &&
1109            Pointee->isVoidType() &&                              // to void*
1110            CE->getSubExpr()->getType()->isIntegerType())         // from int.
1111          return CE->getSubExpr()->isNullPointerConstant(Ctx);
1112      }
1113    }
1114  } else if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(this)) {
1115    // Ignore the ImplicitCastExpr type entirely.
1116    return ICE->getSubExpr()->isNullPointerConstant(Ctx);
1117  } else if (const ParenExpr *PE = dyn_cast<ParenExpr>(this)) {
1118    // Accept ((void*)0) as a null pointer constant, as many other
1119    // implementations do.
1120    return PE->getSubExpr()->isNullPointerConstant(Ctx);
1121  } else if (const CXXDefaultArgExpr *DefaultArg
1122               = dyn_cast<CXXDefaultArgExpr>(this)) {
1123    // See through default argument expressions
1124    return DefaultArg->getExpr()->isNullPointerConstant(Ctx);
1125  } else if (isa<GNUNullExpr>(this)) {
1126    // The GNU __null extension is always a null pointer constant.
1127    return true;
1128  }
1129
1130  // This expression must be an integer type.
1131  if (!getType()->isIntegerType())
1132    return false;
1133
1134  // If we have an integer constant expression, we need to *evaluate* it and
1135  // test for the value 0.
1136  // FIXME: We should probably return false if we're compiling in strict mode
1137  // and Diag is not null (this indicates that the value was foldable but not
1138  // an ICE.
1139  EvalResult Result;
1140  return Evaluate(Result, Ctx) && !Result.HasSideEffects &&
1141        Result.Val.isInt() && Result.Val.getInt() == 0;
1142}
1143
1144/// isBitField - Return true if this expression is a bit-field.
1145bool Expr::isBitField() {
1146  Expr *E = this->IgnoreParenCasts();
1147  if (MemberExpr *MemRef = dyn_cast<MemberExpr>(E))
1148    if (FieldDecl *Field = dyn_cast<FieldDecl>(MemRef->getMemberDecl()))
1149        return Field->isBitField();
1150  return false;
1151}
1152
1153unsigned ExtVectorElementExpr::getNumElements() const {
1154  if (const VectorType *VT = getType()->getAsVectorType())
1155    return VT->getNumElements();
1156  return 1;
1157}
1158
1159/// containsDuplicateElements - Return true if any element access is repeated.
1160bool ExtVectorElementExpr::containsDuplicateElements() const {
1161  const char *compStr = Accessor.getName();
1162  unsigned length = Accessor.getLength();
1163
1164  // Halving swizzles do not contain duplicate elements.
1165  if (!strcmp(compStr, "hi") || !strcmp(compStr, "lo") ||
1166      !strcmp(compStr, "even") || !strcmp(compStr, "odd"))
1167    return false;
1168
1169  // Advance past s-char prefix on hex swizzles.
1170  if (*compStr == 's') {
1171    compStr++;
1172    length--;
1173  }
1174
1175  for (unsigned i = 0; i != length-1; i++) {
1176    const char *s = compStr+i;
1177    for (const char c = *s++; *s; s++)
1178      if (c == *s)
1179        return true;
1180  }
1181  return false;
1182}
1183
1184/// getEncodedElementAccess - We encode the fields as a llvm ConstantArray.
1185void ExtVectorElementExpr::getEncodedElementAccess(
1186                                  llvm::SmallVectorImpl<unsigned> &Elts) const {
1187  const char *compStr = Accessor.getName();
1188  if (*compStr == 's')
1189    compStr++;
1190
1191  bool isHi =   !strcmp(compStr, "hi");
1192  bool isLo =   !strcmp(compStr, "lo");
1193  bool isEven = !strcmp(compStr, "even");
1194  bool isOdd  = !strcmp(compStr, "odd");
1195
1196  for (unsigned i = 0, e = getNumElements(); i != e; ++i) {
1197    uint64_t Index;
1198
1199    if (isHi)
1200      Index = e + i;
1201    else if (isLo)
1202      Index = i;
1203    else if (isEven)
1204      Index = 2 * i;
1205    else if (isOdd)
1206      Index = 2 * i + 1;
1207    else
1208      Index = ExtVectorType::getAccessorIdx(compStr[i]);
1209
1210    Elts.push_back(Index);
1211  }
1212}
1213
1214// constructor for instance messages.
1215ObjCMessageExpr::ObjCMessageExpr(Expr *receiver, Selector selInfo,
1216                QualType retType, ObjCMethodDecl *mproto,
1217                SourceLocation LBrac, SourceLocation RBrac,
1218                Expr **ArgExprs, unsigned nargs)
1219  : Expr(ObjCMessageExprClass, retType), SelName(selInfo),
1220    MethodProto(mproto) {
1221  NumArgs = nargs;
1222  SubExprs = new Stmt*[NumArgs+1];
1223  SubExprs[RECEIVER] = receiver;
1224  if (NumArgs) {
1225    for (unsigned i = 0; i != NumArgs; ++i)
1226      SubExprs[i+ARGS_START] = static_cast<Expr *>(ArgExprs[i]);
1227  }
1228  LBracloc = LBrac;
1229  RBracloc = RBrac;
1230}
1231
1232// constructor for class messages.
1233// FIXME: clsName should be typed to ObjCInterfaceType
1234ObjCMessageExpr::ObjCMessageExpr(IdentifierInfo *clsName, Selector selInfo,
1235                QualType retType, ObjCMethodDecl *mproto,
1236                SourceLocation LBrac, SourceLocation RBrac,
1237                Expr **ArgExprs, unsigned nargs)
1238  : Expr(ObjCMessageExprClass, retType), SelName(selInfo),
1239    MethodProto(mproto) {
1240  NumArgs = nargs;
1241  SubExprs = new Stmt*[NumArgs+1];
1242  SubExprs[RECEIVER] = (Expr*) ((uintptr_t) clsName | IsClsMethDeclUnknown);
1243  if (NumArgs) {
1244    for (unsigned i = 0; i != NumArgs; ++i)
1245      SubExprs[i+ARGS_START] = static_cast<Expr *>(ArgExprs[i]);
1246  }
1247  LBracloc = LBrac;
1248  RBracloc = RBrac;
1249}
1250
1251// constructor for class messages.
1252ObjCMessageExpr::ObjCMessageExpr(ObjCInterfaceDecl *cls, Selector selInfo,
1253                                 QualType retType, ObjCMethodDecl *mproto,
1254                                 SourceLocation LBrac, SourceLocation RBrac,
1255                                 Expr **ArgExprs, unsigned nargs)
1256: Expr(ObjCMessageExprClass, retType), SelName(selInfo),
1257MethodProto(mproto) {
1258  NumArgs = nargs;
1259  SubExprs = new Stmt*[NumArgs+1];
1260  SubExprs[RECEIVER] = (Expr*) ((uintptr_t) cls | IsClsMethDeclKnown);
1261  if (NumArgs) {
1262    for (unsigned i = 0; i != NumArgs; ++i)
1263      SubExprs[i+ARGS_START] = static_cast<Expr *>(ArgExprs[i]);
1264  }
1265  LBracloc = LBrac;
1266  RBracloc = RBrac;
1267}
1268
1269ObjCMessageExpr::ClassInfo ObjCMessageExpr::getClassInfo() const {
1270  uintptr_t x = (uintptr_t) SubExprs[RECEIVER];
1271  switch (x & Flags) {
1272    default:
1273      assert(false && "Invalid ObjCMessageExpr.");
1274    case IsInstMeth:
1275      return ClassInfo(0, 0);
1276    case IsClsMethDeclUnknown:
1277      return ClassInfo(0, (IdentifierInfo*) (x & ~Flags));
1278    case IsClsMethDeclKnown: {
1279      ObjCInterfaceDecl* D = (ObjCInterfaceDecl*) (x & ~Flags);
1280      return ClassInfo(D, D->getIdentifier());
1281    }
1282  }
1283}
1284
1285bool ChooseExpr::isConditionTrue(ASTContext &C) const {
1286  return getCond()->getIntegerConstantExprValue(C) != 0;
1287}
1288
1289static int64_t evaluateOffsetOf(ASTContext& C, const Expr *E) {
1290  if (const MemberExpr *ME = dyn_cast<MemberExpr>(E)) {
1291    QualType Ty = ME->getBase()->getType();
1292
1293    RecordDecl *RD = Ty->getAsRecordType()->getDecl();
1294    const ASTRecordLayout &RL = C.getASTRecordLayout(RD);
1295    if (FieldDecl *FD = dyn_cast<FieldDecl>(ME->getMemberDecl())) {
1296      // FIXME: This is linear time. And the fact that we're indexing
1297      // into the layout by position in the record means that we're
1298      // either stuck numbering the fields in the AST or we have to keep
1299      // the linear search (yuck and yuck).
1300      unsigned i = 0;
1301      for (RecordDecl::field_iterator Field = RD->field_begin(),
1302                                   FieldEnd = RD->field_end();
1303           Field != FieldEnd; (void)++Field, ++i) {
1304        if (*Field == FD)
1305          break;
1306      }
1307
1308      return RL.getFieldOffset(i) + evaluateOffsetOf(C, ME->getBase());
1309    }
1310  } else if (const ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(E)) {
1311    const Expr *Base = ASE->getBase();
1312
1313    int64_t size = C.getTypeSize(ASE->getType());
1314    size *= ASE->getIdx()->getIntegerConstantExprValue(C).getSExtValue();
1315
1316    return size + evaluateOffsetOf(C, Base);
1317  } else if (isa<CompoundLiteralExpr>(E))
1318    return 0;
1319
1320  assert(0 && "Unknown offsetof subexpression!");
1321  return 0;
1322}
1323
1324int64_t UnaryOperator::evaluateOffsetOf(ASTContext& C) const
1325{
1326  assert(Opc == OffsetOf && "Unary operator not offsetof!");
1327
1328  unsigned CharSize = C.Target.getCharWidth();
1329  return ::evaluateOffsetOf(C, cast<Expr>(Val)) / CharSize;
1330}
1331
1332void SizeOfAlignOfExpr::Destroy(ASTContext& C) {
1333  // Override default behavior of traversing children. If this has a type
1334  // operand and the type is a variable-length array, the child iteration
1335  // will iterate over the size expression. However, this expression belongs
1336  // to the type, not to this, so we don't want to delete it.
1337  // We still want to delete this expression.
1338  // FIXME: Same as in Stmt::Destroy - will be eventually in ASTContext's
1339  // pool allocator.
1340  if (isArgumentType())
1341    delete this;
1342  else
1343    Expr::Destroy(C);
1344}
1345
1346//===----------------------------------------------------------------------===//
1347//  ExprIterator.
1348//===----------------------------------------------------------------------===//
1349
1350Expr* ExprIterator::operator[](size_t idx) { return cast<Expr>(I[idx]); }
1351Expr* ExprIterator::operator*() const { return cast<Expr>(*I); }
1352Expr* ExprIterator::operator->() const { return cast<Expr>(*I); }
1353const Expr* ConstExprIterator::operator[](size_t idx) const {
1354  return cast<Expr>(I[idx]);
1355}
1356const Expr* ConstExprIterator::operator*() const { return cast<Expr>(*I); }
1357const Expr* ConstExprIterator::operator->() const { return cast<Expr>(*I); }
1358
1359//===----------------------------------------------------------------------===//
1360//  Child Iterators for iterating over subexpressions/substatements
1361//===----------------------------------------------------------------------===//
1362
1363// DeclRefExpr
1364Stmt::child_iterator DeclRefExpr::child_begin() { return child_iterator(); }
1365Stmt::child_iterator DeclRefExpr::child_end() { return child_iterator(); }
1366
1367// ObjCIvarRefExpr
1368Stmt::child_iterator ObjCIvarRefExpr::child_begin() { return &Base; }
1369Stmt::child_iterator ObjCIvarRefExpr::child_end() { return &Base+1; }
1370
1371// ObjCPropertyRefExpr
1372Stmt::child_iterator ObjCPropertyRefExpr::child_begin() { return &Base; }
1373Stmt::child_iterator ObjCPropertyRefExpr::child_end() { return &Base+1; }
1374
1375// ObjCKVCRefExpr
1376Stmt::child_iterator ObjCKVCRefExpr::child_begin() { return &Base; }
1377Stmt::child_iterator ObjCKVCRefExpr::child_end() { return &Base+1; }
1378
1379// ObjCSuperExpr
1380Stmt::child_iterator ObjCSuperExpr::child_begin() { return child_iterator(); }
1381Stmt::child_iterator ObjCSuperExpr::child_end() { return child_iterator(); }
1382
1383// PredefinedExpr
1384Stmt::child_iterator PredefinedExpr::child_begin() { return child_iterator(); }
1385Stmt::child_iterator PredefinedExpr::child_end() { return child_iterator(); }
1386
1387// IntegerLiteral
1388Stmt::child_iterator IntegerLiteral::child_begin() { return child_iterator(); }
1389Stmt::child_iterator IntegerLiteral::child_end() { return child_iterator(); }
1390
1391// CharacterLiteral
1392Stmt::child_iterator CharacterLiteral::child_begin() { return child_iterator(); }
1393Stmt::child_iterator CharacterLiteral::child_end() { return child_iterator(); }
1394
1395// FloatingLiteral
1396Stmt::child_iterator FloatingLiteral::child_begin() { return child_iterator(); }
1397Stmt::child_iterator FloatingLiteral::child_end() { return child_iterator(); }
1398
1399// ImaginaryLiteral
1400Stmt::child_iterator ImaginaryLiteral::child_begin() { return &Val; }
1401Stmt::child_iterator ImaginaryLiteral::child_end() { return &Val+1; }
1402
1403// StringLiteral
1404Stmt::child_iterator StringLiteral::child_begin() { return child_iterator(); }
1405Stmt::child_iterator StringLiteral::child_end() { return child_iterator(); }
1406
1407// ParenExpr
1408Stmt::child_iterator ParenExpr::child_begin() { return &Val; }
1409Stmt::child_iterator ParenExpr::child_end() { return &Val+1; }
1410
1411// UnaryOperator
1412Stmt::child_iterator UnaryOperator::child_begin() { return &Val; }
1413Stmt::child_iterator UnaryOperator::child_end() { return &Val+1; }
1414
1415// SizeOfAlignOfExpr
1416Stmt::child_iterator SizeOfAlignOfExpr::child_begin() {
1417  // If this is of a type and the type is a VLA type (and not a typedef), the
1418  // size expression of the VLA needs to be treated as an executable expression.
1419  // Why isn't this weirdness documented better in StmtIterator?
1420  if (isArgumentType()) {
1421    if (VariableArrayType* T = dyn_cast<VariableArrayType>(
1422                                   getArgumentType().getTypePtr()))
1423      return child_iterator(T);
1424    return child_iterator();
1425  }
1426  return child_iterator(&Argument.Ex);
1427}
1428Stmt::child_iterator SizeOfAlignOfExpr::child_end() {
1429  if (isArgumentType())
1430    return child_iterator();
1431  return child_iterator(&Argument.Ex + 1);
1432}
1433
1434// ArraySubscriptExpr
1435Stmt::child_iterator ArraySubscriptExpr::child_begin() {
1436  return &SubExprs[0];
1437}
1438Stmt::child_iterator ArraySubscriptExpr::child_end() {
1439  return &SubExprs[0]+END_EXPR;
1440}
1441
1442// CallExpr
1443Stmt::child_iterator CallExpr::child_begin() {
1444  return &SubExprs[0];
1445}
1446Stmt::child_iterator CallExpr::child_end() {
1447  return &SubExprs[0]+NumArgs+ARGS_START;
1448}
1449
1450// MemberExpr
1451Stmt::child_iterator MemberExpr::child_begin() { return &Base; }
1452Stmt::child_iterator MemberExpr::child_end() { return &Base+1; }
1453
1454// ExtVectorElementExpr
1455Stmt::child_iterator ExtVectorElementExpr::child_begin() { return &Base; }
1456Stmt::child_iterator ExtVectorElementExpr::child_end() { return &Base+1; }
1457
1458// CompoundLiteralExpr
1459Stmt::child_iterator CompoundLiteralExpr::child_begin() { return &Init; }
1460Stmt::child_iterator CompoundLiteralExpr::child_end() { return &Init+1; }
1461
1462// CastExpr
1463Stmt::child_iterator CastExpr::child_begin() { return &Op; }
1464Stmt::child_iterator CastExpr::child_end() { return &Op+1; }
1465
1466// BinaryOperator
1467Stmt::child_iterator BinaryOperator::child_begin() {
1468  return &SubExprs[0];
1469}
1470Stmt::child_iterator BinaryOperator::child_end() {
1471  return &SubExprs[0]+END_EXPR;
1472}
1473
1474// ConditionalOperator
1475Stmt::child_iterator ConditionalOperator::child_begin() {
1476  return &SubExprs[0];
1477}
1478Stmt::child_iterator ConditionalOperator::child_end() {
1479  return &SubExprs[0]+END_EXPR;
1480}
1481
1482// AddrLabelExpr
1483Stmt::child_iterator AddrLabelExpr::child_begin() { return child_iterator(); }
1484Stmt::child_iterator AddrLabelExpr::child_end() { return child_iterator(); }
1485
1486// StmtExpr
1487Stmt::child_iterator StmtExpr::child_begin() { return &SubStmt; }
1488Stmt::child_iterator StmtExpr::child_end() { return &SubStmt+1; }
1489
1490// TypesCompatibleExpr
1491Stmt::child_iterator TypesCompatibleExpr::child_begin() {
1492  return child_iterator();
1493}
1494
1495Stmt::child_iterator TypesCompatibleExpr::child_end() {
1496  return child_iterator();
1497}
1498
1499// ChooseExpr
1500Stmt::child_iterator ChooseExpr::child_begin() { return &SubExprs[0]; }
1501Stmt::child_iterator ChooseExpr::child_end() { return &SubExprs[0]+END_EXPR; }
1502
1503// GNUNullExpr
1504Stmt::child_iterator GNUNullExpr::child_begin() { return child_iterator(); }
1505Stmt::child_iterator GNUNullExpr::child_end() { return child_iterator(); }
1506
1507// OverloadExpr
1508Stmt::child_iterator OverloadExpr::child_begin() { return &SubExprs[0]; }
1509Stmt::child_iterator OverloadExpr::child_end() { return &SubExprs[0]+NumExprs; }
1510
1511// ShuffleVectorExpr
1512Stmt::child_iterator ShuffleVectorExpr::child_begin() {
1513  return &SubExprs[0];
1514}
1515Stmt::child_iterator ShuffleVectorExpr::child_end() {
1516  return &SubExprs[0]+NumExprs;
1517}
1518
1519// VAArgExpr
1520Stmt::child_iterator VAArgExpr::child_begin() { return &Val; }
1521Stmt::child_iterator VAArgExpr::child_end() { return &Val+1; }
1522
1523// InitListExpr
1524Stmt::child_iterator InitListExpr::child_begin() {
1525  return InitExprs.size() ? &InitExprs[0] : 0;
1526}
1527Stmt::child_iterator InitListExpr::child_end() {
1528  return InitExprs.size() ? &InitExprs[0] + InitExprs.size() : 0;
1529}
1530
1531// ObjCStringLiteral
1532Stmt::child_iterator ObjCStringLiteral::child_begin() {
1533  return child_iterator();
1534}
1535Stmt::child_iterator ObjCStringLiteral::child_end() {
1536  return child_iterator();
1537}
1538
1539// ObjCEncodeExpr
1540Stmt::child_iterator ObjCEncodeExpr::child_begin() { return child_iterator(); }
1541Stmt::child_iterator ObjCEncodeExpr::child_end() { return child_iterator(); }
1542
1543// ObjCSelectorExpr
1544Stmt::child_iterator ObjCSelectorExpr::child_begin() {
1545  return child_iterator();
1546}
1547Stmt::child_iterator ObjCSelectorExpr::child_end() {
1548  return child_iterator();
1549}
1550
1551// ObjCProtocolExpr
1552Stmt::child_iterator ObjCProtocolExpr::child_begin() {
1553  return child_iterator();
1554}
1555Stmt::child_iterator ObjCProtocolExpr::child_end() {
1556  return child_iterator();
1557}
1558
1559// ObjCMessageExpr
1560Stmt::child_iterator ObjCMessageExpr::child_begin() {
1561  return getReceiver() ? &SubExprs[0] : &SubExprs[0] + ARGS_START;
1562}
1563Stmt::child_iterator ObjCMessageExpr::child_end() {
1564  return &SubExprs[0]+ARGS_START+getNumArgs();
1565}
1566
1567// Blocks
1568Stmt::child_iterator BlockExpr::child_begin() { return child_iterator(); }
1569Stmt::child_iterator BlockExpr::child_end() { return child_iterator(); }
1570
1571Stmt::child_iterator BlockDeclRefExpr::child_begin() { return child_iterator();}
1572Stmt::child_iterator BlockDeclRefExpr::child_end() { return child_iterator(); }
1573