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

1	//===- CoreEngine.h - Path-Sensitive Dataflow Engine ------------- 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 generic engine for intraprocedural, path-sensitive,
10	// dataflow analysis via graph reachability.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
15	#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
16
17	#include "clang/AST/Stmt.h"
18	#include "clang/Analysis/AnalysisDeclContext.h"
19	#include "clang/Analysis/CFG.h"
20	#include "clang/Analysis/ProgramPoint.h"
21	#include "clang/Basic/LLVM.h"
22	#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
23	#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
24	#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
25	#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
26	#include "llvm/ADT/SmallVector.h"
27	#include "llvm/Support/Casting.h"
28	#include <cassert>
29	#include <memory>
30	#include <utility>
31	#include <vector>
32
33	namespace clang {
34
35	class AnalyzerOptions;
36	class CXXBindTemporaryExpr;
37	class Expr;
38	class LabelDecl;
39
40	namespace ento {
41
42	class FunctionSummariesTy;
43	class SubEngine;
44
45	//===----------------------------------------------------------------------===//
46	/// CoreEngine - Implements the core logic of the graph-reachability
47	/// analysis. It traverses the CFG and generates the ExplodedGraph.
48	/// Program "states" are treated as opaque void pointers.
49	/// The template class CoreEngine (which subclasses CoreEngine)
50	/// provides the matching component to the engine that knows the actual types
51	/// for states. Note that this engine only dispatches to transfer functions
52	/// at the statement and block-level. The analyses themselves must implement
53	/// any transfer function logic and the sub-expression level (if any).
54	class CoreEngine {
55	friend class CommonNodeBuilder;
56	friend class EndOfFunctionNodeBuilder;
57	friend class ExprEngine;
58	friend class IndirectGotoNodeBuilder;
59	friend class NodeBuilder;
60	friend struct NodeBuilderContext;
61	friend class SwitchNodeBuilder;
62
63	public:
64	using BlocksExhausted =
65	std::vector<std::pair<BlockEdge, const ExplodedNode *>>;
66
67	using BlocksAborted =
68	std::vector<std::pair<const CFGBlock , const ExplodedNode >>;
69
70	private:
71	SubEngine &SubEng;
72
73	/// G - The simulation graph. Each node is a (location,state) pair.
74	mutable ExplodedGraph G;
75
76	/// WList - A set of queued nodes that need to be processed by the
77	/// worklist algorithm. It is up to the implementation of WList to decide
78	/// the order that nodes are processed.
79	std::unique_ptr<WorkList> WList;
80
81	/// BCounterFactory - A factory object for created BlockCounter objects.
82	/// These are used to record for key nodes in the ExplodedGraph the
83	/// number of times different CFGBlocks have been visited along a path.
84	BlockCounter::Factory BCounterFactory;
85
86	/// The locations where we stopped doing work because we visited a location
87	/// too many times.
88	BlocksExhausted blocksExhausted;
89
90	/// The locations where we stopped because the engine aborted analysis,
91	/// usually because it could not reason about something.
92	BlocksAborted blocksAborted;
93
94	/// The information about functions shared by the whole translation unit.
95	/// (This data is owned by AnalysisConsumer.)
96	FunctionSummariesTy *FunctionSummaries;
97
98	void generateNode(const ProgramPoint &Loc,
99	ProgramStateRef State,
100	ExplodedNode *Pred);
101
102	void HandleBlockEdge(const BlockEdge &E, ExplodedNode *Pred);
103	void HandleBlockEntrance(const BlockEntrance &E, ExplodedNode *Pred);
104	void HandleBlockExit(const CFGBlock B, ExplodedNode Pred);
105
106	void HandleCallEnter(const CallEnter &CE, ExplodedNode *Pred);
107
108	void HandlePostStmt(const CFGBlock B, unsigned StmtIdx, ExplodedNode Pred);
109
110	void HandleBranch(const Stmt Cond, const Stmt Term, const CFGBlock *B,
111	ExplodedNode *Pred);
112	void HandleCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
113	const CFGBlock B, ExplodedNode Pred);
114
115	/// Handle conditional logic for running static initializers.
116	void HandleStaticInit(const DeclStmt DS, const CFGBlock B,
117	ExplodedNode *Pred);
118
119	private:
120	ExplodedNode generateCallExitBeginNode(ExplodedNode N,
121	const ReturnStmt *RS);
122
123	public:
124	/// Construct a CoreEngine object to analyze the provided CFG.
125	CoreEngine(SubEngine &subengine,
126	FunctionSummariesTy *FS,
127	AnalyzerOptions &Opts);
128
129	CoreEngine(const CoreEngine &) = delete;
130	CoreEngine &operator=(const CoreEngine &) = delete;
131
132	/// getGraph - Returns the exploded graph.
133	ExplodedGraph &getGraph() { return G; }
134
135	/// ExecuteWorkList - Run the worklist algorithm for a maximum number of
136	/// steps. Returns true if there is still simulation state on the worklist.
137	bool ExecuteWorkList(const LocationContext *L, unsigned Steps,
138	ProgramStateRef InitState);
139
140	/// Returns true if there is still simulation state on the worklist.
141	bool ExecuteWorkListWithInitialState(const LocationContext *L,
142	unsigned Steps,
143	ProgramStateRef InitState,
144	ExplodedNodeSet &Dst);
145
146	/// Dispatch the work list item based on the given location information.
147	/// Use Pred parameter as the predecessor state.
148	void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
149	const WorkListUnit& WU);
150
151	// Functions for external checking of whether we have unfinished work
152	bool wasBlockAborted() const { return !blocksAborted.empty(); }
153	bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
154	bool hasWorkRemaining() const { return wasBlocksExhausted() \|\|
155	WList->hasWork() \|\|
156	wasBlockAborted(); }
157
158	/// Inform the CoreEngine that a basic block was aborted because
159	/// it could not be completely analyzed.
160	void addAbortedBlock(const ExplodedNode node, const CFGBlock block) {
161	blocksAborted.push_back(std::make_pair(block, node));
162	}
163
164	WorkList *getWorkList() const { return WList.get(); }
165
166	BlocksExhausted::const_iterator blocks_exhausted_begin() const {
167	return blocksExhausted.begin();
168	}
169
170	BlocksExhausted::const_iterator blocks_exhausted_end() const {
171	return blocksExhausted.end();
172	}
173
174	BlocksAborted::const_iterator blocks_aborted_begin() const {
175	return blocksAborted.begin();
176	}
177
178	BlocksAborted::const_iterator blocks_aborted_end() const {
179	return blocksAborted.end();
180	}
181
182	/// Enqueue the given set of nodes onto the work list.
183	void enqueue(ExplodedNodeSet &Set);
184
185	/// Enqueue nodes that were created as a result of processing
186	/// a statement onto the work list.
187	void enqueue(ExplodedNodeSet &Set, const CFGBlock *Block, unsigned Idx);
188
189	/// enqueue the nodes corresponding to the end of function onto the
190	/// end of path / work list.
191	void enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS);
192
193	/// Enqueue a single node created as a result of statement processing.
194	void enqueueStmtNode(ExplodedNode N, const CFGBlock Block, unsigned Idx);
195	};
196
197	// TODO: Turn into a class.
198	struct NodeBuilderContext {
199	const CoreEngine &Eng;
200	const CFGBlock *Block;
201	const LocationContext *LC;
202
203	NodeBuilderContext(const CoreEngine &E, const CFGBlock B, ExplodedNode N)
204	: Eng(E), Block(B), LC(N->getLocationContext()) { assert(B); }
205
206	/// Return the CFGBlock associated with this builder.
207	const CFGBlock *getBlock() const { return Block; }
208
209	/// Returns the number of times the current basic block has been
210	/// visited on the exploded graph path.
211	unsigned blockCount() const {
212	return Eng.WList->getBlockCounter().getNumVisited(
213	LC->getStackFrame(),
214	Block->getBlockID());
215	}
216	};
217
218	/// \class NodeBuilder
219	/// This is the simplest builder which generates nodes in the
220	/// ExplodedGraph.
221	///
222	/// The main benefit of the builder is that it automatically tracks the
223	/// frontier nodes (or destination set). This is the set of nodes which should
224	/// be propagated to the next step / builder. They are the nodes which have been
225	/// added to the builder (either as the input node set or as the newly
226	/// constructed nodes) but did not have any outgoing transitions added.
227	class NodeBuilder {
228	virtual void anchor();
229
230	protected:
231	const NodeBuilderContext &C;
232
233	/// Specifies if the builder results have been finalized. For example, if it
234	/// is set to false, autotransitions are yet to be generated.
235	bool Finalized;
236
237	bool HasGeneratedNodes = false;
238
239	/// The frontier set - a set of nodes which need to be propagated after
240	/// the builder dies.
241	ExplodedNodeSet &Frontier;
242
243	/// Checks if the results are ready.
244	virtual bool checkResults() {
245	return Finalized;
246	}
247
248	bool hasNoSinksInFrontier() {
249	for (const auto I : Frontier)
250	if (I->isSink())
251	return false;
252	return true;
253	}
254
255	/// Allow subclasses to finalize results before result_begin() is executed.
256	virtual void finalizeResults() {}
257
258	ExplodedNode *generateNodeImpl(const ProgramPoint &PP,
259	ProgramStateRef State,
260	ExplodedNode *Pred,
261	bool MarkAsSink = false);
262
263	public:
264	NodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
265	const NodeBuilderContext &Ctx, bool F = true)
266	: C(Ctx), Finalized(F), Frontier(DstSet) {
267	Frontier.Add(SrcNode);
268	}
269
270	NodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
271	const NodeBuilderContext &Ctx, bool F = true)
272	: C(Ctx), Finalized(F), Frontier(DstSet) {
273	Frontier.insert(SrcSet);
274	assert(hasNoSinksInFrontier());
275	}
276
277	virtual ~NodeBuilder() = default;
278
279	/// Generates a node in the ExplodedGraph.
280	ExplodedNode *generateNode(const ProgramPoint &PP,
281	ProgramStateRef State,
282	ExplodedNode *Pred) {
283	return generateNodeImpl(PP, State, Pred, false);
284	}
285
286	/// Generates a sink in the ExplodedGraph.
287	///
288	/// When a node is marked as sink, the exploration from the node is stopped -
289	/// the node becomes the last node on the path and certain kinds of bugs are
290	/// suppressed.
291	ExplodedNode *generateSink(const ProgramPoint &PP,
292	ProgramStateRef State,
293	ExplodedNode *Pred) {
294	return generateNodeImpl(PP, State, Pred, true);
295	}
296
297	const ExplodedNodeSet &getResults() {
298	finalizeResults();
299	assert(checkResults());
300	return Frontier;
301	}
302
303	using iterator = ExplodedNodeSet::iterator;
304
305	/// Iterators through the results frontier.
306	iterator begin() {
307	finalizeResults();
308	assert(checkResults());
309	return Frontier.begin();
310	}
311
312	iterator end() {
313	finalizeResults();
314	return Frontier.end();
315	}
316
317	const NodeBuilderContext &getContext() { return C; }
318	bool hasGeneratedNodes() { return HasGeneratedNodes; }
319
320	void takeNodes(const ExplodedNodeSet &S) {
321	for (const auto I : S)
322	Frontier.erase(I);
323	}
324
325	void takeNodes(ExplodedNode *N) { Frontier.erase(N); }
326	void addNodes(const ExplodedNodeSet &S) { Frontier.insert(S); }
327	void addNodes(ExplodedNode *N) { Frontier.Add(N); }
328	};
329
330	/// \class NodeBuilderWithSinks
331	/// This node builder keeps track of the generated sink nodes.
332	class NodeBuilderWithSinks: public NodeBuilder {
333	void anchor() override;
334
335	protected:
336	SmallVector<ExplodedNode*, 2> sinksGenerated;
337	ProgramPoint &Location;
338
339	public:
340	NodeBuilderWithSinks(ExplodedNode *Pred, ExplodedNodeSet &DstSet,
341	const NodeBuilderContext &Ctx, ProgramPoint &L)
342	: NodeBuilder(Pred, DstSet, Ctx), Location(L) {}
343
344	ExplodedNode *generateNode(ProgramStateRef State,
345	ExplodedNode *Pred,
346	const ProgramPointTag *Tag = nullptr) {
347	const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
348	return NodeBuilder::generateNode(LocalLoc, State, Pred);
349	}
350
351	ExplodedNode generateSink(ProgramStateRef State, ExplodedNode Pred,
352	const ProgramPointTag *Tag = nullptr) {
353	const ProgramPoint &LocalLoc = (Tag ? Location.withTag(Tag) : Location);
354	ExplodedNode *N = NodeBuilder::generateSink(LocalLoc, State, Pred);
355	if (N && N->isSink())
356	sinksGenerated.push_back(N);
357	return N;
358	}
359
360	const SmallVectorImpl<ExplodedNode*> &getSinks() const {
361	return sinksGenerated;
362	}
363	};
364
365	/// \class StmtNodeBuilder
366	/// This builder class is useful for generating nodes that resulted from
367	/// visiting a statement. The main difference from its parent NodeBuilder is
368	/// that it creates a statement specific ProgramPoint.
369	class StmtNodeBuilder: public NodeBuilder {
370	NodeBuilder *EnclosingBldr;
371
372	public:
373	/// Constructs a StmtNodeBuilder. If the builder is going to process
374	/// nodes currently owned by another builder(with larger scope), use
375	/// Enclosing builder to transfer ownership.
376	StmtNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
377	const NodeBuilderContext &Ctx,
378	NodeBuilder *Enclosing = nullptr)
379	: NodeBuilder(SrcNode, DstSet, Ctx), EnclosingBldr(Enclosing) {
380	if (EnclosingBldr)
381	EnclosingBldr->takeNodes(SrcNode);
382	}
383
384	StmtNodeBuilder(ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
385	const NodeBuilderContext &Ctx,
386	NodeBuilder *Enclosing = nullptr)
387	: NodeBuilder(SrcSet, DstSet, Ctx), EnclosingBldr(Enclosing) {
388	if (EnclosingBldr)
389	for (const auto I : SrcSet)
390	EnclosingBldr->takeNodes(I);
391	}
392
393	~StmtNodeBuilder() override;
394
395	using NodeBuilder::generateNode;
396	using NodeBuilder::generateSink;
397
398	ExplodedNode generateNode(const Stmt S,
399	ExplodedNode *Pred,
400	ProgramStateRef St,
401	const ProgramPointTag *tag = nullptr,
402	ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
403	const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
404	Pred->getLocationContext(), tag);
405	return NodeBuilder::generateNode(L, St, Pred);
406	}
407
408	ExplodedNode generateSink(const Stmt S,
409	ExplodedNode *Pred,
410	ProgramStateRef St,
411	const ProgramPointTag *tag = nullptr,
412	ProgramPoint::Kind K = ProgramPoint::PostStmtKind){
413	const ProgramPoint &L = ProgramPoint::getProgramPoint(S, K,
414	Pred->getLocationContext(), tag);
415	return NodeBuilder::generateSink(L, St, Pred);
416	}
417	};
418
419	/// BranchNodeBuilder is responsible for constructing the nodes
420	/// corresponding to the two branches of the if statement - true and false.
421	class BranchNodeBuilder: public NodeBuilder {
422	const CFGBlock *DstT;
423	const CFGBlock *DstF;
424
425	bool InFeasibleTrue;
426	bool InFeasibleFalse;
427
428	void anchor() override;
429
430	public:
431	BranchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet,
432	const NodeBuilderContext &C,
433	const CFGBlock dstT, const CFGBlock dstF)
434	: NodeBuilder(SrcNode, DstSet, C), DstT(dstT), DstF(dstF),
435	InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
436	// The branch node builder does not generate autotransitions.
437	// If there are no successors it means that both branches are infeasible.
438	takeNodes(SrcNode);
439	}
440
441	BranchNodeBuilder(const ExplodedNodeSet &SrcSet, ExplodedNodeSet &DstSet,
442	const NodeBuilderContext &C,
443	const CFGBlock dstT, const CFGBlock dstF)
444	: NodeBuilder(SrcSet, DstSet, C), DstT(dstT), DstF(dstF),
445	InFeasibleTrue(!DstT), InFeasibleFalse(!DstF) {
446	takeNodes(SrcSet);
447	}
448
449	ExplodedNode *generateNode(ProgramStateRef State, bool branch,
450	ExplodedNode *Pred);
451
452	const CFGBlock *getTargetBlock(bool branch) const {
453	return branch ? DstT : DstF;
454	}
455
456	void markInfeasible(bool branch) {
457	if (branch)
458	InFeasibleTrue = true;
459	else
460	InFeasibleFalse = true;
461	}
462
463	bool isFeasible(bool branch) {
464	return branch ? !InFeasibleTrue : !InFeasibleFalse;
465	}
466	};
467
468	class IndirectGotoNodeBuilder {
469	CoreEngine& Eng;
470	const CFGBlock *Src;
471	const CFGBlock &DispatchBlock;
472	const Expr *E;
473	ExplodedNode *Pred;
474
475	public:
476	IndirectGotoNodeBuilder(ExplodedNode pred, const CFGBlock src,
477	const Expr e, const CFGBlock dispatch, CoreEngine* eng)
478	: Eng(eng), Src(src), DispatchBlock(dispatch), E(e), Pred(pred) {}
479
480	class iterator {
481	friend class IndirectGotoNodeBuilder;
482
483	CFGBlock::const_succ_iterator I;
484
485	iterator(CFGBlock::const_succ_iterator i) : I(i) {}
486
487	public:
488	iterator &operator++() { ++I; return *this; }
489	bool operator!=(const iterator &X) const { return I != X.I; }
490
491	const LabelDecl *getLabel() const {
492	return cast<LabelStmt>((*I)->getLabel())->getDecl();
493	}
494
495	const CFGBlock *getBlock() const {
496	return *I;
497	}
498	};
499
500	iterator begin() { return iterator(DispatchBlock.succ_begin()); }
501	iterator end() { return iterator(DispatchBlock.succ_end()); }
502
503	ExplodedNode *generateNode(const iterator &I,
504	ProgramStateRef State,
505	bool isSink = false);
506
507	const Expr *getTarget() const { return E; }
508
509	ProgramStateRef getState() const { return Pred->State; }
510
511	const LocationContext *getLocationContext() const {
512	return Pred->getLocationContext();
513	}
514	};
515
516	class SwitchNodeBuilder {
517	CoreEngine& Eng;
518	const CFGBlock *Src;
519	const Expr *Condition;
520	ExplodedNode *Pred;
521
522	public:
523	SwitchNodeBuilder(ExplodedNode pred, const CFGBlock src,
524	const Expr condition, CoreEngine eng)
525	: Eng(*eng), Src(src), Condition(condition), Pred(pred) {}
526
527	class iterator {
528	friend class SwitchNodeBuilder;
529
530	CFGBlock::const_succ_reverse_iterator I;
531
532	iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {}
533
534	public:
535	iterator &operator++() { ++I; return *this; }
536	bool operator!=(const iterator &X) const { return I != X.I; }
537	bool operator==(const iterator &X) const { return I == X.I; }
538
539	const CaseStmt *getCase() const {
540	return cast<CaseStmt>((*I)->getLabel());
541	}
542
543	const CFGBlock *getBlock() const {
544	return *I;
545	}
546	};
547
548	iterator begin() { return iterator(Src->succ_rbegin()+1); }
549	iterator end() { return iterator(Src->succ_rend()); }
550
551	const SwitchStmt *getSwitch() const {
552	return cast<SwitchStmt>(Src->getTerminator());
553	}
554
555	ExplodedNode *generateCaseStmtNode(const iterator &I,
556	ProgramStateRef State);
557
558	ExplodedNode *generateDefaultCaseNode(ProgramStateRef State,
559	bool isSink = false);
560
561	const Expr *getCondition() const { return Condition; }
562
563	ProgramStateRef getState() const { return Pred->State; }
564
565	const LocationContext *getLocationContext() const {
566	return Pred->getLocationContext();
567	}
568	};
569
570	} // namespace ento
571
572	} // namespace clang
573
574	#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_COREENGINE_H
575