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