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