contrib/llvm-project/clang/include/clang/Analysis/Analyses/Consumed.h

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