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