Home | History | Annotate | Download | only in Analyses
      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/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
    266