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