LEFT | RIGHT |
1 //== GRState*h - Path-Sens. "State" for tracking valuues -----*- C++ -*--==// | 1 //== GRState.h - Path-sensitive "State" for tracking values -----*- C++ -*--==// |
2 // | 2 // |
3 // The LLVM Compiler Infrastructure | 3 // The LLVM Compiler Infrastructure |
4 // | 4 // |
5 // This file is distributed under the University of Illinois Open Source | 5 // This file is distributed under the University of Illinois Open Source |
6 // License. See LICENSE.TXT for details. | 6 // License. See LICENSE.TXT for details. |
7 // | 7 // |
8 //===----------------------------------------------------------------------===// | 8 //===----------------------------------------------------------------------===// |
9 // | 9 // |
10 // This file defines SymbolRef, ExprBindKey, and GRState* | 10 // This file defines SymbolRef, ExprBindKey, and GRState*. |
11 // | 11 // |
12 //===----------------------------------------------------------------------===// | 12 //===----------------------------------------------------------------------===// |
13 | 13 |
14 #ifndef LLVM_CLANG_ANALYSIS_VALUESTATE_H | 14 #ifndef LLVM_CLANG_ANALYSIS_VALUESTATE_H |
15 #define LLVM_CLANG_ANALYSIS_VALUESTATE_H | 15 #define LLVM_CLANG_ANALYSIS_VALUESTATE_H |
16 | 16 |
17 #include "clang/Checker/PathSensitive/ConstraintManager.h" | 17 #include "clang/Checker/PathSensitive/ConstraintManager.h" |
18 #include "clang/Checker/PathSensitive/Environment.h" | 18 #include "clang/Checker/PathSensitive/Environment.h" |
19 #include "clang/Checker/PathSensitive/Store.h" | 19 #include "clang/Checker/PathSensitive/Store.h" |
20 #include "clang/Checker/PathSensitive/ValueManager.h" | 20 #include "clang/Checker/PathSensitive/ValueManager.h" |
(...skipping 24 matching lines...) Expand all Loading... |
45 | 45 |
46 template <typename T> struct GRStateTrait { | 46 template <typename T> struct GRStateTrait { |
47 typedef typename T::data_type data_type; | 47 typedef typename T::data_type data_type; |
48 static inline void* GDMIndex() { return &T::TagInt; } | 48 static inline void* GDMIndex() { return &T::TagInt; } |
49 static inline void* MakeVoidPtr(data_type D) { return (void*) D; } | 49 static inline void* MakeVoidPtr(data_type D) { return (void*) D; } |
50 static inline data_type MakeData(void* const* P) { | 50 static inline data_type MakeData(void* const* P) { |
51 return P ? (data_type) *P : (data_type) 0; | 51 return P ? (data_type) *P : (data_type) 0; |
52 } | 52 } |
53 }; | 53 }; |
54 | 54 |
55 //===----------------------------------------------------------------------===// | |
56 // GRState- An ImmutableMap type Stmt*/Decl*/Symbols to SVals. | |
57 //===----------------------------------------------------------------------===// | |
58 | |
59 class GRStateManager; | 55 class GRStateManager; |
60 | 56 |
61 /// GRState - This class encapsulates the actual data values for | 57 /// GRState - This class encapsulates: |
62 /// for a "state" in our symbolic value tracking. It is intended to be | 58 /// |
63 /// used as a functional object; that is once it is created and made | 59 /// 1. A mapping from expressions to values (Environment) |
64 /// "persistent" in a FoldingSet its values will never change. | 60 /// 2. A mapping from locations to values (Store) |
| 61 /// 3. Constraints on symbolic values (GenericDataMap) |
| 62 /// |
| 63 /// Together these represent the "abstract state" of a program. |
| 64 /// |
| 65 /// GRState is intended to be used as a functional object; that is, |
| 66 /// once it is created and made "persistent" in a FoldingSet, its |
| 67 /// values will never change. |
65 class GRState : public llvm::FoldingSetNode { | 68 class GRState : public llvm::FoldingSetNode { |
66 public: | 69 public: |
67 typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; | 70 typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy; |
68 typedef llvm::ImmutableMap<void*, void*> GenericDataMap; | 71 typedef llvm::ImmutableMap<void*, void*> GenericDataMap; |
69 | 72 |
70 private: | 73 private: |
71 void operator=(const GRState& R) const; // Do not implement. | 74 void operator=(const GRState& R) const; // Do not implement. |
72 | 75 |
73 friend class GRStateManager; | 76 friend class GRStateManager; |
74 | 77 |
75 GRStateManager *StateMgr; | 78 GRStateManager *StateMgr; |
76 Environment Env; | 79 Environment Env; // Maps a Stmt to its current SVal. |
77 Store St; | 80 Store St; // Maps a location to its current value. |
78 GenericDataMap GDM; | 81 GenericDataMap GDM; // Custom data stored by a client of this class. |
79 | 82 |
80 /// makeWithStore - Return a GRState with the same values as the current | 83 /// makeWithStore - Return a GRState with the same values as the current |
81 /// state with the exception of using the specified Store. | 84 /// state with the exception of using the specified Store. |
82 const GRState *makeWithStore(Store store) const; | 85 const GRState *makeWithStore(Store store) const; |
83 | 86 |
84 public: | 87 public: |
85 | 88 |
86 /// This ctor is used when creating the first GRState object. | 89 /// This ctor is used when creating the first GRState object. |
87 GRState(GRStateManager *mgr, const Environment& env, | 90 GRState(GRStateManager *mgr, const Environment& env, |
88 Store st, GenericDataMap gdm) | 91 Store st, GenericDataMap gdm) |
(...skipping 24 matching lines...) Expand all Loading... |
113 /// is a mapping from locations to values. | 116 /// is a mapping from locations to values. |
114 Store getStore() const { return St; } | 117 Store getStore() const { return St; } |
115 | 118 |
116 void setStore(Store s) { St = s; } | 119 void setStore(Store s) { St = s; } |
117 | 120 |
118 /// getGDM - Return the generic data map associated with this state. | 121 /// getGDM - Return the generic data map associated with this state. |
119 GenericDataMap getGDM() const { return GDM; } | 122 GenericDataMap getGDM() const { return GDM; } |
120 | 123 |
121 void setGDM(GenericDataMap gdm) { GDM = gdm; } | 124 void setGDM(GenericDataMap gdm) { GDM = gdm; } |
122 | 125 |
123 /// Profile - Profile the contents of a GRState object for use | 126 /// Profile - Profile the contents of a GRState object for use in a |
124 /// in a FoldingSet. | 127 /// FoldingSet. Two GRState objects are considered equal if they |
| 128 /// have the same Environment, Store, and GenericDataMap. |
125 static void Profile(llvm::FoldingSetNodeID& ID, const GRState* V) { | 129 static void Profile(llvm::FoldingSetNodeID& ID, const GRState* V) { |
126 V->Env.Profile(ID); | 130 V->Env.Profile(ID); |
127 ID.AddPointer(V->St); | 131 ID.AddPointer(V->St); |
128 V->GDM.Profile(ID); | 132 V->GDM.Profile(ID); |
129 } | 133 } |
130 | 134 |
131 /// Profile - Used to profile the contents of this object for inclusion | 135 /// Profile - Used to profile the contents of this object for inclusion |
132 /// in a FoldingSet. | 136 /// in a FoldingSet. |
133 void Profile(llvm::FoldingSetNodeID& ID) const { | 137 void Profile(llvm::FoldingSetNodeID& ID) const { |
134 Profile(ID, this); | 138 Profile(ID, this); |
(...skipping 21 matching lines...) Expand all Loading... |
156 // symbolic values. A call to "Assume" indicates an assumption being placed | 160 // symbolic values. A call to "Assume" indicates an assumption being placed |
157 // on one or symbolic values. Assume methods take the following inputs: | 161 // on one or symbolic values. Assume methods take the following inputs: |
158 // | 162 // |
159 // (1) A GRState object representing the current state. | 163 // (1) A GRState object representing the current state. |
160 // | 164 // |
161 // (2) The assumed constraint (which is specific to a given "Assume" method). | 165 // (2) The assumed constraint (which is specific to a given "Assume" method). |
162 // | 166 // |
163 // (3) A binary value "Assumption" that indicates whether the constraint is | 167 // (3) A binary value "Assumption" that indicates whether the constraint is |
164 // assumed to be true or false. | 168 // assumed to be true or false. |
165 // | 169 // |
166 // The output of "Assume" are two values: | 170 // The output of "Assume*" is a new GRState object with the added constraints. |
167 // | 171 // If no new state is feasible, NULL is returned. |
168 // (a) "isFeasible" is set to true or false to indicate whether or not | |
169 // the assumption is feasible. | |
170 // | |
171 // (b) A new GRState object with the added constraints. | |
172 // | |
173 // FIXME: (a) should probably disappear since it is redundant with (b). | |
174 // (i.e., (b) could just be set to NULL). | |
175 // | 172 // |
176 | 173 |
177 const GRState *Assume(DefinedOrUnknownSVal cond, bool assumption) const; | 174 const GRState *Assume(DefinedOrUnknownSVal cond, bool assumption) const; |
178 ·· | 175 |
| 176 /// This method assumes both "true" and "false" for 'cond', and |
| 177 /// returns both corresponding states. It's shorthand for doing |
| 178 /// 'Assume' twice. |
179 std::pair<const GRState*, const GRState*> | 179 std::pair<const GRState*, const GRState*> |
180 Assume(DefinedOrUnknownSVal cond) const; | 180 Assume(DefinedOrUnknownSVal cond) const; |
181 | 181 |
182 const GRState *AssumeInBound(DefinedOrUnknownSVal idx, | 182 const GRState *AssumeInBound(DefinedOrUnknownSVal idx, |
183 DefinedOrUnknownSVal upperBound, | 183 DefinedOrUnknownSVal upperBound, |
184 bool assumption) const; | 184 bool assumption) const; |
185 | 185 |
186 //==---------------------------------------------------------------------==// | 186 //==---------------------------------------------------------------------==// |
187 // Utility methods for getting regions. | 187 // Utility methods for getting regions. |
188 //==---------------------------------------------------------------------==// | 188 //==---------------------------------------------------------------------==// |
189 | 189 |
190 const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; | 190 const VarRegion* getRegion(const VarDecl *D, const LocationContext *LC) const; |
191 | 191 |
192 //==---------------------------------------------------------------------==// | 192 //==---------------------------------------------------------------------==// |
193 // Binding and retrieving values to/from the environment and symbolic store. | 193 // Binding and retrieving values to/from the environment and symbolic store. |
194 //==---------------------------------------------------------------------==// | 194 //==---------------------------------------------------------------------==// |
195 | 195 |
196 /// BindCompoundLiteral - Return the state that has the bindings currently | 196 /// BindCompoundLiteral - Return the state that has the bindings currently |
197 /// in 'state' plus the bindings for the CompoundLiteral. 'R' is the region | 197 /// in this state plus the bindings for the CompoundLiteral. |
198 /// for the compound literal and 'BegInit' and 'EndInit' represent an | |
199 /// array of initializer values. | |
200 const GRState *bindCompoundLiteral(const CompoundLiteralExpr* CL, | 198 const GRState *bindCompoundLiteral(const CompoundLiteralExpr* CL, |
201 const LocationContext *LC, | 199 const LocationContext *LC, |
202 SVal V) const; | 200 SVal V) const; |
203 | 201 |
204 /// Create a new state by binding the value 'V' to the statement 'S' in the | 202 /// Create a new state by binding the value 'V' to the statement 'S' in the |
205 /// state's environment. | 203 /// state's environment. |
206 const GRState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; | 204 const GRState *BindExpr(const Stmt *S, SVal V, bool Invalidate = true) const; |
207 | 205 |
208 /// Create a new state by binding the value 'V' and location 'locaton' to the | 206 /// Create a new state by binding the value 'V' and location 'locaton' to the |
209 /// statement 'S' in the state's environment. | 207 /// statement 'S' in the state's environment. |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
259 /// Get the lvalue for a field reference. | 257 /// Get the lvalue for a field reference. |
260 SVal getLValue(const FieldDecl *decl, SVal Base) const; | 258 SVal getLValue(const FieldDecl *decl, SVal Base) const; |
261 | 259 |
262 /// Get the lvalue for an array index. | 260 /// Get the lvalue for an array index. |
263 SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; | 261 SVal getLValue(QualType ElementType, SVal Idx, SVal Base) const; |
264 | 262 |
265 const llvm::APSInt *getSymVal(SymbolRef sym) const; | 263 const llvm::APSInt *getSymVal(SymbolRef sym) const; |
266 | 264 |
267 /// Returns the SVal bound to the statement 'S' in the state's environment. | 265 /// Returns the SVal bound to the statement 'S' in the state's environment. |
268 SVal getSVal(const Stmt* S) const; | 266 SVal getSVal(const Stmt* S) const; |
269 | 267 ·· |
270 /// Returns the location of the statement 'S' in the state's environment. | |
271 SVal getLoc(const Stmt* S) const; | |
272 | |
273 SVal getSValAsScalarOrLoc(const Stmt *Ex) const; | 268 SVal getSValAsScalarOrLoc(const Stmt *Ex) const; |
274 | 269 |
275 SVal getSVal(Loc LV, QualType T = QualType()) const; | 270 SVal getSVal(Loc LV, QualType T = QualType()) const; |
276 | 271 |
277 /// Returns the "raw" SVal bound to LV before any value simplfication. | 272 /// Returns the "raw" SVal bound to LV before any value simplfication. |
278 SVal getRawSVal(Loc LV, QualType T= QualType()) const; | 273 SVal getRawSVal(Loc LV, QualType T= QualType()) const; |
279 | 274 |
280 SVal getSVal(const MemRegion* R) const; | 275 SVal getSVal(const MemRegion* R) const; |
281 | 276 |
282 SVal getSValAsScalarOrLoc(const MemRegion *R) const; | 277 SVal getSValAsScalarOrLoc(const MemRegion *R) const; |
(...skipping 376 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
659 } | 654 } |
660 | 655 |
661 inline const llvm::APSInt *GRState::getSymVal(SymbolRef sym) const { | 656 inline const llvm::APSInt *GRState::getSymVal(SymbolRef sym) const { |
662 return getStateManager().getSymVal(this, sym); | 657 return getStateManager().getSymVal(this, sym); |
663 } | 658 } |
664 | 659 |
665 inline SVal GRState::getSVal(const Stmt* Ex) const { | 660 inline SVal GRState::getSVal(const Stmt* Ex) const { |
666 return Env.GetSVal(Ex, getStateManager().ValueMgr); | 661 return Env.GetSVal(Ex, getStateManager().ValueMgr); |
667 } | 662 } |
668 | 663 |
669 inline SVal GRState::getLoc(const Stmt* S) const { | |
670 return Env.GetLoc(S, getStateManager().ValueMgr); | |
671 } | |
672 | |
673 inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { | 664 inline SVal GRState::getSValAsScalarOrLoc(const Stmt *S) const { |
674 if (const Expr *Ex = dyn_cast<Expr>(S)) { | 665 if (const Expr *Ex = dyn_cast<Expr>(S)) { |
675 QualType T = Ex->getType(); | 666 QualType T = Ex->getType(); |
676 if (Loc::IsLocType(T) || T->isIntegerType()) | 667 if (Loc::IsLocType(T) || T->isIntegerType()) |
677 return getSVal(S); | 668 return getSVal(S); |
678 } | 669 } |
679 | 670 |
680 return UnknownVal(); | 671 return UnknownVal(); |
681 } | 672 } |
682 | 673 |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
757 template <typename CB> | 748 template <typename CB> |
758 CB GRState::scanReachableSymbols(const MemRegion * const *beg, | 749 CB GRState::scanReachableSymbols(const MemRegion * const *beg, |
759 const MemRegion * const *end) const { | 750 const MemRegion * const *end) const { |
760 CB cb(this); | 751 CB cb(this); |
761 scanReachableSymbols(beg, end, cb); | 752 scanReachableSymbols(beg, end, cb); |
762 return cb; | 753 return cb; |
763 } | 754 } |
764 } // end clang namespace | 755 } // end clang namespace |
765 | 756 |
766 #endif | 757 #endif |
LEFT | RIGHT |