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