1 | //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- 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 | /// \file |
10 | /// This file contains some templates that are useful if you are working with |
11 | /// the STL at all. |
12 | /// |
13 | /// No library is required when using these functions. |
14 | /// |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #ifndef LLVM_ADT_STLEXTRAS_H |
18 | #define |
19 | |
20 | #include "llvm/ADT/ADL.h" |
21 | #include "llvm/ADT/Hashing.h" |
22 | #include "llvm/ADT/STLForwardCompat.h" |
23 | #include "llvm/ADT/STLFunctionalExtras.h" |
24 | #include "llvm/ADT/iterator.h" |
25 | #include "llvm/ADT/iterator_range.h" |
26 | #include "llvm/Config/abi-breaking.h" |
27 | #include "llvm/Support/ErrorHandling.h" |
28 | #include <algorithm> |
29 | #include <cassert> |
30 | #include <cstddef> |
31 | #include <cstdint> |
32 | #include <cstdlib> |
33 | #include <functional> |
34 | #include <initializer_list> |
35 | #include <iterator> |
36 | #include <limits> |
37 | #include <memory> |
38 | #include <optional> |
39 | #include <tuple> |
40 | #include <type_traits> |
41 | #include <utility> |
42 | |
43 | #ifdef EXPENSIVE_CHECKS |
44 | #include <random> // for std::mt19937 |
45 | #endif |
46 | |
47 | namespace llvm { |
48 | |
49 | //===----------------------------------------------------------------------===// |
50 | // Extra additions to <type_traits> |
51 | //===----------------------------------------------------------------------===// |
52 | |
53 | template <typename T> struct make_const_ptr { |
54 | using type = std::add_pointer_t<std::add_const_t<T>>; |
55 | }; |
56 | |
57 | template <typename T> struct make_const_ref { |
58 | using type = std::add_lvalue_reference_t<std::add_const_t<T>>; |
59 | }; |
60 | |
61 | namespace detail { |
62 | template <class, template <class...> class Op, class... Args> struct detector { |
63 | using value_t = std::false_type; |
64 | }; |
65 | template <template <class...> class Op, class... Args> |
66 | struct detector<std::void_t<Op<Args...>>, Op, Args...> { |
67 | using value_t = std::true_type; |
68 | }; |
69 | } // end namespace detail |
70 | |
71 | /// Detects if a given trait holds for some set of arguments 'Args'. |
72 | /// For example, the given trait could be used to detect if a given type |
73 | /// has a copy assignment operator: |
74 | /// template<class T> |
75 | /// using has_copy_assign_t = decltype(std::declval<T&>() |
76 | /// = std::declval<const T&>()); |
77 | /// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value; |
78 | template <template <class...> class Op, class... Args> |
79 | using is_detected = typename detail::detector<void, Op, Args...>::value_t; |
80 | |
81 | /// This class provides various trait information about a callable object. |
82 | /// * To access the number of arguments: Traits::num_args |
83 | /// * To access the type of an argument: Traits::arg_t<Index> |
84 | /// * To access the type of the result: Traits::result_t |
85 | template <typename T, bool isClass = std::is_class<T>::value> |
86 | struct function_traits : public function_traits<decltype(&T::operator())> {}; |
87 | |
88 | /// Overload for class function types. |
89 | template <typename ClassType, typename ReturnType, typename... Args> |
90 | struct function_traits<ReturnType (ClassType::*)(Args...) const, false> { |
91 | /// The number of arguments to this function. |
92 | enum { num_args = sizeof...(Args) }; |
93 | |
94 | /// The result type of this function. |
95 | using result_t = ReturnType; |
96 | |
97 | /// The type of an argument to this function. |
98 | template <size_t Index> |
99 | using arg_t = std::tuple_element_t<Index, std::tuple<Args...>>; |
100 | }; |
101 | /// Overload for class function types. |
102 | template <typename ClassType, typename ReturnType, typename... Args> |
103 | struct function_traits<ReturnType (ClassType::*)(Args...), false> |
104 | : public function_traits<ReturnType (ClassType::*)(Args...) const> {}; |
105 | /// Overload for non-class function types. |
106 | template <typename ReturnType, typename... Args> |
107 | struct function_traits<ReturnType (*)(Args...), false> { |
108 | /// The number of arguments to this function. |
109 | enum { num_args = sizeof...(Args) }; |
110 | |
111 | /// The result type of this function. |
112 | using result_t = ReturnType; |
113 | |
114 | /// The type of an argument to this function. |
115 | template <size_t i> |
116 | using arg_t = std::tuple_element_t<i, std::tuple<Args...>>; |
117 | }; |
118 | template <typename ReturnType, typename... Args> |
119 | struct function_traits<ReturnType (*const)(Args...), false> |
120 | : public function_traits<ReturnType (*)(Args...)> {}; |
121 | /// Overload for non-class function type references. |
122 | template <typename ReturnType, typename... Args> |
123 | struct function_traits<ReturnType (&)(Args...), false> |
124 | : public function_traits<ReturnType (*)(Args...)> {}; |
125 | |
126 | /// traits class for checking whether type T is one of any of the given |
127 | /// types in the variadic list. |
128 | template <typename T, typename... Ts> |
129 | using is_one_of = std::disjunction<std::is_same<T, Ts>...>; |
130 | |
131 | /// traits class for checking whether type T is a base class for all |
132 | /// the given types in the variadic list. |
133 | template <typename T, typename... Ts> |
134 | using are_base_of = std::conjunction<std::is_base_of<T, Ts>...>; |
135 | |
136 | namespace detail { |
137 | template <typename T, typename... Us> struct TypesAreDistinct; |
138 | template <typename T, typename... Us> |
139 | struct TypesAreDistinct |
140 | : std::integral_constant<bool, !is_one_of<T, Us...>::value && |
141 | TypesAreDistinct<Us...>::value> {}; |
142 | template <typename T> struct TypesAreDistinct<T> : std::true_type {}; |
143 | } // namespace detail |
144 | |
145 | /// Determine if all types in Ts are distinct. |
146 | /// |
147 | /// Useful to statically assert when Ts is intended to describe a non-multi set |
148 | /// of types. |
149 | /// |
150 | /// Expensive (currently quadratic in sizeof(Ts...)), and so should only be |
151 | /// asserted once per instantiation of a type which requires it. |
152 | template <typename... Ts> struct TypesAreDistinct; |
153 | template <> struct TypesAreDistinct<> : std::true_type {}; |
154 | template <typename... Ts> |
155 | struct TypesAreDistinct |
156 | : std::integral_constant<bool, detail::TypesAreDistinct<Ts...>::value> {}; |
157 | |
158 | /// Find the first index where a type appears in a list of types. |
159 | /// |
160 | /// FirstIndexOfType<T, Us...>::value is the first index of T in Us. |
161 | /// |
162 | /// Typically only meaningful when it is otherwise statically known that the |
163 | /// type pack has no duplicate types. This should be guaranteed explicitly with |
164 | /// static_assert(TypesAreDistinct<Us...>::value). |
165 | /// |
166 | /// It is a compile-time error to instantiate when T is not present in Us, i.e. |
167 | /// if is_one_of<T, Us...>::value is false. |
168 | template <typename T, typename... Us> struct FirstIndexOfType; |
169 | template <typename T, typename U, typename... Us> |
170 | struct FirstIndexOfType<T, U, Us...> |
171 | : std::integral_constant<size_t, 1 + FirstIndexOfType<T, Us...>::value> {}; |
172 | template <typename T, typename... Us> |
173 | struct FirstIndexOfType<T, T, Us...> : std::integral_constant<size_t, 0> {}; |
174 | |
175 | /// Find the type at a given index in a list of types. |
176 | /// |
177 | /// TypeAtIndex<I, Ts...> is the type at index I in Ts. |
178 | template <size_t I, typename... Ts> |
179 | using TypeAtIndex = std::tuple_element_t<I, std::tuple<Ts...>>; |
180 | |
181 | /// Helper which adds two underlying types of enumeration type. |
182 | /// Implicit conversion to a common type is accepted. |
183 | template <typename EnumTy1, typename EnumTy2, |
184 | typename UT1 = std::enable_if_t<std::is_enum<EnumTy1>::value, |
185 | std::underlying_type_t<EnumTy1>>, |
186 | typename UT2 = std::enable_if_t<std::is_enum<EnumTy2>::value, |
187 | std::underlying_type_t<EnumTy2>>> |
188 | constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS) { |
189 | return static_cast<UT1>(LHS) + static_cast<UT2>(RHS); |
190 | } |
191 | |
192 | //===----------------------------------------------------------------------===// |
193 | // Extra additions to <iterator> |
194 | //===----------------------------------------------------------------------===// |
195 | |
196 | namespace callable_detail { |
197 | |
198 | /// Templated storage wrapper for a callable. |
199 | /// |
200 | /// This class is consistently default constructible, copy / move |
201 | /// constructible / assignable. |
202 | /// |
203 | /// Supported callable types: |
204 | /// - Function pointer |
205 | /// - Function reference |
206 | /// - Lambda |
207 | /// - Function object |
208 | template <typename T, |
209 | bool = std::is_function_v<std::remove_pointer_t<remove_cvref_t<T>>>> |
210 | class Callable { |
211 | using value_type = std::remove_reference_t<T>; |
212 | using reference = value_type &; |
213 | using const_reference = value_type const &; |
214 | |
215 | std::optional<value_type> Obj; |
216 | |
217 | static_assert(!std::is_pointer_v<value_type>, |
218 | "Pointers to non-functions are not callable." ); |
219 | |
220 | public: |
221 | Callable() = default; |
222 | Callable(T const &O) : Obj(std::in_place, O) {} |
223 | |
224 | Callable(Callable const &Other) = default; |
225 | Callable(Callable &&Other) = default; |
226 | |
227 | Callable &operator=(Callable const &Other) { |
228 | Obj = std::nullopt; |
229 | if (Other.Obj) |
230 | Obj.emplace(*Other.Obj); |
231 | return *this; |
232 | } |
233 | |
234 | Callable &operator=(Callable &&Other) { |
235 | Obj = std::nullopt; |
236 | if (Other.Obj) |
237 | Obj.emplace(std::move(*Other.Obj)); |
238 | return *this; |
239 | } |
240 | |
241 | template <typename... Pn, |
242 | std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0> |
243 | decltype(auto) operator()(Pn &&...Params) { |
244 | return (*Obj)(std::forward<Pn>(Params)...); |
245 | } |
246 | |
247 | template <typename... Pn, |
248 | std::enable_if_t<std::is_invocable_v<T const, Pn...>, int> = 0> |
249 | decltype(auto) operator()(Pn &&...Params) const { |
250 | return (*Obj)(std::forward<Pn>(Params)...); |
251 | } |
252 | |
253 | bool valid() const { return Obj != std::nullopt; } |
254 | bool reset() { return Obj = std::nullopt; } |
255 | |
256 | operator reference() { return *Obj; } |
257 | operator const_reference() const { return *Obj; } |
258 | }; |
259 | |
260 | // Function specialization. No need to waste extra space wrapping with a |
261 | // std::optional. |
262 | template <typename T> class Callable<T, true> { |
263 | static constexpr bool IsPtr = std::is_pointer_v<remove_cvref_t<T>>; |
264 | |
265 | using StorageT = std::conditional_t<IsPtr, T, std::remove_reference_t<T> *>; |
266 | using CastT = std::conditional_t<IsPtr, T, T &>; |
267 | |
268 | private: |
269 | StorageT Func = nullptr; |
270 | |
271 | private: |
272 | template <typename In> static constexpr auto convertIn(In &&I) { |
273 | if constexpr (IsPtr) { |
274 | // Pointer... just echo it back. |
275 | return I; |
276 | } else { |
277 | // Must be a function reference. Return its address. |
278 | return &I; |
279 | } |
280 | } |
281 | |
282 | public: |
283 | Callable() = default; |
284 | |
285 | // Construct from a function pointer or reference. |
286 | // |
287 | // Disable this constructor for references to 'Callable' so we don't violate |
288 | // the rule of 0. |
289 | template < // clang-format off |
290 | typename FnPtrOrRef, |
291 | std::enable_if_t< |
292 | !std::is_same_v<remove_cvref_t<FnPtrOrRef>, Callable>, int |
293 | > = 0 |
294 | > // clang-format on |
295 | Callable(FnPtrOrRef &&F) : Func(convertIn(F)) {} |
296 | |
297 | template <typename... Pn, |
298 | std::enable_if_t<std::is_invocable_v<T, Pn...>, int> = 0> |
299 | decltype(auto) operator()(Pn &&...Params) const { |
300 | return Func(std::forward<Pn>(Params)...); |
301 | } |
302 | |
303 | bool valid() const { return Func != nullptr; } |
304 | void reset() { Func = nullptr; } |
305 | |
306 | operator T const &() const { |
307 | if constexpr (IsPtr) { |
308 | // T is a pointer... just echo it back. |
309 | return Func; |
310 | } else { |
311 | static_assert(std::is_reference_v<T>, |
312 | "Expected a reference to a function." ); |
313 | // T is a function reference... dereference the stored pointer. |
314 | return *Func; |
315 | } |
316 | } |
317 | }; |
318 | |
319 | } // namespace callable_detail |
320 | |
321 | /// Returns true if the given container only contains a single element. |
322 | template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) { |
323 | auto B = std::begin(C), E = std::end(C); |
324 | return B != E && std::next(B) == E; |
325 | } |
326 | |
327 | /// Return a range covering \p RangeOrContainer with the first N elements |
328 | /// excluded. |
329 | template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N = 1) { |
330 | return make_range(std::next(adl_begin(RangeOrContainer), N), |
331 | adl_end(RangeOrContainer)); |
332 | } |
333 | |
334 | /// Return a range covering \p RangeOrContainer with the last N elements |
335 | /// excluded. |
336 | template <typename T> auto drop_end(T &&RangeOrContainer, size_t N = 1) { |
337 | return make_range(adl_begin(RangeOrContainer), |
338 | std::prev(adl_end(RangeOrContainer), N)); |
339 | } |
340 | |
341 | // mapped_iterator - This is a simple iterator adapter that causes a function to |
342 | // be applied whenever operator* is invoked on the iterator. |
343 | |
344 | template <typename ItTy, typename FuncTy, |
345 | typename ReferenceTy = |
346 | decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> |
347 | class mapped_iterator |
348 | : public iterator_adaptor_base< |
349 | mapped_iterator<ItTy, FuncTy>, ItTy, |
350 | typename std::iterator_traits<ItTy>::iterator_category, |
351 | std::remove_reference_t<ReferenceTy>, |
352 | typename std::iterator_traits<ItTy>::difference_type, |
353 | std::remove_reference_t<ReferenceTy> *, ReferenceTy> { |
354 | public: |
355 | mapped_iterator() = default; |
356 | mapped_iterator(ItTy U, FuncTy F) |
357 | : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {} |
358 | |
359 | ItTy getCurrent() { return this->I; } |
360 | |
361 | const FuncTy &getFunction() const { return F; } |
362 | |
363 | ReferenceTy operator*() const { return F(*this->I); } |
364 | |
365 | private: |
366 | callable_detail::Callable<FuncTy> F{}; |
367 | }; |
368 | |
369 | // map_iterator - Provide a convenient way to create mapped_iterators, just like |
370 | // make_pair is useful for creating pairs... |
371 | template <class ItTy, class FuncTy> |
372 | inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) { |
373 | return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F)); |
374 | } |
375 | |
376 | template <class ContainerTy, class FuncTy> |
377 | auto map_range(ContainerTy &&C, FuncTy F) { |
378 | return make_range(map_iterator(std::begin(C), F), |
379 | map_iterator(std::end(C), F)); |
380 | } |
381 | |
382 | /// A base type of mapped iterator, that is useful for building derived |
383 | /// iterators that do not need/want to store the map function (as in |
384 | /// mapped_iterator). These iterators must simply provide a `mapElement` method |
385 | /// that defines how to map a value of the iterator to the provided reference |
386 | /// type. |
387 | template <typename DerivedT, typename ItTy, typename ReferenceTy> |
388 | class mapped_iterator_base |
389 | : public iterator_adaptor_base< |
390 | DerivedT, ItTy, |
391 | typename std::iterator_traits<ItTy>::iterator_category, |
392 | std::remove_reference_t<ReferenceTy>, |
393 | typename std::iterator_traits<ItTy>::difference_type, |
394 | std::remove_reference_t<ReferenceTy> *, ReferenceTy> { |
395 | public: |
396 | using BaseT = mapped_iterator_base; |
397 | |
398 | mapped_iterator_base(ItTy U) |
399 | : mapped_iterator_base::iterator_adaptor_base(std::move(U)) {} |
400 | |
401 | ItTy getCurrent() { return this->I; } |
402 | |
403 | ReferenceTy operator*() const { |
404 | return static_cast<const DerivedT &>(*this).mapElement(*this->I); |
405 | } |
406 | }; |
407 | |
408 | namespace detail { |
409 | template <typename Range> |
410 | using check_has_free_function_rbegin = |
411 | decltype(adl_rbegin(std::declval<Range &>())); |
412 | |
413 | template <typename Range> |
414 | static constexpr bool HasFreeFunctionRBegin = |
415 | is_detected<check_has_free_function_rbegin, Range>::value; |
416 | } // namespace detail |
417 | |
418 | // Returns an iterator_range over the given container which iterates in reverse. |
419 | template <typename ContainerTy> auto reverse(ContainerTy &&C) { |
420 | if constexpr (detail::HasFreeFunctionRBegin<ContainerTy>) |
421 | return make_range(adl_rbegin(C), adl_rend(C)); |
422 | else |
423 | return make_range(std::make_reverse_iterator(adl_end(C)), |
424 | std::make_reverse_iterator(adl_begin(C))); |
425 | } |
426 | |
427 | /// An iterator adaptor that filters the elements of given inner iterators. |
428 | /// |
429 | /// The predicate parameter should be a callable object that accepts the wrapped |
430 | /// iterator's reference type and returns a bool. When incrementing or |
431 | /// decrementing the iterator, it will call the predicate on each element and |
432 | /// skip any where it returns false. |
433 | /// |
434 | /// \code |
435 | /// int A[] = { 1, 2, 3, 4 }; |
436 | /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); |
437 | /// // R contains { 1, 3 }. |
438 | /// \endcode |
439 | /// |
440 | /// Note: filter_iterator_base implements support for forward iteration. |
441 | /// filter_iterator_impl exists to provide support for bidirectional iteration, |
442 | /// conditional on whether the wrapped iterator supports it. |
443 | template <typename WrappedIteratorT, typename PredicateT, typename IterTag> |
444 | class filter_iterator_base |
445 | : public iterator_adaptor_base< |
446 | filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>, |
447 | WrappedIteratorT, |
448 | std::common_type_t<IterTag, |
449 | typename std::iterator_traits< |
450 | WrappedIteratorT>::iterator_category>> { |
451 | using BaseT = typename filter_iterator_base::iterator_adaptor_base; |
452 | |
453 | protected: |
454 | WrappedIteratorT End; |
455 | PredicateT Pred; |
456 | |
457 | void findNextValid() { |
458 | while (this->I != End && !Pred(*this->I)) |
459 | BaseT::operator++(); |
460 | } |
461 | |
462 | filter_iterator_base() = default; |
463 | |
464 | // Construct the iterator. The begin iterator needs to know where the end |
465 | // is, so that it can properly stop when it gets there. The end iterator only |
466 | // needs the predicate to support bidirectional iteration. |
467 | filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End, |
468 | PredicateT Pred) |
469 | : BaseT(Begin), End(End), Pred(Pred) { |
470 | findNextValid(); |
471 | } |
472 | |
473 | public: |
474 | using BaseT::operator++; |
475 | |
476 | filter_iterator_base &operator++() { |
477 | BaseT::operator++(); |
478 | findNextValid(); |
479 | return *this; |
480 | } |
481 | |
482 | decltype(auto) operator*() const { |
483 | assert(BaseT::wrapped() != End && "Cannot dereference end iterator!" ); |
484 | return BaseT::operator*(); |
485 | } |
486 | |
487 | decltype(auto) operator->() const { |
488 | assert(BaseT::wrapped() != End && "Cannot dereference end iterator!" ); |
489 | return BaseT::operator->(); |
490 | } |
491 | }; |
492 | |
493 | /// Specialization of filter_iterator_base for forward iteration only. |
494 | template <typename WrappedIteratorT, typename PredicateT, |
495 | typename IterTag = std::forward_iterator_tag> |
496 | class filter_iterator_impl |
497 | : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> { |
498 | public: |
499 | filter_iterator_impl() = default; |
500 | |
501 | filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, |
502 | PredicateT Pred) |
503 | : filter_iterator_impl::filter_iterator_base(Begin, End, Pred) {} |
504 | }; |
505 | |
506 | /// Specialization of filter_iterator_base for bidirectional iteration. |
507 | template <typename WrappedIteratorT, typename PredicateT> |
508 | class filter_iterator_impl<WrappedIteratorT, PredicateT, |
509 | std::bidirectional_iterator_tag> |
510 | : public filter_iterator_base<WrappedIteratorT, PredicateT, |
511 | std::bidirectional_iterator_tag> { |
512 | using BaseT = typename filter_iterator_impl::filter_iterator_base; |
513 | |
514 | void findPrevValid() { |
515 | while (!this->Pred(*this->I)) |
516 | BaseT::operator--(); |
517 | } |
518 | |
519 | public: |
520 | using BaseT::operator--; |
521 | |
522 | filter_iterator_impl() = default; |
523 | |
524 | filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, |
525 | PredicateT Pred) |
526 | : BaseT(Begin, End, Pred) {} |
527 | |
528 | filter_iterator_impl &operator--() { |
529 | BaseT::operator--(); |
530 | findPrevValid(); |
531 | return *this; |
532 | } |
533 | }; |
534 | |
535 | namespace detail { |
536 | |
537 | template <bool is_bidirectional> struct fwd_or_bidi_tag_impl { |
538 | using type = std::forward_iterator_tag; |
539 | }; |
540 | |
541 | template <> struct fwd_or_bidi_tag_impl<true> { |
542 | using type = std::bidirectional_iterator_tag; |
543 | }; |
544 | |
545 | /// Helper which sets its type member to forward_iterator_tag if the category |
546 | /// of \p IterT does not derive from bidirectional_iterator_tag, and to |
547 | /// bidirectional_iterator_tag otherwise. |
548 | template <typename IterT> struct fwd_or_bidi_tag { |
549 | using type = typename fwd_or_bidi_tag_impl<std::is_base_of< |
550 | std::bidirectional_iterator_tag, |
551 | typename std::iterator_traits<IterT>::iterator_category>::value>::type; |
552 | }; |
553 | |
554 | } // namespace detail |
555 | |
556 | /// Defines filter_iterator to a suitable specialization of |
557 | /// filter_iterator_impl, based on the underlying iterator's category. |
558 | template <typename WrappedIteratorT, typename PredicateT> |
559 | using filter_iterator = filter_iterator_impl< |
560 | WrappedIteratorT, PredicateT, |
561 | typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>; |
562 | |
563 | /// Convenience function that takes a range of elements and a predicate, |
564 | /// and return a new filter_iterator range. |
565 | /// |
566 | /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the |
567 | /// lifetime of that temporary is not kept by the returned range object, and the |
568 | /// temporary is going to be dropped on the floor after the make_iterator_range |
569 | /// full expression that contains this function call. |
570 | template <typename RangeT, typename PredicateT> |
571 | iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> |
572 | make_filter_range(RangeT &&Range, PredicateT Pred) { |
573 | using FilterIteratorT = |
574 | filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; |
575 | return make_range( |
576 | FilterIteratorT(std::begin(std::forward<RangeT>(Range)), |
577 | std::end(std::forward<RangeT>(Range)), Pred), |
578 | FilterIteratorT(std::end(std::forward<RangeT>(Range)), |
579 | std::end(std::forward<RangeT>(Range)), Pred)); |
580 | } |
581 | |
582 | /// A pseudo-iterator adaptor that is designed to implement "early increment" |
583 | /// style loops. |
584 | /// |
585 | /// This is *not a normal iterator* and should almost never be used directly. It |
586 | /// is intended primarily to be used with range based for loops and some range |
587 | /// algorithms. |
588 | /// |
589 | /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but |
590 | /// somewhere between them. The constraints of these iterators are: |
591 | /// |
592 | /// - On construction or after being incremented, it is comparable and |
593 | /// dereferencable. It is *not* incrementable. |
594 | /// - After being dereferenced, it is neither comparable nor dereferencable, it |
595 | /// is only incrementable. |
596 | /// |
597 | /// This means you can only dereference the iterator once, and you can only |
598 | /// increment it once between dereferences. |
599 | template <typename WrappedIteratorT> |
600 | class early_inc_iterator_impl |
601 | : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>, |
602 | WrappedIteratorT, std::input_iterator_tag> { |
603 | using BaseT = typename early_inc_iterator_impl::iterator_adaptor_base; |
604 | |
605 | using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer; |
606 | |
607 | protected: |
608 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS |
609 | bool IsEarlyIncremented = false; |
610 | #endif |
611 | |
612 | public: |
613 | early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {} |
614 | |
615 | using BaseT::operator*; |
616 | decltype(*std::declval<WrappedIteratorT>()) operator*() { |
617 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS |
618 | assert(!IsEarlyIncremented && "Cannot dereference twice!" ); |
619 | IsEarlyIncremented = true; |
620 | #endif |
621 | return *(this->I)++; |
622 | } |
623 | |
624 | using BaseT::operator++; |
625 | early_inc_iterator_impl &operator++() { |
626 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS |
627 | assert(IsEarlyIncremented && "Cannot increment before dereferencing!" ); |
628 | IsEarlyIncremented = false; |
629 | #endif |
630 | return *this; |
631 | } |
632 | |
633 | friend bool operator==(const early_inc_iterator_impl &LHS, |
634 | const early_inc_iterator_impl &RHS) { |
635 | #if LLVM_ENABLE_ABI_BREAKING_CHECKS |
636 | assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!" ); |
637 | #endif |
638 | return (const BaseT &)LHS == (const BaseT &)RHS; |
639 | } |
640 | }; |
641 | |
642 | /// Make a range that does early increment to allow mutation of the underlying |
643 | /// range without disrupting iteration. |
644 | /// |
645 | /// The underlying iterator will be incremented immediately after it is |
646 | /// dereferenced, allowing deletion of the current node or insertion of nodes to |
647 | /// not disrupt iteration provided they do not invalidate the *next* iterator -- |
648 | /// the current iterator can be invalidated. |
649 | /// |
650 | /// This requires a very exact pattern of use that is only really suitable to |
651 | /// range based for loops and other range algorithms that explicitly guarantee |
652 | /// to dereference exactly once each element, and to increment exactly once each |
653 | /// element. |
654 | template <typename RangeT> |
655 | iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>> |
656 | make_early_inc_range(RangeT &&Range) { |
657 | using EarlyIncIteratorT = |
658 | early_inc_iterator_impl<detail::IterOfRange<RangeT>>; |
659 | return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))), |
660 | EarlyIncIteratorT(std::end(std::forward<RangeT>(Range)))); |
661 | } |
662 | |
663 | // Forward declarations required by zip_shortest/zip_equal/zip_first/zip_longest |
664 | template <typename R, typename UnaryPredicate> |
665 | bool all_of(R &&range, UnaryPredicate P); |
666 | |
667 | template <typename R, typename UnaryPredicate> |
668 | bool any_of(R &&range, UnaryPredicate P); |
669 | |
670 | template <typename T> bool all_equal(std::initializer_list<T> Values); |
671 | |
672 | template <typename R> constexpr size_t range_size(R &&Range); |
673 | |
674 | namespace detail { |
675 | |
676 | using std::declval; |
677 | |
678 | // We have to alias this since inlining the actual type at the usage site |
679 | // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. |
680 | template<typename... Iters> struct ZipTupleType { |
681 | using type = std::tuple<decltype(*declval<Iters>())...>; |
682 | }; |
683 | |
684 | template <typename ZipType, typename ReferenceTupleType, typename... Iters> |
685 | using zip_traits = iterator_facade_base< |
686 | ZipType, |
687 | std::common_type_t< |
688 | std::bidirectional_iterator_tag, |
689 | typename std::iterator_traits<Iters>::iterator_category...>, |
690 | // ^ TODO: Implement random access methods. |
691 | ReferenceTupleType, |
692 | typename std::iterator_traits< |
693 | std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type, |
694 | // ^ FIXME: This follows boost::make_zip_iterator's assumption that all |
695 | // inner iterators have the same difference_type. It would fail if, for |
696 | // instance, the second field's difference_type were non-numeric while the |
697 | // first is. |
698 | ReferenceTupleType *, ReferenceTupleType>; |
699 | |
700 | template <typename ZipType, typename ReferenceTupleType, typename... Iters> |
701 | struct zip_common : public zip_traits<ZipType, ReferenceTupleType, Iters...> { |
702 | using Base = zip_traits<ZipType, ReferenceTupleType, Iters...>; |
703 | using IndexSequence = std::index_sequence_for<Iters...>; |
704 | using value_type = typename Base::value_type; |
705 | |
706 | std::tuple<Iters...> iterators; |
707 | |
708 | protected: |
709 | template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const { |
710 | return value_type(*std::get<Ns>(iterators)...); |
711 | } |
712 | |
713 | template <size_t... Ns> void tup_inc(std::index_sequence<Ns...>) { |
714 | (++std::get<Ns>(iterators), ...); |
715 | } |
716 | |
717 | template <size_t... Ns> void tup_dec(std::index_sequence<Ns...>) { |
718 | (--std::get<Ns>(iterators), ...); |
719 | } |
720 | |
721 | template <size_t... Ns> |
722 | bool test_all_equals(const zip_common &other, |
723 | std::index_sequence<Ns...>) const { |
724 | return ((std::get<Ns>(this->iterators) == std::get<Ns>(other.iterators)) && |
725 | ...); |
726 | } |
727 | |
728 | public: |
729 | zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} |
730 | |
731 | value_type operator*() const { return deref(IndexSequence{}); } |
732 | |
733 | ZipType &operator++() { |
734 | tup_inc(IndexSequence{}); |
735 | return static_cast<ZipType &>(*this); |
736 | } |
737 | |
738 | ZipType &operator--() { |
739 | static_assert(Base::IsBidirectional, |
740 | "All inner iterators must be at least bidirectional." ); |
741 | tup_dec(IndexSequence{}); |
742 | return static_cast<ZipType &>(*this); |
743 | } |
744 | |
745 | /// Return true if all the iterator are matching `other`'s iterators. |
746 | bool all_equals(zip_common &other) { |
747 | return test_all_equals(other, IndexSequence{}); |
748 | } |
749 | }; |
750 | |
751 | template <typename... Iters> |
752 | struct zip_first : zip_common<zip_first<Iters...>, |
753 | typename ZipTupleType<Iters...>::type, Iters...> { |
754 | using zip_common<zip_first, typename ZipTupleType<Iters...>::type, |
755 | Iters...>::zip_common; |
756 | |
757 | bool operator==(const zip_first &other) const { |
758 | return std::get<0>(this->iterators) == std::get<0>(other.iterators); |
759 | } |
760 | }; |
761 | |
762 | template <typename... Iters> |
763 | struct zip_shortest |
764 | : zip_common<zip_shortest<Iters...>, typename ZipTupleType<Iters...>::type, |
765 | Iters...> { |
766 | using zip_common<zip_shortest, typename ZipTupleType<Iters...>::type, |
767 | Iters...>::zip_common; |
768 | |
769 | bool operator==(const zip_shortest &other) const { |
770 | return any_iterator_equals(other, std::index_sequence_for<Iters...>{}); |
771 | } |
772 | |
773 | private: |
774 | template <size_t... Ns> |
775 | bool any_iterator_equals(const zip_shortest &other, |
776 | std::index_sequence<Ns...>) const { |
777 | return ((std::get<Ns>(this->iterators) == std::get<Ns>(other.iterators)) || |
778 | ...); |
779 | } |
780 | }; |
781 | |
782 | /// Helper to obtain the iterator types for the tuple storage within `zippy`. |
783 | template <template <typename...> class ItType, typename TupleStorageType, |
784 | typename IndexSequence> |
785 | struct ZippyIteratorTuple; |
786 | |
787 | /// Partial specialization for non-const tuple storage. |
788 | template <template <typename...> class ItType, typename... Args, |
789 | std::size_t... Ns> |
790 | struct ZippyIteratorTuple<ItType, std::tuple<Args...>, |
791 | std::index_sequence<Ns...>> { |
792 | using type = ItType<decltype(adl_begin( |
793 | std::get<Ns>(declval<std::tuple<Args...> &>())))...>; |
794 | }; |
795 | |
796 | /// Partial specialization for const tuple storage. |
797 | template <template <typename...> class ItType, typename... Args, |
798 | std::size_t... Ns> |
799 | struct ZippyIteratorTuple<ItType, const std::tuple<Args...>, |
800 | std::index_sequence<Ns...>> { |
801 | using type = ItType<decltype(adl_begin( |
802 | std::get<Ns>(declval<const std::tuple<Args...> &>())))...>; |
803 | }; |
804 | |
805 | template <template <typename...> class ItType, typename... Args> class zippy { |
806 | private: |
807 | std::tuple<Args...> storage; |
808 | using IndexSequence = std::index_sequence_for<Args...>; |
809 | |
810 | public: |
811 | using iterator = typename ZippyIteratorTuple<ItType, decltype(storage), |
812 | IndexSequence>::type; |
813 | using const_iterator = |
814 | typename ZippyIteratorTuple<ItType, const decltype(storage), |
815 | IndexSequence>::type; |
816 | using iterator_category = typename iterator::iterator_category; |
817 | using value_type = typename iterator::value_type; |
818 | using difference_type = typename iterator::difference_type; |
819 | using pointer = typename iterator::pointer; |
820 | using reference = typename iterator::reference; |
821 | using const_reference = typename const_iterator::reference; |
822 | |
823 | zippy(Args &&...args) : storage(std::forward<Args>(args)...) {} |
824 | |
825 | const_iterator begin() const { return begin_impl(IndexSequence{}); } |
826 | iterator begin() { return begin_impl(IndexSequence{}); } |
827 | const_iterator end() const { return end_impl(IndexSequence{}); } |
828 | iterator end() { return end_impl(IndexSequence{}); } |
829 | |
830 | private: |
831 | template <size_t... Ns> |
832 | const_iterator begin_impl(std::index_sequence<Ns...>) const { |
833 | return const_iterator(adl_begin(std::get<Ns>(storage))...); |
834 | } |
835 | template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) { |
836 | return iterator(adl_begin(std::get<Ns>(storage))...); |
837 | } |
838 | |
839 | template <size_t... Ns> |
840 | const_iterator end_impl(std::index_sequence<Ns...>) const { |
841 | return const_iterator(adl_end(std::get<Ns>(storage))...); |
842 | } |
843 | template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) { |
844 | return iterator(adl_end(std::get<Ns>(storage))...); |
845 | } |
846 | }; |
847 | |
848 | } // end namespace detail |
849 | |
850 | /// zip iterator for two or more iteratable types. Iteration continues until the |
851 | /// end of the *shortest* iteratee is reached. |
852 | template <typename T, typename U, typename... Args> |
853 | detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, |
854 | Args &&...args) { |
855 | return detail::zippy<detail::zip_shortest, T, U, Args...>( |
856 | std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); |
857 | } |
858 | |
859 | /// zip iterator that assumes that all iteratees have the same length. |
860 | /// In builds with assertions on, this assumption is checked before the |
861 | /// iteration starts. |
862 | template <typename T, typename U, typename... Args> |
863 | detail::zippy<detail::zip_first, T, U, Args...> zip_equal(T &&t, U &&u, |
864 | Args &&...args) { |
865 | assert(all_equal({range_size(t), range_size(u), range_size(args)...}) && |
866 | "Iteratees do not have equal length" ); |
867 | return detail::zippy<detail::zip_first, T, U, Args...>( |
868 | std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); |
869 | } |
870 | |
871 | /// zip iterator that, for the sake of efficiency, assumes the first iteratee to |
872 | /// be the shortest. Iteration continues until the end of the first iteratee is |
873 | /// reached. In builds with assertions on, we check that the assumption about |
874 | /// the first iteratee being the shortest holds. |
875 | template <typename T, typename U, typename... Args> |
876 | detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, |
877 | Args &&...args) { |
878 | assert(range_size(t) <= std::min({range_size(u), range_size(args)...}) && |
879 | "First iteratee is not the shortest" ); |
880 | |
881 | return detail::zippy<detail::zip_first, T, U, Args...>( |
882 | std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); |
883 | } |
884 | |
885 | namespace detail { |
886 | template <typename Iter> |
887 | Iter next_or_end(const Iter &I, const Iter &End) { |
888 | if (I == End) |
889 | return End; |
890 | return std::next(I); |
891 | } |
892 | |
893 | template <typename Iter> |
894 | auto deref_or_none(const Iter &I, const Iter &End) -> std::optional< |
895 | std::remove_const_t<std::remove_reference_t<decltype(*I)>>> { |
896 | if (I == End) |
897 | return std::nullopt; |
898 | return *I; |
899 | } |
900 | |
901 | template <typename Iter> struct ZipLongestItemType { |
902 | using type = std::optional<std::remove_const_t< |
903 | std::remove_reference_t<decltype(*std::declval<Iter>())>>>; |
904 | }; |
905 | |
906 | template <typename... Iters> struct ZipLongestTupleType { |
907 | using type = std::tuple<typename ZipLongestItemType<Iters>::type...>; |
908 | }; |
909 | |
910 | template <typename... Iters> |
911 | class zip_longest_iterator |
912 | : public iterator_facade_base< |
913 | zip_longest_iterator<Iters...>, |
914 | std::common_type_t< |
915 | std::forward_iterator_tag, |
916 | typename std::iterator_traits<Iters>::iterator_category...>, |
917 | typename ZipLongestTupleType<Iters...>::type, |
918 | typename std::iterator_traits< |
919 | std::tuple_element_t<0, std::tuple<Iters...>>>::difference_type, |
920 | typename ZipLongestTupleType<Iters...>::type *, |
921 | typename ZipLongestTupleType<Iters...>::type> { |
922 | public: |
923 | using value_type = typename ZipLongestTupleType<Iters...>::type; |
924 | |
925 | private: |
926 | std::tuple<Iters...> iterators; |
927 | std::tuple<Iters...> end_iterators; |
928 | |
929 | template <size_t... Ns> |
930 | bool test(const zip_longest_iterator<Iters...> &other, |
931 | std::index_sequence<Ns...>) const { |
932 | return ((std::get<Ns>(this->iterators) != std::get<Ns>(other.iterators)) || |
933 | ...); |
934 | } |
935 | |
936 | template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const { |
937 | return value_type( |
938 | deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...); |
939 | } |
940 | |
941 | template <size_t... Ns> |
942 | decltype(iterators) tup_inc(std::index_sequence<Ns...>) const { |
943 | return std::tuple<Iters...>( |
944 | next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...); |
945 | } |
946 | |
947 | public: |
948 | zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts) |
949 | : iterators(std::forward<Iters>(ts.first)...), |
950 | end_iterators(std::forward<Iters>(ts.second)...) {} |
951 | |
952 | value_type operator*() const { |
953 | return deref(std::index_sequence_for<Iters...>{}); |
954 | } |
955 | |
956 | zip_longest_iterator<Iters...> &operator++() { |
957 | iterators = tup_inc(std::index_sequence_for<Iters...>{}); |
958 | return *this; |
959 | } |
960 | |
961 | bool operator==(const zip_longest_iterator<Iters...> &other) const { |
962 | return !test(other, std::index_sequence_for<Iters...>{}); |
963 | } |
964 | }; |
965 | |
966 | template <typename... Args> class zip_longest_range { |
967 | public: |
968 | using iterator = |
969 | zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>; |
970 | using iterator_category = typename iterator::iterator_category; |
971 | using value_type = typename iterator::value_type; |
972 | using difference_type = typename iterator::difference_type; |
973 | using pointer = typename iterator::pointer; |
974 | using reference = typename iterator::reference; |
975 | |
976 | private: |
977 | std::tuple<Args...> ts; |
978 | |
979 | template <size_t... Ns> |
980 | iterator begin_impl(std::index_sequence<Ns...>) const { |
981 | return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)), |
982 | adl_end(std::get<Ns>(ts)))...); |
983 | } |
984 | |
985 | template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const { |
986 | return iterator(std::make_pair(adl_end(std::get<Ns>(ts)), |
987 | adl_end(std::get<Ns>(ts)))...); |
988 | } |
989 | |
990 | public: |
991 | zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} |
992 | |
993 | iterator begin() const { |
994 | return begin_impl(std::index_sequence_for<Args...>{}); |
995 | } |
996 | iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); } |
997 | }; |
998 | } // namespace detail |
999 | |
1000 | /// Iterate over two or more iterators at the same time. Iteration continues |
1001 | /// until all iterators reach the end. The std::optional only contains a value |
1002 | /// if the iterator has not reached the end. |
1003 | template <typename T, typename U, typename... Args> |
1004 | detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u, |
1005 | Args &&... args) { |
1006 | return detail::zip_longest_range<T, U, Args...>( |
1007 | std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); |
1008 | } |
1009 | |
1010 | /// Iterator wrapper that concatenates sequences together. |
1011 | /// |
1012 | /// This can concatenate different iterators, even with different types, into |
1013 | /// a single iterator provided the value types of all the concatenated |
1014 | /// iterators expose `reference` and `pointer` types that can be converted to |
1015 | /// `ValueT &` and `ValueT *` respectively. It doesn't support more |
1016 | /// interesting/customized pointer or reference types. |
1017 | /// |
1018 | /// Currently this only supports forward or higher iterator categories as |
1019 | /// inputs and always exposes a forward iterator interface. |
1020 | template <typename ValueT, typename... IterTs> |
1021 | class concat_iterator |
1022 | : public iterator_facade_base<concat_iterator<ValueT, IterTs...>, |
1023 | std::forward_iterator_tag, ValueT> { |
1024 | using BaseT = typename concat_iterator::iterator_facade_base; |
1025 | |
1026 | /// We store both the current and end iterators for each concatenated |
1027 | /// sequence in a tuple of pairs. |
1028 | /// |
1029 | /// Note that something like iterator_range seems nice at first here, but the |
1030 | /// range properties are of little benefit and end up getting in the way |
1031 | /// because we need to do mutation on the current iterators. |
1032 | std::tuple<IterTs...> Begins; |
1033 | std::tuple<IterTs...> Ends; |
1034 | |
1035 | /// Attempts to increment a specific iterator. |
1036 | /// |
1037 | /// Returns true if it was able to increment the iterator. Returns false if |
1038 | /// the iterator is already at the end iterator. |
1039 | template <size_t Index> bool incrementHelper() { |
1040 | auto &Begin = std::get<Index>(Begins); |
1041 | auto &End = std::get<Index>(Ends); |
1042 | if (Begin == End) |
1043 | return false; |
1044 | |
1045 | ++Begin; |
1046 | return true; |
1047 | } |
1048 | |
1049 | /// Increments the first non-end iterator. |
1050 | /// |
1051 | /// It is an error to call this with all iterators at the end. |
1052 | template <size_t... Ns> void increment(std::index_sequence<Ns...>) { |
1053 | // Build a sequence of functions to increment each iterator if possible. |
1054 | bool (concat_iterator::*IncrementHelperFns[])() = { |
1055 | &concat_iterator::incrementHelper<Ns>...}; |
1056 | |
1057 | // Loop over them, and stop as soon as we succeed at incrementing one. |
1058 | for (auto &IncrementHelperFn : IncrementHelperFns) |
1059 | if ((this->*IncrementHelperFn)()) |
1060 | return; |
1061 | |
1062 | llvm_unreachable("Attempted to increment an end concat iterator!" ); |
1063 | } |
1064 | |
1065 | /// Returns null if the specified iterator is at the end. Otherwise, |
1066 | /// dereferences the iterator and returns the address of the resulting |
1067 | /// reference. |
1068 | template <size_t Index> ValueT *getHelper() const { |
1069 | auto &Begin = std::get<Index>(Begins); |
1070 | auto &End = std::get<Index>(Ends); |
1071 | if (Begin == End) |
1072 | return nullptr; |
1073 | |
1074 | return &*Begin; |
1075 | } |
1076 | |
1077 | /// Finds the first non-end iterator, dereferences, and returns the resulting |
1078 | /// reference. |
1079 | /// |
1080 | /// It is an error to call this with all iterators at the end. |
1081 | template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const { |
1082 | // Build a sequence of functions to get from iterator if possible. |
1083 | ValueT *(concat_iterator::*GetHelperFns[])() const = { |
1084 | &concat_iterator::getHelper<Ns>...}; |
1085 | |
1086 | // Loop over them, and return the first result we find. |
1087 | for (auto &GetHelperFn : GetHelperFns) |
1088 | if (ValueT *P = (this->*GetHelperFn)()) |
1089 | return *P; |
1090 | |
1091 | llvm_unreachable("Attempted to get a pointer from an end concat iterator!" ); |
1092 | } |
1093 | |
1094 | public: |
1095 | /// Constructs an iterator from a sequence of ranges. |
1096 | /// |
1097 | /// We need the full range to know how to switch between each of the |
1098 | /// iterators. |
1099 | template <typename... RangeTs> |
1100 | explicit concat_iterator(RangeTs &&... Ranges) |
1101 | : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {} |
1102 | |
1103 | using BaseT::operator++; |
1104 | |
1105 | concat_iterator &operator++() { |
1106 | increment(std::index_sequence_for<IterTs...>()); |
1107 | return *this; |
1108 | } |
1109 | |
1110 | ValueT &operator*() const { |
1111 | return get(std::index_sequence_for<IterTs...>()); |
1112 | } |
1113 | |
1114 | bool operator==(const concat_iterator &RHS) const { |
1115 | return Begins == RHS.Begins && Ends == RHS.Ends; |
1116 | } |
1117 | }; |
1118 | |
1119 | namespace detail { |
1120 | |
1121 | /// Helper to store a sequence of ranges being concatenated and access them. |
1122 | /// |
1123 | /// This is designed to facilitate providing actual storage when temporaries |
1124 | /// are passed into the constructor such that we can use it as part of range |
1125 | /// based for loops. |
1126 | template <typename ValueT, typename... RangeTs> class concat_range { |
1127 | public: |
1128 | using iterator = |
1129 | concat_iterator<ValueT, |
1130 | decltype(std::begin(std::declval<RangeTs &>()))...>; |
1131 | |
1132 | private: |
1133 | std::tuple<RangeTs...> Ranges; |
1134 | |
1135 | template <size_t... Ns> |
1136 | iterator begin_impl(std::index_sequence<Ns...>) { |
1137 | return iterator(std::get<Ns>(Ranges)...); |
1138 | } |
1139 | template <size_t... Ns> |
1140 | iterator begin_impl(std::index_sequence<Ns...>) const { |
1141 | return iterator(std::get<Ns>(Ranges)...); |
1142 | } |
1143 | template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) { |
1144 | return iterator(make_range(std::end(std::get<Ns>(Ranges)), |
1145 | std::end(std::get<Ns>(Ranges)))...); |
1146 | } |
1147 | template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const { |
1148 | return iterator(make_range(std::end(std::get<Ns>(Ranges)), |
1149 | std::end(std::get<Ns>(Ranges)))...); |
1150 | } |
1151 | |
1152 | public: |
1153 | concat_range(RangeTs &&... Ranges) |
1154 | : Ranges(std::forward<RangeTs>(Ranges)...) {} |
1155 | |
1156 | iterator begin() { |
1157 | return begin_impl(std::index_sequence_for<RangeTs...>{}); |
1158 | } |
1159 | iterator begin() const { |
1160 | return begin_impl(std::index_sequence_for<RangeTs...>{}); |
1161 | } |
1162 | iterator end() { |
1163 | return end_impl(std::index_sequence_for<RangeTs...>{}); |
1164 | } |
1165 | iterator end() const { |
1166 | return end_impl(std::index_sequence_for<RangeTs...>{}); |
1167 | } |
1168 | }; |
1169 | |
1170 | } // end namespace detail |
1171 | |
1172 | /// Concatenated range across two or more ranges. |
1173 | /// |
1174 | /// The desired value type must be explicitly specified. |
1175 | template <typename ValueT, typename... RangeTs> |
1176 | detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) { |
1177 | static_assert(sizeof...(RangeTs) > 1, |
1178 | "Need more than one range to concatenate!" ); |
1179 | return detail::concat_range<ValueT, RangeTs...>( |
1180 | std::forward<RangeTs>(Ranges)...); |
1181 | } |
1182 | |
1183 | /// A utility class used to implement an iterator that contains some base object |
1184 | /// and an index. The iterator moves the index but keeps the base constant. |
1185 | template <typename DerivedT, typename BaseT, typename T, |
1186 | typename PointerT = T *, typename ReferenceT = T &> |
1187 | class indexed_accessor_iterator |
1188 | : public llvm::iterator_facade_base<DerivedT, |
1189 | std::random_access_iterator_tag, T, |
1190 | std::ptrdiff_t, PointerT, ReferenceT> { |
1191 | public: |
1192 | ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const { |
1193 | assert(base == rhs.base && "incompatible iterators" ); |
1194 | return index - rhs.index; |
1195 | } |
1196 | bool operator==(const indexed_accessor_iterator &rhs) const { |
1197 | return base == rhs.base && index == rhs.index; |
1198 | } |
1199 | bool operator<(const indexed_accessor_iterator &rhs) const { |
1200 | assert(base == rhs.base && "incompatible iterators" ); |
1201 | return index < rhs.index; |
1202 | } |
1203 | |
1204 | DerivedT &operator+=(ptrdiff_t offset) { |
1205 | this->index += offset; |
1206 | return static_cast<DerivedT &>(*this); |
1207 | } |
1208 | DerivedT &operator-=(ptrdiff_t offset) { |
1209 | this->index -= offset; |
1210 | return static_cast<DerivedT &>(*this); |
1211 | } |
1212 | |
1213 | /// Returns the current index of the iterator. |
1214 | ptrdiff_t getIndex() const { return index; } |
1215 | |
1216 | /// Returns the current base of the iterator. |
1217 | const BaseT &getBase() const { return base; } |
1218 | |
1219 | protected: |
1220 | indexed_accessor_iterator(BaseT base, ptrdiff_t index) |
1221 | : base(base), index(index) {} |
1222 | BaseT base; |
1223 | ptrdiff_t index; |
1224 | }; |
1225 | |
1226 | namespace detail { |
1227 | /// The class represents the base of a range of indexed_accessor_iterators. It |
1228 | /// provides support for many different range functionalities, e.g. |
1229 | /// drop_front/slice/etc.. Derived range classes must implement the following |
1230 | /// static methods: |
1231 | /// * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index) |
1232 | /// - Dereference an iterator pointing to the base object at the given |
1233 | /// index. |
1234 | /// * BaseT offset_base(const BaseT &base, ptrdiff_t index) |
1235 | /// - Return a new base that is offset from the provide base by 'index' |
1236 | /// elements. |
1237 | template <typename DerivedT, typename BaseT, typename T, |
1238 | typename PointerT = T *, typename ReferenceT = T &> |
1239 | class indexed_accessor_range_base { |
1240 | public: |
1241 | using RangeBaseT = indexed_accessor_range_base; |
1242 | |
1243 | /// An iterator element of this range. |
1244 | class iterator : public indexed_accessor_iterator<iterator, BaseT, T, |
1245 | PointerT, ReferenceT> { |
1246 | public: |
1247 | // Index into this iterator, invoking a static method on the derived type. |
1248 | ReferenceT operator*() const { |
1249 | return DerivedT::dereference_iterator(this->getBase(), this->getIndex()); |
1250 | } |
1251 | |
1252 | private: |
1253 | iterator(BaseT owner, ptrdiff_t curIndex) |
1254 | : iterator::indexed_accessor_iterator(owner, curIndex) {} |
1255 | |
1256 | /// Allow access to the constructor. |
1257 | friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, |
1258 | ReferenceT>; |
1259 | }; |
1260 | |
1261 | indexed_accessor_range_base(iterator begin, iterator end) |
1262 | : base(offset_base(base: begin.getBase(), n: begin.getIndex())), |
1263 | count(end.getIndex() - begin.getIndex()) {} |
1264 | indexed_accessor_range_base(const iterator_range<iterator> &range) |
1265 | : indexed_accessor_range_base(range.begin(), range.end()) {} |
1266 | indexed_accessor_range_base(BaseT base, ptrdiff_t count) |
1267 | : base(base), count(count) {} |
1268 | |
1269 | iterator begin() const { return iterator(base, 0); } |
1270 | iterator end() const { return iterator(base, count); } |
1271 | ReferenceT operator[](size_t Index) const { |
1272 | assert(Index < size() && "invalid index for value range" ); |
1273 | return DerivedT::dereference_iterator(base, static_cast<ptrdiff_t>(Index)); |
1274 | } |
1275 | ReferenceT front() const { |
1276 | assert(!empty() && "expected non-empty range" ); |
1277 | return (*this)[0]; |
1278 | } |
1279 | ReferenceT back() const { |
1280 | assert(!empty() && "expected non-empty range" ); |
1281 | return (*this)[size() - 1]; |
1282 | } |
1283 | |
1284 | /// Return the size of this range. |
1285 | size_t size() const { return count; } |
1286 | |
1287 | /// Return if the range is empty. |
1288 | bool empty() const { return size() == 0; } |
1289 | |
1290 | /// Drop the first N elements, and keep M elements. |
1291 | DerivedT slice(size_t n, size_t m) const { |
1292 | assert(n + m <= size() && "invalid size specifiers" ); |
1293 | return DerivedT(offset_base(base, n), m); |
1294 | } |
1295 | |
1296 | /// Drop the first n elements. |
1297 | DerivedT drop_front(size_t n = 1) const { |
1298 | assert(size() >= n && "Dropping more elements than exist" ); |
1299 | return slice(n, m: size() - n); |
1300 | } |
1301 | /// Drop the last n elements. |
1302 | DerivedT drop_back(size_t n = 1) const { |
1303 | assert(size() >= n && "Dropping more elements than exist" ); |
1304 | return DerivedT(base, size() - n); |
1305 | } |
1306 | |
1307 | /// Take the first n elements. |
1308 | DerivedT take_front(size_t n = 1) const { |
1309 | return n < size() ? drop_back(n: size() - n) |
1310 | : static_cast<const DerivedT &>(*this); |
1311 | } |
1312 | |
1313 | /// Take the last n elements. |
1314 | DerivedT take_back(size_t n = 1) const { |
1315 | return n < size() ? drop_front(n: size() - n) |
1316 | : static_cast<const DerivedT &>(*this); |
1317 | } |
1318 | |
1319 | /// Allow conversion to any type accepting an iterator_range. |
1320 | template <typename RangeT, typename = std::enable_if_t<std::is_constructible< |
1321 | RangeT, iterator_range<iterator>>::value>> |
1322 | operator RangeT() const { |
1323 | return RangeT(iterator_range<iterator>(*this)); |
1324 | } |
1325 | |
1326 | /// Returns the base of this range. |
1327 | const BaseT &getBase() const { return base; } |
1328 | |
1329 | private: |
1330 | /// Offset the given base by the given amount. |
1331 | static BaseT offset_base(const BaseT &base, size_t n) { |
1332 | return n == 0 ? base : DerivedT::offset_base(base, n); |
1333 | } |
1334 | |
1335 | protected: |
1336 | indexed_accessor_range_base(const indexed_accessor_range_base &) = default; |
1337 | indexed_accessor_range_base(indexed_accessor_range_base &&) = default; |
1338 | indexed_accessor_range_base & |
1339 | operator=(const indexed_accessor_range_base &) = default; |
1340 | |
1341 | /// The base that owns the provided range of values. |
1342 | BaseT base; |
1343 | /// The size from the owning range. |
1344 | ptrdiff_t count; |
1345 | }; |
1346 | /// Compare this range with another. |
1347 | /// FIXME: Make me a member function instead of friend when it works in C++20. |
1348 | template <typename OtherT, typename DerivedT, typename BaseT, typename T, |
1349 | typename PointerT, typename ReferenceT> |
1350 | bool operator==(const indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, |
1351 | ReferenceT> &lhs, |
1352 | const OtherT &rhs) { |
1353 | return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); |
1354 | } |
1355 | |
1356 | template <typename OtherT, typename DerivedT, typename BaseT, typename T, |
1357 | typename PointerT, typename ReferenceT> |
1358 | bool operator!=(const indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, |
1359 | ReferenceT> &lhs, |
1360 | const OtherT &rhs) { |
1361 | return !(lhs == rhs); |
1362 | } |
1363 | } // end namespace detail |
1364 | |
1365 | /// This class provides an implementation of a range of |
1366 | /// indexed_accessor_iterators where the base is not indexable. Ranges with |
1367 | /// bases that are offsetable should derive from indexed_accessor_range_base |
1368 | /// instead. Derived range classes are expected to implement the following |
1369 | /// static method: |
1370 | /// * ReferenceT dereference(const BaseT &base, ptrdiff_t index) |
1371 | /// - Dereference an iterator pointing to a parent base at the given index. |
1372 | template <typename DerivedT, typename BaseT, typename T, |
1373 | typename PointerT = T *, typename ReferenceT = T &> |
1374 | class indexed_accessor_range |
1375 | : public detail::indexed_accessor_range_base< |
1376 | DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> { |
1377 | public: |
1378 | indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count) |
1379 | : detail::indexed_accessor_range_base< |
1380 | DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>( |
1381 | std::make_pair(base, startIndex), count) {} |
1382 | using detail::indexed_accessor_range_base< |
1383 | DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, |
1384 | ReferenceT>::indexed_accessor_range_base; |
1385 | |
1386 | /// Returns the current base of the range. |
1387 | const BaseT &getBase() const { return this->base.first; } |
1388 | |
1389 | /// Returns the current start index of the range. |
1390 | ptrdiff_t getStartIndex() const { return this->base.second; } |
1391 | |
1392 | /// See `detail::indexed_accessor_range_base` for details. |
1393 | static std::pair<BaseT, ptrdiff_t> |
1394 | offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) { |
1395 | // We encode the internal base as a pair of the derived base and a start |
1396 | // index into the derived base. |
1397 | return std::make_pair(base.first, base.second + index); |
1398 | } |
1399 | /// See `detail::indexed_accessor_range_base` for details. |
1400 | static ReferenceT |
1401 | dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base, |
1402 | ptrdiff_t index) { |
1403 | return DerivedT::dereference(base.first, base.second + index); |
1404 | } |
1405 | }; |
1406 | |
1407 | namespace detail { |
1408 | /// Return a reference to the first or second member of a reference. Otherwise, |
1409 | /// return a copy of the member of a temporary. |
1410 | /// |
1411 | /// When passing a range whose iterators return values instead of references, |
1412 | /// the reference must be dropped from `decltype((elt.first))`, which will |
1413 | /// always be a reference, to avoid returning a reference to a temporary. |
1414 | template <typename EltTy, typename FirstTy> class first_or_second_type { |
1415 | public: |
1416 | using type = std::conditional_t<std::is_reference<EltTy>::value, FirstTy, |
1417 | std::remove_reference_t<FirstTy>>; |
1418 | }; |
1419 | } // end namespace detail |
1420 | |
1421 | /// Given a container of pairs, return a range over the first elements. |
1422 | template <typename ContainerTy> auto make_first_range(ContainerTy &&c) { |
1423 | using EltTy = decltype((*std::begin(c))); |
1424 | return llvm::map_range(std::forward<ContainerTy>(c), |
1425 | [](EltTy elt) -> typename detail::first_or_second_type< |
1426 | EltTy, decltype((elt.first))>::type { |
1427 | return elt.first; |
1428 | }); |
1429 | } |
1430 | |
1431 | /// Given a container of pairs, return a range over the second elements. |
1432 | template <typename ContainerTy> auto make_second_range(ContainerTy &&c) { |
1433 | using EltTy = decltype((*std::begin(c))); |
1434 | return llvm::map_range( |
1435 | std::forward<ContainerTy>(c), |
1436 | [](EltTy elt) -> |
1437 | typename detail::first_or_second_type<EltTy, |
1438 | decltype((elt.second))>::type { |
1439 | return elt.second; |
1440 | }); |
1441 | } |
1442 | |
1443 | //===----------------------------------------------------------------------===// |
1444 | // Extra additions to <utility> |
1445 | //===----------------------------------------------------------------------===// |
1446 | |
1447 | /// Function object to check whether the first component of a container |
1448 | /// supported by std::get (like std::pair and std::tuple) compares less than the |
1449 | /// first component of another container. |
1450 | struct less_first { |
1451 | template <typename T> bool operator()(const T &lhs, const T &rhs) const { |
1452 | return std::less<>()(std::get<0>(lhs), std::get<0>(rhs)); |
1453 | } |
1454 | }; |
1455 | |
1456 | /// Function object to check whether the second component of a container |
1457 | /// supported by std::get (like std::pair and std::tuple) compares less than the |
1458 | /// second component of another container. |
1459 | struct less_second { |
1460 | template <typename T> bool operator()(const T &lhs, const T &rhs) const { |
1461 | return std::less<>()(std::get<1>(lhs), std::get<1>(rhs)); |
1462 | } |
1463 | }; |
1464 | |
1465 | /// \brief Function object to apply a binary function to the first component of |
1466 | /// a std::pair. |
1467 | template<typename FuncTy> |
1468 | struct on_first { |
1469 | FuncTy func; |
1470 | |
1471 | template <typename T> |
1472 | decltype(auto) operator()(const T &lhs, const T &rhs) const { |
1473 | return func(lhs.first, rhs.first); |
1474 | } |
1475 | }; |
1476 | |
1477 | /// Utility type to build an inheritance chain that makes it easy to rank |
1478 | /// overload candidates. |
1479 | template <int N> struct rank : rank<N - 1> {}; |
1480 | template <> struct rank<0> {}; |
1481 | |
1482 | namespace detail { |
1483 | template <typename... Ts> struct Visitor; |
1484 | |
1485 | template <typename HeadT, typename... TailTs> |
1486 | struct Visitor<HeadT, TailTs...> : remove_cvref_t<HeadT>, Visitor<TailTs...> { |
1487 | explicit constexpr Visitor(HeadT &&Head, TailTs &&...Tail) |
1488 | : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)), |
1489 | Visitor<TailTs...>(std::forward<TailTs>(Tail)...) {} |
1490 | using remove_cvref_t<HeadT>::operator(); |
1491 | using Visitor<TailTs...>::operator(); |
1492 | }; |
1493 | |
1494 | template <typename HeadT> struct Visitor<HeadT> : remove_cvref_t<HeadT> { |
1495 | explicit constexpr Visitor(HeadT &&Head) |
1496 | : remove_cvref_t<HeadT>(std::forward<HeadT>(Head)) {} |
1497 | using remove_cvref_t<HeadT>::operator(); |
1498 | }; |
1499 | } // namespace detail |
1500 | |
1501 | /// Returns an opaquely-typed Callable object whose operator() overload set is |
1502 | /// the sum of the operator() overload sets of each CallableT in CallableTs. |
1503 | /// |
1504 | /// The type of the returned object derives from each CallableT in CallableTs. |
1505 | /// The returned object is constructed by invoking the appropriate copy or move |
1506 | /// constructor of each CallableT, as selected by overload resolution on the |
1507 | /// corresponding argument to makeVisitor. |
1508 | /// |
1509 | /// Example: |
1510 | /// |
1511 | /// \code |
1512 | /// auto visitor = makeVisitor([](auto) { return "unhandled type"; }, |
1513 | /// [](int i) { return "int"; }, |
1514 | /// [](std::string s) { return "str"; }); |
1515 | /// auto a = visitor(42); // `a` is now "int". |
1516 | /// auto b = visitor("foo"); // `b` is now "str". |
1517 | /// auto c = visitor(3.14f); // `c` is now "unhandled type". |
1518 | /// \endcode |
1519 | /// |
1520 | /// Example of making a visitor with a lambda which captures a move-only type: |
1521 | /// |
1522 | /// \code |
1523 | /// std::unique_ptr<FooHandler> FH = /* ... */; |
1524 | /// auto visitor = makeVisitor( |
1525 | /// [FH{std::move(FH)}](Foo F) { return FH->handle(F); }, |
1526 | /// [](int i) { return i; }, |
1527 | /// [](std::string s) { return atoi(s); }); |
1528 | /// \endcode |
1529 | template <typename... CallableTs> |
1530 | constexpr decltype(auto) makeVisitor(CallableTs &&...Callables) { |
1531 | return detail::Visitor<CallableTs...>(std::forward<CallableTs>(Callables)...); |
1532 | } |
1533 | |
1534 | //===----------------------------------------------------------------------===// |
1535 | // Extra additions to <algorithm> |
1536 | //===----------------------------------------------------------------------===// |
1537 | |
1538 | // We have a copy here so that LLVM behaves the same when using different |
1539 | // standard libraries. |
1540 | template <class Iterator, class RNG> |
1541 | void shuffle(Iterator first, Iterator last, RNG &&g) { |
1542 | // It would be better to use a std::uniform_int_distribution, |
1543 | // but that would be stdlib dependent. |
1544 | typedef |
1545 | typename std::iterator_traits<Iterator>::difference_type difference_type; |
1546 | for (auto size = last - first; size > 1; ++first, (void)--size) { |
1547 | difference_type offset = g() % size; |
1548 | // Avoid self-assignment due to incorrect assertions in libstdc++ |
1549 | // containers (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85828). |
1550 | if (offset != difference_type(0)) |
1551 | std::iter_swap(first, first + offset); |
1552 | } |
1553 | } |
1554 | |
1555 | /// Adapt std::less<T> for array_pod_sort. |
1556 | template<typename T> |
1557 | inline int array_pod_sort_comparator(const void *P1, const void *P2) { |
1558 | if (std::less<T>()(*reinterpret_cast<const T*>(P1), |
1559 | *reinterpret_cast<const T*>(P2))) |
1560 | return -1; |
1561 | if (std::less<T>()(*reinterpret_cast<const T*>(P2), |
1562 | *reinterpret_cast<const T*>(P1))) |
1563 | return 1; |
1564 | return 0; |
1565 | } |
1566 | |
1567 | /// get_array_pod_sort_comparator - This is an internal helper function used to |
1568 | /// get type deduction of T right. |
1569 | template<typename T> |
1570 | inline int (*get_array_pod_sort_comparator(const T &)) |
1571 | (const void*, const void*) { |
1572 | return array_pod_sort_comparator<T>; |
1573 | } |
1574 | |
1575 | #ifdef EXPENSIVE_CHECKS |
1576 | namespace detail { |
1577 | |
1578 | inline unsigned presortShuffleEntropy() { |
1579 | static unsigned Result(std::random_device{}()); |
1580 | return Result; |
1581 | } |
1582 | |
1583 | template <class IteratorTy> |
1584 | inline void presortShuffle(IteratorTy Start, IteratorTy End) { |
1585 | std::mt19937 Generator(presortShuffleEntropy()); |
1586 | llvm::shuffle(Start, End, Generator); |
1587 | } |
1588 | |
1589 | } // end namespace detail |
1590 | #endif |
1591 | |
1592 | /// array_pod_sort - This sorts an array with the specified start and end |
1593 | /// extent. This is just like std::sort, except that it calls qsort instead of |
1594 | /// using an inlined template. qsort is slightly slower than std::sort, but |
1595 | /// most sorts are not performance critical in LLVM and std::sort has to be |
1596 | /// template instantiated for each type, leading to significant measured code |
1597 | /// bloat. This function should generally be used instead of std::sort where |
1598 | /// possible. |
1599 | /// |
1600 | /// This function assumes that you have simple POD-like types that can be |
1601 | /// compared with std::less and can be moved with memcpy. If this isn't true, |
1602 | /// you should use std::sort. |
1603 | /// |
1604 | /// NOTE: If qsort_r were portable, we could allow a custom comparator and |
1605 | /// default to std::less. |
1606 | template<class IteratorTy> |
1607 | inline void array_pod_sort(IteratorTy Start, IteratorTy End) { |
1608 | // Don't inefficiently call qsort with one element or trigger undefined |
1609 | // behavior with an empty sequence. |
1610 | auto NElts = End - Start; |
1611 | if (NElts <= 1) return; |
1612 | #ifdef EXPENSIVE_CHECKS |
1613 | detail::presortShuffle<IteratorTy>(Start, End); |
1614 | #endif |
1615 | qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); |
1616 | } |
1617 | |
1618 | template <class IteratorTy> |
1619 | inline void array_pod_sort( |
1620 | IteratorTy Start, IteratorTy End, |
1621 | int (*Compare)( |
1622 | const typename std::iterator_traits<IteratorTy>::value_type *, |
1623 | const typename std::iterator_traits<IteratorTy>::value_type *)) { |
1624 | // Don't inefficiently call qsort with one element or trigger undefined |
1625 | // behavior with an empty sequence. |
1626 | auto NElts = End - Start; |
1627 | if (NElts <= 1) return; |
1628 | #ifdef EXPENSIVE_CHECKS |
1629 | detail::presortShuffle<IteratorTy>(Start, End); |
1630 | #endif |
1631 | qsort(&*Start, NElts, sizeof(*Start), |
1632 | reinterpret_cast<int (*)(const void *, const void *)>(Compare)); |
1633 | } |
1634 | |
1635 | namespace detail { |
1636 | template <typename T> |
1637 | // We can use qsort if the iterator type is a pointer and the underlying value |
1638 | // is trivially copyable. |
1639 | using sort_trivially_copyable = std::conjunction< |
1640 | std::is_pointer<T>, |
1641 | std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>; |
1642 | } // namespace detail |
1643 | |
1644 | // Provide wrappers to std::sort which shuffle the elements before sorting |
1645 | // to help uncover non-deterministic behavior (PR35135). |
1646 | template <typename IteratorTy> |
1647 | inline void sort(IteratorTy Start, IteratorTy End) { |
1648 | if constexpr (detail::sort_trivially_copyable<IteratorTy>::value) { |
1649 | // Forward trivially copyable types to array_pod_sort. This avoids a large |
1650 | // amount of code bloat for a minor performance hit. |
1651 | array_pod_sort(Start, End); |
1652 | } else { |
1653 | #ifdef EXPENSIVE_CHECKS |
1654 | detail::presortShuffle<IteratorTy>(Start, End); |
1655 | #endif |
1656 | std::sort(Start, End); |
1657 | } |
1658 | } |
1659 | |
1660 | template <typename Container> inline void sort(Container &&C) { |
1661 | llvm::sort(adl_begin(C), adl_end(C)); |
1662 | } |
1663 | |
1664 | template <typename IteratorTy, typename Compare> |
1665 | inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) { |
1666 | #ifdef EXPENSIVE_CHECKS |
1667 | detail::presortShuffle<IteratorTy>(Start, End); |
1668 | #endif |
1669 | std::sort(Start, End, Comp); |
1670 | } |
1671 | |
1672 | template <typename Container, typename Compare> |
1673 | inline void sort(Container &&C, Compare Comp) { |
1674 | llvm::sort(adl_begin(C), adl_end(C), Comp); |
1675 | } |
1676 | |
1677 | /// Get the size of a range. This is a wrapper function around std::distance |
1678 | /// which is only enabled when the operation is O(1). |
1679 | template <typename R> |
1680 | auto size(R &&Range, |
1681 | std::enable_if_t< |
1682 | std::is_base_of<std::random_access_iterator_tag, |
1683 | typename std::iterator_traits<decltype( |
1684 | Range.begin())>::iterator_category>::value, |
1685 | void> * = nullptr) { |
1686 | return std::distance(Range.begin(), Range.end()); |
1687 | } |
1688 | |
1689 | namespace detail { |
1690 | template <typename Range> |
1691 | using check_has_free_function_size = |
1692 | decltype(adl_size(std::declval<Range &>())); |
1693 | |
1694 | template <typename Range> |
1695 | static constexpr bool HasFreeFunctionSize = |
1696 | is_detected<check_has_free_function_size, Range>::value; |
1697 | } // namespace detail |
1698 | |
1699 | /// Returns the size of the \p Range, i.e., the number of elements. This |
1700 | /// implementation takes inspiration from `std::ranges::size` from C++20 and |
1701 | /// delegates the size check to `adl_size` or `std::distance`, in this order of |
1702 | /// preference. Unlike `llvm::size`, this function does *not* guarantee O(1) |
1703 | /// running time, and is intended to be used in generic code that does not know |
1704 | /// the exact range type. |
1705 | template <typename R> constexpr size_t range_size(R &&Range) { |
1706 | if constexpr (detail::HasFreeFunctionSize<R>) |
1707 | return adl_size(Range); |
1708 | else |
1709 | return static_cast<size_t>(std::distance(adl_begin(Range), adl_end(Range))); |
1710 | } |
1711 | |
1712 | /// Provide wrappers to std::for_each which take ranges instead of having to |
1713 | /// pass begin/end explicitly. |
1714 | template <typename R, typename UnaryFunction> |
1715 | UnaryFunction for_each(R &&Range, UnaryFunction F) { |
1716 | return std::for_each(adl_begin(Range), adl_end(Range), F); |
1717 | } |
1718 | |
1719 | /// Provide wrappers to std::all_of which take ranges instead of having to pass |
1720 | /// begin/end explicitly. |
1721 | template <typename R, typename UnaryPredicate> |
1722 | bool all_of(R &&Range, UnaryPredicate P) { |
1723 | return std::all_of(adl_begin(Range), adl_end(Range), P); |
1724 | } |
1725 | |
1726 | /// Provide wrappers to std::any_of which take ranges instead of having to pass |
1727 | /// begin/end explicitly. |
1728 | template <typename R, typename UnaryPredicate> |
1729 | bool any_of(R &&Range, UnaryPredicate P) { |
1730 | return std::any_of(adl_begin(Range), adl_end(Range), P); |
1731 | } |
1732 | |
1733 | /// Provide wrappers to std::none_of which take ranges instead of having to pass |
1734 | /// begin/end explicitly. |
1735 | template <typename R, typename UnaryPredicate> |
1736 | bool none_of(R &&Range, UnaryPredicate P) { |
1737 | return std::none_of(adl_begin(Range), adl_end(Range), P); |
1738 | } |
1739 | |
1740 | /// Provide wrappers to std::find which take ranges instead of having to pass |
1741 | /// begin/end explicitly. |
1742 | template <typename R, typename T> auto find(R &&Range, const T &Val) { |
1743 | return std::find(adl_begin(Range), adl_end(Range), Val); |
1744 | } |
1745 | |
1746 | /// Provide wrappers to std::find_if which take ranges instead of having to pass |
1747 | /// begin/end explicitly. |
1748 | template <typename R, typename UnaryPredicate> |
1749 | auto find_if(R &&Range, UnaryPredicate P) { |
1750 | return std::find_if(adl_begin(Range), adl_end(Range), P); |
1751 | } |
1752 | |
1753 | template <typename R, typename UnaryPredicate> |
1754 | auto find_if_not(R &&Range, UnaryPredicate P) { |
1755 | return std::find_if_not(adl_begin(Range), adl_end(Range), P); |
1756 | } |
1757 | |
1758 | /// Provide wrappers to std::remove_if which take ranges instead of having to |
1759 | /// pass begin/end explicitly. |
1760 | template <typename R, typename UnaryPredicate> |
1761 | auto remove_if(R &&Range, UnaryPredicate P) { |
1762 | return std::remove_if(adl_begin(Range), adl_end(Range), P); |
1763 | } |
1764 | |
1765 | /// Provide wrappers to std::copy_if which take ranges instead of having to |
1766 | /// pass begin/end explicitly. |
1767 | template <typename R, typename OutputIt, typename UnaryPredicate> |
1768 | OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { |
1769 | return std::copy_if(adl_begin(Range), adl_end(Range), Out, P); |
1770 | } |
1771 | |
1772 | /// Return the single value in \p Range that satisfies |
1773 | /// \p P(<member of \p Range> *, AllowRepeats)->T * returning nullptr |
1774 | /// when no values or multiple values were found. |
1775 | /// When \p AllowRepeats is true, multiple values that compare equal |
1776 | /// are allowed. |
1777 | template <typename T, typename R, typename Predicate> |
1778 | T *find_singleton(R &&Range, Predicate P, bool AllowRepeats = false) { |
1779 | T *RC = nullptr; |
1780 | for (auto &&A : Range) { |
1781 | if (T *PRC = P(A, AllowRepeats)) { |
1782 | if (RC) { |
1783 | if (!AllowRepeats || PRC != RC) |
1784 | return nullptr; |
1785 | } else |
1786 | RC = PRC; |
1787 | } |
1788 | } |
1789 | return RC; |
1790 | } |
1791 | |
1792 | /// Return a pair consisting of the single value in \p Range that satisfies |
1793 | /// \p P(<member of \p Range> *, AllowRepeats)->std::pair<T*, bool> returning |
1794 | /// nullptr when no values or multiple values were found, and a bool indicating |
1795 | /// whether multiple values were found to cause the nullptr. |
1796 | /// When \p AllowRepeats is true, multiple values that compare equal are |
1797 | /// allowed. The predicate \p P returns a pair<T *, bool> where T is the |
1798 | /// singleton while the bool indicates whether multiples have already been |
1799 | /// found. It is expected that first will be nullptr when second is true. |
1800 | /// This allows using find_singleton_nested within the predicate \P. |
1801 | template <typename T, typename R, typename Predicate> |
1802 | std::pair<T *, bool> find_singleton_nested(R &&Range, Predicate P, |
1803 | bool AllowRepeats = false) { |
1804 | T *RC = nullptr; |
1805 | for (auto *A : Range) { |
1806 | std::pair<T *, bool> PRC = P(A, AllowRepeats); |
1807 | if (PRC.second) { |
1808 | assert(PRC.first == nullptr && |
1809 | "Inconsistent return values in find_singleton_nested." ); |
1810 | return PRC; |
1811 | } |
1812 | if (PRC.first) { |
1813 | if (RC) { |
1814 | if (!AllowRepeats || PRC.first != RC) |
1815 | return {nullptr, true}; |
1816 | } else |
1817 | RC = PRC.first; |
1818 | } |
1819 | } |
1820 | return {RC, false}; |
1821 | } |
1822 | |
1823 | template <typename R, typename OutputIt> |
1824 | OutputIt copy(R &&Range, OutputIt Out) { |
1825 | return std::copy(adl_begin(Range), adl_end(Range), Out); |
1826 | } |
1827 | |
1828 | /// Provide wrappers to std::replace_copy_if which take ranges instead of having |
1829 | /// to pass begin/end explicitly. |
1830 | template <typename R, typename OutputIt, typename UnaryPredicate, typename T> |
1831 | OutputIt replace_copy_if(R &&Range, OutputIt Out, UnaryPredicate P, |
1832 | const T &NewValue) { |
1833 | return std::replace_copy_if(adl_begin(Range), adl_end(Range), Out, P, |
1834 | NewValue); |
1835 | } |
1836 | |
1837 | /// Provide wrappers to std::replace_copy which take ranges instead of having to |
1838 | /// pass begin/end explicitly. |
1839 | template <typename R, typename OutputIt, typename T> |
1840 | OutputIt replace_copy(R &&Range, OutputIt Out, const T &OldValue, |
1841 | const T &NewValue) { |
1842 | return std::replace_copy(adl_begin(Range), adl_end(Range), Out, OldValue, |
1843 | NewValue); |
1844 | } |
1845 | |
1846 | /// Provide wrappers to std::move which take ranges instead of having to |
1847 | /// pass begin/end explicitly. |
1848 | template <typename R, typename OutputIt> |
1849 | OutputIt move(R &&Range, OutputIt Out) { |
1850 | return std::move(adl_begin(Range), adl_end(Range), Out); |
1851 | } |
1852 | |
1853 | namespace detail { |
1854 | template <typename Range, typename Element> |
1855 | using check_has_member_contains_t = |
1856 | decltype(std::declval<Range &>().contains(std::declval<const Element &>())); |
1857 | |
1858 | template <typename Range, typename Element> |
1859 | static constexpr bool HasMemberContains = |
1860 | is_detected<check_has_member_contains_t, Range, Element>::value; |
1861 | |
1862 | template <typename Range, typename Element> |
1863 | using check_has_member_find_t = |
1864 | decltype(std::declval<Range &>().find(std::declval<const Element &>()) != |
1865 | std::declval<Range &>().end()); |
1866 | |
1867 | template <typename Range, typename Element> |
1868 | static constexpr bool HasMemberFind = |
1869 | is_detected<check_has_member_find_t, Range, Element>::value; |
1870 | |
1871 | } // namespace detail |
1872 | |
1873 | /// Returns true if \p Element is found in \p Range. Delegates the check to |
1874 | /// either `.contains(Element)`, `.find(Element)`, or `std::find`, in this |
1875 | /// order of preference. This is intended as the canonical way to check if an |
1876 | /// element exists in a range in generic code or range type that does not |
1877 | /// expose a `.contains(Element)` member. |
1878 | template <typename R, typename E> |
1879 | bool is_contained(R &&Range, const E &Element) { |
1880 | if constexpr (detail::HasMemberContains<R, E>) |
1881 | return Range.contains(Element); |
1882 | else if constexpr (detail::HasMemberFind<R, E>) |
1883 | return Range.find(Element) != Range.end(); |
1884 | else |
1885 | return std::find(adl_begin(Range), adl_end(Range), Element) != |
1886 | adl_end(Range); |
1887 | } |
1888 | |
1889 | /// Returns true iff \p Element exists in \p Set. This overload takes \p Set as |
1890 | /// an initializer list and is `constexpr`-friendly. |
1891 | template <typename T, typename E> |
1892 | constexpr bool is_contained(std::initializer_list<T> Set, const E &Element) { |
1893 | // TODO: Use std::find when we switch to C++20. |
1894 | for (const T &V : Set) |
1895 | if (V == Element) |
1896 | return true; |
1897 | return false; |
1898 | } |
1899 | |
1900 | /// Wrapper function around std::is_sorted to check if elements in a range \p R |
1901 | /// are sorted with respect to a comparator \p C. |
1902 | template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) { |
1903 | return std::is_sorted(adl_begin(Range), adl_end(Range), C); |
1904 | } |
1905 | |
1906 | /// Wrapper function around std::is_sorted to check if elements in a range \p R |
1907 | /// are sorted in non-descending order. |
1908 | template <typename R> bool is_sorted(R &&Range) { |
1909 | return std::is_sorted(adl_begin(Range), adl_end(Range)); |
1910 | } |
1911 | |
1912 | /// Wrapper function around std::count to count the number of times an element |
1913 | /// \p Element occurs in the given range \p Range. |
1914 | template <typename R, typename E> auto count(R &&Range, const E &Element) { |
1915 | return std::count(adl_begin(Range), adl_end(Range), Element); |
1916 | } |
1917 | |
1918 | /// Wrapper function around std::count_if to count the number of times an |
1919 | /// element satisfying a given predicate occurs in a range. |
1920 | template <typename R, typename UnaryPredicate> |
1921 | auto count_if(R &&Range, UnaryPredicate P) { |
1922 | return std::count_if(adl_begin(Range), adl_end(Range), P); |
1923 | } |
1924 | |
1925 | /// Wrapper function around std::transform to apply a function to a range and |
1926 | /// store the result elsewhere. |
1927 | template <typename R, typename OutputIt, typename UnaryFunction> |
1928 | OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) { |
1929 | return std::transform(adl_begin(Range), adl_end(Range), d_first, F); |
1930 | } |
1931 | |
1932 | /// Provide wrappers to std::partition which take ranges instead of having to |
1933 | /// pass begin/end explicitly. |
1934 | template <typename R, typename UnaryPredicate> |
1935 | auto partition(R &&Range, UnaryPredicate P) { |
1936 | return std::partition(adl_begin(Range), adl_end(Range), P); |
1937 | } |
1938 | |
1939 | /// Provide wrappers to std::binary_search which take ranges instead of having |
1940 | /// to pass begin/end explicitly. |
1941 | template <typename R, typename T> auto binary_search(R &&Range, T &&Value) { |
1942 | return std::binary_search(adl_begin(Range), adl_end(Range), |
1943 | std::forward<T>(Value)); |
1944 | } |
1945 | |
1946 | template <typename R, typename T, typename Compare> |
1947 | auto binary_search(R &&Range, T &&Value, Compare C) { |
1948 | return std::binary_search(adl_begin(Range), adl_end(Range), |
1949 | std::forward<T>(Value), C); |
1950 | } |
1951 | |
1952 | /// Provide wrappers to std::lower_bound which take ranges instead of having to |
1953 | /// pass begin/end explicitly. |
1954 | template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) { |
1955 | return std::lower_bound(adl_begin(Range), adl_end(Range), |
1956 | std::forward<T>(Value)); |
1957 | } |
1958 | |
1959 | template <typename R, typename T, typename Compare> |
1960 | auto lower_bound(R &&Range, T &&Value, Compare C) { |
1961 | return std::lower_bound(adl_begin(Range), adl_end(Range), |
1962 | std::forward<T>(Value), C); |
1963 | } |
1964 | |
1965 | /// Provide wrappers to std::upper_bound which take ranges instead of having to |
1966 | /// pass begin/end explicitly. |
1967 | template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) { |
1968 | return std::upper_bound(adl_begin(Range), adl_end(Range), |
1969 | std::forward<T>(Value)); |
1970 | } |
1971 | |
1972 | template <typename R, typename T, typename Compare> |
1973 | auto upper_bound(R &&Range, T &&Value, Compare C) { |
1974 | return std::upper_bound(adl_begin(Range), adl_end(Range), |
1975 | std::forward<T>(Value), C); |
1976 | } |
1977 | |
1978 | template <typename R> auto min_element(R &&Range) { |
1979 | return std::min_element(adl_begin(Range), adl_end(Range)); |
1980 | } |
1981 | |
1982 | template <typename R, typename Compare> auto min_element(R &&Range, Compare C) { |
1983 | return std::min_element(adl_begin(Range), adl_end(Range), C); |
1984 | } |
1985 | |
1986 | template <typename R> auto max_element(R &&Range) { |
1987 | return std::max_element(adl_begin(Range), adl_end(Range)); |
1988 | } |
1989 | |
1990 | template <typename R, typename Compare> auto max_element(R &&Range, Compare C) { |
1991 | return std::max_element(adl_begin(Range), adl_end(Range), C); |
1992 | } |
1993 | |
1994 | template <typename R> |
1995 | void stable_sort(R &&Range) { |
1996 | std::stable_sort(adl_begin(Range), adl_end(Range)); |
1997 | } |
1998 | |
1999 | template <typename R, typename Compare> |
2000 | void stable_sort(R &&Range, Compare C) { |
2001 | std::stable_sort(adl_begin(Range), adl_end(Range), C); |
2002 | } |
2003 | |
2004 | /// Binary search for the first iterator in a range where a predicate is false. |
2005 | /// Requires that C is always true below some limit, and always false above it. |
2006 | template <typename R, typename Predicate, |
2007 | typename Val = decltype(*adl_begin(std::declval<R>()))> |
2008 | auto partition_point(R &&Range, Predicate P) { |
2009 | return std::partition_point(adl_begin(Range), adl_end(Range), P); |
2010 | } |
2011 | |
2012 | template<typename Range, typename Predicate> |
2013 | auto unique(Range &&R, Predicate P) { |
2014 | return std::unique(adl_begin(R), adl_end(R), P); |
2015 | } |
2016 | |
2017 | /// Wrapper function around std::unique to allow calling unique on a |
2018 | /// container without having to specify the begin/end iterators. |
2019 | template <typename Range> auto unique(Range &&R) { |
2020 | return std::unique(adl_begin(R), adl_end(R)); |
2021 | } |
2022 | |
2023 | /// Wrapper function around std::equal to detect if pair-wise elements between |
2024 | /// two ranges are the same. |
2025 | template <typename L, typename R> bool equal(L &&LRange, R &&RRange) { |
2026 | return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange), |
2027 | adl_end(RRange)); |
2028 | } |
2029 | |
2030 | /// Returns true if all elements in Range are equal or when the Range is empty. |
2031 | template <typename R> bool all_equal(R &&Range) { |
2032 | auto Begin = adl_begin(Range); |
2033 | auto End = adl_end(Range); |
2034 | return Begin == End || std::equal(Begin + 1, End, Begin); |
2035 | } |
2036 | |
2037 | /// Returns true if all Values in the initializer lists are equal or the list |
2038 | // is empty. |
2039 | template <typename T> bool all_equal(std::initializer_list<T> Values) { |
2040 | return all_equal<std::initializer_list<T>>(std::move(Values)); |
2041 | } |
2042 | |
2043 | /// Provide a container algorithm similar to C++ Library Fundamentals v2's |
2044 | /// `erase_if` which is equivalent to: |
2045 | /// |
2046 | /// C.erase(remove_if(C, pred), C.end()); |
2047 | /// |
2048 | /// This version works for any container with an erase method call accepting |
2049 | /// two iterators. |
2050 | template <typename Container, typename UnaryPredicate> |
2051 | void erase_if(Container &C, UnaryPredicate P) { |
2052 | C.erase(remove_if(C, P), C.end()); |
2053 | } |
2054 | |
2055 | /// Wrapper function to remove a value from a container: |
2056 | /// |
2057 | /// C.erase(remove(C.begin(), C.end(), V), C.end()); |
2058 | template <typename Container, typename ValueType> |
2059 | void erase(Container &C, ValueType V) { |
2060 | C.erase(std::remove(C.begin(), C.end(), V), C.end()); |
2061 | } |
2062 | |
2063 | template <typename Container, typename ValueType> |
2064 | LLVM_DEPRECATED("Use erase instead" , "erase" ) |
2065 | void erase_value(Container &C, ValueType V) { |
2066 | erase(C, V); |
2067 | } |
2068 | |
2069 | /// Wrapper function to append range `R` to container `C`. |
2070 | /// |
2071 | /// C.insert(C.end(), R.begin(), R.end()); |
2072 | template <typename Container, typename Range> |
2073 | void append_range(Container &C, Range &&R) { |
2074 | C.insert(C.end(), adl_begin(R), adl_end(R)); |
2075 | } |
2076 | |
2077 | /// Appends all `Values` to container `C`. |
2078 | template <typename Container, typename... Args> |
2079 | void append_values(Container &C, Args &&...Values) { |
2080 | C.reserve(range_size(C) + sizeof...(Args)); |
2081 | // Append all values one by one. |
2082 | ((void)C.insert(C.end(), std::forward<Args>(Values)), ...); |
2083 | } |
2084 | |
2085 | /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with |
2086 | /// the range [ValIt, ValEnd) (which is not from the same container). |
2087 | template<typename Container, typename RandomAccessIterator> |
2088 | void replace(Container &Cont, typename Container::iterator ContIt, |
2089 | typename Container::iterator ContEnd, RandomAccessIterator ValIt, |
2090 | RandomAccessIterator ValEnd) { |
2091 | while (true) { |
2092 | if (ValIt == ValEnd) { |
2093 | Cont.erase(ContIt, ContEnd); |
2094 | return; |
2095 | } else if (ContIt == ContEnd) { |
2096 | Cont.insert(ContIt, ValIt, ValEnd); |
2097 | return; |
2098 | } |
2099 | *ContIt++ = *ValIt++; |
2100 | } |
2101 | } |
2102 | |
2103 | /// Given a sequence container Cont, replace the range [ContIt, ContEnd) with |
2104 | /// the range R. |
2105 | template<typename Container, typename Range = std::initializer_list< |
2106 | typename Container::value_type>> |
2107 | void replace(Container &Cont, typename Container::iterator ContIt, |
2108 | typename Container::iterator ContEnd, Range R) { |
2109 | replace(Cont, ContIt, ContEnd, R.begin(), R.end()); |
2110 | } |
2111 | |
2112 | /// An STL-style algorithm similar to std::for_each that applies a second |
2113 | /// functor between every pair of elements. |
2114 | /// |
2115 | /// This provides the control flow logic to, for example, print a |
2116 | /// comma-separated list: |
2117 | /// \code |
2118 | /// interleave(names.begin(), names.end(), |
2119 | /// [&](StringRef name) { os << name; }, |
2120 | /// [&] { os << ", "; }); |
2121 | /// \endcode |
2122 | template <typename ForwardIterator, typename UnaryFunctor, |
2123 | typename NullaryFunctor, |
2124 | typename = std::enable_if_t< |
2125 | !std::is_constructible<StringRef, UnaryFunctor>::value && |
2126 | !std::is_constructible<StringRef, NullaryFunctor>::value>> |
2127 | inline void interleave(ForwardIterator begin, ForwardIterator end, |
2128 | UnaryFunctor each_fn, NullaryFunctor between_fn) { |
2129 | if (begin == end) |
2130 | return; |
2131 | each_fn(*begin); |
2132 | ++begin; |
2133 | for (; begin != end; ++begin) { |
2134 | between_fn(); |
2135 | each_fn(*begin); |
2136 | } |
2137 | } |
2138 | |
2139 | template <typename Container, typename UnaryFunctor, typename NullaryFunctor, |
2140 | typename = std::enable_if_t< |
2141 | !std::is_constructible<StringRef, UnaryFunctor>::value && |
2142 | !std::is_constructible<StringRef, NullaryFunctor>::value>> |
2143 | inline void interleave(const Container &c, UnaryFunctor each_fn, |
2144 | NullaryFunctor between_fn) { |
2145 | interleave(adl_begin(c), adl_end(c), each_fn, between_fn); |
2146 | } |
2147 | |
2148 | /// Overload of interleave for the common case of string separator. |
2149 | template <typename Container, typename UnaryFunctor, typename StreamT, |
2150 | typename T = detail::ValueOfRange<Container>> |
2151 | inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn, |
2152 | const StringRef &separator) { |
2153 | interleave(adl_begin(c), adl_end(c), each_fn, [&] { os << separator; }); |
2154 | } |
2155 | template <typename Container, typename StreamT, |
2156 | typename T = detail::ValueOfRange<Container>> |
2157 | inline void interleave(const Container &c, StreamT &os, |
2158 | const StringRef &separator) { |
2159 | interleave( |
2160 | c, os, [&](const T &a) { os << a; }, separator); |
2161 | } |
2162 | |
2163 | template <typename Container, typename UnaryFunctor, typename StreamT, |
2164 | typename T = detail::ValueOfRange<Container>> |
2165 | inline void interleaveComma(const Container &c, StreamT &os, |
2166 | UnaryFunctor each_fn) { |
2167 | interleave(c, os, each_fn, ", " ); |
2168 | } |
2169 | template <typename Container, typename StreamT, |
2170 | typename T = detail::ValueOfRange<Container>> |
2171 | inline void interleaveComma(const Container &c, StreamT &os) { |
2172 | interleaveComma(c, os, [&](const T &a) { os << a; }); |
2173 | } |
2174 | |
2175 | //===----------------------------------------------------------------------===// |
2176 | // Extra additions to <memory> |
2177 | //===----------------------------------------------------------------------===// |
2178 | |
2179 | struct FreeDeleter { |
2180 | void operator()(void* v) { |
2181 | ::free(ptr: v); |
2182 | } |
2183 | }; |
2184 | |
2185 | template<typename First, typename Second> |
2186 | struct pair_hash { |
2187 | size_t operator()(const std::pair<First, Second> &P) const { |
2188 | return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); |
2189 | } |
2190 | }; |
2191 | |
2192 | /// Binary functor that adapts to any other binary functor after dereferencing |
2193 | /// operands. |
2194 | template <typename T> struct deref { |
2195 | T func; |
2196 | |
2197 | // Could be further improved to cope with non-derivable functors and |
2198 | // non-binary functors (should be a variadic template member function |
2199 | // operator()). |
2200 | template <typename A, typename B> auto operator()(A &lhs, B &rhs) const { |
2201 | assert(lhs); |
2202 | assert(rhs); |
2203 | return func(*lhs, *rhs); |
2204 | } |
2205 | }; |
2206 | |
2207 | namespace detail { |
2208 | |
2209 | /// Tuple-like type for `zip_enumerator` dereference. |
2210 | template <typename... Refs> struct enumerator_result; |
2211 | |
2212 | template <typename... Iters> |
2213 | using EnumeratorTupleType = enumerator_result<decltype(*declval<Iters>())...>; |
2214 | |
2215 | /// Zippy iterator that uses the second iterator for comparisons. For the |
2216 | /// increment to be safe, the second range has to be the shortest. |
2217 | /// Returns `enumerator_result` on dereference to provide `.index()` and |
2218 | /// `.value()` member functions. |
2219 | /// Note: Because the dereference operator returns `enumerator_result` as a |
2220 | /// value instead of a reference and does not strictly conform to the C++17's |
2221 | /// definition of forward iterator. However, it satisfies all the |
2222 | /// forward_iterator requirements that the `zip_common` and `zippy` depend on |
2223 | /// and fully conforms to the C++20 definition of forward iterator. |
2224 | /// This is similar to `std::vector<bool>::iterator` that returns bit reference |
2225 | /// wrappers on dereference. |
2226 | template <typename... Iters> |
2227 | struct zip_enumerator : zip_common<zip_enumerator<Iters...>, |
2228 | EnumeratorTupleType<Iters...>, Iters...> { |
2229 | static_assert(sizeof...(Iters) >= 2, "Expected at least two iteratees" ); |
2230 | using zip_common<zip_enumerator<Iters...>, EnumeratorTupleType<Iters...>, |
2231 | Iters...>::zip_common; |
2232 | |
2233 | bool operator==(const zip_enumerator &Other) const { |
2234 | return std::get<1>(this->iterators) == std::get<1>(Other.iterators); |
2235 | } |
2236 | }; |
2237 | |
2238 | template <typename... Refs> struct enumerator_result<std::size_t, Refs...> { |
2239 | static constexpr std::size_t NumRefs = sizeof...(Refs); |
2240 | static_assert(NumRefs != 0); |
2241 | // `NumValues` includes the index. |
2242 | static constexpr std::size_t NumValues = NumRefs + 1; |
2243 | |
2244 | // Tuple type whose element types are references for each `Ref`. |
2245 | using range_reference_tuple = std::tuple<Refs...>; |
2246 | // Tuple type who elements are references to all values, including both |
2247 | // the index and `Refs` reference types. |
2248 | using value_reference_tuple = std::tuple<std::size_t, Refs...>; |
2249 | |
2250 | enumerator_result(std::size_t Index, Refs &&...Rs) |
2251 | : Idx(Index), Storage(std::forward<Refs>(Rs)...) {} |
2252 | |
2253 | /// Returns the 0-based index of the current position within the original |
2254 | /// input range(s). |
2255 | std::size_t index() const { return Idx; } |
2256 | |
2257 | /// Returns the value(s) for the current iterator. This does not include the |
2258 | /// index. |
2259 | decltype(auto) value() const { |
2260 | if constexpr (NumRefs == 1) |
2261 | return std::get<0>(Storage); |
2262 | else |
2263 | return Storage; |
2264 | } |
2265 | |
2266 | /// Returns the value at index `I`. This case covers the index. |
2267 | template <std::size_t I, typename = std::enable_if_t<I == 0>> |
2268 | friend std::size_t get(const enumerator_result &Result) { |
2269 | return Result.Idx; |
2270 | } |
2271 | |
2272 | /// Returns the value at index `I`. This case covers references to the |
2273 | /// iteratees. |
2274 | template <std::size_t I, typename = std::enable_if_t<I != 0>> |
2275 | friend decltype(auto) get(const enumerator_result &Result) { |
2276 | // Note: This is a separate function from the other `get`, instead of an |
2277 | // `if constexpr` case, to work around an MSVC 19.31.31XXX compiler |
2278 | // (Visual Studio 2022 17.1) return type deduction bug. |
2279 | return std::get<I - 1>(Result.Storage); |
2280 | } |
2281 | |
2282 | template <typename... Ts> |
2283 | friend bool operator==(const enumerator_result &Result, |
2284 | const std::tuple<std::size_t, Ts...> &Other) { |
2285 | static_assert(NumRefs == sizeof...(Ts), "Size mismatch" ); |
2286 | if (Result.Idx != std::get<0>(Other)) |
2287 | return false; |
2288 | return Result.is_value_equal(Other, std::make_index_sequence<NumRefs>{}); |
2289 | } |
2290 | |
2291 | private: |
2292 | template <typename Tuple, std::size_t... Idx> |
2293 | bool is_value_equal(const Tuple &Other, std::index_sequence<Idx...>) const { |
2294 | return ((std::get<Idx>(Storage) == std::get<Idx + 1>(Other)) && ...); |
2295 | } |
2296 | |
2297 | std::size_t Idx; |
2298 | // Make this tuple mutable to avoid casts that obfuscate const-correctness |
2299 | // issues. Const-correctness of references is taken care of by `zippy` that |
2300 | // defines const-non and const iterator types that will propagate down to |
2301 | // `enumerator_result`'s `Refs`. |
2302 | // Note that unlike the results of `zip*` functions, `enumerate`'s result are |
2303 | // supposed to be modifiable even when defined as |
2304 | // `const`. |
2305 | mutable range_reference_tuple Storage; |
2306 | }; |
2307 | |
2308 | struct index_iterator |
2309 | : llvm::iterator_facade_base<index_iterator, |
2310 | std::random_access_iterator_tag, std::size_t> { |
2311 | index_iterator(std::size_t Index) : Index(Index) {} |
2312 | |
2313 | index_iterator &operator+=(std::ptrdiff_t N) { |
2314 | Index += N; |
2315 | return *this; |
2316 | } |
2317 | |
2318 | index_iterator &operator-=(std::ptrdiff_t N) { |
2319 | Index -= N; |
2320 | return *this; |
2321 | } |
2322 | |
2323 | std::ptrdiff_t operator-(const index_iterator &R) const { |
2324 | return Index - R.Index; |
2325 | } |
2326 | |
2327 | // Note: This dereference operator returns a value instead of a reference |
2328 | // and does not strictly conform to the C++17's definition of forward |
2329 | // iterator. However, it satisfies all the forward_iterator requirements |
2330 | // that the `zip_common` depends on and fully conforms to the C++20 |
2331 | // definition of forward iterator. |
2332 | std::size_t operator*() const { return Index; } |
2333 | |
2334 | friend bool operator==(const index_iterator &Lhs, const index_iterator &Rhs) { |
2335 | return Lhs.Index == Rhs.Index; |
2336 | } |
2337 | |
2338 | friend bool operator<(const index_iterator &Lhs, const index_iterator &Rhs) { |
2339 | return Lhs.Index < Rhs.Index; |
2340 | } |
2341 | |
2342 | private: |
2343 | std::size_t Index; |
2344 | }; |
2345 | |
2346 | /// Infinite stream of increasing 0-based `size_t` indices. |
2347 | struct index_stream { |
2348 | index_iterator begin() const { return {0}; } |
2349 | index_iterator end() const { |
2350 | // We approximate 'infinity' with the max size_t value, which should be good |
2351 | // enough to index over any container. |
2352 | return index_iterator{std::numeric_limits<std::size_t>::max()}; |
2353 | } |
2354 | }; |
2355 | |
2356 | } // end namespace detail |
2357 | |
2358 | /// Increasing range of `size_t` indices. |
2359 | class index_range { |
2360 | std::size_t Begin; |
2361 | std::size_t End; |
2362 | |
2363 | public: |
2364 | index_range(std::size_t Begin, std::size_t End) : Begin(Begin), End(End) {} |
2365 | detail::index_iterator begin() const { return {Begin}; } |
2366 | detail::index_iterator end() const { return {End}; } |
2367 | }; |
2368 | |
2369 | /// Given two or more input ranges, returns a new range whose values are are |
2370 | /// tuples (A, B, C, ...), such that A is the 0-based index of the item in the |
2371 | /// sequence, and B, C, ..., are the values from the original input ranges. All |
2372 | /// input ranges are required to have equal lengths. Note that the returned |
2373 | /// iterator allows for the values (B, C, ...) to be modified. Example: |
2374 | /// |
2375 | /// ```c++ |
2376 | /// std::vector<char> Letters = {'A', 'B', 'C', 'D'}; |
2377 | /// std::vector<int> Vals = {10, 11, 12, 13}; |
2378 | /// |
2379 | /// for (auto [Index, Letter, Value] : enumerate(Letters, Vals)) { |
2380 | /// printf("Item %zu - %c: %d\n", Index, Letter, Value); |
2381 | /// Value -= 10; |
2382 | /// } |
2383 | /// ``` |
2384 | /// |
2385 | /// Output: |
2386 | /// Item 0 - A: 10 |
2387 | /// Item 1 - B: 11 |
2388 | /// Item 2 - C: 12 |
2389 | /// Item 3 - D: 13 |
2390 | /// |
2391 | /// or using an iterator: |
2392 | /// ```c++ |
2393 | /// for (auto it : enumerate(Vals)) { |
2394 | /// it.value() += 10; |
2395 | /// printf("Item %zu: %d\n", it.index(), it.value()); |
2396 | /// } |
2397 | /// ``` |
2398 | /// |
2399 | /// Output: |
2400 | /// Item 0: 20 |
2401 | /// Item 1: 21 |
2402 | /// Item 2: 22 |
2403 | /// Item 3: 23 |
2404 | /// |
2405 | template <typename FirstRange, typename... RestRanges> |
2406 | auto enumerate(FirstRange &&First, RestRanges &&...Rest) { |
2407 | if constexpr (sizeof...(Rest) != 0) { |
2408 | #ifndef NDEBUG |
2409 | // Note: Create an array instead of an initializer list to work around an |
2410 | // Apple clang 14 compiler bug. |
2411 | size_t sizes[] = {range_size(First), range_size(Rest)...}; |
2412 | assert(all_equal(sizes) && "Ranges have different length" ); |
2413 | #endif |
2414 | } |
2415 | using enumerator = detail::zippy<detail::zip_enumerator, detail::index_stream, |
2416 | FirstRange, RestRanges...>; |
2417 | return enumerator(detail::index_stream{}, std::forward<FirstRange>(First), |
2418 | std::forward<RestRanges>(Rest)...); |
2419 | } |
2420 | |
2421 | namespace detail { |
2422 | |
2423 | template <typename Predicate, typename... Args> |
2424 | bool all_of_zip_predicate_first(Predicate &&P, Args &&...args) { |
2425 | auto z = zip(args...); |
2426 | auto it = z.begin(); |
2427 | auto end = z.end(); |
2428 | while (it != end) { |
2429 | if (!std::apply([&](auto &&...args) { return P(args...); }, *it)) |
2430 | return false; |
2431 | ++it; |
2432 | } |
2433 | return it.all_equals(end); |
2434 | } |
2435 | |
2436 | // Just an adaptor to switch the order of argument and have the predicate before |
2437 | // the zipped inputs. |
2438 | template <typename... ArgsThenPredicate, size_t... InputIndexes> |
2439 | bool all_of_zip_predicate_last( |
2440 | std::tuple<ArgsThenPredicate...> argsThenPredicate, |
2441 | std::index_sequence<InputIndexes...>) { |
2442 | auto constexpr OutputIndex = |
2443 | std::tuple_size<decltype(argsThenPredicate)>::value - 1; |
2444 | return all_of_zip_predicate_first(std::get<OutputIndex>(argsThenPredicate), |
2445 | std::get<InputIndexes>(argsThenPredicate)...); |
2446 | } |
2447 | |
2448 | } // end namespace detail |
2449 | |
2450 | /// Compare two zipped ranges using the provided predicate (as last argument). |
2451 | /// Return true if all elements satisfy the predicate and false otherwise. |
2452 | // Return false if the zipped iterator aren't all at end (size mismatch). |
2453 | template <typename... ArgsAndPredicate> |
2454 | bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate) { |
2455 | return detail::all_of_zip_predicate_last( |
2456 | std::forward_as_tuple(argsAndPredicate...), |
2457 | std::make_index_sequence<sizeof...(argsAndPredicate) - 1>{}); |
2458 | } |
2459 | |
2460 | /// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N) |
2461 | /// time. Not meant for use with random-access iterators. |
2462 | /// Can optionally take a predicate to filter lazily some items. |
2463 | template <typename IterTy, |
2464 | typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)> |
2465 | bool hasNItems( |
2466 | IterTy &&Begin, IterTy &&End, unsigned N, |
2467 | Pred &&ShouldBeCounted = |
2468 | [](const decltype(*std::declval<IterTy>()) &) { return true; }, |
2469 | std::enable_if_t< |
2470 | !std::is_base_of<std::random_access_iterator_tag, |
2471 | typename std::iterator_traits<std::remove_reference_t< |
2472 | decltype(Begin)>>::iterator_category>::value, |
2473 | void> * = nullptr) { |
2474 | for (; N; ++Begin) { |
2475 | if (Begin == End) |
2476 | return false; // Too few. |
2477 | N -= ShouldBeCounted(*Begin); |
2478 | } |
2479 | for (; Begin != End; ++Begin) |
2480 | if (ShouldBeCounted(*Begin)) |
2481 | return false; // Too many. |
2482 | return true; |
2483 | } |
2484 | |
2485 | /// Return true if the sequence [Begin, End) has N or more items. Runs in O(N) |
2486 | /// time. Not meant for use with random-access iterators. |
2487 | /// Can optionally take a predicate to lazily filter some items. |
2488 | template <typename IterTy, |
2489 | typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)> |
2490 | bool hasNItemsOrMore( |
2491 | IterTy &&Begin, IterTy &&End, unsigned N, |
2492 | Pred &&ShouldBeCounted = |
2493 | [](const decltype(*std::declval<IterTy>()) &) { return true; }, |
2494 | std::enable_if_t< |
2495 | !std::is_base_of<std::random_access_iterator_tag, |
2496 | typename std::iterator_traits<std::remove_reference_t< |
2497 | decltype(Begin)>>::iterator_category>::value, |
2498 | void> * = nullptr) { |
2499 | for (; N; ++Begin) { |
2500 | if (Begin == End) |
2501 | return false; // Too few. |
2502 | N -= ShouldBeCounted(*Begin); |
2503 | } |
2504 | return true; |
2505 | } |
2506 | |
2507 | /// Returns true if the sequence [Begin, End) has N or less items. Can |
2508 | /// optionally take a predicate to lazily filter some items. |
2509 | template <typename IterTy, |
2510 | typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)> |
2511 | bool hasNItemsOrLess( |
2512 | IterTy &&Begin, IterTy &&End, unsigned N, |
2513 | Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) { |
2514 | return true; |
2515 | }) { |
2516 | assert(N != std::numeric_limits<unsigned>::max()); |
2517 | return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted); |
2518 | } |
2519 | |
2520 | /// Returns true if the given container has exactly N items |
2521 | template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) { |
2522 | return hasNItems(std::begin(C), std::end(C), N); |
2523 | } |
2524 | |
2525 | /// Returns true if the given container has N or more items |
2526 | template <typename ContainerTy> |
2527 | bool hasNItemsOrMore(ContainerTy &&C, unsigned N) { |
2528 | return hasNItemsOrMore(std::begin(C), std::end(C), N); |
2529 | } |
2530 | |
2531 | /// Returns true if the given container has N or less items |
2532 | template <typename ContainerTy> |
2533 | bool hasNItemsOrLess(ContainerTy &&C, unsigned N) { |
2534 | return hasNItemsOrLess(std::begin(C), std::end(C), N); |
2535 | } |
2536 | |
2537 | /// Returns a raw pointer that represents the same address as the argument. |
2538 | /// |
2539 | /// This implementation can be removed once we move to C++20 where it's defined |
2540 | /// as std::to_address(). |
2541 | /// |
2542 | /// The std::pointer_traits<>::to_address(p) variations of these overloads has |
2543 | /// not been implemented. |
2544 | template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); } |
2545 | template <class T> constexpr T *to_address(T *P) { return P; } |
2546 | |
2547 | // Detect incomplete types, relying on the fact that their size is unknown. |
2548 | namespace detail { |
2549 | template <typename T> using has_sizeof = decltype(sizeof(T)); |
2550 | } // namespace detail |
2551 | |
2552 | /// Detects when type `T` is incomplete. This is true for forward declarations |
2553 | /// and false for types with a full definition. |
2554 | template <typename T> |
2555 | constexpr bool is_incomplete_v = !is_detected<detail::has_sizeof, T>::value; |
2556 | |
2557 | } // end namespace llvm |
2558 | |
2559 | namespace std { |
2560 | template <typename... Refs> |
2561 | struct tuple_size<llvm::detail::enumerator_result<Refs...>> |
2562 | : std::integral_constant<std::size_t, sizeof...(Refs)> {}; |
2563 | |
2564 | template <std::size_t I, typename... Refs> |
2565 | struct tuple_element<I, llvm::detail::enumerator_result<Refs...>> |
2566 | : std::tuple_element<I, std::tuple<Refs...>> {}; |
2567 | |
2568 | template <std::size_t I, typename... Refs> |
2569 | struct tuple_element<I, const llvm::detail::enumerator_result<Refs...>> |
2570 | : std::tuple_element<I, std::tuple<Refs...>> {}; |
2571 | |
2572 | } // namespace std |
2573 | |
2574 | #endif // LLVM_ADT_STLEXTRAS_H |
2575 | |