1//===-- SVals.cpp - Abstract RValues for Path-Sens. Value Tracking --------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9//  This file defines SVal, Loc, and NonLoc, classes that represent
10//  abstract r-values for use with path-sensitive value tracking.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
15#include "clang/AST/Decl.h"
16#include "clang/AST/DeclCXX.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/Type.h"
19#include "clang/Basic/JsonSupport.h"
20#include "clang/Basic/LLVM.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
25#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
26#include "llvm/ADT/Optional.h"
27#include "llvm/Support/Casting.h"
28#include "llvm/Support/Compiler.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
31#include <cassert>
32
33using namespace clang;
34using namespace ento;
35
36//===----------------------------------------------------------------------===//
37// Symbol iteration within an SVal.
38//===----------------------------------------------------------------------===//
39
40//===----------------------------------------------------------------------===//
41// Utility methods.
42//===----------------------------------------------------------------------===//
43
44bool SVal::hasConjuredSymbol() const {
45  if (Optional<nonloc::SymbolVal> SV = getAs<nonloc::SymbolVal>()) {
46    SymbolRef sym = SV->getSymbol();
47    if (isa<SymbolConjured>(sym))
48      return true;
49  }
50
51  if (Optional<loc::MemRegionVal> RV = getAs<loc::MemRegionVal>()) {
52    const MemRegion *R = RV->getRegion();
53    if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
54      SymbolRef sym = SR->getSymbol();
55      if (isa<SymbolConjured>(sym))
56        return true;
57    }
58  }
59
60  return false;
61}
62
63const FunctionDecl *SVal::getAsFunctionDecl() const {
64  if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
65    const MemRegion* R = X->getRegion();
66    if (const FunctionCodeRegion *CTR = R->getAs<FunctionCodeRegion>())
67      if (const auto *FD = dyn_cast<FunctionDecl>(CTR->getDecl()))
68        return FD;
69  }
70
71  if (auto X = getAs<nonloc::PointerToMember>()) {
72    if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(X->getDecl()))
73      return MD;
74  }
75  return nullptr;
76}
77
78/// If this SVal is a location (subclasses Loc) and wraps a symbol,
79/// return that SymbolRef.  Otherwise return 0.
80///
81/// Implicit casts (ex: void* -> char*) can turn Symbolic region into Element
82/// region. If that is the case, gets the underlining region.
83/// When IncludeBaseRegions is set to true and the SubRegion is non-symbolic,
84/// the first symbolic parent region is returned.
85SymbolRef SVal::getAsLocSymbol(bool IncludeBaseRegions) const {
86  // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
87  if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
88    return X->getLoc().getAsLocSymbol(IncludeBaseRegions);
89
90  if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>()) {
91    const MemRegion *R = X->getRegion();
92    if (const SymbolicRegion *SymR = IncludeBaseRegions ?
93                                      R->getSymbolicBase() :
94                                      dyn_cast<SymbolicRegion>(R->StripCasts()))
95      return SymR->getSymbol();
96  }
97  return nullptr;
98}
99
100/// Get the symbol in the SVal or its base region.
101SymbolRef SVal::getLocSymbolInBase() const {
102  Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>();
103
104  if (!X)
105    return nullptr;
106
107  const MemRegion *R = X->getRegion();
108
109  while (const auto *SR = dyn_cast<SubRegion>(R)) {
110    if (const auto *SymR = dyn_cast<SymbolicRegion>(SR))
111      return SymR->getSymbol();
112    else
113      R = SR->getSuperRegion();
114  }
115
116  return nullptr;
117}
118
119// TODO: The next 3 functions have to be simplified.
120
121/// If this SVal wraps a symbol return that SymbolRef.
122/// Otherwise, return 0.
123///
124/// Casts are ignored during lookup.
125/// \param IncludeBaseRegions The boolean that controls whether the search
126/// should continue to the base regions if the region is not symbolic.
127SymbolRef SVal::getAsSymbol(bool IncludeBaseRegions) const {
128  // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
129  if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
130    return X->getSymbol();
131
132  return getAsLocSymbol(IncludeBaseRegions);
133}
134
135/// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
136///  return that expression.  Otherwise return NULL.
137const SymExpr *SVal::getAsSymbolicExpression() const {
138  if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
139    return X->getSymbol();
140
141  return getAsSymbol();
142}
143
144const SymExpr* SVal::getAsSymExpr() const {
145  const SymExpr* Sym = getAsSymbol();
146  if (!Sym)
147    Sym = getAsSymbolicExpression();
148  return Sym;
149}
150
151const MemRegion *SVal::getAsRegion() const {
152  if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
153    return X->getRegion();
154
155  if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
156    return X->getLoc().getAsRegion();
157
158  return nullptr;
159}
160
161const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
162  const MemRegion *R = getRegion();
163  return R ?  R->StripCasts(StripBaseCasts) : nullptr;
164}
165
166const void *nonloc::LazyCompoundVal::getStore() const {
167  return static_cast<const LazyCompoundValData*>(Data)->getStore();
168}
169
170const TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const {
171  return static_cast<const LazyCompoundValData*>(Data)->getRegion();
172}
173
174bool nonloc::PointerToMember::isNullMemberPointer() const {
175  return getPTMData().isNull();
176}
177
178const DeclaratorDecl *nonloc::PointerToMember::getDecl() const {
179  const auto PTMD = this->getPTMData();
180  if (PTMD.isNull())
181    return nullptr;
182
183  const DeclaratorDecl *DD = nullptr;
184  if (PTMD.is<const DeclaratorDecl *>())
185    DD = PTMD.get<const DeclaratorDecl *>();
186  else
187    DD = PTMD.get<const PointerToMemberData *>()->getDeclaratorDecl();
188
189  return DD;
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
204nonloc::PointerToMember::iterator nonloc::PointerToMember::begin() const {
205  const PTMDataType PTMD = getPTMData();
206  if (PTMD.is<const DeclaratorDecl *>())
207    return {};
208  return PTMD.get<const PointerToMemberData *>()->begin();
209}
210
211nonloc::PointerToMember::iterator nonloc::PointerToMember::end() const {
212  const PTMDataType PTMD = getPTMData();
213  if (PTMD.is<const DeclaratorDecl *>())
214    return {};
215  return PTMD.get<const PointerToMemberData *>()->end();
216}
217
218//===----------------------------------------------------------------------===//
219// Useful predicates.
220//===----------------------------------------------------------------------===//
221
222bool SVal::isConstant() const {
223  return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>();
224}
225
226bool SVal::isConstant(int I) const {
227  if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>())
228    return LV->getValue() == I;
229  if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>())
230    return NV->getValue() == I;
231  return false;
232}
233
234bool SVal::isZeroConstant() const {
235  return isConstant(0);
236}
237
238//===----------------------------------------------------------------------===//
239// Transfer function dispatch for Non-Locs.
240//===----------------------------------------------------------------------===//
241
242SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
243                                    BinaryOperator::Opcode Op,
244                                    const nonloc::ConcreteInt& R) const {
245  const llvm::APSInt* X =
246    svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
247
248  if (X)
249    return nonloc::ConcreteInt(*X);
250  else
251    return UndefinedVal();
252}
253
254nonloc::ConcreteInt
255nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
256  return svalBuilder.makeIntVal(~getValue());
257}
258
259nonloc::ConcreteInt
260nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
261  return svalBuilder.makeIntVal(-getValue());
262}
263
264//===----------------------------------------------------------------------===//
265// Transfer function dispatch for Locs.
266//===----------------------------------------------------------------------===//
267
268SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
269                                 BinaryOperator::Opcode Op,
270                                 const loc::ConcreteInt& R) const {
271  assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub);
272
273  const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
274
275  if (X)
276    return nonloc::ConcreteInt(*X);
277  else
278    return UndefinedVal();
279}
280
281//===----------------------------------------------------------------------===//
282// Pretty-Printing.
283//===----------------------------------------------------------------------===//
284
285LLVM_DUMP_METHOD void SVal::dump() const { dumpToStream(llvm::errs()); }
286
287void SVal::printJson(raw_ostream &Out, bool AddQuotes) const {
288  std::string Buf;
289  llvm::raw_string_ostream TempOut(Buf);
290
291  dumpToStream(TempOut);
292
293  Out << JsonFormat(TempOut.str(), AddQuotes);
294}
295
296void SVal::dumpToStream(raw_ostream &os) const {
297  switch (getBaseKind()) {
298    case UnknownValKind:
299      os << "Unknown";
300      break;
301    case NonLocKind:
302      castAs<NonLoc>().dumpToStream(os);
303      break;
304    case LocKind:
305      castAs<Loc>().dumpToStream(os);
306      break;
307    case UndefinedValKind:
308      os << "Undefined";
309      break;
310  }
311}
312
313void NonLoc::dumpToStream(raw_ostream &os) const {
314  switch (getSubKind()) {
315    case nonloc::ConcreteIntKind: {
316      const auto &Value = castAs<nonloc::ConcreteInt>().getValue();
317      os << Value << ' ' << (Value.isSigned() ? 'S' : 'U')
318         << Value.getBitWidth() << 'b';
319      break;
320    }
321    case nonloc::SymbolValKind:
322      os << castAs<nonloc::SymbolVal>().getSymbol();
323      break;
324
325    case nonloc::LocAsIntegerKind: {
326      const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>();
327      os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
328      break;
329    }
330    case nonloc::CompoundValKind: {
331      const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>();
332      os << "compoundVal{";
333      bool first = true;
334      for (const auto &I : C) {
335        if (first) {
336          os << ' '; first = false;
337        }
338        else
339          os << ", ";
340
341        I.dumpToStream(os);
342      }
343      os << "}";
344      break;
345    }
346    case nonloc::LazyCompoundValKind: {
347      const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>();
348      os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
349         << ',' << C.getRegion()
350         << '}';
351      break;
352    }
353    case nonloc::PointerToMemberKind: {
354      os << "pointerToMember{";
355      const nonloc::PointerToMember &CastRes =
356          castAs<nonloc::PointerToMember>();
357      if (CastRes.getDecl())
358        os << "|" << CastRes.getDecl()->getQualifiedNameAsString() << "|";
359      bool first = true;
360      for (const auto &I : CastRes) {
361        if (first) {
362          os << ' '; first = false;
363        }
364        else
365          os << ", ";
366
367        os << (*I).getType().getAsString();
368      }
369
370      os << '}';
371      break;
372    }
373    default:
374      assert(false && "Pretty-printed not implemented for this NonLoc.");
375      break;
376  }
377}
378
379void Loc::dumpToStream(raw_ostream &os) const {
380  switch (getSubKind()) {
381    case loc::ConcreteIntKind:
382      os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)";
383      break;
384    case loc::GotoLabelKind:
385      os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName();
386      break;
387    case loc::MemRegionValKind:
388      os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString();
389      break;
390    default:
391      llvm_unreachable("Pretty-printing not implemented for this Loc.");
392  }
393}
394