1259701Sdim//===- Consumed.h ----------------------------------------------*- C++ --*-===// 2259701Sdim// 3259701Sdim// The LLVM Compiler Infrastructure 4259701Sdim// 5259701Sdim// This file is distributed under the University of Illinois Open Source 6259701Sdim// License. See LICENSE.TXT for details. 7259701Sdim// 8259701Sdim//===----------------------------------------------------------------------===// 9259701Sdim// 10259701Sdim// A intra-procedural analysis for checking consumed properties. This is based, 11259701Sdim// in part, on research on linear types. 12259701Sdim// 13259701Sdim//===----------------------------------------------------------------------===// 14259701Sdim 15259701Sdim#ifndef LLVM_CLANG_CONSUMED_H 16259701Sdim#define LLVM_CLANG_CONSUMED_H 17259701Sdim 18259701Sdim#include "clang/AST/DeclCXX.h" 19259701Sdim#include "clang/AST/ExprCXX.h" 20259701Sdim#include "clang/AST/StmtCXX.h" 21259701Sdim#include "clang/Analysis/AnalysisContext.h" 22259701Sdim#include "clang/Analysis/Analyses/PostOrderCFGView.h" 23259701Sdim#include "clang/Basic/SourceLocation.h" 24259701Sdim 25259701Sdimnamespace clang { 26259701Sdimnamespace consumed { 27259701Sdim 28259701Sdim enum ConsumedState { 29259701Sdim // No state information for the given variable. 30259701Sdim CS_None, 31259701Sdim 32259701Sdim CS_Unknown, 33259701Sdim CS_Unconsumed, 34259701Sdim CS_Consumed 35259701Sdim }; 36259701Sdim 37259701Sdim class ConsumedStmtVisitor; 38259701Sdim 39259701Sdim typedef SmallVector<PartialDiagnosticAt, 1> OptionalNotes; 40259701Sdim typedef std::pair<PartialDiagnosticAt, OptionalNotes> DelayedDiag; 41259701Sdim typedef std::list<DelayedDiag> DiagList; 42259701Sdim 43259701Sdim class ConsumedWarningsHandlerBase { 44259701Sdim 45259701Sdim public: 46259701Sdim 47259701Sdim virtual ~ConsumedWarningsHandlerBase(); 48259701Sdim 49259701Sdim /// \brief Emit the warnings and notes left by the analysis. 50259701Sdim virtual void emitDiagnostics() {} 51259701Sdim 52259701Sdim /// \brief Warn that a variable's state doesn't match at the entry and exit 53259701Sdim /// of a loop. 54259701Sdim /// 55259701Sdim /// \param Loc -- The location of the end of the loop. 56259701Sdim /// 57259701Sdim /// \param VariableName -- The name of the variable that has a mismatched 58259701Sdim /// state. 59259701Sdim virtual void warnLoopStateMismatch(SourceLocation Loc, 60259701Sdim StringRef VariableName) {} 61259701Sdim 62259701Sdim /// \brief Warn about parameter typestate mismatches upon return. 63259701Sdim /// 64259701Sdim /// \param Loc -- The SourceLocation of the return statement. 65259701Sdim /// 66259701Sdim /// \param ExpectedState -- The state the return value was expected to be 67259701Sdim /// in. 68259701Sdim /// 69259701Sdim /// \param ObservedState -- The state the return value was observed to be 70259701Sdim /// in. 71259701Sdim virtual void warnParamReturnTypestateMismatch(SourceLocation Loc, 72259701Sdim StringRef VariableName, 73259701Sdim StringRef ExpectedState, 74259701Sdim StringRef ObservedState) {}; 75259701Sdim 76259701Sdim // FIXME: Add documentation. 77259701Sdim virtual void warnParamTypestateMismatch(SourceLocation LOC, 78259701Sdim StringRef ExpectedState, 79259701Sdim StringRef ObservedState) {} 80259701Sdim 81259701Sdim // FIXME: This can be removed when the attr propagation fix for templated 82259701Sdim // classes lands. 83259701Sdim /// \brief Warn about return typestates set for unconsumable types. 84259701Sdim /// 85259701Sdim /// \param Loc -- The location of the attributes. 86259701Sdim /// 87259701Sdim /// \param TypeName -- The name of the unconsumable type. 88259701Sdim virtual void warnReturnTypestateForUnconsumableType(SourceLocation Loc, 89259701Sdim StringRef TypeName) {} 90259701Sdim 91259701Sdim /// \brief Warn about return typestate mismatches. 92259701Sdim /// 93259701Sdim /// \param Loc -- The SourceLocation of the return statement. 94259701Sdim /// 95259701Sdim /// \param ExpectedState -- The state the return value was expected to be 96259701Sdim /// in. 97259701Sdim /// 98259701Sdim /// \param ObservedState -- The state the return value was observed to be 99259701Sdim /// in. 100259701Sdim virtual void warnReturnTypestateMismatch(SourceLocation Loc, 101259701Sdim StringRef ExpectedState, 102259701Sdim StringRef ObservedState) {} 103259701Sdim 104259701Sdim /// \brief Warn about use-while-consumed errors. 105259701Sdim /// \param MethodName -- The name of the method that was incorrectly 106259701Sdim /// invoked. 107259701Sdim /// 108259701Sdim /// \param State -- The state the object was used in. 109259701Sdim /// 110259701Sdim /// \param Loc -- The SourceLocation of the method invocation. 111259701Sdim virtual void warnUseOfTempInInvalidState(StringRef MethodName, 112259701Sdim StringRef State, 113259701Sdim SourceLocation Loc) {} 114259701Sdim 115259701Sdim /// \brief 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 VariableName -- The name of the variable that holds the unique 122259701Sdim /// value. 123259701Sdim /// 124259701Sdim /// \param Loc -- The SourceLocation of the method invocation. 125259701Sdim virtual void warnUseInInvalidState(StringRef MethodName, 126259701Sdim StringRef VariableName, 127259701Sdim StringRef State, 128259701Sdim SourceLocation Loc) {} 129259701Sdim }; 130259701Sdim 131259701Sdim class ConsumedStateMap { 132259701Sdim 133259701Sdim typedef llvm::DenseMap<const VarDecl *, ConsumedState> VarMapType; 134259701Sdim typedef llvm::DenseMap<const CXXBindTemporaryExpr *, ConsumedState> 135259701Sdim TmpMapType; 136259701Sdim 137259701Sdim protected: 138259701Sdim 139259701Sdim bool Reachable; 140259701Sdim const Stmt *From; 141259701Sdim VarMapType VarMap; 142259701Sdim TmpMapType TmpMap; 143259701Sdim 144259701Sdim public: 145259701Sdim ConsumedStateMap() : Reachable(true), From(NULL) {} 146259701Sdim ConsumedStateMap(const ConsumedStateMap &Other) 147259701Sdim : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap), 148259701Sdim TmpMap() {} 149259701Sdim 150259701Sdim /// \brief Warn if any of the parameters being tracked are not in the state 151259701Sdim /// they were declared to be in upon return from a function. 152259701Sdim void checkParamsForReturnTypestate(SourceLocation BlameLoc, 153259701Sdim ConsumedWarningsHandlerBase &WarningsHandler) const; 154259701Sdim 155259701Sdim /// \brief Clear the TmpMap. 156259701Sdim void clearTemporaries(); 157259701Sdim 158259701Sdim /// \brief Get the consumed state of a given variable. 159259701Sdim ConsumedState getState(const VarDecl *Var) const; 160259701Sdim 161259701Sdim /// \brief Get the consumed state of a given temporary value. 162259701Sdim ConsumedState getState(const CXXBindTemporaryExpr *Tmp) const; 163259701Sdim 164259701Sdim /// \brief Merge this state map with another map. 165259701Sdim void intersect(const ConsumedStateMap *Other); 166259701Sdim 167259701Sdim void intersectAtLoopHead(const CFGBlock *LoopHead, const CFGBlock *LoopBack, 168259701Sdim const ConsumedStateMap *LoopBackStates, 169259701Sdim ConsumedWarningsHandlerBase &WarningsHandler); 170259701Sdim 171259701Sdim /// \brief Return true if this block is reachable. 172259701Sdim bool isReachable() const { return Reachable; } 173259701Sdim 174259701Sdim /// \brief Mark the block as unreachable. 175259701Sdim void markUnreachable(); 176259701Sdim 177259701Sdim /// \brief Set the source for a decision about the branching of states. 178259701Sdim /// \param Source -- The statement that was the origin of a branching 179259701Sdim /// decision. 180259701Sdim void setSource(const Stmt *Source) { this->From = Source; } 181259701Sdim 182259701Sdim /// \brief Set the consumed state of a given variable. 183259701Sdim void setState(const VarDecl *Var, ConsumedState State); 184259701Sdim 185259701Sdim /// \brief Set the consumed state of a given temporary value. 186259701Sdim void setState(const CXXBindTemporaryExpr *Tmp, ConsumedState State); 187259701Sdim 188259701Sdim /// \brief Remove the variable from our state map. 189259701Sdim void remove(const VarDecl *Var); 190259701Sdim 191259701Sdim /// \brief Tests to see if there is a mismatch in the states stored in two 192259701Sdim /// maps. 193259701Sdim /// 194259701Sdim /// \param Other -- The second map to compare against. 195259701Sdim bool operator!=(const ConsumedStateMap *Other) const; 196259701Sdim }; 197259701Sdim 198259701Sdim class ConsumedBlockInfo { 199259701Sdim std::vector<ConsumedStateMap*> StateMapsArray; 200259701Sdim std::vector<unsigned int> VisitOrder; 201259701Sdim 202259701Sdim public: 203259701Sdim ConsumedBlockInfo() { } 204259701Sdim 205259701Sdim ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph) 206259701Sdim : StateMapsArray(NumBlocks, 0), VisitOrder(NumBlocks, 0) { 207259701Sdim unsigned int VisitOrderCounter = 0; 208259701Sdim for (PostOrderCFGView::iterator BI = SortedGraph->begin(), 209259701Sdim BE = SortedGraph->end(); BI != BE; ++BI) { 210259701Sdim VisitOrder[(*BI)->getBlockID()] = VisitOrderCounter++; 211259701Sdim } 212259701Sdim } 213259701Sdim 214259701Sdim bool allBackEdgesVisited(const CFGBlock *CurrBlock, 215259701Sdim const CFGBlock *TargetBlock); 216259701Sdim 217259701Sdim void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap, 218259701Sdim bool &AlreadyOwned); 219259701Sdim void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap); 220259701Sdim 221259701Sdim ConsumedStateMap* borrowInfo(const CFGBlock *Block); 222259701Sdim 223259701Sdim void discardInfo(const CFGBlock *Block); 224259701Sdim 225259701Sdim ConsumedStateMap* getInfo(const CFGBlock *Block); 226259701Sdim 227259701Sdim bool isBackEdge(const CFGBlock *From, const CFGBlock *To); 228259701Sdim bool isBackEdgeTarget(const CFGBlock *Block); 229259701Sdim }; 230259701Sdim 231259701Sdim /// A class that handles the analysis of uniqueness violations. 232259701Sdim class ConsumedAnalyzer { 233259701Sdim 234259701Sdim ConsumedBlockInfo BlockInfo; 235259701Sdim ConsumedStateMap *CurrStates; 236259701Sdim 237259701Sdim ConsumedState ExpectedReturnState; 238259701Sdim 239259701Sdim void determineExpectedReturnState(AnalysisDeclContext &AC, 240259701Sdim const FunctionDecl *D); 241259701Sdim bool hasConsumableAttributes(const CXXRecordDecl *RD); 242259701Sdim bool splitState(const CFGBlock *CurrBlock, 243259701Sdim const ConsumedStmtVisitor &Visitor); 244259701Sdim 245259701Sdim public: 246259701Sdim 247259701Sdim ConsumedWarningsHandlerBase &WarningsHandler; 248259701Sdim 249259701Sdim ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler) 250259701Sdim : WarningsHandler(WarningsHandler) {} 251259701Sdim 252259701Sdim ConsumedState getExpectedReturnState() const { return ExpectedReturnState; } 253259701Sdim 254259701Sdim /// \brief Check a function's CFG for consumed violations. 255259701Sdim /// 256259701Sdim /// We traverse the blocks in the CFG, keeping track of the state of each 257259701Sdim /// value who's type has uniquness annotations. If methods are invoked in 258259701Sdim /// the wrong state a warning is issued. Each block in the CFG is traversed 259259701Sdim /// exactly once. 260259701Sdim void run(AnalysisDeclContext &AC); 261259701Sdim }; 262259701Sdim}} // end namespace clang::consumed 263259701Sdim 264259701Sdim#endif 265