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 = 0b11 };
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 >> 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 const MemRegion *getAsRegion() const;
186
187 /// printJson - Pretty-prints in JSON format.
188 void printJson(raw_ostream &Out, bool AddQuotes) const;
189
190 void dumpToStream(raw_ostream &OS) const;
191 void dump() const;
192
193 SymExpr::symbol_iterator symbol_begin() const {
194 const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true);
195 if (SE)
196 return SE->symbol_begin();
197 else
198 return SymExpr::symbol_iterator();
199 }
200
201 SymExpr::symbol_iterator symbol_end() const {
202 return SymExpr::symbol_end();
203 }
204};
205
206inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) {
207 V.dumpToStream(os);
208 return os;
209}
210
211class UndefinedVal : public SVal {
212public:
213 UndefinedVal() : SVal(UndefinedValKind) {}
214
215private:
216 friend class SVal;
217
218 static bool isKind(const SVal& V) {
219 return V.getBaseKind() == UndefinedValKind;
220 }
221};
222
223class DefinedOrUnknownSVal : public SVal {
224public:
225 // We want calling these methods to be a compiler error since they are
226 // tautologically false.
227 bool isUndef() const = delete;
228 bool isValid() const = delete;
229
230protected:
231 DefinedOrUnknownSVal() = default;
232 explicit DefinedOrUnknownSVal(const void *d, bool isLoc, unsigned ValKind)
233 : SVal(d, isLoc, ValKind) {}
234 explicit DefinedOrUnknownSVal(BaseKind k, void *D = nullptr) : SVal(k, D) {}
235
236private:
237 friend class SVal;
238
239 static bool isKind(const SVal& V) {
240 return !V.isUndef();
241 }
242};
243
244class UnknownVal : public DefinedOrUnknownSVal {
245public:
246 explicit UnknownVal() : DefinedOrUnknownSVal(UnknownValKind) {}
247
248private:
249 friend class SVal;
250
251 static bool isKind(const SVal &V) {
252 return V.getBaseKind() == UnknownValKind;
253 }
254};
255
256class DefinedSVal : public DefinedOrUnknownSVal {
257public:
258 // We want calling these methods to be a compiler error since they are
259 // tautologically true/false.
260 bool isUnknown() const = delete;
261 bool isUnknownOrUndef() const = delete;
262 bool isValid() const = delete;
263
264protected:
265 DefinedSVal() = default;
266 explicit DefinedSVal(const void *d, bool isLoc, unsigned ValKind)
267 : DefinedOrUnknownSVal(d, isLoc, ValKind) {}
268
269private:
270 friend class SVal;
271
272 static bool isKind(const SVal& V) {
273 return !V.isUnknownOrUndef();
274 }
275};
276
277/// Represents an SVal that is guaranteed to not be UnknownVal.
278class KnownSVal : public SVal {
279 friend class SVal;
280
281 KnownSVal() = default;
282
283 static bool isKind(const SVal &V) {
284 return !V.isUnknown();
285 }
286
287public:
288 KnownSVal(const DefinedSVal &V) : SVal(V) {}
289 KnownSVal(const UndefinedVal &V) : SVal(V) {}
290};
291
292class NonLoc : public DefinedSVal {
293protected:
294 NonLoc() = default;
295 explicit NonLoc(unsigned SubKind, const void *d)
296 : DefinedSVal(d, false, SubKind) {}
297
298public:
299 void dumpToStream(raw_ostream &Out) const;
300
301 static bool isCompoundType(QualType T) {
302 return T->isArrayType() || T->isRecordType() ||
303 T->isAnyComplexType() || T->isVectorType();
304 }
305
306private:
307 friend class SVal;
308
309 static bool isKind(const SVal& V) {
310 return V.getBaseKind() == NonLocKind;
311 }
312};
313
314class Loc : public DefinedSVal {
315protected:
316 Loc() = default;
317 explicit Loc(unsigned SubKind, const void *D)
318 : DefinedSVal(const_cast<void *>(D), true, SubKind) {}
319
320public:
321 void dumpToStream(raw_ostream &Out) const;
322
323 static bool isLocType(QualType T) {
324 return T->isAnyPointerType() || T->isBlockPointerType() ||
325 T->isReferenceType() || T->isNullPtrType();
326 }
327
328private:
329 friend class SVal;
330
331 static bool isKind(const SVal& V) {
332 return V.getBaseKind() == LocKind;
333 }
334};
335
336//==------------------------------------------------------------------------==//
337// Subclasses of NonLoc.
338//==------------------------------------------------------------------------==//
339
340namespace nonloc {
341
342/// Represents symbolic expression that isn't a location.
343class SymbolVal : public NonLoc {
344public:
345 SymbolVal() = delete;
346 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {
347 assert(sym);
348 assert(!Loc::isLocType(sym->getType()));
349 }
350
351 SymbolRef getSymbol() const {
352 return (const SymExpr *) Data;
353 }
354
355 bool isExpression() const {
356 return !isa<SymbolData>(getSymbol());
357 }
358
359private:
360 friend class SVal;
361
362 static bool isKind(const SVal& V) {
363 return V.getBaseKind() == NonLocKind &&
364 V.getSubKind() == SymbolValKind;
365 }
366
367 static bool isKind(const NonLoc& V) {
368 return V.getSubKind() == SymbolValKind;
369 }
370};
371
372/// Value representing integer constant.
373class ConcreteInt : public NonLoc {
374public:
375 explicit ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {}
376
377 const llvm::APSInt& getValue() const {
378 return *static_cast<const llvm::APSInt *>(Data);
379 }
380
381 // Transfer functions for binary/unary operations on ConcreteInts.
382 SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op,
383 const ConcreteInt& R) const;
384
385 ConcreteInt evalComplement(SValBuilder &svalBuilder) const;
386
387 ConcreteInt evalMinus(SValBuilder &svalBuilder) const;
388
389private:
390 friend class SVal;
391
392 ConcreteInt() = default;
393
394 static bool isKind(const SVal& V) {
395 return V.getBaseKind() == NonLocKind &&
396 V.getSubKind() == ConcreteIntKind;
397 }
398
399 static bool isKind(const NonLoc& V) {
400 return V.getSubKind() == ConcreteIntKind;
401 }
402};
403
404class LocAsInteger : public NonLoc {
405 friend class ento::SValBuilder;
406
407 explicit LocAsInteger(const std::pair<SVal, uintptr_t> &data)
408 : NonLoc(LocAsIntegerKind, &data) {
409 // We do not need to represent loc::ConcreteInt as LocAsInteger,
410 // as it'd collapse into a nonloc::ConcreteInt instead.
411 assert(data.first.getBaseKind() == LocKind &&
412 (data.first.getSubKind() == loc::MemRegionValKind ||
413 data.first.getSubKind() == loc::GotoLabelKind));
414 }
415
416public:
417 Loc getLoc() const {
418 const std::pair<SVal, uintptr_t> *D =
419 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
420 return D->first.castAs<Loc>();
421 }
422
423 Loc getPersistentLoc() const {
424 const std::pair<SVal, uintptr_t> *D =
425 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
426 const SVal& V = D->first;
427 return V.castAs<Loc>();
428 }
429
430 unsigned getNumBits() const {
431 const std::pair<SVal, uintptr_t> *D =
432 static_cast<const std::pair<SVal, uintptr_t> *>(Data);
433 return D->second;
434 }
435
436private:
437 friend class SVal;
438
439 LocAsInteger() = default;
440
441 static bool isKind(const SVal& V) {
442 return V.getBaseKind() == NonLocKind &&
443 V.getSubKind() == LocAsIntegerKind;
444 }
445
446 static bool isKind(const NonLoc& V) {
447 return V.getSubKind() == LocAsIntegerKind;
448 }
449};
450
451class CompoundVal : public NonLoc {
452 friend class ento::SValBuilder;
453
454 explicit CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {}
455
456public:
457 const CompoundValData* getValue() const {
458 return static_cast<const CompoundValData *>(Data);
459 }
460
461 using iterator = llvm::ImmutableList<SVal>::iterator;
462
463 iterator begin() const;
464 iterator end() const;
465
466private:
467 friend class SVal;
468
469 CompoundVal() = default;
470
471 static bool isKind(const SVal& V) {
472 return V.getBaseKind() == NonLocKind && V.getSubKind() == CompoundValKind;
473 }
474
475 static bool isKind(const NonLoc& V) {
476 return V.getSubKind() == CompoundValKind;
477 }
478};
479
480class LazyCompoundVal : public NonLoc {
481 friend class ento::SValBuilder;
482
483 explicit LazyCompoundVal(const LazyCompoundValData *D)
484 : NonLoc(LazyCompoundValKind, D) {}
485
486public:
487 const LazyCompoundValData *getCVData() const {
488 return static_cast<const LazyCompoundValData *>(Data);
489 }
490
491 const void *getStore() const;
492 const TypedValueRegion *getRegion() const;
493
494private:
495 friend class SVal;
496
497 LazyCompoundVal() = default;
498
499 static bool isKind(const SVal& V) {
500 return V.getBaseKind() == NonLocKind &&
501 V.getSubKind() == LazyCompoundValKind;
502 }
503
504 static bool isKind(const NonLoc& V) {
505 return V.getSubKind() == LazyCompoundValKind;
506 }
507};
508
509/// Value representing pointer-to-member.
510///
511/// This value is qualified as NonLoc because neither loading nor storing
512/// operations are applied to it. Instead, the analyzer uses the L-value coming
513/// from pointer-to-member applied to an object.
514/// This SVal is represented by a NamedDecl which can be a member function
515/// pointer or a member data pointer and an optional list of CXXBaseSpecifiers.
516/// This list is required to accumulate the pointer-to-member cast history to
517/// figure out the correct subobject field. In particular, implicit casts grow
518/// this list and explicit casts like static_cast shrink this list.
519class PointerToMember : public NonLoc {
520 friend class ento::SValBuilder;
521
522public:
523 using PTMDataType =
524 llvm::PointerUnion<const NamedDecl *, const PointerToMemberData *>;
525
526 const PTMDataType getPTMData() const {
527 return PTMDataType::getFromOpaqueValue(const_cast<void *>(Data));
528 }
529
530 bool isNullMemberPointer() const;
531
532 const NamedDecl *getDecl() const;
533
534 template<typename AdjustedDecl>
535 const AdjustedDecl *getDeclAs() const {
536 return dyn_cast_or_null<AdjustedDecl>(getDecl());
537 }
538
539 using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator;
540
541 iterator begin() const;
542 iterator end() const;
543
544private:
545 friend class SVal;
546
547 PointerToMember() = default;
548 explicit PointerToMember(const PTMDataType D)
549 : NonLoc(PointerToMemberKind, D.getOpaqueValue()) {}
550
551 static bool isKind(const SVal& V) {
552 return V.getBaseKind() == NonLocKind &&
553 V.getSubKind() == PointerToMemberKind;
554 }
555
556 static bool isKind(const NonLoc& V) {
557 return V.getSubKind() == PointerToMemberKind;
558 }
559};
560
561} // namespace nonloc
562
563//==------------------------------------------------------------------------==//
564// Subclasses of Loc.
565//==------------------------------------------------------------------------==//
566
567namespace loc {
568
569class GotoLabel : public Loc {
570public:
571 explicit GotoLabel(const LabelDecl *Label) : Loc(GotoLabelKind, Label) {
572 assert(Label);
573 }
574
575 const LabelDecl *getLabel() const {
576 return static_cast<const LabelDecl *>(Data);
577 }
578
579private:
580 friend class SVal;
581
582 GotoLabel() = default;
583
584 static bool isKind(const SVal& V) {
585 return V.getBaseKind() == LocKind && V.getSubKind() == GotoLabelKind;
586 }
587
588 static bool isKind(const Loc& V) {
589 return V.getSubKind() == GotoLabelKind;
590 }
591};
592
593class MemRegionVal : public Loc {
594public:
595 explicit MemRegionVal(const MemRegion* r) : Loc(MemRegionValKind, r) {
596 assert(r);
597 }
598
599 /// Get the underlining region.
600 const MemRegion *getRegion() const {
601 return static_cast<const MemRegion *>(Data);
602 }
603
604 /// Get the underlining region and strip casts.
605 const MemRegion* stripCasts(bool StripBaseCasts = true) const;
606
607 template <typename REGION>
608 const REGION* getRegionAs() const {
609 return dyn_cast<REGION>(getRegion());
610 }
611
612 bool operator==(const MemRegionVal &R) const {
613 return getRegion() == R.getRegion();
614 }
615
616 bool operator!=(const MemRegionVal &R) const {
617 return getRegion() != R.getRegion();
618 }
619
620private:
621 friend class SVal;
622
623 MemRegionVal() = default;
624
625 static bool isKind(const SVal& V) {
626 return V.getBaseKind() == LocKind &&
627 V.getSubKind() == MemRegionValKind;
628 }
629
630 static bool isKind(const Loc& V) {
631 return V.getSubKind() == MemRegionValKind;
632 }
633};
634
635class ConcreteInt : public Loc {
636public:
637 explicit ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {}
638
639 const llvm::APSInt &getValue() const {
640 return *static_cast<const llvm::APSInt *>(Data);
641 }
642
643 // Transfer functions for binary/unary operations on ConcreteInts.
644 SVal evalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op,
645 const ConcreteInt& R) const;
646
647private:
648 friend class SVal;
649
650 ConcreteInt() = default;
651
652 static bool isKind(const SVal& V) {
653 return V.getBaseKind() == LocKind &&
654 V.getSubKind() == ConcreteIntKind;
655 }
656
657 static bool isKind(const Loc& V) {
658 return V.getSubKind() == ConcreteIntKind;
659 }
660};
661
662} // namespace loc
663
664} // namespace ento
665
666} // namespace clang
667
668#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SVALS_H
669