1 //===- Sequence.h - Utility for producing sequences of values ---*- 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 /// \file 9 /// Provides some synthesis utilities to produce sequences of values. The names 10 /// are intentionally kept very short as they tend to occur in common and 11 /// widely used contexts. 12 /// 13 /// The `seq(A, B)` function produces a sequence of values from `A` to up to 14 /// (but not including) `B`, i.e., [`A`, `B`), that can be safely iterated over. 15 /// `seq` supports both integral (e.g., `int`, `char`, `uint32_t`) and enum 16 /// types. `seq_inclusive(A, B)` produces a sequence of values from `A` to `B`, 17 /// including `B`. 18 /// 19 /// Examples with integral types: 20 /// ``` 21 /// for (int x : seq(0, 3)) 22 /// outs() << x << " "; 23 /// ``` 24 /// 25 /// Prints: `0 1 2 `. 26 /// 27 /// ``` 28 /// for (int x : seq_inclusive(0, 3)) 29 /// outs() << x << " "; 30 /// ``` 31 /// 32 /// Prints: `0 1 2 3 `. 33 /// 34 /// Similar to `seq` and `seq_inclusive`, the `enum_seq` and 35 /// `enum_seq_inclusive` functions produce sequences of enum values that can be 36 /// iterated over. 37 /// To enable iteration with enum types, you need to either mark enums as safe 38 /// to iterate on by specializing `enum_iteration_traits`, or opt into 39 /// potentially unsafe iteration at every callsite by passing 40 /// `force_iteration_on_noniterable_enum`. 41 /// 42 /// Examples with enum types: 43 /// ``` 44 /// namespace X { 45 /// enum class MyEnum : unsigned {A = 0, B, C}; 46 /// } // namespace X 47 /// 48 /// template <> struct enum_iteration_traits<X::MyEnum> { 49 /// static contexpr bool is_iterable = true; 50 /// }; 51 /// 52 /// class MyClass { 53 /// public: 54 /// enum Safe { D = 3, E, F }; 55 /// enum MaybeUnsafe { G = 1, H = 2, I = 4 }; 56 /// }; 57 /// 58 /// template <> struct enum_iteration_traits<MyClass::Safe> { 59 /// static contexpr bool is_iterable = true; 60 /// }; 61 /// ``` 62 /// 63 /// ``` 64 /// for (auto v : enum_seq(MyClass::Safe::D, MyClass::Safe::F)) 65 /// outs() << int(v) << " "; 66 /// ``` 67 /// 68 /// Prints: `3 4 `. 69 /// 70 /// ``` 71 /// for (auto v : enum_seq(MyClass::MaybeUnsafe::H, MyClass::MaybeUnsafe::I, 72 /// force_iteration_on_noniterable_enum)) 73 /// outs() << int(v) << " "; 74 /// ``` 75 /// 76 /// Prints: `2 3 `. 77 /// 78 //===----------------------------------------------------------------------===// 79 80 #ifndef LLVM_ADT_SEQUENCE_H 81 #define LLVM_ADT_SEQUENCE_H 82 83 #include <cassert> // assert 84 #include <iterator> // std::random_access_iterator_tag 85 #include <limits> // std::numeric_limits 86 #include <type_traits> // std::is_integral, std::is_enum, std::underlying_type, 87 // std::enable_if 88 89 #include "llvm/Support/MathExtras.h" // AddOverflow / SubOverflow 90 91 namespace llvm { 92 93 // Enum traits that marks enums as safe or unsafe to iterate over. 94 // By default, enum types are *not* considered safe for iteration. 95 // To allow iteration for your enum type, provide a specialization with 96 // `is_iterable` set to `true` in the `llvm` namespace. 97 // Alternatively, you can pass the `force_iteration_on_noniterable_enum` tag 98 // to `enum_seq` or `enum_seq_inclusive`. 99 template <typename EnumT> struct enum_iteration_traits { 100 static constexpr bool is_iterable = false; 101 }; 102 103 struct force_iteration_on_noniterable_enum_t { 104 explicit force_iteration_on_noniterable_enum_t() = default; 105 }; 106 107 // TODO: Make this `inline` once we update to C++17 to avoid ORD violations. 108 constexpr force_iteration_on_noniterable_enum_t 109 force_iteration_on_noniterable_enum; 110 111 namespace detail { 112 113 // Returns whether a value of type U can be represented with type T. 114 template <typename T, typename U> bool canTypeFitValue(const U Value) { 115 const intmax_t BotT = intmax_t(std::numeric_limits<T>::min()); 116 const intmax_t BotU = intmax_t(std::numeric_limits<U>::min()); 117 const uintmax_t TopT = uintmax_t(std::numeric_limits<T>::max()); 118 const uintmax_t TopU = uintmax_t(std::numeric_limits<U>::max()); 119 return !((BotT > BotU && Value < static_cast<U>(BotT)) || 120 (TopT < TopU && Value > static_cast<U>(TopT))); 121 } 122 123 // An integer type that asserts when: 124 // - constructed from a value that doesn't fit into intmax_t, 125 // - casted to a type that cannot hold the current value, 126 // - its internal representation overflows. 127 struct CheckedInt { 128 // Integral constructor, asserts if Value cannot be represented as intmax_t. 129 template <typename Integral, typename std::enable_if_t< 130 std::is_integral<Integral>::value, bool> = 0> 131 static CheckedInt from(Integral FromValue) { 132 if (!canTypeFitValue<intmax_t>(FromValue)) 133 assertOutOfBounds(); 134 CheckedInt Result; 135 Result.Value = static_cast<intmax_t>(FromValue); 136 return Result; 137 } 138 139 // Enum constructor, asserts if Value cannot be represented as intmax_t. 140 template <typename Enum, 141 typename std::enable_if_t<std::is_enum<Enum>::value, bool> = 0> 142 static CheckedInt from(Enum FromValue) { 143 using type = typename std::underlying_type<Enum>::type; 144 return from<type>(static_cast<type>(FromValue)); 145 } 146 147 // Equality 148 bool operator==(const CheckedInt &O) const { return Value == O.Value; } 149 bool operator!=(const CheckedInt &O) const { return Value != O.Value; } 150 151 CheckedInt operator+(intmax_t Offset) const { 152 CheckedInt Result; 153 if (AddOverflow(Value, Offset, Result.Value)) 154 assertOutOfBounds(); 155 return Result; 156 } 157 158 intmax_t operator-(CheckedInt Other) const { 159 intmax_t Result; 160 if (SubOverflow(Value, Other.Value, Result)) 161 assertOutOfBounds(); 162 return Result; 163 } 164 165 // Convert to integral, asserts if Value cannot be represented as Integral. 166 template <typename Integral, typename std::enable_if_t< 167 std::is_integral<Integral>::value, bool> = 0> 168 Integral to() const { 169 if (!canTypeFitValue<Integral>(Value)) 170 assertOutOfBounds(); 171 return static_cast<Integral>(Value); 172 } 173 174 // Convert to enum, asserts if Value cannot be represented as Enum's 175 // underlying type. 176 template <typename Enum, 177 typename std::enable_if_t<std::is_enum<Enum>::value, bool> = 0> 178 Enum to() const { 179 using type = typename std::underlying_type<Enum>::type; 180 return Enum(to<type>()); 181 } 182 183 private: 184 static void assertOutOfBounds() { assert(false && "Out of bounds"); } 185 186 intmax_t Value; 187 }; 188 189 template <typename T, bool IsReverse> struct SafeIntIterator { 190 using iterator_category = std::random_access_iterator_tag; 191 using value_type = T; 192 using difference_type = intmax_t; 193 using pointer = T *; 194 using reference = T &; 195 196 // Construct from T. 197 explicit SafeIntIterator(T Value) : SI(CheckedInt::from<T>(Value)) {} 198 // Construct from other direction. 199 SafeIntIterator(const SafeIntIterator<T, !IsReverse> &O) : SI(O.SI) {} 200 201 // Dereference 202 value_type operator*() const { return SI.to<T>(); } 203 // Indexing 204 value_type operator[](intmax_t Offset) const { return *(*this + Offset); } 205 206 // Can be compared for equivalence using the equality/inequality operators. 207 bool operator==(const SafeIntIterator &O) const { return SI == O.SI; } 208 bool operator!=(const SafeIntIterator &O) const { return SI != O.SI; } 209 // Comparison 210 bool operator<(const SafeIntIterator &O) const { return (*this - O) < 0; } 211 bool operator>(const SafeIntIterator &O) const { return (*this - O) > 0; } 212 bool operator<=(const SafeIntIterator &O) const { return (*this - O) <= 0; } 213 bool operator>=(const SafeIntIterator &O) const { return (*this - O) >= 0; } 214 215 // Pre Increment/Decrement 216 void operator++() { offset(1); } 217 void operator--() { offset(-1); } 218 219 // Post Increment/Decrement 220 SafeIntIterator operator++(int) { 221 const auto Copy = *this; 222 ++*this; 223 return Copy; 224 } 225 SafeIntIterator operator--(int) { 226 const auto Copy = *this; 227 --*this; 228 return Copy; 229 } 230 231 // Compound assignment operators 232 void operator+=(intmax_t Offset) { offset(Offset); } 233 void operator-=(intmax_t Offset) { offset(-Offset); } 234 235 // Arithmetic 236 SafeIntIterator operator+(intmax_t Offset) const { return add(Offset); } 237 SafeIntIterator operator-(intmax_t Offset) const { return add(-Offset); } 238 239 // Difference 240 intmax_t operator-(const SafeIntIterator &O) const { 241 return IsReverse ? O.SI - SI : SI - O.SI; 242 } 243 244 private: 245 SafeIntIterator(const CheckedInt &SI) : SI(SI) {} 246 247 static intmax_t getOffset(intmax_t Offset) { 248 return IsReverse ? -Offset : Offset; 249 } 250 251 CheckedInt add(intmax_t Offset) const { return SI + getOffset(Offset); } 252 253 void offset(intmax_t Offset) { SI = SI + getOffset(Offset); } 254 255 CheckedInt SI; 256 257 // To allow construction from the other direction. 258 template <typename, bool> friend struct SafeIntIterator; 259 }; 260 261 } // namespace detail 262 263 template <typename T> struct iota_range { 264 using value_type = T; 265 using reference = T &; 266 using const_reference = const T &; 267 using iterator = detail::SafeIntIterator<value_type, false>; 268 using const_iterator = iterator; 269 using reverse_iterator = detail::SafeIntIterator<value_type, true>; 270 using const_reverse_iterator = reverse_iterator; 271 using difference_type = intmax_t; 272 using size_type = std::size_t; 273 274 explicit iota_range(T Begin, T End, bool Inclusive) 275 : BeginValue(Begin), PastEndValue(End) { 276 assert(Begin <= End && "Begin must be less or equal to End."); 277 if (Inclusive) 278 ++PastEndValue; 279 } 280 281 size_t size() const { return PastEndValue - BeginValue; } 282 bool empty() const { return BeginValue == PastEndValue; } 283 284 auto begin() const { return const_iterator(BeginValue); } 285 auto end() const { return const_iterator(PastEndValue); } 286 287 auto rbegin() const { return const_reverse_iterator(PastEndValue - 1); } 288 auto rend() const { return const_reverse_iterator(BeginValue - 1); } 289 290 private: 291 static_assert(std::is_integral<T>::value || std::is_enum<T>::value, 292 "T must be an integral or enum type"); 293 static_assert(std::is_same<T, std::remove_cv_t<T>>::value, 294 "T must not be const nor volatile"); 295 296 iterator BeginValue; 297 iterator PastEndValue; 298 }; 299 300 /// Iterate over an integral type from Begin up to - but not including - End. 301 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for 302 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse 303 /// iteration). 304 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value && 305 !std::is_enum<T>::value>> 306 auto seq(T Begin, T End) { 307 return iota_range<T>(Begin, End, false); 308 } 309 310 /// Iterate over an integral type from Begin to End inclusive. 311 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1] 312 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse 313 /// iteration). 314 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value && 315 !std::is_enum<T>::value>> 316 auto seq_inclusive(T Begin, T End) { 317 return iota_range<T>(Begin, End, true); 318 } 319 320 /// Iterate over an enum type from Begin up to - but not including - End. 321 /// Note: `enum_seq` will generate each consecutive value, even if no 322 /// enumerator with that value exists. 323 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for 324 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse 325 /// iteration). 326 template <typename EnumT, 327 typename = std::enable_if_t<std::is_enum<EnumT>::value>> 328 auto enum_seq(EnumT Begin, EnumT End) { 329 static_assert(enum_iteration_traits<EnumT>::is_iterable, 330 "Enum type is not marked as iterable."); 331 return iota_range<EnumT>(Begin, End, false); 332 } 333 334 /// Iterate over an enum type from Begin up to - but not including - End, even 335 /// when `EnumT` is not marked as safely iterable by `enum_iteration_traits`. 336 /// Note: `enum_seq` will generate each consecutive value, even if no 337 /// enumerator with that value exists. 338 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for 339 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse 340 /// iteration). 341 template <typename EnumT, 342 typename = std::enable_if_t<std::is_enum<EnumT>::value>> 343 auto enum_seq(EnumT Begin, EnumT End, force_iteration_on_noniterable_enum_t) { 344 return iota_range<EnumT>(Begin, End, false); 345 } 346 347 /// Iterate over an enum type from Begin to End inclusive. 348 /// Note: `enum_seq_inclusive` will generate each consecutive value, even if no 349 /// enumerator with that value exists. 350 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1] 351 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse 352 /// iteration). 353 template <typename EnumT, 354 typename = std::enable_if_t<std::is_enum<EnumT>::value>> 355 auto enum_seq_inclusive(EnumT Begin, EnumT End) { 356 static_assert(enum_iteration_traits<EnumT>::is_iterable, 357 "Enum type is not marked as iterable."); 358 return iota_range<EnumT>(Begin, End, true); 359 } 360 361 /// Iterate over an enum type from Begin to End inclusive, even when `EnumT` 362 /// is not marked as safely iterable by `enum_iteration_traits`. 363 /// Note: `enum_seq_inclusive` will generate each consecutive value, even if no 364 /// enumerator with that value exists. 365 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1] 366 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse 367 /// iteration). 368 template <typename EnumT, 369 typename = std::enable_if_t<std::is_enum<EnumT>::value>> 370 auto enum_seq_inclusive(EnumT Begin, EnumT End, 371 force_iteration_on_noniterable_enum_t) { 372 return iota_range<EnumT>(Begin, End, true); 373 } 374 375 } // end namespace llvm 376 377 #endif // LLVM_ADT_SEQUENCE_H 378