1 //= RValues.cpp - Abstract RValues for Path-Sens. Value Tracking -*- 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 SVal, Loc, and NonLoc, classes that represent
11 //  abstract r-values for use with path-sensitive value tracking.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
16 #include "clang/AST/ExprObjC.h"
17 #include "clang/Basic/IdentifierTable.h"
18 #include "llvm/Support/raw_ostream.h"
19 using namespace clang;
20 using namespace ento;
21 using llvm::APSInt;
22 
23 //===----------------------------------------------------------------------===//
24 // Symbol iteration within an SVal.
25 //===----------------------------------------------------------------------===//
26 
27 
28 //===----------------------------------------------------------------------===//
29 // Utility methods.
30 //===----------------------------------------------------------------------===//
31 
32 bool SVal::hasConjuredSymbol() const {
33   if (const nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(this)) {
34     SymbolRef sym = SV->getSymbol();
35     if (isa<SymbolConjured>(sym))
36       return true;
37   }
38 
39   if (const loc::MemRegionVal *RV = dyn_cast<loc::MemRegionVal>(this)) {
40     const MemRegion *R = RV->getRegion();
41     if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
42       SymbolRef sym = SR->getSymbol();
43       if (isa<SymbolConjured>(sym))
44         return true;
45     }
46   }
47 
48   return false;
49 }
50 
51 const FunctionDecl *SVal::getAsFunctionDecl() const {
52   if (const loc::MemRegionVal* X = dyn_cast<loc::MemRegionVal>(this)) {
53     const MemRegion* R = X->getRegion();
54     if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>())
55       if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(CTR->getDecl()))
56         return FD;
57   }
58 
59   return 0;
60 }
61 
62 /// \brief If this SVal is a location (subclasses Loc) and wraps a symbol,
63 /// return that SymbolRef.  Otherwise return 0.
64 ///
65 /// Implicit casts (ex: void* -> char*) can turn Symbolic region into Element
66 /// region. If that is the case, gets the underlining region.
67 SymbolRef SVal::getAsLocSymbol() const {
68   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
69   if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this))
70     return X->getLoc().getAsLocSymbol();
71 
72   if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this)) {
73     const MemRegion *R = X->stripCasts();
74     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
75       return SymR->getSymbol();
76   }
77   return 0;
78 }
79 
80 /// Get the symbol in the SVal or its base region.
81 SymbolRef SVal::getLocSymbolInBase() const {
82   const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this);
83 
84   if (!X)
85     return 0;
86 
87   const MemRegion *R = X->getRegion();
88 
89   while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
90     if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
91       return SymR->getSymbol();
92     else
93       R = SR->getSuperRegion();
94   }
95 
96   return 0;
97 }
98 
99 // TODO: The next 3 functions have to be simplified.
100 
101 /// \brief If this SVal wraps a symbol return that SymbolRef.
102 ///  Otherwise return 0.
103 SymbolRef SVal::getAsSymbol() const {
104   // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
105   if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
106     return X->getSymbol();
107 
108   return getAsLocSymbol();
109 }
110 
111 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
112 ///  return that expression.  Otherwise return NULL.
113 const SymExpr *SVal::getAsSymbolicExpression() const {
114   if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
115     return X->getSymbol();
116 
117   return getAsSymbol();
118 }
119 
120 const SymExpr* SVal::getAsSymExpr() const {
121   const SymExpr* Sym = getAsSymbol();
122   if (!Sym)
123     Sym = getAsSymbolicExpression();
124   return Sym;
125 }
126 
127 const MemRegion *SVal::getAsRegion() const {
128   if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this))
129     return X->getRegion();
130 
131   if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this)) {
132     return X->getLoc().getAsRegion();
133   }
134 
135   return 0;
136 }
137 
138 const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
139   const MemRegion *R = getRegion();
140   return R ?  R->StripCasts(StripBaseCasts) : NULL;
141 }
142 
143 const void *nonloc::LazyCompoundVal::getStore() const {
144   return static_cast<const LazyCompoundValData*>(Data)->getStore();
145 }
146 
147 const TypedRegion *nonloc::LazyCompoundVal::getRegion() const {
148   return static_cast<const LazyCompoundValData*>(Data)->getRegion();
149 }
150 
151 //===----------------------------------------------------------------------===//
152 // Other Iterators.
153 //===----------------------------------------------------------------------===//
154 
155 nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
156   return getValue()->begin();
157 }
158 
159 nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
160   return getValue()->end();
161 }
162 
163 //===----------------------------------------------------------------------===//
164 // Useful predicates.
165 //===----------------------------------------------------------------------===//
166 
167 bool SVal::isConstant() const {
168   return isa<nonloc::ConcreteInt>(this) || isa<loc::ConcreteInt>(this);
169 }
170 
171 bool SVal::isConstant(int I) const {
172   if (isa<loc::ConcreteInt>(*this))
173     return cast<loc::ConcreteInt>(*this).getValue() == I;
174   else if (isa<nonloc::ConcreteInt>(*this))
175     return cast<nonloc::ConcreteInt>(*this).getValue() == I;
176   else
177     return false;
178 }
179 
180 bool SVal::isZeroConstant() const {
181   return isConstant(0);
182 }
183 
184 
185 //===----------------------------------------------------------------------===//
186 // Transfer function dispatch for Non-Locs.
187 //===----------------------------------------------------------------------===//
188 
189 SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
190                                     BinaryOperator::Opcode Op,
191                                     const nonloc::ConcreteInt& R) const {
192   const llvm::APSInt* X =
193     svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
194 
195   if (X)
196     return nonloc::ConcreteInt(*X);
197   else
198     return UndefinedVal();
199 }
200 
201 nonloc::ConcreteInt
202 nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
203   return svalBuilder.makeIntVal(~getValue());
204 }
205 
206 nonloc::ConcreteInt
207 nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
208   return svalBuilder.makeIntVal(-getValue());
209 }
210 
211 //===----------------------------------------------------------------------===//
212 // Transfer function dispatch for Locs.
213 //===----------------------------------------------------------------------===//
214 
215 SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
216                                  BinaryOperator::Opcode Op,
217                                  const loc::ConcreteInt& R) const {
218 
219   assert (Op == BO_Add || Op == BO_Sub ||
220           (Op >= BO_LT && Op <= BO_NE));
221 
222   const llvm::APSInt* X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
223 
224   if (X)
225     return loc::ConcreteInt(*X);
226   else
227     return UndefinedVal();
228 }
229 
230 //===----------------------------------------------------------------------===//
231 // Pretty-Printing.
232 //===----------------------------------------------------------------------===//
233 
234 void SVal::dump() const { dumpToStream(llvm::errs()); }
235 
236 void SVal::dumpToStream(raw_ostream &os) const {
237   switch (getBaseKind()) {
238     case UnknownKind:
239       os << "Unknown";
240       break;
241     case NonLocKind:
242       cast<NonLoc>(this)->dumpToStream(os);
243       break;
244     case LocKind:
245       cast<Loc>(this)->dumpToStream(os);
246       break;
247     case UndefinedKind:
248       os << "Undefined";
249       break;
250   }
251 }
252 
253 void NonLoc::dumpToStream(raw_ostream &os) const {
254   switch (getSubKind()) {
255     case nonloc::ConcreteIntKind: {
256       const nonloc::ConcreteInt& C = *cast<nonloc::ConcreteInt>(this);
257       if (C.getValue().isUnsigned())
258         os << C.getValue().getZExtValue();
259       else
260         os << C.getValue().getSExtValue();
261       os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S')
262          << C.getValue().getBitWidth() << 'b';
263       break;
264     }
265     case nonloc::SymbolValKind: {
266       os << cast<nonloc::SymbolVal>(this)->getSymbol();
267       break;
268     }
269     case nonloc::LocAsIntegerKind: {
270       const nonloc::LocAsInteger& C = *cast<nonloc::LocAsInteger>(this);
271       os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
272       break;
273     }
274     case nonloc::CompoundValKind: {
275       const nonloc::CompoundVal& C = *cast<nonloc::CompoundVal>(this);
276       os << "compoundVal{";
277       bool first = true;
278       for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
279         if (first) {
280           os << ' '; first = false;
281         }
282         else
283           os << ", ";
284 
285         (*I).dumpToStream(os);
286       }
287       os << "}";
288       break;
289     }
290     case nonloc::LazyCompoundValKind: {
291       const nonloc::LazyCompoundVal &C = *cast<nonloc::LazyCompoundVal>(this);
292       os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
293          << ',' << C.getRegion()
294          << '}';
295       break;
296     }
297     default:
298       assert (false && "Pretty-printed not implemented for this NonLoc.");
299       break;
300   }
301 }
302 
303 void Loc::dumpToStream(raw_ostream &os) const {
304   switch (getSubKind()) {
305     case loc::ConcreteIntKind:
306       os << cast<loc::ConcreteInt>(this)->getValue().getZExtValue() << " (Loc)";
307       break;
308     case loc::GotoLabelKind:
309       os << "&&" << cast<loc::GotoLabel>(this)->getLabel()->getName();
310       break;
311     case loc::MemRegionKind:
312       os << '&' << cast<loc::MemRegionVal>(this)->getRegion()->getString();
313       break;
314     default:
315       llvm_unreachable("Pretty-printing not implemented for this Loc.");
316   }
317 }
318