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