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