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