Core/PathSensitive/BasicValueFactory.h

0001 //==- BasicValueFactory.h - Basic values for Path Sens analysis --*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines BasicValueFactory, a class that manages the lifetime
0010 //  of APSInt objects and symbolic constraints used by ExprEngine
0011 //  and related classes.
0012 //
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
0016 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H
0017
0018 #include "clang/AST/ASTContext.h"
0019 #include "clang/AST/Expr.h"
0020 #include "clang/AST/Type.h"
0021 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntPtr.h"
0022 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
0023 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
0024 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
0025 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
0026 #include "llvm/ADT/APSInt.h"
0027 #include "llvm/ADT/FoldingSet.h"
0028 #include "llvm/ADT/ImmutableList.h"
0029 #include "llvm/ADT/iterator_range.h"
0030 #include "llvm/Support/Allocator.h"
0031 #include <cassert>
0032 #include <cstdint>
0033 #include <utility>
0034
0035 namespace clang {
0036
0037 class CXXBaseSpecifier;
0038
0039 namespace ento {
0040
0041 class CompoundValData : public llvm::FoldingSetNode {
0042   QualType T;
0043   llvm::ImmutableList<SVal> L;
0044
0045 public:
0046   CompoundValData(QualType t, llvm::ImmutableList<SVal> l) : T(t), L(l) {
0047     assert(NonLoc::isCompoundType(t));
0048   }
0049
0050   using iterator = llvm::ImmutableList<SVal>::iterator;
0051
0052   iterator begin() const { return L.begin(); }
0053   iterator end() const { return L.end(); }
0054
0055   QualType getType() const { return T; }
0056
0057   static void Profile(llvm::FoldingSetNodeID& ID, QualType T,
0058                       llvm::ImmutableList<SVal> L);
0059
0060   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, T, L); }
0061 };
0062
0063 class LazyCompoundValData : public llvm::FoldingSetNode {
0064   StoreRef store;
0065   const TypedValueRegion *region;
0066
0067 public:
0068   LazyCompoundValData(const StoreRef &st, const TypedValueRegion *r)
0069       : store(st), region(r) {
0070     assert(r);
0071     assert(NonLoc::isCompoundType(r->getValueType()));
0072   }
0073
0074   /// It might return null.
0075   const void *getStore() const { return store.getStore(); }
0076
0077   LLVM_ATTRIBUTE_RETURNS_NONNULL
0078   const TypedValueRegion *getRegion() const { return region; }
0079
0080   static void Profile(llvm::FoldingSetNodeID& ID,
0081                       const StoreRef &store,
0082                       const TypedValueRegion *region);
0083
0084   void Profile(llvm::FoldingSetNodeID& ID) { Profile(ID, store, region); }
0085 };
0086
0087 class PointerToMemberData : public llvm::FoldingSetNode {
0088   const NamedDecl *D;
0089   llvm::ImmutableList<const CXXBaseSpecifier *> L;
0090
0091 public:
0092   PointerToMemberData(const NamedDecl *D,
0093                       llvm::ImmutableList<const CXXBaseSpecifier *> L)
0094       : D(D), L(L) {}
0095
0096   using iterator = llvm::ImmutableList<const CXXBaseSpecifier *>::iterator;
0097
0098   iterator begin() const { return L.begin(); }
0099   iterator end() const { return L.end(); }
0100
0101   static void Profile(llvm::FoldingSetNodeID &ID, const NamedDecl *D,
0102                       llvm::ImmutableList<const CXXBaseSpecifier *> L);
0103
0104   void Profile(llvm::FoldingSetNodeID &ID) { Profile(ID, D, L); }
0105
0106   /// It might return null.
0107   const NamedDecl *getDeclaratorDecl() const { return D; }
0108
0109   llvm::ImmutableList<const CXXBaseSpecifier *> getCXXBaseList() const {
0110     return L;
0111   }
0112 };
0113
0114 class BasicValueFactory {
0115   using APSIntSetTy =
0116       llvm::FoldingSet<llvm::FoldingSetNodeWrapper<llvm::APSInt>>;
0117
0118   ASTContext &Ctx;
0119   llvm::BumpPtrAllocator& BPAlloc;
0120
0121   APSIntSetTy APSIntSet;
0122   void *PersistentSVals = nullptr;
0123   void *PersistentSValPairs = nullptr;
0124
0125   llvm::ImmutableList<SVal>::Factory SValListFactory;
0126   llvm::ImmutableList<const CXXBaseSpecifier *>::Factory CXXBaseListFactory;
0127   llvm::FoldingSet<CompoundValData>  CompoundValDataSet;
0128   llvm::FoldingSet<LazyCompoundValData> LazyCompoundValDataSet;
0129   llvm::FoldingSet<PointerToMemberData> PointerToMemberDataSet;
0130
0131   // This is private because external clients should use the factory
0132   // method that takes a QualType.
0133   APSIntPtr getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
0134
0135 public:
0136   BasicValueFactory(ASTContext &ctx, llvm::BumpPtrAllocator &Alloc)
0137       : Ctx(ctx), BPAlloc(Alloc), SValListFactory(Alloc),
0138         CXXBaseListFactory(Alloc) {}
0139
0140   ~BasicValueFactory();
0141
0142   ASTContext &getContext() const { return Ctx; }
0143
0144   APSIntPtr getValue(const llvm::APSInt &X);
0145   APSIntPtr getValue(const llvm::APInt &X, bool isUnsigned);
0146   APSIntPtr getValue(uint64_t X, QualType T);
0147
0148   /// Returns the type of the APSInt used to store values of the given QualType.
0149   APSIntType getAPSIntType(QualType T) const {
0150     // For the purposes of the analysis and constraints, we treat atomics
0151     // as their underlying types.
0152     if (const AtomicType *AT = T->getAs<AtomicType>()) {
0153       T = AT->getValueType();
0154     }
0155
0156     if (T->isIntegralOrEnumerationType() || Loc::isLocType(T)) {
0157       return APSIntType(Ctx.getIntWidth(T),
0158                         !T->isSignedIntegerOrEnumerationType());
0159     } else {
0160       // implicitly handle case of T->isFixedPointType()
0161       return APSIntType(Ctx.getIntWidth(T), T->isUnsignedFixedPointType());
0162     }
0163
0164     llvm_unreachable("Unsupported type in getAPSIntType!");
0165   }
0166
0167   /// Convert - Create a new persistent APSInt with the same value as 'From'
0168   ///  but with the bitwidth and signedness of 'To'.
0169   APSIntPtr Convert(const llvm::APSInt &To, const llvm::APSInt &From) {
0170     APSIntType TargetType(To);
0171     if (TargetType == APSIntType(From))
0172       return getValue(From);
0173
0174     return getValue(TargetType.convert(From));
0175   }
0176
0177   APSIntPtr Convert(QualType T, const llvm::APSInt &From) {
0178     APSIntType TargetType = getAPSIntType(T);
0179     return Convert(TargetType, From);
0180   }
0181
0182   APSIntPtr Convert(APSIntType TargetType, const llvm::APSInt &From) {
0183     if (TargetType == APSIntType(From))
0184       return getValue(From);
0185
0186     return getValue(TargetType.convert(From));
0187   }
0188
0189   APSIntPtr getIntValue(uint64_t X, bool isUnsigned) {
0190     QualType T = isUnsigned ? Ctx.UnsignedIntTy : Ctx.IntTy;
0191     return getValue(X, T);
0192   }
0193
0194   APSIntPtr getMaxValue(const llvm::APSInt &v) {
0195     return getValue(APSIntType(v).getMaxValue());
0196   }
0197
0198   APSIntPtr getMinValue(const llvm::APSInt &v) {
0199     return getValue(APSIntType(v).getMinValue());
0200   }
0201
0202   APSIntPtr getMaxValue(QualType T) { return getMaxValue(getAPSIntType(T)); }
0203
0204   APSIntPtr getMinValue(QualType T) { return getMinValue(getAPSIntType(T)); }
0205
0206   APSIntPtr getMaxValue(APSIntType T) { return getValue(T.getMaxValue()); }
0207
0208   APSIntPtr getMinValue(APSIntType T) { return getValue(T.getMinValue()); }
0209
0210   APSIntPtr Add1(const llvm::APSInt &V) {
0211     llvm::APSInt X = V;
0212     ++X;
0213     return getValue(X);
0214   }
0215
0216   APSIntPtr Sub1(const llvm::APSInt &V) {
0217     llvm::APSInt X = V;
0218     --X;
0219     return getValue(X);
0220   }
0221
0222   APSIntPtr getZeroWithTypeSize(QualType T) {
0223     assert(T->isScalarType());
0224     return getValue(0, Ctx.getTypeSize(T), true);
0225   }
0226
0227   APSIntPtr getTruthValue(bool b, QualType T) {
0228     return getValue(b ? 1 : 0, Ctx.getIntWidth(T),
0229                     T->isUnsignedIntegerOrEnumerationType());
0230   }
0231
0232   APSIntPtr getTruthValue(bool b) {
0233     return getTruthValue(b, Ctx.getLogicalOperationType());
0234   }
0235
0236   const CompoundValData *getCompoundValData(QualType T,
0237                                             llvm::ImmutableList<SVal> Vals);
0238
0239   const LazyCompoundValData *getLazyCompoundValData(const StoreRef &store,
0240                                             const TypedValueRegion *region);
0241
0242   const PointerToMemberData *
0243   getPointerToMemberData(const NamedDecl *ND,
0244                          llvm::ImmutableList<const CXXBaseSpecifier *> L);
0245
0246   llvm::ImmutableList<SVal> getEmptySValList() {
0247     return SValListFactory.getEmptyList();
0248   }
0249
0250   llvm::ImmutableList<SVal> prependSVal(SVal X, llvm::ImmutableList<SVal> L) {
0251     return SValListFactory.add(X, L);
0252   }
0253
0254   llvm::ImmutableList<const CXXBaseSpecifier *> getEmptyCXXBaseList() {
0255     return CXXBaseListFactory.getEmptyList();
0256   }
0257
0258   llvm::ImmutableList<const CXXBaseSpecifier *> prependCXXBase(
0259       const CXXBaseSpecifier *CBS,
0260       llvm::ImmutableList<const CXXBaseSpecifier *> L) {
0261     return CXXBaseListFactory.add(CBS, L);
0262   }
0263
0264   const PointerToMemberData *
0265   accumCXXBase(llvm::iterator_range<CastExpr::path_const_iterator> PathRange,
0266                const nonloc::PointerToMember &PTM, const clang::CastKind &kind);
0267
0268   std::optional<APSIntPtr> evalAPSInt(BinaryOperator::Opcode Op,
0269                                       const llvm::APSInt &V1,
0270                                       const llvm::APSInt &V2);
0271
0272   const std::pair<SVal, uintptr_t>&
0273   getPersistentSValWithData(const SVal& V, uintptr_t Data);
0274
0275   const std::pair<SVal, SVal>&
0276   getPersistentSValPair(const SVal& V1, const SVal& V2);
0277
0278   const SVal* getPersistentSVal(SVal X);
0279 };
0280
0281 } // namespace ento
0282
0283 } // namespace clang
0284
0285 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_BASICVALUEFACTORY_H