1//===-- ExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- 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 a meta-engine for path-sensitive dataflow analysis that
11//  is built on CoreEngine, but provides the boilerplate to execute transfer
12//  functions and build the ExplodedGraph at the expression level.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_CLANG_GR_EXPRENGINE
17#define LLVM_CLANG_GR_EXPRENGINE
18
19#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
23#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
24#include "clang/AST/Type.h"
25#include "clang/AST/ExprObjC.h"
26#include "clang/AST/ExprCXX.h"
27#include "clang/AST/StmtObjC.h"
28
29namespace clang {
30
31class ObjCForCollectionStmt;
32
33namespace ento {
34
35class AnalysisManager;
36class CallOrObjCMessage;
37class ObjCMessage;
38
39class ExprEngine : public SubEngine {
40  AnalysisManager &AMgr;
41
42  CoreEngine Engine;
43
44  /// G - the simulation graph.
45  ExplodedGraph& G;
46
47  /// Builder - The current StmtNodeBuilder which is used when building the
48  ///  nodes for a given statement.
49  StmtNodeBuilder* Builder;
50
51  /// StateMgr - Object that manages the data for all created states.
52  ProgramStateManager StateMgr;
53
54  /// SymMgr - Object that manages the symbol information.
55  SymbolManager& SymMgr;
56
57  /// svalBuilder - SValBuilder object that creates SVals from expressions.
58  SValBuilder &svalBuilder;
59
60  /// EntryNode - The immediate predecessor node.
61  ExplodedNode *EntryNode;
62
63  /// CleanedState - The state for EntryNode "cleaned" of all dead
64  ///  variables and symbols (as determined by a liveness analysis).
65  const ProgramState *CleanedState;
66
67  /// currentStmt - The current block-level statement.
68  const Stmt *currentStmt;
69
70  /// Obj-C Class Identifiers.
71  IdentifierInfo* NSExceptionII;
72
73  /// Obj-C Selectors.
74  Selector* NSExceptionInstanceRaiseSelectors;
75  Selector RaiseSel;
76
77  /// Whether or not GC is enabled in this analysis.
78  bool ObjCGCEnabled;
79
80  /// The BugReporter associated with this engine.  It is important that
81  ///  this object be placed at the very end of member variables so that its
82  ///  destructor is called before the rest of the ExprEngine is destroyed.
83  GRBugReporter BR;
84
85public:
86  ExprEngine(AnalysisManager &mgr, bool gcEnabled);
87
88  ~ExprEngine();
89
90  void ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
91    Engine.ExecuteWorkList(L, Steps, 0);
92  }
93
94  /// Execute the work list with an initial state. Nodes that reaches the exit
95  /// of the function are added into the Dst set, which represent the exit
96  /// state of the function call.
97  void ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
98                                       const ProgramState *InitState,
99                                       ExplodedNodeSet &Dst) {
100    Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst);
101  }
102
103  /// getContext - Return the ASTContext associated with this analysis.
104  ASTContext &getContext() const { return AMgr.getASTContext(); }
105
106  virtual AnalysisManager &getAnalysisManager() { return AMgr; }
107
108  CheckerManager &getCheckerManager() const {
109    return *AMgr.getCheckerManager();
110  }
111
112  SValBuilder &getSValBuilder() { return svalBuilder; }
113
114  BugReporter& getBugReporter() { return BR; }
115
116  StmtNodeBuilder &getBuilder() { assert(Builder); return *Builder; }
117
118  bool isObjCGCEnabled() { return ObjCGCEnabled; }
119
120  /// ViewGraph - Visualize the ExplodedGraph created by executing the
121  ///  simulation.
122  void ViewGraph(bool trim = false);
123
124  void ViewGraph(ExplodedNode** Beg, ExplodedNode** End);
125
126  /// getInitialState - Return the initial state used for the root vertex
127  ///  in the ExplodedGraph.
128  const ProgramState *getInitialState(const LocationContext *InitLoc);
129
130  ExplodedGraph& getGraph() { return G; }
131  const ExplodedGraph& getGraph() const { return G; }
132
133  /// processCFGElement - Called by CoreEngine. Used to generate new successor
134  ///  nodes by processing the 'effects' of a CFG element.
135  void processCFGElement(const CFGElement E, StmtNodeBuilder& Bldr,
136                         ExplodedNode *Pred);
137
138  void ProcessStmt(const CFGStmt S, StmtNodeBuilder &builder,
139                   ExplodedNode *Pred);
140
141  void ProcessInitializer(const CFGInitializer I, StmtNodeBuilder &Bldr,
142                          ExplodedNode *Pred);
143
144  void ProcessImplicitDtor(const CFGImplicitDtor D, StmtNodeBuilder &builder,
145                           ExplodedNode *Pred);
146
147  void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
148                               StmtNodeBuilder &builder, ExplodedNode *Pred);
149  void ProcessBaseDtor(const CFGBaseDtor D, StmtNodeBuilder &builder);
150  void ProcessMemberDtor(const CFGMemberDtor D, StmtNodeBuilder &builder);
151  void ProcessTemporaryDtor(const CFGTemporaryDtor D,
152                            StmtNodeBuilder &builder);
153
154  /// Called by CoreEngine when processing the entrance of a CFGBlock.
155  virtual void processCFGBlockEntrance(ExplodedNodeSet &dstNodes,
156                                GenericNodeBuilder<BlockEntrance> &nodeBuilder);
157
158  /// ProcessBranch - Called by CoreEngine.  Used to generate successor
159  ///  nodes by processing the 'effects' of a branch condition.
160  void processBranch(const Stmt *Condition, const Stmt *Term,
161                     NodeBuilderContext& BuilderCtx,
162                     ExplodedNode *Pred,
163                     const CFGBlock *DstT,
164                     const CFGBlock *DstF);
165
166  /// processIndirectGoto - Called by CoreEngine.  Used to generate successor
167  ///  nodes by processing the 'effects' of a computed goto jump.
168  void processIndirectGoto(IndirectGotoNodeBuilder& builder);
169
170  /// ProcessSwitch - Called by CoreEngine.  Used to generate successor
171  ///  nodes by processing the 'effects' of a switch statement.
172  void processSwitch(SwitchNodeBuilder& builder);
173
174  /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
175  ///  nodes when the control reaches the end of a function.
176  void processEndOfFunction(EndOfFunctionNodeBuilder& builder);
177
178  /// Generate the entry node of the callee.
179  void processCallEnter(CallEnterNodeBuilder &builder);
180
181  /// Generate the first post callsite node.
182  void processCallExit(CallExitNodeBuilder &builder);
183
184  /// Called by CoreEngine when the analysis worklist has terminated.
185  void processEndWorklist(bool hasWorkRemaining);
186
187  /// evalAssume - Callback function invoked by the ConstraintManager when
188  ///  making assumptions about state values.
189  const ProgramState *processAssume(const ProgramState *state, SVal cond,bool assumption);
190
191  /// wantsRegionChangeUpdate - Called by ProgramStateManager to determine if a
192  ///  region change should trigger a processRegionChanges update.
193  bool wantsRegionChangeUpdate(const ProgramState *state);
194
195  /// processRegionChanges - Called by ProgramStateManager whenever a change is made
196  ///  to the store. Used to update checkers that track region values.
197  const ProgramState *
198  processRegionChanges(const ProgramState *state,
199                       const StoreManager::InvalidatedSymbols *invalidated,
200                       ArrayRef<const MemRegion *> ExplicitRegions,
201                       ArrayRef<const MemRegion *> Regions);
202
203  /// printState - Called by ProgramStateManager to print checker-specific data.
204  void printState(raw_ostream &Out, const ProgramState *State,
205                  const char *NL, const char *Sep);
206
207  virtual ProgramStateManager& getStateManager() { return StateMgr; }
208
209  StoreManager& getStoreManager() { return StateMgr.getStoreManager(); }
210
211  ConstraintManager& getConstraintManager() {
212    return StateMgr.getConstraintManager();
213  }
214
215  // FIXME: Remove when we migrate over to just using SValBuilder.
216  BasicValueFactory& getBasicVals() {
217    return StateMgr.getBasicVals();
218  }
219  const BasicValueFactory& getBasicVals() const {
220    return StateMgr.getBasicVals();
221  }
222
223  // FIXME: Remove when we migrate over to just using ValueManager.
224  SymbolManager& getSymbolManager() { return SymMgr; }
225  const SymbolManager& getSymbolManager() const { return SymMgr; }
226
227  // Functions for external checking of whether we have unfinished work
228  bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
229  bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
230  bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
231
232  const CoreEngine &getCoreEngine() const { return Engine; }
233
234public:
235  ExplodedNode *MakeNode(ExplodedNodeSet &Dst, const Stmt *S,
236                         ExplodedNode *Pred, const ProgramState *St,
237                         ProgramPoint::Kind K = ProgramPoint::PostStmtKind,
238                         const ProgramPointTag *tag = 0);
239
240  /// Visit - Transfer function logic for all statements.  Dispatches to
241  ///  other functions that handle specific kinds of statements.
242  void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst);
243
244  /// VisitArraySubscriptExpr - Transfer function for array accesses.
245  void VisitLvalArraySubscriptExpr(const ArraySubscriptExpr *Ex,
246                                   ExplodedNode *Pred,
247                                   ExplodedNodeSet &Dst);
248
249  /// VisitAsmStmt - Transfer function logic for inline asm.
250  void VisitAsmStmt(const AsmStmt *A, ExplodedNode *Pred, ExplodedNodeSet &Dst);
251
252  void VisitAsmStmtHelperOutputs(const AsmStmt *A,
253                                 AsmStmt::const_outputs_iterator I,
254                                 AsmStmt::const_outputs_iterator E,
255                                 ExplodedNode *Pred, ExplodedNodeSet &Dst);
256
257  void VisitAsmStmtHelperInputs(const AsmStmt *A,
258                                AsmStmt::const_inputs_iterator I,
259                                AsmStmt::const_inputs_iterator E,
260                                ExplodedNode *Pred, ExplodedNodeSet &Dst);
261
262  /// VisitBlockExpr - Transfer function logic for BlockExprs.
263  void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
264                      ExplodedNodeSet &Dst);
265
266  /// VisitBinaryOperator - Transfer function logic for binary operators.
267  void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred,
268                           ExplodedNodeSet &Dst);
269
270
271  /// VisitCall - Transfer function for function calls.
272  void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
273                     ExplodedNodeSet &Dst);
274
275  /// VisitCast - Transfer function logic for all casts (implicit and explicit).
276  void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred,
277                ExplodedNodeSet &Dst);
278
279  /// VisitCompoundLiteralExpr - Transfer function logic for compound literals.
280  void VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
281                                ExplodedNode *Pred, ExplodedNodeSet &Dst);
282
283  /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs.
284  void VisitCommonDeclRefExpr(const Expr *DR, const NamedDecl *D,
285                              ExplodedNode *Pred, ExplodedNodeSet &Dst);
286
287  /// VisitDeclStmt - Transfer function logic for DeclStmts.
288  void VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
289                     ExplodedNodeSet &Dst);
290
291  /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
292  void VisitGuardedExpr(const Expr *Ex, const Expr *L, const Expr *R,
293                        ExplodedNode *Pred, ExplodedNodeSet &Dst);
294
295  void VisitInitListExpr(const InitListExpr *E, ExplodedNode *Pred,
296                         ExplodedNodeSet &Dst);
297
298  /// VisitLogicalExpr - Transfer function logic for '&&', '||'
299  void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
300                        ExplodedNodeSet &Dst);
301
302  /// VisitMemberExpr - Transfer function for member expressions.
303  void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
304                           ExplodedNodeSet &Dst);
305
306  /// Transfer function logic for ObjCAtSynchronizedStmts.
307  void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
308                                   ExplodedNode *Pred, ExplodedNodeSet &Dst);
309
310  /// Transfer function logic for computing the lvalue of an Objective-C ivar.
311  void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
312                                ExplodedNodeSet &Dst);
313
314  /// VisitObjCForCollectionStmt - Transfer function logic for
315  ///  ObjCForCollectionStmt.
316  void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
317                                  ExplodedNode *Pred, ExplodedNodeSet &Dst);
318
319  void VisitObjCMessage(const ObjCMessage &msg, ExplodedNode *Pred,
320                        ExplodedNodeSet &Dst);
321
322  /// VisitReturnStmt - Transfer function logic for return statements.
323  void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred,
324                       ExplodedNodeSet &Dst);
325
326  /// VisitOffsetOfExpr - Transfer function for offsetof.
327  void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred,
328                         ExplodedNodeSet &Dst);
329
330  /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
331  void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
332                              ExplodedNode *Pred, ExplodedNodeSet &Dst);
333
334  /// VisitUnaryOperator - Transfer function logic for unary operators.
335  void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred,
336                          ExplodedNodeSet &Dst);
337
338  void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
339                        ExplodedNodeSet & Dst);
340
341  void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *expr,
342                                   ExplodedNode *Pred, ExplodedNodeSet &Dst) {
343    VisitCXXConstructExpr(expr, 0, Pred, Dst);
344  }
345
346  void VisitCXXConstructExpr(const CXXConstructExpr *E, const MemRegion *Dest,
347                             ExplodedNode *Pred, ExplodedNodeSet &Dst);
348
349  void VisitCXXDestructor(const CXXDestructorDecl *DD,
350                          const MemRegion *Dest, const Stmt *S,
351                          ExplodedNode *Pred, ExplodedNodeSet &Dst);
352
353  void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
354                       ExplodedNodeSet &Dst);
355
356  void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
357                          ExplodedNodeSet &Dst);
358
359  void VisitAggExpr(const Expr *E, const MemRegion *Dest, ExplodedNode *Pred,
360                    ExplodedNodeSet &Dst);
361
362  /// Create a C++ temporary object for an rvalue.
363  void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
364                                ExplodedNode *Pred,
365                                ExplodedNodeSet &Dst);
366
367  /// Synthesize CXXThisRegion.
368  const CXXThisRegion *getCXXThisRegion(const CXXRecordDecl *RD,
369                                        const StackFrameContext *SFC);
370
371  const CXXThisRegion *getCXXThisRegion(const CXXMethodDecl *decl,
372                                        const StackFrameContext *frameCtx);
373
374  /// Evaluate arguments with a work list algorithm.
375  void evalArguments(ConstExprIterator AI, ConstExprIterator AE,
376                     const FunctionProtoType *FnType,
377                     ExplodedNode *Pred, ExplodedNodeSet &Dst,
378                     bool FstArgAsLValue = false);
379
380  /// Evaluate callee expression (for a function call).
381  void evalCallee(const CallExpr *callExpr, const ExplodedNodeSet &src,
382                  ExplodedNodeSet &dest);
383
384  /// evalEagerlyAssume - Given the nodes in 'Src', eagerly assume symbolic
385  ///  expressions of the form 'x != 0' and generate new nodes (stored in Dst)
386  ///  with those assumptions.
387  void evalEagerlyAssume(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
388                         const Expr *Ex);
389
390  std::pair<const ProgramPointTag *, const ProgramPointTag*>
391    getEagerlyAssumeTags();
392
393  SVal evalMinus(SVal X) {
394    return X.isValid() ? svalBuilder.evalMinus(cast<NonLoc>(X)) : X;
395  }
396
397  SVal evalComplement(SVal X) {
398    return X.isValid() ? svalBuilder.evalComplement(cast<NonLoc>(X)) : X;
399  }
400
401public:
402
403  SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op,
404                 NonLoc L, NonLoc R, QualType T) {
405    return svalBuilder.evalBinOpNN(state, op, L, R, T);
406  }
407
408  SVal evalBinOp(const ProgramState *state, BinaryOperator::Opcode op,
409                 NonLoc L, SVal R, QualType T) {
410    return R.isValid() ? svalBuilder.evalBinOpNN(state,op,L, cast<NonLoc>(R), T) : R;
411  }
412
413  SVal evalBinOp(const ProgramState *ST, BinaryOperator::Opcode Op,
414                 SVal LHS, SVal RHS, QualType T) {
415    return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T);
416  }
417
418protected:
419  void evalObjCMessage(ExplodedNodeSet &Dst, const ObjCMessage &msg,
420                       ExplodedNode *Pred, const ProgramState *state);
421
422  const ProgramState *invalidateArguments(const ProgramState *State,
423                                          const CallOrObjCMessage &Call,
424                                          const LocationContext *LC);
425
426  const ProgramState *MarkBranch(const ProgramState *St, const Stmt *Terminator,
427                            bool branchTaken);
428
429  /// evalBind - Handle the semantics of binding a value to a specific location.
430  ///  This method is used by evalStore, VisitDeclStmt, and others.
431  void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred,
432                SVal location, SVal Val, bool atDeclInit = false);
433
434public:
435  // FIXME: 'tag' should be removed, and a LocationContext should be used
436  // instead.
437  // FIXME: Comment on the meaning of the arguments, when 'St' may not
438  // be the same as Pred->state, and when 'location' may not be the
439  // same as state->getLValue(Ex).
440  /// Simulate a read of the result of Ex.
441  void evalLoad(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred,
442                const ProgramState *St, SVal location, const ProgramPointTag *tag = 0,
443                QualType LoadTy = QualType());
444
445  // FIXME: 'tag' should be removed, and a LocationContext should be used
446  // instead.
447  void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE,
448                 ExplodedNode *Pred, const ProgramState *St, SVal TargetLV, SVal Val,
449                 const ProgramPointTag *tag = 0);
450private:
451  void evalLoadCommon(ExplodedNodeSet &Dst, const Expr *Ex, ExplodedNode *Pred,
452                      const ProgramState *St, SVal location, const ProgramPointTag *tag,
453                      QualType LoadTy);
454
455  // FIXME: 'tag' should be removed, and a LocationContext should be used
456  // instead.
457  void evalLocation(ExplodedNodeSet &Dst, const Stmt *S, ExplodedNode *Pred,
458                    const ProgramState *St, SVal location,
459                    const ProgramPointTag *tag, bool isLoad);
460
461  bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred);
462
463
464public:
465  /// Returns true if calling the specific function or method would possibly
466  /// cause global variables to be invalidated.
467  bool doesInvalidateGlobals(const CallOrObjCMessage &callOrMessage) const;
468
469};
470
471} // end ento namespace
472
473} // end clang namespace
474
475#endif
476