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 (const MemRegion *R = getAsRegion())
88    if (const SymbolicRegion *SymR =
89            IncludeBaseRegions ? R->getSymbolicBase()
90                               : dyn_cast<SymbolicRegion>(R->StripCasts()))
91      return SymR->getSymbol();
92
93  return nullptr;
94}
95
96/// Get the symbol in the SVal or its base region.
97SymbolRef SVal::getLocSymbolInBase() const {
98  Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>();
99
100  if (!X)
101    return nullptr;
102
103  const MemRegion *R = X->getRegion();
104
105  while (const auto *SR = dyn_cast<SubRegion>(R)) {
106    if (const auto *SymR = dyn_cast<SymbolicRegion>(SR))
107      return SymR->getSymbol();
108    else
109      R = SR->getSuperRegion();
110  }
111
112  return nullptr;
113}
114
115/// If this SVal wraps a symbol return that SymbolRef.
116/// Otherwise, return 0.
117///
118/// Casts are ignored during lookup.
119/// \param IncludeBaseRegions The boolean that controls whether the search
120/// should continue to the base regions if the region is not symbolic.
121SymbolRef SVal::getAsSymbol(bool IncludeBaseRegions) const {
122  // FIXME: should we consider SymbolRef wrapped in CodeTextRegion?
123  if (Optional<nonloc::SymbolVal> X = getAs<nonloc::SymbolVal>())
124    return X->getSymbol();
125
126  return getAsLocSymbol(IncludeBaseRegions);
127}
128
129const MemRegion *SVal::getAsRegion() const {
130  if (Optional<loc::MemRegionVal> X = getAs<loc::MemRegionVal>())
131    return X->getRegion();
132
133  if (Optional<nonloc::LocAsInteger> X = getAs<nonloc::LocAsInteger>())
134    return X->getLoc().getAsRegion();
135
136  return nullptr;
137}
138
139const MemRegion *loc::MemRegionVal::stripCasts(bool StripBaseCasts) const {
140  const MemRegion *R = getRegion();
141  return R ?  R->StripCasts(StripBaseCasts) : nullptr;
142}
143
144const void *nonloc::LazyCompoundVal::getStore() const {
145  return static_cast<const LazyCompoundValData*>(Data)->getStore();
146}
147
148const TypedValueRegion *nonloc::LazyCompoundVal::getRegion() const {
149  return static_cast<const LazyCompoundValData*>(Data)->getRegion();
150}
151
152bool nonloc::PointerToMember::isNullMemberPointer() const {
153  return getPTMData().isNull();
154}
155
156const NamedDecl *nonloc::PointerToMember::getDecl() const {
157  const auto PTMD = this->getPTMData();
158  if (PTMD.isNull())
159    return nullptr;
160
161  const NamedDecl *ND = nullptr;
162  if (PTMD.is<const NamedDecl *>())
163    ND = PTMD.get<const NamedDecl *>();
164  else
165    ND = PTMD.get<const PointerToMemberData *>()->getDeclaratorDecl();
166
167  return ND;
168}
169
170//===----------------------------------------------------------------------===//
171// Other Iterators.
172//===----------------------------------------------------------------------===//
173
174nonloc::CompoundVal::iterator nonloc::CompoundVal::begin() const {
175  return getValue()->begin();
176}
177
178nonloc::CompoundVal::iterator nonloc::CompoundVal::end() const {
179  return getValue()->end();
180}
181
182nonloc::PointerToMember::iterator nonloc::PointerToMember::begin() const {
183  const PTMDataType PTMD = getPTMData();
184  if (PTMD.is<const NamedDecl *>())
185    return {};
186  return PTMD.get<const PointerToMemberData *>()->begin();
187}
188
189nonloc::PointerToMember::iterator nonloc::PointerToMember::end() const {
190  const PTMDataType PTMD = getPTMData();
191  if (PTMD.is<const NamedDecl *>())
192    return {};
193  return PTMD.get<const PointerToMemberData *>()->end();
194}
195
196//===----------------------------------------------------------------------===//
197// Useful predicates.
198//===----------------------------------------------------------------------===//
199
200bool SVal::isConstant() const {
201  return getAs<nonloc::ConcreteInt>() || getAs<loc::ConcreteInt>();
202}
203
204bool SVal::isConstant(int I) const {
205  if (Optional<loc::ConcreteInt> LV = getAs<loc::ConcreteInt>())
206    return LV->getValue() == I;
207  if (Optional<nonloc::ConcreteInt> NV = getAs<nonloc::ConcreteInt>())
208    return NV->getValue() == I;
209  return false;
210}
211
212bool SVal::isZeroConstant() const {
213  return isConstant(0);
214}
215
216//===----------------------------------------------------------------------===//
217// Transfer function dispatch for Non-Locs.
218//===----------------------------------------------------------------------===//
219
220SVal nonloc::ConcreteInt::evalBinOp(SValBuilder &svalBuilder,
221                                    BinaryOperator::Opcode Op,
222                                    const nonloc::ConcreteInt& R) const {
223  const llvm::APSInt* X =
224    svalBuilder.getBasicValueFactory().evalAPSInt(Op, getValue(), R.getValue());
225
226  if (X)
227    return nonloc::ConcreteInt(*X);
228  else
229    return UndefinedVal();
230}
231
232nonloc::ConcreteInt
233nonloc::ConcreteInt::evalComplement(SValBuilder &svalBuilder) const {
234  return svalBuilder.makeIntVal(~getValue());
235}
236
237nonloc::ConcreteInt
238nonloc::ConcreteInt::evalMinus(SValBuilder &svalBuilder) const {
239  return svalBuilder.makeIntVal(-getValue());
240}
241
242//===----------------------------------------------------------------------===//
243// Transfer function dispatch for Locs.
244//===----------------------------------------------------------------------===//
245
246SVal loc::ConcreteInt::evalBinOp(BasicValueFactory& BasicVals,
247                                 BinaryOperator::Opcode Op,
248                                 const loc::ConcreteInt& R) const {
249  assert(BinaryOperator::isComparisonOp(Op) || Op == BO_Sub);
250
251  const llvm::APSInt *X = BasicVals.evalAPSInt(Op, getValue(), R.getValue());
252
253  if (X)
254    return nonloc::ConcreteInt(*X);
255  else
256    return UndefinedVal();
257}
258
259//===----------------------------------------------------------------------===//
260// Pretty-Printing.
261//===----------------------------------------------------------------------===//
262
263LLVM_DUMP_METHOD void SVal::dump() const { dumpToStream(llvm::errs()); }
264
265void SVal::printJson(raw_ostream &Out, bool AddQuotes) const {
266  std::string Buf;
267  llvm::raw_string_ostream TempOut(Buf);
268
269  dumpToStream(TempOut);
270
271  Out << JsonFormat(TempOut.str(), AddQuotes);
272}
273
274void SVal::dumpToStream(raw_ostream &os) const {
275  switch (getBaseKind()) {
276    case UnknownValKind:
277      os << "Unknown";
278      break;
279    case NonLocKind:
280      castAs<NonLoc>().dumpToStream(os);
281      break;
282    case LocKind:
283      castAs<Loc>().dumpToStream(os);
284      break;
285    case UndefinedValKind:
286      os << "Undefined";
287      break;
288  }
289}
290
291void NonLoc::dumpToStream(raw_ostream &os) const {
292  switch (getSubKind()) {
293    case nonloc::ConcreteIntKind: {
294      const auto &Value = castAs<nonloc::ConcreteInt>().getValue();
295      os << Value << ' ' << (Value.isSigned() ? 'S' : 'U')
296         << Value.getBitWidth() << 'b';
297      break;
298    }
299    case nonloc::SymbolValKind:
300      os << castAs<nonloc::SymbolVal>().getSymbol();
301      break;
302
303    case nonloc::LocAsIntegerKind: {
304      const nonloc::LocAsInteger& C = castAs<nonloc::LocAsInteger>();
305      os << C.getLoc() << " [as " << C.getNumBits() << " bit integer]";
306      break;
307    }
308    case nonloc::CompoundValKind: {
309      const nonloc::CompoundVal& C = castAs<nonloc::CompoundVal>();
310      os << "compoundVal{";
311      bool first = true;
312      for (const auto &I : C) {
313        if (first) {
314          os << ' '; first = false;
315        }
316        else
317          os << ", ";
318
319        I.dumpToStream(os);
320      }
321      os << "}";
322      break;
323    }
324    case nonloc::LazyCompoundValKind: {
325      const nonloc::LazyCompoundVal &C = castAs<nonloc::LazyCompoundVal>();
326      os << "lazyCompoundVal{" << const_cast<void *>(C.getStore())
327         << ',' << C.getRegion()
328         << '}';
329      break;
330    }
331    case nonloc::PointerToMemberKind: {
332      os << "pointerToMember{";
333      const nonloc::PointerToMember &CastRes =
334          castAs<nonloc::PointerToMember>();
335      if (CastRes.getDecl())
336        os << "|" << CastRes.getDecl()->getQualifiedNameAsString() << "|";
337      bool first = true;
338      for (const auto &I : CastRes) {
339        if (first) {
340          os << ' '; first = false;
341        }
342        else
343          os << ", ";
344
345        os << (*I).getType().getAsString();
346      }
347
348      os << '}';
349      break;
350    }
351    default:
352      assert(false && "Pretty-printed not implemented for this NonLoc.");
353      break;
354  }
355}
356
357void Loc::dumpToStream(raw_ostream &os) const {
358  switch (getSubKind()) {
359    case loc::ConcreteIntKind:
360      os << castAs<loc::ConcreteInt>().getValue().getZExtValue() << " (Loc)";
361      break;
362    case loc::GotoLabelKind:
363      os << "&&" << castAs<loc::GotoLabel>().getLabel()->getName();
364      break;
365    case loc::MemRegionValKind:
366      os << '&' << castAs<loc::MemRegionVal>().getRegion()->getString();
367      break;
368    default:
369      llvm_unreachable("Pretty-printing not implemented for this Loc.");
370  }
371}
372