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/FoldingSet.h"
22#include "llvm/ADT/ImmutableList.h"
23#include "llvm/ADT/None.h"
24#include "llvm/ADT/Optional.h"
25#include "llvm/ADT/PointerUnion.h"
26#include "llvm/Support/Casting.h"
27#include <cassert>
28#include <cstdint>
29#include <utility>
30
31//==------------------------------------------------------------------------==//
32// Base SVal types.
33//==------------------------------------------------------------------------==//
34
35namespace clang {
36
37class CXXBaseSpecifier;
38class DeclaratorDecl;
39class FunctionDecl;
40class LabelDecl;
41
42namespace ento {
43
44class BasicValueFactory;
45class CompoundValData;
46class LazyCompoundValData;
47class MemRegion;
48class PointerToMemberData;
49class SValBuilder;
50class TypedValueRegion;
51
52namespace nonloc {
53
54/// Sub-kinds for NonLoc values.
55enum Kind {
56#define NONLOC_SVAL(Id, Parent) Id ## Kind,
57#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
58};
59
60} // namespace nonloc
61
62namespace loc {
63
64/// Sub-kinds for Loc values.
65enum Kind {
66#define LOC_SVAL(Id, Parent) Id ## Kind,
67#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
68};
69
70} // namespace loc
71
72/// SVal - This represents a symbolic expression, which can be either
73/// an L-value or an R-value.
74///
75class SVal {
76public:
77 enum BaseKind {
78 // The enumerators must be representable using 2 bits.
79#define BASIC_SVAL(Id, Parent) Id ## Kind,
80#define ABSTRACT_SVAL_WITH_KIND(Id, Parent) Id ## Kind,
81#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def"
82 };
83 enum { BaseBits = 2, BaseMask = 0x3 };
84
85protected:
86 const void *Data = nullptr;
87
88 /// The lowest 2 bits are a BaseKind (0 -- 3).
89 /// The higher bits are an unsigned "kind" value.
90 unsigned Kind = 0;
91
92 explicit SVal(const void *d, bool isLoc, unsigned ValKind)
93 : Data(d), Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {}
94
95 explicit SVal(BaseKind k, const void *D = nullptr) : Data(D), Kind(k) {}
96
97public:
98 explicit SVal() = default;
99
100 /// Convert to the specified SVal type, asserting that this SVal is of
101 /// the desired type.
102 template<typename T>
103 T castAs() const {
104 assert(T::isKind(*this));
105 return *static_cast<const T *>(this);
106 }
107
108 /// Convert to the specified SVal type, returning None if this SVal is
109 /// not of the desired type.
110 template<typename T>
111 Optional<T> getAs() const {
112 if (!T::isKind(*this))
113 return None;
114 return *static_cast<const T *>(this);
115 }
116
117 unsigned getRawKind() const { return Kind; }
118 BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); }
119 unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; }
120
121 // This method is required for using SVal in a FoldingSetNode. It
122 // extracts a unique signature for this SVal object.
123 void Profile(llvm::FoldingSetNodeID &ID) const {
124 ID.AddInteger((unsigned) getRawKind());
125 ID.AddPointer(Data);
126 }
127
128 bool operator==(const SVal &R) const {
129 return getRawKind() == R.getRawKind() && Data == R.Data;
130 }
131
132 bool operator!=(const SVal &R) const {
133 return !(*this == R);
134 }
135
136 bool isUnknown() const {
137 return getRawKind() == UnknownValKind;
138 }
139
140 bool isUndef() const {
141 return getRawKind() == UndefinedValKind;
142 }
143
144 bool isUnknownOrUndef() const {
145 return getRawKind() <= UnknownValKind;
146 }
147
148 bool isValid() const {
149 return getRawKind() > UnknownValKind;
150 }
151
152 bool isConstant() const;
153
154 bool isConstant(int I) const;
155
156 bool isZeroConstant() const;
157
158 /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true;
159 bool hasConjuredSymbol() const;
160
161 /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a
162 /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl.
163 /// Otherwise return 0.
164 const FunctionDecl *getAsFunctionDecl() const;
165
166 /// If this SVal is a location and wraps a symbol, return that
167 /// SymbolRef. Otherwise return 0.
168 ///
169 /// Casts are ignored during lookup.
170 /// \param IncludeBaseRegions The boolean that controls whether the search
171 /// should continue to the base regions if the region is not symbolic.
172 SymbolRef getAsLocSymbol(bool IncludeBaseRegions = false) const;
173
174 /// Get the symbol in the SVal or its base region.
175 SymbolRef getLocSymbolInBase() const;
176
177 /// If this SVal wraps a symbol return that SymbolRef.
178 /// Otherwise, return 0.
179 ///
180 /// Casts are ignored during lookup.
181 /// \param IncludeBaseRegions The boolean that controls whether the search
182 /// should continue to the base regions if the region is not symbolic.
183 SymbolRef getAsSymbol(bool IncludeBaseRegions = false) const;
184
185 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then
186 /// return that expression. Otherwise return NULL.
187 const SymExpr *getAsSymbolicExpression() const;
188
189 const SymExpr *getAsSymExpr() const;
190
191 const MemRegion *getAsRegion() const;
192
193 void dumpToStream(raw_ostream &OS) const;
194 void dump() const;
195
196 SymExpr::symbol_iterator symbol_begin() const {
197 const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true);
198 if (SE)
199 return SE->symbol_begin();
200 else
201 return SymExpr::symbol_iterator();
202 }
203
204 SymExpr::symbol_iterator symbol_end() const {
205 return SymExpr::symbol_end();
206 }
207};
208
209inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) {
210 V.dumpToStream(os);
211 return os;
212}
213
214class UndefinedVal : public SVal {
215public:
216 UndefinedVal() : SVal(UndefinedValKind) {}
217
218private:
219 friend class SVal;
220
221 static bool isKind(const SVal& V) {
222 return V.getBaseKind() == UndefinedValKind;
223 }
224};
225
226class DefinedOrUnknownSVal : public SVal {
227public:
228 // We want calling these methods to be a compiler error since they are
229 // tautologically false.
230 bool isUndef() const = delete;
231 bool isValid() const = delete;
232
233protected:
234 DefinedOrUnknownSVal() = default;
235 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
236 : SVal(d, isLoc, ValKind) {}
237 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {}
238
239private:
240 friend class SVal;
241
242 static bool isKind(const SVal& V) {
243 return !V.isUndef();
244 }
245};
246
247class UnknownVal : public DefinedOrUnknownSVal {
248public:
249 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
250
251private:
252 friend class SVal;
253
254 static bool isKind(const SVal &V) {
255 return V.getBaseKind() == UnknownValKind;
256 }
257};
258
259class DefinedSVal : public DefinedOrUnknownSVal {
260public:
261 // We want calling these methods to be a compiler error since they are
262 // tautologically true/false.
263 bool isUnknown() const = delete;
264 bool isUnknownOrUndef() const = delete;
265 bool isValid() const = delete;
266
267protected:
268 DefinedSVal() = default;
269 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
270 : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
271
272private:
273 friend class SVal;
274
275 static bool isKind(const SVal& V) {
276 return !V.isUnknownOrUndef();
277 }
278};
279
280/// Represents an SVal that is guaranteed to not be UnknownVal.
281class KnownSVal : public SVal {
282 friend class SVal;
283
284 KnownSVal() = default;
285
286 static bool isKind(const SVal &V) {
287 return !V.isUnknown();
288 }
289
290public:
291 KnownSVal(const DefinedSVal &V) : SVal(V) {}
292 KnownSVal(const UndefinedVal &V) : SVal(V) {}
293};
294
295class NonLoc : public DefinedSVal {
296protected:
297 NonLoc() = default;
298 explicit NonLoc(unsigned SubKind, const void *d)
299 : DefinedSVal(d, false, SubKind) {}
300
301public:
302 void dumpToStream(raw_ostream &Out) const;
303
304 static bool isCompoundType(QualType T) {
305 return T->isArrayType() || T->isRecordType() ||
306 T->isComplexType() || T->isVectorType();
307 }
308
309private:
310 friend class SVal;
311
312 static bool isKind(const SVal& V) {
313 return V.getBaseKind() == NonLocKind;
314 }
315};
316
317class Loc : public DefinedSVal {
318protected:
319 Loc() = default;
320 explicit Loc(unsigned SubKind, const void *D)
321 : DefinedSVal(const_cast<void *>(D), true, SubKind) {}
322
323public:
324 void dumpToStream(raw_ostream &Out) const;
325
326 static bool isLocType(QualType T) {
327 return T->isAnyPointerType() || T->isBlockPointerType() ||
328 T->isReferenceType() || T->isNullPtrType();
329 }
330
331private:
332 friend class SVal;
333
334 static bool isKind(const SVal& V) {
335 return V.getBaseKind() == LocKind;
336 }
337};
338
339//==------------------------------------------------------------------------==//
340// Subclasses of NonLoc.
341//==------------------------------------------------------------------------==//
342
343namespace nonloc {
344
345/// Represents symbolic expression that isn't a location.
346class SymbolVal : public NonLoc {
347public:
348 SymbolVal() = delete;
349 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {
350 assert(sym);
351 assert(!Loc::isLocType(sym->getType()));
352 }
353
354 SymbolRef getSymbol() const {
355 return (const SymExpr *) Data;
356 }
357
358 bool isExpression() const {
359 return !isa<SymbolData>(getSymbol());
360 }
361
362private:
363 friend class SVal;
364
365 static bool isKind(const SVal& V) {
366 return V.getBaseKind() == NonLocKind &&
367 V.getSubKind() == SymbolValKind;
368 }
369
370 static bool isKind(const NonLoc& V) {
371 return V.getSubKind() == SymbolValKind;
372 }
373};
374
375/// Value representing integer constant.
376class ConcreteInt : public NonLoc {
377public:
378 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
379
380 const llvm::APSInt& getValue() const {
381 return *static_cast<const llvm::APSInt *>(Data);
382 }
383
384 // Transfer functions for binary/unary operations on ConcreteInts.
385 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
386 const ConcreteInt& R) const;
387
388 ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
389
390 ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
391
392private:
393 friend class SVal;
394
395 ConcreteInt() = default;
396
397 static bool isKind(const SVal& V) {
398 return V.getBaseKind() == NonLocKind &&
399 V.getSubKind() == ConcreteIntKind;
400 }
401
402 static bool isKind(const NonLoc& V) {
403 return V.getSubKind() == ConcreteIntKind;
404 }
405};
406
407class LocAsInteger : public NonLoc {
408 friend class ento::SValBuilder;
409
410 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
411 : NonLoc(LocAsIntegerKind, &data) {
412 // We do not need to represent loc::ConcreteInt as LocAsInteger,
413 // as it'd collapse into a nonloc::ConcreteInt instead.
414 assert(data.first.getBaseKind() == LocKind &&
415 (data.first.getSubKind() == loc::MemRegionValKind ||
416 data.first.getSubKind() == loc::GotoLabelKind));
417 }
418
419public:
420 Loc getLoc() const {
421 const std::pair<SVal, uintptr_t> *D =
422 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
423 return D->first.castAs<Loc>();
424 }
425
426 Loc getPersistentLoc() const {
427 const std::pair<SVal, uintptr_t> *D =
428 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
429 const SVal& V = D->first;
430 return V.castAs<Loc>();
431 }
432
433 unsigned getNumBits() const {
434 const std::pair<SVal, uintptr_t> *D =
435 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
436 return D->second;
437 }
438
439private:
440 friend class SVal;
441
442 LocAsInteger() = default;
443
444 static bool isKind(const SVal& V) {
445 return V.getBaseKind() == NonLocKind &&
446 V.getSubKind() == LocAsIntegerKind;
447 }
448
449 static bool isKind(const NonLoc& V) {
450 return V.getSubKind() == LocAsIntegerKind;
451 }
452};
453
454class CompoundVal : public NonLoc {
455 friend class ento::SValBuilder;
456
457 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
458
459public:
460 const CompoundValData* getValue() const {
461 return static_cast<const CompoundValData *>(Data);
462 }
463
464 using iterator = llvm::ImmutableList<SVal>::iterator;
465
466 iterator begin() const;
467 iterator end() const;
468
469private:
470 friend class SVal;
471
472 CompoundVal() = default;
473
474 static bool isKind(const SVal& V) {
475 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
476 }
477
478 static bool isKind(const NonLoc& V) {
479 return V.getSubKind() == CompoundValKind;
480 }
481};
482
483class LazyCompoundVal : public NonLoc {
484 friend class ento::SValBuilder;
485
486 explicit LazyCompoundVal(const LazyCompoundValData *D)
487 : NonLoc(LazyCompoundValKind, D) {}
488
489public:
490 const LazyCompoundValData *getCVData() const {
491 return static_cast<const LazyCompoundValData *>(Data);
492 }
493
494 const void *getStore() const;
495 const TypedValueRegion *getRegion() const;
496
497private:
498 friend class SVal;
499
500 LazyCompoundVal() = default;
501
502 static bool isKind(const SVal& V) {
503 return V.getBaseKind() == NonLocKind &&
504 V.getSubKind() == LazyCompoundValKind;
505 }
506
507 static bool isKind(const NonLoc& V) {
508 return V.getSubKind() == LazyCompoundValKind;
509 }
510};
511
512/// Value representing pointer-to-member.
513///
514/// This value is qualified as NonLoc because neither loading nor storing
515/// operations are applied to it. Instead, the analyzer uses the L-value coming
516/// from pointer-to-member applied to an object.
517/// This SVal is represented by a DeclaratorDecl which can be a member function
518/// pointer or a member data pointer and a list of CXXBaseSpecifiers. This list
519/// is required to accumulate the pointer-to-member cast history to figure out
520/// the correct subobject field.
521class PointerToMember : public NonLoc {
522 friend class ento::SValBuilder;
523
524public:
525 using PTMDataType =
526 llvm::PointerUnion<const DeclaratorDecl *, const PointerToMemberData *>;
527
528 const PTMDataType getPTMData() const {
529 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data));
530 }
531
532 bool isNullMemberPointer() const;
533
534 const DeclaratorDecl *getDecl() const;
535
536 template<typename AdjustedDecl>
537 const AdjustedDecl *getDeclAs() const {
538 return dyn_cast_or_null<AdjustedDecl>(getDecl());
539 }
540
541 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator;
542
543 iterator begin() const;
544 iterator end() const;
545
546private:
547 friend class SVal;
548
549 PointerToMember() = default;
550 explicit PointerToMember(const PTMDataType D)
551 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {}
552
553 static bool isKind(const SVal& V) {
554 return V.getBaseKind() == NonLocKind &&
555 V.getSubKind() == PointerToMemberKind;
556 }
557
558 static bool isKind(const NonLoc& V) {
559 return V.getSubKind() == PointerToMemberKind;
560 }
561};
562
563} // namespace nonloc
564
565//==------------------------------------------------------------------------==//
566// Subclasses of Loc.
567//==------------------------------------------------------------------------==//
568
569namespace loc {
570
571class GotoLabel : public Loc {
572public:
573 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) {
574 assert(Label);
575 }
576
577 const LabelDecl *getLabel() const {
578 return static_cast<const LabelDecl *>(Data);
579 }
580
581private:
582 friend class SVal;
583
584 GotoLabel() = default;
585
586 static bool isKind(const SVal& V) {
587 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
588 }
589
590 static bool isKind(const Loc& V) {
591 return V.getSubKind() == GotoLabelKind;
592 }
593};
594
595class MemRegionVal : public Loc {
596public:
597 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {
598 assert(r);
599 }
600
601 /// Get the underlining region.
602 const MemRegion *getRegion() const {
603 return static_cast<const MemRegion *>(Data);
604 }
605
606 /// Get the underlining region and strip casts.
607 const MemRegion* stripCasts(bool StripBaseCasts = true) const;
608
609 template <typename REGION>
610 const REGION* getRegionAs() const {
611 return dyn_cast<REGION>(getRegion());
612 }
613
614 bool operator==(const MemRegionVal &R) const {
615 return getRegion() == R.getRegion();
616 }
617
618 bool operator!=(const MemRegionVal &R) const {
619 return getRegion() != R.getRegion();
620 }
621
622private:
623 friend class SVal;
624
625 MemRegionVal() = default;
626
627 static bool isKind(const SVal& V) {
628 return V.getBaseKind() == LocKind &&
629 V.getSubKind() == MemRegionValKind;
630 }
631
632 static bool isKind(const Loc& V) {
633 return V.getSubKind() == MemRegionValKind;
634 }
635};
636
637class ConcreteInt : public Loc {
638public:
639 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
640
641 const llvm::APSInt &getValue() const {
642 return *static_cast<const llvm::APSInt *>(Data);
643 }
644
645 // Transfer functions for binary/unary operations on ConcreteInts.
646 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
647 const ConcreteInt& R) const;
648
649private:
650 friend class SVal;
651
652 ConcreteInt() = default;
653
654 static bool isKind(const SVal& V) {
655 return V.getBaseKind() == LocKind &&
656 V.getSubKind() == ConcreteIntKind;
657 }
658
659 static bool isKind(const Loc& V) {
660 return V.getSubKind() == ConcreteIntKind;
661 }
662};
663
664} // namespace loc
665
666} // namespace ento
667
668} // namespace clang
669
670#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
671