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. |
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> |
130 | 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> |
141 | 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(X: Value, Y: Offset, Result&: Result.Value)) |
153 | assertOutOfBounds(); |
154 | return Result; |
155 | } |
156 | |
157 | intmax_t operator-(CheckedInt Other) const { |
158 | intmax_t Result; |
159 | if (SubOverflow(X: Value, Y: 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> |
167 | 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> |
177 | Enum to() const { |
178 | using type = std::underlying_type_t<Enum>; |
179 | return Enum(to<type>()); |
180 | } |
181 | |
182 | private: |
183 | 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. |
196 | explicit SafeIntIterator(T Value) : SI(CheckedInt::from<T>(Value)) {} |
197 | // Construct from other direction. |
198 | 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(Offset: 1); } |
216 | void operator--() { offset(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: -Offset); } |
233 | |
234 | // Arithmetic |
235 | SafeIntIterator operator+(intmax_t Offset) const { return add(Offset); } |
236 | SafeIntIterator operator-(intmax_t Offset) const { return add(Offset: -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: |
244 | SafeIntIterator(const CheckedInt &SI) : SI(SI) {} |
245 | |
246 | static intmax_t getOffset(intmax_t Offset) { |
247 | return IsReverse ? -Offset : Offset; |
248 | } |
249 | |
250 | CheckedInt add(intmax_t Offset) const { return SI + getOffset(Offset); } |
251 | |
252 | 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 | |
273 | 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 | |
280 | size_t size() const { return PastEndValue - BeginValue; } |
281 | bool empty() const { return BeginValue == PastEndValue; } |
282 | |
283 | auto begin() const { return const_iterator(BeginValue); } |
284 | auto end() const { return const_iterator(PastEndValue); } |
285 | |
286 | auto rbegin() const { return const_reverse_iterator(PastEndValue - 1); } |
287 | 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>> |
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>> |
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>> |
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>> |
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>> |
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>> |
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>> |
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 | |