Consumed.h source code [clang_source_code/include/clang/Analysis/Analyses/Consumed.h]

1	//===- Consumed.h ------------------------------------------------ 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	// A intra-procedural analysis for checking consumed properties. This is based,
10	// in part, on research on linear types.
11	//
12	//===----------------------------------------------------------------------===//
13
14	#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
15	#define LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
16
17	#include "clang/Analysis/Analyses/PostOrderCFGView.h"
18	#include "clang/Analysis/CFG.h"
19	#include "clang/Basic/LLVM.h"
20	#include "clang/Basic/PartialDiagnostic.h"
21	#include "clang/Basic/SourceLocation.h"
22	#include "llvm/ADT/DenseMap.h"
23	#include "llvm/ADT/SmallVector.h"
24	#include "llvm/ADT/StringRef.h"
25	#include <list>
26	#include <memory>
27	#include <utility>
28	#include <vector>
29
30	namespace clang {
31
32	class AnalysisDeclContext;
33	class CXXBindTemporaryExpr;
34	class FunctionDecl;
35	class PostOrderCFGView;
36	class Stmt;
37	class VarDecl;
38
39	namespace consumed {
40
41	class ConsumedStmtVisitor;
42
43	enum ConsumedState {
44	// No state information for the given variable.
45	CS_None,
46
47	CS_Unknown,
48	CS_Unconsumed,
49	CS_Consumed
50	};
51
52	using OptionalNotes = SmallVector<PartialDiagnosticAt, 1>;
53	using DelayedDiag = std::pair<PartialDiagnosticAt, OptionalNotes>;
54	using DiagList = std::list<DelayedDiag>;
55
56	class ConsumedWarningsHandlerBase {
57	public:
58	virtual ~ConsumedWarningsHandlerBase();
59
60	/// Emit the warnings and notes left by the analysis.
61	virtual void emitDiagnostics() {}
62
63	/// Warn that a variable's state doesn't match at the entry and exit
64	/// of a loop.
65	///
66	/// \param Loc -- The location of the end of the loop.
67	///
68	/// \param VariableName -- The name of the variable that has a mismatched
69	/// state.
70	virtual void warnLoopStateMismatch(SourceLocation Loc,
71	StringRef VariableName) {}
72
73	/// Warn about parameter typestate mismatches upon return.
74	///
75	/// \param Loc -- The SourceLocation of the return statement.
76	///
77	/// \param ExpectedState -- The state the return value was expected to be
78	/// in.
79	///
80	/// \param ObservedState -- The state the return value was observed to be
81	/// in.
82	virtual void warnParamReturnTypestateMismatch(SourceLocation Loc,
83	StringRef VariableName,
84	StringRef ExpectedState,
85	StringRef ObservedState) {}
86
87	// FIXME: Add documentation.
88	virtual void warnParamTypestateMismatch(SourceLocation LOC,
89	StringRef ExpectedState,
90	StringRef ObservedState) {}
91
92	// FIXME: This can be removed when the attr propagation fix for templated
93	// classes lands.
94	/// Warn about return typestates set for unconsumable types.
95	///
96	/// \param Loc -- The location of the attributes.
97	///
98	/// \param TypeName -- The name of the unconsumable type.
99	virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc,
100	StringRef TypeName) {}
101
102	/// Warn about return typestate mismatches.
103	///
104	/// \param Loc -- The SourceLocation of the return statement.
105	///
106	/// \param ExpectedState -- The state the return value was expected to be
107	/// in.
108	///
109	/// \param ObservedState -- The state the return value was observed to be
110	/// in.
111	virtual void warnReturnTypestateMismatch(SourceLocation Loc,
112	StringRef ExpectedState,
113	StringRef ObservedState) {}
114
115	/// Warn about use-while-consumed errors.
116	/// \param MethodName -- The name of the method that was incorrectly
117	/// invoked.
118	///
119	/// \param State -- The state the object was used in.
120	///
121	/// \param Loc -- The SourceLocation of the method invocation.
122	virtual void warnUseOfTempInInvalidState(StringRef MethodName,
123	StringRef State,
124	SourceLocation Loc) {}
125
126	/// Warn about use-while-consumed errors.
127	/// \param MethodName -- The name of the method that was incorrectly
128	/// invoked.
129	///
130	/// \param State -- The state the object was used in.
131	///
132	/// \param VariableName -- The name of the variable that holds the unique
133	/// value.
134	///
135	/// \param Loc -- The SourceLocation of the method invocation.
136	virtual void warnUseInInvalidState(StringRef MethodName,
137	StringRef VariableName,
138	StringRef State,
139	SourceLocation Loc) {}
140	};
141
142	class ConsumedStateMap {
143	using VarMapType = llvm::DenseMap<const VarDecl *, ConsumedState>;
144	using TmpMapType =
145	llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState>;
146
147	protected:
148	bool Reachable = true;
149	const Stmt *From = nullptr;
150	VarMapType VarMap;
151	TmpMapType TmpMap;
152
153	public:
154	ConsumedStateMap() = default;
155	ConsumedStateMap(const ConsumedStateMap &Other)
156	: Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap),
157	TmpMap() {}
158
159	/// Warn if any of the parameters being tracked are not in the state
160	/// they were declared to be in upon return from a function.
161	void checkParamsForReturnTypestate(SourceLocation BlameLoc,
162	ConsumedWarningsHandlerBase &WarningsHandler) const;
163
164	/// Clear the TmpMap.
165	void clearTemporaries();
166
167	/// Get the consumed state of a given variable.
168	ConsumedState getState(const VarDecl *Var) const;
169
170	/// Get the consumed state of a given temporary value.
171	ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const;
172
173	/// Merge this state map with another map.
174	void intersect(const ConsumedStateMap &Other);
175
176	void intersectAtLoopHead(const CFGBlock LoopHead, const CFGBlock LoopBack,
177	const ConsumedStateMap *LoopBackStates,
178	ConsumedWarningsHandlerBase &WarningsHandler);
179
180	/// Return true if this block is reachable.
181	bool isReachable() const { return Reachable; }
182
183	/// Mark the block as unreachable.
184	void markUnreachable();
185
186	/// Set the source for a decision about the branching of states.
187	/// \param Source -- The statement that was the origin of a branching
188	/// decision.
189	void setSource(const Stmt *Source) { this->From = Source; }
190
191	/// Set the consumed state of a given variable.
192	void setState(const VarDecl *Var, ConsumedState State);
193
194	/// Set the consumed state of a given temporary value.
195	void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State);
196
197	/// Remove the temporary value from our state map.
198	void remove(const CXXBindTemporaryExpr *Tmp);
199
200	/// Tests to see if there is a mismatch in the states stored in two
201	/// maps.
202	///
203	/// \param Other -- The second map to compare against.
204	bool operator!=(const ConsumedStateMap *Other) const;
205	};
206
207	class ConsumedBlockInfo {
208	std::vector<std::unique_ptr<ConsumedStateMap>> StateMapsArray;
209	std::vector<unsigned int> VisitOrder;
210
211	public:
212	ConsumedBlockInfo() = default;
213
214	ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph)
215	: StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) {
216	unsigned int VisitOrderCounter = 0;
217	for (const auto BI : *SortedGraph)
218	VisitOrder[BI->getBlockID()] = VisitOrderCounter++;
219	}
220
221	bool allBackEdgesVisited(const CFGBlock *CurrBlock,
222	const CFGBlock *TargetBlock);
223
224	void addInfo(const CFGBlock Block, ConsumedStateMap StateMap,
225	std::unique_ptr<ConsumedStateMap> &OwnedStateMap);
226	void addInfo(const CFGBlock *Block,
227	std::unique_ptr<ConsumedStateMap> StateMap);
228
229	ConsumedStateMap* borrowInfo(const CFGBlock *Block);
230
231	void discardInfo(const CFGBlock *Block);
232
233	std::unique_ptr<ConsumedStateMap> getInfo(const CFGBlock *Block);
234
235	bool isBackEdge(const CFGBlock From, const CFGBlock To);
236	bool isBackEdgeTarget(const CFGBlock *Block);
237	};
238
239	/// A class that handles the analysis of uniqueness violations.
240	class ConsumedAnalyzer {
241	ConsumedBlockInfo BlockInfo;
242	std::unique_ptr<ConsumedStateMap> CurrStates;
243
244	ConsumedState ExpectedReturnState;
245
246	void determineExpectedReturnState(AnalysisDeclContext &AC,
247	const FunctionDecl *D);
248	bool splitState(const CFGBlock *CurrBlock,
249	const ConsumedStmtVisitor &Visitor);
250
251	public:
252	ConsumedWarningsHandlerBase &WarningsHandler;
253
254	ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler)
255	: WarningsHandler(WarningsHandler) {}
256
257	ConsumedState getExpectedReturnState() const { return ExpectedReturnState; }
258
259	/// Check a function's CFG for consumed violations.
260	///
261	/// We traverse the blocks in the CFG, keeping track of the state of each
262	/// value who's type has uniquness annotations. If methods are invoked in
263	/// the wrong state a warning is issued. Each block in the CFG is traversed
264	/// exactly once.
265	void run(AnalysisDeclContext &AC);
266	};
267
268	} // namespace consumed
269
270	} // namespace clang
271
272	#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H
273