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
25namespace clang {
26namespace 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.
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.
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.
71    virtual void warnParamReturnTypestateMismatch(SourceLocation Loc,
72                                                  StringRef VariableName,
73                                                  StringRef ExpectedState,
74                                                  StringRef ObservedState) {}
75
76    // FIXME: Add documentation.
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.
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.
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.
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.
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:
145    ConsumedStateMap() : Reachable(true), From(nullptr) {}
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.
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.
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
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
254    ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler)
255        : WarningsHandler(WarningsHandler) {}
256
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