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