Analysis/FlowSensitive/StorageLocation.h

0001 //===-- StorageLocation.h ---------------------------------------*- 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 classes that represent elements of the local variable store
0010 // and of the heap during dataflow analysis.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
0015 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H
0016
0017 #include "clang/AST/Decl.h"
0018 #include "clang/AST/Type.h"
0019 #include "llvm/ADT/DenseMap.h"
0020 #include "llvm/Support/Debug.h"
0021 #include <cassert>
0022
0023 #define DEBUG_TYPE "dataflow"
0024
0025 namespace clang {
0026 namespace dataflow {
0027
0028 /// Base class for elements of the local variable store and of the heap.
0029 ///
0030 /// Each storage location holds a value. The mapping from storage locations to
0031 /// values is stored in the environment.
0032 class StorageLocation {
0033 public:
0034   enum class Kind {
0035     Scalar,
0036     Record,
0037   };
0038
0039   StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) {
0040     assert(Type.isNull() || !Type->isReferenceType());
0041   }
0042
0043   // Non-copyable because addresses of storage locations are used as their
0044   // identities throughout framework and user code. The framework is responsible
0045   // for construction and destruction of storage locations.
0046   StorageLocation(const StorageLocation &) = delete;
0047   StorageLocation &operator=(const StorageLocation &) = delete;
0048
0049   virtual ~StorageLocation() = default;
0050
0051   Kind getKind() const { return LocKind; }
0052
0053   QualType getType() const { return Type; }
0054
0055 private:
0056   Kind LocKind;
0057   QualType Type;
0058 };
0059
0060 /// A storage location that is not subdivided further for the purposes of
0061 /// abstract interpretation. For example: `int`, `int*`, `int&`.
0062 class ScalarStorageLocation final : public StorageLocation {
0063 public:
0064   explicit ScalarStorageLocation(QualType Type)
0065       : StorageLocation(Kind::Scalar, Type) {}
0066
0067   static bool classof(const StorageLocation *Loc) {
0068     return Loc->getKind() == Kind::Scalar;
0069   }
0070 };
0071
0072 /// A storage location for a record (struct, class, or union).
0073 ///
0074 /// Contains storage locations for all modeled fields of the record (also
0075 /// referred to as "children"). The child map is flat, so accessible members of
0076 /// the base class are directly accessible as children of this location.
0077 ///
0078 /// Record storage locations may also contain so-called synthetic fields. These
0079 /// are typically used to model the internal state of a class (e.g. the value
0080 /// stored in a `std::optional`) without having to depend on that class's
0081 /// implementation details. All `RecordStorageLocation`s of a given type should
0082 /// have the same synthetic fields.
0083 ///
0084 /// The storage location for a field of reference type may be null. This
0085 /// typically occurs in one of two situations:
0086 /// - The record has not been fully initialized.
0087 /// - The maximum depth for modelling a self-referential data structure has been
0088 ///   reached.
0089 /// Storage locations for fields of all other types must be non-null.
0090 ///
0091 /// FIXME: Currently, the storage location of unions is modelled the same way as
0092 /// that of structs or classes. Eventually, we need to change this modelling so
0093 /// that all of the members of a given union have the same storage location.
0094 class RecordStorageLocation final : public StorageLocation {
0095 public:
0096   using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>;
0097   using SyntheticFieldMap = llvm::StringMap<StorageLocation *>;
0098
0099   RecordStorageLocation(QualType Type, FieldToLoc TheChildren,
0100                         SyntheticFieldMap TheSyntheticFields)
0101       : StorageLocation(Kind::Record, Type), Children(std::move(TheChildren)),
0102         SyntheticFields(std::move(TheSyntheticFields)) {
0103     assert(!Type.isNull());
0104     assert(Type->isRecordType());
0105     assert([this] {
0106       for (auto [Field, Loc] : Children) {
0107         if (!Field->getType()->isReferenceType() && Loc == nullptr)
0108           return false;
0109       }
0110       return true;
0111     }());
0112   }
0113
0114   static bool classof(const StorageLocation *Loc) {
0115     return Loc->getKind() == Kind::Record;
0116   }
0117
0118   /// Returns the child storage location for `D`.
0119   ///
0120   /// May return null if `D` has reference type; guaranteed to return non-null
0121   /// in all other cases.
0122   ///
0123   /// Note that it is an error to call this with a field that does not exist.
0124   /// The function does not return null in this case.
0125   StorageLocation *getChild(const ValueDecl &D) const {
0126     auto It = Children.find(&D);
0127     LLVM_DEBUG({
0128       if (It == Children.end()) {
0129         llvm::dbgs() << "Couldn't find child " << D.getNameAsString()
0130                      << " on StorageLocation " << this << " of type "
0131                      << getType() << "\n";
0132         llvm::dbgs() << "Existing children:\n";
0133         for ([[maybe_unused]] auto [Field, Loc] : Children) {
0134           llvm::dbgs() << Field->getNameAsString() << "\n";
0135         }
0136       }
0137     });
0138     assert(It != Children.end());
0139     return It->second;
0140   }
0141
0142   /// Returns the storage location for the synthetic field `Name`.
0143   /// The synthetic field must exist.
0144   StorageLocation &getSyntheticField(llvm::StringRef Name) const {
0145     StorageLocation *Loc = SyntheticFields.lookup(Name);
0146     assert(Loc != nullptr);
0147     return *Loc;
0148   }
0149
0150   llvm::iterator_range<SyntheticFieldMap::const_iterator>
0151   synthetic_fields() const {
0152     return {SyntheticFields.begin(), SyntheticFields.end()};
0153   }
0154
0155   /// Changes the child storage location for a field `D` of reference type.
0156   /// All other fields cannot change their storage location and always retain
0157   /// the storage location passed to the `RecordStorageLocation` constructor.
0158   ///
0159   /// Requirements:
0160   ///
0161   ///  `D` must have reference type.
0162   void setChild(const ValueDecl &D, StorageLocation *Loc) {
0163     assert(D.getType()->isReferenceType());
0164     Children[&D] = Loc;
0165   }
0166
0167   llvm::iterator_range<FieldToLoc::const_iterator> children() const {
0168     return {Children.begin(), Children.end()};
0169   }
0170
0171 private:
0172   FieldToLoc Children;
0173   SyntheticFieldMap SyntheticFields;
0174 };
0175
0176 } // namespace dataflow
0177 } // namespace clang
0178
0179 #undef DEBUG_TYPE
0180
0181 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H