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

   1 //===- GRCXXExprEngine.cpp - C++ expr evaluation engine ---------*- 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/CheckerManager.h"
  15 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  17 #include "clang/AST/DeclCXX.h"
  18
  19 using namespace clang;
  20 using namespace ento;
  21
  22 namespace {
  23 class CallExprWLItem {
  24 public:
  25   CallExpr::const_arg_iterator I;
  26   ExplodedNode *N;
  27
  28   CallExprWLItem(const CallExpr::const_arg_iterator &i, ExplodedNode *n)
  29     : I(i), N(n) {}
  30 };
  31 }
  32
  33 void ExprEngine::evalArguments(ConstExprIterator AI, ConstExprIterator AE,
  34                                  const FunctionProtoType *FnType,
  35                                  ExplodedNode *Pred, ExplodedNodeSet &Dst,
  36                                  bool FstArgAsLValue) {
  37
  38
  39   llvm::SmallVector<CallExprWLItem, 20> WorkList;
  40   WorkList.reserve(AE - AI);
  41   WorkList.push_back(CallExprWLItem(AI, Pred));
  42
  43   while (!WorkList.empty()) {
  44     CallExprWLItem Item = WorkList.back();
  45     WorkList.pop_back();
  46
  47     if (Item.I == AE) {
  48       Dst.insert(Item.N);
  49       continue;
  50     }
  51
  52     // Evaluate the argument.
  53     ExplodedNodeSet Tmp;
  54     if (FstArgAsLValue) {
  55       FstArgAsLValue = false;
  56     }
  57
  58     Visit(*Item.I, Item.N, Tmp);
  59     ++(Item.I);
  60     for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI != NE; ++NI)
  61       WorkList.push_back(CallExprWLItem(Item.I, *NI));
  62   }
  63 }
  64
  65 void ExprEngine::evalCallee(const CallExpr *callExpr,
  66                             const ExplodedNodeSet &src,
  67                             ExplodedNodeSet &dest) {
  68
  69   const Expr *callee = 0;
  70
  71   switch (callExpr->getStmtClass()) {
  72     case Stmt::CXXMemberCallExprClass: {
  73       // Evaluate the implicit object argument that is the recipient of the
  74       // call.
  75       callee = cast<CXXMemberCallExpr>(callExpr)->getImplicitObjectArgument();
  76
  77       // FIXME: handle member pointers.
  78       if (!callee)
  79         return;
  80
  81       break;
  82     }
  83     default: {
  84       callee = callExpr->getCallee()->IgnoreParens();
  85       break;
  86     }
  87   }
  88
  89   for (ExplodedNodeSet::iterator i = src.begin(), e = src.end(); i != e; ++i)
  90     Visit(callee, *i, dest);
  91 }
  92
  93 const CXXThisRegion *ExprEngine::getCXXThisRegion(const CXXRecordDecl *D,
  94                                                  const StackFrameContext *SFC) {
  95   const Type *T = D->getTypeForDecl();
  96   QualType PT = getContext().getPointerType(QualType(T, 0));
  97   return svalBuilder.getRegionManager().getCXXThisRegion(PT, SFC);
  98 }
  99
 100 const CXXThisRegion *ExprEngine::getCXXThisRegion(const CXXMethodDecl *decl,
 101                                             const StackFrameContext *frameCtx) {
 102   return svalBuilder.getRegionManager().
 103                     getCXXThisRegion(decl->getThisType(getContext()), frameCtx);
 104 }
 105
 106 void ExprEngine::CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred,
 107                                             ExplodedNodeSet &Dst) {
 108   ExplodedNodeSet Tmp;
 109   Visit(Ex, Pred, Tmp);
 110   for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
 111     const GRState *state = GetState(*I);
 112
 113     // Bind the temporary object to the value of the expression. Then bind
 114     // the expression to the location of the object.
 115     SVal V = state->getSVal(Ex);
 116
 117     const MemRegion *R =
 118       svalBuilder.getRegionManager().getCXXTempObjectRegion(Ex,
 119                                                    Pred->getLocationContext());
 120
 121     state = state->bindLoc(loc::MemRegionVal(R), V);
 122     MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, loc::MemRegionVal(R)));
 123   }
 124 }
 125
 126 void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *E,
 127                                        const MemRegion *Dest,
 128                                        ExplodedNode *Pred,
 129                                        ExplodedNodeSet &destNodes) {
 130
 131   const CXXConstructorDecl *CD = E->getConstructor();
 132   assert(CD);
 133
 134 #if 0
 135   if (!(CD->doesThisDeclarationHaveABody() && AMgr.shouldInlineCall()))
 136     // FIXME: invalidate the object.
 137     return;
 138 #endif
 139
 140   // Evaluate other arguments.
 141   ExplodedNodeSet argsEvaluated;
 142   const FunctionProtoType *FnType = CD->getType()->getAs<FunctionProtoType>();
 143   evalArguments(E->arg_begin(), E->arg_end(), FnType, Pred, argsEvaluated);
 144
 145 #if 0
 146   // Is the constructor elidable?
 147   if (E->isElidable()) {
 148     VisitAggExpr(E->getArg(0), destNodes, Pred, Dst);
 149     // FIXME: this is here to force propagation if VisitAggExpr doesn't
 150     if (destNodes.empty())
 151       destNodes.Add(Pred);
 152     return;
 153   }
 154 #endif
 155
 156   // Perform the previsit of the constructor.
 157   ExplodedNodeSet destPreVisit;
 158   getCheckerManager().runCheckersForPreStmt(destPreVisit, argsEvaluated, E,
 159                                             *this);
 160
 161   // Evaluate the constructor.  Currently we don't now allow checker-specific
 162   // implementations of specific constructors (as we do with ordinary
 163   // function calls.  We can re-evaluate this in the future.
 164
 165 #if 0
 166   // Inlining currently isn't fully implemented.
 167
 168   if (AMgr.shouldInlineCall()) {
 169     if (!Dest)
 170       Dest =
 171         svalBuilder.getRegionManager().getCXXTempObjectRegion(E,
 172                                                   Pred->getLocationContext());
 173
 174     // The callee stack frame context used to create the 'this'
 175     // parameter region.
 176     const StackFrameContext *SFC =
 177       AMgr.getStackFrame(CD, Pred->getLocationContext(),
 178                          E, Builder->getBlock(), Builder->getIndex());
 179
 180     // Create the 'this' region.
 181     const CXXThisRegion *ThisR =
 182       getCXXThisRegion(E->getConstructor()->getParent(), SFC);
 183
 184     CallEnter Loc(E, SFC, Pred->getLocationContext());
 185
 186
 187     for (ExplodedNodeSet::iterator NI = argsEvaluated.begin(),
 188                                   NE = argsEvaluated.end(); NI != NE; ++NI) {
 189       const GRState *state = GetState(*NI);
 190       // Setup 'this' region, so that the ctor is evaluated on the object pointed
 191       // by 'Dest'.
 192       state = state->bindLoc(loc::MemRegionVal(ThisR), loc::MemRegionVal(Dest));
 193       if (ExplodedNode *N = Builder->generateNode(Loc, state, *NI))
 194         destNodes.Add(N);
 195     }
 196   }
 197 #endif
 198
 199   // Default semantics: invalidate all regions passed as arguments.
 200   llvm::SmallVector<const MemRegion*, 10> regionsToInvalidate;
 201
 202   // FIXME: We can have collisions on the conjured symbol if the
 203   //  expression *I also creates conjured symbols.  We probably want
 204   //  to identify conjured symbols by an expression pair: the enclosing
 205   //  expression (the context) and the expression itself.  This should
 206   //  disambiguate conjured symbols.
 207   unsigned blockCount = Builder->getCurrentBlockCount();
 208
 209   // NOTE: Even if RegionsToInvalidate is empty, we must still invalidate
 210   //  global variables.
 211   ExplodedNodeSet destCall;
 212
 213   for (ExplodedNodeSet::iterator
 214         i = destPreVisit.begin(), e = destPreVisit.end();
 215        i != e; ++i)
 216   {
 217     ExplodedNode *Pred = *i;
 218     const GRState *state = GetState(Pred);
 219
 220     // Accumulate list of regions that are invalidated.
 221     for (CXXConstructExpr::const_arg_iterator
 222           ai = E->arg_begin(), ae = E->arg_end();
 223           ai != ae; ++ai)
 224     {
 225       SVal val = state->getSVal(*ai);
 226       if (const MemRegion *region = val.getAsRegion())
 227         regionsToInvalidate.push_back(region);
 228     }
 229
 230     // Invalidate the regions.
 231     state = state->invalidateRegions(regionsToInvalidate.data(),
 232                                      regionsToInvalidate.data() +
 233                                      regionsToInvalidate.size(),
 234                                      E, blockCount, 0,
 235                                      /* invalidateGlobals = */ true);
 236
 237     Builder->MakeNode(destCall, E, Pred, state);
 238   }
 239
 240   // Do the post visit.
 241   getCheckerManager().runCheckersForPostStmt(destNodes, destCall, E, *this);
 242 }
 243
 244 void ExprEngine::VisitCXXDestructor(const CXXDestructorDecl *DD,
 245                                       const MemRegion *Dest,
 246                                       const Stmt *S,
 247                                       ExplodedNode *Pred,
 248                                       ExplodedNodeSet &Dst) {
 249   if (!(DD->doesThisDeclarationHaveABody() && AMgr.shouldInlineCall()))
 250     return;
 251   // Create the context for 'this' region.
 252   const StackFrameContext *SFC = AMgr.getStackFrame(DD,
 253                                                     Pred->getLocationContext(),
 254                                                     S, Builder->getBlock(),
 255                                                     Builder->getIndex());
 256
 257   const CXXThisRegion *ThisR = getCXXThisRegion(DD->getParent(), SFC);
 258
 259   CallEnter PP(S, SFC, Pred->getLocationContext());
 260
 261   const GRState *state = Pred->getState();
 262   state = state->bindLoc(loc::MemRegionVal(ThisR), loc::MemRegionVal(Dest));
 263   ExplodedNode *N = Builder->generateNode(PP, state, Pred);
 264   if (N)
 265     Dst.Add(N);
 266 }
 267
 268 void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
 269                                    ExplodedNodeSet &Dst) {
 270
 271   unsigned blockCount = Builder->getCurrentBlockCount();
 272   DefinedOrUnknownSVal symVal =
 273     svalBuilder.getConjuredSymbolVal(NULL, CNE, CNE->getType(), blockCount);
 274   const MemRegion *NewReg = cast<loc::MemRegionVal>(symVal).getRegion();
 275   QualType ObjTy = CNE->getType()->getAs<PointerType>()->getPointeeType();
 276   const ElementRegion *EleReg =
 277     getStoreManager().GetElementZeroRegion(NewReg, ObjTy);
 278
 279   if (CNE->isArray()) {
 280     // FIXME: allocating an array requires simulating the constructors.
 281     // For now, just return a symbolicated region.
 282     const GRState *state = GetState(Pred);
 283     state = state->BindExpr(CNE, loc::MemRegionVal(EleReg));
 284     MakeNode(Dst, CNE, Pred, state);
 285     return;
 286   }
 287
 288   // Evaluate constructor arguments.
 289   const FunctionProtoType *FnType = NULL;
 290   const CXXConstructorDecl *CD = CNE->getConstructor();
 291   if (CD)
 292     FnType = CD->getType()->getAs<FunctionProtoType>();
 293   ExplodedNodeSet argsEvaluated;
 294   evalArguments(CNE->constructor_arg_begin(), CNE->constructor_arg_end(),
 295                 FnType, Pred, argsEvaluated);
 296
 297   // Initialize the object region and bind the 'new' expression.
 298   for (ExplodedNodeSet::iterator I = argsEvaluated.begin(),
 299                                  E = argsEvaluated.end(); I != E; ++I) {
 300
 301     const GRState *state = GetState(*I);
 302
 303     // Accumulate list of regions that are invalidated.
 304     // FIXME: Eventually we should unify the logic for constructor
 305     // processing in one place.
 306     llvm::SmallVector<const MemRegion*, 10> regionsToInvalidate;
 307     for (CXXNewExpr::const_arg_iterator
 308           ai = CNE->constructor_arg_begin(), ae = CNE->constructor_arg_end();
 309           ai != ae; ++ai)
 310     {
 311       SVal val = state->getSVal(*ai);
 312       if (const MemRegion *region = val.getAsRegion())
 313         regionsToInvalidate.push_back(region);
 314     }
 315
 316     if (ObjTy->isRecordType()) {
 317       regionsToInvalidate.push_back(EleReg);
 318       // Invalidate the regions.
 319       state = state->invalidateRegions(regionsToInvalidate.data(),
 320                                        regionsToInvalidate.data() +
 321                                        regionsToInvalidate.size(),
 322                                        CNE, blockCount, 0,
 323                                        /* invalidateGlobals = */ true);
 324
 325     } else {
 326       // Invalidate the regions.
 327       state = state->invalidateRegions(regionsToInvalidate.data(),
 328                                        regionsToInvalidate.data() +
 329                                        regionsToInvalidate.size(),
 330                                        CNE, blockCount, 0,
 331                                        /* invalidateGlobals = */ true);
 332
 333       if (CNE->hasInitializer()) {
 334         SVal V = state->getSVal(*CNE->constructor_arg_begin());
 335         state = state->bindLoc(loc::MemRegionVal(EleReg), V);
 336       } else {
 337         // Explicitly set to undefined, because currently we retrieve symbolic
 338         // value from symbolic region.
 339         state = state->bindLoc(loc::MemRegionVal(EleReg), UndefinedVal());
 340       }
 341     }
 342     state = state->BindExpr(CNE, loc::MemRegionVal(EleReg));
 343     MakeNode(Dst, CNE, *I, state);
 344   }
 345 }
 346
 347 void ExprEngine::VisitCXXDeleteExpr(const CXXDeleteExpr *CDE,
 348                                       ExplodedNode *Pred,ExplodedNodeSet &Dst) {
 349   // Should do more checking.
 350   ExplodedNodeSet Argevaluated;
 351   Visit(CDE->getArgument(), Pred, Argevaluated);
 352   for (ExplodedNodeSet::iterator I = Argevaluated.begin(),
 353                                  E = Argevaluated.end(); I != E; ++I) {
 354     const GRState *state = GetState(*I);
 355     MakeNode(Dst, CDE, *I, state);
 356   }
 357 }
 358
 359 void ExprEngine::VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
 360                                     ExplodedNodeSet &Dst) {
 361   // Get the this object region from StoreManager.
 362   const MemRegion *R =
 363     svalBuilder.getRegionManager().getCXXThisRegion(
 364                                   getContext().getCanonicalType(TE->getType()),
 365                                                Pred->getLocationContext());
 366
 367   const GRState *state = GetState(Pred);
 368   SVal V = state->getSVal(loc::MemRegionVal(R));
 369   MakeNode(Dst, TE, Pred, state->BindExpr(TE, V));
 370 }