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
30namespace clang {
31
32class AnalysisDeclContext;
33class CXXBindTemporaryExpr;
34class FunctionDecl;
35class PostOrderCFGView;
36class Stmt;
37class VarDecl;
38
39namespace 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
273