blob: 354ad5c57ab914113164f8d05a8699101aedefa0 [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"
Zhongxing Xu41fd0182009-05-06 11:51:48 +000021#include "clang/Basic/TargetInfo.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000022
23#include "llvm/ADT/ImmutableMap.h"
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000024#include "llvm/ADT/ImmutableList.h"
Zhongxing Xua071eb02008-10-24 06:01:33 +000025#include "llvm/Support/raw_ostream.h"
Zhongxing Xu17892752008-10-08 02:50:44 +000026#include "llvm/Support/Compiler.h"
27
28using namespace clang;
29
Zhongxing Xubaf03a72008-11-24 09:44:56 +000030// Actual Store type.
Zhongxing Xu1c96b242008-10-17 05:57:07 +000031typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000032
Ted Kremenek50dc1b32008-12-24 01:05:03 +000033//===----------------------------------------------------------------------===//
34// Region "Views"
35//===----------------------------------------------------------------------===//
36//
37// MemRegions can be layered on top of each other. This GDM entry tracks
38// what are the MemRegions that layer a given MemRegion.
39//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000040typedef llvm::ImmutableSet<const MemRegion*> RegionViews;
Ted Kremenek50dc1b32008-12-24 01:05:03 +000041namespace { class VISIBILITY_HIDDEN RegionViewMap {}; }
42static int RegionViewMapIndex = 0;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000043namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000044 template<> struct GRStateTrait<RegionViewMap>
45 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
46 RegionViews> > {
47
48 static void* GDMIndex() { return &RegionViewMapIndex; }
49 };
Zhongxing Xudc0a25d2008-11-16 04:07:26 +000050}
Zhongxing Xu17892752008-10-08 02:50:44 +000051
Zhongxing Xu20794942009-05-06 08:33:50 +000052// RegionCasts records the current cast type of a region.
53namespace { class VISIBILITY_HIDDEN RegionCasts {}; }
54static int RegionCastsIndex = 0;
55namespace clang {
56 template<> struct GRStateTrait<RegionCasts>
57 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*,
58 QualType> > {
59 static void* GDMIndex() { return &RegionCastsIndex; }
60 };
61}
62
Ted Kremenek50dc1b32008-12-24 01:05:03 +000063//===----------------------------------------------------------------------===//
64// Region "Extents"
65//===----------------------------------------------------------------------===//
66//
67// MemRegions represent chunks of memory with a size (their "extent"). This
68// GDM entry tracks the extents for regions. Extents are in bytes.
Ted Kremenekd6cfbe42009-01-07 22:18:50 +000069//
Ted Kremenek50dc1b32008-12-24 01:05:03 +000070namespace { class VISIBILITY_HIDDEN RegionExtents {}; }
71static int RegionExtentsIndex = 0;
Zhongxing Xubaf03a72008-11-24 09:44:56 +000072namespace clang {
Ted Kremenek50dc1b32008-12-24 01:05:03 +000073 template<> struct GRStateTrait<RegionExtents>
74 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
75 static void* GDMIndex() { return &RegionExtentsIndex; }
76 };
Zhongxing Xubaf03a72008-11-24 09:44:56 +000077}
78
Ted Kremenek50dc1b32008-12-24 01:05:03 +000079//===----------------------------------------------------------------------===//
80// Region "killsets".
81//===----------------------------------------------------------------------===//
82//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000083// RegionStore lazily adds value bindings to regions when the analyzer handles
84// assignment statements. Killsets track which default values have been
85// killed, thus distinguishing between "unknown" values and default
86// values. Regions are added to killset only when they are assigned "unknown"
87// directly, otherwise we should have their value in the region bindings.
Ted Kremenek50dc1b32008-12-24 01:05:03 +000088//
89namespace { class VISIBILITY_HIDDEN RegionKills {}; }
Ted Kremenek2ed14be2008-12-05 00:47:52 +000090static int RegionKillsIndex = 0;
Ted Kremenekc48ea6e2008-12-04 02:08:27 +000091namespace clang {
Ted Kremenek2ed14be2008-12-05 00:47:52 +000092 template<> struct GRStateTrait<RegionKills>
Ted Kremenek50dc1b32008-12-24 01:05:03 +000093 : public GRStatePartialTrait< llvm::ImmutableSet<const MemRegion*> > {
Ted Kremenek2ed14be2008-12-05 00:47:52 +000094 static void* GDMIndex() { return &RegionKillsIndex; }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +000095 };
96}
97
Ted Kremenek50dc1b32008-12-24 01:05:03 +000098//===----------------------------------------------------------------------===//
Zhongxing Xu5834ed62009-01-13 01:49:57 +000099// Regions with default values.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000100//===----------------------------------------------------------------------===//
101//
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000102// This GDM entry tracks what regions have a default value if they have no bound
103// value and have not been killed.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000104//
105namespace { class VISIBILITY_HIDDEN RegionDefaultValue {}; }
106static int RegionDefaultValueIndex = 0;
107namespace clang {
108 template<> struct GRStateTrait<RegionDefaultValue>
109 : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
110 static void* GDMIndex() { return &RegionDefaultValueIndex; }
111 };
112}
113
114//===----------------------------------------------------------------------===//
115// Main RegionStore logic.
116//===----------------------------------------------------------------------===//
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000117
Zhongxing Xu17892752008-10-08 02:50:44 +0000118namespace {
119
Ted Kremenek59e8f112009-03-03 01:35:36 +0000120class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
121 typedef llvm::DenseMap<const MemRegion*,
122 llvm::ImmutableSet<const MemRegion*> > Map;
123
124 llvm::ImmutableSet<const MemRegion*>::Factory F;
125 Map M;
126
127public:
128 void add(const MemRegion* Parent, const MemRegion* SubRegion) {
129 Map::iterator I = M.find(Parent);
130 M.insert(std::make_pair(Parent,
131 F.Add(I == M.end() ? F.GetEmptySet() : I->second, SubRegion)));
132 }
133
134 ~RegionStoreSubRegionMap() {}
135
Ted Kremenek5dc27462009-03-03 02:51:43 +0000136 bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000137 Map::iterator I = M.find(Parent);
138
139 if (I == M.end())
Ted Kremenek5dc27462009-03-03 02:51:43 +0000140 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000141
142 llvm::ImmutableSet<const MemRegion*> S = I->second;
143 for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
144 SI != SE; ++SI) {
145 if (!V.Visit(Parent, *SI))
Ted Kremenek5dc27462009-03-03 02:51:43 +0000146 return false;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000147 }
Ted Kremenek5dc27462009-03-03 02:51:43 +0000148
149 return true;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000150 }
151};
152
Zhongxing Xu17892752008-10-08 02:50:44 +0000153class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
154 RegionBindingsTy::Factory RBFactory;
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000155 RegionViews::Factory RVFactory;
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000156
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000157 const MemRegion* SelfRegion;
158 const ImplicitParamDecl *SelfDecl;
Zhongxing Xu17892752008-10-08 02:50:44 +0000159
160public:
161 RegionStoreManager(GRStateManager& mgr)
Ted Kremenekc62abc12009-04-21 21:51:34 +0000162 : StoreManager(mgr),
Ted Kremenekd6cfbe42009-01-07 22:18:50 +0000163 RBFactory(mgr.getAllocator()),
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000164 RVFactory(mgr.getAllocator()),
Ted Kremenekc62abc12009-04-21 21:51:34 +0000165 SelfRegion(0), SelfDecl(0) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000166 if (const ObjCMethodDecl* MD =
167 dyn_cast<ObjCMethodDecl>(&StateMgr.getCodeDecl()))
168 SelfDecl = MD->getSelfDecl();
169 }
Zhongxing Xu17892752008-10-08 02:50:44 +0000170
171 virtual ~RegionStoreManager() {}
172
Ted Kremenek14453bf2009-03-03 19:02:42 +0000173 SubRegionMap* getSubRegionMap(const GRState *state);
Ted Kremenek59e8f112009-03-03 01:35:36 +0000174
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000175 const GRState* BindCompoundLiteral(const GRState* St,
176 const CompoundLiteralExpr* CL, SVal V);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000177
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000178 /// getLValueString - Returns an SVal representing the lvalue of a
179 /// StringLiteral. Within RegionStore a StringLiteral has an
180 /// associated StringRegion, and the lvalue of a StringLiteral is
181 /// the lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000182 SVal getLValueString(const GRState* St, const StringLiteral* S);
183
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000184 /// getLValueCompoundLiteral - Returns an SVal representing the
185 /// lvalue of a compound literal. Within RegionStore a compound
186 /// literal has an associated region, and the lvalue of the
187 /// compound literal is the lvalue of that region.
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000188 SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);
189
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000190 /// getLValueVar - Returns an SVal that represents the lvalue of a
191 /// variable. Within RegionStore a variable has an associated
192 /// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000193 SVal getLValueVar(const GRState* St, const VarDecl* VD);
194
195 SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);
196
197 SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000198
199 SVal getLValueFieldOrIvar(const GRState* St, SVal Base, const Decl* D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000200
Ted Kremenekf936f452009-05-04 06:18:28 +0000201 SVal getLValueElement(const GRState* St, QualType elementType,
202 SVal Base, SVal Offset);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000203
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000204 SVal getSizeInElements(const GRState* St, const MemRegion* R);
205
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000206 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
207 /// type. 'Array' represents the lvalue of the array being decayed
208 /// to a pointer, and the returned SVal represents the decayed
209 /// version of that lvalue (i.e., a pointer to the first element of
210 /// the array). This is called by GRExprEngine when evaluating
211 /// casts from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000212 SVal ArrayToPointer(Loc Array);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000213
Zhongxing Xu88980592009-05-06 02:42:32 +0000214 CastResult CastRegion(const GRState* state, const MemRegion* R,
215 QualType CastToTy);
216
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000217 SVal EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R);
218
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000219 /// The high level logic for this method is this:
220 /// Retrieve (L)
221 /// if L has binding
222 /// return L's binding
223 /// else if L is in killset
224 /// return unknown
225 /// else
226 /// if L is on stack or heap
227 /// return undefined
228 /// else
229 /// return symbolic
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000230 SVal Retrieve(const GRState* state, Loc L, QualType T = QualType());
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000231
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000232 const GRState* Bind(const GRState* St, Loc LV, SVal V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000233
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000234 Store Remove(Store store, Loc LV);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000235
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000236 Store getInitialStore() { return RBFactory.GetEmptyMap().getRoot(); }
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000237
238 /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
239 /// 'this' object (C++). When used when analyzing a normal function this
240 /// method returns NULL.
241 const MemRegion* getSelfRegion(Store) {
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000242 if (!SelfDecl)
243 return 0;
244
245 if (!SelfRegion) {
246 const ObjCMethodDecl *MD = cast<ObjCMethodDecl>(&StateMgr.getCodeDecl());
247 SelfRegion = MRMgr.getObjCObjectRegion(MD->getClassInterface(),
248 MRMgr.getHeapRegion());
249 }
250
251 return SelfRegion;
Ted Kremenek9deb0e32008-10-24 20:32:16 +0000252 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000253
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000254 /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
255 /// It returns a new Store with these values removed, and populates LSymbols
256 // and DSymbols with the known set of live and dead symbols respectively.
257 Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +0000258 SymbolReaper& SymReaper,
259 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000260
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000261 const GRState* BindDecl(const GRState* St, const VarDecl* VD, SVal InitVal);
262
263 const GRState* BindDeclWithNoInit(const GRState* St, const VarDecl* VD) {
264 return St;
265 }
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000266
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000267 const GRState* setExtent(const GRState* St, const MemRegion* R, SVal Extent);
Zhongxing Xu20794942009-05-06 08:33:50 +0000268 const GRState* setCastType(const GRState* St, const MemRegion* R, QualType T);
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000269
Zhongxing Xu17892752008-10-08 02:50:44 +0000270 static inline RegionBindingsTy GetRegionBindings(Store store) {
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000271 return RegionBindingsTy(static_cast<const RegionBindingsTy::TreeTy*>(store));
Zhongxing Xu17892752008-10-08 02:50:44 +0000272 }
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000273
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +0000274 void print(Store store, std::ostream& Out, const char* nl, const char *sep);
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000275
276 void iterBindings(Store store, BindingsHandler& f) {
277 // FIXME: Implement.
278 }
Zhongxing Xua82512a2008-10-24 08:42:28 +0000279
280private:
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000281 const GRState* BindArray(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000282
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000283 /// Retrieve the values in a struct and return a CompoundVal, used when doing
284 /// struct copy:
285 /// struct s x, y;
286 /// x = y;
287 /// y's value is retrieved by this method.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000288 SVal RetrieveStruct(const GRState* St, const TypedRegion* R);
Zhongxing Xu0b242ec2008-12-04 01:12:41 +0000289
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000290 SVal RetrieveArray(const GRState* St, const TypedRegion* R);
291
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000292 const GRState* BindStruct(const GRState* St, const TypedRegion* R, SVal V);
Zhongxing Xu63123d82008-11-23 04:30:35 +0000293
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000294 /// KillStruct - Set the entire struct to unknown.
295 const GRState* KillStruct(const GRState* St, const TypedRegion* R);
296
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000297 // Utility methods.
298 BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
299 ASTContext& getContext() { return StateMgr.getContext(); }
Zhongxing Xua15f7ac2009-05-08 01:33:18 +0000300
Zhongxing Xu63123d82008-11-23 04:30:35 +0000301 SymbolManager& getSymbolManager() { return StateMgr.getSymbolManager(); }
Zhongxing Xudc0a25d2008-11-16 04:07:26 +0000302
303 const GRState* AddRegionView(const GRState* St,
304 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +0000305 const GRState* RemoveRegionView(const GRState* St,
306 const MemRegion* View, const MemRegion* Base);
Zhongxing Xu17892752008-10-08 02:50:44 +0000307};
308
309} // end anonymous namespace
310
Ted Kremenek95c7b002008-10-24 01:04:59 +0000311StoreManager* clang::CreateRegionStoreManager(GRStateManager& StMgr) {
Zhongxing Xu24194ef2008-10-24 01:38:55 +0000312 return new RegionStoreManager(StMgr);
Ted Kremenek95c7b002008-10-24 01:04:59 +0000313}
314
Ted Kremenek14453bf2009-03-03 19:02:42 +0000315SubRegionMap* RegionStoreManager::getSubRegionMap(const GRState *state) {
Ted Kremenek59e8f112009-03-03 01:35:36 +0000316 RegionBindingsTy B = GetRegionBindings(state->getStore());
317 RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
318
319 for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
320 if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
321 M->add(R->getSuperRegion(), R);
322 }
323
Ted Kremenek14453bf2009-03-03 19:02:42 +0000324 return M;
Ted Kremenek59e8f112009-03-03 01:35:36 +0000325}
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000326
327/// getLValueString - Returns an SVal representing the lvalue of a
328/// StringLiteral. Within RegionStore a StringLiteral has an
329/// associated StringRegion, and the lvalue of a StringLiteral is the
330/// lvalue of that region.
Zhongxing Xu143bf822008-10-25 14:18:57 +0000331SVal RegionStoreManager::getLValueString(const GRState* St,
332 const StringLiteral* S) {
333 return loc::MemRegionVal(MRMgr.getStringRegion(S));
334}
335
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000336/// getLValueVar - Returns an SVal that represents the lvalue of a
337/// variable. Within RegionStore a variable has an associated
338/// VarRegion, and the lvalue of the variable is the lvalue of that region.
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000339SVal RegionStoreManager::getLValueVar(const GRState* St, const VarDecl* VD) {
340 return loc::MemRegionVal(MRMgr.getVarRegion(VD));
341}
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000342
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000343/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
344/// of a compound literal. Within RegionStore a compound literal
345/// has an associated region, and the lvalue of the compound literal
346/// is the lvalue of that region.
347SVal
348RegionStoreManager::getLValueCompoundLiteral(const GRState* St,
349 const CompoundLiteralExpr* CL) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000350 return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL));
351}
352
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000353SVal RegionStoreManager::getLValueIvar(const GRState* St, const ObjCIvarDecl* D,
354 SVal Base) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000355 return getLValueFieldOrIvar(St, Base, D);
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000356}
357
358SVal RegionStoreManager::getLValueField(const GRState* St, SVal Base,
359 const FieldDecl* D) {
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000360 return getLValueFieldOrIvar(St, Base, D);
361}
362
363SVal RegionStoreManager::getLValueFieldOrIvar(const GRState* St, SVal Base,
364 const Decl* D) {
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000365 if (Base.isUnknownOrUndef())
366 return Base;
367
368 Loc BaseL = cast<Loc>(Base);
369 const MemRegion* BaseR = 0;
370
371 switch (BaseL.getSubKind()) {
372 case loc::MemRegionKind:
373 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
Zhongxing Xua1718c72009-04-03 07:33:13 +0000374 if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(BaseR)) {
375 SymbolRef Sym = SR->getSymbol();
376 BaseR = MRMgr.getTypedViewRegion(Sym->getType(getContext()), SR);
377 }
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000378 break;
379
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000380 case loc::GotoLabelKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000381 // These are anormal cases. Flag an undefined value.
382 return UndefinedVal();
383
384 case loc::ConcreteIntKind:
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000385 // While these seem funny, this can happen through casts.
386 // FIXME: What we should return is the field offset. For example,
387 // add the field offset to the integer value. That way funny things
388 // like this work properly: &(((struct foo *) 0xa)->f)
389 return Base;
390
391 default:
Zhongxing Xu13d1ee22008-11-07 08:57:30 +0000392 assert(0 && "Unhandled Base.");
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000393 return Base;
394 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000395
396 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
397 // of FieldDecl.
398 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
399 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000400
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000401 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
Zhongxing Xuc4bf72c2008-10-22 13:44:38 +0000402}
403
Ted Kremenekf936f452009-05-04 06:18:28 +0000404SVal RegionStoreManager::getLValueElement(const GRState* St,
405 QualType elementType,
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000406 SVal Base, SVal Offset) {
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000407
Ted Kremenekde7ec632009-03-09 22:44:49 +0000408 // If the base is an unknown or undefined value, just return it back.
409 // FIXME: For absolute pointer addresses, we just return that value back as
410 // well, although in reality we should return the offset added to that
411 // value.
412 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
Zhongxing Xu4a1513e2008-10-27 12:23:17 +0000413 return Base;
414
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000415 // Only handle integer offsets... for now.
416 if (!isa<nonloc::ConcreteInt>(Offset))
Zhongxing Xue4d13932008-11-13 09:48:44 +0000417 return UnknownVal();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000418
Zhongxing Xuce760782009-05-09 13:20:07 +0000419 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000420
421 // Pointer of any type can be cast and used as array base.
422 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
423
424 if (!ElemR) {
425 //
426 // If the base region is not an ElementRegion, create one.
427 // This can happen in the following example:
428 //
429 // char *p = __builtin_alloc(10);
430 // p[1] = 8;
431 //
Zhongxing Xuce760782009-05-09 13:20:07 +0000432 // Observe that 'p' binds to an AllocaRegion.
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000433 //
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000434
435 // Offset might be unsigned. We have to convert it to signed ConcreteInt.
436 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&Offset)) {
437 const llvm::APSInt& OffI = CI->getValue();
438 if (OffI.isUnsigned()) {
439 llvm::APSInt Tmp = OffI;
440 Tmp.setIsSigned(true);
441 Offset = NonLoc::MakeVal(getBasicVals(), Tmp);
442 }
443 }
Ted Kremenekf936f452009-05-04 06:18:28 +0000444 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
445 BaseRegion));
Zhongxing Xue4d13932008-11-13 09:48:44 +0000446 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000447
448 SVal BaseIdx = ElemR->getIndex();
449
450 if (!isa<nonloc::ConcreteInt>(BaseIdx))
451 return UnknownVal();
452
453 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
454 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
455 assert(BaseIdxI.isSigned());
456
457 // FIXME: This appears to be the assumption of this code. We should review
458 // whether or not BaseIdxI.getBitWidth() < OffI.getBitWidth(). If it
459 // can't we need to put a comment here. If it can, we should handle it.
460 assert(BaseIdxI.getBitWidth() >= OffI.getBitWidth());
Zhongxing Xue4d13932008-11-13 09:48:44 +0000461
Zhongxing Xuce760782009-05-09 13:20:07 +0000462 const MemRegion *ArrayR = ElemR->getSuperRegion();
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000463 SVal NewIdx;
464
465 if (OffI.isUnsigned() || OffI.getBitWidth() < BaseIdxI.getBitWidth()) {
466 // 'Offset' might be unsigned. We have to convert it to signed and
467 // possibly extend it.
468 llvm::APSInt Tmp = OffI;
469
470 if (OffI.getBitWidth() < BaseIdxI.getBitWidth())
471 Tmp.extend(BaseIdxI.getBitWidth());
472
473 Tmp.setIsSigned(true);
474 Tmp += BaseIdxI; // Compute the new offset.
Zhongxing Xu5ea2ffc2009-02-19 08:37:16 +0000475 NewIdx = NonLoc::MakeVal(getBasicVals(), Tmp);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000476 }
Ted Kremeneka7ac9442009-01-22 20:27:48 +0000477 else
478 NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000479
Ted Kremenekf936f452009-05-04 06:18:28 +0000480 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR));
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000481}
482
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000483SVal RegionStoreManager::getSizeInElements(const GRState* St,
484 const MemRegion* R) {
485 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
486 // Get the type of the variable.
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000487 QualType T = VR->getDesugaredValueType(getContext());
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000488
Ted Kremenek14553ab2009-01-30 00:08:43 +0000489 // FIXME: Handle variable-length arrays.
490 if (isa<VariableArrayType>(T))
491 return UnknownVal();
492
493 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
494 // return the size as signed integer.
495 return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
496 }
Zhongxing Xu20794942009-05-06 08:33:50 +0000497
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000498 GRStateRef state(St, StateMgr);
499 const QualType* CastTy = state.get<RegionCasts>(VR);
500
Zhongxing Xue6536af2009-05-08 02:00:55 +0000501 // If the VarRegion is cast to other type, compute the size with respect to
502 // that type.
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000503 if (CastTy) {
504 QualType EleTy =cast<PointerType>(CastTy->getTypePtr())->getPointeeType();
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000505 QualType VarTy = VR->getValueType(getContext());
Zhongxing Xue6536af2009-05-08 02:00:55 +0000506 uint64_t EleSize = getContext().getTypeSize(EleTy);
507 uint64_t VarSize = getContext().getTypeSize(VarTy);
508 return NonLoc::MakeIntVal(getBasicVals(), VarSize / EleSize, false);
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000509 }
510
Ted Kremenek14553ab2009-01-30 00:08:43 +0000511 // Clients can use ordinary variables as if they were arrays. These
512 // essentially are arrays of size 1.
513 return NonLoc::MakeIntVal(getBasicVals(), 1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000514 }
515
516 if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
Zhongxing Xu6613d082008-11-24 02:18:56 +0000517 const StringLiteral* Str = SR->getStringLiteral();
Zhongxing Xud0fd3b72008-11-24 02:30:48 +0000518 // We intentionally made the size value signed because it participates in
519 // operations with signed indices.
Ted Kremenek14553ab2009-01-30 00:08:43 +0000520 return NonLoc::MakeIntVal(getBasicVals(), Str->getByteLength()+1, false);
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000521 }
522
Ted Kremenek0312c0e2009-03-01 05:44:08 +0000523 if (const TypedViewRegion* ATR = dyn_cast<TypedViewRegion>(R)) {
Ted Kremenek2e842572009-01-22 23:56:56 +0000524#if 0
525 // FIXME: This logic doesn't really work, as we can have all sorts of
526 // weird cases. For example, this crashes on test case 'rdar-6442306-1.m'.
527 // The weird cases come in when arbitrary casting comes into play, violating
528 // any type-safe programming.
529
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000530 GRStateRef state(St, StateMgr);
531
532 // Get the size of the super region in bytes.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000533 const SVal* Extent = state.get<RegionExtents>(ATR->getSuperRegion());
534 assert(Extent && "region extent not exist");
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000535
536 // Assume it's ConcreteInt for now.
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000537 llvm::APSInt SSize = cast<nonloc::ConcreteInt>(*Extent).getValue();
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000538
539 // Get the size of the element in bits.
Zhongxing Xuff697822009-05-09 00:50:33 +0000540 QualType LvT = ATR->getLocationType(getContext());
Ted Kremenek6eddeb12008-12-13 21:49:13 +0000541 QualType ElemTy = cast<PointerType>(LvT.getTypePtr())->getPointeeType();
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000542
543 uint64_t X = getContext().getTypeSize(ElemTy);
544
545 const llvm::APSInt& ESize = getBasicVals().getValue(X, SSize.getBitWidth(),
546 false);
547
548 // Calculate the number of elements.
549
550 // FIXME: What do we do with signed-ness problem? Shall we make all APSInts
551 // signed?
552 if (SSize.isUnsigned())
553 SSize.setIsSigned(true);
554
555 // FIXME: move this operation into BasicVals.
556 const llvm::APSInt S =
557 (SSize * getBasicVals().getValue(8, SSize.getBitWidth(), false)) / ESize;
558
559 return NonLoc::MakeVal(getBasicVals(), S);
Ted Kremenek2e842572009-01-22 23:56:56 +0000560#else
561 ATR = ATR;
562 return UnknownVal();
563#endif
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000564 }
565
566 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
567 // FIXME: Unsupported yet.
568 FR = 0;
569 return UnknownVal();
570 }
Zhongxing Xu369f4292008-11-22 13:23:00 +0000571
Zhongxing Xu02ebefb2009-02-06 08:51:30 +0000572 if (isa<SymbolicRegion>(R)) {
Zhongxing Xua48f7372009-02-06 08:44:27 +0000573 return UnknownVal();
574 }
575
Zhongxing Xuce760782009-05-09 13:20:07 +0000576 if (isa<AllocaRegion>(R)) {
577 return UnknownVal();
578 }
579
Zhongxing Xuccb16162009-05-06 08:08:27 +0000580 if (isa<ElementRegion>(R)) {
581 return UnknownVal();
582 }
583
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000584 assert(0 && "Other regions are not supported yet.");
Ted Kremeneka21362d2009-01-06 19:12:06 +0000585 return UnknownVal();
Zhongxing Xue8a964b2008-11-22 13:21:46 +0000586}
587
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000588/// ArrayToPointer - Emulates the "decay" of an array to a pointer
589/// type. 'Array' represents the lvalue of the array being decayed
590/// to a pointer, and the returned SVal represents the decayed
591/// version of that lvalue (i.e., a pointer to the first element of
592/// the array). This is called by GRExprEngine when evaluating casts
593/// from arrays to pointers.
Zhongxing Xuf1d537f2009-03-30 05:55:46 +0000594SVal RegionStoreManager::ArrayToPointer(Loc Array) {
Ted Kremenekabb042f2008-12-13 19:24:37 +0000595 if (!isa<loc::MemRegionVal>(Array))
596 return UnknownVal();
597
598 const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
599 const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
600
Ted Kremenekbbee1a72009-01-13 01:03:27 +0000601 if (!ArrayR)
Ted Kremenekabb042f2008-12-13 19:24:37 +0000602 return UnknownVal();
603
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000604 // Strip off typedefs from the ArrayRegion's ValueType.
605 QualType T = ArrayR->getValueType(getContext())->getDesugaredType();
Ted Kremenekf936f452009-05-04 06:18:28 +0000606 ArrayType *AT = cast<ArrayType>(T);
607 T = AT->getElementType();
608
Zhongxing Xu63123d82008-11-23 04:30:35 +0000609 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Ted Kremenekf936f452009-05-04 06:18:28 +0000610 ElementRegion* ER = MRMgr.getElementRegion(T, Idx, ArrayR);
Zhongxing Xu0b7e6422008-10-26 02:23:57 +0000611
612 return loc::MemRegionVal(ER);
Zhongxing Xub1d542a2008-10-24 01:09:32 +0000613}
614
Zhongxing Xu88980592009-05-06 02:42:32 +0000615RegionStoreManager::CastResult
616RegionStoreManager::CastRegion(const GRState* state, const MemRegion* R,
Zhongxing Xu41fd0182009-05-06 11:51:48 +0000617 QualType CastToTy) {
Zhongxing Xu88980592009-05-06 02:42:32 +0000618
619 ASTContext& Ctx = StateMgr.getContext();
620
621 // We need to know the real type of CastToTy.
622 QualType ToTy = Ctx.getCanonicalType(CastToTy);
623
624 // Check cast to ObjCQualifiedID type.
625 if (isa<ObjCQualifiedIdType>(ToTy)) {
626 // FIXME: Record the type information aside.
627 return CastResult(state, R);
628 }
629
630 // CodeTextRegion should be cast to only function pointer type.
631 if (isa<CodeTextRegion>(R)) {
632 assert(CastToTy->isFunctionPointerType() || CastToTy->isBlockPointerType());
633 return CastResult(state, R);
634 }
635
Zhongxing Xudb3a0982009-05-09 10:03:08 +0000636 // Now assume we are casting from pointer to pointer. Other cases should
637 // already be handled.
Zhongxing Xu88980592009-05-06 02:42:32 +0000638 QualType PointeeTy = cast<PointerType>(ToTy.getTypePtr())->getPointeeType();
639
Zhongxing Xu88980592009-05-06 02:42:32 +0000640 // Process region cast according to the kind of the region being cast.
641
642
643 // FIXME: Need to handle arbitrary downcasts.
644 // FIXME: Handle the case where a TypedViewRegion (layering a SymbolicRegion
645 // or an AllocaRegion is cast to another view, thus causing the memory
646 // to be re-used for a different purpose.
647
648 if (isa<SymbolicRegion>(R) || isa<AllocaRegion>(R)) {
Zhongxing Xuce760782009-05-09 13:20:07 +0000649 state = setCastType(state, R, ToTy);
650 return CastResult(state, R);
Zhongxing Xu88980592009-05-06 02:42:32 +0000651 }
652
653 // VarRegion, ElementRegion, and FieldRegion has an inherent type. Normally
654 // they should not be cast. We only layer an ElementRegion when the cast-to
655 // pointee type is of smaller size. In other cases, we return the original
656 // VarRegion.
657 if (isa<VarRegion>(R) || isa<ElementRegion>(R) || isa<FieldRegion>(R)
658 || isa<ObjCIvarRegion>(R) || isa<CompoundLiteralRegion>(R)) {
Zhongxing Xu2572eda2009-05-08 07:28:25 +0000659 // If the pointee type is incomplete, do not compute its size, and return
660 // the original region.
661 if (const RecordType *RT = dyn_cast<RecordType>(PointeeTy.getTypePtr())) {
662 const RecordDecl *D = RT->getDecl();
663 if (!D->getDefinition(getContext()))
664 return CastResult(state, R);
665 }
666
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000667 QualType ObjTy = cast<TypedRegion>(R)->getValueType(getContext());
Zhongxing Xufb1e3312009-05-08 02:12:59 +0000668 uint64_t PointeeTySize = getContext().getTypeSize(PointeeTy);
669 uint64_t ObjTySize = getContext().getTypeSize(ObjTy);
670
671 if (PointeeTySize > 0 && PointeeTySize < ObjTySize) {
Zhongxing Xu20794942009-05-06 08:33:50 +0000672 // Record the cast type of the region.
673 state = setCastType(state, R, ToTy);
674
Zhongxing Xuccb16162009-05-06 08:08:27 +0000675 SVal Idx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu20794942009-05-06 08:33:50 +0000676 ElementRegion* ER = MRMgr.getElementRegion(PointeeTy, Idx, R);
Zhongxing Xuccb16162009-05-06 08:08:27 +0000677 return CastResult(state, ER);
678 } else
679 return CastResult(state, R);
Zhongxing Xu88980592009-05-06 02:42:32 +0000680 }
681
682 if (isa<TypedViewRegion>(R)) {
683 const MemRegion* ViewR = MRMgr.getTypedViewRegion(CastToTy, R);
684 return CastResult(state, ViewR);
685 }
686
687 if (isa<ObjCObjectRegion>(R)) {
688 return CastResult(state, R);
689 }
690
691 assert(0 && "Unprocessed region.");
692}
693
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000694SVal RegionStoreManager::EvalBinOp(BinaryOperator::Opcode Op, Loc L, NonLoc R) {
695 // Assume the base location is MemRegionVal(ElementRegion).
Ted Kremenek5dc27462009-03-03 02:51:43 +0000696 if (!isa<loc::MemRegionVal>(L))
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000697 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000698
Zhongxing Xua1718c72009-04-03 07:33:13 +0000699 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
700 if (isa<SymbolicRegion>(MR))
701 return UnknownVal();
702
703 const TypedRegion* TR = cast<TypedRegion>(MR);
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000704 const ElementRegion* ER = dyn_cast<ElementRegion>(TR);
705
706 if (!ER) {
707 // If the region is not element region, create one with index 0. This can
708 // happen in the following example:
709 // char *p = foo();
710 // p += 3;
711 // Note that p binds to a TypedViewRegion(SymbolicRegion).
712 nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000713 ER = MRMgr.getElementRegion(TR->getValueType(getContext()), Idx, TR);
Zhongxing Xu2b1dc172009-03-11 07:43:49 +0000714 }
715
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000716 SVal Idx = ER->getIndex();
717
718 nonloc::ConcreteInt* Base = dyn_cast<nonloc::ConcreteInt>(&Idx);
719 nonloc::ConcreteInt* Offset = dyn_cast<nonloc::ConcreteInt>(&R);
720
721 // Only support concrete integer indexes for now.
722 if (Base && Offset) {
Ted Kremenek610e81d2009-03-13 15:35:24 +0000723 // FIXME: For now, convert the signedness and bitwidth of offset in case
724 // they don't match. This can result from pointer arithmetic. In reality,
725 // we should figure out what are the proper semantics and implement them.
726 //
Ted Kremenek1060a3c2009-03-13 15:39:16 +0000727 // This addresses the test case test/Analysis/ptr-arith.c
728 //
Ted Kremenek610e81d2009-03-13 15:35:24 +0000729 nonloc::ConcreteInt OffConverted(getBasicVals().Convert(Base->getValue(),
730 Offset->getValue()));
731 SVal NewIdx = Base->EvalBinOp(getBasicVals(), Op, OffConverted);
Ted Kremenekf936f452009-05-04 06:18:28 +0000732 const MemRegion* NewER =
733 MRMgr.getElementRegion(ER->getElementType(), NewIdx,
734 cast<TypedRegion>(ER->getSuperRegion()));
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000735 return Loc::MakeVal(NewER);
736
Ted Kremenek5dc27462009-03-03 02:51:43 +0000737 }
738
739 return UnknownVal();
Zhongxing Xu94aa6c12009-03-02 07:52:23 +0000740}
741
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000742SVal RegionStoreManager::Retrieve(const GRState* St, Loc L, QualType T) {
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000743 assert(!isa<UnknownVal>(L) && "location unknown");
744 assert(!isa<UndefinedVal>(L) && "location undefined");
745
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000746 // FIXME: Is this even possible? Shouldn't this be treated as a null
747 // dereference at a higher level?
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000748 if (isa<loc::ConcreteInt>(L))
749 return UndefinedVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000750
Zhongxing Xua1718c72009-04-03 07:33:13 +0000751 const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
752
753 // We return unknown for symbolic region for now. This might be improved.
754 // Example:
755 // void f(int* p) { int x = *p; }
756 if (isa<SymbolicRegion>(MR))
757 return UnknownVal();
758
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000759 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
760 // instead of 'Loc', and have the other Loc cases handled at a higher level.
Zhongxing Xua1718c72009-04-03 07:33:13 +0000761 const TypedRegion* R = cast<TypedRegion>(MR);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000762 assert(R && "bad region");
763
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000764 // FIXME: We should eventually handle funny addressing. e.g.:
765 //
766 // int x = ...;
767 // int *p = &x;
768 // char *q = (char*) p;
769 // char c = *q; // returns the first byte of 'x'.
770 //
771 // Such funny addressing will occur due to layering of regions.
772
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000773 QualType RTy = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000774
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000775 if (RTy->isStructureType())
776 return RetrieveStruct(St, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000777
778 if (RTy->isArrayType())
779 return RetrieveArray(St, R);
780
Zhongxing Xu1038f9f2009-03-09 09:15:51 +0000781 // FIXME: handle Vector types.
782 if (RTy->isVectorType())
Ted Kremenek265a3052009-02-24 02:23:11 +0000783 return UnknownVal();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000784
785 RegionBindingsTy B = GetRegionBindings(St->getStore());
786 RegionBindingsTy::data_type* V = B.lookup(R);
787
788 // Check if the region has a binding.
789 if (V)
790 return *V;
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000791
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000792 GRStateRef state(St, StateMgr);
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000793
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000794 // Check if the region is in killset.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000795 if (state.contains<RegionKills>(R))
796 return UnknownVal();
797
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000798 // If the region is an element or field, it may have a default value.
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000799 if (isa<ElementRegion>(R) || isa<FieldRegion>(R)) {
800 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
801 GRStateTrait<RegionDefaultValue>::lookup_type D =
802 state.get<RegionDefaultValue>(SuperR);
803 if (D)
804 return *D;
805 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000806
807 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
808 const MemRegion *SR = IVR->getSuperRegion();
809
810 // If the super region is 'self' then return the symbol representing
811 // the value of the ivar upon entry to the method.
812 if (SR == SelfRegion) {
813 // FIXME: Do we need to handle the case where the super region
814 // has a view? We want to canonicalize the bindings.
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000815 return ValMgr.getRegionValueSymbolVal(R);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000816 }
817
818 // Otherwise, we need a new symbol. For now return Unknown.
819 return UnknownVal();
820 }
Zhongxing Xu562c4d92009-01-23 11:22:12 +0000821
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000822 // The location does not have a bound value. This means that it has
823 // the value it had upon its creation and/or entry to the analyzed
824 // function/method. These are either symbolic values or 'undefined'.
825
826 // We treat function parameters as symbolic values.
Ted Kremenek6fd8f912009-01-22 23:43:57 +0000827 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
828 const VarDecl *VD = VR->getDecl();
829
Ted Kremenekcec35252009-03-04 00:23:05 +0000830 if (VD == SelfDecl)
831 return loc::MemRegionVal(getSelfRegion(0));
832
833 if (isa<ParmVarDecl>(VD) || isa<ImplicitParamDecl>(VD) ||
834 VD->hasGlobalStorage()) {
Zhongxing Xud8895f62009-02-19 09:56:08 +0000835 QualType VTy = VD->getType();
836 if (Loc::IsLocType(VTy) || VTy->isIntegerType())
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000837 return ValMgr.getRegionValueSymbolVal(VR);
Zhongxing Xud8895f62009-02-19 09:56:08 +0000838 else
839 return UnknownVal();
840 }
Ted Kremenek3de2d3c2009-03-05 04:50:08 +0000841 }
Ted Kremenek265a3052009-02-24 02:23:11 +0000842
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000843 if (MRMgr.onStack(R) || MRMgr.onHeap(R)) {
844 // All stack variables are considered to have undefined values
845 // upon creation. All heap allocated blocks are considered to
846 // have undefined values as well unless they are explicitly bound
847 // to specific values.
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000848 return UndefinedVal();
Ted Kremenek869fb4a2008-12-24 07:46:32 +0000849 }
850
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000851 // All other integer values are symbolic.
852 if (Loc::IsLocType(RTy) || RTy->isIntegerType())
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000853 return ValMgr.getRegionValueSymbolVal(R);
Zhongxing Xuff8d2042009-03-09 09:31:22 +0000854 else
855 return UnknownVal();
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000856}
857
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000858SVal RegionStoreManager::RetrieveStruct(const GRState* St,const TypedRegion* R){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000859 QualType T = R->getValueType(getContext());
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000860 assert(T->isStructureType());
861
862 const RecordType* RT = cast<RecordType>(T.getTypePtr());
863 RecordDecl* RD = RT->getDecl();
864 assert(RD->isDefinition());
865
866 llvm::ImmutableList<SVal> StructVal = getBasicVals().getEmptySValList();
867
Douglas Gregor6ab35242009-04-09 21:40:53 +0000868 std::vector<FieldDecl *> Fields(RD->field_begin(getContext()),
869 RD->field_end(getContext()));
Douglas Gregor44b43212008-12-11 16:49:14 +0000870
Douglas Gregore267ff32008-12-11 20:41:00 +0000871 for (std::vector<FieldDecl *>::reverse_iterator Field = Fields.rbegin(),
872 FieldEnd = Fields.rend();
873 Field != FieldEnd; ++Field) {
874 FieldRegion* FR = MRMgr.getFieldRegion(*Field, R);
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000875 QualType FTy = (*Field)->getType();
876 SVal FieldValue = Retrieve(St, loc::MemRegionVal(FR), FTy);
Zhongxing Xu6e3f01c2008-10-31 07:16:08 +0000877 StructVal = getBasicVals().consVals(FieldValue, StructVal);
878 }
879
880 return NonLoc::MakeCompoundVal(T, StructVal, getBasicVals());
881}
882
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000883SVal RegionStoreManager::RetrieveArray(const GRState* St, const TypedRegion* R){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000884 QualType T = R->getValueType(getContext());
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000885 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
886
887 llvm::ImmutableList<SVal> ArrayVal = getBasicVals().getEmptySValList();
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000888 llvm::APSInt Size(CAT->getSize(), false);
889 llvm::APSInt i = getBasicVals().getValue(0, Size.getBitWidth(),
890 Size.isUnsigned());
891
892 for (; i < Size; ++i) {
893 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000894 ElementRegion* ER = MRMgr.getElementRegion(R->getValueType(getContext()),
Ted Kremenekf936f452009-05-04 06:18:28 +0000895 Idx, R);
896 QualType ETy = ER->getElementType();
Zhongxing Xu3e001f32009-05-03 00:27:40 +0000897 SVal ElementVal = Retrieve(St, loc::MemRegionVal(ER), ETy);
898 ArrayVal = getBasicVals().consVals(ElementVal, ArrayVal);
899 }
900
901 return NonLoc::MakeCompoundVal(T, ArrayVal, getBasicVals());
902}
903
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000904const GRState* RegionStoreManager::Bind(const GRState* St, Loc L, SVal V) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000905 // If we get here, the location should be a region.
906 const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000907 assert(R);
908
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000909 // Check if the region is a struct region.
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000910 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000911 if (TR->getValueType(getContext())->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000912 return BindStruct(St, TR, V);
Zhongxing Xu17892752008-10-08 02:50:44 +0000913
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000914 Store store = St->getStore();
Zhongxing Xu17892752008-10-08 02:50:44 +0000915 RegionBindingsTy B = GetRegionBindings(store);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000916
917 if (V.isUnknown()) {
918 // Remove the binding.
919 store = RBFactory.Remove(B, R).getRoot();
920
921 // Add the region to the killset.
922 GRStateRef state(St, StateMgr);
923 St = state.add<RegionKills>(R);
924 }
925 else
926 store = RBFactory.Add(B, R, V).getRoot();
927
928 return StateMgr.MakeStateWithStore(St, store);
Zhongxing Xu17892752008-10-08 02:50:44 +0000929}
930
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000931Store RegionStoreManager::Remove(Store store, Loc L) {
Ted Kremenek0964a062009-01-21 06:57:53 +0000932 const MemRegion* R = 0;
933
934 if (isa<loc::MemRegionVal>(L))
935 R = cast<loc::MemRegionVal>(L).getRegion();
Ted Kremenek0964a062009-01-21 06:57:53 +0000936
937 if (R) {
938 RegionBindingsTy B = GetRegionBindings(store);
939 return RBFactory.Remove(B, R).getRoot();
940 }
941
942 return store;
Zhongxing Xu9c9ca082008-12-16 02:36:30 +0000943}
944
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000945const GRState* RegionStoreManager::BindDecl(const GRState* St,
946 const VarDecl* VD, SVal InitVal) {
Zhongxing Xua4f28ff2008-11-13 08:41:36 +0000947
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000948 QualType T = VD->getType();
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000949 VarRegion* VR = MRMgr.getVarRegion(VD);
Zhongxing Xuf0dfa8d2008-10-31 08:10:01 +0000950
Ted Kremenek0964a062009-01-21 06:57:53 +0000951 if (T->isArrayType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000952 return BindArray(St, VR, InitVal);
Ted Kremenek0964a062009-01-21 06:57:53 +0000953 if (T->isStructureType())
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000954 return BindStruct(St, VR, InitVal);
Zhongxing Xud463d442008-11-02 12:13:30 +0000955
Ted Kremenek0964a062009-01-21 06:57:53 +0000956 return Bind(St, Loc::MakeVal(VR), InitVal);
Zhongxing Xu17892752008-10-08 02:50:44 +0000957}
Zhongxing Xu53bcdd42008-10-21 05:29:26 +0000958
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000959// FIXME: this method should be merged into Bind().
960const GRState*
961RegionStoreManager::BindCompoundLiteral(const GRState* St,
962 const CompoundLiteralExpr* CL, SVal V) {
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000963 CompoundLiteralRegion* R = MRMgr.getCompoundLiteralRegion(CL);
Zhongxing Xu4193eca2008-12-20 06:32:12 +0000964 return Bind(St, loc::MemRegionVal(R), V);
Zhongxing Xuf22679e2008-11-07 10:38:33 +0000965}
966
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000967const GRState* RegionStoreManager::setExtent(const GRState* St,
968 const MemRegion* R, SVal Extent) {
969 GRStateRef state(St, StateMgr);
Ted Kremenek50dc1b32008-12-24 01:05:03 +0000970 return state.set<RegionExtents>(R, Extent);
Zhongxing Xubaf03a72008-11-24 09:44:56 +0000971}
972
973
Ted Kremenek241677a2009-01-21 22:26:05 +0000974static void UpdateLiveSymbols(SVal X, SymbolReaper& SymReaper) {
Ted Kremenek02c4d2d2009-03-04 00:11:38 +0000975 if (loc::MemRegionVal *XR = dyn_cast<loc::MemRegionVal>(&X)) {
976 const MemRegion *R = XR->getRegion();
977
978 while (R) {
979 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
980 SymReaper.markLive(SR->getSymbol());
981 return;
982 }
983
984 if (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
985 R = SR->getSuperRegion();
986 continue;
987 }
988
989 break;
990 }
991
992 return;
993 }
994
Ted Kremenek241677a2009-01-21 22:26:05 +0000995 for (SVal::symbol_iterator SI=X.symbol_begin(), SE=X.symbol_end();SI!=SE;++SI)
996 SymReaper.markLive(*SI);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +0000997}
998
Ted Kremenek2ed14be2008-12-05 00:47:52 +0000999Store RegionStoreManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
Ted Kremenek241677a2009-01-21 22:26:05 +00001000 SymbolReaper& SymReaper,
1001 llvm::SmallVectorImpl<const MemRegion*>& RegionRoots)
1002{
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001003
Ted Kremenek2ed14be2008-12-05 00:47:52 +00001004 Store store = state->getStore();
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001005 RegionBindingsTy B = GetRegionBindings(store);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001006
1007 // Lazily constructed backmap from MemRegions to SubRegions.
1008 typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
1009 typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
1010
1011 // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
1012 // the ability to reuse memory. This way we can keep TmpAlloc around as
1013 // an instance variable of RegionStoreManager (avoiding repeated malloc
1014 // overhead).
1015 llvm::BumpPtrAllocator TmpAlloc;
1016
1017 // Factory objects.
1018 SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
1019 SubRegionsTy::Factory SubRegF(TmpAlloc);
1020
1021 // The backmap from regions to subregions.
1022 SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
1023
1024 // Do a pass over the regions in the store. For VarRegions we check if
1025 // the variable is still live and if so add it to the list of live roots.
1026 // For other regions we populate our region backmap.
Zhongxing Xuc2fdb072009-03-18 01:54:31 +00001027
1028 llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
1029
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001030 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
Zhongxing Xuc2fdb072009-03-18 01:54:31 +00001031 IntermediateRoots.push_back(I.getKey());
1032 }
1033
1034 while (!IntermediateRoots.empty()) {
1035 const MemRegion* R = IntermediateRoots.back();
1036 IntermediateRoots.pop_back();
1037
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001038 if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
Ted Kremenek241677a2009-01-21 22:26:05 +00001039 if (SymReaper.isLive(Loc, VR->getDecl()))
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001040 RegionRoots.push_back(VR); // This is a live "root".
Zhongxing Xu5c86b192009-04-29 09:24:35 +00001041 }
1042 else if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
1043 if (SymReaper.isLive(SR->getSymbol()))
1044 RegionRoots.push_back(SR);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001045 }
1046 else {
1047 // Get the super region for R.
1048 const MemRegion* SuperR = cast<SubRegion>(R)->getSuperRegion();
Zhongxing Xuc2fdb072009-03-18 01:54:31 +00001049
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001050 // Get the current set of subregions for SuperR.
1051 const SubRegionsTy* SRptr = SubRegMap.lookup(SuperR);
Zhongxing Xua3eda832009-05-08 23:28:07 +00001052 SubRegionsTy SRs = SRptr ? *SRptr : SubRegF.GetEmptySet();
Zhongxing Xuc2fdb072009-03-18 01:54:31 +00001053
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001054 // Add R to the subregions of SuperR.
Zhongxing Xua3eda832009-05-08 23:28:07 +00001055 SubRegMap = SubRegMapF.Add(SubRegMap, SuperR, SubRegF.Add(SRs, R));
Zhongxing Xuc2fdb072009-03-18 01:54:31 +00001056
1057 // Super region may be VarRegion or subregion of another VarRegion. Add it
1058 // to the work list.
1059 if (isa<SubRegion>(SuperR))
1060 IntermediateRoots.push_back(SuperR);
Ted Kremenek3de2d3c2009-03-05 04:50:08 +00001061 }
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001062 }
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001063
1064 // Process the worklist of RegionRoots. This performs a "mark-and-sweep"
1065 // of the store. We want to find all live symbols and dead regions.
1066 llvm::SmallPtrSet<const MemRegion*, 10> Marked;
1067
1068 while (!RegionRoots.empty()) {
1069 // Dequeue the next region on the worklist.
1070 const MemRegion* R = RegionRoots.back();
1071 RegionRoots.pop_back();
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001072
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001073 // Check if we have already processed this region.
1074 if (Marked.count(R)) continue;
1075
1076 // Mark this region as processed. This is needed for termination in case
1077 // a region is referenced more than once.
1078 Marked.insert(R);
1079
1080 // Mark the symbol for any live SymbolicRegion as "live". This means we
1081 // should continue to track that symbol.
1082 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
Ted Kremenek241677a2009-01-21 22:26:05 +00001083 SymReaper.markLive(SymR->getSymbol());
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001084
1085 // Get the data binding for R (if any).
1086 RegionBindingsTy::data_type* Xptr = B.lookup(R);
1087 if (Xptr) {
1088 SVal X = *Xptr;
Ted Kremenek241677a2009-01-21 22:26:05 +00001089 UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001090
1091 // If X is a region, then add it the RegionRoots.
1092 if (loc::MemRegionVal* RegionX = dyn_cast<loc::MemRegionVal>(&X))
1093 RegionRoots.push_back(RegionX->getRegion());
1094 }
1095
1096 // Get the subregions of R. These are RegionRoots as well since they
1097 // represent values that are also bound to R.
1098 const SubRegionsTy* SRptr = SubRegMap.lookup(R);
1099 if (!SRptr) continue;
1100 SubRegionsTy SR = *SRptr;
1101
1102 for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
1103 RegionRoots.push_back(*I);
1104 }
1105
1106 // We have now scanned the store, marking reachable regions and symbols
1107 // as live. We now remove all the regions that are dead from the store
Ted Kremenek3de2d3c2009-03-05 04:50:08 +00001108 // as well as update DSymbols with the set symbols that are now dead.
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001109 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1110 const MemRegion* R = I.getKey();
1111
1112 // If this region live? Is so, none of its symbols are dead.
1113 if (Marked.count(R))
1114 continue;
1115
1116 // Remove this dead region from the store.
Zhongxing Xu9c9ca082008-12-16 02:36:30 +00001117 store = Remove(store, Loc::MakeVal(R));
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001118
1119 // Mark all non-live symbols that this region references as dead.
Ted Kremenek241677a2009-01-21 22:26:05 +00001120 if (const SymbolicRegion* SymR = dyn_cast<SymbolicRegion>(R))
1121 SymReaper.maybeDead(SymR->getSymbol());
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001122
1123 SVal X = I.getData();
1124 SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
Ted Kremenek241677a2009-01-21 22:26:05 +00001125 for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
Ted Kremenekc48ea6e2008-12-04 02:08:27 +00001126 }
1127
Zhongxing Xu8916d5b2008-11-10 09:39:04 +00001128 return store;
1129}
1130
Zhongxing Xua071eb02008-10-24 06:01:33 +00001131void RegionStoreManager::print(Store store, std::ostream& Out,
1132 const char* nl, const char *sep) {
1133 llvm::raw_os_ostream OS(Out);
1134 RegionBindingsTy B = GetRegionBindings(store);
1135 OS << "Store:" << nl;
1136
1137 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1138 OS << ' '; I.getKey()->print(OS); OS << " : ";
1139 I.getData().print(OS); OS << nl;
1140 }
Zhongxing Xu5b8b6f22008-10-24 04:33:15 +00001141}
Zhongxing Xua82512a2008-10-24 08:42:28 +00001142
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001143const GRState* RegionStoreManager::BindArray(const GRState* St,
1144 const TypedRegion* R, SVal Init) {
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001145 QualType T = R->getValueType(getContext());
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001146 assert(T->isArrayType());
1147
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001148 // When we are binding the whole array, it always has default value 0.
1149 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001150 St = state.set<RegionDefaultValue>(R, NonLoc::MakeIntVal(getBasicVals(), 0,
1151 false));
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001152
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001153 ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
1154
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001155 llvm::APSInt Size(CAT->getSize(), false);
Sebastian Redl1be3da52009-01-26 19:54:12 +00001156 llvm::APSInt i = getBasicVals().getValue(0, Size.getBitWidth(),
1157 Size.isUnsigned());
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001158
1159 // Check if the init expr is a StringLiteral.
1160 if (isa<loc::MemRegionVal>(Init)) {
1161 const MemRegion* InitR = cast<loc::MemRegionVal>(Init).getRegion();
1162 const StringLiteral* S = cast<StringRegion>(InitR)->getStringLiteral();
1163 const char* str = S->getStrData();
1164 unsigned len = S->getByteLength();
1165 unsigned j = 0;
1166
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001167 // Copy bytes from the string literal into the target array. Trailing bytes
1168 // in the array that are not covered by the string literal are initialized
1169 // to zero.
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001170 for (; i < Size; ++i, ++j) {
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001171 if (j >= len)
1172 break;
1173
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001174 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Ted Kremenekf936f452009-05-04 06:18:28 +00001175 ElementRegion* ER =
1176 MRMgr.getElementRegion(cast<ArrayType>(T)->getElementType(),
1177 Idx, R);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001178
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001179 SVal V = NonLoc::MakeVal(getBasicVals(), str[j], sizeof(char)*8, true);
1180 St = Bind(St, loc::MemRegionVal(ER), V);
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001181 }
1182
Zhongxing Xubd4f7452009-03-09 06:49:50 +00001183 return St;
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001184 }
1185
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001186 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(Init);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001187 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
1188
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001189 for (; i < Size; ++i, ++VI) {
1190 // The init list might be shorter than the array decl.
1191 if (VI == VE)
1192 break;
1193
Zhongxing Xu6987c7b2008-11-30 05:49:49 +00001194 SVal Idx = NonLoc::MakeVal(getBasicVals(), i);
Ted Kremenekf936f452009-05-04 06:18:28 +00001195 ElementRegion* ER =
1196 MRMgr.getElementRegion(cast<ArrayType>(T)->getElementType(),
1197 Idx, R);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001198
1199 if (CAT->getElementType()->isStructureType())
1200 St = BindStruct(St, ER, *VI);
1201 else
1202 St = Bind(St, Loc::MakeVal(ER), *VI);
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001203 }
1204
Zhongxing Xubd4f7452009-03-09 06:49:50 +00001205 return St;
Zhongxing Xu1a12a0e2008-10-31 10:24:47 +00001206}
1207
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001208const GRState*
1209RegionStoreManager::BindStruct(const GRState* St, const TypedRegion* R, SVal V){
Zhongxing Xua82d8aa2009-05-09 03:57:34 +00001210 QualType T = R->getValueType(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001211 assert(T->isStructureType());
1212
Zhongxing Xub13ecdb2009-03-12 03:45:35 +00001213 const RecordType* RT = T->getAsRecordType();
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001214 RecordDecl* RD = RT->getDecl();
Zhongxing Xuc45a8252009-03-11 09:07:35 +00001215
1216 if (!RD->isDefinition())
1217 return St;
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001218
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001219 if (V.isUnknown())
1220 return KillStruct(St, R);
1221
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001222 nonloc::CompoundVal& CV = cast<nonloc::CompoundVal>(V);
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001223 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
Douglas Gregor6ab35242009-04-09 21:40:53 +00001224 RecordDecl::field_iterator FI = RD->field_begin(getContext()),
1225 FE = RD->field_end(getContext());
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001226
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001227 for (; FI != FE; ++FI, ++VI) {
1228
1229 // There may be fewer values than fields only when we are initializing a
1230 // struct decl. In this case, mark the region as having default value.
1231 if (VI == VE) {
Zhongxing Xu13020162008-12-24 07:29:24 +00001232 GRStateRef state(St, StateMgr);
Ted Kremenek14553ab2009-01-30 00:08:43 +00001233 const NonLoc& Idx = NonLoc::MakeIntVal(getBasicVals(), 0, false);
1234 St = state.set<RegionDefaultValue>(R, Idx);
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001235 break;
1236 }
1237
Zhongxing Xuaf0a8442008-10-31 10:53:01 +00001238 QualType FTy = (*FI)->getType();
1239 FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
1240
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001241 if (Loc::IsLocType(FTy) || FTy->isIntegerType())
1242 St = Bind(St, Loc::MakeVal(FR), *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001243
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001244 else if (FTy->isArrayType())
1245 St = BindArray(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001246
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001247 else if (FTy->isStructureType())
1248 St = BindStruct(St, FR, *VI);
Zhongxing Xua82512a2008-10-24 08:42:28 +00001249 }
1250
Zhongxing Xu4193eca2008-12-20 06:32:12 +00001251 return St;
Zhongxing Xuc3a05992008-11-19 11:06:24 +00001252}
1253
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001254const GRState* RegionStoreManager::KillStruct(const GRState* St,
1255 const TypedRegion* R){
1256 GRStateRef state(St, StateMgr);
1257
1258 // Kill the struct region because it is assigned "unknown".
1259 St = state.add<RegionKills>(R);
1260
1261 // Set the default value of the struct region to "unknown".
1262 St = state.set<RegionDefaultValue>(R, UnknownVal());
1263
1264 Store store = St->getStore();
1265 RegionBindingsTy B = GetRegionBindings(store);
1266
1267 // Remove all bindings for the subregions of the struct.
1268 for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
1269 const MemRegion* r = I.getKey();
1270 if (const SubRegion* sr = dyn_cast<SubRegion>(r))
1271 if (sr->isSubRegionOf(R))
1272 store = Remove(store, Loc::MakeVal(sr));
Zhongxing Xu9c2a3db2009-01-13 03:07:41 +00001273 // FIXME: Maybe we should also remove the bindings for the "views" of the
1274 // subregions.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001275 }
1276
1277 return StateMgr.MakeStateWithStore(St, store);
1278}
1279
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001280const GRState* RegionStoreManager::AddRegionView(const GRState* St,
1281 const MemRegion* View,
1282 const MemRegion* Base) {
1283 GRStateRef state(St, StateMgr);
1284
1285 // First, retrieve the region view of the base region.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001286 const RegionViews* d = state.get<RegionViewMap>(Base);
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001287 RegionViews L = d ? *d : RVFactory.GetEmptySet();
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001288
1289 // Now add View to the region view.
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001290 L = RVFactory.Add(L, View);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001291
1292 // Create a new state with the new region view.
Ted Kremenek50dc1b32008-12-24 01:05:03 +00001293 return state.set<RegionViewMap>(Base, L);
Zhongxing Xudc0a25d2008-11-16 04:07:26 +00001294}
Zhongxing Xu5834ed62009-01-13 01:49:57 +00001295
1296const GRState* RegionStoreManager::RemoveRegionView(const GRState* St,
1297 const MemRegion* View,
1298 const MemRegion* Base) {
1299 GRStateRef state(St, StateMgr);
1300
1301 // Retrieve the region view of the base region.
1302 const RegionViews* d = state.get<RegionViewMap>(Base);
1303
1304 // If the base region has no view, return.
1305 if (!d)
1306 return St;
1307
1308 // Remove the view.
1309 RegionViews V = *d;
1310 V = RVFactory.Remove(V, View);
1311
1312 return state.set<RegionViewMap>(Base, V);
1313}
Zhongxing Xu20794942009-05-06 08:33:50 +00001314
1315const GRState* RegionStoreManager::setCastType(const GRState* St,
1316 const MemRegion* R, QualType T) {
1317 GRStateRef state(St, StateMgr);
1318 return state.set<RegionCasts>(R, T);
1319}