Branch data Line data Source code
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 LLVM_ADT_STLEXTRAS_H
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 : 0 : 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 : 0 : mapped_iterator(ItTy U, FuncTy F)
357 : 0 : : 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 : 0 : inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
373 : 0 : return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
374 : : }
375 : :
376 : : template <class ContainerTy, class FuncTy>
377 : 0 : auto map_range(ContainerTy &&C, FuncTy F) {
378 : 0 : return make_range(map_iterator(std::begin(C), F),
379 : 0 : 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 : 0 : void findNextValid() {
458 [ # # # # : 0 : while (this->I != End && !Pred(*this->I))
# # ]
459 : 0 : BaseT::operator++();
460 : 0 : }
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 : 0 : filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
468 : : PredicateT Pred)
469 : 0 : : BaseT(Begin), End(End), Pred(Pred) {
470 : 0 : findNextValid();
471 : 0 : }
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 : 0 : filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
525 : : PredicateT Pred)
526 : 0 : : 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 : 0 : make_filter_range(RangeT &&Range, PredicateT Pred) {
573 : : using FilterIteratorT =
574 : : filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
575 [ # # ]: 0 : return make_range(
576 [ # # ]: 0 : FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
577 : : std::end(std::forward<RangeT>(Range)), Pred),
578 [ # # ]: 0 : FilterIteratorT(std::end(std::forward<RangeT>(Range)),
579 : 0 : 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(begin.getBase(), 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, 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(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(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 : : template <typename L, typename R, typename BinaryPredicate>
2031 : : bool equal(L &&LRange, R &&RRange, BinaryPredicate P) {
2032 : : return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
2033 : : adl_end(RRange), P);
2034 : : }
2035 : :
2036 : : /// Returns true if all elements in Range are equal or when the Range is empty.
2037 : : template <typename R> bool all_equal(R &&Range) {
2038 : : auto Begin = adl_begin(Range);
2039 : : auto End = adl_end(Range);
2040 : : return Begin == End || std::equal(Begin + 1, End, Begin);
2041 : : }
2042 : :
2043 : : /// Returns true if all Values in the initializer lists are equal or the list
2044 : : // is empty.
2045 : : template <typename T> bool all_equal(std::initializer_list<T> Values) {
2046 : : return all_equal<std::initializer_list<T>>(std::move(Values));
2047 : : }
2048 : :
2049 : : /// Provide a container algorithm similar to C++ Library Fundamentals v2's
2050 : : /// `erase_if` which is equivalent to:
2051 : : ///
2052 : : /// C.erase(remove_if(C, pred), C.end());
2053 : : ///
2054 : : /// This version works for any container with an erase method call accepting
2055 : : /// two iterators.
2056 : : template <typename Container, typename UnaryPredicate>
2057 : : void erase_if(Container &C, UnaryPredicate P) {
2058 : : C.erase(remove_if(C, P), C.end());
2059 : : }
2060 : :
2061 : : /// Wrapper function to remove a value from a container:
2062 : : ///
2063 : : /// C.erase(remove(C.begin(), C.end(), V), C.end());
2064 : : template <typename Container, typename ValueType>
2065 : : void erase(Container &C, ValueType V) {
2066 : : C.erase(std::remove(C.begin(), C.end(), V), C.end());
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(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
|
