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