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