contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp

   1 //=-- ExprEngineC.cpp - ExprEngine support for C expressions ----*- C++ -*-===//
   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 defines ExprEngine's support for C expressions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/AST/ExprCXX.h"
  15 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  17
  18 using namespace clang;
  19 using namespace ento;
  20 using llvm::APSInt;
  21
  22 void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,
  23                                      ExplodedNode *Pred,
  24                                      ExplodedNodeSet &Dst) {
  25
  26   Expr *LHS = B->getLHS()->IgnoreParens();
  27   Expr *RHS = B->getRHS()->IgnoreParens();
  28
  29   // FIXME: Prechecks eventually go in ::Visit().
  30   ExplodedNodeSet CheckedSet;
  31   ExplodedNodeSet Tmp2;
  32   getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this);
  33
  34   // With both the LHS and RHS evaluated, process the operation itself.
  35   for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end();
  36          it != ei; ++it) {
  37
  38     ProgramStateRef state = (*it)->getState();
  39     const LocationContext *LCtx = (*it)->getLocationContext();
  40     SVal LeftV = state->getSVal(LHS, LCtx);
  41     SVal RightV = state->getSVal(RHS, LCtx);
  42
  43     BinaryOperator::Opcode Op = B->getOpcode();
  44
  45     if (Op == BO_Assign) {
  46       // EXPERIMENTAL: "Conjured" symbols.
  47       // FIXME: Handle structs.
  48       if (RightV.isUnknown()) {
  49         unsigned Count = currBldrCtx->blockCount();
  50         RightV = svalBuilder.conjureSymbolVal(0, B->getRHS(), LCtx, Count);
  51       }
  52       // Simulate the effects of a "store":  bind the value of the RHS
  53       // to the L-Value represented by the LHS.
  54       SVal ExprVal = B->isGLValue() ? LeftV : RightV;
  55       evalStore(Tmp2, B, LHS, *it, state->BindExpr(B, LCtx, ExprVal),
  56                 LeftV, RightV);
  57       continue;
  58     }
  59
  60     if (!B->isAssignmentOp()) {
  61       StmtNodeBuilder Bldr(*it, Tmp2, *currBldrCtx);
  62
  63       if (B->isAdditiveOp()) {
  64         // If one of the operands is a location, conjure a symbol for the other
  65         // one (offset) if it's unknown so that memory arithmetic always
  66         // results in an ElementRegion.
  67         // TODO: This can be removed after we enable history tracking with
  68         // SymSymExpr.
  69         unsigned Count = currBldrCtx->blockCount();
  70         if (LeftV.getAs<Loc>() &&
  71             RHS->getType()->isIntegralOrEnumerationType() &&
  72             RightV.isUnknown()) {
  73           RightV = svalBuilder.conjureSymbolVal(RHS, LCtx, RHS->getType(),
  74                                                 Count);
  75         }
  76         if (RightV.getAs<Loc>() &&
  77             LHS->getType()->isIntegralOrEnumerationType() &&
  78             LeftV.isUnknown()) {
  79           LeftV = svalBuilder.conjureSymbolVal(LHS, LCtx, LHS->getType(),
  80                                                Count);
  81         }
  82       }
  83
  84       // Process non-assignments except commas or short-circuited
  85       // logical expressions (LAnd and LOr).
  86       SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());
  87       if (Result.isUnknown()) {
  88         Bldr.generateNode(B, *it, state);
  89         continue;
  90       }
  91
  92       state = state->BindExpr(B, LCtx, Result);
  93       Bldr.generateNode(B, *it, state);
  94       continue;
  95     }
  96
  97     assert (B->isCompoundAssignmentOp());
  98
  99     switch (Op) {
 100       default:
 101         llvm_unreachable("Invalid opcode for compound assignment.");
 102       case BO_MulAssign: Op = BO_Mul; break;
 103       case BO_DivAssign: Op = BO_Div; break;
 104       case BO_RemAssign: Op = BO_Rem; break;
 105       case BO_AddAssign: Op = BO_Add; break;
 106       case BO_SubAssign: Op = BO_Sub; break;
 107       case BO_ShlAssign: Op = BO_Shl; break;
 108       case BO_ShrAssign: Op = BO_Shr; break;
 109       case BO_AndAssign: Op = BO_And; break;
 110       case BO_XorAssign: Op = BO_Xor; break;
 111       case BO_OrAssign:  Op = BO_Or;  break;
 112     }
 113
 114     // Perform a load (the LHS).  This performs the checks for
 115     // null dereferences, and so on.
 116     ExplodedNodeSet Tmp;
 117     SVal location = LeftV;
 118     evalLoad(Tmp, B, LHS, *it, state, location);
 119
 120     for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E;
 121          ++I) {
 122
 123       state = (*I)->getState();
 124       const LocationContext *LCtx = (*I)->getLocationContext();
 125       SVal V = state->getSVal(LHS, LCtx);
 126
 127       // Get the computation type.
 128       QualType CTy =
 129         cast<CompoundAssignOperator>(B)->getComputationResultType();
 130       CTy = getContext().getCanonicalType(CTy);
 131
 132       QualType CLHSTy =
 133         cast<CompoundAssignOperator>(B)->getComputationLHSType();
 134       CLHSTy = getContext().getCanonicalType(CLHSTy);
 135
 136       QualType LTy = getContext().getCanonicalType(LHS->getType());
 137
 138       // Promote LHS.
 139       V = svalBuilder.evalCast(V, CLHSTy, LTy);
 140
 141       // Compute the result of the operation.
 142       SVal Result = svalBuilder.evalCast(evalBinOp(state, Op, V, RightV, CTy),
 143                                          B->getType(), CTy);
 144
 145       // EXPERIMENTAL: "Conjured" symbols.
 146       // FIXME: Handle structs.
 147
 148       SVal LHSVal;
 149
 150       if (Result.isUnknown()) {
 151         // The symbolic value is actually for the type of the left-hand side
 152         // expression, not the computation type, as this is the value the
 153         // LValue on the LHS will bind to.
 154         LHSVal = svalBuilder.conjureSymbolVal(0, B->getRHS(), LCtx, LTy,
 155                                               currBldrCtx->blockCount());
 156         // However, we need to convert the symbol to the computation type.
 157         Result = svalBuilder.evalCast(LHSVal, CTy, LTy);
 158       }
 159       else {
 160         // The left-hand side may bind to a different value then the
 161         // computation type.
 162         LHSVal = svalBuilder.evalCast(Result, LTy, CTy);
 163       }
 164
 165       // In C++, assignment and compound assignment operators return an
 166       // lvalue.
 167       if (B->isGLValue())
 168         state = state->BindExpr(B, LCtx, location);
 169       else
 170         state = state->BindExpr(B, LCtx, Result);
 171
 172       evalStore(Tmp2, B, LHS, *I, state, location, LHSVal);
 173     }
 174   }
 175
 176   // FIXME: postvisits eventually go in ::Visit()
 177   getCheckerManager().runCheckersForPostStmt(Dst, Tmp2, B, *this);
 178 }
 179
 180 void ExprEngine::VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
 181                                 ExplodedNodeSet &Dst) {
 182
 183   CanQualType T = getContext().getCanonicalType(BE->getType());
 184
 185   // Get the value of the block itself.
 186   SVal V = svalBuilder.getBlockPointer(BE->getBlockDecl(), T,
 187                                        Pred->getLocationContext(),
 188                                        currBldrCtx->blockCount());
 189
 190   ProgramStateRef State = Pred->getState();
 191
 192   // If we created a new MemRegion for the block, we should explicitly bind
 193   // the captured variables.
 194   if (const BlockDataRegion *BDR =
 195       dyn_cast_or_null<BlockDataRegion>(V.getAsRegion())) {
 196
 197     BlockDataRegion::referenced_vars_iterator I = BDR->referenced_vars_begin(),
 198                                               E = BDR->referenced_vars_end();
 199
 200     for (; I != E; ++I) {
 201       const MemRegion *capturedR = I.getCapturedRegion();
 202       const MemRegion *originalR = I.getOriginalRegion();
 203       if (capturedR != originalR) {
 204         SVal originalV = State->getSVal(loc::MemRegionVal(originalR));
 205         State = State->bindLoc(loc::MemRegionVal(capturedR), originalV);
 206       }
 207     }
 208   }
 209
 210   ExplodedNodeSet Tmp;
 211   StmtNodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
 212   Bldr.generateNode(BE, Pred,
 213                     State->BindExpr(BE, Pred->getLocationContext(), V),
 214                     0, ProgramPoint::PostLValueKind);
 215
 216   // FIXME: Move all post/pre visits to ::Visit().
 217   getCheckerManager().runCheckersForPostStmt(Dst, Tmp, BE, *this);
 218 }
 219
 220 void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
 221                            ExplodedNode *Pred, ExplodedNodeSet &Dst) {
 222
 223   ExplodedNodeSet dstPreStmt;
 224   getCheckerManager().runCheckersForPreStmt(dstPreStmt, Pred, CastE, *this);
 225
 226   if (CastE->getCastKind() == CK_LValueToRValue) {
 227     for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end();
 228          I!=E; ++I) {
 229       ExplodedNode *subExprNode = *I;
 230       ProgramStateRef state = subExprNode->getState();
 231       const LocationContext *LCtx = subExprNode->getLocationContext();
 232       evalLoad(Dst, CastE, CastE, subExprNode, state, state->getSVal(Ex, LCtx));
 233     }
 234     return;
 235   }
 236
 237   // All other casts.
 238   QualType T = CastE->getType();
 239   QualType ExTy = Ex->getType();
 240
 241   if (const ExplicitCastExpr *ExCast=dyn_cast_or_null<ExplicitCastExpr>(CastE))
 242     T = ExCast->getTypeAsWritten();
 243
 244   StmtNodeBuilder Bldr(dstPreStmt, Dst, *currBldrCtx);
 245   for (ExplodedNodeSet::iterator I = dstPreStmt.begin(), E = dstPreStmt.end();
 246        I != E; ++I) {
 247
 248     Pred = *I;
 249     ProgramStateRef state = Pred->getState();
 250     const LocationContext *LCtx = Pred->getLocationContext();
 251
 252     switch (CastE->getCastKind()) {
 253       case CK_LValueToRValue:
 254         llvm_unreachable("LValueToRValue casts handled earlier.");
 255       case CK_ToVoid:
 256         continue;
 257         // The analyzer doesn't do anything special with these casts,
 258         // since it understands retain/release semantics already.
 259       case CK_ARCProduceObject:
 260       case CK_ARCConsumeObject:
 261       case CK_ARCReclaimReturnedObject:
 262       case CK_ARCExtendBlockObject: // Fall-through.
 263       case CK_CopyAndAutoreleaseBlockObject:
 264         // The analyser can ignore atomic casts for now, although some future
 265         // checkers may want to make certain that you're not modifying the same
 266         // value through atomic and nonatomic pointers.
 267       case CK_AtomicToNonAtomic:
 268       case CK_NonAtomicToAtomic:
 269         // True no-ops.
 270       case CK_NoOp:
 271       case CK_ConstructorConversion:
 272       case CK_UserDefinedConversion:
 273       case CK_FunctionToPointerDecay:
 274       case CK_BuiltinFnToFnPtr: {
 275         // Copy the SVal of Ex to CastE.
 276         ProgramStateRef state = Pred->getState();
 277         const LocationContext *LCtx = Pred->getLocationContext();
 278         SVal V = state->getSVal(Ex, LCtx);
 279         state = state->BindExpr(CastE, LCtx, V);
 280         Bldr.generateNode(CastE, Pred, state);
 281         continue;
 282       }
 283       case CK_MemberPointerToBoolean:
 284         // FIXME: For now, member pointers are represented by void *.
 285         // FALLTHROUGH
 286       case CK_Dependent:
 287       case CK_ArrayToPointerDecay:
 288       case CK_BitCast:
 289       case CK_IntegralCast:
 290       case CK_NullToPointer:
 291       case CK_IntegralToPointer:
 292       case CK_PointerToIntegral:
 293       case CK_PointerToBoolean:
 294       case CK_IntegralToBoolean:
 295       case CK_IntegralToFloating:
 296       case CK_FloatingToIntegral:
 297       case CK_FloatingToBoolean:
 298       case CK_FloatingCast:
 299       case CK_FloatingRealToComplex:
 300       case CK_FloatingComplexToReal:
 301       case CK_FloatingComplexToBoolean:
 302       case CK_FloatingComplexCast:
 303       case CK_FloatingComplexToIntegralComplex:
 304       case CK_IntegralRealToComplex:
 305       case CK_IntegralComplexToReal:
 306       case CK_IntegralComplexToBoolean:
 307       case CK_IntegralComplexCast:
 308       case CK_IntegralComplexToFloatingComplex:
 309       case CK_CPointerToObjCPointerCast:
 310       case CK_BlockPointerToObjCPointerCast:
 311       case CK_AnyPointerToBlockPointerCast:
 312       case CK_ObjCObjectLValueCast:
 313       case CK_ZeroToOCLEvent:
 314       case CK_LValueBitCast: {
 315         // Delegate to SValBuilder to process.
 316         SVal V = state->getSVal(Ex, LCtx);
 317         V = svalBuilder.evalCast(V, T, ExTy);
 318         state = state->BindExpr(CastE, LCtx, V);
 319         Bldr.generateNode(CastE, Pred, state);
 320         continue;
 321       }
 322       case CK_DerivedToBase:
 323       case CK_UncheckedDerivedToBase: {
 324         // For DerivedToBase cast, delegate to the store manager.
 325         SVal val = state->getSVal(Ex, LCtx);
 326         val = getStoreManager().evalDerivedToBase(val, CastE);
 327         state = state->BindExpr(CastE, LCtx, val);
 328         Bldr.generateNode(CastE, Pred, state);
 329         continue;
 330       }
 331       // Handle C++ dyn_cast.
 332       case CK_Dynamic: {
 333         SVal val = state->getSVal(Ex, LCtx);
 334
 335         // Compute the type of the result.
 336         QualType resultType = CastE->getType();
 337         if (CastE->isGLValue())
 338           resultType = getContext().getPointerType(resultType);
 339
 340         bool Failed = false;
 341
 342         // Check if the value being cast evaluates to 0.
 343         if (val.isZeroConstant())
 344           Failed = true;
 345         // Else, evaluate the cast.
 346         else
 347           val = getStoreManager().evalDynamicCast(val, T, Failed);
 348
 349         if (Failed) {
 350           if (T->isReferenceType()) {
 351             // A bad_cast exception is thrown if input value is a reference.
 352             // Currently, we model this, by generating a sink.
 353             Bldr.generateSink(CastE, Pred, state);
 354             continue;
 355           } else {
 356             // If the cast fails on a pointer, bind to 0.
 357             state = state->BindExpr(CastE, LCtx, svalBuilder.makeNull());
 358           }
 359         } else {
 360           // If we don't know if the cast succeeded, conjure a new symbol.
 361           if (val.isUnknown()) {
 362             DefinedOrUnknownSVal NewSym =
 363               svalBuilder.conjureSymbolVal(0, CastE, LCtx, resultType,
 364                                            currBldrCtx->blockCount());
 365             state = state->BindExpr(CastE, LCtx, NewSym);
 366           } else
 367             // Else, bind to the derived region value.
 368             state = state->BindExpr(CastE, LCtx, val);
 369         }
 370         Bldr.generateNode(CastE, Pred, state);
 371         continue;
 372       }
 373       case CK_NullToMemberPointer: {
 374         // FIXME: For now, member pointers are represented by void *.
 375         SVal V = svalBuilder.makeNull();
 376         state = state->BindExpr(CastE, LCtx, V);
 377         Bldr.generateNode(CastE, Pred, state);
 378         continue;
 379       }
 380       // Various C++ casts that are not handled yet.
 381       case CK_ToUnion:
 382       case CK_BaseToDerived:
 383       case CK_BaseToDerivedMemberPointer:
 384       case CK_DerivedToBaseMemberPointer:
 385       case CK_ReinterpretMemberPointer:
 386       case CK_VectorSplat: {
 387         // Recover some path-sensitivty by conjuring a new value.
 388         QualType resultType = CastE->getType();
 389         if (CastE->isGLValue())
 390           resultType = getContext().getPointerType(resultType);
 391         SVal result = svalBuilder.conjureSymbolVal(0, CastE, LCtx,
 392                                                    resultType,
 393                                                    currBldrCtx->blockCount());
 394         state = state->BindExpr(CastE, LCtx, result);
 395         Bldr.generateNode(CastE, Pred, state);
 396         continue;
 397       }
 398     }
 399   }
 400 }
 401
 402 void ExprEngine::VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
 403                                           ExplodedNode *Pred,
 404                                           ExplodedNodeSet &Dst) {
 405   StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
 406
 407   ProgramStateRef State = Pred->getState();
 408   const LocationContext *LCtx = Pred->getLocationContext();
 409
 410   const Expr *Init = CL->getInitializer();
 411   SVal V = State->getSVal(CL->getInitializer(), LCtx);
 412
 413   if (isa<CXXConstructExpr>(Init)) {
 414     // No work needed. Just pass the value up to this expression.
 415   } else {
 416     assert(isa<InitListExpr>(Init));
 417     Loc CLLoc = State->getLValue(CL, LCtx);
 418     State = State->bindLoc(CLLoc, V);
 419
 420     // Compound literal expressions are a GNU extension in C++.
 421     // Unlike in C, where CLs are lvalues, in C++ CLs are prvalues,
 422     // and like temporary objects created by the functional notation T()
 423     // CLs are destroyed at the end of the containing full-expression.
 424     // HOWEVER, an rvalue of array type is not something the analyzer can
 425     // reason about, since we expect all regions to be wrapped in Locs.
 426     // So we treat array CLs as lvalues as well, knowing that they will decay
 427     // to pointers as soon as they are used.
 428     if (CL->isGLValue() || CL->getType()->isArrayType())
 429       V = CLLoc;
 430   }
 431
 432   B.generateNode(CL, Pred, State->BindExpr(CL, LCtx, V));
 433 }
 434
 435 void ExprEngine::VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
 436                                ExplodedNodeSet &Dst) {
 437   // Assumption: The CFG has one DeclStmt per Decl.
 438   const VarDecl *VD = dyn_cast_or_null<VarDecl>(*DS->decl_begin());
 439
 440   if (!VD) {
 441     //TODO:AZ: remove explicit insertion after refactoring is done.
 442     Dst.insert(Pred);
 443     return;
 444   }
 445
 446   // FIXME: all pre/post visits should eventually be handled by ::Visit().
 447   ExplodedNodeSet dstPreVisit;
 448   getCheckerManager().runCheckersForPreStmt(dstPreVisit, Pred, DS, *this);
 449
 450   ExplodedNodeSet dstEvaluated;
 451   StmtNodeBuilder B(dstPreVisit, dstEvaluated, *currBldrCtx);
 452   for (ExplodedNodeSet::iterator I = dstPreVisit.begin(), E = dstPreVisit.end();
 453        I!=E; ++I) {
 454     ExplodedNode *N = *I;
 455     ProgramStateRef state = N->getState();
 456     const LocationContext *LC = N->getLocationContext();
 457
 458     // Decls without InitExpr are not initialized explicitly.
 459     if (const Expr *InitEx = VD->getInit()) {
 460
 461       // Note in the state that the initialization has occurred.
 462       ExplodedNode *UpdatedN = N;
 463       SVal InitVal = state->getSVal(InitEx, LC);
 464
 465       if (isa<CXXConstructExpr>(InitEx->IgnoreImplicit())) {
 466         // We constructed the object directly in the variable.
 467         // No need to bind anything.
 468         B.generateNode(DS, UpdatedN, state);
 469       } else {
 470         // We bound the temp obj region to the CXXConstructExpr. Now recover
 471         // the lazy compound value when the variable is not a reference.
 472         if (AMgr.getLangOpts().CPlusPlus && VD->getType()->isRecordType() &&
 473             !VD->getType()->isReferenceType()) {
 474           if (Optional<loc::MemRegionVal> M =
 475                   InitVal.getAs<loc::MemRegionVal>()) {
 476             InitVal = state->getSVal(M->getRegion());
 477             assert(InitVal.getAs<nonloc::LazyCompoundVal>());
 478           }
 479         }
 480
 481         // Recover some path-sensitivity if a scalar value evaluated to
 482         // UnknownVal.
 483         if (InitVal.isUnknown()) {
 484           QualType Ty = InitEx->getType();
 485           if (InitEx->isGLValue()) {
 486             Ty = getContext().getPointerType(Ty);
 487           }
 488
 489           InitVal = svalBuilder.conjureSymbolVal(0, InitEx, LC, Ty,
 490                                                  currBldrCtx->blockCount());
 491         }
 492
 493
 494         B.takeNodes(UpdatedN);
 495         ExplodedNodeSet Dst2;
 496         evalBind(Dst2, DS, UpdatedN, state->getLValue(VD, LC), InitVal, true);
 497         B.addNodes(Dst2);
 498       }
 499     }
 500     else {
 501       B.generateNode(DS, N, state);
 502     }
 503   }
 504
 505   getCheckerManager().runCheckersForPostStmt(Dst, B.getResults(), DS, *this);
 506 }
 507
 508 void ExprEngine::VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
 509                                   ExplodedNodeSet &Dst) {
 510   assert(B->getOpcode() == BO_LAnd ||
 511          B->getOpcode() == BO_LOr);
 512
 513   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
 514   ProgramStateRef state = Pred->getState();
 515
 516   ExplodedNode *N = Pred;
 517   while (!N->getLocation().getAs<BlockEntrance>()) {
 518     ProgramPoint P = N->getLocation();
 519     assert(P.getAs<PreStmt>()|| P.getAs<PreStmtPurgeDeadSymbols>());
 520     (void) P;
 521     assert(N->pred_size() == 1);
 522     N = *N->pred_begin();
 523   }
 524   assert(N->pred_size() == 1);
 525   N = *N->pred_begin();
 526   BlockEdge BE = N->getLocation().castAs<BlockEdge>();
 527   SVal X;
 528
 529   // Determine the value of the expression by introspecting how we
 530   // got this location in the CFG.  This requires looking at the previous
 531   // block we were in and what kind of control-flow transfer was involved.
 532   const CFGBlock *SrcBlock = BE.getSrc();
 533   // The only terminator (if there is one) that makes sense is a logical op.
 534   CFGTerminator T = SrcBlock->getTerminator();
 535   if (const BinaryOperator *Term = cast_or_null<BinaryOperator>(T.getStmt())) {
 536     (void) Term;
 537     assert(Term->isLogicalOp());
 538     assert(SrcBlock->succ_size() == 2);
 539     // Did we take the true or false branch?
 540     unsigned constant = (*SrcBlock->succ_begin() == BE.getDst()) ? 1 : 0;
 541     X = svalBuilder.makeIntVal(constant, B->getType());
 542   }
 543   else {
 544     // If there is no terminator, by construction the last statement
 545     // in SrcBlock is the value of the enclosing expression.
 546     // However, we still need to constrain that value to be 0 or 1.
 547     assert(!SrcBlock->empty());
 548     CFGStmt Elem = SrcBlock->rbegin()->castAs<CFGStmt>();
 549     const Expr *RHS = cast<Expr>(Elem.getStmt());
 550     SVal RHSVal = N->getState()->getSVal(RHS, Pred->getLocationContext());
 551
 552     if (RHSVal.isUndef()) {
 553       X = RHSVal;
 554     } else {
 555       DefinedOrUnknownSVal DefinedRHS = RHSVal.castAs<DefinedOrUnknownSVal>();
 556       ProgramStateRef StTrue, StFalse;
 557       llvm::tie(StTrue, StFalse) = N->getState()->assume(DefinedRHS);
 558       if (StTrue) {
 559         if (StFalse) {
 560           // We can't constrain the value to 0 or 1.
 561           // The best we can do is a cast.
 562           X = getSValBuilder().evalCast(RHSVal, B->getType(), RHS->getType());
 563         } else {
 564           // The value is known to be true.
 565           X = getSValBuilder().makeIntVal(1, B->getType());
 566         }
 567       } else {
 568         // The value is known to be false.
 569         assert(StFalse && "Infeasible path!");
 570         X = getSValBuilder().makeIntVal(0, B->getType());
 571       }
 572     }
 573   }
 574   Bldr.generateNode(B, Pred, state->BindExpr(B, Pred->getLocationContext(), X));
 575 }
 576
 577 void ExprEngine::VisitInitListExpr(const InitListExpr *IE,
 578                                    ExplodedNode *Pred,
 579                                    ExplodedNodeSet &Dst) {
 580   StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
 581
 582   ProgramStateRef state = Pred->getState();
 583   const LocationContext *LCtx = Pred->getLocationContext();
 584   QualType T = getContext().getCanonicalType(IE->getType());
 585   unsigned NumInitElements = IE->getNumInits();
 586
 587   if (!IE->isGLValue() &&
 588       (T->isArrayType() || T->isRecordType() || T->isVectorType() ||
 589        T->isAnyComplexType())) {
 590     llvm::ImmutableList<SVal> vals = getBasicVals().getEmptySValList();
 591
 592     // Handle base case where the initializer has no elements.
 593     // e.g: static int* myArray[] = {};
 594     if (NumInitElements == 0) {
 595       SVal V = svalBuilder.makeCompoundVal(T, vals);
 596       B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V));
 597       return;
 598     }
 599
 600     for (InitListExpr::const_reverse_iterator it = IE->rbegin(),
 601          ei = IE->rend(); it != ei; ++it) {
 602       SVal V = state->getSVal(cast<Expr>(*it), LCtx);
 603       vals = getBasicVals().consVals(V, vals);
 604     }
 605
 606     B.generateNode(IE, Pred,
 607                    state->BindExpr(IE, LCtx,
 608                                    svalBuilder.makeCompoundVal(T, vals)));
 609     return;
 610   }
 611
 612   // Handle scalars: int{5} and int{} and GLvalues.
 613   // Note, if the InitListExpr is a GLvalue, it means that there is an address
 614   // representing it, so it must have a single init element.
 615   assert(NumInitElements <= 1);
 616
 617   SVal V;
 618   if (NumInitElements == 0)
 619     V = getSValBuilder().makeZeroVal(T);
 620   else
 621     V = state->getSVal(IE->getInit(0), LCtx);
 622
 623   B.generateNode(IE, Pred, state->BindExpr(IE, LCtx, V));
 624 }
 625
 626 void ExprEngine::VisitGuardedExpr(const Expr *Ex,
 627                                   const Expr *L,
 628                                   const Expr *R,
 629                                   ExplodedNode *Pred,
 630                                   ExplodedNodeSet &Dst) {
 631   assert(L && R);
 632
 633   StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
 634   ProgramStateRef state = Pred->getState();
 635   const LocationContext *LCtx = Pred->getLocationContext();
 636   const CFGBlock *SrcBlock = 0;
 637
 638   // Find the predecessor block.
 639   ProgramStateRef SrcState = state;
 640   for (const ExplodedNode *N = Pred ; N ; N = *N->pred_begin()) {
 641     ProgramPoint PP = N->getLocation();
 642     if (PP.getAs<PreStmtPurgeDeadSymbols>() || PP.getAs<BlockEntrance>()) {
 643       assert(N->pred_size() == 1);
 644       continue;
 645     }
 646     SrcBlock = PP.castAs<BlockEdge>().getSrc();
 647     SrcState = N->getState();
 648     break;
 649   }
 650
 651   assert(SrcBlock && "missing function entry");
 652
 653   // Find the last expression in the predecessor block.  That is the
 654   // expression that is used for the value of the ternary expression.
 655   bool hasValue = false;
 656   SVal V;
 657
 658   for (CFGBlock::const_reverse_iterator I = SrcBlock->rbegin(),
 659                                         E = SrcBlock->rend(); I != E; ++I) {
 660     CFGElement CE = *I;
 661     if (Optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {
 662       const Expr *ValEx = cast<Expr>(CS->getStmt());
 663       ValEx = ValEx->IgnoreParens();
 664
 665       // For GNU extension '?:' operator, the left hand side will be an
 666       // OpaqueValueExpr, so get the underlying expression.
 667       if (const OpaqueValueExpr *OpaqueEx = dyn_cast<OpaqueValueExpr>(L))
 668         L = OpaqueEx->getSourceExpr();
 669
 670       // If the last expression in the predecessor block matches true or false
 671       // subexpression, get its the value.
 672       if (ValEx == L->IgnoreParens() || ValEx == R->IgnoreParens()) {
 673         hasValue = true;
 674         V = SrcState->getSVal(ValEx, LCtx);
 675       }
 676       break;
 677     }
 678   }
 679
 680   if (!hasValue)
 681     V = svalBuilder.conjureSymbolVal(0, Ex, LCtx, currBldrCtx->blockCount());
 682
 683   // Generate a new node with the binding from the appropriate path.
 684   B.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V, true));
 685 }
 686
 687 void ExprEngine::
 688 VisitOffsetOfExpr(const OffsetOfExpr *OOE,
 689                   ExplodedNode *Pred, ExplodedNodeSet &Dst) {
 690   StmtNodeBuilder B(Pred, Dst, *currBldrCtx);
 691   APSInt IV;
 692   if (OOE->EvaluateAsInt(IV, getContext())) {
 693     assert(IV.getBitWidth() == getContext().getTypeSize(OOE->getType()));
 694     assert(OOE->getType()->isBuiltinType());
 695     assert(OOE->getType()->getAs<BuiltinType>()->isInteger());
 696     assert(IV.isSigned() == OOE->getType()->isSignedIntegerType());
 697     SVal X = svalBuilder.makeIntVal(IV);
 698     B.generateNode(OOE, Pred,
 699                    Pred->getState()->BindExpr(OOE, Pred->getLocationContext(),
 700                                               X));
 701   }
 702   // FIXME: Handle the case where __builtin_offsetof is not a constant.
 703 }
 704
 705
 706 void ExprEngine::
 707 VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
 708                               ExplodedNode *Pred,
 709                               ExplodedNodeSet &Dst) {
 710   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
 711
 712   QualType T = Ex->getTypeOfArgument();
 713
 714   if (Ex->getKind() == UETT_SizeOf) {
 715     if (!T->isIncompleteType() && !T->isConstantSizeType()) {
 716       assert(T->isVariableArrayType() && "Unknown non-constant-sized type.");
 717
 718       // FIXME: Add support for VLA type arguments and VLA expressions.
 719       // When that happens, we should probably refactor VLASizeChecker's code.
 720       return;
 721     }
 722     else if (T->getAs<ObjCObjectType>()) {
 723       // Some code tries to take the sizeof an ObjCObjectType, relying that
 724       // the compiler has laid out its representation.  Just report Unknown
 725       // for these.
 726       return;
 727     }
 728   }
 729
 730   APSInt Value = Ex->EvaluateKnownConstInt(getContext());
 731   CharUnits amt = CharUnits::fromQuantity(Value.getZExtValue());
 732
 733   ProgramStateRef state = Pred->getState();
 734   state = state->BindExpr(Ex, Pred->getLocationContext(),
 735                           svalBuilder.makeIntVal(amt.getQuantity(),
 736                                                      Ex->getType()));
 737   Bldr.generateNode(Ex, Pred, state);
 738 }
 739
 740 void ExprEngine::VisitUnaryOperator(const UnaryOperator* U,
 741                                     ExplodedNode *Pred,
 742                                     ExplodedNodeSet &Dst) {
 743   // FIXME: Prechecks eventually go in ::Visit().
 744   ExplodedNodeSet CheckedSet;
 745   getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, U, *this);
 746
 747   ExplodedNodeSet EvalSet;
 748   StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
 749
 750   for (ExplodedNodeSet::iterator I = CheckedSet.begin(), E = CheckedSet.end();
 751        I != E; ++I) {
 752     switch (U->getOpcode()) {
 753     default: {
 754       Bldr.takeNodes(*I);
 755       ExplodedNodeSet Tmp;
 756       VisitIncrementDecrementOperator(U, *I, Tmp);
 757       Bldr.addNodes(Tmp);
 758       break;
 759     }
 760     case UO_Real: {
 761       const Expr *Ex = U->getSubExpr()->IgnoreParens();
 762
 763       // FIXME: We don't have complex SValues yet.
 764       if (Ex->getType()->isAnyComplexType()) {
 765         // Just report "Unknown."
 766         break;
 767       }
 768
 769       // For all other types, UO_Real is an identity operation.
 770       assert (U->getType() == Ex->getType());
 771       ProgramStateRef state = (*I)->getState();
 772       const LocationContext *LCtx = (*I)->getLocationContext();
 773       Bldr.generateNode(U, *I, state->BindExpr(U, LCtx,
 774                                                state->getSVal(Ex, LCtx)));
 775       break;
 776     }
 777
 778     case UO_Imag: {
 779       const Expr *Ex = U->getSubExpr()->IgnoreParens();
 780       // FIXME: We don't have complex SValues yet.
 781       if (Ex->getType()->isAnyComplexType()) {
 782         // Just report "Unknown."
 783         break;
 784       }
 785       // For all other types, UO_Imag returns 0.
 786       ProgramStateRef state = (*I)->getState();
 787       const LocationContext *LCtx = (*I)->getLocationContext();
 788       SVal X = svalBuilder.makeZeroVal(Ex->getType());
 789       Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, X));
 790       break;
 791     }
 792
 793     case UO_Plus:
 794       assert(!U->isGLValue());
 795       // FALL-THROUGH.
 796     case UO_Deref:
 797     case UO_AddrOf:
 798     case UO_Extension: {
 799       // FIXME: We can probably just have some magic in Environment::getSVal()
 800       // that propagates values, instead of creating a new node here.
 801       //
 802       // Unary "+" is a no-op, similar to a parentheses.  We still have places
 803       // where it may be a block-level expression, so we need to
 804       // generate an extra node that just propagates the value of the
 805       // subexpression.
 806       const Expr *Ex = U->getSubExpr()->IgnoreParens();
 807       ProgramStateRef state = (*I)->getState();
 808       const LocationContext *LCtx = (*I)->getLocationContext();
 809       Bldr.generateNode(U, *I, state->BindExpr(U, LCtx,
 810                                                state->getSVal(Ex, LCtx)));
 811       break;
 812     }
 813
 814     case UO_LNot:
 815     case UO_Minus:
 816     case UO_Not: {
 817       assert (!U->isGLValue());
 818       const Expr *Ex = U->getSubExpr()->IgnoreParens();
 819       ProgramStateRef state = (*I)->getState();
 820       const LocationContext *LCtx = (*I)->getLocationContext();
 821
 822       // Get the value of the subexpression.
 823       SVal V = state->getSVal(Ex, LCtx);
 824
 825       if (V.isUnknownOrUndef()) {
 826         Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V));
 827         break;
 828       }
 829
 830       switch (U->getOpcode()) {
 831         default:
 832           llvm_unreachable("Invalid Opcode.");
 833         case UO_Not:
 834           // FIXME: Do we need to handle promotions?
 835           state = state->BindExpr(U, LCtx, evalComplement(V.castAs<NonLoc>()));
 836           break;
 837         case UO_Minus:
 838           // FIXME: Do we need to handle promotions?
 839           state = state->BindExpr(U, LCtx, evalMinus(V.castAs<NonLoc>()));
 840           break;
 841         case UO_LNot:
 842           // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
 843           //
 844           //  Note: technically we do "E == 0", but this is the same in the
 845           //    transfer functions as "0 == E".
 846           SVal Result;
 847           if (Optional<Loc> LV = V.getAs<Loc>()) {
 848             Loc X = svalBuilder.makeNull();
 849             Result = evalBinOp(state, BO_EQ, *LV, X, U->getType());
 850           }
 851           else if (Ex->getType()->isFloatingType()) {
 852             // FIXME: handle floating point types.
 853             Result = UnknownVal();
 854           } else {
 855             nonloc::ConcreteInt X(getBasicVals().getValue(0, Ex->getType()));
 856             Result = evalBinOp(state, BO_EQ, V.castAs<NonLoc>(), X,
 857                                U->getType());
 858           }
 859
 860           state = state->BindExpr(U, LCtx, Result);
 861           break;
 862       }
 863       Bldr.generateNode(U, *I, state);
 864       break;
 865     }
 866     }
 867   }
 868
 869   getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, U, *this);
 870 }
 871
 872 void ExprEngine::VisitIncrementDecrementOperator(const UnaryOperator* U,
 873                                                  ExplodedNode *Pred,
 874                                                  ExplodedNodeSet &Dst) {
 875   // Handle ++ and -- (both pre- and post-increment).
 876   assert (U->isIncrementDecrementOp());
 877   const Expr *Ex = U->getSubExpr()->IgnoreParens();
 878
 879   const LocationContext *LCtx = Pred->getLocationContext();
 880   ProgramStateRef state = Pred->getState();
 881   SVal loc = state->getSVal(Ex, LCtx);
 882
 883   // Perform a load.
 884   ExplodedNodeSet Tmp;
 885   evalLoad(Tmp, U, Ex, Pred, state, loc);
 886
 887   ExplodedNodeSet Dst2;
 888   StmtNodeBuilder Bldr(Tmp, Dst2, *currBldrCtx);
 889   for (ExplodedNodeSet::iterator I=Tmp.begin(), E=Tmp.end();I!=E;++I) {
 890
 891     state = (*I)->getState();
 892     assert(LCtx == (*I)->getLocationContext());
 893     SVal V2_untested = state->getSVal(Ex, LCtx);
 894
 895     // Propagate unknown and undefined values.
 896     if (V2_untested.isUnknownOrUndef()) {
 897       Bldr.generateNode(U, *I, state->BindExpr(U, LCtx, V2_untested));
 898       continue;
 899     }
 900     DefinedSVal V2 = V2_untested.castAs<DefinedSVal>();
 901
 902     // Handle all other values.
 903     BinaryOperator::Opcode Op = U->isIncrementOp() ? BO_Add : BO_Sub;
 904
 905     // If the UnaryOperator has non-location type, use its type to create the
 906     // constant value. If the UnaryOperator has location type, create the
 907     // constant with int type and pointer width.
 908     SVal RHS;
 909
 910     if (U->getType()->isAnyPointerType())
 911       RHS = svalBuilder.makeArrayIndex(1);
 912     else if (U->getType()->isIntegralOrEnumerationType())
 913       RHS = svalBuilder.makeIntVal(1, U->getType());
 914     else
 915       RHS = UnknownVal();
 916
 917     SVal Result = evalBinOp(state, Op, V2, RHS, U->getType());
 918
 919     // Conjure a new symbol if necessary to recover precision.
 920     if (Result.isUnknown()){
 921       DefinedOrUnknownSVal SymVal =
 922         svalBuilder.conjureSymbolVal(0, Ex, LCtx, currBldrCtx->blockCount());
 923       Result = SymVal;
 924
 925       // If the value is a location, ++/-- should always preserve
 926       // non-nullness.  Check if the original value was non-null, and if so
 927       // propagate that constraint.
 928       if (Loc::isLocType(U->getType())) {
 929         DefinedOrUnknownSVal Constraint =
 930         svalBuilder.evalEQ(state, V2,svalBuilder.makeZeroVal(U->getType()));
 931
 932         if (!state->assume(Constraint, true)) {
 933           // It isn't feasible for the original value to be null.
 934           // Propagate this constraint.
 935           Constraint = svalBuilder.evalEQ(state, SymVal,
 936                                        svalBuilder.makeZeroVal(U->getType()));
 937
 938
 939           state = state->assume(Constraint, false);
 940           assert(state);
 941         }
 942       }
 943     }
 944
 945     // Since the lvalue-to-rvalue conversion is explicit in the AST,
 946     // we bind an l-value if the operator is prefix and an lvalue (in C++).
 947     if (U->isGLValue())
 948       state = state->BindExpr(U, LCtx, loc);
 949     else
 950       state = state->BindExpr(U, LCtx, U->isPostfix() ? V2 : Result);
 951
 952     // Perform the store.
 953     Bldr.takeNodes(*I);
 954     ExplodedNodeSet Dst3;
 955     evalStore(Dst3, U, U, *I, state, loc, Result);
 956     Bldr.addNodes(Dst3);
 957   }
 958   Dst.insert(Dst2);
 959 }