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