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
25namespace clang {
26namespace 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.
32class StorageLocation {
33public:
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
55private:
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&`.
62class ScalarStorageLocation final : public StorageLocation {
63public:
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.
94class RecordStorageLocation final : public StorageLocation {
95public:
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
171private:
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