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