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