Consumed.h revision 7385840b600d0e4a96d75042f612f6430e4a0390 
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_CONSUMED_H
16#define LLVM_CLANG_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/AnalysisContext.h"
22#include "clang/Analysis/Analyses/PostOrderCFGView.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    // FIXME: This can be removed when the attr propagation fix for templated
63    //        classes lands.
64    /// \brief Warn about return typestates set for unconsumable types.
65    ///
66    /// \param Loc -- The location of the attributes.
67    ///
68    /// \param TypeName -- The name of the unconsumable type.
69    virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc,
70                                                        StringRef TypeName) {}
71
72    /// \brief Warn about return typestate mismatches.
73    /// \param Loc -- The SourceLocation of the return statement.
74    virtual void warnReturnTypestateMismatch(SourceLocation Loc,
75                                             StringRef ExpectedState,
76                                             StringRef ObservedState) {}
77
78    /// \brief Warn about unnecessary-test errors.
79    /// \param VariableName -- The name of the variable that holds the unique
80    /// value.
81    ///
82    /// \param VariableState -- The known state of the value.
83    ///
84    /// \param Loc -- The SourceLocation of the unnecessary test.
85    virtual void warnUnnecessaryTest(StringRef VariableName,
86                                     StringRef VariableState,
87                                     SourceLocation Loc) {}
88
89    /// \brief Warn about use-while-consumed errors.
90    /// \param MethodName -- The name of the method that was incorrectly
91    /// invoked.
92    ///
93    /// \param State -- The state the object was used in.
94    ///
95    /// \param Loc -- The SourceLocation of the method invocation.
96    virtual void warnUseOfTempInInvalidState(StringRef MethodName,
97                                             StringRef State,
98                                             SourceLocation Loc) {}
99
100    /// \brief Warn about use-while-consumed errors.
101    /// \param MethodName -- The name of the method that was incorrectly
102    /// invoked.
103    ///
104    /// \param State -- The state the object was used in.
105    ///
106    /// \param VariableName -- The name of the variable that holds the unique
107    /// value.
108    ///
109    /// \param Loc -- The SourceLocation of the method invocation.
110    virtual void warnUseInInvalidState(StringRef MethodName,
111                                       StringRef VariableName,
112                                       StringRef State,
113                                       SourceLocation Loc) {}
114  };
115
116  class ConsumedStateMap {
117
118    typedef llvm::DenseMap<const VarDecl *, ConsumedState> MapType;
119    typedef std::pair<const VarDecl *, ConsumedState> PairType;
120
121  protected:
122
123    bool Reachable;
124    const Stmt *From;
125    MapType Map;
126
127  public:
128    ConsumedStateMap() : Reachable(true), From(NULL) {}
129    ConsumedStateMap(const ConsumedStateMap &Other)
130      : Reachable(Other.Reachable), From(Other.From), Map(Other.Map) {}
131
132    /// \brief Get the consumed state of a given variable.
133    ConsumedState getState(const VarDecl *Var) const;
134
135    /// \brief Merge this state map with another map.
136    void intersect(const ConsumedStateMap *Other);
137
138    void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack,
139      const ConsumedStateMap *LoopBackStates,
140      ConsumedWarningsHandlerBase &WarningsHandler);
141
142    /// \brief Return true if this block is reachable.
143    bool isReachable() const { return Reachable; }
144
145    /// \brief Mark the block as unreachable.
146    void markUnreachable();
147
148    /// \brief Set the source for a decision about the branching of states.
149    /// \param Source -- The statement that was the origin of a branching
150    /// decision.
151    void setSource(const Stmt *Source) { this->From = Source; }
152
153    /// \brief Set the consumed state of a given variable.
154    void setState(const VarDecl *Var, ConsumedState State);
155
156    /// \brief Remove the variable from our state map.
157    void remove(const VarDecl *Var);
158
159    /// \brief Tests to see if there is a mismatch in the states stored in two
160    /// maps.
161    ///
162    /// \param Other -- The second map to compare against.
163    bool operator!=(const ConsumedStateMap *Other) const;
164  };
165
166  class ConsumedBlockInfo {
167    std::vector<ConsumedStateMap*> StateMapsArray;
168    std::vector<int> VisitOrder;
169
170  public:
171    ConsumedBlockInfo() : StateMapsArray(NULL) {}
172
173    ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph)
174        : StateMapsArray(NumBlocks, 0), VisitOrder(NumBlocks, 0) {
175      unsigned int VisitOrderCounter = 0;
176      for (PostOrderCFGView::iterator BI = SortedGraph->begin(),
177           BE = SortedGraph->end(); BI != BE; ++BI) {
178        VisitOrder[(*BI)->getBlockID()] = VisitOrderCounter++;
179      }
180    }
181
182    bool allBackEdgesVisited(const CFGBlock *CurrBlock,
183                             const CFGBlock *TargetBlock);
184
185    void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap,
186                 bool &AlreadyOwned);
187    void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap);
188
189    ConsumedStateMap* borrowInfo(const CFGBlock *Block);
190
191    void discardInfo(const CFGBlock *Block);
192
193    ConsumedStateMap* getInfo(const CFGBlock *Block);
194
195    bool isBackEdge(const CFGBlock *From, const CFGBlock *To);
196    bool isBackEdgeTarget(const CFGBlock *Block);
197  };
198
199  /// A class that handles the analysis of uniqueness violations.
200  class ConsumedAnalyzer {
201
202    ConsumedBlockInfo BlockInfo;
203    ConsumedStateMap *CurrStates;
204
205    ConsumedState ExpectedReturnState;
206
207    void determineExpectedReturnState(AnalysisDeclContext &AC,
208                                      const FunctionDecl *D);
209    bool hasConsumableAttributes(const CXXRecordDecl *RD);
210    bool splitState(const CFGBlock *CurrBlock,
211                    const ConsumedStmtVisitor &Visitor);
212
213  public:
214
215    ConsumedWarningsHandlerBase &WarningsHandler;
216
217    ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler)
218        : WarningsHandler(WarningsHandler) {}
219
220    ConsumedState getExpectedReturnState() const { return ExpectedReturnState; }
221
222    /// \brief Check a function's CFG for consumed violations.
223    ///
224    /// We traverse the blocks in the CFG, keeping track of the state of each
225    /// value who's type has uniquness annotations.  If methods are invoked in
226    /// the wrong state a warning is issued.  Each block in the CFG is traversed
227    /// exactly once.
228    void run(AnalysisDeclContext &AC);
229  };
230}} // end namespace clang::consumed
231
232#endif
233