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
|
