1 | //===- SVals.h - Abstract Values for Static Analysis ------------*- C++ -*-===// |
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 | #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H |
15 | #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H |
16 | |
17 | #include "clang/AST/Expr.h" |
18 | #include "clang/AST/Type.h" |
19 | #include "clang/Basic/LLVM.h" |
20 | #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" |
21 | #include "llvm/ADT/APSInt.h" |
22 | #include "llvm/ADT/FoldingSet.h" |
23 | #include "llvm/ADT/ImmutableList.h" |
24 | #include "llvm/ADT/PointerUnion.h" |
25 | #include "llvm/ADT/STLForwardCompat.h" |
26 | #include "llvm/ADT/iterator_range.h" |
27 | #include "llvm/Support/Casting.h" |
28 | #include <cassert> |
29 | #include <cstdint> |
30 | #include <optional> |
31 | #include <utility> |
32 | |
33 | //==------------------------------------------------------------------------==// |
34 | // Base SVal types. |
35 | //==------------------------------------------------------------------------==// |
36 | |
37 | namespace clang { |
38 | |
39 | class CXXBaseSpecifier; |
40 | class FunctionDecl; |
41 | class LabelDecl; |
42 | |
43 | namespace ento { |
44 | |
45 | class CompoundValData; |
46 | class LazyCompoundValData; |
47 | class MemRegion; |
48 | class PointerToMemberData; |
49 | class SValBuilder; |
50 | class TypedValueRegion; |
51 | |
52 | /// SVal - This represents a symbolic expression, which can be either |
53 | /// an L-value or an R-value. |
54 | /// |
55 | class SVal { |
56 | public: |
57 | enum SValKind : unsigned char { |
58 | #define BASIC_SVAL(Id, Parent) Id##Kind, |
59 | #define LOC_SVAL(Id, Parent) Loc##Id##Kind, |
60 | #define NONLOC_SVAL(Id, Parent) NonLoc##Id##Kind, |
61 | #define SVAL_RANGE(Id, First, Last) \ |
62 | BEGIN_##Id = Id##First##Kind, END_##Id = Id##Last##Kind, |
63 | #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" |
64 | }; |
65 | |
66 | protected: |
67 | const void *Data = nullptr; |
68 | SValKind Kind = UndefinedValKind; |
69 | |
70 | explicit SVal(SValKind Kind, const void *Data = nullptr) |
71 | : Data(Data), Kind(Kind) {} |
72 | |
73 | template <typename T> const T *castDataAs() const { |
74 | return static_cast<const T *>(Data); |
75 | } |
76 | |
77 | public: |
78 | explicit SVal() = default; |
79 | |
80 | /// Convert to the specified SVal type, asserting that this SVal is of |
81 | /// the desired type. |
82 | template <typename T> T castAs() const { return llvm::cast<T>(*this); } |
83 | |
84 | /// Convert to the specified SVal type, returning std::nullopt if this SVal is |
85 | /// not of the desired type. |
86 | template <typename T> std::optional<T> getAs() const { |
87 | return llvm::dyn_cast<T>(*this); |
88 | } |
89 | |
90 | SValKind getKind() const { return Kind; } |
91 | |
92 | // This method is required for using SVal in a FoldingSetNode. It |
93 | // extracts a unique signature for this SVal object. |
94 | void Profile(llvm::FoldingSetNodeID &ID) const { |
95 | ID.AddPointer(Ptr: Data); |
96 | ID.AddInteger(I: llvm::to_underlying(E: getKind())); |
97 | } |
98 | |
99 | bool operator==(SVal R) const { return Kind == R.Kind && Data == R.Data; } |
100 | bool operator!=(SVal R) const { return !(*this == R); } |
101 | |
102 | bool isUnknown() const { return getKind() == UnknownValKind; } |
103 | |
104 | bool isUndef() const { return getKind() == UndefinedValKind; } |
105 | |
106 | bool isUnknownOrUndef() const { return isUnknown() || isUndef(); } |
107 | |
108 | bool isValid() const { return !isUnknownOrUndef(); } |
109 | |
110 | bool isConstant() const; |
111 | |
112 | bool isConstant(int I) const; |
113 | |
114 | bool isZeroConstant() const; |
115 | |
116 | /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a |
117 | /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. |
118 | /// Otherwise return 0. |
119 | const FunctionDecl *getAsFunctionDecl() const; |
120 | |
121 | /// If this SVal is a location and wraps a symbol, return that |
122 | /// SymbolRef. 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. |
127 | SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const; |
128 | |
129 | /// Get the symbol in the SVal or its base region. |
130 | SymbolRef getLocSymbolInBase() const; |
131 | |
132 | /// If this SVal wraps a symbol return that SymbolRef. |
133 | /// Otherwise, return 0. |
134 | /// |
135 | /// Casts are ignored during lookup. |
136 | /// \param IncludeBaseRegions The boolean that controls whether the search |
137 | /// should continue to the base regions if the region is not symbolic. |
138 | SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const; |
139 | |
140 | /// If this SVal is loc::ConcreteInt or nonloc::ConcreteInt, |
141 | /// return a pointer to APSInt which is held in it. |
142 | /// Otherwise, return nullptr. |
143 | const llvm::APSInt *getAsInteger() const; |
144 | |
145 | const MemRegion *getAsRegion() const; |
146 | |
147 | /// printJson - Pretty-prints in JSON format. |
148 | void printJson(raw_ostream &Out, bool AddQuotes) const; |
149 | |
150 | void dumpToStream(raw_ostream &OS) const; |
151 | void dump() const; |
152 | |
153 | llvm::iterator_range<SymExpr::symbol_iterator> symbols() const { |
154 | if (const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/IncludeBaseRegions: true)) |
155 | return SE->symbols(); |
156 | SymExpr::symbol_iterator end{}; |
157 | return llvm::make_range(x: end, y: end); |
158 | } |
159 | |
160 | /// Try to get a reasonable type for the given value. |
161 | /// |
162 | /// \returns The best approximation of the value type or Null. |
163 | /// In theory, all symbolic values should be typed, but this function |
164 | /// is still a WIP and might have a few blind spots. |
165 | /// |
166 | /// \note This function should not be used when the user has access to the |
167 | /// bound expression AST node as well, since AST always has exact types. |
168 | /// |
169 | /// \note Loc values are interpreted as pointer rvalues for the purposes of |
170 | /// this method. |
171 | QualType getType(const ASTContext &) const; |
172 | }; |
173 | |
174 | inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { |
175 | V.dumpToStream(OS&: os); |
176 | return os; |
177 | } |
178 | |
179 | namespace nonloc { |
180 | /// Sub-kinds for NonLoc values. |
181 | #define NONLOC_SVAL(Id, Parent) \ |
182 | inline constexpr auto Id##Kind = SVal::SValKind::NonLoc##Id##Kind; |
183 | #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" |
184 | } // namespace nonloc |
185 | |
186 | namespace loc { |
187 | /// Sub-kinds for Loc values. |
188 | #define LOC_SVAL(Id, Parent) \ |
189 | inline constexpr auto Id##Kind = SVal::SValKind::Loc##Id##Kind; |
190 | #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" |
191 | } // namespace loc |
192 | |
193 | class UndefinedVal : public SVal { |
194 | public: |
195 | UndefinedVal() : SVal(UndefinedValKind) {} |
196 | static bool classof(SVal V) { return V.getKind() == UndefinedValKind; } |
197 | }; |
198 | |
199 | class DefinedOrUnknownSVal : public SVal { |
200 | public: |
201 | // We want calling these methods to be a compiler error since they are |
202 | // tautologically false. |
203 | bool isUndef() const = delete; |
204 | bool isValid() const = delete; |
205 | |
206 | static bool classof(SVal V) { return !V.isUndef(); } |
207 | |
208 | protected: |
209 | explicit DefinedOrUnknownSVal(SValKind Kind, const void *Data = nullptr) |
210 | : SVal(Kind, Data) {} |
211 | }; |
212 | |
213 | class UnknownVal : public DefinedOrUnknownSVal { |
214 | public: |
215 | explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {} |
216 | |
217 | static bool classof(SVal V) { return V.getKind() == UnknownValKind; } |
218 | }; |
219 | |
220 | class DefinedSVal : public DefinedOrUnknownSVal { |
221 | public: |
222 | // We want calling these methods to be a compiler error since they are |
223 | // tautologically true/false. |
224 | bool isUnknown() const = delete; |
225 | bool isUnknownOrUndef() const = delete; |
226 | bool isValid() const = delete; |
227 | |
228 | static bool classof(SVal V) { return !V.isUnknownOrUndef(); } |
229 | |
230 | protected: |
231 | explicit DefinedSVal(SValKind Kind, const void *Data) |
232 | : DefinedOrUnknownSVal(Kind, Data) {} |
233 | }; |
234 | |
235 | /// Represents an SVal that is guaranteed to not be UnknownVal. |
236 | class KnownSVal : public SVal { |
237 | public: |
238 | /*implicit*/ KnownSVal(DefinedSVal V) : SVal(V) {} |
239 | /*implicit*/ KnownSVal(UndefinedVal V) : SVal(V) {} |
240 | static bool classof(SVal V) { return !V.isUnknown(); } |
241 | }; |
242 | |
243 | class NonLoc : public DefinedSVal { |
244 | protected: |
245 | NonLoc(SValKind Kind, const void *Data) : DefinedSVal(Kind, Data) {} |
246 | |
247 | public: |
248 | void dumpToStream(raw_ostream &Out) const; |
249 | |
250 | static bool isCompoundType(QualType T) { |
251 | return T->isArrayType() || T->isRecordType() || |
252 | T->isAnyComplexType() || T->isVectorType(); |
253 | } |
254 | |
255 | static bool classof(SVal V) { |
256 | return BEGIN_NonLoc <= V.getKind() && V.getKind() <= END_NonLoc; |
257 | } |
258 | }; |
259 | |
260 | class Loc : public DefinedSVal { |
261 | protected: |
262 | Loc(SValKind Kind, const void *Data) : DefinedSVal(Kind, Data) {} |
263 | |
264 | public: |
265 | void dumpToStream(raw_ostream &Out) const; |
266 | |
267 | static bool isLocType(QualType T) { |
268 | return T->isAnyPointerType() || T->isBlockPointerType() || |
269 | T->isReferenceType() || T->isNullPtrType(); |
270 | } |
271 | |
272 | static bool classof(SVal V) { |
273 | return BEGIN_Loc <= V.getKind() && V.getKind() <= END_Loc; |
274 | } |
275 | }; |
276 | |
277 | //==------------------------------------------------------------------------==// |
278 | // Subclasses of NonLoc. |
279 | //==------------------------------------------------------------------------==// |
280 | |
281 | namespace nonloc { |
282 | |
283 | /// Represents symbolic expression that isn't a location. |
284 | class SymbolVal : public NonLoc { |
285 | public: |
286 | SymbolVal() = delete; |
287 | explicit SymbolVal(SymbolRef Sym) : NonLoc(SymbolValKind, Sym) { |
288 | assert(Sym); |
289 | assert(!Loc::isLocType(Sym->getType())); |
290 | } |
291 | |
292 | LLVM_ATTRIBUTE_RETURNS_NONNULL |
293 | SymbolRef getSymbol() const { |
294 | return (const SymExpr *) Data; |
295 | } |
296 | |
297 | bool isExpression() const { |
298 | return !isa<SymbolData>(Val: getSymbol()); |
299 | } |
300 | |
301 | static bool classof(SVal V) { return V.getKind() == SymbolValKind; } |
302 | }; |
303 | |
304 | /// Value representing integer constant. |
305 | class ConcreteInt : public NonLoc { |
306 | public: |
307 | explicit ConcreteInt(const llvm::APSInt &V) : NonLoc(ConcreteIntKind, &V) {} |
308 | |
309 | const llvm::APSInt &getValue() const { return *castDataAs<llvm::APSInt>(); } |
310 | |
311 | static bool classof(SVal V) { return V.getKind() == ConcreteIntKind; } |
312 | }; |
313 | |
314 | class LocAsInteger : public NonLoc { |
315 | friend class ento::SValBuilder; |
316 | |
317 | explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data) |
318 | : NonLoc(LocAsIntegerKind, &data) { |
319 | // We do not need to represent loc::ConcreteInt as LocAsInteger, |
320 | // as it'd collapse into a nonloc::ConcreteInt instead. |
321 | [[maybe_unused]] SValKind K = data.first.getKind(); |
322 | assert(K == loc::MemRegionValKind || K == loc::GotoLabelKind); |
323 | } |
324 | |
325 | public: |
326 | Loc getLoc() const { |
327 | return castDataAs<std::pair<SVal, uintptr_t>>()->first.castAs<Loc>(); |
328 | } |
329 | |
330 | unsigned getNumBits() const { |
331 | return castDataAs<std::pair<SVal, uintptr_t>>()->second; |
332 | } |
333 | |
334 | static bool classof(SVal V) { return V.getKind() == LocAsIntegerKind; } |
335 | }; |
336 | |
337 | class CompoundVal : public NonLoc { |
338 | friend class ento::SValBuilder; |
339 | |
340 | explicit CompoundVal(const CompoundValData *D) : NonLoc(CompoundValKind, D) { |
341 | assert(D); |
342 | } |
343 | |
344 | public: |
345 | LLVM_ATTRIBUTE_RETURNS_NONNULL |
346 | const CompoundValData* getValue() const { |
347 | return castDataAs<CompoundValData>(); |
348 | } |
349 | |
350 | using iterator = llvm::ImmutableList<SVal>::iterator; |
351 | iterator begin() const; |
352 | iterator end() const; |
353 | |
354 | static bool classof(SVal V) { return V.getKind() == CompoundValKind; } |
355 | }; |
356 | |
357 | class LazyCompoundVal : public NonLoc { |
358 | friend class ento::SValBuilder; |
359 | |
360 | explicit LazyCompoundVal(const LazyCompoundValData *D) |
361 | : NonLoc(LazyCompoundValKind, D) { |
362 | assert(D); |
363 | } |
364 | |
365 | public: |
366 | LLVM_ATTRIBUTE_RETURNS_NONNULL |
367 | const LazyCompoundValData *getCVData() const { |
368 | return castDataAs<LazyCompoundValData>(); |
369 | } |
370 | |
371 | /// It might return null. |
372 | const void *getStore() const; |
373 | |
374 | LLVM_ATTRIBUTE_RETURNS_NONNULL |
375 | const TypedValueRegion *getRegion() const; |
376 | |
377 | static bool classof(SVal V) { return V.getKind() == LazyCompoundValKind; } |
378 | }; |
379 | |
380 | /// Value representing pointer-to-member. |
381 | /// |
382 | /// This value is qualified as NonLoc because neither loading nor storing |
383 | /// operations are applied to it. Instead, the analyzer uses the L-value coming |
384 | /// from pointer-to-member applied to an object. |
385 | /// This SVal is represented by a NamedDecl which can be a member function |
386 | /// pointer or a member data pointer and an optional list of CXXBaseSpecifiers. |
387 | /// This list is required to accumulate the pointer-to-member cast history to |
388 | /// figure out the correct subobject field. In particular, implicit casts grow |
389 | /// this list and explicit casts like static_cast shrink this list. |
390 | class PointerToMember : public NonLoc { |
391 | friend class ento::SValBuilder; |
392 | |
393 | public: |
394 | using PTMDataType = |
395 | llvm::PointerUnion<const NamedDecl *, const PointerToMemberData *>; |
396 | |
397 | const PTMDataType getPTMData() const { |
398 | return PTMDataType::getFromOpaqueValue(VP: const_cast<void *>(Data)); |
399 | } |
400 | |
401 | bool isNullMemberPointer() const; |
402 | |
403 | const NamedDecl *getDecl() const; |
404 | |
405 | template<typename AdjustedDecl> |
406 | const AdjustedDecl *getDeclAs() const { |
407 | return dyn_cast_or_null<AdjustedDecl>(getDecl()); |
408 | } |
409 | |
410 | using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator; |
411 | |
412 | iterator begin() const; |
413 | iterator end() const; |
414 | |
415 | static bool classof(SVal V) { return V.getKind() == PointerToMemberKind; } |
416 | |
417 | private: |
418 | explicit PointerToMember(const PTMDataType D) |
419 | : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {} |
420 | }; |
421 | |
422 | } // namespace nonloc |
423 | |
424 | //==------------------------------------------------------------------------==// |
425 | // Subclasses of Loc. |
426 | //==------------------------------------------------------------------------==// |
427 | |
428 | namespace loc { |
429 | |
430 | class GotoLabel : public Loc { |
431 | public: |
432 | explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) { |
433 | assert(Label); |
434 | } |
435 | |
436 | const LabelDecl *getLabel() const { return castDataAs<LabelDecl>(); } |
437 | |
438 | static bool classof(SVal V) { return V.getKind() == GotoLabelKind; } |
439 | }; |
440 | |
441 | class MemRegionVal : public Loc { |
442 | public: |
443 | explicit MemRegionVal(const MemRegion *r) : Loc(MemRegionValKind, r) { |
444 | assert(r); |
445 | } |
446 | |
447 | /// Get the underlining region. |
448 | LLVM_ATTRIBUTE_RETURNS_NONNULL |
449 | const MemRegion *getRegion() const { return castDataAs<MemRegion>(); } |
450 | |
451 | /// Get the underlining region and strip casts. |
452 | LLVM_ATTRIBUTE_RETURNS_NONNULL |
453 | const MemRegion* stripCasts(bool StripBaseCasts = true) const; |
454 | |
455 | template <typename REGION> |
456 | const REGION* getRegionAs() const { |
457 | return dyn_cast<REGION>(getRegion()); |
458 | } |
459 | |
460 | bool operator==(const MemRegionVal &R) const { |
461 | return getRegion() == R.getRegion(); |
462 | } |
463 | |
464 | bool operator!=(const MemRegionVal &R) const { |
465 | return getRegion() != R.getRegion(); |
466 | } |
467 | |
468 | static bool classof(SVal V) { return V.getKind() == MemRegionValKind; } |
469 | }; |
470 | |
471 | class ConcreteInt : public Loc { |
472 | public: |
473 | explicit ConcreteInt(const llvm::APSInt &V) : Loc(ConcreteIntKind, &V) {} |
474 | |
475 | const llvm::APSInt &getValue() const { return *castDataAs<llvm::APSInt>(); } |
476 | |
477 | static bool classof(SVal V) { return V.getKind() == ConcreteIntKind; } |
478 | }; |
479 | |
480 | } // namespace loc |
481 | } // namespace ento |
482 | } // namespace clang |
483 | |
484 | namespace llvm { |
485 | template <typename To, typename From> |
486 | struct CastInfo< |
487 | To, From, |
488 | std::enable_if_t<std::is_base_of<::clang::ento::SVal, From>::value>> |
489 | : public CastIsPossible<To, ::clang::ento::SVal> { |
490 | using Self = CastInfo< |
491 | To, From, |
492 | std::enable_if_t<std::is_base_of<::clang::ento::SVal, From>::value>>; |
493 | static bool isPossible(const From &V) { |
494 | return To::classof(*static_cast<const ::clang::ento::SVal *>(&V)); |
495 | } |
496 | static std::optional<To> castFailed() { return std::optional<To>{}; } |
497 | static To doCast(const From &f) { |
498 | return *static_cast<const To *>(cast<::clang::ento::SVal>(&f)); |
499 | } |
500 | static std::optional<To> doCastIfPossible(const From &f) { |
501 | if (!Self::isPossible(V: f)) |
502 | return Self::castFailed(); |
503 | return doCast(f); |
504 | } |
505 | }; |
506 | } // namespace llvm |
507 | |
508 | #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H |
509 | |