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