Home | History | Annotate | Download | only in Core 
      1 //===- ExprEngineCXX.cpp - ExprEngine support for C++ -----------*- 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 the C++ expression evaluation engine.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
     15 #include "clang/AST/DeclCXX.h"
     16 #include "clang/AST/StmtCXX.h"
     17 #include "clang/Basic/PrettyStackTrace.h"
     18 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
     19 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
     20 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
     21 
     22 using namespace clang;
     23 using namespace ento;
     24 
     25 void ExprEngine::CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
     26                                           ExplodedNode *Pred,
     27                                           ExplodedNodeSet &Dst) {
     28   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
     29   const Expr *tempExpr = ME->GetTemporaryExpr()->IgnoreParens();
     30   ProgramStateRef state = Pred->getState();
     31   const LocationContext *LCtx = Pred->getLocationContext();
     32 
     33   state = createTemporaryRegionIfNeeded(state, LCtx, tempExpr, ME);
     34   Bldr.generateNode(ME, Pred, state);
     35 }
     36 
     37 // FIXME: This is the sort of code that should eventually live in a Core
     38 // checker rather than as a special case in ExprEngine.
     39 void ExprEngine::performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred,
     40                                     const CallEvent &Call) {
     41   SVal ThisVal;
     42   bool AlwaysReturnsLValue;
     43   if (const CXXConstructorCall *Ctor = dyn_cast<CXXConstructorCall>(&Call)) {
     44     assert(Ctor->getDecl()->isTrivial());
     45     assert(Ctor->getDecl()->isCopyOrMoveConstructor());
     46     ThisVal = Ctor->getCXXThisVal();
     47     AlwaysReturnsLValue = false;
     48   } else {
     49     assert(cast<CXXMethodDecl>(Call.getDecl())->isTrivial());
     50     assert(cast<CXXMethodDecl>(Call.getDecl())->getOverloadedOperator() ==
     51            OO_Equal);
     52     ThisVal = cast<CXXInstanceCall>(Call).getCXXThisVal();
     53     AlwaysReturnsLValue = true;
     54   }
     55 
     56   const LocationContext *LCtx = Pred->getLocationContext();
     57 
     58   ExplodedNodeSet Dst;
     59   Bldr.takeNodes(Pred);
     60 
     61   SVal V = Call.getArgSVal(0);
     62 
     63   // If the value being copied is not unknown, load from its location to get
     64   // an aggregate rvalue.
     65   if (Optional<Loc> L = V.getAs<Loc>())
     66     V = Pred->getState()->getSVal(*L);
     67   else
     68     assert(V.isUnknown());
     69 
     70   const Expr *CallExpr = Call.getOriginExpr();
     71   evalBind(Dst, CallExpr, Pred, ThisVal, V, true);
     72 
     73   PostStmt PS(CallExpr, LCtx);
     74   for (ExplodedNodeSet::iterator I = Dst.begin(), E = Dst.end();
     75        I != E; ++I) {
     76     ProgramStateRef State = (*I)->getState();
     77     if (AlwaysReturnsLValue)
     78       State = State->BindExpr(CallExpr, LCtx, ThisVal);
     79     else
     80       State = bindReturnValue(Call, LCtx, State);
     81     Bldr.generateNode(PS, State, *I);
     82   }
     83 }
     84 
     85 
     86 /// Returns a region representing the first element of a (possibly
     87 /// multi-dimensional) array.
     88 ///
     89 /// On return, \p Ty will be set to the base type of the array.
     90 ///
     91 /// If the type is not an array type at all, the original value is returned.
     92 static SVal makeZeroElementRegion(ProgramStateRef State, SVal LValue,
     93                                   QualType &Ty) {
     94   SValBuilder &SVB = State->getStateManager().getSValBuilder();
     95   ASTContext &Ctx = SVB.getContext();
     96 
     97   while (const ArrayType *AT = Ctx.getAsArrayType(Ty)) {
     98     Ty = AT->getElementType();
     99     LValue = State->getLValue(Ty, SVB.makeZeroArrayIndex(), LValue);
    100   }
    101 
    102   return LValue;
    103 }
    104 
    105 void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *CE,
    106                                        ExplodedNode *Pred,
    107                                        ExplodedNodeSet &destNodes) {
    108   const LocationContext *LCtx = Pred->getLocationContext();
    109   ProgramStateRef State = Pred->getState();
    110 
    111   const MemRegion *Target = 0;
    112 
    113   // FIXME: Handle arrays, which run the same constructor for every element.
    114   // For now, we just run the first constructor (which should still invalidate
    115   // the entire array).
    116 
    117   switch (CE->getConstructionKind()) {
    118   case CXXConstructExpr::CK_Complete: {
    119     // See if we're constructing an existing region by looking at the next
    120     // element in the CFG.
    121     const CFGBlock *B = currBldrCtx->getBlock();
    122     if (currStmtIdx + 1 < B->size()) {
    123       CFGElement Next = (*B)[currStmtIdx+1];
    124 
    125       // Is this a constructor for a local variable?
    126       if (Optional<CFGStmt> StmtElem = Next.getAs<CFGStmt>()) {
    127         if (const DeclStmt *DS = dyn_cast<DeclStmt>(StmtElem->getStmt())) {
    128           if (const VarDecl *Var = dyn_cast<VarDecl>(DS->getSingleDecl())) {
    129             if (Var->getInit()->IgnoreImplicit() == CE) {
    130               SVal LValue = State->getLValue(Var, LCtx);
    131               QualType Ty = Var->getType();
    132               LValue = makeZeroElementRegion(State, LValue, Ty);
    133               Target = LValue.getAsRegion();
    134             }
    135           }
    136         }
    137       }
    138 
    139       // Is this a constructor for a member?
    140       if (Optional<CFGInitializer> InitElem = Next.getAs<CFGInitializer>()) {
    141         const CXXCtorInitializer *Init = InitElem->getInitializer();
    142         assert(Init->isAnyMemberInitializer());
    143 
    144         const CXXMethodDecl *CurCtor = cast<CXXMethodDecl>(LCtx->getDecl());
    145         Loc ThisPtr = getSValBuilder().getCXXThis(CurCtor,
    146                                                   LCtx->getCurrentStackFrame());
    147         SVal ThisVal = State->getSVal(ThisPtr);
    148 
    149         const ValueDecl *Field;
    150         SVal FieldVal;
    151         if (Init->isIndirectMemberInitializer()) {
    152           Field = Init->getIndirectMember();
    153           FieldVal = State->getLValue(Init->getIndirectMember(), ThisVal);
    154         } else {
    155           Field = Init->getMember();
    156           FieldVal = State->getLValue(Init->getMember(), ThisVal);
    157         }
    158 
    159         QualType Ty = Field->getType();
    160         FieldVal = makeZeroElementRegion(State, FieldVal, Ty);
    161         Target = FieldVal.getAsRegion();
    162       }
    163 
    164       // FIXME: This will eventually need to handle new-expressions as well.
    165       // Don't forget to update the pre-constructor initialization code below.
    166     }
    167 
    168     // If we couldn't find an existing region to construct into, assume we're
    169     // constructing a temporary.
    170     if (!Target) {
    171       MemRegionManager &MRMgr = getSValBuilder().getRegionManager();
    172       Target = MRMgr.getCXXTempObjectRegion(CE, LCtx);
    173     }
    174 
    175     break;
    176   }
    177   case CXXConstructExpr::CK_VirtualBase:
    178     // Make sure we are not calling virtual base class initializers twice.
    179     // Only the most-derived object should initialize virtual base classes.
    180     if (const Stmt *Outer = LCtx->getCurrentStackFrame()->getCallSite()) {
    181       const CXXConstructExpr *OuterCtor = dyn_cast<CXXConstructExpr>(Outer);
    182       if (OuterCtor) {
    183         switch (OuterCtor->getConstructionKind()) {
    184         case CXXConstructExpr::CK_NonVirtualBase:
    185         case CXXConstructExpr::CK_VirtualBase:
    186           // Bail out!
    187           destNodes.Add(Pred);
    188           return;
    189         case CXXConstructExpr::CK_Complete:
    190         case CXXConstructExpr::CK_Delegating:
    191           break;
    192         }
    193       }
    194     }
    195     // FALLTHROUGH
    196   case CXXConstructExpr::CK_NonVirtualBase:
    197   case CXXConstructExpr::CK_Delegating: {
    198     const CXXMethodDecl *CurCtor = cast<CXXMethodDecl>(LCtx->getDecl());
    199     Loc ThisPtr = getSValBuilder().getCXXThis(CurCtor,
    200                                               LCtx->getCurrentStackFrame());
    201     SVal ThisVal = State->getSVal(ThisPtr);
    202 
    203     if (CE->getConstructionKind() == CXXConstructExpr::CK_Delegating) {
    204       Target = ThisVal.getAsRegion();
    205     } else {
    206       // Cast to the base type.
    207       bool IsVirtual =
    208         (CE->getConstructionKind() == CXXConstructExpr::CK_VirtualBase);
    209       SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, CE->getType(),
    210                                                          IsVirtual);
    211       Target = BaseVal.getAsRegion();
    212     }
    213     break;
    214   }
    215   }
    216 
    217   CallEventManager &CEMgr = getStateManager().getCallEventManager();
    218   CallEventRef<CXXConstructorCall> Call =
    219     CEMgr.getCXXConstructorCall(CE, Target, State, LCtx);
    220 
    221   ExplodedNodeSet DstPreVisit;
    222   getCheckerManager().runCheckersForPreStmt(DstPreVisit, Pred, CE, *this);
    223 
    224   ExplodedNodeSet PreInitialized;
    225   {
    226     StmtNodeBuilder Bldr(DstPreVisit, PreInitialized, *currBldrCtx);
    227     if (CE->requiresZeroInitialization()) {
    228       // Type of the zero doesn't matter.
    229       SVal ZeroVal = svalBuilder.makeZeroVal(getContext().CharTy);
    230 
    231       for (ExplodedNodeSet::iterator I = DstPreVisit.begin(),
    232                                      E = DstPreVisit.end();
    233            I != E; ++I) {
    234         ProgramStateRef State = (*I)->getState();
    235         // FIXME: Once we properly handle constructors in new-expressions, we'll
    236         // need to invalidate the region before setting a default value, to make
    237         // sure there aren't any lingering bindings around. This probably needs
    238         // to happen regardless of whether or not the object is zero-initialized
    239         // to handle random fields of a placement-initialized object picking up
    240         // old bindings. We might only want to do it when we need to, though.
    241         // FIXME: This isn't actually correct for arrays -- we need to zero-
    242         // initialize the entire array, not just the first element -- but our
    243         // handling of arrays everywhere else is weak as well, so this shouldn't
    244         // actually make things worse. Placement new makes this tricky as well,
    245         // since it's then possible to be initializing one part of a multi-
    246         // dimensional array.
    247         State = State->bindDefault(loc::MemRegionVal(Target), ZeroVal);
    248         Bldr.generateNode(CE, *I, State, /*tag=*/0, ProgramPoint::PreStmtKind);
    249       }
    250     }
    251   }
    252 
    253   ExplodedNodeSet DstPreCall;
    254   getCheckerManager().runCheckersForPreCall(DstPreCall, PreInitialized,
    255                                             *Call, *this);
    256 
    257   ExplodedNodeSet DstEvaluated;
    258   StmtNodeBuilder Bldr(DstPreCall, DstEvaluated, *currBldrCtx);
    259 
    260   bool IsArray = isa<ElementRegion>(Target);
    261   if (CE->getConstructor()->isTrivial() &&
    262       CE->getConstructor()->isCopyOrMoveConstructor() &&
    263       !IsArray) {
    264     // FIXME: Handle other kinds of trivial constructors as well.
    265     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
    266          I != E; ++I)
    267       performTrivialCopy(Bldr, *I, *Call);
    268 
    269   } else {
    270     for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
    271          I != E; ++I)
    272       defaultEvalCall(Bldr, *I, *Call);
    273   }
    274 
    275   ExplodedNodeSet DstPostCall;
    276   getCheckerManager().runCheckersForPostCall(DstPostCall, DstEvaluated,
    277                                              *Call, *this);
    278   getCheckerManager().runCheckersForPostStmt(destNodes, DstPostCall, CE, *this);
    279 }
    280 
    281 void ExprEngine::VisitCXXDestructor(QualType ObjectType,
    282                                     const MemRegion *Dest,
    283                                     const Stmt *S,
    284                                     bool IsBaseDtor,
    285                                     ExplodedNode *Pred,
    286                                     ExplodedNodeSet &Dst) {
    287   const LocationContext *LCtx = Pred->getLocationContext();
    288   ProgramStateRef State = Pred->getState();
    289 
    290   // FIXME: We need to run the same destructor on every element of the array.
    291   // This workaround will just run the first destructor (which will still
    292   // invalidate the entire array).
    293   SVal DestVal = loc::MemRegionVal(Dest);
    294   DestVal = makeZeroElementRegion(State, DestVal, ObjectType);
    295   Dest = DestVal.getAsRegion();
    296 
    297   const CXXRecordDecl *RecordDecl = ObjectType->getAsCXXRecordDecl();
    298   assert(RecordDecl && "Only CXXRecordDecls should have destructors");
    299   const CXXDestructorDecl *DtorDecl = RecordDecl->getDestructor();
    300 
    301   CallEventManager &CEMgr = getStateManager().getCallEventManager();
    302   CallEventRef<CXXDestructorCall> Call =
    303     CEMgr.getCXXDestructorCall(DtorDecl, S, Dest, IsBaseDtor, State, LCtx);
    304 
    305   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
    306                                 Call->getSourceRange().getBegin(),
    307                                 "Error evaluating destructor");
    308 
    309   ExplodedNodeSet DstPreCall;
    310   getCheckerManager().runCheckersForPreCall(DstPreCall, Pred,
    311                                             *Call, *this);
    312 
    313   ExplodedNodeSet DstInvalidated;
    314   StmtNodeBuilder Bldr(DstPreCall, DstInvalidated, *currBldrCtx);
    315   for (ExplodedNodeSet::iterator I = DstPreCall.begin(), E = DstPreCall.end();
    316        I != E; ++I)
    317     defaultEvalCall(Bldr, *I, *Call);
    318 
    319   ExplodedNodeSet DstPostCall;
    320   getCheckerManager().runCheckersForPostCall(Dst, DstInvalidated,
    321                                              *Call, *this);
    322 }
    323 
    324 void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
    325                                    ExplodedNodeSet &Dst) {
    326   // FIXME: Much of this should eventually migrate to CXXAllocatorCall.
    327   // Also, we need to decide how allocators actually work -- they're not
    328   // really part of the CXXNewExpr because they happen BEFORE the
    329   // CXXConstructExpr subexpression. See PR12014 for some discussion.
    330 
    331   unsigned blockCount = currBldrCtx->blockCount();
    332   const LocationContext *LCtx = Pred->getLocationContext();
    333   DefinedOrUnknownSVal symVal = UnknownVal();
    334   FunctionDecl *FD = CNE->getOperatorNew();
    335 
    336   bool IsStandardGlobalOpNewFunction = false;
    337   if (FD && !isa<CXXMethodDecl>(FD) && !FD->isVariadic()) {
    338     if (FD->getNumParams() == 2) {
    339       QualType T = FD->getParamDecl(1)->getType();
    340       if (const IdentifierInfo *II = T.getBaseTypeIdentifier())
    341         // NoThrow placement new behaves as a standard new.
    342         IsStandardGlobalOpNewFunction = II->getName().equals("nothrow_t");
    343     }
    344     else
    345       // Placement forms are considered non-standard.
    346       IsStandardGlobalOpNewFunction = (FD->getNumParams() == 1);
    347   }
    348 
    349   // We assume all standard global 'operator new' functions allocate memory in
    350   // heap. We realize this is an approximation that might not correctly model
    351   // a custom global allocator.
    352   if (IsStandardGlobalOpNewFunction)
    353     symVal = svalBuilder.getConjuredHeapSymbolVal(CNE, LCtx, blockCount);
    354   else
    355     symVal = svalBuilder.conjureSymbolVal(0, CNE, LCtx, CNE->getType(),
    356                                           blockCount);
    357 
    358   ProgramStateRef State = Pred->getState();
    359   CallEventManager &CEMgr = getStateManager().getCallEventManager();
    360   CallEventRef<CXXAllocatorCall> Call =
    361     CEMgr.getCXXAllocatorCall(CNE, State, LCtx);
    362 
    363   // Invalidate placement args.
    364   // FIXME: Once we figure out how we want allocators to work,
    365   // we should be using the usual pre-/(default-)eval-/post-call checks here.
    366   State = Call->invalidateRegions(blockCount);
    367   if (!State)
    368     return;
    369 
    370   // If we're compiling with exceptions enabled, and this allocation function
    371   // is not declared as non-throwing, failures /must/ be signalled by
    372   // exceptions, and thus the return value will never be NULL.
    373   // C++11 [basic.stc.dynamic.allocation]p3.
    374   if (FD && getContext().getLangOpts().CXXExceptions) {
    375     QualType Ty = FD->getType();
    376     if (const FunctionProtoType *ProtoType = Ty->getAs<FunctionProtoType>())
    377       if (!ProtoType->isNothrow(getContext()))
    378         State = State->assume(symVal, true);
    379   }
    380 
    381   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
    382 
    383   if (CNE->isArray()) {
    384     // FIXME: allocating an array requires simulating the constructors.
    385     // For now, just return a symbolicated region.
    386     const MemRegion *NewReg = symVal.castAs<loc::MemRegionVal>().getRegion();
    387     QualType ObjTy = CNE->getType()->getAs<PointerType>()->getPointeeType();
    388     const ElementRegion *EleReg =
    389       getStoreManager().GetElementZeroRegion(NewReg, ObjTy);
    390     State = State->BindExpr(CNE, Pred->getLocationContext(),
    391                             loc::MemRegionVal(EleReg));
    392     Bldr.generateNode(CNE, Pred, State);
    393     return;
    394   }
    395 
    396   // FIXME: Once we have proper support for CXXConstructExprs inside
    397   // CXXNewExpr, we need to make sure that the constructed object is not
    398   // immediately invalidated here. (The placement call should happen before
    399   // the constructor call anyway.)
    400   SVal Result = symVal;
    401   if (FD && FD->isReservedGlobalPlacementOperator()) {
    402     // Non-array placement new should always return the placement location.
    403     SVal PlacementLoc = State->getSVal(CNE->getPlacementArg(0), LCtx);
    404     Result = svalBuilder.evalCast(PlacementLoc, CNE->getType(),
    405                                   CNE->getPlacementArg(0)->getType());
    406   }
    407 
    408   // Bind the address of the object, then check to see if we cached out.
    409   State = State->BindExpr(CNE, LCtx, Result);
    410   ExplodedNode *NewN = Bldr.generateNode(CNE, Pred, State);
    411   if (!NewN)
    412     return;
    413 
    414   // If the type is not a record, we won't have a CXXConstructExpr as an
    415   // initializer. Copy the value over.
    416   if (const Expr *Init = CNE->getInitializer()) {
    417     if (!isa<CXXConstructExpr>(Init)) {
    418       assert(Bldr.getResults().size() == 1);
    419       Bldr.takeNodes(NewN);
    420       evalBind(Dst, CNE, NewN, Result, State->getSVal(Init, LCtx),
    421                /*FirstInit=*/IsStandardGlobalOpNewFunction);
    422     }
    423   }
    424 }
    425 
    426 void ExprEngine::VisitCXXDeleteExpr(const CXXDeleteExpr *CDE,
    427                                     ExplodedNode *Pred, ExplodedNodeSet &Dst) {
    428   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
    429   ProgramStateRef state = Pred->getState();
    430   Bldr.generateNode(CDE, Pred, state);
    431 }
    432 
    433 void ExprEngine::VisitCXXCatchStmt(const CXXCatchStmt *CS,
    434                                    ExplodedNode *Pred,
    435                                    ExplodedNodeSet &Dst) {
    436   const VarDecl *VD = CS->getExceptionDecl();
    437   if (!VD) {
    438     Dst.Add(Pred);
    439     return;
    440   }
    441 
    442   const LocationContext *LCtx = Pred->getLocationContext();
    443   SVal V = svalBuilder.conjureSymbolVal(CS, LCtx, VD->getType(),
    444                                         currBldrCtx->blockCount());
    445   ProgramStateRef state = Pred->getState();
    446   state = state->bindLoc(state->getLValue(VD, LCtx), V);
    447 
    448   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
    449   Bldr.generateNode(CS, Pred, state);
    450 }
    451 
    452 void ExprEngine::VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
    453                                     ExplodedNodeSet &Dst) {
    454   StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
    455 
    456   // Get the this object region from StoreManager.
    457   const LocationContext *LCtx = Pred->getLocationContext();
    458   const MemRegion *R =
    459     svalBuilder.getRegionManager().getCXXThisRegion(
    460                                   getContext().getCanonicalType(TE->getType()),
    461                                                     LCtx);
    462 
    463   ProgramStateRef state = Pred->getState();
    464   SVal V = state->getSVal(loc::MemRegionVal(R));
    465   Bldr.generateNode(TE, Pred, state->BindExpr(TE, LCtx, V));
    466 }
    467