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/AnalysisDeclContext.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. 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 205 ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph) 206 : StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) { 207 unsigned int VisitOrderCounter = 0; 208 for (PostOrderCFGView::iterator BI = SortedGraph->begin(), 209 BE = SortedGraph->end(); BI != BE; ++BI) { 210 VisitOrder[(*BI)->getBlockID()] = VisitOrderCounter++; 211 } 212 } 213 214 bool allBackEdgesVisited(const CFGBlock *CurrBlock, 215 const CFGBlock *TargetBlock); 216 217 void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap, 218 std::unique_ptr<ConsumedStateMap> &OwnedStateMap); 219 void addInfo(const CFGBlock *Block, 220 std::unique_ptr<ConsumedStateMap> StateMap); 221 222 ConsumedStateMap* borrowInfo(const CFGBlock *Block); 223 224 void discardInfo(const CFGBlock *Block); 225 226 std::unique_ptr<ConsumedStateMap> getInfo(const CFGBlock *Block); 227 228 bool isBackEdge(const CFGBlock *From, const CFGBlock *To); 229 bool isBackEdgeTarget(const CFGBlock *Block); 230 }; 231 232 /// A class that handles the analysis of uniqueness violations. 233 class ConsumedAnalyzer { 234 235 ConsumedBlockInfo BlockInfo; 236 std::unique_ptr<ConsumedStateMap> CurrStates; 237 238 ConsumedState ExpectedReturnState; 239 240 void determineExpectedReturnState(AnalysisDeclContext &AC, 241 const FunctionDecl *D); 242 bool splitState(const CFGBlock *CurrBlock, 243 const ConsumedStmtVisitor &Visitor); 244 245 public: 246 247 ConsumedWarningsHandlerBase &WarningsHandler; 248 249 ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler) 250 : WarningsHandler(WarningsHandler) {} 251 252 ConsumedState getExpectedReturnState() const { return ExpectedReturnState; } 253 254 /// \brief Check a function's CFG for consumed violations. 255 /// 256 /// We traverse the blocks in the CFG, keeping track of the state of each 257 /// value who's type has uniquness annotations. If methods are invoked in 258 /// the wrong state a warning is issued. Each block in the CFG is traversed 259 /// exactly once. 260 void run(AnalysisDeclContext &AC); 261 }; 262 }} // end namespace clang::consumed 263 264 #endif 265
