blob: 60948062f6f9f54db3f9ba05668da9edaa0bae34 [file] [log] [blame]
Zhongxing Xu17892752008-10-08 02:50:44 +00001//== RegionStore.cpp - Field-sensitive store model --------------*- 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// This file defines a basic region store model. In this model, we do have field
11// sensitivity. But we assume nothing about the heap shape. So recursive data
12// structures are largely ignored. Basically we do 1-limiting analysis.
13// Parameter pointers are assumed with no aliasing. Pointee objects of
14// parameters are created lazily.
15//
16//===----------------------------------------------------------------------===//
17#include "clang/Analysis/PathSensitive/MemRegion.h"
18#include "clang/Analysis/PathSensitive/GRState.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000019#include "clang/Analysis/PathSensitive/GRStateTrait.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000020#include "clang/Analysis/Analyses/LiveVariables.h"
21
22#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000023#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000024#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000025#include "llvm/Support/Compiler.h"
26
27using namespace clang;
28
Zhongxing Xubaf03a72008-11-24 09:44:56 +000029// Actual Store type.
Zhongxing Xu1c96b242008-10-17 05:57:07 +000030typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000031
Ted Kremenek50dc1b32008-12-24 01:05:03 +000032//===----------------------------------------------------------------------===//
33// Region "Views"
34//===----------------------------------------------------------------------===//
35//
36// MemRegions can be layered on top of each other. This GDM entry tracks
37// what are the MemRegions that layer a given MemRegion.
38//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000039typedef llvm::ImmutableSet<const MemRegion*> RegionViews;
Ted Kremenek50dc1b32008-12-24 01:05:03 +000040namespace { class VISIBILITY_HIDDEN RegionViewMap {}; }
41static int RegionViewMapIndex = 0;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000042namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000043 template<> struct GRStateTrait<RegionViewMap>
44 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
45 RegionViews> > {
46
47 static void* GDMIndex() { return &RegionViewMapIndex; }
48 };
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000049}
Zhongxing Xu17892752008-10-08 02:50:44 +000050
Ted Kremenek50dc1b32008-12-24 01:05:03 +000051//===----------------------------------------------------------------------===//
52// Region "Extents"
53//===----------------------------------------------------------------------===//
54//
55// MemRegions represent chunks of memory with a size (their "extent"). This
56// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +000057//
Ted Kremenek50dc1b32008-12-24 01:05:03 +000058namespace { class VISIBILITY_HIDDEN RegionExtents {}; }
59static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000060namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000061 template<> struct GRStateTrait<RegionExtents>
62 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
63 static void* GDMIndex() { return &RegionExtentsIndex; }
64 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +000065}
66
Ted Kremenek50dc1b32008-12-24 01:05:03 +000067//===----------------------------------------------------------------------===//
68// Region "killsets".
69//===----------------------------------------------------------------------===//
70//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000071// RegionStore lazily adds value bindings to regions when the analyzer handles
72// assignment statements. Killsets track which default values have been
73// killed, thus distinguishing between "unknown" values and default
74// values. Regions are added to killset only when they are assigned "unknown"
75// directly, otherwise we should have their value in the region bindings.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000076//
77namespace { class VISIBILITY_HIDDEN RegionKills {}; }
Ted Kremenek2ed14be2008-12-05 00:47:52 +000078static int RegionKillsIndex = 0;
Ted Kremenekc48ea6e2008-12-04 02:08:27 +000079namespace clang {
Ted Kremenek2ed14be2008-12-05 00:47:52 +000080 template<> struct GRStateTrait<RegionKills>
Ted Kremenek50dc1b32008-12-24 01:05:03 +000081 : public GRStatePartialTrait< llvm::ImmutableSet<const MemRegion*> > {
Ted Kremenek2ed14be2008-12-05 00:47:52 +000082 static void* GDMIndex() { return &RegionKillsIndex; }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +000083 };
84}
85
Ted Kremenek50dc1b32008-12-24 01:05:03 +000086//===----------------------------------------------------------------------===//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000087// Regions with default values.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000088//===----------------------------------------------------------------------===//
89//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000090// This GDM entry tracks what regions have a default value if they have no bound
91// value and have not been killed.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000092//
93namespace { class VISIBILITY_HIDDEN RegionDefaultValue {}; }
94static int RegionDefaultValueIndex = 0;
95namespace clang {
96 template<> struct GRStateTrait<RegionDefaultValue>
97 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
98 static void* GDMIndex() { return &RegionDefaultValueIndex; }
99 };
100}
101
102//===----------------------------------------------------------------------===//
103// Main RegionStore logic.
104//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000105
Zhongxing Xu17892752008-10-08 02:50:44 +0000106namespace {
107
Ted Kremenek59e8f112009-03-03 01:35:36 +0000108class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
109 typedef llvm::DenseMap<const MemRegion*,
110 llvm::ImmutableSet<const MemRegion*> > Map;
111
112 llvm::ImmutableSet<const MemRegion*>::Factory F;
113 Map M;
114
115public:
116 void add(const MemRegion* Parent, const MemRegion* SubRegion) {
117 Map::iterator I = M.find(Parent);
118 M.insert(std::make_pair(Parent,
119 F.Add(I == M.end() ? F.GetEmptySet() : I->second, SubRegion)));
120 }
121
122 ~RegionStoreSubRegionMap() {}
123
Ted Kremenek5dc27462009-03-03 02:51:43 +0000124 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000125 Map::iterator I = M.find(Parent);
126
127 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000128 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000129
130 llvm::ImmutableSet<const MemRegion*> S = I->second;
131 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
132 SI != SE; ++SI) {
133 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000134 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000135 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000136
137 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000138 }
139};
140
Zhongxing Xu17892752008-10-08 02:50:44 +0000141class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
142 RegionBindingsTy::Factory RBFactory;
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000143 RegionViews::Factory RVFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000144
Zhongxing Xu17892752008-10-08 02:50:44 +0000145 GRStateManager& StateMgr;
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000146 const MemRegion* SelfRegion;
147 const ImplicitParamDecl *SelfDecl;
Zhongxing Xu17892752008-10-08 02:50:44 +0000148
149public:
150 RegionStoreManager(GRStateManager& mgr)
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000151 : StoreManager(mgr.getAllocator()),
152 RBFactory(mgr.getAllocator()),
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000153 RVFactory(mgr.getAllocator()),
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000154 StateMgr(mgr), SelfRegion(0), SelfDecl(0) {
155 if (const ObjCMethodDecl* MD =
156 dyn_cast<ObjCMethodDecl>(&StateMgr.getCodeDecl()))
157 SelfDecl = MD->getSelfDecl();
158 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000159
160 virtual ~RegionStoreManager() {}
161
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000162 MemRegionManager& getRegionManager() { return MRMgr; }
Ted Kremenek4f090272008-10-27 21:54:31 +0000163
Ted Kremenek14453bf2009-03-03 19:02:42 +0000164 SubRegionMap* getSubRegionMap(const GRState *state);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000165
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000166 const GRState* BindCompoundLiteral(const GRState* St,
167 const CompoundLiteralExpr* CL, SVal V);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000168
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000169 /// getLValueString - Returns an SVal representing the lvalue of a
170 /// StringLiteral. Within RegionStore a StringLiteral has an
171 /// associated StringRegion, and the lvalue of a StringLiteral is
172 /// the lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000173 SVal getLValueString(const GRState* St, const StringLiteral* S);
174
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000175 /// getLValueCompoundLiteral - Returns an SVal representing the
176 /// lvalue of a compound literal. Within RegionStore a compound
177 /// literal has an associated region, and the lvalue of the
178 /// compound literal is the lvalue of that region.
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000179 SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);
180
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000181 /// getLValueVar - Returns an SVal that represents the lvalue of a
182 /// variable. Within RegionStore a variable has an associated
183 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000184 SVal getLValueVar(const GRState* St, const VarDecl* VD);
185
186 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
187
188 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000189
190 SVal getLValueFieldOrIvar(const GRState* St, SVal Base, const Decl* D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000191
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000192 SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);
193
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000194 SVal getSizeInElements(const GRState* St, const MemRegion* R);
195
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000196 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
197 /// type. 'Array' represents the lvalue of the array being decayed
198 /// to a pointer, and the returned SVal represents the decayed
199 /// version of that lvalue (i.e., a pointer to the first element of
200 /// the array). This is called by GRExprEngine when evaluating
201 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000202 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000203
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000204 /// CastRegion - Used by GRExprEngine::VisitCast to handle casts from
205 /// a MemRegion* to a specific location type. 'R' is the region being
206 /// casted and 'CastToTy' the result type of the cast.
207 CastResult CastRegion(const GRState* state, const MemRegion* R,
208 QualType CastToTy);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000209
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000210 SVal EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R);
211
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000212 /// The high level logic for this method is this:
213 /// Retrieve (L)
214 /// if L has binding
215 /// return L's binding
216 /// else if L is in killset
217 /// return unknown
218 /// else
219 /// if L is on stack or heap
220 /// return undefined
221 /// else
222 /// return symbolic
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000223 SVal Retrieve(const GRState* state, Loc L, QualType T = QualType());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000224
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000225 const GRState* Bind(const GRState* St, Loc LV, SVal V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000226
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000227 Store Remove(Store store, Loc LV);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000228
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000229 Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000230
231 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
232 /// 'this' object (C++). When used when analyzing a normal function this
233 /// method returns NULL.
234 const MemRegion* getSelfRegion(Store) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000235 if (!SelfDecl)
236 return 0;
237
238 if (!SelfRegion) {
239 const ObjCMethodDecl *MD = cast<ObjCMethodDecl>(&StateMgr.getCodeDecl());
240 SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
241 MRMgr.getHeapRegion());
242 }
243
244 return SelfRegion;
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000245 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000246
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000247 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
248 /// It returns a new Store with these values removed, and populates LSymbols
249 // and DSymbols with the known set of live and dead symbols respectively.
250 Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +0000251 SymbolReaper& SymReaper,
252 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000253
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000254 const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal);
255
256 const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) {
257 return St;
258 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000259
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000260 const GRState* setExtent(const GRState* St, const MemRegion* R, SVal Extent);
261
Zhongxing Xu17892752008-10-08 02:50:44 +0000262 static inline RegionBindingsTy GetRegionBindings(Store store) {
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000263 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000264 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000265
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000266 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000267
268 void iterBindings(Store store, BindingsHandler& f) {
269 // FIXME: Implement.
270 }
Zhongxing Xua82512a2008-10-24 08:42:28 +0000271
272private:
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000273 const GRState* BindArray(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000274
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000275 /// Retrieve the values in a struct and return a CompoundVal, used when doing
276 /// struct copy:
277 /// struct s x, y;
278 /// x = y;
279 /// y's value is retrieved by this method.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000280 SVal RetrieveStruct(const GRState* St, const TypedRegion* R);
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000281
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000282 const GRState* BindStruct(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu63123d82008-11-23 04:30:35 +0000283
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000284 /// KillStruct - Set the entire struct to unknown.
285 const GRState* KillStruct(const GRState* St, const TypedRegion* R);
286
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000287 // Utility methods.
288 BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
289 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xu63123d82008-11-23 04:30:35 +0000290 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000291
292 const GRState* AddRegionView(const GRState* St,
293 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000294 const GRState* RemoveRegionView(const GRState* St,
295 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu17892752008-10-08 02:50:44 +0000296};
297
298} // end anonymous namespace
299
Ted Kremenek95c7b002008-10-24 01:04:59 +0000300StoreManager* clang::CreateRegionStoreManager(GRStateManager& StMgr) {
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000301 return new RegionStoreManager(StMgr);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000302}
303
Ted Kremenek14453bf2009-03-03 19:02:42 +0000304SubRegionMap* RegionStoreManager::getSubRegionMap(const GRState *state) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000305 RegionBindingsTy B = GetRegionBindings(state->getStore());
306 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
307
308 for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
309 if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
310 M->add(R->getSuperRegion(), R);
311 }
312
Ted Kremenek14453bf2009-03-03 19:02:42 +0000313 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000314}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000315
316/// getLValueString - Returns an SVal representing the lvalue of a
317/// StringLiteral. Within RegionStore a StringLiteral has an
318/// associated StringRegion, and the lvalue of a StringLiteral is the
319/// lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000320SVal RegionStoreManager::getLValueString(const GRState* St,
321 const StringLiteral* S) {
322 return loc::MemRegionVal(MRMgr.getStringRegion(S));
323}
324
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000325/// getLValueVar - Returns an SVal that represents the lvalue of a
326/// variable. Within RegionStore a variable has an associated
327/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000328SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
329 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
330}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000331
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000332/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
333/// of a compound literal. Within RegionStore a compound literal
334/// has an associated region, and the lvalue of the compound literal
335/// is the lvalue of that region.
336SVal
337RegionStoreManager::getLValueCompoundLiteral(const GRState* St,
338 const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000339 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
340}
341
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000342SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
343 SVal Base) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000344 return getLValueFieldOrIvar(St, Base, D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000345}
346
347SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
348 const FieldDecl* D) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000349 return getLValueFieldOrIvar(St, Base, D);
350}
351
352SVal RegionStoreManager::getLValueFieldOrIvar(const GRState* St, SVal Base,
353 const Decl* D) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000354 if (Base.isUnknownOrUndef())
355 return Base;
356
357 Loc BaseL = cast<Loc>(Base);
358 const MemRegion* BaseR = 0;
359
360 switch (BaseL.getSubKind()) {
361 case loc::MemRegionKind:
362 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
363 break;
364
365 case loc::SymbolValKind:
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000366 BaseR = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(&BaseL)->getSymbol());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000367 break;
368
369 case loc::GotoLabelKind:
370 case loc::FuncValKind:
371 // These are anormal cases. Flag an undefined value.
372 return UndefinedVal();
373
374 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000375 // While these seem funny, this can happen through casts.
376 // FIXME: What we should return is the field offset. For example,
377 // add the field offset to the integer value. That way funny things
378 // like this work properly: &(((struct foo *) 0xa)->f)
379 return Base;
380
381 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000382 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000383 return Base;
384 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000385
386 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
387 // of FieldDecl.
388 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
389 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000390
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000391 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000392}
393
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000394SVal RegionStoreManager::getLValueElement(const GRState* St,
395 SVal Base, SVal Offset) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000396
Ted Kremenekde7ec632009-03-09 22:44:49 +0000397 // If the base is an unknown or undefined value, just return it back.
398 // FIXME: For absolute pointer addresses, we just return that value back as
399 // well, although in reality we should return the offset added to that
400 // value.
401 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000402 return Base;
403
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000404 // Only handle integer offsets... for now.
405 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000406 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000407
Zhongxing Xua48f7372009-02-06 08:44:27 +0000408 const TypedRegion* BaseRegion = 0;
409
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000410 BaseRegion = isa<loc::SymbolVal>(Base)
411 ? MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(Base).getSymbol())
412 : cast<TypedRegion>(cast<loc::MemRegionVal>(Base).getRegion());
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000413
414 // Pointer of any type can be cast and used as array base.
415 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
416
417 if (!ElemR) {
418 //
419 // If the base region is not an ElementRegion, create one.
420 // This can happen in the following example:
421 //
422 // char *p = __builtin_alloc(10);
423 // p[1] = 8;
424 //
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000425 // Observe that 'p' binds to an TypedViewRegion<AllocaRegion>.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000426 //
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000427
428 // Offset might be unsigned. We have to convert it to signed ConcreteInt.
429 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&Offset)) {
430 const llvm::APSInt& OffI = CI->getValue();
431 if (OffI.isUnsigned()) {
432 llvm::APSInt Tmp = OffI;
433 Tmp.setIsSigned(true);
434 Offset = NonLoc::MakeVal(getBasicVals(), Tmp);
435 }
436 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000437 return loc::MemRegionVal(MRMgr.getElementRegion(Offset, BaseRegion));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000438 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000439
440 SVal BaseIdx = ElemR->getIndex();
441
442 if (!isa<nonloc::ConcreteInt>(BaseIdx))
443 return UnknownVal();
444
445 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
446 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
447 assert(BaseIdxI.isSigned());
448
449 // FIXME: This appears to be the assumption of this code. We should review
450 // whether or not BaseIdxI.getBitWidth() < OffI.getBitWidth(). If it
451 // can't we need to put a comment here. If it can, we should handle it.
452 assert(BaseIdxI.getBitWidth() >= OffI.getBitWidth());
Zhongxing Xue4d13932008-11-13 09:48:44 +0000453
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000454 const TypedRegion *ArrayR = ElemR->getArrayRegion();
455 SVal NewIdx;
456
457 if (OffI.isUnsigned() || OffI.getBitWidth() < BaseIdxI.getBitWidth()) {
458 // 'Offset' might be unsigned. We have to convert it to signed and
459 // possibly extend it.
460 llvm::APSInt Tmp = OffI;
461
462 if (OffI.getBitWidth() < BaseIdxI.getBitWidth())
463 Tmp.extend(BaseIdxI.getBitWidth());
464
465 Tmp.setIsSigned(true);
466 Tmp += BaseIdxI; // Compute the new offset.
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000467 NewIdx = NonLoc::MakeVal(getBasicVals(), Tmp);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000468 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000469 else
470 NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000471
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000472 return loc::MemRegionVal(MRMgr.getElementRegion(NewIdx, ArrayR));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000473}
474
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000475SVal RegionStoreManager::getSizeInElements(const GRState* St,
476 const MemRegion* R) {
477 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
478 // Get the type of the variable.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000479 QualType T = VR->getDesugaredRValueType(getContext());
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000480
Ted Kremenek14553ab2009-01-30 00:08:43 +0000481 // FIXME: Handle variable-length arrays.
482 if (isa<VariableArrayType>(T))
483 return UnknownVal();
484
485 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
486 // return the size as signed integer.
487 return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
488 }
489
490 // Clients can use ordinary variables as if they were arrays. These
491 // essentially are arrays of size 1.
492 return NonLoc::MakeIntVal(getBasicVals(), 1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000493 }
494
495 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
Zhongxing Xu6613d082008-11-24 02:18:56 +0000496 const StringLiteral* Str = SR->getStringLiteral();
Zhongxing Xud0fd3b72008-11-24 02:30:48 +0000497 // We intentionally made the size value signed because it participates in
498 // operations with signed indices.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000499 return NonLoc::MakeIntVal(getBasicVals(), Str->getByteLength()+1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000500 }
501
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000502 if (const TypedViewRegion* ATR = dyn_cast<TypedViewRegion>(R)) {
Ted Kremenek2e842572009-01-22 23:56:56 +0000503#if 0
504 // FIXME: This logic doesn't really work, as we can have all sorts of
505 // weird cases. For example, this crashes on test case 'rdar-6442306-1.m'.
506 // The weird cases come in when arbitrary casting comes into play, violating
507 // any type-safe programming.
508
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000509 GRStateRef state(St, StateMgr);
510
511 // Get the size of the super region in bytes.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000512 const SVal* Extent = state.get<RegionExtents>(ATR->getSuperRegion());
513 assert(Extent && "region extent not exist");
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000514
515 // Assume it's ConcreteInt for now.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000516 llvm::APSInt SSize = cast<nonloc::ConcreteInt>(*Extent).getValue();
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000517
518 // Get the size of the element in bits.
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000519 QualType LvT = ATR->getLValueType(getContext());
520 QualType ElemTy = cast<PointerType>(LvT.getTypePtr())->getPointeeType();
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000521
522 uint64_t X = getContext().getTypeSize(ElemTy);
523
524 const llvm::APSInt& ESize = getBasicVals().getValue(X, SSize.getBitWidth(),
525 false);
526
527 // Calculate the number of elements.
528
529 // FIXME: What do we do with signed-ness problem? Shall we make all APSInts
530 // signed?
531 if (SSize.isUnsigned())
532 SSize.setIsSigned(true);
533
534 // FIXME: move this operation into BasicVals.
535 const llvm::APSInt S =
536 (SSize * getBasicVals().getValue(8, SSize.getBitWidth(), false)) / ESize;
537
538 return NonLoc::MakeVal(getBasicVals(), S);
Ted Kremenek2e842572009-01-22 23:56:56 +0000539#else
540 ATR = ATR;
541 return UnknownVal();
542#endif
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000543 }
544
545 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
546 // FIXME: Unsupported yet.
547 FR = 0;
548 return UnknownVal();
549 }
Zhongxing Xu369f4292008-11-22 13:23:00 +0000550
Zhongxing Xu02ebefb2009-02-06 08:51:30 +0000551 if (isa<SymbolicRegion>(R)) {
Zhongxing Xua48f7372009-02-06 08:44:27 +0000552 return UnknownVal();
553 }
554
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000555 assert(0 && "Other regions are not supported yet.");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000556 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000557}
558
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000559/// ArrayToPointer - Emulates the "decay" of an array to a pointer
560/// type. 'Array' represents the lvalue of the array being decayed
561/// to a pointer, and the returned SVal represents the decayed
562/// version of that lvalue (i.e., a pointer to the first element of
563/// the array). This is called by GRExprEngine when evaluating casts
564/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000565SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000566 if (!isa<loc::MemRegionVal>(Array))
567 return UnknownVal();
568
569 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
570 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
571
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000572 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000573 return UnknownVal();
574
Zhongxing Xu63123d82008-11-23 04:30:35 +0000575 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000576 ElementRegion* ER = MRMgr.getElementRegion(Idx, ArrayR);
577
578 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000579}
580
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000581StoreManager::CastResult
582RegionStoreManager::CastRegion(const GRState* state, const MemRegion* R,
583 QualType CastToTy) {
584
585 // Return the same region if the region types are compatible.
586 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) {
587 ASTContext& Ctx = StateMgr.getContext();
588 QualType Ta = Ctx.getCanonicalType(TR->getLValueType(Ctx));
589 QualType Tb = Ctx.getCanonicalType(CastToTy);
590
591 if (Ta == Tb)
592 return CastResult(state, R);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000593 }
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000594
595 // FIXME: We should handle the case when we are casting *back* to a
596 // previous type. For example:
597 //
598 // void* x = ...;
599 // char* y = (char*) x;
600 // void* z = (void*) y; // <-- we should get the same region that is
601 // bound to 'x'
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000602 const MemRegion* ViewR = MRMgr.getTypedViewRegion(CastToTy, R);
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000603 return CastResult(AddRegionView(state, ViewR, R), ViewR);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000604}
605
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000606SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R) {
607 // Assume the base location is MemRegionVal(ElementRegion).
Ted Kremenek5dc27462009-03-03 02:51:43 +0000608 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000609 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000610
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000611 const TypedRegion* TR
612 = cast<TypedRegion>(cast<loc::MemRegionVal>(L).getRegion());
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000613
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000614 const ElementRegion* ER = dyn_cast<ElementRegion>(TR);
615
616 if (!ER) {
617 // If the region is not element region, create one with index 0. This can
618 // happen in the following example:
619 // char *p = foo();
620 // p += 3;
621 // Note that p binds to a TypedViewRegion(SymbolicRegion).
622 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
623 ER = MRMgr.getElementRegion(Idx, TR);
624 }
625
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000626 SVal Idx = ER->getIndex();
627
628 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
629 nonloc::ConcreteInt* Offset = dyn_cast<nonloc::ConcreteInt>(&R);
630
631 // Only support concrete integer indexes for now.
632 if (Base && Offset) {
Ted Kremenek610e81d2009-03-13 15:35:24 +0000633 // FIXME: For now, convert the signedness and bitwidth of offset in case
634 // they don't match. This can result from pointer arithmetic. In reality,
635 // we should figure out what are the proper semantics and implement them.
636 //
Ted Kremenek1060a3c2009-03-13 15:39:16 +0000637 // This addresses the test case test/Analysis/ptr-arith.c
638 //
Ted Kremenek610e81d2009-03-13 15:35:24 +0000639 nonloc::ConcreteInt OffConverted(getBasicVals().Convert(Base->getValue(),
640 Offset->getValue()));
641 SVal NewIdx = Base->EvalBinOp(getBasicVals(), Op, OffConverted);
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000642 const MemRegion* NewER = MRMgr.getElementRegion(NewIdx,
643 ER->getArrayRegion());
644 return Loc::MakeVal(NewER);
645
Ted Kremenek5dc27462009-03-03 02:51:43 +0000646 }
647
648 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000649}
650
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000651SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000652 assert(!isa<UnknownVal>(L) && "location unknown");
653 assert(!isa<UndefinedVal>(L) && "location undefined");
654
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000655 // FIXME: What does loc::SymbolVal represent? It represents the value
656 // of a location but that value is not known. In the future we should
657 // handle potential aliasing relationships; e.g. a loc::SymbolVal could
658 // be an alias for a particular region.
Zhongxing Xu779747c2009-02-20 05:19:30 +0000659 // Example:
660 // void foo(char* buf) {
661 // char c = *buf;
662 // }
663 if (isa<loc::SymbolVal>(L)) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000664 return UnknownVal();
Zhongxing Xu779747c2009-02-20 05:19:30 +0000665 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000666
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000667 // FIXME: Is this even possible? Shouldn't this be treated as a null
668 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000669 if (isa<loc::ConcreteInt>(L))
670 return UndefinedVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000671
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000672 // FIXME: Should this be refactored into GRExprEngine or GRStateManager?
673 // It seems that all StoreManagers would do the same thing here.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000674 if (isa<loc::FuncVal>(L))
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000675 return L;
676
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000677 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
678 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000679 const TypedRegion* R
680 = cast<TypedRegion>(cast<loc::MemRegionVal>(L).getRegion());
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000681 assert(R && "bad region");
682
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000683 // FIXME: We should eventually handle funny addressing. e.g.:
684 //
685 // int x = ...;
686 // int *p = &x;
687 // char *q = (char*) p;
688 // char c = *q; // returns the first byte of 'x'.
689 //
690 // Such funny addressing will occur due to layering of regions.
691
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000692 QualType RTy = R->getRValueType(getContext());
693 if (RTy->isStructureType())
694 return RetrieveStruct(St, R);
695 // FIXME: handle Vector types.
696 if (RTy->isVectorType())
Ted Kremenek265a3052009-02-24 02:23:11 +0000697 return UnknownVal();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000698
699 RegionBindingsTy B = GetRegionBindings(St->getStore());
700 RegionBindingsTy::data_type* V = B.lookup(R);
701
702 // Check if the region has a binding.
703 if (V)
704 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000705
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000706 GRStateRef state(St, StateMgr);
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000707
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000708 // Check if the region is in killset.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000709 if (state.contains<RegionKills>(R))
710 return UnknownVal();
711
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000712 // If the region is an element or field, it may have a default value.
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000713 if (isa<ElementRegion>(R) || isa<FieldRegion>(R)) {
714 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
715 GRStateTrait<RegionDefaultValue>::lookup_type D =
716 state.get<RegionDefaultValue>(SuperR);
717 if (D)
718 return *D;
719 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000720
721 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
722 const MemRegion *SR = IVR->getSuperRegion();
723
724 // If the super region is 'self' then return the symbol representing
725 // the value of the ivar upon entry to the method.
726 if (SR == SelfRegion) {
727 // FIXME: Do we need to handle the case where the super region
728 // has a view? We want to canonicalize the bindings.
729 return SVal::GetRValueSymbolVal(getSymbolManager(), R);
730 }
731
732 // Otherwise, we need a new symbol. For now return Unknown.
733 return UnknownVal();
734 }
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000735
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000736 // The location does not have a bound value. This means that it has
737 // the value it had upon its creation and/or entry to the analyzed
738 // function/method. These are either symbolic values or 'undefined'.
739
740 // We treat function parameters as symbolic values.
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000741 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
742 const VarDecl *VD = VR->getDecl();
743
Ted Kremenekcec35252009-03-04 00:23:05 +0000744 if (VD == SelfDecl)
745 return loc::MemRegionVal(getSelfRegion(0));
746
747 if (isa<ParmVarDecl>(VD) || isa<ImplicitParamDecl>(VD) ||
748 VD->hasGlobalStorage()) {
Zhongxing Xud8895f62009-02-19 09:56:08 +0000749 QualType VTy = VD->getType();
750 if (Loc::IsLocType(VTy) || VTy->isIntegerType())
751 return SVal::GetRValueSymbolVal(getSymbolManager(), VR);
752 else
753 return UnknownVal();
754 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000755 }
Ted Kremenek265a3052009-02-24 02:23:11 +0000756
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000757 if (MRMgr.onStack(R) || MRMgr.onHeap(R)) {
758 // All stack variables are considered to have undefined values
759 // upon creation. All heap allocated blocks are considered to
760 // have undefined values as well unless they are explicitly bound
761 // to specific values.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000762 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000763 }
764
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000765 // All other integer values are symbolic.
766 if (Loc::IsLocType(RTy) || RTy->isIntegerType())
767 return SVal::GetRValueSymbolVal(getSymbolManager(), R);
768 else
769 return UnknownVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000770}
771
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000772SVal RegionStoreManager::RetrieveStruct(const GRState* St,const TypedRegion* R){
773
774 Store store = St->getStore();
775 GRStateRef state(St, StateMgr);
776
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000777 // FIXME: Verify we want getRValueType instead of getLValueType.
778 QualType T = R->getRValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000779 assert(T->isStructureType());
780
781 const RecordType* RT = cast<RecordType>(T.getTypePtr());
782 RecordDecl* RD = RT->getDecl();
783 assert(RD->isDefinition());
784
785 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
786
Douglas Gregore267ff32008-12-11 20:41:00 +0000787 std::vector<FieldDecl *> Fields(RD->field_begin(), RD->field_end());
Douglas Gregor44b43212008-12-11 16:49:14 +0000788
Douglas Gregore267ff32008-12-11 20:41:00 +0000789 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
790 FieldEnd = Fields.rend();
791 Field != FieldEnd; ++Field) {
792 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000793 RegionBindingsTy B = GetRegionBindings(store);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000794 RegionBindingsTy::data_type* data = B.lookup(FR);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000795
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000796 SVal FieldValue;
797 if (data)
798 FieldValue = *data;
799 else if (state.contains<RegionKills>(FR))
800 FieldValue = UnknownVal();
801 else {
802 if (MRMgr.onStack(FR) || MRMgr.onHeap(FR))
803 FieldValue = UndefinedVal();
804 else
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000805 FieldValue = SVal::GetRValueSymbolVal(getSymbolManager(), FR);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000806 }
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000807
808 StructVal = getBasicVals().consVals(FieldValue, StructVal);
809 }
810
811 return NonLoc::MakeCompoundVal(T, StructVal, getBasicVals());
812}
813
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000814const GRState* RegionStoreManager::Bind(const GRState* St, Loc L, SVal V) {
815 // Currently we don't bind value to symbolic location. But if the logic is
816 // made clear, we might change this decision.
817 if (isa<loc::SymbolVal>(L))
818 return St;
Zhongxing Xu8fe63af2008-10-27 09:24:07 +0000819
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000820 // If we get here, the location should be a region.
821 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000822 assert(R);
823
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000824 // Check if the region is a struct region.
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000825 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000826 // FIXME: Verify we want getRValueType().
827 if (TR->getRValueType(getContext())->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000828 return BindStruct(St, TR, V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000829
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000830 Store store = St->getStore();
Zhongxing Xu17892752008-10-08 02:50:44 +0000831 RegionBindingsTy B = GetRegionBindings(store);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000832
833 if (V.isUnknown()) {
834 // Remove the binding.
835 store = RBFactory.Remove(B, R).getRoot();
836
837 // Add the region to the killset.
838 GRStateRef state(St, StateMgr);
839 St = state.add<RegionKills>(R);
840 }
841 else
842 store = RBFactory.Add(B, R, V).getRoot();
843
844 return StateMgr.MakeStateWithStore(St, store);
Zhongxing Xu17892752008-10-08 02:50:44 +0000845}
846
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000847Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +0000848 const MemRegion* R = 0;
849
850 if (isa<loc::MemRegionVal>(L))
851 R = cast<loc::MemRegionVal>(L).getRegion();
852 else if (isa<loc::SymbolVal>(L))
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000853 R = MRMgr.getSymbolicRegion(cast<loc::SymbolVal>(L).getSymbol());
Ted Kremenek0964a062009-01-21 06:57:53 +0000854
855 if (R) {
856 RegionBindingsTy B = GetRegionBindings(store);
857 return RBFactory.Remove(B, R).getRoot();
858 }
859
860 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000861}
862
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000863const GRState* RegionStoreManager::BindDecl(const GRState* St,
864 const VarDecl* VD, SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000865
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000866 QualType T = VD->getType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000867 VarRegion* VR = MRMgr.getVarRegion(VD);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000868
Ted Kremenek0964a062009-01-21 06:57:53 +0000869 if (T->isArrayType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000870 return BindArray(St, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +0000871 if (T->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000872 return BindStruct(St, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +0000873
Ted Kremenek0964a062009-01-21 06:57:53 +0000874 return Bind(St, Loc::MakeVal(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +0000875}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000876
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000877// FIXME: this method should be merged into Bind().
878const GRState*
879RegionStoreManager::BindCompoundLiteral(const GRState* St,
880 const CompoundLiteralExpr* CL, SVal V) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000881 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000882 return Bind(St, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000883}
884
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000885const GRState* RegionStoreManager::setExtent(const GRState* St,
886 const MemRegion* R, SVal Extent) {
887 GRStateRef state(St, StateMgr);
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000888 return state.set<RegionExtents>(R, Extent);
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000889}
890
891
Ted Kremenek241677a2009-01-21 22:26:05 +0000892static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
Ted Kremenek02c4d2d2009-03-04 00:11:38 +0000893 if (loc::MemRegionVal *XR = dyn_cast<loc::MemRegionVal>(&X)) {
894 const MemRegion *R = XR->getRegion();
895
896 while (R) {
897 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
898 SymReaper.markLive(SR->getSymbol());
899 return;
900 }
901
902 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
903 R = SR->getSuperRegion();
904 continue;
905 }
906
907 break;
908 }
909
910 return;
911 }
912
Ted Kremenek241677a2009-01-21 22:26:05 +0000913 for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
914 SymReaper.markLive(*SI);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000915}
916
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000917Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +0000918 SymbolReaper& SymReaper,
919 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
920{
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000921
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000922 Store store = state->getStore();
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000923 RegionBindingsTy B = GetRegionBindings(store);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000924
925 // Lazily constructed backmap from MemRegions to SubRegions.
926 typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
927 typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
928
929 // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
930 // the ability to reuse memory. This way we can keep TmpAlloc around as
931 // an instance variable of RegionStoreManager (avoiding repeated malloc
932 // overhead).
933 llvm::BumpPtrAllocator TmpAlloc;
934
935 // Factory objects.
936 SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
937 SubRegionsTy::Factory SubRegF(TmpAlloc);
938
939 // The backmap from regions to subregions.
940 SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
941
942 // Do a pass over the regions in the store. For VarRegions we check if
943 // the variable is still live and if so add it to the list of live roots.
944 // For other regions we populate our region backmap.
Zhongxing Xuc2fdb072009-03-18 01:54:31 +0000945
946 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
947
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000948 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Zhongxing Xuc2fdb072009-03-18 01:54:31 +0000949 IntermediateRoots.push_back(I.getKey());
950 }
951
952 while (!IntermediateRoots.empty()) {
953 const MemRegion* R = IntermediateRoots.back();
954 IntermediateRoots.pop_back();
955
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000956 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
Ted Kremenek241677a2009-01-21 22:26:05 +0000957 if (SymReaper.isLive(Loc, VR->getDecl()))
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000958 RegionRoots.push_back(VR); // This is a live "root".
959 }
960 else {
961 // Get the super region for R.
962 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
Zhongxing Xuc2fdb072009-03-18 01:54:31 +0000963
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000964 // Get the current set of subregions for SuperR.
965 const SubRegionsTy* SRptr = SubRegMap.lookup(SuperR);
966 SubRegionsTy SR = SRptr ? *SRptr : SubRegF.GetEmptySet();
Zhongxing Xuc2fdb072009-03-18 01:54:31 +0000967
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000968 // Add R to the subregions of SuperR.
969 SubRegMap = SubRegMapF.Add(SubRegMap, SuperR, SubRegF.Add(SR, R));
Zhongxing Xuc2fdb072009-03-18 01:54:31 +0000970
971 // Super region may be VarRegion or subregion of another VarRegion. Add it
972 // to the work list.
973 if (isa<SubRegion>(SuperR))
974 IntermediateRoots.push_back(SuperR);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000975 }
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000976 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000977
978 // Process the worklist of RegionRoots. This performs a "mark-and-sweep"
979 // of the store. We want to find all live symbols and dead regions.
980 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
981
982 while (!RegionRoots.empty()) {
983 // Dequeue the next region on the worklist.
984 const MemRegion* R = RegionRoots.back();
985 RegionRoots.pop_back();
Zhongxing Xu8916d5b2008-11-10 09:39:04 +0000986
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000987 // Check if we have already processed this region.
988 if (Marked.count(R)) continue;
989
990 // Mark this region as processed. This is needed for termination in case
991 // a region is referenced more than once.
992 Marked.insert(R);
993
994 // Mark the symbol for any live SymbolicRegion as "live". This means we
995 // should continue to track that symbol.
996 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
Ted Kremenek241677a2009-01-21 22:26:05 +0000997 SymReaper.markLive(SymR->getSymbol());
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000998
999 // Get the data binding for R (if any).
1000 RegionBindingsTy::data_type* Xptr = B.lookup(R);
1001 if (Xptr) {
1002 SVal X = *Xptr;
Ted Kremenek241677a2009-01-21 22:26:05 +00001003 UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001004
1005 // If X is a region, then add it the RegionRoots.
1006 if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
1007 RegionRoots.push_back(RegionX->getRegion());
1008 }
1009
1010 // Get the subregions of R. These are RegionRoots as well since they
1011 // represent values that are also bound to R.
1012 const SubRegionsTy* SRptr = SubRegMap.lookup(R);
1013 if (!SRptr) continue;
1014 SubRegionsTy SR = *SRptr;
1015
1016 for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
1017 RegionRoots.push_back(*I);
1018 }
1019
1020 // We have now scanned the store, marking reachable regions and symbols
1021 // as live. We now remove all the regions that are dead from the store
Ted Kremenek3de2d3c2009-03-05 04:50:08 +00001022 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001023 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1024 const MemRegion* R = I.getKey();
1025
1026 // If this region live? Is so, none of its symbols are dead.
1027 if (Marked.count(R))
1028 continue;
1029
1030 // Remove this dead region from the store.
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001031 store = Remove(store, Loc::MakeVal(R));
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001032
1033 // Mark all non-live symbols that this region references as dead.
Ted Kremenek241677a2009-01-21 22:26:05 +00001034 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1035 SymReaper.maybeDead(SymR->getSymbol());
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001036
1037 SVal X = I.getData();
1038 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
Ted Kremenek241677a2009-01-21 22:26:05 +00001039 for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001040 }
1041
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001042 return store;
1043}
1044
Zhongxing Xua071eb02008-10-24 06:01:33 +00001045void RegionStoreManager::print(Store store, std::ostream& Out,
1046 const char* nl, const char *sep) {
1047 llvm::raw_os_ostream OS(Out);
1048 RegionBindingsTy B = GetRegionBindings(store);
1049 OS << "Store:" << nl;
1050
1051 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1052 OS << ' '; I.getKey()->print(OS); OS << " : ";
1053 I.getData().print(OS); OS << nl;
1054 }
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +00001055}
Zhongxing Xua82512a2008-10-24 08:42:28 +00001056
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001057const GRState* RegionStoreManager::BindArray(const GRState* St,
1058 const TypedRegion* R, SVal Init) {
Ted Kremenek6eddeb12008-12-13 21:49:13 +00001059
1060 // FIXME: Verify we should use getLValueType or getRValueType.
Zhongxing Xu2ef93722008-12-14 03:14:52 +00001061 QualType T = R->getRValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001062 assert(T->isArrayType());
1063
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001064 // When we are binding the whole array, it always has default value 0.
1065 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001066 St = state.set<RegionDefaultValue>(R, NonLoc::MakeIntVal(getBasicVals(), 0,
1067 false));
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001068
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001069 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1070
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001071 llvm::APSInt Size(CAT->getSize(), false);
Sebastian Redl1be3da52009-01-26 19:54:12 +00001072 llvm::APSInt i = getBasicVals().getValue(0, Size.getBitWidth(),
1073 Size.isUnsigned());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001074
1075 // Check if the init expr is a StringLiteral.
1076 if (isa<loc::MemRegionVal>(Init)) {
1077 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1078 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1079 const char* str = S->getStrData();
1080 unsigned len = S->getByteLength();
1081 unsigned j = 0;
1082
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001083 // Copy bytes from the string literal into the target array. Trailing bytes
1084 // in the array that are not covered by the string literal are initialized
1085 // to zero.
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001086 for (; i < Size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001087 if (j >= len)
1088 break;
1089
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001090 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
1091 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
1092
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001093 SVal V = NonLoc::MakeVal(getBasicVals(), str[j], sizeof(char)*8, true);
1094 St = Bind(St, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001095 }
1096
Zhongxing Xubd4f7452009-03-09 06:49:50 +00001097 return St;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001098 }
1099
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001100
1101 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
1102
1103 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1104
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001105 for (; i < Size; ++i, ++VI) {
1106 // The init list might be shorter than the array decl.
1107 if (VI == VE)
1108 break;
1109
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001110 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001111 ElementRegion* ER = MRMgr.getElementRegion(Idx, R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001112
1113 if (CAT->getElementType()->isStructureType())
1114 St = BindStruct(St, ER, *VI);
1115 else
1116 St = Bind(St, Loc::MakeVal(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001117 }
1118
Zhongxing Xubd4f7452009-03-09 06:49:50 +00001119 return St;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001120}
1121
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001122const GRState*
1123RegionStoreManager::BindStruct(const GRState* St, const TypedRegion* R, SVal V){
Ted Kremenek6eddeb12008-12-13 21:49:13 +00001124 // FIXME: Verify that we should use getRValueType or getLValueType.
1125 QualType T = R->getRValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001126 assert(T->isStructureType());
1127
Zhongxing Xub13ecdb2009-03-12 03:45:35 +00001128 const RecordType* RT = T->getAsRecordType();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001129 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001130
1131 if (!RD->isDefinition())
1132 return St;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001133
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001134 if (V.isUnknown())
1135 return KillStruct(St, R);
1136
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001137 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001138 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1139 RecordDecl::field_iterator FI = RD->field_begin(), FE = RD->field_end();
1140
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001141 for (; FI != FE; ++FI, ++VI) {
1142
1143 // There may be fewer values than fields only when we are initializing a
1144 // struct decl. In this case, mark the region as having default value.
1145 if (VI == VE) {
Zhongxing Xu13020162008-12-24 07:29:24 +00001146 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001147 const NonLoc& Idx = NonLoc::MakeIntVal(getBasicVals(), 0, false);
1148 St = state.set<RegionDefaultValue>(R, Idx);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001149 break;
1150 }
1151
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001152 QualType FTy = (*FI)->getType();
1153 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1154
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001155 if (Loc::IsLocType(FTy) || FTy->isIntegerType())
1156 St = Bind(St, Loc::MakeVal(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001157
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001158 else if (FTy->isArrayType())
1159 St = BindArray(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001160
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001161 else if (FTy->isStructureType())
1162 St = BindStruct(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001163 }
1164
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001165 return St;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001166}
1167
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001168const GRState* RegionStoreManager::KillStruct(const GRState* St,
1169 const TypedRegion* R){
1170 GRStateRef state(St, StateMgr);
1171
1172 // Kill the struct region because it is assigned "unknown".
1173 St = state.add<RegionKills>(R);
1174
1175 // Set the default value of the struct region to "unknown".
1176 St = state.set<RegionDefaultValue>(R, UnknownVal());
1177
1178 Store store = St->getStore();
1179 RegionBindingsTy B = GetRegionBindings(store);
1180
1181 // Remove all bindings for the subregions of the struct.
1182 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1183 const MemRegion* r = I.getKey();
1184 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
1185 if (sr->isSubRegionOf(R))
1186 store = Remove(store, Loc::MakeVal(sr));
Zhongxing Xu9c2a3db2009-01-13 03:07:41 +00001187 // FIXME: Maybe we should also remove the bindings for the "views" of the
1188 // subregions.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001189 }
1190
1191 return StateMgr.MakeStateWithStore(St, store);
1192}
1193
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001194const GRState* RegionStoreManager::AddRegionView(const GRState* St,
1195 const MemRegion* View,
1196 const MemRegion* Base) {
1197 GRStateRef state(St, StateMgr);
1198
1199 // First, retrieve the region view of the base region.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001200 const RegionViews* d = state.get<RegionViewMap>(Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001201 RegionViews L = d ? *d : RVFactory.GetEmptySet();
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001202
1203 // Now add View to the region view.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001204 L = RVFactory.Add(L, View);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001205
1206 // Create a new state with the new region view.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001207 return state.set<RegionViewMap>(Base, L);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001208}
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001209
1210const GRState* RegionStoreManager::RemoveRegionView(const GRState* St,
1211 const MemRegion* View,
1212 const MemRegion* Base) {
1213 GRStateRef state(St, StateMgr);
1214
1215 // Retrieve the region view of the base region.
1216 const RegionViews* d = state.get<RegionViewMap>(Base);
1217
1218 // If the base region has no view, return.
1219 if (!d)
1220 return St;
1221
1222 // Remove the view.
1223 RegionViews V = *d;
1224 V = RVFactory.Remove(V, View);
1225
1226 return state.set<RegionViewMap>(Base, V);
1227}