ExprEngine.h source code [clang_source_code/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h]

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"
21	#include "clang/Analysis/DomainSpecific/ObjCNoReturn.h"
22	#include "clang/Analysis/ProgramPoint.h"
23	#include "clang/Basic/LLVM.h"
24	#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
25	#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
26	#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
27	#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
28	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
29	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
30	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
31	#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
32	#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
33	#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
34	#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.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.
86	enum InliningModes {
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
112	EvalCallOptions() {}
113	};
114
115	private:
116	cross_tu::CrossTranslationUnitContext &CTU;
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:
159	ExprEngine(cross_tu::CrossTranslationUnitContext &CTU, AnalysisManager &mgr,
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
185	AnalysisDeclContextManager &getAnalysisDeclContextManager() {
186	return AMgr.getAnalysisDeclContextManager();
187	}
188
189	CheckerManager &getCheckerManager() const {
190	return *AMgr.getCheckerManager();
191	}
192
193	SValBuilder &getSValBuilder() { return svalBuilder; }
194
195	BugReporter &getBugReporter() { return BR; }
196
197	cross_tu::CrossTranslationUnitContext *
198	getCrossTranslationUnitContext() override {
199	return &CTU;
200	}
201
202	const NodeBuilderContext &getBuilderContext() {
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,
267	ProgramPoint::Kind K = ProgramPoint::PreStmtPurgeDeadSymbolsKind);
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.
370	ProgramStateRef
371	processRegionChanges(ProgramStateRef state,
372	const InvalidatedSymbols *invalidated,
373	ArrayRef<const MemRegion *> ExplicitRegions,
374	ArrayRef<const MemRegion *> Regions,
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
387	ConstraintManager &getConstraintManager() {
388	return StateMgr.getConstraintManager();
389	}
390
391	// FIXME: Remove when we migrate over to just using SValBuilder.
392	BasicValueFactory &getBasicVals() {
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
556	SVal evalMinus(SVal X) {
557	return X.isValid() ? svalBuilder.evalMinus(X.castAs<NonLoc>()) : X;
558	}
559
560	SVal evalComplement(SVal X) {
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:
581	SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
582	NonLoc L, NonLoc R, QualType T) {
583	return svalBuilder.evalBinOpNN(state, op, L, R, T);
584	}
585
586	SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op,
587	NonLoc L, SVal R, QualType T) {
588	return R.isValid() ? svalBuilder.evalBinOpNN(state, op, L,
589	R.castAs<NonLoc>(), T) : R;
590	}
591
592	SVal evalBinOp(ProgramStateRef ST, BinaryOperator::Opcode Op,
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.
656	CFGElement getCurrentCFGElement() {
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.
837	struct ReplayWithoutInlining{};
838	template <>
839	struct ProgramStateTrait<ReplayWithoutInlining> :
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
849