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