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_CONSUMED_H
  16 #define LLVM_CLANG_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/AnalysisContext.h"
  22 #include "clang/Analysis/Analyses/PostOrderCFGView.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(NULL) {}
 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 variable from our state map.
 189     void remove(const VarDecl *Var);
 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
 205     ConsumedBlockInfo(unsigned int NumBlocks, PostOrderCFGView *SortedGraph)
 206         : StateMapsArray(NumBlocks, 0), VisitOrder(NumBlocks, 0) {
 207       unsigned int VisitOrderCounter = 0;
 208       for (PostOrderCFGView::iterator BI = SortedGraph->begin(),
 209            BE = SortedGraph->end(); BI != BE; ++BI) {
 210         VisitOrder[(*BI)->getBlockID()] = VisitOrderCounter++;
 211       }
 212     }
 213
 214     bool allBackEdgesVisited(const CFGBlock *CurrBlock,
 215                              const CFGBlock *TargetBlock);
 216
 217     void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap,
 218                  bool &AlreadyOwned);
 219     void addInfo(const CFGBlock *Block, ConsumedStateMap *StateMap);
 220
 221     ConsumedStateMap* borrowInfo(const CFGBlock *Block);
 222
 223     void discardInfo(const CFGBlock *Block);
 224
 225     ConsumedStateMap* getInfo(const CFGBlock *Block);
 226
 227     bool isBackEdge(const CFGBlock *From, const CFGBlock *To);
 228     bool isBackEdgeTarget(const CFGBlock *Block);
 229   };
 230
 231   /// A class that handles the analysis of uniqueness violations.
 232   class ConsumedAnalyzer {
 233
 234     ConsumedBlockInfo BlockInfo;
 235     ConsumedStateMap *CurrStates;
 236
 237     ConsumedState ExpectedReturnState;
 238
 239     void determineExpectedReturnState(AnalysisDeclContext &AC,
 240                                       const FunctionDecl *D);
 241     bool hasConsumableAttributes(const CXXRecordDecl *RD);
 242     bool splitState(const CFGBlock *CurrBlock,
 243                     const ConsumedStmtVisitor &Visitor);
 244
 245   public:
 246
 247     ConsumedWarningsHandlerBase &WarningsHandler;
 248
 249     ConsumedAnalyzer(ConsumedWarningsHandlerBase &WarningsHandler)
 250         : WarningsHandler(WarningsHandler) {}
 251
 252     ConsumedState getExpectedReturnState() const { return ExpectedReturnState; }
 253
 254     /// \brief Check a function's CFG for consumed violations.
 255     ///
 256     /// We traverse the blocks in the CFG, keeping track of the state of each
 257     /// value who's type has uniquness annotations.  If methods are invoked in
 258     /// the wrong state a warning is issued.  Each block in the CFG is traversed
 259     /// exactly once.
 260     void run(AnalysisDeclContext &AC);
 261   };
 262 }} // end namespace clang::consumed
 263
 264 #endif