1//===- Optional.h - Simple variant for passing optional values --*- 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 provides Optional, a template class modeled in the spirit of
10// OCaml's 'opt' variant. The idea is to strongly type whether or not
11// a value can be optional.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_ADT_OPTIONAL_H
16#define LLVM_ADT_OPTIONAL_H
17
18#include "llvm/ADT/Hashing.h"
19#include "llvm/ADT/None.h"
20#include "llvm/Support/Compiler.h"
21#include "llvm/Support/type_traits.h"
22#include <cassert>
23#include <memory>
24#include <new>
25#include <utility>
26
27namespace llvm {
28
29class raw_ostream;
30
31namespace optional_detail {
32
33struct in_place_t {};
34
35/// Storage for any type.
36//
37// The specialization condition intentionally uses
38// llvm::is_trivially_copy_constructible instead of
39// std::is_trivially_copy_constructible. GCC versions prior to 7.4 may
40// instantiate the copy constructor of `T` when
41// std::is_trivially_copy_constructible is instantiated. This causes
42// compilation to fail if we query the trivially copy constructible property of
43// a class which is not copy constructible.
44//
45// The current implementation of OptionalStorage insists that in order to use
46// the trivial specialization, the value_type must be trivially copy
47// constructible and trivially copy assignable due to =default implementations
48// of the copy/move constructor/assignment. It does not follow that this is
49// necessarily the case std::is_trivially_copyable is true (hence the expanded
50// specialization condition).
51//
52// The move constructible / assignable conditions emulate the remaining behavior
53// of std::is_trivially_copyable.
54template <typename T, bool = (llvm::is_trivially_copy_constructible<T>::value &&
55 std::is_trivially_copy_assignable<T>::value &&
56 (std::is_trivially_move_constructible<T>::value ||
57 !std::is_move_constructible<T>::value) &&
58 (std::is_trivially_move_assignable<T>::value ||
59 !std::is_move_assignable<T>::value))>
60class OptionalStorage {
61 union {
62 char empty;
63 T value;
64 };
65 bool hasVal;
66
67public:
68 ~OptionalStorage() { reset(); }
69
70 constexpr OptionalStorage() noexcept : empty(), hasVal(false) {}
71
72 constexpr OptionalStorage(OptionalStorage const &other) : OptionalStorage() {
73 if (other.hasValue()) {
74 emplace(other.value);
75 }
76 }
77 constexpr OptionalStorage(OptionalStorage &&other) : OptionalStorage() {
78 if (other.hasValue()) {
79 emplace(std::move(other.value));
80 }
81 }
82
83 template <class... Args>
84 constexpr explicit OptionalStorage(in_place_t, Args &&... args)
85 : value(std::forward<Args>(args)...), hasVal(true) {}
86
87 void reset() noexcept {
88 if (hasVal) {
89 value.~T();
90 hasVal = false;
91 }
92 }
93
94 constexpr bool hasValue() const noexcept { return hasVal; }
95
96 T &getValue() LLVM_LVALUE_FUNCTION noexcept {
97 assert(hasVal);
98 return value;
99 }
100 constexpr T const &getValue() const LLVM_LVALUE_FUNCTION noexcept {
101 assert(hasVal);
102 return value;
103 }
104#if LLVM_HAS_RVALUE_REFERENCE_THIS
105 T &&getValue() && noexcept {
106 assert(hasVal);
107 return std::move(value);
108 }
109#endif
110
111 template <class... Args> void emplace(Args &&... args) {
112 reset();
113 ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...);
114 hasVal = true;
115 }
116
117 OptionalStorage &operator=(T const &y) {
118 if (hasValue()) {
119 value = y;
120 } else {
121 ::new ((void *)std::addressof(value)) T(y);
122 hasVal = true;
123 }
124 return *this;
125 }
126 OptionalStorage &operator=(T &&y) {
127 if (hasValue()) {
128 value = std::move(y);
129 } else {
130 ::new ((void *)std::addressof(value)) T(std::move(y));
131 hasVal = true;
132 }
133 return *this;
134 }
135
136 OptionalStorage &operator=(OptionalStorage const &other) {
137 if (other.hasValue()) {
138 if (hasValue()) {
139 value = other.value;
140 } else {
141 ::new ((void *)std::addressof(value)) T(other.value);
142 hasVal = true;
143 }
144 } else {
145 reset();
146 }
147 return *this;
148 }
149
150 OptionalStorage &operator=(OptionalStorage &&other) {
151 if (other.hasValue()) {
152 if (hasValue()) {
153 value = std::move(other.value);
154 } else {
155 ::new ((void *)std::addressof(value)) T(std::move(other.value));
156 hasVal = true;
157 }
158 } else {
159 reset();
160 }
161 return *this;
162 }
163};
164
165template <typename T> class OptionalStorage<T, true> {
166 union {
167 char empty;
168 T value;
169 };
170 bool hasVal = false;
171
172public:
173 ~OptionalStorage() = default;
174
175 constexpr OptionalStorage() noexcept : empty{} {}
176
177 constexpr OptionalStorage(OptionalStorage const &other) = default;
178 constexpr OptionalStorage(OptionalStorage &&other) = default;
179
180 OptionalStorage &operator=(OptionalStorage const &other) = default;
181 OptionalStorage &operator=(OptionalStorage &&other) = default;
182
183 template <class... Args>
184 constexpr explicit OptionalStorage(in_place_t, Args &&... args)
185 : value(std::forward<Args>(args)...), hasVal(true) {}
186
187 void reset() noexcept {
188 if (hasVal) {
189 value.~T();
190 hasVal = false;
191 }
192 }
193
194 constexpr bool hasValue() const noexcept { return hasVal; }
195
196 T &getValue() LLVM_LVALUE_FUNCTION noexcept {
197 assert(hasVal);
198 return value;
199 }
200 constexpr T const &getValue() const LLVM_LVALUE_FUNCTION noexcept {
201 assert(hasVal);
202 return value;
203 }
204#if LLVM_HAS_RVALUE_REFERENCE_THIS
205 T &&getValue() && noexcept {
206 assert(hasVal);
207 return std::move(value);
208 }
209#endif
210
211 template <class... Args> void emplace(Args &&... args) {
212 reset();
213 ::new ((void *)std::addressof(value)) T(std::forward<Args>(args)...);
214 hasVal = true;
215 }
216
217 OptionalStorage &operator=(T const &y) {
218 if (hasValue()) {
219 value = y;
220 } else {
221 ::new ((void *)std::addressof(value)) T(y);
222 hasVal = true;
223 }
224 return *this;
225 }
226 OptionalStorage &operator=(T &&y) {
227 if (hasValue()) {
228 value = std::move(y);
229 } else {
230 ::new ((void *)std::addressof(value)) T(std::move(y));
231 hasVal = true;
232 }
233 return *this;
234 }
235};
236
237} // namespace optional_detail
238
239template <typename T> class Optional {
240 optional_detail::OptionalStorage<T> Storage;
241
242public:
243 using value_type = T;
244
245 constexpr Optional() {}
246 constexpr Optional(NoneType) {}
247
248 constexpr Optional(const T &y) : Storage(optional_detail::in_place_t{}, y) {}
249 constexpr Optional(const Optional &O) = default;
250
251 constexpr Optional(T &&y)
252 : Storage(optional_detail::in_place_t{}, std::move(y)) {}
253 constexpr Optional(Optional &&O) = default;
254
255 Optional &operator=(T &&y) {
256 Storage = std::move(y);
257 return *this;
258 }
259 Optional &operator=(Optional &&O) = default;
260
261 /// Create a new object by constructing it in place with the given arguments.
262 template <typename... ArgTypes> void emplace(ArgTypes &&... Args) {
263 Storage.emplace(std::forward<ArgTypes>(Args)...);
264 }
265
266 static constexpr Optional create(const T *y) {
267 return y ? Optional(*y) : Optional();
268 }
269
270 Optional &operator=(const T &y) {
271 Storage = y;
272 return *this;
273 }
274 Optional &operator=(const Optional &O) = default;
275
276 void reset() { Storage.reset(); }
277
278 constexpr const T *getPointer() const { return &Storage.getValue(); }
279 T *getPointer() { return &Storage.getValue(); }
280 constexpr const T &getValue() const LLVM_LVALUE_FUNCTION {
281 return Storage.getValue();
282 }
283 T &getValue() LLVM_LVALUE_FUNCTION { return Storage.getValue(); }
284
285 constexpr explicit operator bool() const { return hasValue(); }
286 constexpr bool hasValue() const { return Storage.hasValue(); }
287 constexpr const T *operator->() const { return getPointer(); }
288 T *operator->() { return getPointer(); }
289 constexpr const T &operator*() const LLVM_LVALUE_FUNCTION {
290 return getValue();
291 }
292 T &operator*() LLVM_LVALUE_FUNCTION { return getValue(); }
293
294 template <typename U>
295 constexpr T getValueOr(U &&value) const LLVM_LVALUE_FUNCTION {
296 return hasValue() ? getValue() : std::forward<U>(value);
297 }
298
299 /// Apply a function to the value if present; otherwise return None.
300 template <class Function>
301 auto map(const Function &F) const LLVM_LVALUE_FUNCTION
302 -> Optional<decltype(F(getValue()))> {
303 if (*this) return F(getValue());
304 return None;
305 }
306
307#if LLVM_HAS_RVALUE_REFERENCE_THIS
308 T &&getValue() && { return std::move(Storage.getValue()); }
309 T &&operator*() && { return std::move(Storage.getValue()); }
310
311 template <typename U>
312 T getValueOr(U &&value) && {
313 return hasValue() ? std::move(getValue()) : std::forward<U>(value);
314 }
315
316 /// Apply a function to the value if present; otherwise return None.
317 template <class Function>
318 auto map(const Function &F) &&
319 -> Optional<decltype(F(std::move(*this).getValue()))> {
320 if (*this) return F(std::move(*this).getValue());
321 return None;
322 }
323#endif
324};
325
326template <class T> llvm::hash_code hash_value(const Optional<T> &O) {
327 return O ? hash_combine(true, *O) : hash_value(false);
328}
329
330template <typename T, typename U>
331constexpr bool operator==(const Optional<T> &X, const Optional<U> &Y) {
332 if (X && Y)
333 return *X == *Y;
334 return X.hasValue() == Y.hasValue();
335}
336
337template <typename T, typename U>
338constexpr bool operator!=(const Optional<T> &X, const Optional<U> &Y) {
339 return !(X == Y);
340}
341
342template <typename T, typename U>
343constexpr bool operator<(const Optional<T> &X, const Optional<U> &Y) {
344 if (X && Y)
345 return *X < *Y;
346 return X.hasValue() < Y.hasValue();
347}
348
349template <typename T, typename U>
350constexpr bool operator<=(const Optional<T> &X, const Optional<U> &Y) {
351 return !(Y < X);
352}
353
354template <typename T, typename U>
355constexpr bool operator>(const Optional<T> &X, const Optional<U> &Y) {
356 return Y < X;
357}
358
359template <typename T, typename U>
360constexpr bool operator>=(const Optional<T> &X, const Optional<U> &Y) {
361 return !(X < Y);
362}
363
364template <typename T>
365constexpr bool operator==(const Optional<T> &X, NoneType) {
366 return !X;
367}
368
369template <typename T>
370constexpr bool operator==(NoneType, const Optional<T> &X) {
371 return X == None;
372}
373
374template <typename T>
375constexpr bool operator!=(const Optional<T> &X, NoneType) {
376 return !(X == None);
377}
378
379template <typename T>
380constexpr bool operator!=(NoneType, const Optional<T> &X) {
381 return X != None;
382}
383
384template <typename T> constexpr bool operator<(const Optional<T> &, NoneType) {
385 return false;
386}
387
388template <typename T> constexpr bool operator<(NoneType, const Optional<T> &X) {
389 return X.hasValue();
390}
391
392template <typename T>
393constexpr bool operator<=(const Optional<T> &X, NoneType) {
394 return !(None < X);
395}
396
397template <typename T>
398constexpr bool operator<=(NoneType, const Optional<T> &X) {
399 return !(X < None);
400}
401
402template <typename T> constexpr bool operator>(const Optional<T> &X, NoneType) {
403 return None < X;
404}
405
406template <typename T> constexpr bool operator>(NoneType, const Optional<T> &X) {
407 return X < None;
408}
409
410template <typename T>
411constexpr bool operator>=(const Optional<T> &X, NoneType) {
412 return None <= X;
413}
414
415template <typename T>
416constexpr bool operator>=(NoneType, const Optional<T> &X) {
417 return X <= None;
418}
419
420template <typename T>
421constexpr bool operator==(const Optional<T> &X, const T &Y) {
422 return X && *X == Y;
423}
424
425template <typename T>
426constexpr bool operator==(const T &X, const Optional<T> &Y) {
427 return Y && X == *Y;
428}
429
430template <typename T>
431constexpr bool operator!=(const Optional<T> &X, const T &Y) {
432 return !(X == Y);
433}
434
435template <typename T>
436constexpr bool operator!=(const T &X, const Optional<T> &Y) {
437 return !(X == Y);
438}
439
440template <typename T>
441constexpr bool operator<(const Optional<T> &X, const T &Y) {
442 return !X || *X < Y;
443}
444
445template <typename T>
446constexpr bool operator<(const T &X, const Optional<T> &Y) {
447 return Y && X < *Y;
448}
449
450template <typename T>
451constexpr bool operator<=(const Optional<T> &X, const T &Y) {
452 return !(Y < X);
453}
454
455template <typename T>
456constexpr bool operator<=(const T &X, const Optional<T> &Y) {
457 return !(Y < X);
458}
459
460template <typename T>
461constexpr bool operator>(const Optional<T> &X, const T &Y) {
462 return Y < X;
463}
464
465template <typename T>
466constexpr bool operator>(const T &X, const Optional<T> &Y) {
467 return Y < X;
468}
469
470template <typename T>
471constexpr bool operator>=(const Optional<T> &X, const T &Y) {
472 return !(X < Y);
473}
474
475template <typename T>
476constexpr bool operator>=(const T &X, const Optional<T> &Y) {
477 return !(X < Y);
478}
479
480raw_ostream &operator<<(raw_ostream &OS, NoneType);
481
482template <typename T, typename = decltype(std::declval<raw_ostream &>()
483 << std::declval<const T &>())>
484raw_ostream &operator<<(raw_ostream &OS, const Optional<T> &O) {
485 if (O)
486 OS << *O;
487 else
488 OS << None;
489 return OS;
490}
491
492} // end namespace llvm
493
494#endif // LLVM_ADT_OPTIONAL_H
495