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 | |
158 | // The copy assignment operator is defined as deleted pending further |
159 | // motivation. |
160 | ConsumedStateMap &operator=(const ConsumedStateMap &) = delete; |
161 | |
162 | /// Warn if any of the parameters being tracked are not in the state |
163 | /// they were declared to be in upon return from a function. |
164 | void checkParamsForReturnTypestate(SourceLocation BlameLoc, |
165 | ConsumedWarningsHandlerBase &WarningsHandler) const; |
166 | |
167 | /// Clear the TmpMap. |
168 | void clearTemporaries(); |
169 | |
170 | /// Get the consumed state of a given variable. |
171 | ConsumedState getState(const VarDecl *Var) const; |
172 | |
173 | /// Get the consumed state of a given temporary value. |
174 | ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const; |
175 | |
176 | /// Merge this state map with another map. |
177 | void intersect(const ConsumedStateMap &Other); |
178 | |
179 | void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack, |
180 | const ConsumedStateMap *LoopBackStates, |
181 | ConsumedWarningsHandlerBase &WarningsHandler); |
182 | |
183 | /// Return true if this block is reachable. |
184 | bool isReachable() const { return Reachable; } |
185 | |
186 | /// Mark the block as unreachable. |
187 | void markUnreachable(); |
188 | |
189 | /// Set the source for a decision about the branching of states. |
190 | /// \param Source -- The statement that was the origin of a branching |
191 | /// decision. |
192 | void setSource(const Stmt *Source) { this->From = Source; } |
193 | |
194 | /// Set the consumed state of a given variable. |
195 | void setState(const VarDecl *Var, ConsumedState State); |
196 | |
197 | /// Set the consumed state of a given temporary value. |
198 | void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State); |
199 | |
200 | /// Remove the temporary value from our state map. |
201 | void remove(const CXXBindTemporaryExpr *Tmp); |
202 | |
203 | /// Tests to see if there is a mismatch in the states stored in two |
204 | /// maps. |
205 | /// |
206 | /// \param Other -- The second map to compare against. |
207 | bool operator!=(const ConsumedStateMap *Other) const; |
208 | }; |
209 | |
210 | class ConsumedBlockInfo { |
211 | std::vector<std::unique_ptr<ConsumedStateMap>> StateMapsArray; |
212 | std::vector<unsigned int> VisitOrder; |
213 | |
214 | public: |
215 | ConsumedBlockInfo() = default; |
216 | |
217 | ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph) |
218 | : StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) { |
219 | unsigned int VisitOrderCounter = 0; |
220 | for (const auto BI : *SortedGraph) |
221 | VisitOrder[BI->getBlockID()] = VisitOrderCounter++; |
222 | } |
223 | |
224 | bool allBackEdgesVisited(const CFGBlock *CurrBlock, |
225 | const CFGBlock *TargetBlock); |
226 | |
227 | void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap, |
228 | std::unique_ptr<ConsumedStateMap> &OwnedStateMap); |
229 | void addInfo(const CFGBlock *Block, |
230 | std::unique_ptr<ConsumedStateMap> StateMap); |
231 | |
232 | ConsumedStateMap* borrowInfo(const CFGBlock *Block); |
233 | |
234 | void discardInfo(const CFGBlock *Block); |
235 | |
236 | std::unique_ptr<ConsumedStateMap> getInfo(const CFGBlock *Block); |
237 | |
238 | bool isBackEdge(const CFGBlock *From, const CFGBlock *To); |
239 | bool isBackEdgeTarget(const CFGBlock *Block); |
240 | }; |
241 | |
242 | /// A class that handles the analysis of uniqueness violations. |
243 | class ConsumedAnalyzer { |
244 | ConsumedBlockInfo BlockInfo; |
245 | std::unique_ptr<ConsumedStateMap> CurrStates; |
246 | |
247 | ConsumedState ExpectedReturnState = CS_None; |
248 | |
249 | void determineExpectedReturnState(AnalysisDeclContext &AC, |
250 | const FunctionDecl *D); |
251 | bool splitState(const CFGBlock *CurrBlock, |
252 | const ConsumedStmtVisitor &Visitor); |
253 | |
254 | public: |
255 | ConsumedWarningsHandlerBase &WarningsHandler; |
256 | |
257 | ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler) |
258 | : WarningsHandler(WarningsHandler) {} |
259 | |
260 | ConsumedState getExpectedReturnState() const { return ExpectedReturnState; } |
261 | |
262 | /// Check a function's CFG for consumed violations. |
263 | /// |
264 | /// We traverse the blocks in the CFG, keeping track of the state of each |
265 | /// value who's type has uniqueness annotations. If methods are invoked in |
266 | /// the wrong state a warning is issued. Each block in the CFG is traversed |
267 | /// exactly once. |
268 | void run(AnalysisDeclContext &AC); |
269 | }; |
270 | |
271 | } // namespace consumed |
272 | |
273 | } // namespace clang |
274 | |
275 | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H |
276 | |