blob: 5f1a1e1d09a7520c4ee525241ee344b841c5ba65 [file] [log] [blame]
Ted Kremenekc62abc12009-04-21 21:51:34 +00001//== Store.cpp - Interface for maps from Locations to Values ----*- 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 defined the types Store and StoreManager.
11//
12//===----------------------------------------------------------------------===//
13
Ted Kremenek1309f9a2010-01-25 04:41:41 +000014#include "clang/Checker/PathSensitive/Store.h"
15#include "clang/Checker/PathSensitive/GRState.h"
Ken Dyck199c3d62010-01-11 17:06:35 +000016#include "clang/AST/CharUnits.h"
Ted Kremenekc62abc12009-04-21 21:51:34 +000017
18using namespace clang;
19
Ted Kremenekf7a0cf42009-07-29 21:43:22 +000020StoreManager::StoreManager(GRStateManager &stateMgr)
21 : ValMgr(stateMgr.getValueManager()), StateMgr(stateMgr),
Zhongxing Xu2a393db2010-02-08 06:00:22 +000022 MRMgr(ValMgr.getRegionManager()), Ctx(stateMgr.getContext()) {}
Ted Kremenekc62abc12009-04-21 21:51:34 +000023
Jordy Roseff59efd2010-08-03 20:44:35 +000024Store StoreManager::EnterStackFrame(const GRState *state,
25 const StackFrameContext *frame) {
26 return state->getStore();
27}
28
Zhongxing Xu09270cc2009-10-14 06:55:01 +000029const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base,
Zhongxing Xu652be342009-11-16 04:49:44 +000030 QualType EleTy, uint64_t index) {
Ted Kremenek02282ac2010-09-15 03:13:30 +000031 NonLoc idx = ValMgr.makeArrayIndex(index);
Zhongxing Xu09270cc2009-10-14 06:55:01 +000032 return MRMgr.getElementRegion(EleTy, idx, Base, ValMgr.getContext());
Ted Kremenek411af402009-07-06 22:23:45 +000033}
34
Ted Kremenek19e1f0b2009-08-01 06:17:29 +000035// FIXME: Merge with the implementation of the same method in MemRegion.cpp
Ted Kremenek169077d2009-07-06 23:47:19 +000036static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
Ted Kremenek6217b802009-07-29 21:53:49 +000037 if (const RecordType *RT = Ty->getAs<RecordType>()) {
Ted Kremenek169077d2009-07-06 23:47:19 +000038 const RecordDecl *D = RT->getDecl();
Douglas Gregor952b0172010-02-11 01:04:33 +000039 if (!D->getDefinition())
Ted Kremenek169077d2009-07-06 23:47:19 +000040 return false;
41 }
Mike Stump1eb44332009-09-09 15:08:12 +000042
Ted Kremenek169077d2009-07-06 23:47:19 +000043 return true;
44}
45
Zhongxing Xu856c6bc2010-04-19 11:47:28 +000046const ElementRegion *StoreManager::GetElementZeroRegion(const MemRegion *R,
47 QualType T) {
Ted Kremenek02282ac2010-09-15 03:13:30 +000048 NonLoc idx = ValMgr.makeZeroArrayIndex();
Zhongxing Xu856c6bc2010-04-19 11:47:28 +000049 assert(!T.isNull());
50 return MRMgr.getElementRegion(T, idx, R, Ctx);
51}
52
Zhongxing Xu09270cc2009-10-14 06:55:01 +000053const MemRegion *StoreManager::CastRegion(const MemRegion *R, QualType CastToTy) {
Mike Stump1eb44332009-09-09 15:08:12 +000054
Ted Kremenek48ce7de2009-07-06 20:21:51 +000055 ASTContext& Ctx = StateMgr.getContext();
Mike Stump1eb44332009-09-09 15:08:12 +000056
Ted Kremenekb9a44252009-07-06 22:39:40 +000057 // Handle casts to Objective-C objects.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +000058 if (CastToTy->isObjCObjectPointerType())
Zhongxing Xu479529e2009-11-10 02:17:20 +000059 return R->StripCasts();
Ted Kremenek19e1f0b2009-08-01 06:17:29 +000060
Ted Kremenek63b9cfe2009-07-18 06:27:51 +000061 if (CastToTy->isBlockPointerType()) {
Ted Kremenekabd46e12009-08-28 04:49:15 +000062 // FIXME: We may need different solutions, depending on the symbol
Ted Kremenek63b9cfe2009-07-18 06:27:51 +000063 // involved. Blocks can be casted to/from 'id', as they can be treated
Ted Kremenekabd46e12009-08-28 04:49:15 +000064 // as Objective-C objects. This could possibly be handled by enhancing
Mike Stump1eb44332009-09-09 15:08:12 +000065 // our reasoning of downcasts of symbolic objects.
Ted Kremenekabd46e12009-08-28 04:49:15 +000066 if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R))
Zhongxing Xu09270cc2009-10-14 06:55:01 +000067 return R;
Ted Kremenek63b9cfe2009-07-18 06:27:51 +000068
69 // We don't know what to make of it. Return a NULL region, which
70 // will be interpretted as UnknownVal.
Zhongxing Xu09270cc2009-10-14 06:55:01 +000071 return NULL;
Ted Kremenek63b9cfe2009-07-18 06:27:51 +000072 }
Ted Kremenek411af402009-07-06 22:23:45 +000073
Ted Kremenek48ce7de2009-07-06 20:21:51 +000074 // Now assume we are casting from pointer to pointer. Other cases should
75 // already be handled.
Ted Kremenek6217b802009-07-29 21:53:49 +000076 QualType PointeeTy = CastToTy->getAs<PointerType>()->getPointeeType();
Ted Kremenek9a108eb2009-08-02 04:12:53 +000077 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
78
79 // Handle casts to void*. We just pass the region through.
Douglas Gregora4923eb2009-11-16 21:35:15 +000080 if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy)
Zhongxing Xu09270cc2009-10-14 06:55:01 +000081 return R;
Mike Stump1eb44332009-09-09 15:08:12 +000082
Ted Kremenek9a108eb2009-08-02 04:12:53 +000083 // Handle casts from compatible types.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +000084 if (R->isBoundable())
85 if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
Zhongxing Xu018220c2010-08-11 06:10:55 +000086 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType());
Ted Kremenek9a108eb2009-08-02 04:12:53 +000087 if (CanonPointeeTy == ObjTy)
Zhongxing Xu09270cc2009-10-14 06:55:01 +000088 return R;
Ted Kremenek19e1f0b2009-08-01 06:17:29 +000089 }
90
Ted Kremenek48ce7de2009-07-06 20:21:51 +000091 // Process region cast according to the kind of the region being cast.
Ted Kremenekfc8f57c2009-07-06 22:56:37 +000092 switch (R->getKind()) {
Ted Kremenekde0d2632010-01-05 02:18:06 +000093 case MemRegion::CXXThisRegionKind:
Ted Kremenek67d12872009-12-07 22:05:27 +000094 case MemRegion::GenericMemSpaceRegionKind:
95 case MemRegion::StackLocalsSpaceRegionKind:
96 case MemRegion::StackArgumentsSpaceRegionKind:
97 case MemRegion::HeapSpaceRegionKind:
Ted Kremenek2b87ae42009-12-11 06:43:27 +000098 case MemRegion::UnknownSpaceRegionKind:
Ted Kremenekdcee3ce2010-07-01 20:16:50 +000099 case MemRegion::NonStaticGlobalSpaceRegionKind:
100 case MemRegion::StaticGlobalSpaceRegionKind: {
Ted Kremenekfc8f57c2009-07-06 22:56:37 +0000101 assert(0 && "Invalid region cast");
102 break;
Mike Stump1eb44332009-09-09 15:08:12 +0000103 }
Ted Kremenek1e4a32a2010-09-01 23:00:46 +0000104
Ted Kremenekeb1c7a02009-11-25 01:32:22 +0000105 case MemRegion::FunctionTextRegionKind:
Ted Kremenekbf0fe6c2009-11-25 23:58:21 +0000106 case MemRegion::BlockTextRegionKind:
Ted Kremenek1e4a32a2010-09-01 23:00:46 +0000107 case MemRegion::BlockDataRegionKind:
Ted Kremenekfc8f57c2009-07-06 22:56:37 +0000108 case MemRegion::StringRegionKind:
Ted Kremenekfc8f57c2009-07-06 22:56:37 +0000109 // FIXME: Need to handle arbitrary downcasts.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000110 case MemRegion::SymbolicRegionKind:
111 case MemRegion::AllocaRegionKind:
Ted Kremenekfc8f57c2009-07-06 22:56:37 +0000112 case MemRegion::CompoundLiteralRegionKind:
Ted Kremenekfc8f57c2009-07-06 22:56:37 +0000113 case MemRegion::FieldRegionKind:
114 case MemRegion::ObjCIvarRegionKind:
Mike Stump1eb44332009-09-09 15:08:12 +0000115 case MemRegion::VarRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000116 case MemRegion::CXXTempObjectRegionKind:
117 case MemRegion::CXXBaseObjectRegionKind:
Zhongxing Xu09270cc2009-10-14 06:55:01 +0000118 return MakeElementRegion(R, PointeeTy);
Mike Stump1eb44332009-09-09 15:08:12 +0000119
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000120 case MemRegion::ElementRegionKind: {
121 // If we are casting from an ElementRegion to another type, the
122 // algorithm is as follows:
123 //
124 // (1) Compute the "raw offset" of the ElementRegion from the
125 // base region. This is done by calling 'getAsRawOffset()'.
126 //
Mike Stump1eb44332009-09-09 15:08:12 +0000127 // (2a) If we get a 'RegionRawOffset' after calling
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000128 // 'getAsRawOffset()', determine if the absolute offset
Mike Stump1eb44332009-09-09 15:08:12 +0000129 // can be exactly divided into chunks of the size of the
130 // casted-pointee type. If so, create a new ElementRegion with
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000131 // the pointee-cast type as the new ElementType and the index
132 // being the offset divded by the chunk size. If not, create
133 // a new ElementRegion at offset 0 off the raw offset region.
134 //
135 // (2b) If we don't a get a 'RegionRawOffset' after calling
136 // 'getAsRawOffset()', it means that we are at offset 0.
Mike Stump1eb44332009-09-09 15:08:12 +0000137 //
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000138 // FIXME: Handle symbolic raw offsets.
Mike Stump1eb44332009-09-09 15:08:12 +0000139
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000140 const ElementRegion *elementR = cast<ElementRegion>(R);
Zhongxing Xu7caf9b32010-08-02 04:56:14 +0000141 const RegionRawOffset &rawOff = elementR->getAsArrayOffset();
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000142 const MemRegion *baseR = rawOff.getRegion();
Mike Stump1eb44332009-09-09 15:08:12 +0000143
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000144 // If we cannot compute a raw offset, throw up our hands and return
145 // a NULL MemRegion*.
146 if (!baseR)
Zhongxing Xu09270cc2009-10-14 06:55:01 +0000147 return NULL;
Mike Stump1eb44332009-09-09 15:08:12 +0000148
Ken Dyck199c3d62010-01-11 17:06:35 +0000149 CharUnits off = CharUnits::fromQuantity(rawOff.getByteOffset());
Mike Stump1eb44332009-09-09 15:08:12 +0000150
Ken Dyck199c3d62010-01-11 17:06:35 +0000151 if (off.isZero()) {
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000152 // Edge case: we are at 0 bytes off the beginning of baseR. We
153 // check to see if type we are casting to is the same as the base
Mike Stump1eb44332009-09-09 15:08:12 +0000154 // region. If so, just return the base region.
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000155 if (const TypedRegion *TR = dyn_cast<TypedRegion>(baseR)) {
Zhongxing Xu018220c2010-08-11 06:10:55 +0000156 QualType ObjTy = Ctx.getCanonicalType(TR->getValueType());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000157 QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
158 if (CanonPointeeTy == ObjTy)
Zhongxing Xu09270cc2009-10-14 06:55:01 +0000159 return baseR;
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000160 }
Mike Stump1eb44332009-09-09 15:08:12 +0000161
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000162 // Otherwise, create a new ElementRegion at offset 0.
Zhongxing Xu09270cc2009-10-14 06:55:01 +0000163 return MakeElementRegion(baseR, PointeeTy);
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000164 }
Mike Stump1eb44332009-09-09 15:08:12 +0000165
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000166 // We have a non-zero offset from the base region. We want to determine
167 // if the offset can be evenly divided by sizeof(PointeeTy). If so,
168 // we create an ElementRegion whose index is that value. Otherwise, we
169 // create two ElementRegions, one that reflects a raw offset and the other
170 // that reflects the cast.
Mike Stump1eb44332009-09-09 15:08:12 +0000171
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000172 // Compute the index for the new ElementRegion.
173 int64_t newIndex = 0;
174 const MemRegion *newSuperR = 0;
175
176 // We can only compute sizeof(PointeeTy) if it is a complete type.
177 if (IsCompleteType(Ctx, PointeeTy)) {
178 // Compute the size in **bytes**.
Ken Dyck199c3d62010-01-11 17:06:35 +0000179 CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy);
Ted Kremenek974d97b2010-04-07 00:46:49 +0000180 if (!pointeeTySize.isZero()) {
181 // Is the offset a multiple of the size? If so, we can layer the
182 // ElementRegion (with elementType == PointeeTy) directly on top of
183 // the base region.
184 if (off % pointeeTySize == 0) {
185 newIndex = off / pointeeTySize;
186 newSuperR = baseR;
187 }
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000188 }
189 }
Mike Stump1eb44332009-09-09 15:08:12 +0000190
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000191 if (!newSuperR) {
192 // Create an intermediate ElementRegion to represent the raw byte.
193 // This will be the super region of the final ElementRegion.
Ken Dyck199c3d62010-01-11 17:06:35 +0000194 newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity());
Ted Kremenek19e1f0b2009-08-01 06:17:29 +0000195 }
Mike Stump1eb44332009-09-09 15:08:12 +0000196
Zhongxing Xu09270cc2009-10-14 06:55:01 +0000197 return MakeElementRegion(newSuperR, PointeeTy, newIndex);
Ted Kremenek48ce7de2009-07-06 20:21:51 +0000198 }
199 }
Mike Stump1eb44332009-09-09 15:08:12 +0000200
Zhongxing Xu09270cc2009-10-14 06:55:01 +0000201 assert(0 && "unreachable");
202 return 0;
Ted Kremenek48ce7de2009-07-06 20:21:51 +0000203}
Ted Kremenek1894dce2009-08-25 20:51:30 +0000204
205
206/// CastRetrievedVal - Used by subclasses of StoreManager to implement
207/// implicit casts that arise from loads from regions that are reinterpreted
208/// as another region.
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000209SVal StoreManager::CastRetrievedVal(SVal V, const TypedRegion *R,
210 QualType castTy, bool performTestOnly) {
Ted Kremenek852274d2009-12-16 03:18:58 +0000211
Zhongxing Xu652be342009-11-16 04:49:44 +0000212 if (castTy.isNull())
213 return V;
Ted Kremenek852274d2009-12-16 03:18:58 +0000214
215 ASTContext &Ctx = ValMgr.getContext();
Zhongxing Xu2f4a6b22009-12-09 08:32:57 +0000216
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000217 if (performTestOnly) {
218 // Automatically translate references to pointers.
Zhongxing Xu018220c2010-08-11 06:10:55 +0000219 QualType T = R->getValueType();
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000220 if (const ReferenceType *RT = T->getAs<ReferenceType>())
221 T = Ctx.getPointerType(RT->getPointeeType());
222
223 assert(ValMgr.getContext().hasSameUnqualifiedType(castTy, T));
224 return V;
225 }
226
227 if (const Loc *L = dyn_cast<Loc>(&V))
Ted Kremenek9c149532010-12-01 21:57:22 +0000228 return ValMgr.getSValBuilder().evalCastL(*L, castTy);
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000229 else if (const NonLoc *NL = dyn_cast<NonLoc>(&V))
Ted Kremenek9c149532010-12-01 21:57:22 +0000230 return ValMgr.getSValBuilder().evalCastNL(*NL, castTy);
Ted Kremenekc50e6df2010-01-11 02:33:26 +0000231
Zhongxing Xu652be342009-11-16 04:49:44 +0000232 return V;
Ted Kremenek1894dce2009-08-25 20:51:30 +0000233}
234
Zhongxing Xuc1511e02010-02-08 07:58:06 +0000235SVal StoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) {
236 if (Base.isUnknownOrUndef())
237 return Base;
238
239 Loc BaseL = cast<Loc>(Base);
240 const MemRegion* BaseR = 0;
241
242 switch (BaseL.getSubKind()) {
243 case loc::MemRegionKind:
244 BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
245 break;
246
247 case loc::GotoLabelKind:
248 // These are anormal cases. Flag an undefined value.
249 return UndefinedVal();
250
251 case loc::ConcreteIntKind:
252 // While these seem funny, this can happen through casts.
253 // FIXME: What we should return is the field offset. For example,
254 // add the field offset to the integer value. That way funny things
255 // like this work properly: &(((struct foo *) 0xa)->f)
256 return Base;
257
258 default:
259 assert(0 && "Unhandled Base.");
260 return Base;
261 }
262
263 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
264 // of FieldDecl.
265 if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
266 return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
267
268 return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
269}
Zhongxing Xu52535682010-02-08 08:17:02 +0000270
Ted Kremenek02282ac2010-09-15 03:13:30 +0000271SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset,
Zhongxing Xu52535682010-02-08 08:17:02 +0000272 SVal Base) {
273
274 // If the base is an unknown or undefined value, just return it back.
275 // FIXME: For absolute pointer addresses, we just return that value back as
276 // well, although in reality we should return the offset added to that
277 // value.
278 if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
279 return Base;
280
Zhongxing Xu52535682010-02-08 08:17:02 +0000281 const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
282
283 // Pointer of any type can be cast and used as array base.
284 const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
285
286 // Convert the offset to the appropriate size and signedness.
Ted Kremenek02282ac2010-09-15 03:13:30 +0000287 Offset = cast<NonLoc>(ValMgr.convertToArrayIndex(Offset));
Zhongxing Xu52535682010-02-08 08:17:02 +0000288
289 if (!ElemR) {
290 //
291 // If the base region is not an ElementRegion, create one.
292 // This can happen in the following example:
293 //
294 // char *p = __builtin_alloc(10);
295 // p[1] = 8;
296 //
297 // Observe that 'p' binds to an AllocaRegion.
298 //
299 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
300 BaseRegion, Ctx));
301 }
302
303 SVal BaseIdx = ElemR->getIndex();
304
305 if (!isa<nonloc::ConcreteInt>(BaseIdx))
306 return UnknownVal();
307
308 const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
Jordy Rosee7011172010-08-16 01:15:17 +0000309
310 // Only allow non-integer offsets if the base region has no offset itself.
311 // FIXME: This is a somewhat arbitrary restriction. We should be using
Ted Kremenek846eabd2010-12-01 21:28:31 +0000312 // SValBuilder here to add the two offsets without checking their types.
Jordy Rosee7011172010-08-16 01:15:17 +0000313 if (!isa<nonloc::ConcreteInt>(Offset)) {
314 if (isa<ElementRegion>(BaseRegion->StripCasts()))
315 return UnknownVal();
316
317 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
318 ElemR->getSuperRegion(),
319 Ctx));
320 }
321
Zhongxing Xu52535682010-02-08 08:17:02 +0000322 const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
323 assert(BaseIdxI.isSigned());
324
325 // Compute the new index.
Ted Kremenek02282ac2010-09-15 03:13:30 +0000326 nonloc::ConcreteInt NewIdx(ValMgr.getBasicValueFactory().getValue(BaseIdxI +
327 OffI));
Zhongxing Xu52535682010-02-08 08:17:02 +0000328
329 // Construct the new ElementRegion.
330 const MemRegion *ArrayR = ElemR->getSuperRegion();
331 return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
332 Ctx));
333}