Audacity 3.2.0
TypeList.h
Go to the documentation of this file.
1/*!********************************************************************
2
3 Audacity: A Digital Audio Editor
4
5 @file TypeList.h
6 @brief Metaprogramming utilities for manipulating lists of types
7
8 See examples of use in TypeList.cpp
9
10 Paul Licameli
11
12**********************************************************************/
13#ifndef __AUDACITY_TYPELIST__
14#define __AUDACITY_TYPELIST__
15
16#include <cstddef>
17#include <tuple>
18#include <type_traits>
19#include <utility>
20
22namespace TypeList {
23
24/*
25 Some of these utilities use "metafunctions." These are classes with a nested
26 class template or type alias template, named `typemap`, which takes one type
27 parameter.
28
29 The template `Fn` takes such class templates or type alias templates and adapts
30 them to this convention. It can also compose such templates.
31
32 Some utilities require a predicate, which means a metafunction that produces
33 types that have an embedded static constexpr member called `value` and
34 convertible to bool.
35
36 Many utilities define a nested type `type` and an associated type alias ending
37 in `_t` that forces template expansion of that type.
38
39 Sometimes specialization of the template causes no compilation error while any
40 use of the `type` in the specialization (outside of a sfinae context) would.
41 It can be useful for such a template to be an alternative in
42 `typename std::conditional_t<test, Alt1, Alt2>::type`
43 where the `test` chooses the other alternative. Think of this as a
44 metaprogramming equivalent of null pointer checking.
45
46 The lists are not lazy. The size and member types of a TypeList specialization
47 are always defined.
48
49 (That is, tere is no attempt here to implement meta-iterators of lists of
50 undetermined length, that determine their tail types only when required by
51 template substitution.)
52
53 However there is short-circuit evaluation of alternatives in And and Or, which
54 can make compound predicates out of simpler ones.
55 */
56
58template<typename T> struct type_identity { using type = T; };
59
61template<typename... Types> struct List;
63template<> struct List<> {
64 static constexpr size_t length = 0;
65 static constexpr bool null = true;
66};
68template<typename Type, typename... Types> struct List<Type, Types...> {
69 static constexpr size_t length = sizeof...(Types);
70 static constexpr bool null = false;
71 using head = Type;
72 using tail = List<Types...>;
73};
74
75using Nil = List<>;
76
77template<typename TypeList> struct Null;
78template<typename TypeList> constexpr auto Null_v = Null<TypeList>::value;
79template<typename... Types> struct Null<List<Types...>>
80 : std::bool_constant<sizeof...(Types) == 0> {};
81
82template<typename TypeList> struct Length;
83template<typename TypeList> using Length_t = typename Length<TypeList>::type;
84template<typename TypeList> constexpr auto Length_v = Length_t<TypeList>::value;
85template<typename... Types> struct Length<List<Types...>>
86 : std::integral_constant<size_t, sizeof...(Types)>{};
87
89template<typename TypeList> struct Head;
95template<typename TypeList> using Head_t = typename Head<TypeList>::type;
96template<typename... Types> struct Head<List<Types...>> {
97 using type = typename List<Types...>::head;
98};
99
101template<typename TypeList> struct Tail;
107template<typename TypeList> using Tail_t = typename Tail<TypeList>::type;
108template<typename... Types> struct Tail<List<Types...>> {
109 using type = typename List<Types...>::tail;
110};
111
113template<typename TypeList> using Rest = Tail<TypeList>;
114template<typename TypeList> using Rest_t = Tail_t<TypeList>;
115
116template<size_t N, typename TypeList> struct Nth {
117private:
118 template<size_t I, typename TL> struct Countdown {
119 using type = typename Countdown<I - 1, Tail_t<TL>>::type;
120 };
121 template<typename TL> struct Countdown<0, TL> {
123 };
124public:
126};
127template<size_t N, typename TypeList> using Nth_t =
128 typename Nth<N, TypeList>::type;
129
133template<typename TypeList> using First = Nth<0, TypeList>;
134template<typename TypeList> using First_t = typename First<TypeList>::type;
135
136template<typename TypeList> using Second = Nth<1, TypeList>;
137template<typename TypeList> using Second_t = typename Second<TypeList>::type;
138
140template<typename Type, typename TypeList> struct Cons;
141template<typename Type, typename TypeList> using Cons_t =
143template<typename Type, typename... Types> struct Cons<Type, List<Types...>> {
144 using type = List<Type, Types...>;
145};
146
148template<typename TypeList, typename Type> struct PushFront
149 : Cons<Type, TypeList> {};
150template<typename TypeList, typename Type> using PushFront_t =
152
154template<typename TypeList, typename Type> struct PushBack;
155template<typename TypeList, typename Type> using PushBack_t =
157template<typename Type, typename... Types> struct
158PushBack<List<Types...>, Type> { using type = List<Types..., Type>; };
159
162template<typename TypeList> struct NonEmptyTails {
163private:
164 struct Next { using type =
166 };
167public:
168 using type = typename std::conditional_t<
169 Null_v<TypeList>, type_identity<Nil>, Next
170 >::type;
171};
172template<typename TypeList> using NonEmptyTails_t =
174
177template<typename TypeList> struct Tails {
179};
180template<typename TypeList> using Tails_t = typename Tails<TypeList>::type;
181
182template<typename TypeList> struct Last;
183template<typename TypeList> using Last_t = typename Last<TypeList>::type;
184template<typename Type> struct Last<List<Type>> { using type = Type; };
185template<typename Type, typename... Types> struct Last<List<Type, Types...>> {
186 using type = Last_t<List<Types...>>;
187};
188
189template<typename TypeList> struct ButLast;
190template<typename TypeList> using ButLast_t = typename ButLast<TypeList>::type;
191template<typename Type> struct ButLast<List<Type>> { using type = Nil; };
192template<typename Type, typename... Types>
193struct ButLast<List<Type, Types...>> {
194 using type = Cons_t<Type, ButLast_t<List<Types...>>>;
195};
196
199template<template<typename> class... Template> struct Fn;
200template<> struct Fn<> { template<typename T> using typemap = T; };
201template<template<typename> class Template,
202 template<typename> class... Templates>
203struct Fn<Template, Templates...> {
204 template<typename T> using typemap =
205 Template<typename Fn<Templates...>::template typemap<T>>;
206};
207
210template<typename... Metafunctions> struct Compose;
211template<> struct Compose<> { template<typename T> using typemap = T; };
212template<typename Metafunction, typename... Metafunctions>
213struct Compose<Metafunction, Metafunctions...> {
214 template<typename T> using typemap = typename Metafunction::template typemap<
215 typename Compose<Metafunctions...>::template typemap<T>>;
216};
217
219
221template<template<typename, typename> class BinaryTemplate, typename First>
222struct Bind1st {
223 template<typename T> using typemap = BinaryTemplate<First, T>;
224};
225
227template<template<typename, typename> class BinaryTemplate, typename Second>
228struct Bind2nd {
229 template<typename T> using typemap = BinaryTemplate<T, Second>;
230};
231
233template<template<typename...> class Template, typename TypeList> struct Apply;
234template<template<typename...> class Template, typename TypeList>
236template<template<typename...> class Template, typename... Types>
237struct Apply<Template, List<Types...>> { using type = Template<Types...>; };
238
240template<typename TupleLike> struct Bind {
241private:
242 template<typename> struct Impl;
243 template<size_t... Is> struct Impl<std::index_sequence<Is...>> {
245 };
246 enum : size_t { size = std::tuple_size_v<TupleLike> };
247public:
249};
250template<typename TupleLike> using Bind_t = typename Bind<TupleLike>::type;
251
253template<typename Metafunction, typename TypeList> struct Map {
254private:
255 template<typename... Types> struct Impl {
257 };
258public:
260};
261template<typename Metafunction, typename TypeList> using Map_t =
263
266template<typename Metafunction, typename TypeList> struct MapList {
268};
269template<typename Metafunction, typename TypeList> using MapList_t
271
272template<typename... Lists> struct Append;
273template<typename... Lists> using Append_t = typename Append<Lists...>::type;
274template<> struct Append<> { using type = Nil; };
275template<typename TypeList, typename... TypeLists>
276struct Append<TypeList, TypeLists...> {
277private:
278 template<typename... FirstTypes> struct CaptureFirst {
279 template<typename... RestTypes> struct CaptureRest {
280 using type = List<FirstTypes..., RestTypes...>;
281 };
282 using type = typename Apply_t<CaptureRest, Append_t<TypeLists...>>::type;
283 };
284public:
286};
287
289template<template<typename Type, typename Accumulator> class Op,
290 typename TypeList, typename Initial
291>
292struct LeftFold {
293private:
294 template<typename... Types> struct Impl {
295 template<typename Acc, typename...> struct Accumulate;
296 template<typename Acc> struct Accumulate<Acc> { using type = Acc; };
297 template<typename Acc, typename T, typename... Ts>
298 struct Accumulate<Acc, T, Ts...> {
299 using type = typename Accumulate<Op<T, Acc>, Ts...>::type;
300 };
301 using type = typename Accumulate<Initial, Types...>::type;
302 };
303public:
305};
306template<template<typename Type, typename Accumulator> class Op,
307 typename TypeList, typename Initial
308>
310
312template<template<typename Prefix, typename Accumulator> class Op,
313 typename TypeList, typename Initial
314>
316private:
317 template<typename T, typename Pair> struct Op1 {
320 };
321 template<typename T, typename Pair> using Op1_t =
322 typename Op1<T, Pair>::type;
323public:
325};
326template<template<typename Prefix, typename Accumulator> class Op,
327 typename TypeList, typename Initial
328>
330
332template<template<typename Type, typename Accumulator> class Op,
333 typename TypeList, typename Initial
334>
335struct RightFold {
336private:
337 template<typename Acc, typename TL> struct Accumulate {
338 using type = Op<Head_t<TL>, typename Accumulate<Acc, Tail_t<TL>>::type>;
339 };
340 template<typename Acc> struct Accumulate<Acc, Nil> { using type = Acc; };
341public:
343};
344template<template<typename Type, typename Accumulator> class Op,
345 typename TypeList, typename Initial
346>
348
350template<template<typename Tail, typename Accumulator> class Op,
351 typename TypeList, typename Initial
352>
354private:
355 template<typename Acc, typename TL> struct Accumulate {
356 using type = Op<TL, typename Accumulate<Acc, Tail_t<TL>>::type>;
357 };
358 template<typename Acc> struct Accumulate<Acc, Nil> { using type = Acc; };
359public:
361};
362template<template<typename Tail, typename Accumulator> class Op,
363 typename TypeList, typename Initial
364>
366
367template<typename TypeList> struct Reverse : LeftFold<Cons_t, TypeList, Nil>{};
368template<typename TypeList> using Reverse_t = typename Reverse<TypeList>::type;
369
371template<typename Predicate, typename T> struct Call {
372 using type = typename Predicate::template typemap<T>;
373};
374template<typename Predicate, typename T> using Call_t =
376
378template<bool Const> using MaybeConst =
379 std::conditional_t<Const, Fn<std::add_const_t>, Identity>;
380
382template<bool Const, typename TypeList> using MapConst =
383 std::conditional_t<Const,
386 >;
387template<bool Const, typename TypeList> using MapConst_t =
389
391template<typename Predicate, typename T> using Is = Call<Predicate, T>;
392template<typename Predicate, typename T> using Is_t =
393 typename Is<Predicate, T>::type;
394template<typename Predicate, typename T> static constexpr bool Is_v =
396
397template<typename Predicate> using Not = Compose<Fn<std::negation>, Predicate>;
398
402template<typename... Predicates> struct Or;
403template<> struct Or<> {
404 template<typename T> using typemap = std::false_type;
405};
406template<typename Predicate, typename... Predicates>
407struct Or<Predicate, Predicates...> {
408private:
409 template<typename T> struct Rest {
410 static constexpr bool value = Is_v<Or<Predicates...>, T>;
411 };
412public:
413 template<typename T> using typemap = typename std::disjunction<
414 typename Predicate::template typemap<T>, Rest<T>
415 >;
416};
417
421template<typename... Predicates> struct And;
422template<> struct And<> {
423 template<typename T> using typemap = std::true_type;
424};
425template<typename Predicate, typename... Predicates>
426struct And<Predicate, Predicates...> {
427private:
428 template<typename T> struct Rest {
429 static constexpr bool value = Is_v<And<Predicates...>, T>;
430 };
431public:
432 template<typename T> using typemap = typename std::conjunction<
433 typename Predicate::template typemap<T>, Rest<T>
434 >;
435};
436
439template<typename Predicate, typename TypeList> struct Every
440 : Apply_t<std::conjunction, Map_t<Predicate, TypeList>> {};
442template<typename Predicate, typename TypeList> constexpr auto Every_v =
444
447template<typename Predicate, typename TypeList> struct Some
448 : Apply_t<std::disjunction, Map_t<Predicate, TypeList>> {};
450template<typename Predicate, typename TypeList> constexpr auto Some_v =
452
456template<typename Predicate, typename TypeList> struct NotEvery
457 : Some<Not<Predicate>, TypeList> {};
459template<typename Predicate, typename TypeList> constexpr auto NotEvery_v =
461
465template<typename Predicate, typename TypeList> struct NotAny
466 : Every<Not<Predicate>, TypeList> {};
468template<typename Predicate, typename TypeList> constexpr auto NotAny_v =
470
473template<typename Item, typename TypeList> struct In
474 : Some<Bind1st<std::is_same, Item>, TypeList> {};
475template<typename Item, typename TypeList> constexpr auto In_v =
477
479template<typename Item, typename TypeList> struct HasBaseIn
480 : Some<Bind2nd<std::is_base_of, Item>, TypeList> {};
481template<typename Item, typename TypeList> constexpr auto HasBaseIn_v =
483
486template<typename Predicate, typename TypeList> struct StablePartition {
487private:
488 template<typename Type, typename Acc> using Op = std::conditional_t<
489 Is_v<Predicate, Type>,
492 >;
493public:
495};
496template<typename Predicate, typename TypeList> using StablePartition_t =
498
500template<typename Predicate, typename TypeList> struct Filter {
502};
503template<typename Predicate, typename TypeList> using Filter_t =
505}
506
507#endif
Utilities for compile-time type manipulation. Some terminology as in Lisp.
Definition: TypeList.h:22
static constexpr bool Is_v
Definition: TypeList.h:394
typename RightFold< Op, TypeList, Initial >::type RightFold_t
Definition: TypeList.h:347
std::conditional_t< Const, Fn< std::add_const_t >, Identity > MaybeConst
Conditionally add const to a type.
Definition: TypeList.h:379
constexpr auto HasBaseIn_v
Definition: TypeList.h:481
typename NonEmptyTails< TypeList >::type NonEmptyTails_t
Definition: TypeList.h:173
constexpr auto NotEvery_v
The constant value in the corresponding type.
Definition: TypeList.h:459
constexpr auto Length_v
Definition: TypeList.h:84
typename Bind< TupleLike >::type Bind_t
Definition: TypeList.h:250
typename Tails< TypeList >::type Tails_t
Definition: TypeList.h:180
typename PushFront< TypeList, Type >::type PushFront_t
Definition: TypeList.h:151
typename Second< TypeList >::type Second_t
Definition: TypeList.h:137
typename Is< Predicate, T >::type Is_t
Definition: TypeList.h:393
constexpr auto In_v
Definition: TypeList.h:475
constexpr auto NotAny_v
The constant value in the corresponding type.
Definition: TypeList.h:468
typename LeftFoldList< Op, TypeList, Initial >::type LeftFoldList_t
Definition: TypeList.h:329
typename LeftFold< Op, TypeList, Initial >::type LeftFold_t
Definition: TypeList.h:309
Tail_t< TypeList > Rest_t
Definition: TypeList.h:114
constexpr auto Null_v
Definition: TypeList.h:78
typename StablePartition< Predicate, TypeList >::type StablePartition_t
Definition: TypeList.h:497
typename Tail< TypeList >::type Tail_t
Definition: TypeList.h:107
typename Length< TypeList >::type Length_t
Definition: TypeList.h:83
constexpr auto Every_v
The constant value in the corresponding type.
Definition: TypeList.h:442
List<> Nil
Definition: TypeList.h:75
typename Last< TypeList >::type Last_t
Definition: TypeList.h:183
typename Filter< Predicate, TypeList >::type Filter_t
Definition: TypeList.h:504
typename ButLast< TypeList >::type ButLast_t
Definition: TypeList.h:190
typename Reverse< TypeList >::type Reverse_t
Definition: TypeList.h:368
typename Call< Predicate, T >::type Call_t
Definition: TypeList.h:375
typename Apply< Template, TypeList >::type Apply_t
Definition: TypeList.h:235
typename PushBack< TypeList, Type >::type PushBack_t
Definition: TypeList.h:156
typename Map< Metafunction, TypeList >::type Map_t
Definition: TypeList.h:262
std::conditional_t< Const, Map< Fn< std::add_const_t >, TypeList >, type_identity< TypeList > > MapConst
Conditionally map const over a type list.
Definition: TypeList.h:386
typename MapList< Metafunction, TypeList >::type MapList_t
Definition: TypeList.h:270
typename MapConst< Const, TypeList >::type MapConst_t
Definition: TypeList.h:388
typename Cons< Type, TypeList >::type Cons_t
Definition: TypeList.h:142
typename Head< TypeList >::type Head_t
Definition: TypeList.h:95
constexpr auto Some_v
The constant value in the corresponding type.
Definition: TypeList.h:450
typename RightFoldList< Op, TypeList, Initial >::type RightFoldList_t
Definition: TypeList.h:365
typename Append< Lists... >::type Append_t
Definition: TypeList.h:273
typename Nth< N, TypeList >::type Nth_t
Definition: TypeList.h:128
typename First< TypeList >::type First_t
Definition: TypeList.h:134
double Accumulate(const TrackList &list, double(Track::*memfn)() const, double ident, const double &(*combine)(const double &, const double &))
Definition: Track.cpp:972
STL namespace.
typename std::conjunction< typename Predicate::template typemap< T >, Rest< T > > typemap
Definition: TypeList.h:434
std::true_type typemap
Definition: TypeList.h:423
typename Apply_t< CaptureRest, Append_t< TypeLists... > >::type type
Definition: TypeList.h:282
typename Apply_t< CaptureFirst, TypeList >::type type
Definition: TypeList.h:285
Bind the types in TypeList to the parameters of a variadic Template.
Definition: TypeList.h:233
Given a binary template and a fixed argument, make a metafunction.
Definition: TypeList.h:222
BinaryTemplate< First, T > typemap
Definition: TypeList.h:223
Given a binary template and a fixed argument, make a metafunction.
Definition: TypeList.h:228
BinaryTemplate< T, Second > typemap
Definition: TypeList.h:229
Destructure any tuple-like type into a TypeList.
Definition: TypeList.h:240
typename Impl< std::make_index_sequence< size > >::type type
Definition: TypeList.h:248
Cons_t< Type, ButLast_t< List< Types... > > > type
Definition: TypeList.h:194
Apply a metafunction to a type.
Definition: TypeList.h:371
typename Predicate::template typemap< T > type
Definition: TypeList.h:372
typename Metafunction::template typemap< typename Compose< Metafunctions... >::template typemap< T > > typemap
Definition: TypeList.h:215
Build a type list from a type and another type list.
Definition: TypeList.h:140
Select only the subsequence of the type list satisfying the predicate.
Definition: TypeList.h:500
First_t< StablePartition_t< Predicate, TypeList > > type
Definition: TypeList.h:501
Template< typename Fn< Templates... >::template typemap< T > > typemap
Definition: TypeList.h:205
Whether the given type is derived from any member of the list.
Definition: TypeList.h:480
typename List< Types... >::head type
Definition: TypeList.h:97
Delays expansion of nested alias head; so Head<Nil> is legal.
Definition: TypeList.h:89
Last_t< List< Types... > > type
Definition: TypeList.h:186
typename Accumulate< Op< T, Acc >, Ts... >::type type
Definition: TypeList.h:299
typename Accumulate< Initial, Types... >::type type
Definition: TypeList.h:301
Left fold reduction of a list of types by a binary template.
Definition: TypeList.h:292
typename Apply_t< Impl, TypeList >::type type
Definition: TypeList.h:304
PushBack_t< Second_t< Pair >, T > NewPrefix
Definition: TypeList.h:318
Like LeftFold, but passing nonempty prefixes, not elements, to Op.
Definition: TypeList.h:315
typename Op1< T, Pair >::type Op1_t
Definition: TypeList.h:322
First_t< LeftFold_t< Op1_t, TypeList, List< Initial, Nil > > > type
Definition: TypeList.h:324
Non-empty specialization also defines first and rest.
Definition: TypeList.h:68
Empty specialization.
Definition: TypeList.h:63
Primary template for a list of arbitrary types.
Definition: TypeList.h:61
Transform a list of types by the given metafunction.
Definition: TypeList.h:253
typename Apply_t< Impl, TypeList >::type type
Definition: TypeList.h:259
Map_t< Metafunction, NonEmptyTails_t< TypeList > > type
Definition: TypeList.h:267
Cons_t< TypeList, typename NonEmptyTails< Tail_t< TypeList > >::type > type
Definition: TypeList.h:165
typename std::conditional_t< Null_v< TypeList >, type_identity< Nil >, Next >::type type
Definition: TypeList.h:170
typename Countdown< I - 1, Tail_t< TL > >::type type
Definition: TypeList.h:119
typename Countdown< N, TypeList >::type type
Definition: TypeList.h:125
typename std::disjunction< typename Predicate::template typemap< T >, Rest< T > > typemap
Definition: TypeList.h:415
std::false_type typemap
Definition: TypeList.h:404
PushBack – no Common Lisp equivalent name.
Definition: TypeList.h:154
An alternative more suggestive of C++ than Lisp conventions.
Definition: TypeList.h:149
Op< Head_t< TL >, typename Accumulate< Acc, Tail_t< TL > >::type > type
Definition: TypeList.h:338
Right fold reduction of a list of types by a binary template.
Definition: TypeList.h:335
typename Accumulate< Initial, TypeList >::type type
Definition: TypeList.h:342
Op< TL, typename Accumulate< Acc, Tail_t< TL > >::type > type
Definition: TypeList.h:356
Like RightFold, but passing nonempty tails, not elements, to Op.
Definition: TypeList.h:353
typename Accumulate< Initial, TypeList >::type type
Definition: TypeList.h:360
RightFold_t< Op, TypeList, List< Nil, Nil > > type
Definition: TypeList.h:494
std::conditional_t< Is_v< Predicate, Type >, List< Cons_t< Type, First_t< Acc > >, Second_t< Acc > >, List< First_t< Acc >, Cons_t< Type, Second_t< Acc > > > > Op
Definition: TypeList.h:492
typename List< Types... >::tail type
Definition: TypeList.h:109
Delays expansion of nested alias rest; so Tail<Nil> is legal.
Definition: TypeList.h:101
PushBack_t< NonEmptyTails_t< TypeList >, Nil > type
Definition: TypeList.h:178
standard in C++20; add a level of indirection to a type
Definition: TypeList.h:58