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