1 | //===-- StorageLocation.h ---------------------------------------*- 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 classes that represent elements of the local variable store |
10 | // and of the heap during dataflow analysis. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H |
15 | #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H |
16 | |
17 | #include "clang/AST/Decl.h" |
18 | #include "clang/AST/Type.h" |
19 | #include "llvm/ADT/DenseMap.h" |
20 | #include "llvm/Support/Debug.h" |
21 | #include <cassert> |
22 | |
23 | #define DEBUG_TYPE "dataflow" |
24 | |
25 | namespace clang { |
26 | namespace dataflow { |
27 | |
28 | /// Base class for elements of the local variable store and of the heap. |
29 | /// |
30 | /// Each storage location holds a value. The mapping from storage locations to |
31 | /// values is stored in the environment. |
32 | class StorageLocation { |
33 | public: |
34 | enum class Kind { |
35 | Scalar, |
36 | Record, |
37 | }; |
38 | |
39 | StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) { |
40 | assert(Type.isNull() || !Type->isReferenceType()); |
41 | } |
42 | |
43 | // Non-copyable because addresses of storage locations are used as their |
44 | // identities throughout framework and user code. The framework is responsible |
45 | // for construction and destruction of storage locations. |
46 | StorageLocation(const StorageLocation &) = delete; |
47 | StorageLocation &operator=(const StorageLocation &) = delete; |
48 | |
49 | virtual ~StorageLocation() = default; |
50 | |
51 | Kind getKind() const { return LocKind; } |
52 | |
53 | QualType getType() const { return Type; } |
54 | |
55 | private: |
56 | Kind LocKind; |
57 | QualType Type; |
58 | }; |
59 | |
60 | /// A storage location that is not subdivided further for the purposes of |
61 | /// abstract interpretation. For example: `int`, `int*`, `int&`. |
62 | class ScalarStorageLocation final : public StorageLocation { |
63 | public: |
64 | explicit ScalarStorageLocation(QualType Type) |
65 | : StorageLocation(Kind::Scalar, Type) {} |
66 | |
67 | static bool classof(const StorageLocation *Loc) { |
68 | return Loc->getKind() == Kind::Scalar; |
69 | } |
70 | }; |
71 | |
72 | /// A storage location for a record (struct, class, or union). |
73 | /// |
74 | /// Contains storage locations for all modeled fields of the record (also |
75 | /// referred to as "children"). The child map is flat, so accessible members of |
76 | /// the base class are directly accessible as children of this location. |
77 | /// |
78 | /// Record storage locations may also contain so-called synthetic fields. These |
79 | /// are typically used to model the internal state of a class (e.g. the value |
80 | /// stored in a `std::optional`) without having to depend on that class's |
81 | /// implementation details. All `RecordStorageLocation`s of a given type should |
82 | /// have the same synthetic fields. |
83 | /// |
84 | /// The storage location for a field of reference type may be null. This |
85 | /// typically occurs in one of two situations: |
86 | /// - The record has not been fully initialized. |
87 | /// - The maximum depth for modelling a self-referential data structure has been |
88 | /// reached. |
89 | /// Storage locations for fields of all other types must be non-null. |
90 | /// |
91 | /// FIXME: Currently, the storage location of unions is modelled the same way as |
92 | /// that of structs or classes. Eventually, we need to change this modelling so |
93 | /// that all of the members of a given union have the same storage location. |
94 | class RecordStorageLocation final : public StorageLocation { |
95 | public: |
96 | using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>; |
97 | using SyntheticFieldMap = llvm::StringMap<StorageLocation *>; |
98 | |
99 | RecordStorageLocation(QualType Type, FieldToLoc TheChildren, |
100 | SyntheticFieldMap TheSyntheticFields) |
101 | : StorageLocation(Kind::Record, Type), Children(std::move(TheChildren)), |
102 | SyntheticFields(std::move(TheSyntheticFields)) { |
103 | assert(!Type.isNull()); |
104 | assert(Type->isRecordType()); |
105 | assert([this] { |
106 | for (auto [Field, Loc] : Children) { |
107 | if (!Field->getType()->isReferenceType() && Loc == nullptr) |
108 | return false; |
109 | } |
110 | return true; |
111 | }()); |
112 | } |
113 | |
114 | static bool classof(const StorageLocation *Loc) { |
115 | return Loc->getKind() == Kind::Record; |
116 | } |
117 | |
118 | /// Returns the child storage location for `D`. |
119 | /// |
120 | /// May return null if `D` has reference type; guaranteed to return non-null |
121 | /// in all other cases. |
122 | /// |
123 | /// Note that it is an error to call this with a field that does not exist. |
124 | /// The function does not return null in this case. |
125 | StorageLocation *getChild(const ValueDecl &D) const { |
126 | auto It = Children.find(Val: &D); |
127 | LLVM_DEBUG({ |
128 | if (It == Children.end()) { |
129 | llvm::dbgs() << "Couldn't find child " << D.getNameAsString() |
130 | << " on StorageLocation " << this << " of type " |
131 | << getType() << "\n" ; |
132 | llvm::dbgs() << "Existing children:\n" ; |
133 | for ([[maybe_unused]] auto [Field, Loc] : Children) { |
134 | llvm::dbgs() << Field->getNameAsString() << "\n" ; |
135 | } |
136 | } |
137 | }); |
138 | assert(It != Children.end()); |
139 | return It->second; |
140 | } |
141 | |
142 | /// Returns the storage location for the synthetic field `Name`. |
143 | /// The synthetic field must exist. |
144 | StorageLocation &getSyntheticField(llvm::StringRef Name) const { |
145 | StorageLocation *Loc = SyntheticFields.lookup(Key: Name); |
146 | assert(Loc != nullptr); |
147 | return *Loc; |
148 | } |
149 | |
150 | llvm::iterator_range<SyntheticFieldMap::const_iterator> |
151 | synthetic_fields() const { |
152 | return {SyntheticFields.begin(), SyntheticFields.end()}; |
153 | } |
154 | |
155 | /// Changes the child storage location for a field `D` of reference type. |
156 | /// All other fields cannot change their storage location and always retain |
157 | /// the storage location passed to the `RecordStorageLocation` constructor. |
158 | /// |
159 | /// Requirements: |
160 | /// |
161 | /// `D` must have reference type. |
162 | void setChild(const ValueDecl &D, StorageLocation *Loc) { |
163 | assert(D.getType()->isReferenceType()); |
164 | Children[&D] = Loc; |
165 | } |
166 | |
167 | llvm::iterator_range<FieldToLoc::const_iterator> children() const { |
168 | return {Children.begin(), Children.end()}; |
169 | } |
170 | |
171 | private: |
172 | FieldToLoc Children; |
173 | SyntheticFieldMap SyntheticFields; |
174 | }; |
175 | |
176 | } // namespace dataflow |
177 | } // namespace clang |
178 | |
179 | #undef DEBUG_TYPE |
180 | |
181 | #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H |
182 | |