LLVM 20.0.0git
STLExtras.h
Go to the documentation of this file.
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"
24#include "llvm/ADT/iterator.h"
26#include "llvm/Config/abi-breaking.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
47namespace llvm {
48
49//===----------------------------------------------------------------------===//
50// Extra additions to <type_traits>
51//===----------------------------------------------------------------------===//
52
53template <typename T> struct make_const_ptr {
54 using type = std::add_pointer_t<std::add_const_t<T>>;
55};
56
57template <typename T> struct make_const_ref {
58 using type = std::add_lvalue_reference_t<std::add_const_t<T>>;
59};
60
61namespace detail {
62template <class, template <class...> class Op, class... Args> struct detector {
63 using value_t = std::false_type;
64};
65template <template <class...> class Op, class... Args>
66struct 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;
78template <template <class...> class Op, class... Args>
79using 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
85template <typename T, bool isClass = std::is_class<T>::value>
86struct function_traits : public function_traits<decltype(&T::operator())> {};
87
88/// Overload for class function types.
89template <typename ClassType, typename ReturnType, typename... Args>
90struct 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.
102template <typename ClassType, typename ReturnType, typename... Args>
103struct function_traits<ReturnType (ClassType::*)(Args...), false>
104 : public function_traits<ReturnType (ClassType::*)(Args...) const> {};
105/// Overload for non-class function types.
106template <typename ReturnType, typename... Args>
107struct 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};
118template <typename ReturnType, typename... Args>
119struct function_traits<ReturnType (*const)(Args...), false>
120 : public function_traits<ReturnType (*)(Args...)> {};
121/// Overload for non-class function type references.
122template <typename ReturnType, typename... Args>
123struct 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.
128template <typename T, typename... Ts>
129using 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.
133template <typename T, typename... Ts>
134using are_base_of = std::conjunction<std::is_base_of<T, Ts>...>;
135
136namespace detail {
137template <typename T, typename... Us> struct TypesAreDistinct;
138template <typename T, typename... Us>
140 : std::integral_constant<bool, !is_one_of<T, Us...>::value &&
141 TypesAreDistinct<Us...>::value> {};
142template <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.
152template <typename... Ts> struct TypesAreDistinct;
153template <> struct TypesAreDistinct<> : std::true_type {};
154template <typename... Ts>
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.
168template <typename T, typename... Us> struct FirstIndexOfType;
169template <typename T, typename U, typename... Us>
170struct FirstIndexOfType<T, U, Us...>
171 : std::integral_constant<size_t, 1 + FirstIndexOfType<T, Us...>::value> {};
172template <typename T, typename... Us>
173struct 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.
178template <size_t I, typename... Ts>
179using 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.
183template <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>>>
188constexpr 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
196namespace 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
208template <typename T,
209 bool = std::is_function_v<std::remove_pointer_t<remove_cvref_t<T>>>>
210class 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
220public:
221 Callable() = default;
222 Callable(T const &O) : Obj(std::in_place, O) {}
223
224 Callable(Callable const &Other) = default;
225 Callable(Callable &&Other) = default;
226
228 Obj = std::nullopt;
229 if (Other.Obj)
230 Obj.emplace(*Other.Obj);
231 return *this;
232 }
233
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.
262template <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
268private:
269 StorageT Func = nullptr;
270
271private:
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
282public:
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.
322template <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.
329template <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.
336template <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
344template <typename ItTy, typename FuncTy,
345 typename ReferenceTy =
346 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
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> {
354public:
355 mapped_iterator() = default;
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
365private:
367};
368
369// map_iterator - Provide a convenient way to create mapped_iterators, just like
370// make_pair is useful for creating pairs...
371template <class ItTy, class FuncTy>
373 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
374}
375
376template <class ContainerTy, class FuncTy>
377auto map_range(ContainerTy &&C, FuncTy F) {
378 return make_range(map_iterator(std::begin(C), F),
379 map_iterator(std::end(C), F));
380}
381
382/// A base type of mapped iterator, that is useful for building derived
383/// iterators that do not need/want to store the map function (as in
384/// mapped_iterator). These iterators must simply provide a `mapElement` method
385/// that defines how to map a value of the iterator to the provided reference
386/// type.
387template <typename DerivedT, typename ItTy, typename ReferenceTy>
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> {
395public:
397
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
408namespace detail {
409template <typename Range>
411 decltype(adl_rbegin(std::declval<Range &>()));
412
413template <typename Range>
414static constexpr bool HasFreeFunctionRBegin =
416} // namespace detail
417
418// Returns an iterator_range over the given container which iterates in reverse.
419template <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.
443template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
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
453protected:
456
458 while (this->I != End && !Pred(*this->I))
459 BaseT::operator++();
460 }
461
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.
469 : BaseT(Begin), End(End), Pred(Pred) {
471 }
472
473public:
474 using BaseT::operator++;
475
477 BaseT::operator++();
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.
494template <typename WrappedIteratorT, typename PredicateT,
495 typename IterTag = std::forward_iterator_tag>
497 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
498public:
500
504};
505
506/// Specialization of filter_iterator_base for bidirectional iteration.
507template <typename WrappedIteratorT, typename 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
519public:
520 using BaseT::operator--;
521
523
526 : BaseT(Begin, End, Pred) {}
527
529 BaseT::operator--();
530 findPrevValid();
531 return *this;
532 }
533};
534
535namespace detail {
536
537template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
538 using type = std::forward_iterator_tag;
539};
540
541template <> 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.
548template <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.
558template <typename WrappedIteratorT, typename PredicateT>
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.
570template <typename RangeT, typename PredicateT>
573 using FilterIteratorT =
575 return make_range(
576 FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
577 std::end(std::forward<RangeT>(Range)), Pred),
578 FilterIteratorT(std::end(std::forward<RangeT>(Range)),
579 std::end(std::forward<RangeT>(Range)), Pred));
580}
581
582/// A pseudo-iterator adaptor that is designed to implement "early increment"
583/// style loops.
584///
585/// This is *not a normal iterator* and should almost never be used directly. It
586/// is intended primarily to be used with range based for loops and some range
587/// algorithms.
588///
589/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
590/// somewhere between them. The constraints of these iterators are:
591///
592/// - On construction or after being incremented, it is comparable and
593/// dereferencable. It is *not* incrementable.
594/// - After being dereferenced, it is neither comparable nor dereferencable, it
595/// is only incrementable.
596///
597/// This means you can only dereference the iterator once, and you can only
598/// increment it once between dereferences.
599template <typename WrappedIteratorT>
601 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
602 WrappedIteratorT, std::input_iterator_tag> {
604
605 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
606
607protected:
608#if LLVM_ENABLE_ABI_BREAKING_CHECKS
609 bool IsEarlyIncremented = false;
610#endif
611
612public:
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++;
626#if LLVM_ENABLE_ABI_BREAKING_CHECKS
627 assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
628 IsEarlyIncremented = false;
629#endif
630 return *this;
631 }
632
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.
654template <typename RangeT>
655iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
657 using EarlyIncIteratorT =
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
664template <typename R, typename UnaryPredicate>
665bool all_of(R &&range, UnaryPredicate P);
666
667template <typename R, typename UnaryPredicate>
668bool any_of(R &&range, UnaryPredicate P);
669
670template <typename T> bool all_equal(std::initializer_list<T> Values);
671
672template <typename R> constexpr size_t range_size(R &&Range);
673
674namespace detail {
675
676using 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.
680template<typename... Iters> struct ZipTupleType {
681 using type = std::tuple<decltype(*declval<Iters>())...>;
682};
683
684template <typename ZipType, typename ReferenceTupleType, typename... Iters>
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
700template <typename ZipType, typename ReferenceTupleType, typename... Iters>
701struct 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
708protected:
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
728public:
729 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
730
732
733 ZipType &operator++() {
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.");
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
751template <typename... Iters>
752struct 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
762template <typename... Iters>
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
773private:
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`.
783template <template <typename...> class ItType, typename TupleStorageType,
784 typename IndexSequence>
786
787/// Partial specialization for non-const tuple storage.
788template <template <typename...> class ItType, typename... Args,
789 std::size_t... Ns>
790struct 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.
797template <template <typename...> class ItType, typename... Args,
798 std::size_t... Ns>
799struct 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
805template <template <typename...> class ItType, typename... Args> class zippy {
806private:
807 std::tuple<Args...> storage;
808 using IndexSequence = std::index_sequence_for<Args...>;
809
810public:
811 using iterator = typename ZippyIteratorTuple<ItType, decltype(storage),
812 IndexSequence>::type;
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
830private:
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.
852template <typename T, typename U, typename... Args>
853detail::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.
862template <typename T, typename U, typename... Args>
863detail::zippy<detail::zip_first, T, U, Args...> zip_equal(T &&t, U &&u,
864 Args &&...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.
875template <typename T, typename U, typename... Args>
876detail::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
885namespace detail {
886template <typename Iter>
887Iter next_or_end(const Iter &I, const Iter &End) {
888 if (I == End)
889 return End;
890 return std::next(I);
891}
892
893template <typename Iter>
894auto 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
901template <typename Iter> struct ZipLongestItemType {
902 using type = std::optional<std::remove_const_t<
903 std::remove_reference_t<decltype(*std::declval<Iter>())>>>;
904};
905
906template <typename... Iters> struct ZipLongestTupleType {
907 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>;
908};
909
910template <typename... Iters>
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> {
922public:
923 using value_type = typename ZipLongestTupleType<Iters...>::type;
924
925private:
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
947public:
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
953 return deref(std::index_sequence_for<Iters...>{});
954 }
955
957 iterators = tup_inc(std::index_sequence_for<Iters...>{});
958 return *this;
959 }
960
962 return !test(other, std::index_sequence_for<Iters...>{});
963 }
964};
965
966template <typename... Args> class zip_longest_range {
967public:
968 using iterator =
973 using pointer = typename iterator::pointer;
975
976private:
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
990public:
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.
1003template <typename T, typename U, typename... Args>
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.
1020template <typename ValueT, typename... IterTs>
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
1094public:
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
1106 increment(std::index_sequence_for<IterTs...>());
1107 return *this;
1108 }
1109
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
1119namespace 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.
1126template <typename ValueT, typename... RangeTs> class concat_range {
1127public:
1128 using iterator =
1130 decltype(std::begin(std::declval<RangeTs &>()))...>;
1131
1132private:
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
1152public:
1153 concat_range(RangeTs &&... Ranges)
1154 : Ranges(std::forward<RangeTs>(Ranges)...) {}
1155
1157 return begin_impl(std::index_sequence_for<RangeTs...>{});
1158 }
1159 iterator begin() const {
1160 return begin_impl(std::index_sequence_for<RangeTs...>{});
1161 }
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.
1175template <typename ValueT, typename... RangeTs>
1176detail::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.
1185template <typename DerivedT, typename BaseT, typename T,
1186 typename PointerT = T *, typename ReferenceT = T &>
1188 : public llvm::iterator_facade_base<DerivedT,
1189 std::random_access_iterator_tag, T,
1190 std::ptrdiff_t, PointerT, ReferenceT> {
1191public:
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
1219protected:
1221 : base(base), index(index) {}
1222 BaseT base;
1224};
1225
1226namespace 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.
1237template <typename DerivedT, typename BaseT, typename T,
1238 typename PointerT = T *, typename ReferenceT = T &>
1240public:
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
1262 : base(offset_base(begin.getBase(), begin.getIndex())),
1263 count(end.getIndex() - begin.getIndex()) {}
1265 : indexed_accessor_range_base(range.begin(), range.end()) {}
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<
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
1329private:
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
1335protected:
1340
1341 /// The base that owns the provided range of values.
1342 BaseT base;
1343 /// The size from the owning range.
1345};
1346/// Compare this range with another.
1347/// FIXME: Make me a member function instead of friend when it works in C++20.
1348template <typename OtherT, typename DerivedT, typename BaseT, typename T,
1349 typename PointerT, typename ReferenceT>
1350bool 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
1356template <typename OtherT, typename DerivedT, typename BaseT, typename T,
1357 typename PointerT, typename ReferenceT>
1358bool 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.
1372template <typename DerivedT, typename BaseT, typename T,
1373 typename PointerT = T *, typename ReferenceT = T &>
1376 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
1377public:
1380 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
1381 std::make_pair(base, startIndex), count) {}
1383 DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
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
1407namespace 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.
1414template <typename EltTy, typename FirstTy> class first_or_second_type {
1415public:
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.
1422template <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.
1432template <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.
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.
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.
1467template<typename FuncTy>
1468struct 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.
1479template <int N> struct rank : rank<N - 1> {};
1480template <> struct rank<0> {};
1481
1482namespace detail {
1483template <typename... Ts> struct Visitor;
1484
1485template <typename HeadT, typename... TailTs>
1486struct 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
1494template <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
1529template <typename... CallableTs>
1530constexpr 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.
1540template <class Iterator, class RNG>
1541void 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.
1556template<typename T>
1557inline 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.
1569template<typename T>
1570inline 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
1576namespace detail {
1577
1578inline unsigned presortShuffleEntropy() {
1579 static unsigned Result(std::random_device{}());
1580 return Result;
1581}
1582
1583template <class IteratorTy>
1584inline 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.
1606template<class IteratorTy>
1607inline 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
1618template <class IteratorTy>
1619inline 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
1635namespace detail {
1636template <typename T>
1637// We can use qsort if the iterator type is a pointer and the underlying value
1638// is trivially copyable.
1639using 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).
1646template <typename IteratorTy>
1647inline void sort(IteratorTy Start, IteratorTy End) {
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
1660template <typename Container> inline void sort(Container &&C) {
1662}
1663
1664template <typename IteratorTy, typename Compare>
1665inline 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
1672template <typename Container, typename Compare>
1673inline 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).
1679template <typename R>
1680auto 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
1689namespace detail {
1690template <typename Range>
1692 decltype(adl_size(std::declval<Range &>()));
1693
1694template <typename Range>
1695static constexpr bool HasFreeFunctionSize =
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.
1705template <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.
1714template <typename R, typename UnaryFunction>
1715UnaryFunction 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.
1721template <typename R, typename UnaryPredicate>
1722bool 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.
1728template <typename R, typename UnaryPredicate>
1729bool 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.
1735template <typename R, typename UnaryPredicate>
1736bool 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.
1742template <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.
1748template <typename R, typename UnaryPredicate>
1749auto find_if(R &&Range, UnaryPredicate P) {
1750 return std::find_if(adl_begin(Range), adl_end(Range), P);
1751}
1752
1753template <typename R, typename UnaryPredicate>
1754auto 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.
1760template <typename R, typename UnaryPredicate>
1761auto 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.
1767template <typename R, typename OutputIt, typename UnaryPredicate>
1768OutputIt 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.
1777template <typename T, typename R, typename Predicate>
1778T *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.
1801template <typename T, typename R, typename Predicate>
1802std::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
1823template <typename R, typename OutputIt>
1824OutputIt 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.
1830template <typename R, typename OutputIt, typename UnaryPredicate, typename T>
1831OutputIt 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.
1839template <typename R, typename OutputIt, typename T>
1840OutputIt 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.
1848template <typename R, typename OutputIt>
1849OutputIt move(R &&Range, OutputIt Out) {
1850 return std::move(adl_begin(Range), adl_end(Range), Out);
1851}
1852
1853namespace detail {
1854template <typename Range, typename Element>
1856 decltype(std::declval<Range &>().contains(std::declval<const Element &>()));
1857
1858template <typename Range, typename Element>
1859static constexpr bool HasMemberContains =
1861
1862template <typename Range, typename Element>
1864 decltype(std::declval<Range &>().find(std::declval<const Element &>()) !=
1865 std::declval<Range &>().end());
1866
1867template <typename Range, typename Element>
1868static constexpr bool HasMemberFind =
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.
1878template <typename R, typename E>
1879bool 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.
1891template <typename T, typename E>
1892constexpr 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.
1902template <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.
1908template <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.
1914template <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.
1920template <typename R, typename UnaryPredicate>
1921auto 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.
1927template <typename R, typename OutputIt, typename UnaryFunction>
1928OutputIt 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.
1934template <typename R, typename UnaryPredicate>
1935auto 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.
1941template <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
1946template <typename R, typename T, typename Compare>
1947auto 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.
1954template <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
1959template <typename R, typename T, typename Compare>
1960auto 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.
1967template <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
1972template <typename R, typename T, typename Compare>
1973auto 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
1978template <typename R> auto min_element(R &&Range) {
1979 return std::min_element(adl_begin(Range), adl_end(Range));
1980}
1981
1982template <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
1986template <typename R> auto max_element(R &&Range) {
1987 return std::max_element(adl_begin(Range), adl_end(Range));
1988}
1989
1990template <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
1994template <typename R>
1996 std::stable_sort(adl_begin(Range), adl_end(Range));
1997}
1998
1999template <typename R, typename Compare>
2000void 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.
2006template <typename R, typename Predicate,
2007 typename Val = decltype(*adl_begin(std::declval<R>()))>
2008auto partition_point(R &&Range, Predicate P) {
2009 return std::partition_point(adl_begin(Range), adl_end(Range), P);
2010}
2011
2012template<typename Range, typename Predicate>
2013auto 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.
2019template <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.
2025template <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
2030template <typename L, typename R, typename BinaryPredicate>
2031bool 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.
2037template <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.
2045template <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.
2056template <typename Container, typename UnaryPredicate>
2057void 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());
2064template <typename Container, typename ValueType>
2065void 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());
2072template <typename Container, typename Range>
2073void 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`.
2078template <typename Container, typename... Args>
2079void 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).
2087template<typename Container, typename RandomAccessIterator>
2088void 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.
2105template<typename Container, typename Range = std::initializer_list<
2106 typename Container::value_type>>
2107void 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
2122template <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>>
2127inline 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
2139template <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>>
2143inline 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.
2149template <typename Container, typename UnaryFunctor, typename StreamT,
2150 typename T = detail::ValueOfRange<Container>>
2151inline 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}
2155template <typename Container, typename StreamT,
2156 typename T = detail::ValueOfRange<Container>>
2157inline void interleave(const Container &c, StreamT &os,
2158 const StringRef &separator) {
2159 interleave(
2160 c, os, [&](const T &a) { os << a; }, separator);
2161}
2162
2163template <typename Container, typename UnaryFunctor, typename StreamT,
2164 typename T = detail::ValueOfRange<Container>>
2165inline void interleaveComma(const Container &c, StreamT &os,
2166 UnaryFunctor each_fn) {
2167 interleave(c, os, each_fn, ", ");
2168}
2169template <typename Container, typename StreamT,
2170 typename T = detail::ValueOfRange<Container>>
2171inline 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
2180 void operator()(void* v) {
2181 ::free(v);
2182 }
2183};
2184
2185template<typename First, typename Second>
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.
2194template <typename T> struct deref {
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
2207namespace detail {
2208
2209/// Tuple-like type for `zip_enumerator` dereference.
2210template <typename... Refs> struct enumerator_result;
2211
2212template <typename... 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.
2226template <typename... Iters>
2227struct 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
2238template <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
2291private:
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
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
2342private:
2343 std::size_t Index;
2344};
2345
2346/// Infinite stream of increasing 0-based `size_t` indices.
2348 index_iterator begin() const { return {0}; }
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.
2360 std::size_t Begin;
2361 std::size_t End;
2362
2363public:
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
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///
2405template <typename FirstRange, typename... RestRanges>
2406auto 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 }
2416 FirstRange, RestRanges...>;
2417 return enumerator(detail::index_stream{}, std::forward<FirstRange>(First),
2418 std::forward<RestRanges>(Rest)...);
2419}
2420
2421namespace detail {
2422
2423template <typename Predicate, typename... Args>
2424bool 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.
2438template <typename... ArgsThenPredicate, size_t... InputIndexes>
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).
2453template <typename... ArgsAndPredicate>
2454bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate) {
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.
2463template <typename IterTy,
2464 typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
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.
2488template <typename IterTy,
2489 typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
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.
2509template <typename IterTy,
2510 typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
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
2521template <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
2526template <typename ContainerTy>
2527bool 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
2532template <typename ContainerTy>
2533bool 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.
2544template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
2545template <class T> constexpr T *to_address(T *P) { return P; }
2546
2547// Detect incomplete types, relying on the fact that their size is unknown.
2548namespace detail {
2549template <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.
2554template <typename T>
2556
2557} // end namespace llvm
2558
2559namespace std {
2560template <typename... Refs>
2561struct tuple_size<llvm::detail::enumerator_result<Refs...>>
2562 : std::integral_constant<std::size_t, sizeof...(Refs)> {};
2563
2564template <std::size_t I, typename... Refs>
2565struct tuple_element<I, llvm::detail::enumerator_result<Refs...>>
2566 : std::tuple_element<I, std::tuple<Refs...>> {};
2567
2568template <std::size_t I, typename... Refs>
2569struct 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
aarch64 promote const
basic Basic Alias true
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Given that RA is a live value
bool End
Definition: ELF_riscv.cpp:480
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define T
modulo schedule test
nvptx lower args
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains library features backported from future STL versions.
Value * RHS
Value * LHS
INLINE void g(uint32_t *state, size_t a, size_t b, size_t c, size_t d, uint32_t x, uint32_t y)
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
This class represents an Operation in the Expression.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
LLVM Value Representation.
Definition: Value.h:74
Templated storage wrapper for a callable.
Definition: STLExtras.h:210
Callable & operator=(Callable &&Other)
Definition: STLExtras.h:234
Callable(Callable const &Other)=default
Callable & operator=(Callable const &Other)
Definition: STLExtras.h:227
Callable(Callable &&Other)=default
Iterator wrapper that concatenates sequences together.
Definition: STLExtras.h:1023
concat_iterator & operator++()
Definition: STLExtras.h:1105
bool operator==(const concat_iterator &RHS) const
Definition: STLExtras.h:1114
ValueT & operator*() const
Definition: STLExtras.h:1110
concat_iterator(RangeTs &&... Ranges)
Constructs an iterator from a sequence of ranges.
Definition: STLExtras.h:1100
Helper to store a sequence of ranges being concatenated and access them.
Definition: STLExtras.h:1126
concat_range(RangeTs &&... Ranges)
Definition: STLExtras.h:1153
iterator end() const
Definition: STLExtras.h:1165
concat_iterator< ValueT, decltype(std::begin(std::declval< RangeTs & >()))... > iterator
Definition: STLExtras.h:1130
iterator begin() const
Definition: STLExtras.h:1159
Return a reference to the first or second member of a reference.
Definition: STLExtras.h:1414
std::conditional_t< std::is_reference< EltTy >::value, FirstTy, std::remove_reference_t< FirstTy > > type
Definition: STLExtras.h:1417
An iterator element of this range.
Definition: STLExtras.h:1245
The class represents the base of a range of indexed_accessor_iterators.
Definition: STLExtras.h:1239
DerivedT slice(size_t n, size_t m) const
Drop the first N elements, and keep M elements.
Definition: STLExtras.h:1291
size_t size() const
Return the size of this range.
Definition: STLExtras.h:1285
bool empty() const
Return if the range is empty.
Definition: STLExtras.h:1288
indexed_accessor_range_base & operator=(const indexed_accessor_range_base &)=default
DerivedT take_front(size_t n=1) const
Take the first n elements.
Definition: STLExtras.h:1308
ReferenceT operator[](size_t Index) const
Definition: STLExtras.h:1271
DerivedT drop_back(size_t n=1) const
Drop the last n elements.
Definition: STLExtras.h:1302
DerivedT take_back(size_t n=1) const
Take the last n elements.
Definition: STLExtras.h:1314
DerivedT drop_front(size_t n=1) const
Drop the first n elements.
Definition: STLExtras.h:1297
indexed_accessor_range_base(const indexed_accessor_range_base &)=default
indexed_accessor_range_base(BaseT base, ptrdiff_t count)
Definition: STLExtras.h:1266
indexed_accessor_range_base(indexed_accessor_range_base &&)=default
indexed_accessor_range_base(iterator begin, iterator end)
Definition: STLExtras.h:1261
ptrdiff_t count
The size from the owning range.
Definition: STLExtras.h:1344
BaseT base
The base that owns the provided range of values.
Definition: STLExtras.h:1342
indexed_accessor_range_base(const iterator_range< iterator > &range)
Definition: STLExtras.h:1264
const BaseT & getBase() const
Returns the base of this range.
Definition: STLExtras.h:1327
zip_longest_iterator(std::pair< Iters &&, Iters && >... ts)
Definition: STLExtras.h:948
value_type operator*() const
Definition: STLExtras.h:952
bool operator==(const zip_longest_iterator< Iters... > &other) const
Definition: STLExtras.h:961
zip_longest_iterator< Iters... > & operator++()
Definition: STLExtras.h:956
typename ZipLongestTupleType< Iters... >::type value_type
Definition: STLExtras.h:923
typename iterator::iterator_category iterator_category
Definition: STLExtras.h:970
typename iterator::pointer pointer
Definition: STLExtras.h:973
zip_longest_iterator< decltype(adl_begin(std::declval< Args >()))... > iterator
Definition: STLExtras.h:969
typename iterator::difference_type difference_type
Definition: STLExtras.h:972
typename iterator::reference reference
Definition: STLExtras.h:974
zip_longest_range(Args &&... ts_)
Definition: STLExtras.h:991
typename iterator::value_type value_type
Definition: STLExtras.h:971
iterator end()
Definition: STLExtras.h:828
typename iterator::value_type value_type
Definition: STLExtras.h:817
typename iterator::difference_type difference_type
Definition: STLExtras.h:818
typename iterator::reference reference
Definition: STLExtras.h:820
typename iterator::pointer pointer
Definition: STLExtras.h:819
zippy(Args &&...args)
Definition: STLExtras.h:823
typename const_iterator::reference const_reference
Definition: STLExtras.h:821
typename ZippyIteratorTuple< ItType, decltype(storage), IndexSequence >::type iterator
Definition: STLExtras.h:812
typename ZippyIteratorTuple< ItType, const decltype(storage), IndexSequence >::type const_iterator
Definition: STLExtras.h:815
const_iterator begin() const
Definition: STLExtras.h:825
typename iterator::iterator_category iterator_category
Definition: STLExtras.h:816
const_iterator end() const
Definition: STLExtras.h:827
iterator begin()
Definition: STLExtras.h:826
A pseudo-iterator adaptor that is designed to implement "early increment" style loops.
Definition: STLExtras.h:602
friend bool operator==(const early_inc_iterator_impl &LHS, const early_inc_iterator_impl &RHS)
Definition: STLExtras.h:633
early_inc_iterator_impl(WrappedIteratorT I)
Definition: STLExtras.h:613
early_inc_iterator_impl & operator++()
Definition: STLExtras.h:625
An iterator adaptor that filters the elements of given inner iterators.
Definition: STLExtras.h:450
filter_iterator_base & operator++()
Definition: STLExtras.h:476
WrappedIteratorT End
Definition: STLExtras.h:454
filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:467
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:524
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:497
filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
Definition: STLExtras.h:501
Increasing range of size_t indices.
Definition: STLExtras.h:2359
index_range(std::size_t Begin, std::size_t End)
Definition: STLExtras.h:2364
detail::index_iterator begin() const
Definition: STLExtras.h:2365
detail::index_iterator end() const
Definition: STLExtras.h:2366
A utility class used to implement an iterator that contains some base object and an index.
Definition: STLExtras.h:1190
DerivedT & operator+=(ptrdiff_t offset)
Definition: STLExtras.h:1204
const BaseT & getBase() const
Returns the current base of the iterator.
Definition: STLExtras.h:1217
bool operator==(const indexed_accessor_iterator &rhs) const
Definition: STLExtras.h:1196
indexed_accessor_iterator(BaseT base, ptrdiff_t index)
Definition: STLExtras.h:1220
DerivedT & operator-=(ptrdiff_t offset)
Definition: STLExtras.h:1208
ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const
Definition: STLExtras.h:1192
bool operator<(const indexed_accessor_iterator &rhs) const
Definition: STLExtras.h:1199
ptrdiff_t getIndex() const
Returns the current index of the iterator.
Definition: STLExtras.h:1214
This class provides an implementation of a range of indexed_accessor_iterators where the base is not ...
Definition: STLExtras.h:1376
indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
Definition: STLExtras.h:1378
const BaseT & getBase() const
Returns the current base of the range.
Definition: STLExtras.h:1387
ptrdiff_t getStartIndex() const
Returns the current start index of the range.
Definition: STLExtras.h:1390
static ReferenceT dereference_iterator(const std::pair< BaseT, ptrdiff_t > &base, ptrdiff_t index)
See detail::indexed_accessor_range_base for details.
Definition: STLExtras.h:1401
static std::pair< BaseT, ptrdiff_t > offset_base(const std::pair< BaseT, ptrdiff_t > &base, ptrdiff_t index)
See detail::indexed_accessor_range_base for details.
Definition: STLExtras.h:1394
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:237
WrappedIteratorT I
Definition: iterator.h:241
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
A range adaptor for a pair of iterators.
A base type of mapped iterator, that is useful for building derived iterators that do not need/want t...
Definition: STLExtras.h:394
ReferenceTy operator*() const
Definition: STLExtras.h:403
const FuncTy & getFunction() const
Definition: STLExtras.h:361
mapped_iterator(ItTy U, FuncTy F)
Definition: STLExtras.h:356
ReferenceTy operator*() const
Definition: STLExtras.h:363
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:236
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ Tail
Attemps to make calls as fast as possible while guaranteeing that tail call optimization can always b...
Definition: CallingConv.h:76
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
auto deref_or_none(const Iter &I, const Iter &End) -> std::optional< std::remove_const_t< std::remove_reference_t< decltype(*I)> > >
Definition: STLExtras.h:894
decltype(std::declval< Range & >().contains(std::declval< const Element & >())) check_has_member_contains_t
Definition: STLExtras.h:1856
decltype(std::declval< Range & >().find(std::declval< const Element & >()) !=std::declval< Range & >().end()) check_has_member_find_t
Definition: STLExtras.h:1865
bool all_of_zip_predicate_first(Predicate &&P, Args &&...args)
Definition: STLExtras.h:2424
static constexpr bool HasMemberFind
Definition: STLExtras.h:1868
std::conjunction< std::is_pointer< T >, std::is_trivially_copyable< typename std::iterator_traits< T >::value_type > > sort_trivially_copyable
Definition: STLExtras.h:1641
static constexpr bool HasFreeFunctionRBegin
Definition: STLExtras.h:414
bool operator!=(const DenseSetImpl< ValueT, MapTy, ValueInfoT > &LHS, const DenseSetImpl< ValueT, MapTy, ValueInfoT > &RHS)
Inequality comparison for DenseSet.
Definition: DenseSet.h:259
static constexpr bool HasMemberContains
Definition: STLExtras.h:1859
decltype(sizeof(T)) has_sizeof
Definition: STLExtras.h:2549
bool all_of_zip_predicate_last(std::tuple< ArgsThenPredicate... > argsThenPredicate, std::index_sequence< InputIndexes... >)
Definition: STLExtras.h:2439
Iter next_or_end(const Iter &I, const Iter &End)
Definition: STLExtras.h:887
decltype(adl_rbegin(std::declval< Range & >())) check_has_free_function_rbegin
Definition: STLExtras.h:411
static constexpr bool HasFreeFunctionSize
Definition: STLExtras.h:1695
decltype(adl_size(std::declval< Range & >())) check_has_free_function_size
Definition: STLExtras.h:1692
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
Definition: STLExtras.h:853
void stable_sort(R &&Range)
Definition: STLExtras.h:1995
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
std::conjunction< std::is_base_of< T, Ts >... > are_base_of
traits class for checking whether type T is a base class for all the given types in the variadic list...
Definition: STLExtras.h:134
auto min_element(R &&Range)
Definition: STLExtras.h:1978
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1715
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
detail::zip_longest_range< T, U, Args... > zip_longest(T &&t, U &&u, Args &&... args)
Iterate over two or more iterators at the same time.
Definition: STLExtras.h:1004
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1680
int(*)(const void *, const void *) get_array_pod_sort_comparator(const T &)
get_array_pod_sort_comparator - This is an internal helper function used to get type deduction of T r...
Definition: STLExtras.h:1570
constexpr bool is_incomplete_v
Detects when type T is incomplete.
Definition: STLExtras.h:2555
detail::zippy< detail::zip_first, T, U, Args... > zip_equal(T &&t, U &&u, Args &&...args)
zip iterator that assumes that all iteratees have the same length.
Definition: STLExtras.h:863
constexpr auto adl_begin(RangeT &&range) -> decltype(adl_detail::begin_impl(std::forward< RangeT >(range)))
Returns the begin iterator to range using std::begin and function found through Argument-Dependent Lo...
Definition: ADL.h:78
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition: STLExtras.h:2406
void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)
An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...
Definition: STLExtras.h:2127
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
Definition: STLExtras.h:2008
int array_pod_sort_comparator(const void *P1, const void *P2)
Adapt std::less<T> for array_pod_sort.
Definition: STLExtras.h:1557
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
mapped_iterator< ItTy, FuncTy > map_iterator(ItTy I, FuncTy F)
Definition: STLExtras.h:372
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2073
bool hasNItemsOrLess(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;})
Returns true if the sequence [Begin, End) has N or less items.
Definition: STLExtras.h:2511
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:2165
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:656
void shuffle(Iterator first, Iterator last, RNG &&g)
Definition: STLExtras.h:1541
constexpr auto adl_end(RangeT &&range) -> decltype(adl_detail::end_impl(std::forward< RangeT >(range)))
Returns the end iterator to range using std::end and functions found through Argument-Dependent Looku...
Definition: ADL.h:86
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:2013
auto binary_search(R &&Range, T &&Value)
Provide wrappers to std::binary_search which take ranges instead of having to pass begin/end explicit...
Definition: STLExtras.h:1941
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1967
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1768
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
auto map_range(ContainerTy &&C, FuncTy F)
Definition: STLExtras.h:377
typename detail::detector< void, Op, Args... >::value_t is_detected
Detects if a given trait holds for some set of arguments 'Args'.
Definition: STLExtras.h:79
constexpr auto adl_rbegin(RangeT &&range) -> decltype(adl_detail::rbegin_impl(std::forward< RangeT >(range)))
Returns the reverse-begin iterator to range using std::rbegin and function found through Argument-Dep...
Definition: ADL.h:94
bool hasNItemsOrMore(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;}, std::enable_if_t< !std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< std::remove_reference_t< decltype(Begin)> >::iterator_category >::value, void > *=nullptr)
Return true if the sequence [Begin, End) has N or more items.
Definition: STLExtras.h:2490
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2065
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
Definition: STLExtras.h:1928
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1729
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
constexpr size_t range_size(R &&Range)
Returns the size of the Range, i.e., the number of elements.
Definition: STLExtras.h:1705
detail::zippy< detail::zip_first, T, U, Args... > zip_first(T &&t, U &&u, Args &&...args)
zip iterator that, for the sake of efficiency, assumes the first iteratee to be the shortest.
Definition: STLExtras.h:876
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1647
bool hasNItems(IterTy &&Begin, IterTy &&End, unsigned N, Pred &&ShouldBeCounted=[](const decltype(*std::declval< IterTy >()) &) { return true;}, std::enable_if_t< !std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< std::remove_reference_t< decltype(Begin)> >::iterator_category >::value, void > *=nullptr)
Return true if the sequence [Begin, End) has exactly N items.
Definition: STLExtras.h:2465
auto find_if_not(R &&Range, UnaryPredicate P)
Definition: STLExtras.h:1754
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1736
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
Definition: STLExtras.h:1422
constexpr auto adl_size(RangeT &&range) -> decltype(adl_detail::size_impl(std::forward< RangeT >(range)))
Returns the size of range using std::size and functions found through Argument-Dependent Lookup (ADL)...
Definition: ADL.h:118
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1176
bool is_sorted(R &&Range, Compare C)
Wrapper function around std::is_sorted to check if elements in a range R are sorted with respect to a...
Definition: STLExtras.h:1902
bool hasSingleElement(ContainerTy &&C)
Returns true if the given container only contains a single element.
Definition: STLExtras.h:322
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:572
std::pair< T *, bool > find_singleton_nested(R &&Range, Predicate P, bool AllowRepeats=false)
Return a pair consisting of the single value in Range that satisfies P(<member of Range> *,...
Definition: STLExtras.h:1802
T * find_singleton(R &&Range, Predicate P, bool AllowRepeats=false)
Return the single value in Range that satisfies P(<member of Range> *, AllowRepeats)->T * returning n...
Definition: STLExtras.h:1778
auto drop_end(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the last N elements excluded.
Definition: STLExtras.h:336
@ Other
Any other memory.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
auto remove_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1761
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1954
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:1914
DWARFExpression::Operation Op
auto max_element(R &&Range)
Definition: STLExtras.h:1986
OutputIt replace_copy_if(R &&Range, OutputIt Out, UnaryPredicate P, const T &NewValue)
Provide wrappers to std::replace_copy_if which take ranges instead of having to pass begin/end explic...
Definition: STLExtras.h:1831
auto to_address(const Ptr &P)
Returns a raw pointer that represents the same address as the argument.
Definition: STLExtras.h:2544
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1824
auto partition(R &&Range, UnaryPredicate P)
Provide wrappers to std::partition which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1935
std::disjunction< std::is_same< T, Ts >... > is_one_of
traits class for checking whether type T is one of any of the given types in the variadic list.
Definition: STLExtras.h:129
auto make_second_range(ContainerTy &&c)
Given a container of pairs, return a range over the second elements.
Definition: STLExtras.h:1432
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
OutputIt replace_copy(R &&Range, OutputIt Out, const T &OldValue, const T &NewValue)
Provide wrappers to std::replace_copy which take ranges instead of having to pass begin/end explicitl...
Definition: STLExtras.h:1840
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
Definition: STLExtras.h:1921
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
std::tuple_element_t< I, std::tuple< Ts... > > TypeAtIndex
Find the type at a given index in a list of types.
Definition: STLExtras.h:179
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2057
constexpr auto adl_rend(RangeT &&range) -> decltype(adl_detail::rend_impl(std::forward< RangeT >(range)))
Returns the reverse-end iterator to range using std::rend and functions found through Argument-Depend...
Definition: ADL.h:102
void replace(Container &Cont, typename Container::iterator ContIt, typename Container::iterator ContEnd, RandomAccessIterator ValIt, RandomAccessIterator ValEnd)
Given a sequence container Cont, replace the range [ContIt, ContEnd) with the range [ValIt,...
Definition: STLExtras.h:2088
void append_values(Container &C, Args &&...Values)
Appends all Values to container C.
Definition: STLExtras.h:2079
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
Definition: STLExtras.h:2045
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1607
constexpr decltype(auto) makeVisitor(CallableTs &&...Callables)
Returns an opaquely-typed Callable object whose operator() overload set is the sum of the operator() ...
Definition: STLExtras.h:1530
bool equal(L &&LRange, R &&RRange)
Wrapper function around std::equal to detect if pair-wise elements between two ranges are the same.
Definition: STLExtras.h:2025
bool all_of_zip(ArgsAndPredicate &&...argsAndPredicate)
Compare two zipped ranges using the provided predicate (as last argument).
Definition: STLExtras.h:2454
constexpr auto addEnumValues(EnumTy1 LHS, EnumTy2 RHS)
Helper which adds two underlying types of enumeration type.
Definition: STLExtras.h:188
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
Find the first index where a type appears in a list of types.
Definition: STLExtras.h:168
void operator()(void *v)
Definition: STLExtras.h:2180
Determine if all types in Ts are distinct.
Definition: STLExtras.h:156
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:2194
auto operator()(A &lhs, B &rhs) const
Definition: STLExtras.h:2200
constexpr Visitor(HeadT &&Head, TailTs &&...Tail)
Definition: STLExtras.h:1487
constexpr Visitor(HeadT &&Head)
Definition: STLExtras.h:1495
std::optional< std::remove_const_t< std::remove_reference_t< decltype(*std::declval< Iter >())> > > type
Definition: STLExtras.h:903
std::tuple< typename ZipLongestItemType< Iters >::type... > type
Definition: STLExtras.h:907
std::tuple< decltype(*declval< Iters >())... > type
Definition: STLExtras.h:681
ItType< decltype(adl_begin(std::get< Ns >(declval< const std::tuple< Args... > & >())))... > type
Definition: STLExtras.h:802
ItType< decltype(adl_begin(std::get< Ns >(declval< std::tuple< Args... > & >())))... > type
Definition: STLExtras.h:793
Helper to obtain the iterator types for the tuple storage within zippy.
Definition: STLExtras.h:785
std::false_type value_t
Definition: STLExtras.h:63
decltype(auto) value() const
Returns the value(s) for the current iterator.
Definition: STLExtras.h:2259
friend decltype(auto) get(const enumerator_result &Result)
Returns the value at index I.
Definition: STLExtras.h:2275
std::tuple< std::size_t, Refs... > value_reference_tuple
Definition: STLExtras.h:2248
friend bool operator==(const enumerator_result &Result, const std::tuple< std::size_t, Ts... > &Other)
Definition: STLExtras.h:2283
std::size_t index() const
Returns the 0-based index of the current position within the original input range(s).
Definition: STLExtras.h:2255
friend std::size_t get(const enumerator_result &Result)
Returns the value at index I. This case covers the index.
Definition: STLExtras.h:2268
enumerator_result(std::size_t Index, Refs &&...Rs)
Definition: STLExtras.h:2250
Tuple-like type for zip_enumerator dereference.
Definition: STLExtras.h:2210
std::bidirectional_iterator_tag type
Definition: STLExtras.h:542
std::forward_iterator_tag type
Definition: STLExtras.h:538
Helper which sets its type member to forward_iterator_tag if the category of IterT does not derive fr...
Definition: STLExtras.h:548
typename fwd_or_bidi_tag_impl< std::is_base_of< std::bidirectional_iterator_tag, typename std::iterator_traits< IterT >::iterator_category >::value >::type type
Definition: STLExtras.h:551
friend bool operator==(const index_iterator &Lhs, const index_iterator &Rhs)
Definition: STLExtras.h:2334
std::ptrdiff_t operator-(const index_iterator &R) const
Definition: STLExtras.h:2323
std::size_t operator*() const
Definition: STLExtras.h:2332
friend bool operator<(const index_iterator &Lhs, const index_iterator &Rhs)
Definition: STLExtras.h:2338
index_iterator & operator-=(std::ptrdiff_t N)
Definition: STLExtras.h:2318
index_iterator & operator+=(std::ptrdiff_t N)
Definition: STLExtras.h:2313
index_iterator(std::size_t Index)
Definition: STLExtras.h:2311
Infinite stream of increasing 0-based size_t indices.
Definition: STLExtras.h:2347
index_iterator begin() const
Definition: STLExtras.h:2348
index_iterator end() const
Definition: STLExtras.h:2349
std::index_sequence_for< Iters... > IndexSequence
Definition: STLExtras.h:703
void tup_inc(std::index_sequence< Ns... >)
Definition: STLExtras.h:713
zip_common(Iters &&... ts)
Definition: STLExtras.h:729
bool test_all_equals(const zip_common &other, std::index_sequence< Ns... >) const
Definition: STLExtras.h:722
std::tuple< Iters... > iterators
Definition: STLExtras.h:706
ZipType & operator++()
Definition: STLExtras.h:733
value_type operator*() const
Definition: STLExtras.h:731
typename Base::value_type value_type
Definition: STLExtras.h:704
bool all_equals(zip_common &other)
Return true if all the iterator are matching other's iterators.
Definition: STLExtras.h:746
ZipType & operator--()
Definition: STLExtras.h:738
void tup_dec(std::index_sequence< Ns... >)
Definition: STLExtras.h:717
value_type deref(std::index_sequence< Ns... >) const
Definition: STLExtras.h:709
Zippy iterator that uses the second iterator for comparisons.
Definition: STLExtras.h:2228
bool operator==(const zip_enumerator &Other) const
Definition: STLExtras.h:2233
bool operator==(const zip_first &other) const
Definition: STLExtras.h:757
bool operator==(const zip_shortest &other) const
Definition: STLExtras.h:769
std::tuple_element_t< Index, std::tuple< Args... > > arg_t
The type of an argument to this function.
Definition: STLExtras.h:99
ReturnType result_t
The result type of this function.
Definition: STLExtras.h:95
std::tuple_element_t< i, std::tuple< Args... > > arg_t
The type of an argument to this function.
Definition: STLExtras.h:116
ReturnType result_t
The result type of this function.
Definition: STLExtras.h:112
This class provides various trait information about a callable object.
Definition: STLExtras.h:86
Function object to check whether the first component of a container supported by std::get (like std::...
Definition: STLExtras.h:1450
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:1451
Function object to check whether the second component of a container supported by std::get (like std:...
Definition: STLExtras.h:1459
bool operator()(const T &lhs, const T &rhs) const
Definition: STLExtras.h:1460
std::add_pointer_t< std::add_const_t< T > > type
Definition: STLExtras.h:54
std::add_lvalue_reference_t< std::add_const_t< T > > type
Definition: STLExtras.h:58
Function object to apply a binary function to the first component of a std::pair.
Definition: STLExtras.h:1468
size_t operator()(const std::pair< First, Second > &P) const
Definition: STLExtras.h:2187
Utility type to build an inheritance chain that makes it easy to rank overload candidates.
Definition: STLExtras.h:1479