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