1341825Sdim//===- Consumed.h -----------------------------------------------*- C++ -*-===// 2259701Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6259701Sdim// 7259701Sdim//===----------------------------------------------------------------------===// 8259701Sdim// 9259701Sdim// A intra-procedural analysis for checking consumed properties. This is based, 10259701Sdim// in part, on research on linear types. 11259701Sdim// 12259701Sdim//===----------------------------------------------------------------------===// 13259701Sdim 14280031Sdim#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H 15280031Sdim#define LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H 16259701Sdim 17276479Sdim#include "clang/Analysis/Analyses/PostOrderCFGView.h" 18341825Sdim#include "clang/Analysis/CFG.h" 19341825Sdim#include "clang/Basic/LLVM.h" 20341825Sdim#include "clang/Basic/PartialDiagnostic.h" 21259701Sdim#include "clang/Basic/SourceLocation.h" 22341825Sdim#include "llvm/ADT/DenseMap.h" 23341825Sdim#include "llvm/ADT/SmallVector.h" 24341825Sdim#include "llvm/ADT/StringRef.h" 25341825Sdim#include <list> 26341825Sdim#include <memory> 27341825Sdim#include <utility> 28341825Sdim#include <vector> 29259701Sdim 30259701Sdimnamespace clang { 31341825Sdim 32341825Sdimclass AnalysisDeclContext; 33341825Sdimclass CXXBindTemporaryExpr; 34341825Sdimclass FunctionDecl; 35341825Sdimclass PostOrderCFGView; 36341825Sdimclass Stmt; 37341825Sdimclass VarDecl; 38341825Sdim 39259701Sdimnamespace consumed { 40341825Sdim 41341825Sdim class ConsumedStmtVisitor; 42341825Sdim 43259701Sdim enum ConsumedState { 44259701Sdim // No state information for the given variable. 45259701Sdim CS_None, 46341825Sdim 47259701Sdim CS_Unknown, 48259701Sdim CS_Unconsumed, 49259701Sdim CS_Consumed 50259701Sdim }; 51259701Sdim 52341825Sdim using OptionalNotes = SmallVector<PartialDiagnosticAt, 1>; 53341825Sdim using DelayedDiag = std::pair<PartialDiagnosticAt, OptionalNotes>; 54341825Sdim using DiagList = std::list<DelayedDiag>; 55341825Sdim 56259701Sdim class ConsumedWarningsHandlerBase { 57259701Sdim public: 58259701Sdim virtual ~ConsumedWarningsHandlerBase(); 59259701Sdim 60341825Sdim /// Emit the warnings and notes left by the analysis. 61259701Sdim virtual void emitDiagnostics() {} 62341825Sdim 63341825Sdim /// Warn that a variable's state doesn't match at the entry and exit 64259701Sdim /// of a loop. 65259701Sdim /// 66259701Sdim /// \param Loc -- The location of the end of the loop. 67259701Sdim /// 68259701Sdim /// \param VariableName -- The name of the variable that has a mismatched 69259701Sdim /// state. 70259701Sdim virtual void warnLoopStateMismatch(SourceLocation Loc, 71259701Sdim StringRef VariableName) {} 72341825Sdim 73341825Sdim /// Warn about parameter typestate mismatches upon return. 74259701Sdim /// 75259701Sdim /// \param Loc -- The SourceLocation of the return statement. 76259701Sdim /// 77259701Sdim /// \param ExpectedState -- The state the return value was expected to be 78259701Sdim /// in. 79259701Sdim /// 80259701Sdim /// \param ObservedState -- The state the return value was observed to be 81259701Sdim /// in. 82259701Sdim virtual void warnParamReturnTypestateMismatch(SourceLocation Loc, 83259701Sdim StringRef VariableName, 84259701Sdim StringRef ExpectedState, 85296417Sdim StringRef ObservedState) {} 86341825Sdim 87259701Sdim // FIXME: Add documentation. 88259701Sdim virtual void warnParamTypestateMismatch(SourceLocation LOC, 89259701Sdim StringRef ExpectedState, 90259701Sdim StringRef ObservedState) {} 91341825Sdim 92259701Sdim // FIXME: This can be removed when the attr propagation fix for templated 93259701Sdim // classes lands. 94341825Sdim /// Warn about return typestates set for unconsumable types. 95341825Sdim /// 96259701Sdim /// \param Loc -- The location of the attributes. 97259701Sdim /// 98259701Sdim /// \param TypeName -- The name of the unconsumable type. 99259701Sdim virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc, 100259701Sdim StringRef TypeName) {} 101341825Sdim 102341825Sdim /// Warn about return typestate mismatches. 103259701Sdim /// 104259701Sdim /// \param Loc -- The SourceLocation of the return statement. 105259701Sdim /// 106259701Sdim /// \param ExpectedState -- The state the return value was expected to be 107259701Sdim /// in. 108259701Sdim /// 109259701Sdim /// \param ObservedState -- The state the return value was observed to be 110259701Sdim /// in. 111259701Sdim virtual void warnReturnTypestateMismatch(SourceLocation Loc, 112259701Sdim StringRef ExpectedState, 113259701Sdim StringRef ObservedState) {} 114259701Sdim 115341825Sdim /// Warn about use-while-consumed errors. 116259701Sdim /// \param MethodName -- The name of the method that was incorrectly 117259701Sdim /// invoked. 118259701Sdim /// 119259701Sdim /// \param State -- The state the object was used in. 120259701Sdim /// 121259701Sdim /// \param Loc -- The SourceLocation of the method invocation. 122259701Sdim virtual void warnUseOfTempInInvalidState(StringRef MethodName, 123259701Sdim StringRef State, 124259701Sdim SourceLocation Loc) {} 125259701Sdim 126341825Sdim /// Warn about use-while-consumed errors. 127259701Sdim /// \param MethodName -- The name of the method that was incorrectly 128259701Sdim /// invoked. 129259701Sdim /// 130259701Sdim /// \param State -- The state the object was used in. 131259701Sdim /// 132259701Sdim /// \param VariableName -- The name of the variable that holds the unique 133259701Sdim /// value. 134259701Sdim /// 135259701Sdim /// \param Loc -- The SourceLocation of the method invocation. 136259701Sdim virtual void warnUseInInvalidState(StringRef MethodName, 137259701Sdim StringRef VariableName, 138259701Sdim StringRef State, 139259701Sdim SourceLocation Loc) {} 140259701Sdim }; 141259701Sdim 142259701Sdim class ConsumedStateMap { 143341825Sdim using VarMapType = llvm::DenseMap<const VarDecl *, ConsumedState>; 144341825Sdim using TmpMapType = 145341825Sdim llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState>; 146341825Sdim 147259701Sdim protected: 148341825Sdim bool Reachable = true; 149341825Sdim const Stmt *From = nullptr; 150259701Sdim VarMapType VarMap; 151259701Sdim TmpMapType TmpMap; 152341825Sdim 153259701Sdim public: 154341825Sdim ConsumedStateMap() = default; 155259701Sdim ConsumedStateMap(const ConsumedStateMap &Other) 156341825Sdim : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap), 157341825Sdim TmpMap() {} 158341825Sdim 159341825Sdim /// Warn if any of the parameters being tracked are not in the state 160259701Sdim /// they were declared to be in upon return from a function. 161259701Sdim void checkParamsForReturnTypestate(SourceLocation BlameLoc, 162259701Sdim ConsumedWarningsHandlerBase &WarningsHandler) const; 163341825Sdim 164341825Sdim /// Clear the TmpMap. 165259701Sdim void clearTemporaries(); 166341825Sdim 167341825Sdim /// Get the consumed state of a given variable. 168259701Sdim ConsumedState getState(const VarDecl *Var) const; 169341825Sdim 170341825Sdim /// Get the consumed state of a given temporary value. 171259701Sdim ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const; 172341825Sdim 173341825Sdim /// Merge this state map with another map. 174296417Sdim void intersect(const ConsumedStateMap &Other); 175296417Sdim 176259701Sdim void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack, 177259701Sdim const ConsumedStateMap *LoopBackStates, 178259701Sdim ConsumedWarningsHandlerBase &WarningsHandler); 179341825Sdim 180341825Sdim /// Return true if this block is reachable. 181259701Sdim bool isReachable() const { return Reachable; } 182341825Sdim 183341825Sdim /// Mark the block as unreachable. 184259701Sdim void markUnreachable(); 185341825Sdim 186341825Sdim /// Set the source for a decision about the branching of states. 187259701Sdim /// \param Source -- The statement that was the origin of a branching 188259701Sdim /// decision. 189259701Sdim void setSource(const Stmt *Source) { this->From = Source; } 190341825Sdim 191341825Sdim /// Set the consumed state of a given variable. 192259701Sdim void setState(const VarDecl *Var, ConsumedState State); 193341825Sdim 194341825Sdim /// Set the consumed state of a given temporary value. 195259701Sdim void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State); 196341825Sdim 197341825Sdim /// Remove the temporary value from our state map. 198276479Sdim void remove(const CXXBindTemporaryExpr *Tmp); 199341825Sdim 200341825Sdim /// Tests to see if there is a mismatch in the states stored in two 201259701Sdim /// maps. 202259701Sdim /// 203259701Sdim /// \param Other -- The second map to compare against. 204259701Sdim bool operator!=(const ConsumedStateMap *Other) const; 205259701Sdim }; 206341825Sdim 207259701Sdim class ConsumedBlockInfo { 208296417Sdim std::vector<std::unique_ptr<ConsumedStateMap>> StateMapsArray; 209259701Sdim std::vector<unsigned int> VisitOrder; 210341825Sdim 211259701Sdim public: 212296417Sdim ConsumedBlockInfo() = default; 213276479Sdim 214259701Sdim ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph) 215296417Sdim : StateMapsArray(NumBlocks), VisitOrder(NumBlocks, 0) { 216259701Sdim unsigned int VisitOrderCounter = 0; 217341825Sdim for (const auto BI : *SortedGraph) 218341825Sdim VisitOrder[BI->getBlockID()] = VisitOrderCounter++; 219259701Sdim } 220341825Sdim 221259701Sdim bool allBackEdgesVisited(const CFGBlock *CurrBlock, 222259701Sdim const CFGBlock *TargetBlock); 223296417Sdim 224259701Sdim void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap, 225296417Sdim std::unique_ptr<ConsumedStateMap> &OwnedStateMap); 226296417Sdim void addInfo(const CFGBlock *Block, 227296417Sdim std::unique_ptr<ConsumedStateMap> StateMap); 228296417Sdim 229259701Sdim ConsumedStateMap* borrowInfo(const CFGBlock *Block); 230341825Sdim 231259701Sdim void discardInfo(const CFGBlock *Block); 232296417Sdim 233296417Sdim std::unique_ptr<ConsumedStateMap> getInfo(const CFGBlock *Block); 234296417Sdim 235259701Sdim bool isBackEdge(const CFGBlock *From, const CFGBlock *To); 236259701Sdim bool isBackEdgeTarget(const CFGBlock *Block); 237259701Sdim }; 238259701Sdim 239259701Sdim /// A class that handles the analysis of uniqueness violations. 240259701Sdim class ConsumedAnalyzer { 241259701Sdim ConsumedBlockInfo BlockInfo; 242296417Sdim std::unique_ptr<ConsumedStateMap> CurrStates; 243296417Sdim 244259701Sdim ConsumedState ExpectedReturnState; 245341825Sdim 246259701Sdim void determineExpectedReturnState(AnalysisDeclContext &AC, 247259701Sdim const FunctionDecl *D); 248259701Sdim bool splitState(const CFGBlock *CurrBlock, 249259701Sdim const ConsumedStmtVisitor &Visitor); 250341825Sdim 251259701Sdim public: 252259701Sdim ConsumedWarningsHandlerBase &WarningsHandler; 253259701Sdim 254259701Sdim ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler) 255259701Sdim : WarningsHandler(WarningsHandler) {} 256259701Sdim 257259701Sdim ConsumedState getExpectedReturnState() const { return ExpectedReturnState; } 258341825Sdim 259341825Sdim /// Check a function's CFG for consumed violations. 260259701Sdim /// 261259701Sdim /// We traverse the blocks in the CFG, keeping track of the state of each 262259701Sdim /// value who's type has uniquness annotations. If methods are invoked in 263259701Sdim /// the wrong state a warning is issued. Each block in the CFG is traversed 264259701Sdim /// exactly once. 265259701Sdim void run(AnalysisDeclContext &AC); 266259701Sdim }; 267259701Sdim 268341825Sdim} // namespace consumed 269341825Sdim 270341825Sdim} // namespace clang 271341825Sdim 272341825Sdim#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H 273