clang  9.0.0svn
ExprEngine.h
Go to the documentation of this file.
1 //===- ExprEngine.h - Path-Sensitive Expression-Level Dataflow --*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines a meta-engine for path-sensitive dataflow analysis that
10 // is built on CoreEngine, but provides the boilerplate to execute transfer
11 // functions and build the ExplodedGraph at the expression level.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
16 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
17 
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/Type.h"
20 #include "clang/Analysis/CFG.h"
23 #include "clang/Basic/LLVM.h"
35 #include "llvm/ADT/ArrayRef.h"
36 #include <cassert>
37 #include <utility>
38 
39 namespace clang {
40 
41 class AnalysisDeclContextManager;
42 class AnalyzerOptions;
43 class ASTContext;
44 class ConstructionContext;
45 class CXXBindTemporaryExpr;
46 class CXXCatchStmt;
47 class CXXConstructExpr;
48 class CXXDeleteExpr;
49 class CXXNewExpr;
50 class CXXThisExpr;
51 class Decl;
52 class DeclStmt;
53 class GCCAsmStmt;
54 class LambdaExpr;
55 class LocationContext;
56 class MaterializeTemporaryExpr;
57 class MSAsmStmt;
58 class NamedDecl;
59 class ObjCAtSynchronizedStmt;
60 class ObjCForCollectionStmt;
61 class ObjCIvarRefExpr;
62 class ObjCMessageExpr;
63 class ReturnStmt;
64 class Stmt;
65 
66 namespace cross_tu {
67 
68 class CrossTranslationUnitContext;
69 
70 } // namespace cross_tu
71 
72 namespace ento {
73 
74 class BasicValueFactory;
75 class CallEvent;
76 class CheckerManager;
77 class ConstraintManager;
78 class CXXTempObjectRegion;
79 class MemRegion;
80 class RegionAndSymbolInvalidationTraits;
81 class SymbolManager;
82 
83 class ExprEngine : public SubEngine {
84 public:
85  /// The modes of inlining, which override the default analysis-wide settings.
87  /// Follow the default settings for inlining callees.
88  Inline_Regular = 0,
89 
90  /// Do minimal inlining of callees.
91  Inline_Minimal = 0x1
92  };
93 
94  /// Hints for figuring out of a call should be inlined during evalCall().
95  struct EvalCallOptions {
96  /// This call is a constructor or a destructor for which we do not currently
97  /// compute the this-region correctly.
98  bool IsCtorOrDtorWithImproperlyModeledTargetRegion = false;
99 
100  /// This call is a constructor or a destructor for a single element within
101  /// an array, a part of array construction or destruction.
102  bool IsArrayCtorOrDtor = false;
103 
104  /// This call is a constructor or a destructor of a temporary value.
105  bool IsTemporaryCtorOrDtor = false;
106 
107  /// This call is a constructor for a temporary that is lifetime-extended
108  /// by binding it to a reference-type field within an aggregate,
109  /// for example 'A { const C &c; }; A a = { C() };'
110  bool IsTemporaryLifetimeExtendedViaAggregate = false;
111 
113  };
114 
115 private:
117 
118  AnalysisManager &AMgr;
119 
120  AnalysisDeclContextManager &AnalysisDeclContexts;
121 
122  CoreEngine Engine;
123 
124  /// G - the simulation graph.
125  ExplodedGraph &G;
126 
127  /// StateMgr - Object that manages the data for all created states.
128  ProgramStateManager StateMgr;
129 
130  /// SymMgr - Object that manages the symbol information.
131  SymbolManager &SymMgr;
132 
133  /// MRMgr - MemRegionManager object that creates memory regions.
134  MemRegionManager &MRMgr;
135 
136  /// svalBuilder - SValBuilder object that creates SVals from expressions.
137  SValBuilder &svalBuilder;
138 
139  unsigned int currStmtIdx = 0;
140  const NodeBuilderContext *currBldrCtx = nullptr;
141 
142  /// Helper object to determine if an Objective-C message expression
143  /// implicitly never returns.
144  ObjCNoReturn ObjCNoRet;
145 
146  /// The BugReporter associated with this engine. It is important that
147  /// this object be placed at the very end of member variables so that its
148  /// destructor is called before the rest of the ExprEngine is destroyed.
149  GRBugReporter BR;
150 
151  /// The functions which have been analyzed through inlining. This is owned by
152  /// AnalysisConsumer. It can be null.
153  SetOfConstDecls *VisitedCallees;
154 
155  /// The flag, which specifies the mode of inlining for the engine.
156  InliningModes HowToInline;
157 
158 public:
160  SetOfConstDecls *VisitedCalleesIn,
161  FunctionSummariesTy *FS, InliningModes HowToInlineIn);
162 
163  ~ExprEngine() override;
164 
165  /// Returns true if there is still simulation state on the worklist.
166  bool ExecuteWorkList(const LocationContext *L, unsigned Steps = 150000) {
167  return Engine.ExecuteWorkList(L, Steps, nullptr);
168  }
169 
170  /// Execute the work list with an initial state. Nodes that reaches the exit
171  /// of the function are added into the Dst set, which represent the exit
172  /// state of the function call. Returns true if there is still simulation
173  /// state on the worklist.
174  bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps,
175  ProgramStateRef InitState,
176  ExplodedNodeSet &Dst) {
177  return Engine.ExecuteWorkListWithInitialState(L, Steps, InitState, Dst);
178  }
179 
180  /// getContext - Return the ASTContext associated with this analysis.
181  ASTContext &getContext() const { return AMgr.getASTContext(); }
182 
183  AnalysisManager &getAnalysisManager() override { return AMgr; }
184 
186  return AMgr.getAnalysisDeclContextManager();
187  }
188 
190  return *AMgr.getCheckerManager();
191  }
192 
193  SValBuilder &getSValBuilder() { return svalBuilder; }
194 
195  BugReporter &getBugReporter() { return BR; }
196 
199  return &CTU;
200  }
201 
203  assert(currBldrCtx);
204  return *currBldrCtx;
205  }
206 
207  const Stmt *getStmt() const;
208 
209  void GenerateAutoTransition(ExplodedNode *N);
210  void enqueueEndOfPath(ExplodedNodeSet &S);
211  void GenerateCallExitNode(ExplodedNode *N);
212 
213 
214  /// Dump graph to the specified filename.
215  /// If filename is empty, generate a temporary one.
216  /// \return The filename the graph is written into.
217  std::string DumpGraph(bool trim = false, StringRef Filename="");
218 
219  /// Dump the graph consisting of the given nodes to a specified filename.
220  /// Generate a temporary filename if it's not provided.
221  /// \return The filename the graph is written into.
222  std::string DumpGraph(ArrayRef<const ExplodedNode *> Nodes,
223  StringRef Filename = "");
224 
225  /// Visualize the ExplodedGraph created by executing the simulation.
226  void ViewGraph(bool trim = false);
227 
228  /// Visualize a trimmed ExplodedGraph that only contains paths to the given
229  /// nodes.
230  void ViewGraph(ArrayRef<const ExplodedNode *> Nodes);
231 
232  /// getInitialState - Return the initial state used for the root vertex
233  /// in the ExplodedGraph.
234  ProgramStateRef getInitialState(const LocationContext *InitLoc) override;
235 
236  ExplodedGraph &getGraph() { return G; }
237  const ExplodedGraph &getGraph() const { return G; }
238 
239  /// Run the analyzer's garbage collection - remove dead symbols and
240  /// bindings from the state.
241  ///
242  /// Checkers can participate in this process with two callbacks:
243  /// \c checkLiveSymbols and \c checkDeadSymbols. See the CheckerDocumentation
244  /// class for more information.
245  ///
246  /// \param Node The predecessor node, from which the processing should start.
247  /// \param Out The returned set of output nodes.
248  /// \param ReferenceStmt The statement which is about to be processed.
249  /// Everything needed for this statement should be considered live.
250  /// A null statement means that everything in child LocationContexts
251  /// is dead.
252  /// \param LC The location context of the \p ReferenceStmt. A null location
253  /// context means that we have reached the end of analysis and that
254  /// all statements and local variables should be considered dead.
255  /// \param DiagnosticStmt Used as a location for any warnings that should
256  /// occur while removing the dead (e.g. leaks). By default, the
257  /// \p ReferenceStmt is used.
258  /// \param K Denotes whether this is a pre- or post-statement purge. This
259  /// must only be ProgramPoint::PostStmtPurgeDeadSymbolsKind if an
260  /// entire location context is being cleared, in which case the
261  /// \p ReferenceStmt must either be a ReturnStmt or \c NULL. Otherwise,
262  /// it must be ProgramPoint::PreStmtPurgeDeadSymbolsKind (the default)
263  /// and \p ReferenceStmt must be valid (non-null).
264  void removeDead(ExplodedNode *Node, ExplodedNodeSet &Out,
265  const Stmt *ReferenceStmt, const LocationContext *LC,
266  const Stmt *DiagnosticStmt = nullptr,
268 
269  /// processCFGElement - Called by CoreEngine. Used to generate new successor
270  /// nodes by processing the 'effects' of a CFG element.
271  void processCFGElement(const CFGElement E, ExplodedNode *Pred,
272  unsigned StmtIdx, NodeBuilderContext *Ctx) override;
273 
274  void ProcessStmt(const Stmt *S, ExplodedNode *Pred);
275 
276  void ProcessLoopExit(const Stmt* S, ExplodedNode *Pred);
277 
278  void ProcessInitializer(const CFGInitializer I, ExplodedNode *Pred);
279 
280  void ProcessImplicitDtor(const CFGImplicitDtor D, ExplodedNode *Pred);
281 
282  void ProcessNewAllocator(const CXXNewExpr *NE, ExplodedNode *Pred);
283 
284  void ProcessAutomaticObjDtor(const CFGAutomaticObjDtor D,
285  ExplodedNode *Pred, ExplodedNodeSet &Dst);
286  void ProcessDeleteDtor(const CFGDeleteDtor D,
287  ExplodedNode *Pred, ExplodedNodeSet &Dst);
288  void ProcessBaseDtor(const CFGBaseDtor D,
289  ExplodedNode *Pred, ExplodedNodeSet &Dst);
290  void ProcessMemberDtor(const CFGMemberDtor D,
291  ExplodedNode *Pred, ExplodedNodeSet &Dst);
292  void ProcessTemporaryDtor(const CFGTemporaryDtor D,
293  ExplodedNode *Pred, ExplodedNodeSet &Dst);
294 
295  /// Called by CoreEngine when processing the entrance of a CFGBlock.
296  void processCFGBlockEntrance(const BlockEdge &L,
297  NodeBuilderWithSinks &nodeBuilder,
298  ExplodedNode *Pred) override;
299 
300  /// ProcessBranch - Called by CoreEngine. Used to generate successor
301  /// nodes by processing the 'effects' of a branch condition.
302  void processBranch(const Stmt *Condition,
303  NodeBuilderContext& BuilderCtx,
304  ExplodedNode *Pred,
305  ExplodedNodeSet &Dst,
306  const CFGBlock *DstT,
307  const CFGBlock *DstF) override;
308 
309  /// Called by CoreEngine.
310  /// Used to generate successor nodes for temporary destructors depending
311  /// on whether the corresponding constructor was visited.
312  void processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
313  NodeBuilderContext &BldCtx,
314  ExplodedNode *Pred, ExplodedNodeSet &Dst,
315  const CFGBlock *DstT,
316  const CFGBlock *DstF) override;
317 
318  /// Called by CoreEngine. Used to processing branching behavior
319  /// at static initializers.
320  void processStaticInitializer(const DeclStmt *DS,
321  NodeBuilderContext& BuilderCtx,
322  ExplodedNode *Pred,
323  ExplodedNodeSet &Dst,
324  const CFGBlock *DstT,
325  const CFGBlock *DstF) override;
326 
327  /// processIndirectGoto - Called by CoreEngine. Used to generate successor
328  /// nodes by processing the 'effects' of a computed goto jump.
329  void processIndirectGoto(IndirectGotoNodeBuilder& builder) override;
330 
331  /// ProcessSwitch - Called by CoreEngine. Used to generate successor
332  /// nodes by processing the 'effects' of a switch statement.
333  void processSwitch(SwitchNodeBuilder& builder) override;
334 
335  /// Called by CoreEngine. Used to notify checkers that processing a
336  /// function has begun. Called for both inlined and and top-level functions.
337  void processBeginOfFunction(NodeBuilderContext &BC,
338  ExplodedNode *Pred, ExplodedNodeSet &Dst,
339  const BlockEdge &L) override;
340 
341  /// Called by CoreEngine. Used to notify checkers that processing a
342  /// function has ended. Called for both inlined and and top-level functions.
343  void processEndOfFunction(NodeBuilderContext& BC,
344  ExplodedNode *Pred,
345  const ReturnStmt *RS = nullptr) override;
346 
347  /// Remove dead bindings/symbols before exiting a function.
348  void removeDeadOnEndOfFunction(NodeBuilderContext& BC,
349  ExplodedNode *Pred,
350  ExplodedNodeSet &Dst);
351 
352  /// Generate the entry node of the callee.
353  void processCallEnter(NodeBuilderContext& BC, CallEnter CE,
354  ExplodedNode *Pred) override;
355 
356  /// Generate the sequence of nodes that simulate the call exit and the post
357  /// visit for CallExpr.
358  void processCallExit(ExplodedNode *Pred) override;
359 
360  /// Called by CoreEngine when the analysis worklist has terminated.
361  void processEndWorklist() override;
362 
363  /// evalAssume - Callback function invoked by the ConstraintManager when
364  /// making assumptions about state values.
365  ProgramStateRef processAssume(ProgramStateRef state, SVal cond,
366  bool assumption) override;
367 
368  /// processRegionChanges - Called by ProgramStateManager whenever a change is made
369  /// to the store. Used to update checkers that track region values.
371  processRegionChanges(ProgramStateRef state,
372  const InvalidatedSymbols *invalidated,
373  ArrayRef<const MemRegion *> ExplicitRegions,
375  const LocationContext *LCtx,
376  const CallEvent *Call) override;
377 
378  /// printState - Called by ProgramStateManager to print checker-specific data.
379  void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
380  const char *Sep,
381  const LocationContext *LCtx = nullptr) override;
382 
383  ProgramStateManager &getStateManager() override { return StateMgr; }
384 
385  StoreManager &getStoreManager() { return StateMgr.getStoreManager(); }
386 
388  return StateMgr.getConstraintManager();
389  }
390 
391  // FIXME: Remove when we migrate over to just using SValBuilder.
393  return StateMgr.getBasicVals();
394  }
395 
396  SymbolManager &getSymbolManager() { return SymMgr; }
397  MemRegionManager &getRegionManager() { return MRMgr; }
398 
399 
400  // Functions for external checking of whether we have unfinished work
401  bool wasBlocksExhausted() const { return Engine.wasBlocksExhausted(); }
402  bool hasEmptyWorkList() const { return !Engine.getWorkList()->hasWork(); }
403  bool hasWorkRemaining() const { return Engine.hasWorkRemaining(); }
404 
405  const CoreEngine &getCoreEngine() const { return Engine; }
406 
407 public:
408  /// Visit - Transfer function logic for all statements. Dispatches to
409  /// other functions that handle specific kinds of statements.
410  void Visit(const Stmt *S, ExplodedNode *Pred, ExplodedNodeSet &Dst);
411 
412  /// VisitArraySubscriptExpr - Transfer function for array accesses.
413  void VisitArraySubscriptExpr(const ArraySubscriptExpr *Ex,
414  ExplodedNode *Pred,
415  ExplodedNodeSet &Dst);
416 
417  /// VisitGCCAsmStmt - Transfer function logic for inline asm.
418  void VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
419  ExplodedNodeSet &Dst);
420 
421  /// VisitMSAsmStmt - Transfer function logic for MS inline asm.
422  void VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
423  ExplodedNodeSet &Dst);
424 
425  /// VisitBlockExpr - Transfer function logic for BlockExprs.
426  void VisitBlockExpr(const BlockExpr *BE, ExplodedNode *Pred,
427  ExplodedNodeSet &Dst);
428 
429  /// VisitLambdaExpr - Transfer function logic for LambdaExprs.
430  void VisitLambdaExpr(const LambdaExpr *LE, ExplodedNode *Pred,
431  ExplodedNodeSet &Dst);
432 
433  /// VisitBinaryOperator - Transfer function logic for binary operators.
434  void VisitBinaryOperator(const BinaryOperator* B, ExplodedNode *Pred,
435  ExplodedNodeSet &Dst);
436 
437 
438  /// VisitCall - Transfer function for function calls.
439  void VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
440  ExplodedNodeSet &Dst);
441 
442  /// VisitCast - Transfer function logic for all casts (implicit and explicit).
443  void VisitCast(const CastExpr *CastE, const Expr *Ex, ExplodedNode *Pred,
444  ExplodedNodeSet &Dst);
445 
446  /// VisitCompoundLiteralExpr - Transfer function logic for compound literals.
447  void VisitCompoundLiteralExpr(const CompoundLiteralExpr *CL,
448  ExplodedNode *Pred, ExplodedNodeSet &Dst);
449 
450  /// Transfer function logic for DeclRefExprs and BlockDeclRefExprs.
451  void VisitCommonDeclRefExpr(const Expr *DR, const NamedDecl *D,
452  ExplodedNode *Pred, ExplodedNodeSet &Dst);
453 
454  /// VisitDeclStmt - Transfer function logic for DeclStmts.
455  void VisitDeclStmt(const DeclStmt *DS, ExplodedNode *Pred,
456  ExplodedNodeSet &Dst);
457 
458  /// VisitGuardedExpr - Transfer function logic for ?, __builtin_choose
459  void VisitGuardedExpr(const Expr *Ex, const Expr *L, const Expr *R,
460  ExplodedNode *Pred, ExplodedNodeSet &Dst);
461 
462  void VisitInitListExpr(const InitListExpr *E, ExplodedNode *Pred,
463  ExplodedNodeSet &Dst);
464 
465  /// VisitLogicalExpr - Transfer function logic for '&&', '||'
466  void VisitLogicalExpr(const BinaryOperator* B, ExplodedNode *Pred,
467  ExplodedNodeSet &Dst);
468 
469  /// VisitMemberExpr - Transfer function for member expressions.
470  void VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
471  ExplodedNodeSet &Dst);
472 
473  /// VisitAtomicExpr - Transfer function for builtin atomic expressions
474  void VisitAtomicExpr(const AtomicExpr *E, ExplodedNode *Pred,
475  ExplodedNodeSet &Dst);
476 
477  /// Transfer function logic for ObjCAtSynchronizedStmts.
478  void VisitObjCAtSynchronizedStmt(const ObjCAtSynchronizedStmt *S,
479  ExplodedNode *Pred, ExplodedNodeSet &Dst);
480 
481  /// Transfer function logic for computing the lvalue of an Objective-C ivar.
482  void VisitLvalObjCIvarRefExpr(const ObjCIvarRefExpr *DR, ExplodedNode *Pred,
483  ExplodedNodeSet &Dst);
484 
485  /// VisitObjCForCollectionStmt - Transfer function logic for
486  /// ObjCForCollectionStmt.
487  void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S,
488  ExplodedNode *Pred, ExplodedNodeSet &Dst);
489 
490  void VisitObjCMessage(const ObjCMessageExpr *ME, ExplodedNode *Pred,
491  ExplodedNodeSet &Dst);
492 
493  /// VisitReturnStmt - Transfer function logic for return statements.
494  void VisitReturnStmt(const ReturnStmt *R, ExplodedNode *Pred,
495  ExplodedNodeSet &Dst);
496 
497  /// VisitOffsetOfExpr - Transfer function for offsetof.
498  void VisitOffsetOfExpr(const OffsetOfExpr *Ex, ExplodedNode *Pred,
499  ExplodedNodeSet &Dst);
500 
501  /// VisitUnaryExprOrTypeTraitExpr - Transfer function for sizeof.
502  void VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *Ex,
503  ExplodedNode *Pred, ExplodedNodeSet &Dst);
504 
505  /// VisitUnaryOperator - Transfer function logic for unary operators.
506  void VisitUnaryOperator(const UnaryOperator* B, ExplodedNode *Pred,
507  ExplodedNodeSet &Dst);
508 
509  /// Handle ++ and -- (both pre- and post-increment).
510  void VisitIncrementDecrementOperator(const UnaryOperator* U,
511  ExplodedNode *Pred,
512  ExplodedNodeSet &Dst);
513 
514  void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
515  ExplodedNodeSet &PreVisit,
516  ExplodedNodeSet &Dst);
517 
518  void VisitCXXCatchStmt(const CXXCatchStmt *CS, ExplodedNode *Pred,
519  ExplodedNodeSet &Dst);
520 
521  void VisitCXXThisExpr(const CXXThisExpr *TE, ExplodedNode *Pred,
522  ExplodedNodeSet & Dst);
523 
524  void VisitCXXConstructExpr(const CXXConstructExpr *E, ExplodedNode *Pred,
525  ExplodedNodeSet &Dst);
526 
527  void VisitCXXDestructor(QualType ObjectType, const MemRegion *Dest,
528  const Stmt *S, bool IsBaseDtor,
529  ExplodedNode *Pred, ExplodedNodeSet &Dst,
530  const EvalCallOptions &Options);
531 
532  void VisitCXXNewAllocatorCall(const CXXNewExpr *CNE,
533  ExplodedNode *Pred,
534  ExplodedNodeSet &Dst);
535 
536  void VisitCXXNewExpr(const CXXNewExpr *CNE, ExplodedNode *Pred,
537  ExplodedNodeSet &Dst);
538 
539  void VisitCXXDeleteExpr(const CXXDeleteExpr *CDE, ExplodedNode *Pred,
540  ExplodedNodeSet &Dst);
541 
542  /// Create a C++ temporary object for an rvalue.
543  void CreateCXXTemporaryObject(const MaterializeTemporaryExpr *ME,
544  ExplodedNode *Pred,
545  ExplodedNodeSet &Dst);
546 
547  /// evalEagerlyAssumeBinOpBifurcation - Given the nodes in 'Src', eagerly assume symbolic
548  /// expressions of the form 'x != 0' and generate new nodes (stored in Dst)
549  /// with those assumptions.
550  void evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst, ExplodedNodeSet &Src,
551  const Expr *Ex);
552 
553  static std::pair<const ProgramPointTag *, const ProgramPointTag *>
554  geteagerlyAssumeBinOpBifurcationTags();
555 
557  return X.isValid() ? svalBuilder.evalMinus(X.castAs<NonLoc>()) : X;
558  }
559 
561  return X.isValid() ? svalBuilder.evalComplement(X.castAs<NonLoc>()) : X;
562  }
563 
564  ProgramStateRef handleLValueBitCast(ProgramStateRef state, const Expr *Ex,
565  const LocationContext *LCtx, QualType T,
566  QualType ExTy, const CastExpr *CastE,
567  StmtNodeBuilder &Bldr,
568  ExplodedNode *Pred);
569 
570  ProgramStateRef handleLVectorSplat(ProgramStateRef state,
571  const LocationContext *LCtx,
572  const CastExpr *CastE,
573  StmtNodeBuilder &Bldr,
574  ExplodedNode *Pred);
575 
576  void handleUOExtension(ExplodedNodeSet::iterator I,
577  const UnaryOperator* U,
578  StmtNodeBuilder &Bldr);
579 
580 public:
582  NonLoc L, NonLoc R, QualType T) {
583  return svalBuilder.evalBinOpNN(state, op, L, R, T);
584  }
585 
587  NonLoc L, SVal R, QualType T) {
588  return R.isValid() ? svalBuilder.evalBinOpNN(state, op, L,
589  R.castAs<NonLoc>(), T) : R;
590  }
591 
593  SVal LHS, SVal RHS, QualType T) {
594  return svalBuilder.evalBinOp(ST, Op, LHS, RHS, T);
595  }
596 
597  /// By looking at a certain item that may be potentially part of an object's
598  /// ConstructionContext, retrieve such object's location. A particular
599  /// statement can be transparently passed as \p Item in most cases.
600  static Optional<SVal>
601  getObjectUnderConstruction(ProgramStateRef State,
602  const ConstructionContextItem &Item,
603  const LocationContext *LC);
604 
605 protected:
606  /// evalBind - Handle the semantics of binding a value to a specific location.
607  /// This method is used by evalStore, VisitDeclStmt, and others.
608  void evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE, ExplodedNode *Pred,
609  SVal location, SVal Val, bool atDeclInit = false,
610  const ProgramPoint *PP = nullptr);
611 
612  /// Call PointerEscape callback when a value escapes as a result of bind.
613  ProgramStateRef processPointerEscapedOnBind(ProgramStateRef State,
614  SVal Loc,
615  SVal Val,
616  const LocationContext *LCtx) override;
617  /// Call PointerEscape callback when a value escapes as a result of
618  /// region invalidation.
619  /// \param[in] ITraits Specifies invalidation traits for regions/symbols.
620  ProgramStateRef notifyCheckersOfPointerEscape(
621  ProgramStateRef State,
622  const InvalidatedSymbols *Invalidated,
623  ArrayRef<const MemRegion *> ExplicitRegions,
624  const CallEvent *Call,
625  RegionAndSymbolInvalidationTraits &ITraits) override;
626 
627  /// A simple wrapper when you only need to notify checkers of pointer-escape
628  /// of a single value.
629  ProgramStateRef escapeValue(ProgramStateRef State, SVal V,
630  PointerEscapeKind K) const;
631 
632 public:
633  // FIXME: 'tag' should be removed, and a LocationContext should be used
634  // instead.
635  // FIXME: Comment on the meaning of the arguments, when 'St' may not
636  // be the same as Pred->state, and when 'location' may not be the
637  // same as state->getLValue(Ex).
638  /// Simulate a read of the result of Ex.
639  void evalLoad(ExplodedNodeSet &Dst,
640  const Expr *NodeEx, /* Eventually will be a CFGStmt */
641  const Expr *BoundExpr,
642  ExplodedNode *Pred,
643  ProgramStateRef St,
644  SVal location,
645  const ProgramPointTag *tag = nullptr,
646  QualType LoadTy = QualType());
647 
648  // FIXME: 'tag' should be removed, and a LocationContext should be used
649  // instead.
650  void evalStore(ExplodedNodeSet &Dst, const Expr *AssignE, const Expr *StoreE,
651  ExplodedNode *Pred, ProgramStateRef St, SVal TargetLV, SVal Val,
652  const ProgramPointTag *tag = nullptr);
653 
654  /// Return the CFG element corresponding to the worklist element
655  /// that is currently being processed by ExprEngine.
657  return (*currBldrCtx->getBlock())[currStmtIdx];
658  }
659 
660  /// Create a new state in which the call return value is binded to the
661  /// call origin expression.
662  ProgramStateRef bindReturnValue(const CallEvent &Call,
663  const LocationContext *LCtx,
664  ProgramStateRef State);
665 
666  /// Evaluate a call, running pre- and post-call checks and allowing checkers
667  /// to be responsible for handling the evaluation of the call itself.
668  void evalCall(ExplodedNodeSet &Dst, ExplodedNode *Pred,
669  const CallEvent &Call);
670 
671  /// Default implementation of call evaluation.
672  void defaultEvalCall(NodeBuilder &B, ExplodedNode *Pred,
673  const CallEvent &Call,
674  const EvalCallOptions &CallOpts = {});
675 
676 private:
677  ProgramStateRef finishArgumentConstruction(ProgramStateRef State,
678  const CallEvent &Call);
679  void finishArgumentConstruction(ExplodedNodeSet &Dst, ExplodedNode *Pred,
680  const CallEvent &Call);
681 
682  void evalLoadCommon(ExplodedNodeSet &Dst,
683  const Expr *NodeEx, /* Eventually will be a CFGStmt */
684  const Expr *BoundEx,
685  ExplodedNode *Pred,
686  ProgramStateRef St,
687  SVal location,
688  const ProgramPointTag *tag,
689  QualType LoadTy);
690 
691  void evalLocation(ExplodedNodeSet &Dst,
692  const Stmt *NodeEx, /* This will eventually be a CFGStmt */
693  const Stmt *BoundEx,
694  ExplodedNode *Pred,
695  ProgramStateRef St,
696  SVal location,
697  bool isLoad);
698 
699  /// Count the stack depth and determine if the call is recursive.
700  void examineStackFrames(const Decl *D, const LocationContext *LCtx,
701  bool &IsRecursive, unsigned &StackDepth);
702 
703  enum CallInlinePolicy {
704  CIP_Allowed,
705  CIP_DisallowedOnce,
706  CIP_DisallowedAlways
707  };
708 
709  /// See if a particular call should be inlined, by only looking
710  /// at the call event and the current state of analysis.
711  CallInlinePolicy mayInlineCallKind(const CallEvent &Call,
712  const ExplodedNode *Pred,
713  AnalyzerOptions &Opts,
714  const EvalCallOptions &CallOpts);
715 
716  /// Checks our policies and decides weither the given call should be inlined.
717  bool shouldInlineCall(const CallEvent &Call, const Decl *D,
718  const ExplodedNode *Pred,
719  const EvalCallOptions &CallOpts = {});
720 
721  bool inlineCall(const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
722  ExplodedNode *Pred, ProgramStateRef State);
723 
724  /// Conservatively evaluate call by invalidating regions and binding
725  /// a conjured return value.
726  void conservativeEvalCall(const CallEvent &Call, NodeBuilder &Bldr,
727  ExplodedNode *Pred, ProgramStateRef State);
728 
729  /// Either inline or process the call conservatively (or both), based
730  /// on DynamicDispatchBifurcation data.
731  void BifurcateCall(const MemRegion *BifurReg,
732  const CallEvent &Call, const Decl *D, NodeBuilder &Bldr,
733  ExplodedNode *Pred);
734 
735  bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC);
736 
737  /// Models a trivial copy or move constructor or trivial assignment operator
738  /// call with a simple bind.
739  void performTrivialCopy(NodeBuilder &Bldr, ExplodedNode *Pred,
740  const CallEvent &Call);
741 
742  /// If the value of the given expression \p InitWithAdjustments is a NonLoc,
743  /// copy it into a new temporary object region, and replace the value of the
744  /// expression with that.
745  ///
746  /// If \p Result is provided, the new region will be bound to this expression
747  /// instead of \p InitWithAdjustments.
748  ///
749  /// Returns the temporary region with adjustments into the optional
750  /// OutRegionWithAdjustments out-parameter if a new region was indeed needed,
751  /// otherwise sets it to nullptr.
752  ProgramStateRef createTemporaryRegionIfNeeded(
753  ProgramStateRef State, const LocationContext *LC,
754  const Expr *InitWithAdjustments, const Expr *Result = nullptr,
755  const SubRegion **OutRegionWithAdjustments = nullptr);
756 
757  /// Returns a region representing the first element of a (possibly
758  /// multi-dimensional) array, for the purposes of element construction or
759  /// destruction.
760  ///
761  /// On return, \p Ty will be set to the base type of the array.
762  ///
763  /// If the type is not an array type at all, the original value is returned.
764  /// Otherwise the "IsArray" flag is set.
765  static SVal makeZeroElementRegion(ProgramStateRef State, SVal LValue,
766  QualType &Ty, bool &IsArray);
767 
768  /// For a DeclStmt or CXXInitCtorInitializer, walk backward in the current CFG
769  /// block to find the constructor expression that directly constructed into
770  /// the storage for this statement. Returns null if the constructor for this
771  /// statement created a temporary object region rather than directly
772  /// constructing into an existing region.
773  const CXXConstructExpr *findDirectConstructorForCurrentCFGElement();
774 
775  /// Update the program state with all the path-sensitive information
776  /// that's necessary to perform construction of an object with a given
777  /// syntactic construction context. If the construction context is unavailable
778  /// or unusable for any reason, a dummy temporary region is returned, and the
779  /// IsConstructorWithImproperlyModeledTargetRegion flag is set in \p CallOpts.
780  /// Returns the updated program state and the new object's this-region.
781  std::pair<ProgramStateRef, SVal> prepareForObjectConstruction(
782  const Expr *E, ProgramStateRef State, const LocationContext *LCtx,
783  const ConstructionContext *CC, EvalCallOptions &CallOpts);
784 
785  /// Store the location of a C++ object corresponding to a statement
786  /// until the statement is actually encountered. For example, if a DeclStmt
787  /// has CXXConstructExpr as its initializer, the object would be considered
788  /// to be "under construction" between CXXConstructExpr and DeclStmt.
789  /// This allows, among other things, to keep bindings to variable's fields
790  /// made within the constructor alive until its declaration actually
791  /// goes into scope.
792  static ProgramStateRef
793  addObjectUnderConstruction(ProgramStateRef State,
794  const ConstructionContextItem &Item,
795  const LocationContext *LC, SVal V);
796 
797  /// Mark the object sa fully constructed, cleaning up the state trait
798  /// that tracks objects under construction.
799  static ProgramStateRef
800  finishObjectConstruction(ProgramStateRef State,
801  const ConstructionContextItem &Item,
802  const LocationContext *LC);
803 
804  /// If the given expression corresponds to a temporary that was used for
805  /// passing into an elidable copy/move constructor and that constructor
806  /// was actually elided, track that we also need to elide the destructor.
807  static ProgramStateRef elideDestructor(ProgramStateRef State,
808  const CXXBindTemporaryExpr *BTE,
809  const LocationContext *LC);
810 
811  /// Stop tracking the destructor that corresponds to an elided constructor.
812  static ProgramStateRef
813  cleanupElidedDestructor(ProgramStateRef State,
814  const CXXBindTemporaryExpr *BTE,
815  const LocationContext *LC);
816 
817  /// Returns true if the given expression corresponds to a temporary that
818  /// was constructed for passing into an elidable copy/move constructor
819  /// and that constructor was actually elided.
820  static bool isDestructorElided(ProgramStateRef State,
821  const CXXBindTemporaryExpr *BTE,
822  const LocationContext *LC);
823 
824  /// Check if all objects under construction have been fully constructed
825  /// for the given context range (including FromLC, not including ToLC).
826  /// This is useful for assertions. Also checks if elided destructors
827  /// were cleaned up.
828  static bool areAllObjectsFullyConstructed(ProgramStateRef State,
829  const LocationContext *FromLC,
830  const LocationContext *ToLC);
831 };
832 
833 /// Traits for storing the call processing policy inside GDM.
834 /// The GDM stores the corresponding CallExpr pointer.
835 // FIXME: This does not use the nice trait macros because it must be accessible
836 // from multiple translation units.
838 template <>
840  public ProgramStatePartialTrait<const void*> {
841  static void *GDMIndex();
842 };
843 
844 } // namespace ento
845 
846 } // namespace clang
847 
848 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPRENGINE_H
MemRegionManager & getRegionManager()
Definition: ExprEngine.h:397
AnalysisDeclContextManager & getAnalysisDeclContextManager()
This represents a GCC inline-assembly statement extension.
Definition: Stmt.h:2708
A (possibly-)qualified type.
Definition: Type.h:639
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
CheckerManager * getCheckerManager() const
bool ExecuteWorkList(const LocationContext *L, unsigned Steps, ProgramStateRef InitState)
ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
Definition: CoreEngine.cpp:80
Stmt - This represents one statement.
Definition: Stmt.h:65
Information about invalidation for a particular region/symbol.
Definition: MemRegion.h:1439
BasicValueFactory & getBasicVals()
Definition: ProgramState.h:537
This builder class is useful for generating nodes that resulted from visiting a statement.
Definition: CoreEngine.h:369
C Language Family Type Representation.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:631
StringRef P
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Execute the work list with an initial state.
Definition: ExprEngine.h:174
SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc L, NonLoc R, QualType T)
Definition: ExprEngine.h:581
Represents C++ object destructor generated from a call to delete.
Definition: CFG.h:408
Hints for figuring out of a call should be inlined during evalCall().
Definition: ExprEngine.h:95
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1261
The l-value was an access to a declared entity or something equivalently strong, like the address of ...
Represents a prvalue temporary that is written into memory so that a reference can bind to it...
Definition: ExprCXX.h:4155
cross_tu::CrossTranslationUnitContext * getCrossTranslationUnitContext() override
Definition: ExprEngine.h:198
CompoundLiteralExpr - [C99 6.5.2.5].
Definition: Expr.h:2963
const NodeBuilderContext & getBuilderContext()
Definition: ExprEngine.h:202
bool ExecuteWorkListWithInitialState(const LocationContext *L, unsigned Steps, ProgramStateRef InitState, ExplodedNodeSet &Dst)
Returns true if there is still simulation state on the worklist.
Definition: CoreEngine.cpp:197
BoundNodesTreeBuilder Nodes
bool hasWorkRemaining() const
Definition: CoreEngine.h:154
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:154
LineState State
Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...
Definition: CFG.h:383
bool hasEmptyWorkList() const
Definition: ExprEngine.h:402
bool wasBlocksExhausted() const
Definition: ExprEngine.h:401
i32 captured_struct **param SharedsTy A type which contains references the shared variables *param Shareds Context with the list of shared variables from the p *TaskFunction *param Data Additional data for task generation like final * state
AnalysisDeclContextManager & getAnalysisDeclContextManager()
Definition: ExprEngine.h:185
Describes an C or C++ initializer list.
Definition: Expr.h:4214
BinaryOperatorKind
WorkList * getWorkList() const
Definition: CoreEngine.h:164
CFGElement getCurrentCFGElement()
Return the CFG element corresponding to the worklist element that is currently being processed by Exp...
Definition: ExprEngine.h:656
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3313
const CoreEngine & getCoreEngine() const
Definition: ExprEngine.h:405
CastExpr - Base class for type casts, including both implicit casts (ImplicitCastExpr) and explicit c...
Definition: Expr.h:3036
Represents binding an expression to a temporary.
Definition: ExprCXX.h:1216
SVal evalComplement(SVal X)
Definition: ExprEngine.h:560
A C++ lambda expression, which produces a function object (of unspecified type) that can be invoked l...
Definition: ExprCXX.h:1648
ASTContext & getASTContext() override
Represents the this expression in C++.
Definition: ExprCXX.h:975
CheckerManager & getCheckerManager() const
Definition: ExprEngine.h:189
StringRef Filename
Definition: Format.cpp:1667
UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand...
Definition: Expr.h:2255
SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op, SVal LHS, SVal RHS, QualType T)
Definition: ExprEngine.h:592
Represents a single basic block in a source-level CFG.
Definition: CFG.h:551
InliningModes
The modes of inlining, which override the default analysis-wide settings.
Definition: ExprEngine.h:86
This represents one expression.
Definition: Expr.h:108
virtual SVal evalMinus(NonLoc val)=0
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:5384
This is the simplest builder which generates nodes in the ExplodedGraph.
Definition: CoreEngine.h:227
bool isValid() const
Definition: SVals.h:148
Represents Objective-C&#39;s @synchronized statement.
Definition: StmtObjC.h:261
ASTContext & getContext() const
getContext - Return the ASTContext associated with this analysis.
Definition: ExprEngine.h:181
Traits for storing the call processing policy inside GDM.
Definition: ExprEngine.h:837
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
Definition: Stmt.h:2476
SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type)
An expression that sends a message to the given Objective-C object or class.
Definition: ExprObjC.h:903
This represents a Microsoft inline-assembly statement extension.
Definition: Stmt.h:2883
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:1929
Represents C++ object destructor implicitly generated for base object in destructor.
Definition: CFG.h:434
SymbolManager & getSymbolManager()
Definition: ExprEngine.h:396
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:411
ProgramPoints can be "tagged" as representing points specific to a given analysis entity...
Definition: ProgramPoint.h:39
AnalysisManager & getAnalysisManager() override
Definition: ExprEngine.h:183
bool wasBlocksExhausted() const
Definition: CoreEngine.h:153
Represents a new-expression for memory allocation and constructor calls, e.g: "new CXXNewExpr(foo)"...
Definition: ExprCXX.h:1913
virtual bool hasWork() const =0
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:1153
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:75
AtomicExpr - Variadic atomic builtins: __atomic_exchange, __atomic_fetch_*, __atomic_load, __atomic_store, and __atomic_compare_exchange_*, for the similarly-named C++11 instructions, and __c11 variants for <stdatomic.h>, and corresponding __opencl_atomic_* for OpenCL 2.0.
Definition: Expr.h:5640
BugReporter & getBugReporter()
Definition: ExprEngine.h:195
BasicValueFactory & getBasicVals()
Definition: ExprEngine.h:392
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0
Create a new value which represents a binary expression with two non- location operands.
bool ExecuteWorkList(const LocationContext *L, unsigned Steps=150000)
Returns true if there is still simulation state on the worklist.
Definition: ExprEngine.h:166
ast_type_traits::DynTypedNode Node
CoreEngine - Implements the core logic of the graph-reachability analysis.
Definition: CoreEngine.h:54
Dataflow Directional Tag Classes.
SValBuilder & getSValBuilder()
Definition: ExprEngine.h:193
Represents a delete expression for memory deallocation and destructor calls, e.g. ...
Definition: ExprCXX.h:2169
StoreManager & getStoreManager()
Definition: ExprEngine.h:385
bool hasWorkRemaining() const
Definition: ExprEngine.h:403
This node builder keeps track of the generated sink nodes.
Definition: CoreEngine.h:332
const ExplodedGraph & getGraph() const
Definition: ExprEngine.h:237
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:170
ProgramStateManager & getStateManager() override
Definition: ExprEngine.h:383
This class is used for tools that requires cross translation unit capability.
Represents a single point (AST node) in the program that requires attention during construction of an...
PointerEscapeKind
Describes the different reasons a pointer escapes during analysis.
ConstraintManager & getConstraintManager()
Definition: ProgramState.h:564
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition: SVals.h:103
SVal evalMinus(SVal X)
Definition: ExprEngine.h:556
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2345
SubRegion - A region that subsets another larger region.
Definition: MemRegion.h:435
Represents Objective-C&#39;s collection statement.
Definition: StmtObjC.h:23
Stores options for the analyzer from the command line.
ObjCIvarRefExpr - A reference to an ObjC instance variable.
Definition: ExprObjC.h:512
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:14015
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:2720
ConstructionContext&#39;s subclasses describe different ways of constructing an object in C++...
virtual SVal evalComplement(NonLoc val)=0
Represents C++ object destructor implicitly generated by compiler on various occasions.
Definition: CFG.h:358
SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc L, SVal R, QualType T)
Definition: ExprEngine.h:586
CXXCatchStmt - This represents a C++ catch block.
Definition: StmtCXX.h:28
Represents a top-level expression in a basic block.
Definition: CFG.h:55
GRBugReporter is used for generating path-sensitive reports.
Definition: BugReporter.h:512
Represents C++ object destructor implicitly generated for member object in destructor.
Definition: CFG.h:455
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2429
Represents C++ base or member initializer from constructor&#39;s initialization list. ...
Definition: CFG.h:219
ExplodedGraph & getGraph()
Definition: ExprEngine.h:236
This represents a decl that may have a name.
Definition: Decl.h:248
ConstraintManager & getConstraintManager()
Definition: ExprEngine.h:387
OffsetOfExpr - [C99 7.17] - This represents an expression of the form offsetof(record-type, member-designator).
Definition: Expr.h:2150
Represents C++ object destructor implicitly generated at the end of full expression for temporary obj...
Definition: CFG.h:476
const CFGBlock * getBlock() const
Return the CFGBlock associated with this builder.
Definition: CoreEngine.h:207