]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | // SValBuilder.cpp - Basic class for all SValBuilder implementations -*- 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 SValBuilder, the base class for all (complete) SValBuilder | |
11 | // implementations. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #include "clang/AST/ExprCXX.h" | |
16 | #include "clang/AST/DeclCXX.h" | |
17 | #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" | |
18 | #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" | |
19 | #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" | |
20 | #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" | |
21 | #include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" | |
22 | ||
23 | using namespace clang; | |
24 | using namespace ento; | |
25 | ||
26 | //===----------------------------------------------------------------------===// | |
27 | // Basic SVal creation. | |
28 | //===----------------------------------------------------------------------===// | |
29 | ||
30 | void SValBuilder::anchor() { } | |
31 | ||
32 | DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { | |
33 | if (Loc::isLocType(type)) | |
34 | return makeNull(); | |
35 | ||
36 | if (type->isIntegerType()) | |
37 | return makeIntVal(0, type); | |
38 | ||
39 | // FIXME: Handle floats. | |
40 | // FIXME: Handle structs. | |
41 | return UnknownVal(); | |
42 | } | |
43 | ||
44 | NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, | |
45 | const llvm::APSInt& rhs, QualType type) { | |
46 | // The Environment ensures we always get a persistent APSInt in | |
47 | // BasicValueFactory, so we don't need to get the APSInt from | |
48 | // BasicValueFactory again. | |
49 | assert(lhs); | |
50 | assert(!Loc::isLocType(type)); | |
51 | return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); | |
52 | } | |
53 | ||
54 | NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs, | |
55 | BinaryOperator::Opcode op, const SymExpr *rhs, | |
56 | QualType type) { | |
57 | assert(rhs); | |
58 | assert(!Loc::isLocType(type)); | |
59 | return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); | |
60 | } | |
61 | ||
62 | NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, | |
63 | const SymExpr *rhs, QualType type) { | |
64 | assert(lhs && rhs); | |
65 | assert(!Loc::isLocType(type)); | |
66 | return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); | |
67 | } | |
68 | ||
69 | NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, | |
70 | QualType fromTy, QualType toTy) { | |
71 | assert(operand); | |
72 | assert(!Loc::isLocType(toTy)); | |
73 | return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); | |
74 | } | |
75 | ||
76 | SVal SValBuilder::convertToArrayIndex(SVal val) { | |
77 | if (val.isUnknownOrUndef()) | |
78 | return val; | |
79 | ||
80 | // Common case: we have an appropriately sized integer. | |
81 | if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&val)) { | |
82 | const llvm::APSInt& I = CI->getValue(); | |
83 | if (I.getBitWidth() == ArrayIndexWidth && I.isSigned()) | |
84 | return val; | |
85 | } | |
86 | ||
87 | return evalCastFromNonLoc(cast<NonLoc>(val), ArrayIndexTy); | |
88 | } | |
89 | ||
90 | nonloc::ConcreteInt SValBuilder::makeBoolVal(const CXXBoolLiteralExpr *boolean){ | |
91 | return makeTruthVal(boolean->getValue()); | |
92 | } | |
93 | ||
94 | DefinedOrUnknownSVal | |
95 | SValBuilder::getRegionValueSymbolVal(const TypedValueRegion* region) { | |
96 | QualType T = region->getValueType(); | |
97 | ||
98 | if (!SymbolManager::canSymbolicate(T)) | |
99 | return UnknownVal(); | |
100 | ||
101 | SymbolRef sym = SymMgr.getRegionValueSymbol(region); | |
102 | ||
103 | if (Loc::isLocType(T)) | |
104 | return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); | |
105 | ||
106 | return nonloc::SymbolVal(sym); | |
107 | } | |
108 | ||
109 | DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, | |
110 | const Expr *expr, | |
111 | const LocationContext *LCtx, | |
112 | unsigned count) { | |
113 | QualType T = expr->getType(); | |
114 | return conjureSymbolVal(symbolTag, expr, LCtx, T, count); | |
115 | } | |
116 | ||
117 | DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const void *symbolTag, | |
118 | const Expr *expr, | |
119 | const LocationContext *LCtx, | |
120 | QualType type, | |
121 | unsigned count) { | |
122 | if (!SymbolManager::canSymbolicate(type)) | |
123 | return UnknownVal(); | |
124 | ||
125 | SymbolRef sym = SymMgr.conjureSymbol(expr, LCtx, type, count, symbolTag); | |
126 | ||
127 | if (Loc::isLocType(type)) | |
128 | return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); | |
129 | ||
130 | return nonloc::SymbolVal(sym); | |
131 | } | |
132 | ||
133 | ||
134 | DefinedOrUnknownSVal SValBuilder::conjureSymbolVal(const Stmt *stmt, | |
135 | const LocationContext *LCtx, | |
136 | QualType type, | |
137 | unsigned visitCount) { | |
138 | if (!SymbolManager::canSymbolicate(type)) | |
139 | return UnknownVal(); | |
140 | ||
141 | SymbolRef sym = SymMgr.conjureSymbol(stmt, LCtx, type, visitCount); | |
142 | ||
143 | if (Loc::isLocType(type)) | |
144 | return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); | |
145 | ||
146 | return nonloc::SymbolVal(sym); | |
147 | } | |
148 | ||
149 | DefinedOrUnknownSVal | |
150 | SValBuilder::getConjuredHeapSymbolVal(const Expr *E, | |
151 | const LocationContext *LCtx, | |
152 | unsigned VisitCount) { | |
153 | QualType T = E->getType(); | |
154 | assert(Loc::isLocType(T)); | |
155 | assert(SymbolManager::canSymbolicate(T)); | |
156 | ||
157 | SymbolRef sym = SymMgr.conjureSymbol(E, LCtx, T, VisitCount); | |
158 | return loc::MemRegionVal(MemMgr.getSymbolicHeapRegion(sym)); | |
159 | } | |
160 | ||
161 | DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag, | |
162 | const MemRegion *region, | |
163 | const Expr *expr, QualType type, | |
164 | unsigned count) { | |
165 | assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type"); | |
166 | ||
167 | SymbolRef sym = | |
168 | SymMgr.getMetadataSymbol(region, expr, type, count, symbolTag); | |
169 | ||
170 | if (Loc::isLocType(type)) | |
171 | return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); | |
172 | ||
173 | return nonloc::SymbolVal(sym); | |
174 | } | |
175 | ||
176 | DefinedOrUnknownSVal | |
177 | SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, | |
178 | const TypedValueRegion *region) { | |
179 | QualType T = region->getValueType(); | |
180 | ||
181 | if (!SymbolManager::canSymbolicate(T)) | |
182 | return UnknownVal(); | |
183 | ||
184 | SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region); | |
185 | ||
186 | if (Loc::isLocType(T)) | |
187 | return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); | |
188 | ||
189 | return nonloc::SymbolVal(sym); | |
190 | } | |
191 | ||
192 | DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) { | |
193 | return loc::MemRegionVal(MemMgr.getFunctionTextRegion(func)); | |
194 | } | |
195 | ||
196 | DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block, | |
197 | CanQualType locTy, | |
198 | const LocationContext *locContext) { | |
199 | const BlockTextRegion *BC = | |
200 | MemMgr.getBlockTextRegion(block, locTy, locContext->getAnalysisDeclContext()); | |
201 | const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext); | |
202 | return loc::MemRegionVal(BD); | |
203 | } | |
204 | ||
205 | /// Return a memory region for the 'this' object reference. | |
206 | loc::MemRegionVal SValBuilder::getCXXThis(const CXXMethodDecl *D, | |
207 | const StackFrameContext *SFC) { | |
208 | return loc::MemRegionVal(getRegionManager(). | |
209 | getCXXThisRegion(D->getThisType(getContext()), SFC)); | |
210 | } | |
211 | ||
212 | /// Return a memory region for the 'this' object reference. | |
213 | loc::MemRegionVal SValBuilder::getCXXThis(const CXXRecordDecl *D, | |
214 | const StackFrameContext *SFC) { | |
215 | const Type *T = D->getTypeForDecl(); | |
216 | QualType PT = getContext().getPointerType(QualType(T, 0)); | |
217 | return loc::MemRegionVal(getRegionManager().getCXXThisRegion(PT, SFC)); | |
218 | } | |
219 | ||
220 | //===----------------------------------------------------------------------===// | |
221 | ||
222 | SVal SValBuilder::makeSymExprValNN(ProgramStateRef State, | |
223 | BinaryOperator::Opcode Op, | |
224 | NonLoc LHS, NonLoc RHS, | |
225 | QualType ResultTy) { | |
226 | if (!State->isTainted(RHS) && !State->isTainted(LHS)) | |
227 | return UnknownVal(); | |
228 | ||
229 | const SymExpr *symLHS = LHS.getAsSymExpr(); | |
230 | const SymExpr *symRHS = RHS.getAsSymExpr(); | |
231 | // TODO: When the Max Complexity is reached, we should conjure a symbol | |
232 | // instead of generating an Unknown value and propagate the taint info to it. | |
233 | const unsigned MaxComp = 10000; // 100000 28X | |
234 | ||
235 | if (symLHS && symRHS && | |
236 | (symLHS->computeComplexity() + symRHS->computeComplexity()) < MaxComp) | |
237 | return makeNonLoc(symLHS, Op, symRHS, ResultTy); | |
238 | ||
239 | if (symLHS && symLHS->computeComplexity() < MaxComp) | |
240 | if (const nonloc::ConcreteInt *rInt = dyn_cast<nonloc::ConcreteInt>(&RHS)) | |
241 | return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy); | |
242 | ||
243 | if (symRHS && symRHS->computeComplexity() < MaxComp) | |
244 | if (const nonloc::ConcreteInt *lInt = dyn_cast<nonloc::ConcreteInt>(&LHS)) | |
245 | return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy); | |
246 | ||
247 | return UnknownVal(); | |
248 | } | |
249 | ||
250 | ||
251 | SVal SValBuilder::evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, | |
252 | SVal lhs, SVal rhs, QualType type) { | |
253 | ||
254 | if (lhs.isUndef() || rhs.isUndef()) | |
255 | return UndefinedVal(); | |
256 | ||
257 | if (lhs.isUnknown() || rhs.isUnknown()) | |
258 | return UnknownVal(); | |
259 | ||
260 | if (isa<Loc>(lhs)) { | |
261 | if (isa<Loc>(rhs)) | |
262 | return evalBinOpLL(state, op, cast<Loc>(lhs), cast<Loc>(rhs), type); | |
263 | ||
264 | return evalBinOpLN(state, op, cast<Loc>(lhs), cast<NonLoc>(rhs), type); | |
265 | } | |
266 | ||
267 | if (isa<Loc>(rhs)) { | |
268 | // Support pointer arithmetic where the addend is on the left | |
269 | // and the pointer on the right. | |
270 | assert(op == BO_Add); | |
271 | ||
272 | // Commute the operands. | |
273 | return evalBinOpLN(state, op, cast<Loc>(rhs), cast<NonLoc>(lhs), type); | |
274 | } | |
275 | ||
276 | return evalBinOpNN(state, op, cast<NonLoc>(lhs), cast<NonLoc>(rhs), type); | |
277 | } | |
278 | ||
279 | DefinedOrUnknownSVal SValBuilder::evalEQ(ProgramStateRef state, | |
280 | DefinedOrUnknownSVal lhs, | |
281 | DefinedOrUnknownSVal rhs) { | |
282 | return cast<DefinedOrUnknownSVal>(evalBinOp(state, BO_EQ, lhs, rhs, | |
283 | Context.IntTy)); | |
284 | } | |
285 | ||
286 | /// Recursively check if the pointer types are equal modulo const, volatile, | |
287 | /// and restrict qualifiers. Assumes the input types are canonical. | |
288 | /// TODO: This is based off of code in SemaCast; can we reuse it. | |
289 | static bool haveSimilarTypes(ASTContext &Context, QualType T1, | |
290 | QualType T2) { | |
291 | while (Context.UnwrapSimilarPointerTypes(T1, T2)) { | |
292 | Qualifiers Quals1, Quals2; | |
293 | T1 = Context.getUnqualifiedArrayType(T1, Quals1); | |
294 | T2 = Context.getUnqualifiedArrayType(T2, Quals2); | |
295 | ||
296 | // Make sure that non cvr-qualifiers the other qualifiers (e.g., address | |
297 | // spaces) are identical. | |
298 | Quals1.removeCVRQualifiers(); | |
299 | Quals2.removeCVRQualifiers(); | |
300 | if (Quals1 != Quals2) | |
301 | return false; | |
302 | } | |
303 | ||
304 | if (T1 != T2) | |
305 | return false; | |
306 | ||
307 | return true; | |
308 | } | |
309 | ||
310 | // FIXME: should rewrite according to the cast kind. | |
311 | SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) { | |
312 | castTy = Context.getCanonicalType(castTy); | |
313 | originalTy = Context.getCanonicalType(originalTy); | |
314 | if (val.isUnknownOrUndef() || castTy == originalTy) | |
315 | return val; | |
316 | ||
317 | // For const casts, just propagate the value. | |
318 | if (!castTy->isVariableArrayType() && !originalTy->isVariableArrayType()) | |
319 | if (haveSimilarTypes(Context, Context.getPointerType(castTy), | |
320 | Context.getPointerType(originalTy))) | |
321 | return val; | |
322 | ||
323 | // Check for casts from pointers to integers. | |
324 | if (castTy->isIntegerType() && Loc::isLocType(originalTy)) | |
325 | return evalCastFromLoc(cast<Loc>(val), castTy); | |
326 | ||
327 | // Check for casts from integers to pointers. | |
328 | if (Loc::isLocType(castTy) && originalTy->isIntegerType()) { | |
329 | if (nonloc::LocAsInteger *LV = dyn_cast<nonloc::LocAsInteger>(&val)) { | |
330 | if (const MemRegion *R = LV->getLoc().getAsRegion()) { | |
331 | StoreManager &storeMgr = StateMgr.getStoreManager(); | |
332 | R = storeMgr.castRegion(R, castTy); | |
333 | return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); | |
334 | } | |
335 | return LV->getLoc(); | |
336 | } | |
337 | return dispatchCast(val, castTy); | |
338 | } | |
339 | ||
340 | // Just pass through function and block pointers. | |
341 | if (originalTy->isBlockPointerType() || originalTy->isFunctionPointerType()) { | |
342 | assert(Loc::isLocType(castTy)); | |
343 | return val; | |
344 | } | |
345 | ||
346 | // Check for casts from array type to another type. | |
347 | if (originalTy->isArrayType()) { | |
348 | // We will always decay to a pointer. | |
349 | val = StateMgr.ArrayToPointer(cast<Loc>(val)); | |
350 | ||
351 | // Are we casting from an array to a pointer? If so just pass on | |
352 | // the decayed value. | |
353 | if (castTy->isPointerType() || castTy->isReferenceType()) | |
354 | return val; | |
355 | ||
356 | // Are we casting from an array to an integer? If so, cast the decayed | |
357 | // pointer value to an integer. | |
358 | assert(castTy->isIntegerType()); | |
359 | ||
360 | // FIXME: Keep these here for now in case we decide soon that we | |
361 | // need the original decayed type. | |
362 | // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); | |
363 | // QualType pointerTy = C.getPointerType(elemTy); | |
364 | return evalCastFromLoc(cast<Loc>(val), castTy); | |
365 | } | |
366 | ||
367 | // Check for casts from a region to a specific type. | |
368 | if (const MemRegion *R = val.getAsRegion()) { | |
369 | // Handle other casts of locations to integers. | |
370 | if (castTy->isIntegerType()) | |
371 | return evalCastFromLoc(loc::MemRegionVal(R), castTy); | |
372 | ||
373 | // FIXME: We should handle the case where we strip off view layers to get | |
374 | // to a desugared type. | |
375 | if (!Loc::isLocType(castTy)) { | |
376 | // FIXME: There can be gross cases where one casts the result of a function | |
377 | // (that returns a pointer) to some other value that happens to fit | |
378 | // within that pointer value. We currently have no good way to | |
379 | // model such operations. When this happens, the underlying operation | |
380 | // is that the caller is reasoning about bits. Conceptually we are | |
381 | // layering a "view" of a location on top of those bits. Perhaps | |
382 | // we need to be more lazy about mutual possible views, even on an | |
383 | // SVal? This may be necessary for bit-level reasoning as well. | |
384 | return UnknownVal(); | |
385 | } | |
386 | ||
387 | // We get a symbolic function pointer for a dereference of a function | |
388 | // pointer, but it is of function type. Example: | |
389 | ||
390 | // struct FPRec { | |
391 | // void (*my_func)(int * x); | |
392 | // }; | |
393 | // | |
394 | // int bar(int x); | |
395 | // | |
396 | // int f1_a(struct FPRec* foo) { | |
397 | // int x; | |
398 | // (*foo->my_func)(&x); | |
399 | // return bar(x)+1; // no-warning | |
400 | // } | |
401 | ||
402 | assert(Loc::isLocType(originalTy) || originalTy->isFunctionType() || | |
403 | originalTy->isBlockPointerType() || castTy->isReferenceType()); | |
404 | ||
405 | StoreManager &storeMgr = StateMgr.getStoreManager(); | |
406 | ||
407 | // Delegate to store manager to get the result of casting a region to a | |
408 | // different type. If the MemRegion* returned is NULL, this expression | |
409 | // Evaluates to UnknownVal. | |
410 | R = storeMgr.castRegion(R, castTy); | |
411 | return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); | |
412 | } | |
413 | ||
414 | return dispatchCast(val, castTy); | |
415 | } |