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