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