forked from carbon-language/carbon-lang
-
Notifications
You must be signed in to change notification settings - Fork 0
/
arena.h
280 lines (239 loc) · 9.86 KB
/
arena.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#ifndef CARBON_EXPLORER_BASE_ARENA_H_
#define CARBON_EXPLORER_BASE_ARENA_H_
#include <any>
#include <map>
#include <memory>
#include <type_traits>
#include <unordered_map>
#include <utility>
#include <vector>
#include "explorer/base/nonnull.h"
#include "llvm/ADT/Hashing.h"
namespace Carbon {
// Adapter metafunction that converts T to a form that is usable as part of
// a key in a hash map.
//
// ArgKey<T>::type must be implicitly convertible from T, equality-comparable,
// and have a hash_value overload as defined in llvm/ADT/Hashing.h. This
// should only be customized in cases where we cannot modify T itself to
// satisfy those requirements.
template <typename T, typename = void>
struct ArgKey {
using type = T;
};
template <typename T>
using ArgKeyType = typename ArgKey<T>::type;
// Allocates and maintains ownership of arbitrary objects, so that their
// lifetimes all end at the same time. It can also canonicalize the allocated
// objects (see the documentation of New).
class Arena {
// CanonicalizeAllocation<T>::value is true if canonicalization is enabled
// for T, and false otherwise.
template <typename T, typename = void>
struct CanonicalizeAllocation;
public:
// Values of this type can be passed as the first argument to New in order to
// have the address of the created object written to the given pointer before
// the constructor is run. This is used during cloning to support pointer
// cycles within the AST.
template <typename T>
struct WriteAddressTo {
Nonnull<T**> target;
};
template <typename T>
WriteAddressTo(T** target) -> WriteAddressTo<T>;
// Returns a pointer to an object constructed as if by `T(args...)`, owned
// by this Arena.
//
// If T::EnableCanonicalizedAllocation exists and names a type, this method
// will canonicalize the allocated objects, meaning that two calls to this
// method with the same T and equal arguments will return pointers to the same
// object. If canonicalization is enabled, all types in Args... must be
// copyable, equality-comparable, and have a hash_value overload as defined in
// llvm/ADT/Hashing.h. If it's not possible to modify an argument type A to
// satisfy those requirements, the ArgKey<A> customization point can be used
// instead.
//
// Canonically-allocated objects must not be mutated, because those mutations
// would be visible to all users that happened to allocate a T object with
// the same constructor arguments. To help enforce this, the returned pointer
// will be const when canonicalization is enabled. Since that means there
// is no way to allocate a mutable instance of T, canonicalization should
// only be enabled for types that are inherently immutable.
//
// Canonicalization does not guarantee that equal objects will be identical,
// but it can substantially reduce the incidence of equal-but-not-identical
// objects, which can facilitate various optimizations.
template <
typename T, typename... Args,
typename std::enable_if_t<std::is_constructible_v<T, Args...> &&
!CanonicalizeAllocation<T>::value>* = nullptr>
auto New(Args&&... args) -> Nonnull<T*>;
template <
typename T, typename... Args,
typename std::enable_if_t<std::is_constructible_v<T, Args...> &&
CanonicalizeAllocation<T>::value>* = nullptr>
auto New(Args&&... args) -> Nonnull<const T*>;
// Allocates an object in the arena, writing its address to the given pointer.
template <
typename T, typename U, typename... Args,
typename std::enable_if_t<std::is_constructible_v<T, Args...>>* = nullptr>
void New(WriteAddressTo<U> addr, Args&&... args);
auto allocated() -> int64_t { return allocated_; }
private:
// Virtualizes arena entries so that a single vector can contain many types,
// avoiding templated statics.
class ArenaEntry {
public:
virtual ~ArenaEntry() = default;
};
// Templated destruction of a pointer.
template <typename T>
class ArenaEntryTyped;
// Hash functor implemented in terms of hash_value (see llvm/ADT/Hashing.h).
struct LlvmHasher {
template <typename T>
auto operator()(const T& t) const -> size_t {
using llvm::hash_value;
return hash_value(t);
}
};
// Factory metafunction for globally unique type IDs.
// &TypeId<T>::id == &TypeId<U>::id if and only if std::is_same_v<T,U>.
//
// Inspired by llvm::Any::TypeId.
template <typename T>
struct TypeId {
// This is only used for an address to compare; the value is unimportant.
static char id;
};
// A canonicalization table maps a tuple of constructor argument values to
// a non-null pointer to a T object constructed with those arguments.
template <typename T, typename... Args>
using CanonicalizationTable =
std::unordered_map<std::tuple<ArgKeyType<Args>...>, Nonnull<const T*>,
LlvmHasher>;
// Allocates an object in the arena. Unlike New, this will always allocate
// and construct a new object.
template <typename T, typename... Args>
auto UniqueNew(Args&&... args) -> Nonnull<T*>;
// Returns a pointer to the canonical instance of T constructed from
// `args...`, or null if there is no such instance yet. Returns a mutable
// reference so that a null entry can be updated.
template <typename T, typename... Args>
auto CanonicalInstance(const Args&... args) -> const T*&;
// Manages allocations in an arena for destruction at shutdown.
std::vector<std::unique_ptr<ArenaEntry>> arena_;
int64_t allocated_ = 0;
// Maps a CanonicalizationTable type to a unique instance of that type for
// this arena. For a key equal to &TypeId<T>::id for some T, the corresponding
// value contains a T*.
std::map<char*, std::any> canonical_tables_;
};
// ---------------------------------------
// Implementation details only below here.
// ---------------------------------------
template <>
struct ArgKey<std::nullopt_t> {
using type = struct NulloptProxy {
NulloptProxy(std::nullopt_t) {}
friend auto operator==(NulloptProxy, NulloptProxy) -> bool { return true; }
friend auto hash_value(NulloptProxy) -> llvm::hash_code {
return llvm::hash_combine();
}
};
};
template <typename T>
struct ArgKey<std::vector<T>> {
using type = class VectorProxy {
public:
VectorProxy(std::vector<T> vec) : vec_(std::move(vec)) {}
friend auto operator==(const VectorProxy& lhs, const VectorProxy& rhs) {
return lhs.vec_ == rhs.vec_;
}
friend auto hash_value(const VectorProxy& v) {
return llvm::hash_combine(
llvm::hash_combine_range(v.vec_.begin(), v.vec_.end()),
v.vec_.size());
}
private:
std::vector<T> vec_;
};
};
template <typename T, typename... Args,
typename std::enable_if_t<std::is_constructible_v<T, Args...> &&
!Arena::CanonicalizeAllocation<T>::value>*>
auto Arena::New(Args&&... args) -> Nonnull<T*> {
return UniqueNew<T>(std::forward<Args>(args)...);
}
template <typename T, typename... Args,
typename std::enable_if_t<std::is_constructible_v<T, Args...> &&
Arena::CanonicalizeAllocation<T>::value>*>
auto Arena::New(Args&&... args) -> Nonnull<const T*> {
const T*& canonical_instance = CanonicalInstance<T>(args...);
if (canonical_instance == nullptr) {
canonical_instance = UniqueNew<T>(std::forward<Args>(args)...);
}
return canonical_instance;
}
template <typename T, typename U, typename... Args,
typename std::enable_if_t<std::is_constructible_v<T, Args...>>*>
void Arena::New(WriteAddressTo<U> addr, Args&&... args) {
static_assert(!CanonicalizeAllocation<T>::value,
"This form of New does not support canonicalization yet");
arena_.push_back(
std::make_unique<ArenaEntryTyped<T>>(addr, std::forward<Args>(args)...));
allocated_ += sizeof(T);
}
template <typename T, typename... Args>
auto Arena::UniqueNew(Args&&... args) -> Nonnull<T*> {
auto smart_ptr =
std::make_unique<ArenaEntryTyped<T>>(std::forward<Args>(args)...);
Nonnull<T*> ptr = smart_ptr->Instance();
arena_.push_back(std::move(smart_ptr));
allocated_ += sizeof(T);
return ptr;
}
template <typename T, typename>
struct Arena::CanonicalizeAllocation : public std::false_type {};
template <typename T>
struct Arena::CanonicalizeAllocation<
T, std::void_t<typename T::EnableCanonicalizedAllocation>>
: public std::true_type {};
template <typename T, typename... Args>
auto Arena::CanonicalInstance(const Args&... args) -> const T*& {
using MapType = CanonicalizationTable<T, Args...>;
std::any& wrapped_table = canonical_tables_[&TypeId<MapType>::id];
if (!wrapped_table.has_value()) {
wrapped_table.emplace<MapType>();
}
MapType& table = std::any_cast<MapType&>(wrapped_table);
return table[typename MapType::key_type(args...)];
}
// Templated destruction of a pointer.
template <typename T>
class Arena::ArenaEntryTyped : public ArenaEntry {
public:
struct WriteAddressHelper {};
template <typename... Args>
explicit ArenaEntryTyped(Args&&... args)
: instance_(std::forward<Args>(args)...) {}
template <typename... Args>
explicit ArenaEntryTyped(WriteAddressHelper, Args&&... args)
: ArenaEntryTyped(std::forward<Args>(args)...) {}
template <typename U, typename... Args>
explicit ArenaEntryTyped(WriteAddressTo<U> write_address, Args&&... args)
: ArenaEntryTyped(
(*write_address.target = &instance_, WriteAddressHelper{}),
std::forward<Args>(args)...) {}
auto Instance() -> Nonnull<T*> { return Nonnull<T*>(&instance_); }
private:
T instance_;
};
template <typename T>
char Arena::TypeId<T>::id = 1;
} // namespace Carbon
#endif // CARBON_EXPLORER_BASE_ARENA_H_