lib/StaticAnalyzer/EntoSA/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/PathSensitive/AnalysisManager.h"
  15 #include "clang/StaticAnalyzer/PathSensitive/ExprEngine.h"
  16 #include "clang/AST/DeclCXX.h"
  17
  18 using namespace clang;
  19 using namespace ento;
  20
  21 namespace {
  22 class CallExprWLItem {
  23 public:
  24   CallExpr::const_arg_iterator I;
  25   ExplodedNode *N;
  26
  27   CallExprWLItem(const CallExpr::const_arg_iterator &i, ExplodedNode *n)
  28     : I(i), N(n) {}
  29 };
  30 }
  31
  32 void ExprEngine::evalArguments(ConstExprIterator AI, ConstExprIterator AE,
  33                                  const FunctionProtoType *FnType,
  34                                  ExplodedNode *Pred, ExplodedNodeSet &Dst,
  35                                  bool FstArgAsLValue) {
  36
  37
  38   llvm::SmallVector<CallExprWLItem, 20> WorkList;
  39   WorkList.reserve(AE - AI);
  40   WorkList.push_back(CallExprWLItem(AI, Pred));
  41
  42   while (!WorkList.empty()) {
  43     CallExprWLItem Item = WorkList.back();
  44     WorkList.pop_back();
  45
  46     if (Item.I == AE) {
  47       Dst.insert(Item.N);
  48       continue;
  49     }
  50
  51     // Evaluate the argument.
  52     ExplodedNodeSet Tmp;
  53     bool VisitAsLvalue = FstArgAsLValue;
  54     if (FstArgAsLValue) {
  55       FstArgAsLValue = false;
  56     } else {
  57       const unsigned ParamIdx = Item.I - AI;
  58       VisitAsLvalue = FnType && ParamIdx < FnType->getNumArgs()
  59         ? FnType->getArgType(ParamIdx)->isReferenceType()
  60         : false;
  61     }
  62
  63     Visit(*Item.I, Item.N, Tmp);
  64     ++(Item.I);
  65     for (ExplodedNodeSet::iterator NI=Tmp.begin(), NE=Tmp.end(); NI != NE; ++NI)
  66       WorkList.push_back(CallExprWLItem(Item.I, *NI));
  67   }
  68 }
  69
  70 const CXXThisRegion *ExprEngine::getCXXThisRegion(const CXXRecordDecl *D,
  71                                                  const StackFrameContext *SFC) {
  72   Type *T = D->getTypeForDecl();
  73   QualType PT = getContext().getPointerType(QualType(T, 0));
  74   return svalBuilder.getRegionManager().getCXXThisRegion(PT, SFC);
  75 }
  76
  77 const CXXThisRegion *ExprEngine::getCXXThisRegion(const CXXMethodDecl *decl,
  78                                             const StackFrameContext *frameCtx) {
  79   return svalBuilder.getRegionManager().
  80                     getCXXThisRegion(decl->getThisType(getContext()), frameCtx);
  81 }
  82
  83 void ExprEngine::CreateCXXTemporaryObject(const Expr *Ex, ExplodedNode *Pred,
  84                                             ExplodedNodeSet &Dst) {
  85   ExplodedNodeSet Tmp;
  86   Visit(Ex, Pred, Tmp);
  87   for (ExplodedNodeSet::iterator I = Tmp.begin(), E = Tmp.end(); I != E; ++I) {
  88     const GRState *state = GetState(*I);
  89
  90     // Bind the temporary object to the value of the expression. Then bind
  91     // the expression to the location of the object.
  92     SVal V = state->getSVal(Ex);
  93
  94     const MemRegion *R =
  95       svalBuilder.getRegionManager().getCXXTempObjectRegion(Ex,
  96                                                    Pred->getLocationContext());
  97
  98     state = state->bindLoc(loc::MemRegionVal(R), V);
  99     MakeNode(Dst, Ex, Pred, state->BindExpr(Ex, loc::MemRegionVal(R)));
 100   }
 101 }
 102
 103 void ExprEngine::VisitCXXConstructExpr(const CXXConstructExpr *E,
 104                                          const MemRegion *Dest,
 105                                          ExplodedNode *Pred,
 106                                          ExplodedNodeSet &Dst) {
 107   if (!Dest)
 108     Dest = svalBuilder.getRegionManager().getCXXTempObjectRegion(E,
 109                                                     Pred->getLocationContext());
 110
 111   if (E->isElidable()) {
 112     VisitAggExpr(E->getArg(0), Dest, Pred, Dst);
 113     return;
 114   }
 115
 116   const CXXConstructorDecl *CD = E->getConstructor();
 117   assert(CD);
 118
 119   if (!(CD->isThisDeclarationADefinition() && AMgr.shouldInlineCall()))
 120     // FIXME: invalidate the object.
 121     return;
 122
 123
 124   // Evaluate other arguments.
 125   ExplodedNodeSet argsEvaluated;
 126   const FunctionProtoType *FnType = CD->getType()->getAs<FunctionProtoType>();
 127   evalArguments(E->arg_begin(), E->arg_end(), FnType, Pred, argsEvaluated);
 128   // The callee stack frame context used to create the 'this' parameter region.
 129   const StackFrameContext *SFC = AMgr.getStackFrame(CD,
 130                                                     Pred->getLocationContext(),
 131                                                     E, Builder->getBlock(),
 132                                                     Builder->getIndex());
 133
 134   const CXXThisRegion *ThisR =getCXXThisRegion(E->getConstructor()->getParent(),
 135                                                SFC);
 136
 137   CallEnter Loc(E, SFC, Pred->getLocationContext());
 138   for (ExplodedNodeSet::iterator NI = argsEvaluated.begin(),
 139                                  NE = argsEvaluated.end(); NI != NE; ++NI) {
 140     const GRState *state = GetState(*NI);
 141     // Setup 'this' region, so that the ctor is evaluated on the object pointed
 142     // by 'Dest'.
 143     state = state->bindLoc(loc::MemRegionVal(ThisR), loc::MemRegionVal(Dest));
 144     ExplodedNode *N = Builder->generateNode(Loc, state, Pred);
 145     if (N)
 146       Dst.Add(N);
 147   }
 148 }
 149
 150 void ExprEngine::VisitCXXDestructor(const CXXDestructorDecl *DD,
 151                                       const MemRegion *Dest,
 152                                       const Stmt *S,
 153                                       ExplodedNode *Pred,
 154                                       ExplodedNodeSet &Dst) {
 155   if (!(DD->isThisDeclarationADefinition() && AMgr.shouldInlineCall()))
 156     return;
 157   // Create the context for 'this' region.
 158   const StackFrameContext *SFC = AMgr.getStackFrame(DD,
 159                                                     Pred->getLocationContext(),
 160                                                     S, Builder->getBlock(),
 161                                                     Builder->getIndex());
 162
 163   const CXXThisRegion *ThisR = getCXXThisRegion(DD->getParent(), SFC);
 164
 165   CallEnter PP(S, SFC, Pred->getLocationContext());
 166
 167   const GRState *state = Pred->getState();
 168   state = state->bindLoc(loc::MemRegionVal(ThisR), loc::MemRegionVal(Dest));
 169   ExplodedNode *N = Builder->generateNode(PP, state, Pred);
 170   if (N)
 171     Dst.Add(N);
 172 }
 173
 174 void ExprEngine::VisitCXXMemberCallExpr(const CXXMemberCallExpr *MCE,
 175                                           ExplodedNode *Pred,
 176                                           ExplodedNodeSet &Dst) {
 177   // Get the method type.
 178   const FunctionProtoType *FnType =
 179                        MCE->getCallee()->getType()->getAs<FunctionProtoType>();
 180   assert(FnType && "Method type not available");
 181
 182   // Evaluate explicit arguments with a worklist.
 183   ExplodedNodeSet argsEvaluated;
 184   evalArguments(MCE->arg_begin(), MCE->arg_end(), FnType, Pred, argsEvaluated);
 185
 186   // Evaluate the implicit object argument.
 187   ExplodedNodeSet AllargsEvaluated;
 188   const MemberExpr *ME = dyn_cast<MemberExpr>(MCE->getCallee()->IgnoreParens());
 189   if (!ME)
 190     return;
 191   Expr *ObjArgExpr = ME->getBase();
 192   for (ExplodedNodeSet::iterator I = argsEvaluated.begin(),
 193                                  E = argsEvaluated.end(); I != E; ++I) {
 194       Visit(ObjArgExpr, *I, AllargsEvaluated);
 195   }
 196
 197   // Now evaluate the call itself.
 198   const CXXMethodDecl *MD = cast<CXXMethodDecl>(ME->getMemberDecl());
 199   assert(MD && "not a CXXMethodDecl?");
 200   evalMethodCall(MCE, MD, ObjArgExpr, Pred, AllargsEvaluated, Dst);
 201 }
 202
 203 void ExprEngine::VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *C,
 204                                             ExplodedNode *Pred,
 205                                             ExplodedNodeSet &Dst) {
 206   const CXXMethodDecl *MD = dyn_cast_or_null<CXXMethodDecl>(C->getCalleeDecl());
 207   if (!MD) {
 208     // If the operator doesn't represent a method call treat as regural call.
 209     VisitCall(C, Pred, C->arg_begin(), C->arg_end(), Dst);
 210     return;
 211   }
 212
 213   // Determine the type of function we're calling (if available).
 214   const FunctionProtoType *Proto = NULL;
 215   QualType FnType = C->getCallee()->IgnoreParens()->getType();
 216   if (const PointerType *FnTypePtr = FnType->getAs<PointerType>())
 217     Proto = FnTypePtr->getPointeeType()->getAs<FunctionProtoType>();
 218
 219   // Evaluate arguments treating the first one (object method is called on)
 220   // as alvalue.
 221   ExplodedNodeSet argsEvaluated;
 222   evalArguments(C->arg_begin(), C->arg_end(), Proto, Pred, argsEvaluated, true);
 223
 224   // Now evaluate the call itself.
 225   evalMethodCall(C, MD, C->getArg(0), Pred, argsEvaluated, Dst);
 226 }
 227
 228 void ExprEngine::evalMethodCall(const CallExpr *MCE, const CXXMethodDecl *MD,
 229                                   const Expr *ThisExpr, ExplodedNode *Pred,
 230                                   ExplodedNodeSet &Src, ExplodedNodeSet &Dst) {
 231   // Allow checkers to pre-visit the member call.
 232   ExplodedNodeSet PreVisitChecks;
 233   CheckerVisit(MCE, PreVisitChecks, Src, PreVisitStmtCallback);
 234
 235   if (!(MD->isThisDeclarationADefinition() && AMgr.shouldInlineCall())) {
 236     // FIXME: conservative method call evaluation.
 237     CheckerVisit(MCE, Dst, PreVisitChecks, PostVisitStmtCallback);
 238     return;
 239   }
 240
 241   const StackFrameContext *SFC = AMgr.getStackFrame(MD,
 242                                                     Pred->getLocationContext(),
 243                                                     MCE,
 244                                                     Builder->getBlock(),
 245                                                     Builder->getIndex());
 246   const CXXThisRegion *ThisR = getCXXThisRegion(MD, SFC);
 247   CallEnter Loc(MCE, SFC, Pred->getLocationContext());
 248   for (ExplodedNodeSet::iterator I = PreVisitChecks.begin(),
 249          E = PreVisitChecks.end(); I != E; ++I) {
 250     // Set up 'this' region.
 251     const GRState *state = GetState(*I);
 252     state = state->bindLoc(loc::MemRegionVal(ThisR), state->getSVal(ThisExpr));
 253     Dst.Add(Builder->generateNode(Loc, state, *I));
 254   }
 255 }
 256
 257 void ExprEngine::VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
 258                                    ExplodedNodeSet &Dst) {
 259   if (CNE->isArray()) {
 260     // FIXME: allocating an array has not been handled.
 261     return;
 262   }
 263
 264   unsigned Count = Builder->getCurrentBlockCount();
 265   DefinedOrUnknownSVal symVal =
 266     svalBuilder.getConjuredSymbolVal(NULL, CNE, CNE->getType(), Count);
 267   const MemRegion *NewReg = cast<loc::MemRegionVal>(symVal).getRegion();
 268
 269   QualType ObjTy = CNE->getType()->getAs<PointerType>()->getPointeeType();
 270
 271   const ElementRegion *EleReg =
 272                          getStoreManager().GetElementZeroRegion(NewReg, ObjTy);
 273
 274   // Evaluate constructor arguments.
 275   const FunctionProtoType *FnType = NULL;
 276   const CXXConstructorDecl *CD = CNE->getConstructor();
 277   if (CD)
 278     FnType = CD->getType()->getAs<FunctionProtoType>();
 279   ExplodedNodeSet argsEvaluated;
 280   evalArguments(CNE->constructor_arg_begin(), CNE->constructor_arg_end(),
 281                 FnType, Pred, argsEvaluated);
 282
 283   // Initialize the object region and bind the 'new' expression.
 284   for (ExplodedNodeSet::iterator I = argsEvaluated.begin(),
 285                                  E = argsEvaluated.end(); I != E; ++I) {
 286     const GRState *state = GetState(*I);
 287
 288     if (ObjTy->isRecordType()) {
 289       state = state->InvalidateRegion(EleReg, CNE, Count);
 290     } else {
 291       if (CNE->hasInitializer()) {
 292         SVal V = state->getSVal(*CNE->constructor_arg_begin());
 293         state = state->bindLoc(loc::MemRegionVal(EleReg), V);
 294       } else {
 295         // Explicitly set to undefined, because currently we retrieve symbolic
 296         // value from symbolic region.
 297         state = state->bindLoc(loc::MemRegionVal(EleReg), UndefinedVal());
 298       }
 299     }
 300     state = state->BindExpr(CNE, loc::MemRegionVal(EleReg));
 301     MakeNode(Dst, CNE, *I, state);
 302   }
 303 }
 304
 305 void ExprEngine::VisitCXXDeleteExpr(const CXXDeleteExpr *CDE,
 306                                       ExplodedNode *Pred,ExplodedNodeSet &Dst) {
 307   // Should do more checking.
 308   ExplodedNodeSet Argevaluated;
 309   Visit(CDE->getArgument(), Pred, Argevaluated);
 310   for (ExplodedNodeSet::iterator I = Argevaluated.begin(),
 311                                  E = Argevaluated.end(); I != E; ++I) {
 312     const GRState *state = GetState(*I);
 313     MakeNode(Dst, CDE, *I, state);
 314   }
 315 }
 316
 317 void ExprEngine::VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
 318                                     ExplodedNodeSet &Dst) {
 319   // Get the this object region from StoreManager.
 320   const MemRegion *R =
 321     svalBuilder.getRegionManager().getCXXThisRegion(
 322                                   getContext().getCanonicalType(TE->getType()),
 323                                                Pred->getLocationContext());
 324
 325   const GRState *state = GetState(Pred);
 326   SVal V = state->getSVal(loc::MemRegionVal(R));
 327   MakeNode(Dst, TE, Pred, state->BindExpr(TE, V));
 328 }