1 //== Store.cpp - Interface for maps from Locations to Values ----*- C++ -*--==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defined the types Store and StoreManager.
12 //===----------------------------------------------------------------------===//
14 #include "clang/StaticAnalyzer/PathSensitive/Store.h"
15 #include "clang/StaticAnalyzer/PathSensitive/GRState.h"
16 #include "clang/AST/CharUnits.h"
18 using namespace clang
;
21 StoreManager::StoreManager(GRStateManager
&stateMgr
)
22 : svalBuilder(stateMgr
.getSValBuilder()), StateMgr(stateMgr
),
23 MRMgr(svalBuilder
.getRegionManager()), Ctx(stateMgr
.getContext()) {}
25 Store
StoreManager::enterStackFrame(const GRState
*state
,
26 const StackFrameContext
*frame
) {
27 return state
->getStore();
30 const MemRegion
*StoreManager::MakeElementRegion(const MemRegion
*Base
,
31 QualType EleTy
, uint64_t index
) {
32 NonLoc idx
= svalBuilder
.makeArrayIndex(index
);
33 return MRMgr
.getElementRegion(EleTy
, idx
, Base
, svalBuilder
.getContext());
36 // FIXME: Merge with the implementation of the same method in MemRegion.cpp
37 static bool IsCompleteType(ASTContext
&Ctx
, QualType Ty
) {
38 if (const RecordType
*RT
= Ty
->getAs
<RecordType
>()) {
39 const RecordDecl
*D
= RT
->getDecl();
40 if (!D
->getDefinition())
47 const ElementRegion
*StoreManager::GetElementZeroRegion(const MemRegion
*R
,
49 NonLoc idx
= svalBuilder
.makeZeroArrayIndex();
51 return MRMgr
.getElementRegion(T
, idx
, R
, Ctx
);
54 const MemRegion
*StoreManager::CastRegion(const MemRegion
*R
, QualType CastToTy
) {
56 ASTContext
& Ctx
= StateMgr
.getContext();
58 // Handle casts to Objective-C objects.
59 if (CastToTy
->isObjCObjectPointerType())
60 return R
->StripCasts();
62 if (CastToTy
->isBlockPointerType()) {
63 // FIXME: We may need different solutions, depending on the symbol
64 // involved. Blocks can be casted to/from 'id', as they can be treated
65 // as Objective-C objects. This could possibly be handled by enhancing
66 // our reasoning of downcasts of symbolic objects.
67 if (isa
<CodeTextRegion
>(R
) || isa
<SymbolicRegion
>(R
))
70 // We don't know what to make of it. Return a NULL region, which
71 // will be interpretted as UnknownVal.
75 // Now assume we are casting from pointer to pointer. Other cases should
76 // already be handled.
77 QualType PointeeTy
= CastToTy
->getAs
<PointerType
>()->getPointeeType();
78 QualType CanonPointeeTy
= Ctx
.getCanonicalType(PointeeTy
);
80 // Handle casts to void*. We just pass the region through.
81 if (CanonPointeeTy
.getLocalUnqualifiedType() == Ctx
.VoidTy
)
84 // Handle casts from compatible types.
86 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(R
)) {
87 QualType ObjTy
= Ctx
.getCanonicalType(TR
->getValueType());
88 if (CanonPointeeTy
== ObjTy
)
92 // Process region cast according to the kind of the region being cast.
93 switch (R
->getKind()) {
94 case MemRegion::CXXThisRegionKind
:
95 case MemRegion::GenericMemSpaceRegionKind
:
96 case MemRegion::StackLocalsSpaceRegionKind
:
97 case MemRegion::StackArgumentsSpaceRegionKind
:
98 case MemRegion::HeapSpaceRegionKind
:
99 case MemRegion::UnknownSpaceRegionKind
:
100 case MemRegion::NonStaticGlobalSpaceRegionKind
:
101 case MemRegion::StaticGlobalSpaceRegionKind
: {
102 assert(0 && "Invalid region cast");
106 case MemRegion::FunctionTextRegionKind
:
107 case MemRegion::BlockTextRegionKind
:
108 case MemRegion::BlockDataRegionKind
:
109 case MemRegion::StringRegionKind
:
110 // FIXME: Need to handle arbitrary downcasts.
111 case MemRegion::SymbolicRegionKind
:
112 case MemRegion::AllocaRegionKind
:
113 case MemRegion::CompoundLiteralRegionKind
:
114 case MemRegion::FieldRegionKind
:
115 case MemRegion::ObjCIvarRegionKind
:
116 case MemRegion::VarRegionKind
:
117 case MemRegion::CXXTempObjectRegionKind
:
118 case MemRegion::CXXBaseObjectRegionKind
:
119 return MakeElementRegion(R
, PointeeTy
);
121 case MemRegion::ElementRegionKind
: {
122 // If we are casting from an ElementRegion to another type, the
123 // algorithm is as follows:
125 // (1) Compute the "raw offset" of the ElementRegion from the
126 // base region. This is done by calling 'getAsRawOffset()'.
128 // (2a) If we get a 'RegionRawOffset' after calling
129 // 'getAsRawOffset()', determine if the absolute offset
130 // can be exactly divided into chunks of the size of the
131 // casted-pointee type. If so, create a new ElementRegion with
132 // the pointee-cast type as the new ElementType and the index
133 // being the offset divded by the chunk size. If not, create
134 // a new ElementRegion at offset 0 off the raw offset region.
136 // (2b) If we don't a get a 'RegionRawOffset' after calling
137 // 'getAsRawOffset()', it means that we are at offset 0.
139 // FIXME: Handle symbolic raw offsets.
141 const ElementRegion
*elementR
= cast
<ElementRegion
>(R
);
142 const RegionRawOffset
&rawOff
= elementR
->getAsArrayOffset();
143 const MemRegion
*baseR
= rawOff
.getRegion();
145 // If we cannot compute a raw offset, throw up our hands and return
146 // a NULL MemRegion*.
150 CharUnits off
= rawOff
.getOffset();
153 // Edge case: we are at 0 bytes off the beginning of baseR. We
154 // check to see if type we are casting to is the same as the base
155 // region. If so, just return the base region.
156 if (const TypedRegion
*TR
= dyn_cast
<TypedRegion
>(baseR
)) {
157 QualType ObjTy
= Ctx
.getCanonicalType(TR
->getValueType());
158 QualType CanonPointeeTy
= Ctx
.getCanonicalType(PointeeTy
);
159 if (CanonPointeeTy
== ObjTy
)
163 // Otherwise, create a new ElementRegion at offset 0.
164 return MakeElementRegion(baseR
, PointeeTy
);
167 // We have a non-zero offset from the base region. We want to determine
168 // if the offset can be evenly divided by sizeof(PointeeTy). If so,
169 // we create an ElementRegion whose index is that value. Otherwise, we
170 // create two ElementRegions, one that reflects a raw offset and the other
171 // that reflects the cast.
173 // Compute the index for the new ElementRegion.
174 int64_t newIndex
= 0;
175 const MemRegion
*newSuperR
= 0;
177 // We can only compute sizeof(PointeeTy) if it is a complete type.
178 if (IsCompleteType(Ctx
, PointeeTy
)) {
179 // Compute the size in **bytes**.
180 CharUnits pointeeTySize
= Ctx
.getTypeSizeInChars(PointeeTy
);
181 if (!pointeeTySize
.isZero()) {
182 // Is the offset a multiple of the size? If so, we can layer the
183 // ElementRegion (with elementType == PointeeTy) directly on top of
185 if (off
% pointeeTySize
== 0) {
186 newIndex
= off
/ pointeeTySize
;
193 // Create an intermediate ElementRegion to represent the raw byte.
194 // This will be the super region of the final ElementRegion.
195 newSuperR
= MakeElementRegion(baseR
, Ctx
.CharTy
, off
.getQuantity());
198 return MakeElementRegion(newSuperR
, PointeeTy
, newIndex
);
202 assert(0 && "unreachable");
207 /// CastRetrievedVal - Used by subclasses of StoreManager to implement
208 /// implicit casts that arise from loads from regions that are reinterpreted
209 /// as another region.
210 SVal
StoreManager::CastRetrievedVal(SVal V
, const TypedRegion
*R
,
211 QualType castTy
, bool performTestOnly
) {
216 ASTContext
&Ctx
= svalBuilder
.getContext();
218 if (performTestOnly
) {
219 // Automatically translate references to pointers.
220 QualType T
= R
->getValueType();
221 if (const ReferenceType
*RT
= T
->getAs
<ReferenceType
>())
222 T
= Ctx
.getPointerType(RT
->getPointeeType());
224 assert(svalBuilder
.getContext().hasSameUnqualifiedType(castTy
, T
));
228 if (const Loc
*L
= dyn_cast
<Loc
>(&V
))
229 return svalBuilder
.evalCastL(*L
, castTy
);
230 else if (const NonLoc
*NL
= dyn_cast
<NonLoc
>(&V
))
231 return svalBuilder
.evalCastNL(*NL
, castTy
);
236 SVal
StoreManager::getLValueFieldOrIvar(const Decl
* D
, SVal Base
) {
237 if (Base
.isUnknownOrUndef())
240 Loc BaseL
= cast
<Loc
>(Base
);
241 const MemRegion
* BaseR
= 0;
243 switch (BaseL
.getSubKind()) {
244 case loc::MemRegionKind
:
245 BaseR
= cast
<loc::MemRegionVal
>(BaseL
).getRegion();
248 case loc::GotoLabelKind
:
249 // These are anormal cases. Flag an undefined value.
250 return UndefinedVal();
252 case loc::ConcreteIntKind
:
253 // While these seem funny, this can happen through casts.
254 // FIXME: What we should return is the field offset. For example,
255 // add the field offset to the integer value. That way funny things
256 // like this work properly: &(((struct foo *) 0xa)->f)
260 assert(0 && "Unhandled Base.");
264 // NOTE: We must have this check first because ObjCIvarDecl is a subclass
266 if (const ObjCIvarDecl
*ID
= dyn_cast
<ObjCIvarDecl
>(D
))
267 return loc::MemRegionVal(MRMgr
.getObjCIvarRegion(ID
, BaseR
));
269 return loc::MemRegionVal(MRMgr
.getFieldRegion(cast
<FieldDecl
>(D
), BaseR
));
272 SVal
StoreManager::getLValueElement(QualType elementType
, NonLoc Offset
,
275 // If the base is an unknown or undefined value, just return it back.
276 // FIXME: For absolute pointer addresses, we just return that value back as
277 // well, although in reality we should return the offset added to that
279 if (Base
.isUnknownOrUndef() || isa
<loc::ConcreteInt
>(Base
))
282 const MemRegion
* BaseRegion
= cast
<loc::MemRegionVal
>(Base
).getRegion();
284 // Pointer of any type can be cast and used as array base.
285 const ElementRegion
*ElemR
= dyn_cast
<ElementRegion
>(BaseRegion
);
287 // Convert the offset to the appropriate size and signedness.
288 Offset
= cast
<NonLoc
>(svalBuilder
.convertToArrayIndex(Offset
));
292 // If the base region is not an ElementRegion, create one.
293 // This can happen in the following example:
295 // char *p = __builtin_alloc(10);
298 // Observe that 'p' binds to an AllocaRegion.
300 return loc::MemRegionVal(MRMgr
.getElementRegion(elementType
, Offset
,
304 SVal BaseIdx
= ElemR
->getIndex();
306 if (!isa
<nonloc::ConcreteInt
>(BaseIdx
))
309 const llvm::APSInt
& BaseIdxI
= cast
<nonloc::ConcreteInt
>(BaseIdx
).getValue();
311 // Only allow non-integer offsets if the base region has no offset itself.
312 // FIXME: This is a somewhat arbitrary restriction. We should be using
313 // SValBuilder here to add the two offsets without checking their types.
314 if (!isa
<nonloc::ConcreteInt
>(Offset
)) {
315 if (isa
<ElementRegion
>(BaseRegion
->StripCasts()))
318 return loc::MemRegionVal(MRMgr
.getElementRegion(elementType
, Offset
,
319 ElemR
->getSuperRegion(),
323 const llvm::APSInt
& OffI
= cast
<nonloc::ConcreteInt
>(Offset
).getValue();
324 assert(BaseIdxI
.isSigned());
326 // Compute the new index.
327 nonloc::ConcreteInt
NewIdx(svalBuilder
.getBasicValueFactory().getValue(BaseIdxI
+
330 // Construct the new ElementRegion.
331 const MemRegion
*ArrayR
= ElemR
->getSuperRegion();
332 return loc::MemRegionVal(MRMgr
.getElementRegion(elementType
, NewIdx
, ArrayR
,