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