1 /* 2 * Copyright 2014 Google Inc. All rights reserved. 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 #ifndef FRUIT_META_VECTOR_H 18 #define FRUIT_META_VECTOR_H 19 20 #include <fruit/impl/meta/basics.h> 21 #include <fruit/impl/meta/eval.h> 22 #include <fruit/impl/meta/fold.h> 23 #include <fruit/impl/meta/logical_operations.h> 24 #include <fruit/impl/meta/numeric_operations.h> 25 #include <functional> 26 27 namespace fruit { 28 namespace impl { 29 namespace meta { 30 31 // Used to pass around a Vector<Types...>, no meaning per se. 32 template <typename... Types> 33 struct Vector {}; 34 35 // Using ConsVector(MetaExpr...) instead of Vector<MetaExpr...> in a meta-expression allows the 36 // types to be evaluated. Avoid using Vector<...> directly in a meta-expression, unless you're sure 37 // that the arguments have already been evaluated (e.g. if Args... are arguments of a metafunction, 38 // Vector<Args...> is ok but Vector<MyFunction(Args)...> is wrong. 39 struct ConsVector { 40 template <typename... Types> 41 struct apply { 42 using type = Vector<Types...>; 43 }; 44 }; 45 46 struct GenerateIntSequenceEvenHelper { 47 template <typename Half> 48 struct apply; 49 50 template <int... ns> 51 struct apply<Vector<Int<ns>...>> { 52 using type = Vector<Int<ns>..., Int<sizeof...(ns) + ns>...>; 53 }; 54 }; 55 56 struct GenerateIntSequenceOddHelper { 57 template <typename Half> 58 struct apply; 59 60 template <int... ns> 61 struct apply<Vector<Int<ns>...>> { 62 using type = Vector<Int<ns>..., Int<sizeof...(ns)>, Int<sizeof...(ns) + 1 + ns>...>; 63 }; 64 }; 65 66 struct GenerateIntSequence { 67 template <typename N> 68 struct apply { 69 using type = If(Bool<(N::value % 2) == 0>, GenerateIntSequenceEvenHelper(GenerateIntSequence(Int<N::value / 2>)), 70 GenerateIntSequenceOddHelper(GenerateIntSequence(Int<N::value / 2>))); 71 }; 72 }; 73 74 template <> 75 struct GenerateIntSequence::apply<Int<0>> { 76 using type = Vector<>; 77 }; 78 79 template <> 80 struct GenerateIntSequence::apply<Int<1>> { 81 using type = Vector<Int<0>>; 82 }; 83 84 struct IsInVector { 85 template <typename T> 86 struct AlwaysFalseBool { 87 constexpr static bool value = false; 88 }; 89 90 template <bool... bs> 91 struct BoolVector; 92 93 template <typename T, typename V> 94 struct apply; 95 96 template <typename T, typename... Ts> 97 struct apply<T, Vector<Ts...>> { 98 using type = Bool< 99 !std::is_same<BoolVector<AlwaysFalseBool<Ts>::value...>, BoolVector<std::is_same<T, Ts>::value...>>::value>; 100 }; 101 }; 102 103 struct IsVectorContained { 104 template <typename V1, typename V2> 105 struct apply; 106 107 template <typename T> 108 struct AlwaysTrueBool { 109 constexpr static bool value = true; 110 }; 111 112 template <bool... bs> 113 struct BoolVector; 114 115 template <typename... Ts, typename V2> 116 struct apply<Vector<Ts...>, V2> { 117 using type = Bool<std::is_same<BoolVector<AlwaysTrueBool<Ts>::value...>, 118 BoolVector<Id<typename IsInVector::template apply<Ts, V2>::type>::value...>>::value>; 119 }; 120 }; 121 122 struct VectorSize { 123 template <typename V> 124 struct apply; 125 126 template <typename... Ts> 127 struct apply<Vector<Ts...>> { 128 using type = Int<sizeof...(Ts)>; 129 }; 130 }; 131 132 struct PushFront { 133 template <typename V, typename T> 134 struct apply; 135 136 template <typename T, typename... Ts> 137 struct apply<Vector<Ts...>, T> { 138 using type = Vector<T, Ts...>; 139 }; 140 }; 141 142 struct PushBack { 143 template <typename V, typename T> 144 struct apply; 145 146 template <typename T, typename... Ts> 147 struct apply<Vector<Ts...>, T> { 148 using type = Vector<Ts..., T>; 149 }; 150 }; 151 152 struct ConcatVectors { 153 template <typename V1, typename V2> 154 struct apply; 155 156 template <typename... Ts, typename... Us> 157 struct apply<Vector<Ts...>, Vector<Us...>> { 158 using type = Vector<Ts..., Us...>; 159 }; 160 }; 161 162 struct TransformVector { 163 template <typename V, typename F> 164 struct apply; 165 166 template <typename... Ts, typename F> 167 struct apply<Vector<Ts...>, F> { 168 using type = Vector<Eval<typename F::template apply<Ts>::type>...>; 169 }; 170 }; 171 172 struct ReplaceInVectorHelper { 173 template <typename ToReplace, typename NewElem, typename T> 174 struct apply { 175 using type = T; 176 }; 177 178 template <typename ToReplace, typename NewElem> 179 struct apply<ToReplace, NewElem, ToReplace> { 180 using type = NewElem; 181 }; 182 }; 183 184 struct ReplaceInVector { 185 template <typename V, typename ToReplace, typename NewElem> 186 struct apply { 187 using type = TransformVector(V, PartialCall(ReplaceInVectorHelper, ToReplace, NewElem)); 188 }; 189 }; 190 191 // If V is Vector<T1, ..., Tn> this calculates F(InitialValue, F(T1, F(..., F(Tn) ...))). 192 // If V is Vector<> this returns InitialValue. 193 struct FoldVector { 194 template <typename V, typename F, typename InitialValue> 195 struct apply; 196 197 template <typename... Ts, typename F, typename InitialValue> 198 struct apply<Vector<Ts...>, F, InitialValue> { 199 using type = Fold(F, InitialValue, Ts...); 200 }; 201 }; 202 203 template <typename Unused> 204 using AlwaysVoidPtr = void*; 205 206 // Returns a copy of V but without the first N elements. 207 // N must be at least 0 and at most VectorSize(V). 208 struct VectorRemoveFirstN { 209 template <typename V, typename N, typename Indexes = Eval<GenerateIntSequence(N)>> 210 struct apply; 211 212 template <typename... Types, typename N, typename... Indexes> 213 struct apply<Vector<Types...>, N, Vector<Indexes...>> { 214 template <typename... RemainingTypes> 215 static Vector<RemainingTypes...> f(AlwaysVoidPtr<Indexes>..., RemainingTypes*...); 216 217 using type = decltype(f((Types*)nullptr...)); 218 }; 219 }; 220 221 struct VectorEndsWith { 222 template <typename V, typename T> 223 struct apply { 224 using N = Int<Eval<VectorSize(V)>::value - 1>; 225 using type = IsSame(VectorRemoveFirstN(V, N), Vector<T>); 226 }; 227 228 template <typename T> 229 struct apply<Vector<>, T> { 230 using type = Bool<false>; 231 }; 232 }; 233 234 // Removes all None elements from the vector. 235 // O(n) instantiations. 236 struct VectorRemoveNone { 237 template <typename V> 238 struct apply { 239 using type = Vector<>; 240 }; 241 242 template <typename T, typename... Ts> 243 struct apply<Vector<T, Ts...>> { 244 using type = PushFront(VectorRemoveNone(Vector<Ts...>), T); 245 }; 246 247 template <typename... Ts> 248 struct apply<Vector<None, Ts...>> { 249 using type = VectorRemoveNone(Vector<Ts...>); 250 }; 251 }; 252 253 struct ConstructErrorWithArgVectorHelper { 254 template <typename ErrorTag, typename ArgsVector, typename... OtherArgs> 255 struct apply; 256 257 template <typename ErrorTag, typename... Args, typename... OtherArgs> 258 struct apply<ErrorTag, Vector<Args...>, OtherArgs...> { 259 using type = ConstructError(ErrorTag, OtherArgs..., Args...); 260 }; 261 }; 262 263 struct ConstructErrorWithArgVector { 264 template <typename ErrorTag, typename ArgsVector, typename... OtherArgs> 265 struct apply { 266 using type = ConstructErrorWithArgVectorHelper(ErrorTag, VectorRemoveNone(ArgsVector), OtherArgs...); 267 }; 268 }; 269 270 } // namespace meta 271 } // namespace impl 272 } // namespace fruit 273 274 #endif // FRUIT_META_VECTOR_H 275