1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 // This file defines the |TaggedUnion| class template. It implements a tagged
18 // union, i.e. it both holds a value of one of a set of pre-determined types, as
19 // well as an enum value indicating which union member is active. The enum type
20 // used as tag and the set of union member types a specified as template
21 // parameters.
22 //
23 // For example, consider this declaration of a simple variant type:
24 //
25 //   enum VariantType {
26 //     Variant_Int = 0,
27 //     Variant_Double = 1,
28 //     Variant_Boolean = 3,
29 //     Variant_String = 2,
30 //   };
31 //
32 //   using Variant = TaggedUnion<VariantType,
33 //                        TaggedUnionMember<Variant_Int, int>,
34 //                        TaggedUnionMember<Variant_Double, double>,
35 //                        TaggedUnionMember<Variant_Boolean, bool>,
36 //                        TaggedUnionMember<Variant_String, std::string>>;
37 //
38 // |TaggedUnion::which()| can be used to determine what the active member is,
39 // and |TaggedUnion::get()| returns a pointer to the member as long as that
40 // member is active:
41 //
42 //   Variant value;
43 //   ASSERT_EQ(Variant_Int, value.which());
44 //   ASSERT_NE(nullptr, value.get<Variant_Int>());
45 //   ASSERT_EQ(0, *value.get<Variant_Int>());
46 //
47 // |TaggedUnion::Activate()| activates a member. It returns a reference to the
48 // activated member:
49 //
50 //   value.Activate<Variant_String>() = "-1";
51 //   ASSERT_EQ(Variant_String, value.which());
52 //
53 // To allow generic code to process a |TaggedUnion|, you can use a variant of
54 // what is commonly known as "the indices trick". The idea is to use template
55 // parameter pack expansion on |TaggedUnion|'s |Member| parameter to invoke some
56 // function for each member. For example, the following code determines the
57 // integer value of a |Variant| value as declared above:
58 //
59 //   template <typename Type>
60 //   void MemberToInt(const Type* member, int* value) {
61 //     if (member) {
62 //       *value = static_cast<int>(*member);
63 //     }
64 //   }
65 //
66 //   void MemberToInt(const std::string* member, int* value) {
67 //     if (member) {
68 //       *value = std::stoi(*member);
69 //     }
70 //   }
71 //
72 //   template <typename... Member>
73 //   int VariantToInt(const TaggedUnion<VariantType, Member...>& variant) {
74 //     int value = 0;
75 //     int dummy[] = {
76 //         (MemberToInt(
77 //              variant.template get<static_cast<VariantType>(Member::kTag)>(),
78 //              &value),
79 //          0)...};
80 //     (void)dummy;
81 //     return value;
82 //   };
83 //
84 // Using this, you can convert a |Variant| in arbitrary state to an integer:
85 //
86 //   ASSERT_EQ(-1, VariantToInt(value));
87 
88 #ifndef NVRAM_MESSAGES_TAGGED_UNION_H_
89 #define NVRAM_MESSAGES_TAGGED_UNION_H_
90 
91 extern "C" {
92 #include <stddef.h>
93 }
94 
95 #include <new>
96 
97 #include <nvram/messages/compiler.h>
98 
99 namespace nvram {
100 
101 template <uint64_t tag, typename Member>
102 struct TaggedUnionMember {
103   static constexpr uint64_t kTag = tag;
104   using Type = Member;
105 };
106 
107 template <typename TagType, typename... Members>
108 class TaggedUnion;
109 
110 namespace detail {
111 
112 // A compile-time maximum implementation.
113 template <size_t... Values>
114 struct Max;
115 
116 template <>
117 struct Max<> {
118   static constexpr size_t value = 0;
119 };
120 
121 template <size_t head, size_t... tail>
122 struct Max<head, tail...> {
123   static constexpr size_t value =
124       head > Max<tail...>::value ? head : Max<tail...>::value;
125 };
126 
127 // A helper template that determines the |TaggedUnionMember| type corresponding
128 // to |tag| via recursive expansion of the |Member| parameter list.
129 template <typename TagType, TagType tag, typename... Member>
130 struct MemberForTag;
131 
132 template <typename TagType,
133           TagType tag,
134           uint64_t member_tag,
135           typename MemberType,
136           typename... Tail>
137 struct MemberForTag<TagType,
138                     tag,
139                     TaggedUnionMember<member_tag, MemberType>,
140                     Tail...> {
141   using Type = typename MemberForTag<TagType, tag, Tail...>::Type;
142 };
143 
144 template <typename TagType, TagType tag, typename MemberType, typename... Tail>
145 struct MemberForTag<TagType,
146                     tag,
147                     TaggedUnionMember<static_cast<uint64_t>(tag), MemberType>,
148                     Tail...> {
149   using Type = TaggedUnionMember<tag, MemberType>;
150 };
151 
152 // Extracts the first element of its template parameter list.
153 template <typename Elem, typename...Tail>
154 struct Head {
155   using Type = Elem;
156 };
157 
158 }  // namespace detail
159 
160 template <typename TagType, typename... Member>
161 class TaggedUnion {
162  public:
163   template <TagType tag>
164   struct MemberLookup {
165     using Type = typename detail::MemberForTag<TagType, tag, Member...>::Type;
166   };
167 
168   // Construct a |TaggedUnion| object. Note that the constructor will activate
169   // the first declared union member.
170   TaggedUnion() {
171     Construct<static_cast<TagType>(detail::Head<Member...>::Type::kTag)>();
172   }
173 
174   ~TaggedUnion() {
175     Destroy();
176   }
177 
178   // |TaggedUnion| is copyable and movable, provided the members have suitable
179   // copy and move assignment operators.
180   TaggedUnion(const TaggedUnion<TagType, Member...>& other) {
181     CopyFrom(other);
182   }
183   TaggedUnion(TaggedUnion<TagType, Member...>&& other) {
184     MoveFrom(other);
185   }
186   TaggedUnion<TagType, Member...>& operator=(
187       const TaggedUnion<TagType, Member...>& other) {
188     CopyFrom(other);
189   }
190   TaggedUnion<TagType, Member...>& operator=(
191       TaggedUnion<TagType, Member...>&& other) {
192     MoveFrom(other);
193   }
194 
195   // Returns the tag value corresponding to the active member.
196   TagType which() const { return which_; }
197 
198   // Get a pointer to the member corresponding to |tag|. Returns nullptr if
199   // |tag| doesn't correspond to the active member.
200   template <TagType tag>
201   const typename MemberLookup<tag>::Type::Type* get() const {
202     return which_ == tag ? GetUnchecked<tag>() : nullptr;
203   }
204 
205   // Get a pointer to the member corresponding to |tag|. Returns nullptr if
206   // |tag| doesn't correspond to the active member.
207   template <TagType tag>
208   typename MemberLookup<tag>::Type::Type* get() {
209     return which_ == tag ? GetUnchecked<tag>() : nullptr;
210   }
211 
212   // Activate the member identified by |tag|. First, the currently active member
213   // will be destroyed. Then, the member corresponding to |tag| will be
214   // constructed (i.e. value-initialized). Returns a reference to the activated
215   // member.
216   template <TagType tag>
217   typename MemberLookup<tag>::Type::Type& Activate() {
218     Destroy();
219     Construct<tag>();
220     return *GetUnchecked<tag>();
221   }
222 
223  private:
224   template<TagType tag>
225   const typename MemberLookup<tag>::Type::Type* GetUnchecked() const {
226     return reinterpret_cast<const typename MemberLookup<tag>::Type::Type*>(
227         storage_);
228   }
229 
230   template<TagType tag>
231   typename MemberLookup<tag>::Type::Type* GetUnchecked() {
232     return reinterpret_cast<typename MemberLookup<tag>::Type::Type*>(storage_);
233   }
234 
235   template <TagType tag>
236   void Construct() {
237     using MemberType = typename MemberLookup<tag>::Type::Type;
238     new (storage_) MemberType();
239     which_ = tag;
240   }
241 
242   template <typename CurrentMember>
243   void DestroyMember() {
244     using MemberType = typename CurrentMember::Type;
245     if (CurrentMember::kTag == which_) {
246       GetUnchecked<static_cast<TagType>(CurrentMember::kTag)>()->~MemberType();
247     }
248   }
249 
250   // This is marked noinline to prevent bloat due to the compiler inlining
251   // |Destroy()| into each instance of the |Activate()| function.
252   NVRAM_NOINLINE void Destroy() {
253     int dummy[] = {(DestroyMember<Member>(), 0)...};
254     (void)dummy;
255   }
256 
257   template <typename CurrentMember>
258   void CopyMember(const typename CurrentMember::Type* member) {
259     if (member) {
260       if (CurrentMember::kTag != which_) {
261         Activate<CurrentMember::kTag>();
262       }
263       *GetUnchecked<static_cast<TagType>(CurrentMember::kTag)>() = *member;
264     }
265   }
266 
267   NVRAM_NOINLINE void CopyFrom(const TaggedUnion<TagType, Member...>& other) {
268     int dummy[] = {
269         (CopyMember<Member>(
270              other.template get<static_cast<TagType>(Member::kTag)>()),
271          0)...};
272     (void)dummy;
273   }
274 
275   template <typename CurrentMember>
276   void MoveMember(const typename CurrentMember::Type* member) {
277     if (member) {
278       if (CurrentMember::kTag != which_) {
279         Activate<CurrentMember::kTag>();
280       }
281       *GetUnchecked<static_cast<TagType>(CurrentMember::kTag)>() =
282           static_cast<typename CurrentMember::Type&&>(*member);
283     }
284   }
285 
286   NVRAM_NOINLINE void MoveFrom(const TaggedUnion<TagType, Member...>& other) {
287     int dummy[] = {
288         (MoveMember<Member>(
289              other.template get<static_cast<TagType>(Member::kTag)>()),
290          0)...};
291     (void)dummy;
292   }
293 
294   // The + 0 is required to work around a G++ bug:
295   // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55382
296   alignas(detail::Max<alignof(typename Member::Type)...>::value + 0)
297       uint8_t storage_[detail::Max<sizeof(typename Member::Type)...>::value];
298   TagType which_;
299 };
300 
301 }  // namespace nvram
302 
303 #endif  // NVRAM_MESSAGES_TAGGED_UNION_H_
304