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