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 inline constexpr force_iteration_on_noniterable_enum_t
108 force_iteration_on_noniterable_enum;
109
110 namespace detail {
111
112 // Returns whether a value of type U can be represented with type T.
canTypeFitValue(const U Value)113 template <typename T, typename U> bool canTypeFitValue(const U Value) {
114 const intmax_t BotT = intmax_t(std::numeric_limits<T>::min());
115 const intmax_t BotU = intmax_t(std::numeric_limits<U>::min());
116 const uintmax_t TopT = uintmax_t(std::numeric_limits<T>::max());
117 const uintmax_t TopU = uintmax_t(std::numeric_limits<U>::max());
118 return !((BotT > BotU && Value < static_cast<U>(BotT)) ||
119 (TopT < TopU && Value > static_cast<U>(TopT)));
120 }
121
122 // An integer type that asserts when:
123 // - constructed from a value that doesn't fit into intmax_t,
124 // - casted to a type that cannot hold the current value,
125 // - its internal representation overflows.
126 struct CheckedInt {
127 // Integral constructor, asserts if Value cannot be represented as intmax_t.
128 template <typename Integral,
129 std::enable_if_t<std::is_integral<Integral>::value, bool> = 0>
fromCheckedInt130 static CheckedInt from(Integral FromValue) {
131 if (!canTypeFitValue<intmax_t>(FromValue))
132 assertOutOfBounds();
133 CheckedInt Result;
134 Result.Value = static_cast<intmax_t>(FromValue);
135 return Result;
136 }
137
138 // Enum constructor, asserts if Value cannot be represented as intmax_t.
139 template <typename Enum,
140 std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
fromCheckedInt141 static CheckedInt from(Enum FromValue) {
142 using type = std::underlying_type_t<Enum>;
143 return from<type>(static_cast<type>(FromValue));
144 }
145
146 // Equality
147 bool operator==(const CheckedInt &O) const { return Value == O.Value; }
148 bool operator!=(const CheckedInt &O) const { return Value != O.Value; }
149
150 CheckedInt operator+(intmax_t Offset) const {
151 CheckedInt Result;
152 if (AddOverflow(Value, Offset, Result.Value))
153 assertOutOfBounds();
154 return Result;
155 }
156
157 intmax_t operator-(CheckedInt Other) const {
158 intmax_t Result;
159 if (SubOverflow(Value, Other.Value, Result))
160 assertOutOfBounds();
161 return Result;
162 }
163
164 // Convert to integral, asserts if Value cannot be represented as Integral.
165 template <typename Integral,
166 std::enable_if_t<std::is_integral<Integral>::value, bool> = 0>
toCheckedInt167 Integral to() const {
168 if (!canTypeFitValue<Integral>(Value))
169 assertOutOfBounds();
170 return static_cast<Integral>(Value);
171 }
172
173 // Convert to enum, asserts if Value cannot be represented as Enum's
174 // underlying type.
175 template <typename Enum,
176 std::enable_if_t<std::is_enum<Enum>::value, bool> = 0>
toCheckedInt177 Enum to() const {
178 using type = std::underlying_type_t<Enum>;
179 return Enum(to<type>());
180 }
181
182 private:
assertOutOfBoundsCheckedInt183 static void assertOutOfBounds() { assert(false && "Out of bounds"); }
184
185 intmax_t Value;
186 };
187
188 template <typename T, bool IsReverse> struct SafeIntIterator {
189 using iterator_category = std::random_access_iterator_tag;
190 using value_type = T;
191 using difference_type = intmax_t;
192 using pointer = T *;
193 using reference = value_type; // The iterator does not reference memory.
194
195 // Construct from T.
SafeIntIteratorSafeIntIterator196 explicit SafeIntIterator(T Value) : SI(CheckedInt::from<T>(Value)) {}
197 // Construct from other direction.
SafeIntIteratorSafeIntIterator198 SafeIntIterator(const SafeIntIterator<T, !IsReverse> &O) : SI(O.SI) {}
199
200 // Dereference
201 reference operator*() const { return SI.to<T>(); }
202 // Indexing
203 reference operator[](intmax_t Offset) const { return *(*this + Offset); }
204
205 // Can be compared for equivalence using the equality/inequality operators.
206 bool operator==(const SafeIntIterator &O) const { return SI == O.SI; }
207 bool operator!=(const SafeIntIterator &O) const { return SI != O.SI; }
208 // Comparison
209 bool operator<(const SafeIntIterator &O) const { return (*this - O) < 0; }
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
214 // Pre Increment/Decrement
215 void operator++() { offset(1); }
216 void operator--() { offset(-1); }
217
218 // Post Increment/Decrement
219 SafeIntIterator operator++(int) {
220 const auto Copy = *this;
221 ++*this;
222 return Copy;
223 }
224 SafeIntIterator operator--(int) {
225 const auto Copy = *this;
226 --*this;
227 return Copy;
228 }
229
230 // Compound assignment operators
231 void operator+=(intmax_t Offset) { offset(Offset); }
232 void operator-=(intmax_t Offset) { offset(-Offset); }
233
234 // Arithmetic
235 SafeIntIterator operator+(intmax_t Offset) const { return add(Offset); }
236 SafeIntIterator operator-(intmax_t Offset) const { return add(-Offset); }
237
238 // Difference
239 intmax_t operator-(const SafeIntIterator &O) const {
240 return IsReverse ? O.SI - SI : SI - O.SI;
241 }
242
243 private:
SafeIntIteratorSafeIntIterator244 SafeIntIterator(const CheckedInt &SI) : SI(SI) {}
245
getOffsetSafeIntIterator246 static intmax_t getOffset(intmax_t Offset) {
247 return IsReverse ? -Offset : Offset;
248 }
249
addSafeIntIterator250 CheckedInt add(intmax_t Offset) const { return SI + getOffset(Offset); }
251
offsetSafeIntIterator252 void offset(intmax_t Offset) { SI = SI + getOffset(Offset); }
253
254 CheckedInt SI;
255
256 // To allow construction from the other direction.
257 template <typename, bool> friend struct SafeIntIterator;
258 };
259
260 } // namespace detail
261
262 template <typename T> struct iota_range {
263 using value_type = T;
264 using reference = T &;
265 using const_reference = const T &;
266 using iterator = detail::SafeIntIterator<value_type, false>;
267 using const_iterator = iterator;
268 using reverse_iterator = detail::SafeIntIterator<value_type, true>;
269 using const_reverse_iterator = reverse_iterator;
270 using difference_type = intmax_t;
271 using size_type = std::size_t;
272
iota_rangeiota_range273 explicit iota_range(T Begin, T End, bool Inclusive)
274 : BeginValue(Begin), PastEndValue(End) {
275 assert(Begin <= End && "Begin must be less or equal to End.");
276 if (Inclusive)
277 ++PastEndValue;
278 }
279
sizeiota_range280 size_t size() const { return PastEndValue - BeginValue; }
emptyiota_range281 bool empty() const { return BeginValue == PastEndValue; }
282
beginiota_range283 auto begin() const { return const_iterator(BeginValue); }
endiota_range284 auto end() const { return const_iterator(PastEndValue); }
285
rbeginiota_range286 auto rbegin() const { return const_reverse_iterator(PastEndValue - 1); }
rendiota_range287 auto rend() const { return const_reverse_iterator(BeginValue - 1); }
288
289 private:
290 static_assert(std::is_integral<T>::value || std::is_enum<T>::value,
291 "T must be an integral or enum type");
292 static_assert(std::is_same<T, std::remove_cv_t<T>>::value,
293 "T must not be const nor volatile");
294
295 iterator BeginValue;
296 iterator PastEndValue;
297 };
298
299 /// Iterate over an integral type from Begin up to - but not including - End.
300 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
301 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
302 /// iteration).
303 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value &&
304 !std::is_enum<T>::value>>
seq(T Begin,T End)305 auto seq(T Begin, T End) {
306 return iota_range<T>(Begin, End, false);
307 }
308
309 /// Iterate over an integral type from 0 up to - but not including - Size.
310 /// Note: Size value has to be within [INTMAX_MIN, INTMAX_MAX - 1] for
311 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
312 /// iteration).
313 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value &&
314 !std::is_enum<T>::value>>
seq(T Size)315 auto seq(T Size) {
316 return seq<T>(0, Size);
317 }
318
319 /// Iterate over an integral type from Begin to End inclusive.
320 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
321 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
322 /// iteration).
323 template <typename T, typename = std::enable_if_t<std::is_integral<T>::value &&
324 !std::is_enum<T>::value>>
seq_inclusive(T Begin,T End)325 auto seq_inclusive(T Begin, T End) {
326 return iota_range<T>(Begin, End, true);
327 }
328
329 /// Iterate over an enum type from Begin up to - but not including - End.
330 /// Note: `enum_seq` will generate each consecutive value, even if no
331 /// enumerator with that value exists.
332 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
333 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
334 /// iteration).
335 template <typename EnumT,
336 typename = std::enable_if_t<std::is_enum<EnumT>::value>>
enum_seq(EnumT Begin,EnumT End)337 auto enum_seq(EnumT Begin, EnumT End) {
338 static_assert(enum_iteration_traits<EnumT>::is_iterable,
339 "Enum type is not marked as iterable.");
340 return iota_range<EnumT>(Begin, End, false);
341 }
342
343 /// Iterate over an enum type from Begin up to - but not including - End, even
344 /// when `EnumT` is not marked as safely iterable by `enum_iteration_traits`.
345 /// Note: `enum_seq` will generate each consecutive value, even if no
346 /// enumerator with that value exists.
347 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for
348 /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse
349 /// iteration).
350 template <typename EnumT,
351 typename = std::enable_if_t<std::is_enum<EnumT>::value>>
enum_seq(EnumT Begin,EnumT End,force_iteration_on_noniterable_enum_t)352 auto enum_seq(EnumT Begin, EnumT End, force_iteration_on_noniterable_enum_t) {
353 return iota_range<EnumT>(Begin, End, false);
354 }
355
356 /// Iterate over an enum type from Begin to End inclusive.
357 /// Note: `enum_seq_inclusive` will generate each consecutive value, even if no
358 /// enumerator with that value exists.
359 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
360 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
361 /// iteration).
362 template <typename EnumT,
363 typename = std::enable_if_t<std::is_enum<EnumT>::value>>
enum_seq_inclusive(EnumT Begin,EnumT End)364 auto enum_seq_inclusive(EnumT Begin, EnumT End) {
365 static_assert(enum_iteration_traits<EnumT>::is_iterable,
366 "Enum type is not marked as iterable.");
367 return iota_range<EnumT>(Begin, End, true);
368 }
369
370 /// Iterate over an enum type from Begin to End inclusive, even when `EnumT`
371 /// is not marked as safely iterable by `enum_iteration_traits`.
372 /// Note: `enum_seq_inclusive` will generate each consecutive value, even if no
373 /// enumerator with that value exists.
374 /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1]
375 /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse
376 /// iteration).
377 template <typename EnumT,
378 typename = std::enable_if_t<std::is_enum<EnumT>::value>>
enum_seq_inclusive(EnumT Begin,EnumT End,force_iteration_on_noniterable_enum_t)379 auto enum_seq_inclusive(EnumT Begin, EnumT End,
380 force_iteration_on_noniterable_enum_t) {
381 return iota_range<EnumT>(Begin, End, true);
382 }
383
384 } // end namespace llvm
385
386 #endif // LLVM_ADT_SEQUENCE_H
387