SVals.cpp revision 5344baa704f42b22d9df25c24ffbbf6b4716603b 
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"
18using namespace clang;
19using namespace ento;
20using llvm::APSInt;
21
22//===----------------------------------------------------------------------===//
23// Symbol iteration within an SVal.
24//===----------------------------------------------------------------------===//
25
26
27//===----------------------------------------------------------------------===//
28// Utility methods.
29//===----------------------------------------------------------------------===//
30
31bool SVal::hasConjuredSymbol() const {
32  if (const nonloc::SymbolVal* SV = dyn_cast<nonloc::SymbolVal>(this)) {
33    SymbolRef sym = SV->getSymbol();
34    if (isa<SymbolConjured>(sym))
35      return true;
36  }
37
38  if (const loc::MemRegionVal *RV = dyn_cast<loc::MemRegionVal>(this)) {
39    const MemRegion *R = RV->getRegion();
40    if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R)) {
41      SymbolRef sym = SR->getSymbol();
42      if (isa<SymbolConjured>(sym))
43        return true;
44    }
45  }
46
47  return false;
48}
49
50const FunctionDecl *SVal::getAsFunctionDecl() const {
51  if (const loc::MemRegionVal* X = dyn_cast<loc::MemRegionVal>(this)) {
52    const MemRegion* R = X->getRegion();
53    if (const FunctionTextRegion *CTR = R->getAs<FunctionTextRegion>())
54      return CTR->getDecl();
55  }
56
57  return 0;
58}
59
60// If this SVal is a location (subclasses Loc) and wraps a symbol, return
61// that SymbolRef.  Otherwise return 0.
62// FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
63SymbolRef SVal::getAsLocSymbol() const {
64  if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this))
65    return X->getLoc().getAsLocSymbol();
66
67  if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this)) {
68    const MemRegion *R = X->stripCasts();
69    if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(R))
70      return SymR->getSymbol();
71  }
72  return 0;
73}
74
75/// Get the symbol in the SVal or its base region.
76SymbolRef SVal::getLocSymbolInBase() const {
77  const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this);
78
79  if (!X)
80    return 0;
81
82  const MemRegion *R = X->getRegion();
83
84  while (const SubRegion *SR = dyn_cast<SubRegion>(R)) {
85    if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SR))
86      return SymR->getSymbol();
87    else
88      R = SR->getSuperRegion();
89  }
90
91  return 0;
92}
93
94/// getAsSymbol - If this Sval wraps a symbol return that SymbolRef.
95///  Otherwise return 0.
96// FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
97SymbolRef SVal::getAsSymbol() const {
98  if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
99    return X->getSymbol();
100
101  if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
102    if (SymbolRef Y = X->getSymbol())
103      return Y;
104
105  return getAsLocSymbol();
106}
107
108/// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
109///  return that expression.  Otherwise return NULL.
110const SymExpr *SVal::getAsSymbolicExpression() const {
111  if (const nonloc::SymbolVal *X = dyn_cast<nonloc::SymbolVal>(this))
112    return X->getSymbol();
113
114  return getAsSymbol();
115}
116
117const SymExpr* SVal::getAsSymExpr() const {
118  const SymExpr* Sym = getAsSymbol();
119  if (!Sym)
120    Sym = getAsSymbolicExpression();
121  return Sym;
122}
123
124const MemRegion *SVal::getAsRegion() const {
125  if (const loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(this))
126    return X->getRegion();
127
128  if (const nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(this)) {
129    return X->getLoc().getAsRegion();
130  }
131
132  return 0;
133}
134
135const MemRegion *loc::MemRegionVal::stripCasts() const {
136  const MemRegion *R = getRegion();
137  return R ?  R->StripCasts() : NULL;
138}
139
140bool SVal::symbol_iterator::operator==(const symbol_iterator &X) const {
141  return itr == X.itr;
142}
143
144bool SVal::symbol_iterator::operator!=(const symbol_iterator &X) const {
145  return itr != X.itr;
146}
147
148SVal::symbol_iterator::symbol_iterator(const SymExpr *SE) {
149  itr.push_back(SE);
150  while (!isa<SymbolData>(itr.back())) expand();
151}
152
153SVal::symbol_iterator &SVal::symbol_iterator::operator++() {
154  assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
155  assert(isa<SymbolData>(itr.back()));
156  itr.pop_back();
157  if (!itr.empty())
158    while (!isa<SymbolData>(itr.back())) expand();
159  return *this;
160}
161
162SymbolRef SVal::symbol_iterator::operator*() {
163  assert(!itr.empty() && "attempting to dereference an 'end' iterator");
164  return cast<SymbolData>(itr.back());
165}
166
167void SVal::symbol_iterator::expand() {
168  const SymExpr *SE = itr.back();
169  itr.pop_back();
170
171  if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
172    itr.push_back(SIE->getLHS());
173    return;
174  }
175  else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
176    itr.push_back(SSE->getLHS());
177    itr.push_back(SSE->getRHS());
178    return;
179  }
180
181  llvm_unreachable("unhandled expansion case");
182}
183
184const void *nonloc::LazyCompoundVal::getStore() const {
185  return static_cast<const LazyCompoundValData*>(Data)->getStore();
186}
187
188const TypedRegion *nonloc::LazyCompoundVal::getRegion() const {
189  return static_cast<const LazyCompoundValData*>(Data)->getRegion();
190}
191
192//===----------------------------------------------------------------------===//
193// Other Iterators.
194//===----------------------------------------------------------------------===//
195
196nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
197  return getValue()->begin();
198}
199
200nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
201  return getValue()->end();
202}
203
204//===----------------------------------------------------------------------===//
205// Useful predicates.
206//===----------------------------------------------------------------------===//
207
208bool SVal::isConstant() const {
209  return isa<nonloc::ConcreteInt>(this) || isa<loc::ConcreteInt>(this);
210}
211
212bool SVal::isConstant(int I) const {
213  if (isa<loc::ConcreteInt>(*this))
214    return cast<loc::ConcreteInt>(*this).getValue() == I;
215  else if (isa<nonloc::ConcreteInt>(*this))
216    return cast<nonloc::ConcreteInt>(*this).getValue() == I;
217  else
218    return false;
219}
220
221bool SVal::isZeroConstant() const {
222  return isConstant(0);
223}
224
225
226//===----------------------------------------------------------------------===//
227// Transfer function dispatch for Non-Locs.
228//===----------------------------------------------------------------------===//
229
230SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
231                                    BinaryOperator::Opcode Op,
232                                    const nonloc::ConcreteInt& R) const {
233  const llvm::APSInt* X =
234    svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
235
236  if (X)
237    return nonloc::ConcreteInt(*X);
238  else
239    return UndefinedVal();
240}
241
242nonloc::ConcreteInt
243nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
244  return svalBuilder.makeIntVal(~getValue());
245}
246
247nonloc::ConcreteInt
248nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
249  return svalBuilder.makeIntVal(-getValue());
250}
251
252//===----------------------------------------------------------------------===//
253// Transfer function dispatch for Locs.
254//===----------------------------------------------------------------------===//
255
256SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
257                                 BinaryOperator::Opcode Op,
258                                 const loc::ConcreteInt& R) const {
259
260  assert (Op == BO_Add || Op == BO_Sub ||
261          (Op >= BO_LT && Op <= BO_NE));
262
263  const llvm::APSInt* X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
264
265  if (X)
266    return loc::ConcreteInt(*X);
267  else
268    return UndefinedVal();
269}
270
271//===----------------------------------------------------------------------===//
272// Pretty-Printing.
273//===----------------------------------------------------------------------===//
274
275void SVal::dump() const { dumpToStream(llvm::errs()); }
276
277void SVal::dumpToStream(raw_ostream &os) const {
278  switch (getBaseKind()) {
279    case UnknownKind:
280      os << "Unknown";
281      break;
282    case NonLocKind:
283      cast<NonLoc>(this)->dumpToStream(os);
284      break;
285    case LocKind:
286      cast<Loc>(this)->dumpToStream(os);
287      break;
288    case UndefinedKind:
289      os << "Undefined";
290      break;
291    default:
292      assert (false && "Invalid SVal.");
293  }
294}
295
296void NonLoc::dumpToStream(raw_ostream &os) const {
297  switch (getSubKind()) {
298    case nonloc::ConcreteIntKind: {
299      const nonloc::ConcreteInt& C = *cast<nonloc::ConcreteInt>(this);
300      if (C.getValue().isUnsigned())
301        os << C.getValue().getZExtValue();
302      else
303        os << C.getValue().getSExtValue();
304      os << ' ' << (C.getValue().isUnsigned() ? 'U' : 'S')
305         << C.getValue().getBitWidth() << 'b';
306      break;
307    }
308    case nonloc::SymbolValKind: {
309      os << cast<nonloc::SymbolVal>(this)->getSymbol();
310      break;
311    }
312    case nonloc::LocAsIntegerKind: {
313      const nonloc::LocAsInteger& C = *cast<nonloc::LocAsInteger>(this);
314      os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
315      break;
316    }
317    case nonloc::CompoundValKind: {
318      const nonloc::CompoundVal& C = *cast<nonloc::CompoundVal>(this);
319      os << "compoundVal{";
320      bool first = true;
321      for (nonloc::CompoundVal::iterator I=C.begin(), E=C.end(); I!=E; ++I) {
322        if (first) {
323          os << ' '; first = false;
324        }
325        else
326          os << ", ";
327
328        (*I).dumpToStream(os);
329      }
330      os << "}";
331      break;
332    }
333    case nonloc::LazyCompoundValKind: {
334      const nonloc::LazyCompoundVal &C = *cast<nonloc::LazyCompoundVal>(this);
335      os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
336         << ',' << C.getRegion()
337         << '}';
338      break;
339    }
340    default:
341      assert (false && "Pretty-printed not implemented for this NonLoc.");
342      break;
343  }
344}
345
346void Loc::dumpToStream(raw_ostream &os) const {
347  switch (getSubKind()) {
348    case loc::ConcreteIntKind:
349      os << cast<loc::ConcreteInt>(this)->getValue().getZExtValue() << " (Loc)";
350      break;
351    case loc::GotoLabelKind:
352      os << "&&" << cast<loc::GotoLabel>(this)->getLabel()->getName();
353      break;
354    case loc::MemRegionKind:
355      os << '&' << cast<loc::MemRegionVal>(this)->getRegion()->getString();
356      break;
357    case loc::ObjCPropRefKind: {
358      const ObjCPropertyRefExpr *E = cast<loc::ObjCPropRef>(this)->getPropRefExpr();
359      os << "objc-prop{";
360      if (E->isSuperReceiver())
361        os << "super.";
362      else if (E->getBase())
363        os << "<base>.";
364
365      if (E->isImplicitProperty())
366        os << E->getImplicitPropertyGetter()->getSelector().getAsString();
367      else
368        os << E->getExplicitProperty()->getName();
369
370      os << "}";
371      break;
372    }
373    default:
374      llvm_unreachable("Pretty-printing not implemented for this Loc.");
375  }
376}
377