1 //===-- include/flang/Common/template.h -------------------------*- 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 #ifndef FORTRAN_COMMON_TEMPLATE_H_ 10 #define FORTRAN_COMMON_TEMPLATE_H_ 11 12 #include "flang/Common/idioms.h" 13 #include <functional> 14 #include <optional> 15 #include <tuple> 16 #include <type_traits> 17 #include <variant> 18 #include <vector> 19 20 // Utility templates for metaprogramming and for composing the 21 // std::optional<>, std::tuple<>, and std::variant<> containers. 22 23 namespace Fortran::common { 24 25 // SearchTypeList<PREDICATE, TYPES...> scans a list of types. The zero-based 26 // index of the first type T in the list for which PREDICATE<T>::value() is 27 // true is returned, or -1 if the predicate is false for every type in the list. 28 // This is a compile-time operation; see SearchTypes below for a run-time form. 29 template <int N, template <typename> class PREDICATE, typename TUPLE> 30 struct SearchTypeListHelper { valueSearchTypeListHelper31 static constexpr int value() { 32 if constexpr (N >= std::tuple_size_v<TUPLE>) { 33 return -1; 34 } else if constexpr (PREDICATE<std::tuple_element_t<N, TUPLE>>::value()) { 35 return N; 36 } else { 37 return SearchTypeListHelper<N + 1, PREDICATE, TUPLE>::value(); 38 } 39 } 40 }; 41 42 template <template <typename> class PREDICATE, typename... TYPES> 43 constexpr int SearchTypeList{ 44 SearchTypeListHelper<0, PREDICATE, std::tuple<TYPES...>>::value()}; 45 46 // TypeIndex<A, TYPES...> scans a list of types for simple type equality. 47 // The zero-based index of A in the list is returned, or -1 if A is not present. 48 template <typename A> struct MatchType { 49 template <typename B> struct Match { valueMatchType::Match50 static constexpr bool value() { 51 return std::is_same_v<std::decay_t<A>, std::decay_t<B>>; 52 } 53 }; 54 }; 55 56 template <typename A, typename... TYPES> 57 constexpr int TypeIndex{SearchTypeList<MatchType<A>::template Match, TYPES...>}; 58 59 // IsTypeInList<A, TYPES...> is a simple presence predicate. 60 template <typename A, typename... TYPES> 61 constexpr bool IsTypeInList{TypeIndex<A, TYPES...> >= 0}; 62 63 // OverMembers extracts the list of types that constitute the alternatives 64 // of a std::variant or elements of a std::tuple and passes that list as 65 // parameter types to a given variadic template. 66 template <template <typename...> class, typename> struct OverMembersHelper; 67 template <template <typename...> class T, typename... Ts> 68 struct OverMembersHelper<T, std::variant<Ts...>> { 69 using type = T<Ts...>; 70 }; 71 template <template <typename...> class T, typename... Ts> 72 struct OverMembersHelper<T, std::tuple<Ts...>> { 73 using type = T<Ts...>; 74 }; 75 76 template <template <typename...> class T, typename TUPLEorVARIANT> 77 using OverMembers = 78 typename OverMembersHelper<T, std::decay_t<TUPLEorVARIANT>>::type; 79 80 // SearchMembers<PREDICATE> scans the types that constitute the alternatives 81 // of a std::variant instantiation or elements of a std::tuple. 82 // The zero-based index of the first type T among the alternatives for which 83 // PREDICATE<T>::value() is true is returned, or -1 when the predicate is false 84 // for every type in the set. 85 template <template <typename> class PREDICATE> struct SearchMembersHelper { 86 template <typename... Ts> struct Scanner { 87 static constexpr int value() { return SearchTypeList<PREDICATE, Ts...>; } 88 }; 89 }; 90 91 template <template <typename> class PREDICATE, typename TUPLEorVARIANT> 92 constexpr int SearchMembers{ 93 OverMembers<SearchMembersHelper<PREDICATE>::template Scanner, 94 TUPLEorVARIANT>::value()}; 95 96 template <typename A, typename TUPLEorVARIANT> 97 constexpr bool HasMember{ 98 SearchMembers<MatchType<A>::template Match, TUPLEorVARIANT> >= 0}; 99 100 // std::optional<std::optional<A>> -> std::optional<A> 101 template <typename A> 102 std::optional<A> JoinOptional(std::optional<std::optional<A>> &&x) { 103 if (x) { 104 return std::move(*x); 105 } 106 return std::nullopt; 107 } 108 109 // Convert an std::optional to an ordinary pointer 110 template <typename A> const A *GetPtrFromOptional(const std::optional<A> &x) { 111 if (x) { 112 return &*x; 113 } else { 114 return nullptr; 115 } 116 } 117 118 // Copy a value from one variant type to another. The types allowed in the 119 // source variant must all be allowed in the destination variant type. 120 template <typename TOV, typename FROMV> TOV CopyVariant(const FROMV &u) { 121 return std::visit([](const auto &x) -> TOV { return {x}; }, u); 122 } 123 124 // Move a value from one variant type to another. The types allowed in the 125 // source variant must all be allowed in the destination variant type. 126 template <typename TOV, typename FROMV> 127 common::IfNoLvalue<TOV, FROMV> MoveVariant(FROMV &&u) { 128 return std::visit( 129 [](auto &&x) -> TOV { return {std::move(x)}; }, std::move(u)); 130 } 131 132 // CombineTuples takes a list of std::tuple<> template instantiation types 133 // and constructs a new std::tuple type that concatenates all of their member 134 // types. E.g., 135 // CombineTuples<std::tuple<char, int>, std::tuple<float, double>> 136 // is std::tuple<char, int, float, double>. 137 template <typename... TUPLES> struct CombineTuplesHelper { 138 static decltype(auto) f(TUPLES *...a) { 139 return std::tuple_cat(std::move(*a)...); 140 } 141 using type = decltype(f(static_cast<TUPLES *>(nullptr)...)); 142 }; 143 template <typename... TUPLES> 144 using CombineTuples = typename CombineTuplesHelper<TUPLES...>::type; 145 146 // CombineVariants takes a list of std::variant<> instantiations and constructs 147 // a new instantiation that holds all of their alternatives, which must be 148 // pairwise distinct. 149 template <typename> struct VariantToTupleHelper; 150 template <typename... Ts> struct VariantToTupleHelper<std::variant<Ts...>> { 151 using type = std::tuple<Ts...>; 152 }; 153 template <typename VARIANT> 154 using VariantToTuple = typename VariantToTupleHelper<VARIANT>::type; 155 156 template <typename A, typename... REST> struct AreTypesDistinctHelper { 157 static constexpr bool value() { 158 if constexpr (sizeof...(REST) > 0) { 159 // extra () for clang-format 160 return ((... && !std::is_same_v<A, REST>)) && 161 AreTypesDistinctHelper<REST...>::value(); 162 } 163 return true; 164 } 165 }; 166 template <typename... Ts> 167 constexpr bool AreTypesDistinct{AreTypesDistinctHelper<Ts...>::value()}; 168 169 template <typename A, typename... Ts> struct AreSameTypeHelper { 170 using type = A; 171 static constexpr bool value() { 172 if constexpr (sizeof...(Ts) == 0) { 173 return true; 174 } else { 175 using Rest = AreSameTypeHelper<Ts...>; 176 return std::is_same_v<type, typename Rest::type> && Rest::value(); 177 } 178 } 179 }; 180 181 template <typename... Ts> 182 constexpr bool AreSameType{AreSameTypeHelper<Ts...>::value()}; 183 184 template <typename> struct TupleToVariantHelper; 185 template <typename... Ts> struct TupleToVariantHelper<std::tuple<Ts...>> { 186 static_assert(AreTypesDistinct<Ts...>, 187 "TupleToVariant: types are not pairwise distinct"); 188 using type = std::variant<Ts...>; 189 }; 190 template <typename TUPLE> 191 using TupleToVariant = typename TupleToVariantHelper<TUPLE>::type; 192 193 template <typename... VARIANTS> struct CombineVariantsHelper { 194 using type = TupleToVariant<CombineTuples<VariantToTuple<VARIANTS>...>>; 195 }; 196 template <typename... VARIANTS> 197 using CombineVariants = typename CombineVariantsHelper<VARIANTS...>::type; 198 199 // SquashVariantOfVariants: given a std::variant whose alternatives are 200 // all std::variant instantiations, form a new union over their alternatives. 201 template <typename VARIANT> 202 using SquashVariantOfVariants = OverMembers<CombineVariants, VARIANT>; 203 204 // Given a type function, MapTemplate applies it to each of the types 205 // in a tuple or variant, and collect the results in a given variadic 206 // template (typically a std::variant). 207 template <template <typename> class, template <typename...> class, typename...> 208 struct MapTemplateHelper; 209 template <template <typename> class F, template <typename...> class PACKAGE, 210 typename... Ts> 211 struct MapTemplateHelper<F, PACKAGE, std::tuple<Ts...>> { 212 using type = PACKAGE<F<Ts>...>; 213 }; 214 template <template <typename> class F, template <typename...> class PACKAGE, 215 typename... Ts> 216 struct MapTemplateHelper<F, PACKAGE, std::variant<Ts...>> { 217 using type = PACKAGE<F<Ts>...>; 218 }; 219 template <template <typename> class F, typename TUPLEorVARIANT, 220 template <typename...> class PACKAGE = std::variant> 221 using MapTemplate = 222 typename MapTemplateHelper<F, PACKAGE, TUPLEorVARIANT>::type; 223 224 // std::tuple<std::optional<>...> -> std::optional<std::tuple<...>> 225 // i.e., inverts a tuple of optional values into an optional tuple that has 226 // a value only if all of the original elements were present. 227 template <typename... A, std::size_t... J> 228 std::optional<std::tuple<A...>> AllElementsPresentHelper( 229 std::tuple<std::optional<A>...> &&t, std::index_sequence<J...>) { 230 bool present[]{std::get<J>(t).has_value()...}; 231 for (std::size_t j{0}; j < sizeof...(J); ++j) { 232 if (!present[j]) { 233 return std::nullopt; 234 } 235 } 236 return {std::make_tuple(*std::get<J>(t)...)}; 237 } 238 239 template <typename... A> 240 std::optional<std::tuple<A...>> AllElementsPresent( 241 std::tuple<std::optional<A>...> &&t) { 242 return AllElementsPresentHelper( 243 std::move(t), std::index_sequence_for<A...>{}); 244 } 245 246 // std::vector<std::optional<A>> -> std::optional<std::vector<A>> 247 // i.e., inverts a vector of optional values into an optional vector that 248 // will have a value only when all of the original elements are present. 249 template <typename A> 250 std::optional<std::vector<A>> AllElementsPresent( 251 std::vector<std::optional<A>> &&v) { 252 for (const auto &maybeA : v) { 253 if (!maybeA) { 254 return std::nullopt; 255 } 256 } 257 std::vector<A> result; 258 for (auto &&maybeA : std::move(v)) { 259 result.emplace_back(std::move(*maybeA)); 260 } 261 return result; 262 } 263 264 // (std::optional<>...) -> std::optional<std::tuple<...>> 265 // i.e., given some number of optional values, return a optional tuple of 266 // those values that is present only of all of the values were so. 267 template <typename... A> 268 std::optional<std::tuple<A...>> AllPresent(std::optional<A> &&...x) { 269 return AllElementsPresent(std::make_tuple(std::move(x)...)); 270 } 271 272 // (f(A...) -> R) -> std::optional<A>... -> std::optional<R> 273 // Apply a function to optional arguments if all are present. 274 // N.B. If the function returns std::optional, MapOptional will return 275 // std::optional<std::optional<...>> and you will probably want to 276 // run it through JoinOptional to "squash" it. 277 template <typename R, typename... A> 278 std::optional<R> MapOptional( 279 std::function<R(A &&...)> &&f, std::optional<A> &&...x) { 280 if (auto args{AllPresent(std::move(x)...)}) { 281 return std::make_optional(std::apply(std::move(f), std::move(*args))); 282 } 283 return std::nullopt; 284 } 285 template <typename R, typename... A> 286 std::optional<R> MapOptional(R (*f)(A &&...), std::optional<A> &&...x) { 287 return MapOptional(std::function<R(A && ...)>{f}, std::move(x)...); 288 } 289 290 // Given a VISITOR class of the general form 291 // struct VISITOR { 292 // using Result = ...; 293 // using Types = std::tuple<...>; 294 // template<typename T> Result Test() { ... } 295 // }; 296 // SearchTypes will traverse the element types in the tuple in order 297 // and invoke VISITOR::Test<T>() on each until it returns a value that 298 // casts to true. If no invocation of Test succeeds, SearchTypes will 299 // return a default value. 300 template <std::size_t J, typename VISITOR> 301 common::IfNoLvalue<typename VISITOR::Result, VISITOR> SearchTypesHelper( 302 VISITOR &&visitor, typename VISITOR::Result &&defaultResult) { 303 using Tuple = typename VISITOR::Types; 304 if constexpr (J < std::tuple_size_v<Tuple>) { 305 if (auto result{visitor.template Test<std::tuple_element_t<J, Tuple>>()}) { 306 return result; 307 } 308 return SearchTypesHelper<J + 1, VISITOR>( 309 std::move(visitor), std::move(defaultResult)); 310 } else { 311 return std::move(defaultResult); 312 } 313 } 314 315 template <typename VISITOR> 316 common::IfNoLvalue<typename VISITOR::Result, VISITOR> SearchTypes( 317 VISITOR &&visitor, 318 typename VISITOR::Result defaultResult = typename VISITOR::Result{}) { 319 return SearchTypesHelper<0, VISITOR>( 320 std::move(visitor), std::move(defaultResult)); 321 } 322 } // namespace Fortran::common 323 #endif // FORTRAN_COMMON_TEMPLATE_H_ 324