contrib/llvm/tools/clang/include/clang/Analysis/Analyses/Consumed.h

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