1 /*
2 * Copyright 2019 Google LLC
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 /**
18 * This file provides general utilities for metaprogramming.
19 *
20 * - LIFT_MEMBER_TO_TYPE: Generates distinct types in correspondence with
21 * member-pointers (for both fields and functions). For example,
22 * LIFT_MEMBER_TO_TYPE(S, X) != LIFT_MEMBER_TO_TYPE(R, X), even if the
23 * declarations of S::X and R::X are identical.
24 *
25 * - Unit: An empty struct (i.e. has a single canonical element). It is useful
26 * in contexts where a non-void return type is necessary but undesired: for
27 * example, in a constexpr function called only for static_asserts.
28 *
29 * - Pack<T...>: Helps passing around the 'parameter packs' arising from
30 * variadic templates (they are not first-class). In particular, these allow
31 * writing a function such that F<A, B>() and F<Pack<A, B>>() are equivalent
32 * (Pack<A, B> _is_ first-class).
33 *
34 * - MemberPointerTraits: Allows removing the 'container' part from
35 * member-pointer types, e.g.
36 * 'R T::*' => 'R'
37 * 'R (T::*)(A, B)' => 'R(A, B)'
38 *
39 * - FunctionTraits: Allows destructuring function types, e.g. 'bool(int,
40 * int)' into ResultType = bool, ArgPackType = Pack<int, int>.
41 *
42 * - FailIfReached: Allows writing static_asserts for templates that should
43 * never be instantiated. This is a workaround for the fact that
44 * 'static_assert(false, "")' can trigger regardless of where it's located.
45 *
46 * - Identity<T>: An alias useful with higher order templates.
47 *
48 * - CastContainerElements: Allows 'casting' homogenous containers to
49 * heterogenous tuples, e.g. vector<X> -> tuple<A, B> - useful when
50 * when the type-list was erased earlier.
51 *
52 * - LiftVoidReturn: Wraps a callable object, so that returned 'void' becomes
53 * 'Unit' (if applicable). This avoids spread of special cases when handling
54 * callables and function-types generically (e.g. 'auto r = f()' is valid
55 * for f() returning anything _except_ void).
56 *
57 * - MAKE_LINK and LinkedType<T>: Given types T, U and MAKE_LINK(T, U),
58 * LinkedType<T> == U. This can often be handled with template
59 * specialization, but (like AbslHashValue) we use ADL so that T (and
60 * MAKE_LINK next to it) can appear in any namespace.
61 *
62 * - IsTypeOneOf<T, Us...>: A function to determines if the type T is in the
63 * list of types Us.
64 *
65 * - IsSubsetOf<Pack<Ts...>, Pack<Us...>>: Determins if a pack of types Ts
66 * is a subset of a pack of types Us.
67 */
68
69 #ifndef FCP_BASE_META_H_
70 #define FCP_BASE_META_H_
71
72 #include <tuple>
73 #include <type_traits>
74
75 #include "fcp/base/monitoring.h"
76
77 namespace fcp {
78
79 /**
80 * An empty struct - i.e. there is a single canonical element.
81 *
82 * It is useful in contexts where a non-void return type is necessary but
83 * undesired: for example, in a constexpr function called only for
84 * static_asserts.
85 *
86 * Unit defines equality (they're always equal). True() always returns true,
87 * which is convenient for allowing a unit-returning function call in a
88 * static_assert.
89 *
90 * Unit::Ignore(...) sinks any arguments to a Unit. This is useful in C++11's
91 * restricted constexpr as well as for parameter-pack expansions.
92 */
93 struct Unit {
94 constexpr bool operator==(Unit other) const { return true; }
95 constexpr bool operator!=(Unit other) const { return !(*this == other); }
TrueUnit96 constexpr bool True() const { return true; }
97
98 /** Ignores all arguments (of any type), returning Unit */
99 template <typename... ArgTypes>
IgnoreUnit100 static constexpr Unit Ignore(ArgTypes... args) {
101 return {};
102 }
103 };
104
105 /**
106 * Pack<T...> facilitates passing around a parameter-pack T...
107 *
108 * Types are more or less first-class, in that you can place one somewhere (e.g.
109 * as a struct member) and use it later. This is not the case for
110 * parameter-packs: one can only expand T... within some template<typename...
111 * T>.
112 *
113 * Pack<> is a work-around for that:
114 *
115 * - To store a parameter-pack T... in hand: Instead store Pack<T...>, e.g.
116 * 'using P = Pack<T...>'
117 *
118 * - To revitalize the parameter pack later: Define a target function like
119 * template<typename... T> F(Pack<T...>)
120 * and call it as
121 * F(P{})
122 * (noting P from the prior example). The T... in scope of F arises from
123 * template argument deduction.
124 */
125 template <typename... T>
126 struct Pack {
127 /** Returns the related index-sequence type.
128 *
129 * Example:
130 *
131 * template <typename... T, size_t... Idx>
132 * void Impl(Pack<T...>, absl::index_sequence<Idx...>) {
133 * auto zipped[] = {
134 * F<T>(Idx)... // T... and Idx... are zipped together.
135 * };
136 * }
137 *
138 * template <typename... T>
139 * void Foo(Pack<T...> pack) {
140 * Impl(pack, pack.MakeIndexSequence());
141 * }
142 */
MakeIndexSequencePack143 static constexpr absl::index_sequence_for<T...> MakeIndexSequence() {
144 return {};
145 }
146 };
147
148 /**
149 * Workaround for static_assert(false) tripping even for un-instantiated
150 * templates.
151 */
152 template <typename T>
FailIfReached()153 constexpr bool FailIfReached() {
154 return !std::is_same<T, T>::value;
155 }
156
157 namespace meta_internal {
158
159 template <typename T, T M>
160 struct MemberTag {
161 static_assert(std::is_member_pointer<T>::value,
162 "Expected a member-pointer type");
163 };
164
165 template <typename CastOp, typename... T>
166 using CastResultType = std::tuple<typename CastOp::template TargetType<T>...>;
167
168 template <typename... T, size_t... Idx, typename Container, typename CastOp>
CastContainerElementsImpl(Container const & container,CastOp const & cast,Pack<T...>,absl::index_sequence<Idx...>)169 CastResultType<CastOp, T...> CastContainerElementsImpl(
170 Container const& container, CastOp const& cast, Pack<T...>,
171 absl::index_sequence<Idx...>) {
172 FCP_CHECK(sizeof...(T) == container.size());
173 return CastResultType<CastOp, T...>{cast.template Cast<T>(container[Idx])...};
174 }
175
176 template <typename F>
177 class VoidLifter {
178 private:
179 template <typename T>
180 struct Tag {};
181
182 template <typename... A>
DoCall(Tag<void>,A &&...args)183 Unit DoCall(Tag<void>, A&&... args) {
184 f_(std::forward<A>(args)...);
185 return {};
186 }
187
188 template <typename R, typename... A>
DoCall(Tag<R>,A &&...args)189 R DoCall(Tag<R>, A&&... args) {
190 return f_(std::forward<A>(args)...);
191 }
192
193 public:
VoidLifter(F f)194 explicit VoidLifter(F f) : f_(std::move(f)) {}
195
196 template <typename... A>
197 auto operator()(A&&... args) -> decltype(
198 DoCall(Tag<decltype(std::declval<F>()(std::forward<A>(args)...))>{},
199 std::forward<A>(args)...)) {
200 return DoCall(Tag<decltype(std::declval<F>()(std::forward<A>(args)...))>{},
201 std::forward<A>(args)...);
202 }
203
204 private:
205 F f_;
206 };
207
208 template <typename U, typename Dummy = void>
209 struct FailIfLinkMissing {
210 using Type = U;
211 };
212
213 template <typename Dummy>
214 struct FailIfLinkMissing<void, Dummy> {
215 static_assert(FailIfReached<Dummy>(),
216 "Expected a type linked from T, via MAKE_LINK(T, U). Note that "
217 "MAKE_LINK must appear in the same namespace as T.");
218 };
219
220 template <typename T>
221 struct LinkedTypeToken {
222 using Type = T;
223 };
224
225 /**
226 * Default case for LookupTypeLink. MAKE_LINK creates overloads which are more
227 * specific (argument type matches without needing a template).
228 */
229 template <typename T>
230 inline LinkedTypeToken<void> TypeLink_(LinkedTypeToken<T>) {
231 return {};
232 }
233
234 /**
235 * Resolves MAKE_LINK at the level of values (i.e. the link target is
236 * represented in the return type). May be called qualified, i.e.
237 * fcp::meta_internal::LookupTypeLink.
238 *
239 * This depends on ADL. TypeLink_ is an unqualified name, so those next to T are
240 * overload candidates. As such, it's fine to call meta_internal::LookupTypeLink
241 * but *not* meta_internal::TypeLink_ (hence this indirection).
242 */
243 template <typename T>
244 constexpr auto LookupTypeLink(LinkedTypeToken<T> t) -> decltype(TypeLink_(t)) {
245 return {};
246 }
247
248 template <template <typename> class M, typename Z>
249 struct UnwrapTemplateImpl {
250 static constexpr bool kValid = false;
251
252 struct Type {
253 static_assert(FailIfReached<Z>(), "Z must be M<T> for some type T");
254 };
255 };
256
257 template <template <typename> class M, typename T>
258 struct UnwrapTemplateImpl<M, M<T>> {
259 static constexpr bool kValid = true;
260 using Type = T;
261 };
262
263 template <template <typename> class M, typename Z>
264 using UnwrapTemplate = meta_internal::UnwrapTemplateImpl<M, std::decay_t<Z>>;
265
266 } // namespace meta_internal
267
268 /**
269 * Generates distinct types in correspondence with member-pointers (for both
270 * fields and functions).
271 *
272 * For example, LIFT_MEMBER_TO_TYPE(S, X) != LIFT_MEMBER_TO_TYPE(R, X), even if
273 * the declarations of S::X and R::X are identical.
274 *
275 * The lifted type is always an empty struct, so it can be instantiated with {}
276 * (for use in overload resolution) at no cost.
277 */
278 #define LIFT_MEMBER_TO_TYPE(type, member) \
279 LIFT_MEMBER_POINTER_TO_TYPE(&type::member)
280
281 /**
282 * Same as LIFT_MEMBER_TO_TYPE, but invoked as e.g.
283 * LIFT_MEMBER_POINTER_TO_TYPE(&S::X)
284 */
285 #define LIFT_MEMBER_POINTER_TO_TYPE(ptr) \
286 ::fcp::meta_internal::MemberTag<decltype(ptr), ptr>
287
288 /**
289 * Allows removing the 'container' part from member-pointer types, e.g.
290 * 'R T::*' => 'R' 'R (T::*)(A, B)' => 'R(A, B)'
291 */
292 template <typename T>
293 struct MemberPointerTraits {
294 static_assert(
295 FailIfReached<T>(),
296 "Expected a member pointer (both fields and functions are accepted)");
297 };
298
299 template <typename T, typename R>
300 struct MemberPointerTraits<R T::*> {
301 using TargetType = R;
302 };
303
304 template <typename T>
305 struct FunctionTraits {
306 static_assert(FailIfReached<T>(), "Expected a function type");
307 };
308
309 template <typename R, typename... A>
310 struct FunctionTraits<R(A...)> {
311 using ResultType = R;
312 using ArgPackType = Pack<A...>;
313 };
314
315 /** Type-level identity function; useful for higher order templates */
316 template <typename T>
317 using Identity = T;
318
319 /** See other overload; this one takes a Pack<T...> instead of explicit T... */
320 template <typename... T, typename Container, typename CastOp>
321 auto CastContainerElements(Pack<T...> pack, Container const& container,
322 CastOp const& cast)
323 -> decltype(meta_internal::CastContainerElementsImpl(
324 container, cast, pack, pack.MakeIndexSequence())) {
325 return meta_internal::CastContainerElementsImpl(container, cast, pack,
326 pack.MakeIndexSequence());
327 }
328
329 /**
330 * Allows 'casting' homogenous containers to heterogenous tuples, e.g.
331 * vector<X> -> tuple<A, B> - useful when when the type-list was erased
332 * earlier.
333 *
334 * 'CastOp' determines how to cast each element. It should be a type like the
335 * following:
336 *
337 * struct FooCast {
338 * template<typename T>
339 * using TargetType = Y<T>;
340 *
341 * template <typename T>
342 * TargetType<T> Cast(X const& val) const {
343 * ...
344 * }
345 * };
346 *
347 * Supposing vector<X> vx, CastContainerElements<A, B>(vx, FooCast{}) would
348 * yield a tuple<Y<A>, Y<B>> with values {Cast<A>(vx[0]), Cast<B>(vx[1])}.
349 *
350 * This function supports the 'Pack' wrapper. For example, the previous example
351 * could also be written as CastContainerElements(Pack<X, Y>{}, vx, FooCast{}).
352 */
353 template <typename... T, typename Container, typename CastOp>
354 auto CastContainerElements(Container const& container, CastOp const& cast)
355 -> decltype(CastContainerElements(Pack<T...>{}, container, cast)) {
356 return CastContainerElements(Pack<T...>{}, container, cast);
357 }
358
359 /**
360 * Wraps a callable object, so that returned 'void' becomes 'Unit' (if
361 * applicable). This avoids spread of special cases when handling callables and
362 * function-types generically (e.g. 'auto r = f()' is valid for f() returning
363 * anything _except_ void).
364 */
365 template <typename F>
366 meta_internal::VoidLifter<F> LiftVoidReturn(F f) {
367 return meta_internal::VoidLifter<F>(std::move(f));
368 }
369
370 /** See LinkedType<T> */
371 #define MAKE_LINK(a, b) \
372 inline ::fcp::meta_internal::LinkedTypeToken<b> TypeLink_( \
373 ::fcp::meta_internal::LinkedTypeToken<a>) { \
374 return {}; \
375 }
376
377 /**
378 * See LinkedType<T>. This form returns void instead of failing when a link is
379 * missing
380 */
381 template <typename T>
382 using LinkedTypeOrVoid = typename decltype(meta_internal::LookupTypeLink(
383 std::declval<meta_internal::LinkedTypeToken<T>>()))::Type;
384
385 /**
386 * Indicates if some MAKE_LINK(T, ...) is visible.
387 */
388 template <typename T>
389 constexpr bool HasLinkedType() {
390 return !std::is_same<LinkedTypeOrVoid<T>, void>::value;
391 }
392
393 /**
394 * Given types T, U and MAKE_LINK(T, U), LinkedType<T> == U.
395 *
396 * This can often be handled with template specialization, but (like
397 * AbslHashValue) we use ADL to avoid restrictions on the namespaces in which
398 * specializations can appear.
399 *
400 * The type T can appear in any namespace, but MAKE_LINK(T, U) must appear in
401 * the same namespace (ideally, place it right after the declaration of T).
402 * LinkedType<T> then works in any namespace.
403 *
404 * It is an error to use this alias for a T without a MAKE_LINK. See
405 * HasLinkedType() and LinkedTypeOrVoid.
406 */
407 template <typename T>
408 using LinkedType =
409 typename meta_internal::FailIfLinkMissing<LinkedTypeOrVoid<T>>::Type;
410
411
412 /*
413 * Given type T and typelist Us... determines if T is one of the types in Us.
414 */
415 template <typename T, typename... Us>
416 struct IsTypeOneOfT : std::disjunction<std::is_same<T, Us>...> {};
417
418 template <typename T, typename... Us>
419 constexpr bool IsTypeOneOf() {
420 return IsTypeOneOfT<T, Us...>::value;
421 }
422
423 /*
424 * Given two typelists Ts... and Us... determines if Ts is a subset of Us.
425 */
426 template <typename Ts, typename Us>
427 struct IsSubsetOf : std::false_type {};
428
429 template <typename... Ts, typename... Us>
430 struct IsSubsetOf<Pack<Ts...>, Pack<Us...>>
431 : std::conjunction<IsTypeOneOfT<Ts, Us...>...> {};
432
433 template <template <typename> class M, typename Z>
434 using UnapplyTemplate =
435 typename meta_internal::UnwrapTemplateImpl<M, std::decay_t<Z>>::Type;
436
437 template <template <typename> class M, typename Z>
438 constexpr bool IsAppliedTemplate() {
439 return meta_internal::UnwrapTemplateImpl<M, std::decay_t<Z>>::kValid;
440 }
441
442 } // namespace fcp
443
444 #endif // FCP_BASE_META_H_
445