STLExtras.h revision 360784
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// This file contains some templates that are useful if you are working with the 10// STL at all. 11// 12// No library is required when using these functions. 13// 14//===----------------------------------------------------------------------===// 15 16#ifndef LLVM_ADT_STLEXTRAS_H 17#define LLVM_ADT_STLEXTRAS_H 18 19#include "llvm/ADT/Optional.h" 20#include "llvm/ADT/iterator.h" 21#include "llvm/ADT/iterator_range.h" 22#include "llvm/Config/abi-breaking.h" 23#include "llvm/Support/ErrorHandling.h" 24#include <algorithm> 25#include <cassert> 26#include <cstddef> 27#include <cstdint> 28#include <cstdlib> 29#include <functional> 30#include <initializer_list> 31#include <iterator> 32#include <limits> 33#include <memory> 34#include <tuple> 35#include <type_traits> 36#include <utility> 37 38#ifdef EXPENSIVE_CHECKS 39#include <random> // for std::mt19937 40#endif 41 42namespace llvm { 43 44// Only used by compiler if both template types are the same. Useful when 45// using SFINAE to test for the existence of member functions. 46template <typename T, T> struct SameType; 47 48namespace detail { 49 50template <typename RangeT> 51using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 52 53} // end namespace detail 54 55//===----------------------------------------------------------------------===// 56// Extra additions to <type_traits> 57//===----------------------------------------------------------------------===// 58 59template <typename T> 60struct negation : std::integral_constant<bool, !bool(T::value)> {}; 61 62template <typename...> struct conjunction : std::true_type {}; 63template <typename B1> struct conjunction<B1> : B1 {}; 64template <typename B1, typename... Bn> 65struct conjunction<B1, Bn...> 66 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {}; 67 68template <typename T> struct make_const_ptr { 69 using type = 70 typename std::add_pointer<typename std::add_const<T>::type>::type; 71}; 72 73template <typename T> struct make_const_ref { 74 using type = typename std::add_lvalue_reference< 75 typename std::add_const<T>::type>::type; 76}; 77 78//===----------------------------------------------------------------------===// 79// Extra additions to <functional> 80//===----------------------------------------------------------------------===// 81 82template <class Ty> struct identity { 83 using argument_type = Ty; 84 85 Ty &operator()(Ty &self) const { 86 return self; 87 } 88 const Ty &operator()(const Ty &self) const { 89 return self; 90 } 91}; 92 93/// An efficient, type-erasing, non-owning reference to a callable. This is 94/// intended for use as the type of a function parameter that is not used 95/// after the function in question returns. 96/// 97/// This class does not own the callable, so it is not in general safe to store 98/// a function_ref. 99template<typename Fn> class function_ref; 100 101template<typename Ret, typename ...Params> 102class function_ref<Ret(Params...)> { 103 Ret (*callback)(intptr_t callable, Params ...params) = nullptr; 104 intptr_t callable; 105 106 template<typename Callable> 107 static Ret callback_fn(intptr_t callable, Params ...params) { 108 return (*reinterpret_cast<Callable*>(callable))( 109 std::forward<Params>(params)...); 110 } 111 112public: 113 function_ref() = default; 114 function_ref(std::nullptr_t) {} 115 116 template <typename Callable> 117 function_ref(Callable &&callable, 118 typename std::enable_if< 119 !std::is_same<typename std::remove_reference<Callable>::type, 120 function_ref>::value>::type * = nullptr) 121 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 122 callable(reinterpret_cast<intptr_t>(&callable)) {} 123 124 Ret operator()(Params ...params) const { 125 return callback(callable, std::forward<Params>(params)...); 126 } 127 128 operator bool() const { return callback; } 129}; 130 131// deleter - Very very very simple method that is used to invoke operator 132// delete on something. It is used like this: 133// 134// for_each(V.begin(), B.end(), deleter<Interval>); 135template <class T> 136inline void deleter(T *Ptr) { 137 delete Ptr; 138} 139 140//===----------------------------------------------------------------------===// 141// Extra additions to <iterator> 142//===----------------------------------------------------------------------===// 143 144namespace adl_detail { 145 146using std::begin; 147 148template <typename ContainerTy> 149auto adl_begin(ContainerTy &&container) 150 -> decltype(begin(std::forward<ContainerTy>(container))) { 151 return begin(std::forward<ContainerTy>(container)); 152} 153 154using std::end; 155 156template <typename ContainerTy> 157auto adl_end(ContainerTy &&container) 158 -> decltype(end(std::forward<ContainerTy>(container))) { 159 return end(std::forward<ContainerTy>(container)); 160} 161 162using std::swap; 163 164template <typename T> 165void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(), 166 std::declval<T>()))) { 167 swap(std::forward<T>(lhs), std::forward<T>(rhs)); 168} 169 170} // end namespace adl_detail 171 172template <typename ContainerTy> 173auto adl_begin(ContainerTy &&container) 174 -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) { 175 return adl_detail::adl_begin(std::forward<ContainerTy>(container)); 176} 177 178template <typename ContainerTy> 179auto adl_end(ContainerTy &&container) 180 -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) { 181 return adl_detail::adl_end(std::forward<ContainerTy>(container)); 182} 183 184template <typename T> 185void adl_swap(T &&lhs, T &&rhs) noexcept( 186 noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) { 187 adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs)); 188} 189 190/// Test whether \p RangeOrContainer is empty. Similar to C++17 std::empty. 191template <typename T> 192constexpr bool empty(const T &RangeOrContainer) { 193 return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer); 194} 195 196/// Return a range covering \p RangeOrContainer with the first N elements 197/// excluded. 198template <typename T> 199auto drop_begin(T &&RangeOrContainer, size_t N) -> 200 iterator_range<decltype(adl_begin(RangeOrContainer))> { 201 return make_range(std::next(adl_begin(RangeOrContainer), N), 202 adl_end(RangeOrContainer)); 203} 204 205// mapped_iterator - This is a simple iterator adapter that causes a function to 206// be applied whenever operator* is invoked on the iterator. 207 208template <typename ItTy, typename FuncTy, 209 typename FuncReturnTy = 210 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> 211class mapped_iterator 212 : public iterator_adaptor_base< 213 mapped_iterator<ItTy, FuncTy>, ItTy, 214 typename std::iterator_traits<ItTy>::iterator_category, 215 typename std::remove_reference<FuncReturnTy>::type> { 216public: 217 mapped_iterator(ItTy U, FuncTy F) 218 : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {} 219 220 ItTy getCurrent() { return this->I; } 221 222 FuncReturnTy operator*() { return F(*this->I); } 223 224private: 225 FuncTy F; 226}; 227 228// map_iterator - Provide a convenient way to create mapped_iterators, just like 229// make_pair is useful for creating pairs... 230template <class ItTy, class FuncTy> 231inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) { 232 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F)); 233} 234 235template <class ContainerTy, class FuncTy> 236auto map_range(ContainerTy &&C, FuncTy F) 237 -> decltype(make_range(map_iterator(C.begin(), F), 238 map_iterator(C.end(), F))) { 239 return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F)); 240} 241 242/// Helper to determine if type T has a member called rbegin(). 243template <typename Ty> class has_rbegin_impl { 244 using yes = char[1]; 245 using no = char[2]; 246 247 template <typename Inner> 248 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); 249 250 template <typename> 251 static no& test(...); 252 253public: 254 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 255}; 256 257/// Metafunction to determine if T& or T has a member called rbegin(). 258template <typename Ty> 259struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> { 260}; 261 262// Returns an iterator_range over the given container which iterates in reverse. 263// Note that the container must have rbegin()/rend() methods for this to work. 264template <typename ContainerTy> 265auto reverse(ContainerTy &&C, 266 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = 267 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { 268 return make_range(C.rbegin(), C.rend()); 269} 270 271// Returns a std::reverse_iterator wrapped around the given iterator. 272template <typename IteratorTy> 273std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { 274 return std::reverse_iterator<IteratorTy>(It); 275} 276 277// Returns an iterator_range over the given container which iterates in reverse. 278// Note that the container must have begin()/end() methods which return 279// bidirectional iterators for this to work. 280template <typename ContainerTy> 281auto reverse( 282 ContainerTy &&C, 283 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) 284 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), 285 llvm::make_reverse_iterator(std::begin(C)))) { 286 return make_range(llvm::make_reverse_iterator(std::end(C)), 287 llvm::make_reverse_iterator(std::begin(C))); 288} 289 290/// An iterator adaptor that filters the elements of given inner iterators. 291/// 292/// The predicate parameter should be a callable object that accepts the wrapped 293/// iterator's reference type and returns a bool. When incrementing or 294/// decrementing the iterator, it will call the predicate on each element and 295/// skip any where it returns false. 296/// 297/// \code 298/// int A[] = { 1, 2, 3, 4 }; 299/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); 300/// // R contains { 1, 3 }. 301/// \endcode 302/// 303/// Note: filter_iterator_base implements support for forward iteration. 304/// filter_iterator_impl exists to provide support for bidirectional iteration, 305/// conditional on whether the wrapped iterator supports it. 306template <typename WrappedIteratorT, typename PredicateT, typename IterTag> 307class filter_iterator_base 308 : public iterator_adaptor_base< 309 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>, 310 WrappedIteratorT, 311 typename std::common_type< 312 IterTag, typename std::iterator_traits< 313 WrappedIteratorT>::iterator_category>::type> { 314 using BaseT = iterator_adaptor_base< 315 filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>, 316 WrappedIteratorT, 317 typename std::common_type< 318 IterTag, typename std::iterator_traits< 319 WrappedIteratorT>::iterator_category>::type>; 320 321protected: 322 WrappedIteratorT End; 323 PredicateT Pred; 324 325 void findNextValid() { 326 while (this->I != End && !Pred(*this->I)) 327 BaseT::operator++(); 328 } 329 330 // Construct the iterator. The begin iterator needs to know where the end 331 // is, so that it can properly stop when it gets there. The end iterator only 332 // needs the predicate to support bidirectional iteration. 333 filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End, 334 PredicateT Pred) 335 : BaseT(Begin), End(End), Pred(Pred) { 336 findNextValid(); 337 } 338 339public: 340 using BaseT::operator++; 341 342 filter_iterator_base &operator++() { 343 BaseT::operator++(); 344 findNextValid(); 345 return *this; 346 } 347}; 348 349/// Specialization of filter_iterator_base for forward iteration only. 350template <typename WrappedIteratorT, typename PredicateT, 351 typename IterTag = std::forward_iterator_tag> 352class filter_iterator_impl 353 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> { 354 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>; 355 356public: 357 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, 358 PredicateT Pred) 359 : BaseT(Begin, End, Pred) {} 360}; 361 362/// Specialization of filter_iterator_base for bidirectional iteration. 363template <typename WrappedIteratorT, typename PredicateT> 364class filter_iterator_impl<WrappedIteratorT, PredicateT, 365 std::bidirectional_iterator_tag> 366 : public filter_iterator_base<WrappedIteratorT, PredicateT, 367 std::bidirectional_iterator_tag> { 368 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, 369 std::bidirectional_iterator_tag>; 370 void findPrevValid() { 371 while (!this->Pred(*this->I)) 372 BaseT::operator--(); 373 } 374 375public: 376 using BaseT::operator--; 377 378 filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End, 379 PredicateT Pred) 380 : BaseT(Begin, End, Pred) {} 381 382 filter_iterator_impl &operator--() { 383 BaseT::operator--(); 384 findPrevValid(); 385 return *this; 386 } 387}; 388 389namespace detail { 390 391template <bool is_bidirectional> struct fwd_or_bidi_tag_impl { 392 using type = std::forward_iterator_tag; 393}; 394 395template <> struct fwd_or_bidi_tag_impl<true> { 396 using type = std::bidirectional_iterator_tag; 397}; 398 399/// Helper which sets its type member to forward_iterator_tag if the category 400/// of \p IterT does not derive from bidirectional_iterator_tag, and to 401/// bidirectional_iterator_tag otherwise. 402template <typename IterT> struct fwd_or_bidi_tag { 403 using type = typename fwd_or_bidi_tag_impl<std::is_base_of< 404 std::bidirectional_iterator_tag, 405 typename std::iterator_traits<IterT>::iterator_category>::value>::type; 406}; 407 408} // namespace detail 409 410/// Defines filter_iterator to a suitable specialization of 411/// filter_iterator_impl, based on the underlying iterator's category. 412template <typename WrappedIteratorT, typename PredicateT> 413using filter_iterator = filter_iterator_impl< 414 WrappedIteratorT, PredicateT, 415 typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>; 416 417/// Convenience function that takes a range of elements and a predicate, 418/// and return a new filter_iterator range. 419/// 420/// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the 421/// lifetime of that temporary is not kept by the returned range object, and the 422/// temporary is going to be dropped on the floor after the make_iterator_range 423/// full expression that contains this function call. 424template <typename RangeT, typename PredicateT> 425iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 426make_filter_range(RangeT &&Range, PredicateT Pred) { 427 using FilterIteratorT = 428 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; 429 return make_range( 430 FilterIteratorT(std::begin(std::forward<RangeT>(Range)), 431 std::end(std::forward<RangeT>(Range)), Pred), 432 FilterIteratorT(std::end(std::forward<RangeT>(Range)), 433 std::end(std::forward<RangeT>(Range)), Pred)); 434} 435 436/// A pseudo-iterator adaptor that is designed to implement "early increment" 437/// style loops. 438/// 439/// This is *not a normal iterator* and should almost never be used directly. It 440/// is intended primarily to be used with range based for loops and some range 441/// algorithms. 442/// 443/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but 444/// somewhere between them. The constraints of these iterators are: 445/// 446/// - On construction or after being incremented, it is comparable and 447/// dereferencable. It is *not* incrementable. 448/// - After being dereferenced, it is neither comparable nor dereferencable, it 449/// is only incrementable. 450/// 451/// This means you can only dereference the iterator once, and you can only 452/// increment it once between dereferences. 453template <typename WrappedIteratorT> 454class early_inc_iterator_impl 455 : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>, 456 WrappedIteratorT, std::input_iterator_tag> { 457 using BaseT = 458 iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>, 459 WrappedIteratorT, std::input_iterator_tag>; 460 461 using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer; 462 463protected: 464#if LLVM_ENABLE_ABI_BREAKING_CHECKS 465 bool IsEarlyIncremented = false; 466#endif 467 468public: 469 early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {} 470 471 using BaseT::operator*; 472 typename BaseT::reference operator*() { 473#if LLVM_ENABLE_ABI_BREAKING_CHECKS 474 assert(!IsEarlyIncremented && "Cannot dereference twice!"); 475 IsEarlyIncremented = true; 476#endif 477 return *(this->I)++; 478 } 479 480 using BaseT::operator++; 481 early_inc_iterator_impl &operator++() { 482#if LLVM_ENABLE_ABI_BREAKING_CHECKS 483 assert(IsEarlyIncremented && "Cannot increment before dereferencing!"); 484 IsEarlyIncremented = false; 485#endif 486 return *this; 487 } 488 489 using BaseT::operator==; 490 bool operator==(const early_inc_iterator_impl &RHS) const { 491#if LLVM_ENABLE_ABI_BREAKING_CHECKS 492 assert(!IsEarlyIncremented && "Cannot compare after dereferencing!"); 493#endif 494 return BaseT::operator==(RHS); 495 } 496}; 497 498/// Make a range that does early increment to allow mutation of the underlying 499/// range without disrupting iteration. 500/// 501/// The underlying iterator will be incremented immediately after it is 502/// dereferenced, allowing deletion of the current node or insertion of nodes to 503/// not disrupt iteration provided they do not invalidate the *next* iterator -- 504/// the current iterator can be invalidated. 505/// 506/// This requires a very exact pattern of use that is only really suitable to 507/// range based for loops and other range algorithms that explicitly guarantee 508/// to dereference exactly once each element, and to increment exactly once each 509/// element. 510template <typename RangeT> 511iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>> 512make_early_inc_range(RangeT &&Range) { 513 using EarlyIncIteratorT = 514 early_inc_iterator_impl<detail::IterOfRange<RangeT>>; 515 return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))), 516 EarlyIncIteratorT(std::end(std::forward<RangeT>(Range)))); 517} 518 519// forward declarations required by zip_shortest/zip_first/zip_longest 520template <typename R, typename UnaryPredicate> 521bool all_of(R &&range, UnaryPredicate P); 522template <typename R, typename UnaryPredicate> 523bool any_of(R &&range, UnaryPredicate P); 524 525namespace detail { 526 527using std::declval; 528 529// We have to alias this since inlining the actual type at the usage site 530// in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. 531template<typename... Iters> struct ZipTupleType { 532 using type = std::tuple<decltype(*declval<Iters>())...>; 533}; 534 535template <typename ZipType, typename... Iters> 536using zip_traits = iterator_facade_base< 537 ZipType, typename std::common_type<std::bidirectional_iterator_tag, 538 typename std::iterator_traits< 539 Iters>::iterator_category...>::type, 540 // ^ TODO: Implement random access methods. 541 typename ZipTupleType<Iters...>::type, 542 typename std::iterator_traits<typename std::tuple_element< 543 0, std::tuple<Iters...>>::type>::difference_type, 544 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all 545 // inner iterators have the same difference_type. It would fail if, for 546 // instance, the second field's difference_type were non-numeric while the 547 // first is. 548 typename ZipTupleType<Iters...>::type *, 549 typename ZipTupleType<Iters...>::type>; 550 551template <typename ZipType, typename... Iters> 552struct zip_common : public zip_traits<ZipType, Iters...> { 553 using Base = zip_traits<ZipType, Iters...>; 554 using value_type = typename Base::value_type; 555 556 std::tuple<Iters...> iterators; 557 558protected: 559 template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const { 560 return value_type(*std::get<Ns>(iterators)...); 561 } 562 563 template <size_t... Ns> 564 decltype(iterators) tup_inc(std::index_sequence<Ns...>) const { 565 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); 566 } 567 568 template <size_t... Ns> 569 decltype(iterators) tup_dec(std::index_sequence<Ns...>) const { 570 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...); 571 } 572 573public: 574 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} 575 576 value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); } 577 578 const value_type operator*() const { 579 return deref(std::index_sequence_for<Iters...>{}); 580 } 581 582 ZipType &operator++() { 583 iterators = tup_inc(std::index_sequence_for<Iters...>{}); 584 return *reinterpret_cast<ZipType *>(this); 585 } 586 587 ZipType &operator--() { 588 static_assert(Base::IsBidirectional, 589 "All inner iterators must be at least bidirectional."); 590 iterators = tup_dec(std::index_sequence_for<Iters...>{}); 591 return *reinterpret_cast<ZipType *>(this); 592 } 593}; 594 595template <typename... Iters> 596struct zip_first : public zip_common<zip_first<Iters...>, Iters...> { 597 using Base = zip_common<zip_first<Iters...>, Iters...>; 598 599 bool operator==(const zip_first<Iters...> &other) const { 600 return std::get<0>(this->iterators) == std::get<0>(other.iterators); 601 } 602 603 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} 604}; 605 606template <typename... Iters> 607class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> { 608 template <size_t... Ns> 609 bool test(const zip_shortest<Iters...> &other, 610 std::index_sequence<Ns...>) const { 611 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != 612 std::get<Ns>(other.iterators)...}, 613 identity<bool>{}); 614 } 615 616public: 617 using Base = zip_common<zip_shortest<Iters...>, Iters...>; 618 619 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} 620 621 bool operator==(const zip_shortest<Iters...> &other) const { 622 return !test(other, std::index_sequence_for<Iters...>{}); 623 } 624}; 625 626template <template <typename...> class ItType, typename... Args> class zippy { 627public: 628 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>; 629 using iterator_category = typename iterator::iterator_category; 630 using value_type = typename iterator::value_type; 631 using difference_type = typename iterator::difference_type; 632 using pointer = typename iterator::pointer; 633 using reference = typename iterator::reference; 634 635private: 636 std::tuple<Args...> ts; 637 638 template <size_t... Ns> 639 iterator begin_impl(std::index_sequence<Ns...>) const { 640 return iterator(std::begin(std::get<Ns>(ts))...); 641 } 642 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const { 643 return iterator(std::end(std::get<Ns>(ts))...); 644 } 645 646public: 647 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} 648 649 iterator begin() const { 650 return begin_impl(std::index_sequence_for<Args...>{}); 651 } 652 iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); } 653}; 654 655} // end namespace detail 656 657/// zip iterator for two or more iteratable types. 658template <typename T, typename U, typename... Args> 659detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, 660 Args &&... args) { 661 return detail::zippy<detail::zip_shortest, T, U, Args...>( 662 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 663} 664 665/// zip iterator that, for the sake of efficiency, assumes the first iteratee to 666/// be the shortest. 667template <typename T, typename U, typename... Args> 668detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, 669 Args &&... args) { 670 return detail::zippy<detail::zip_first, T, U, Args...>( 671 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 672} 673 674namespace detail { 675template <typename Iter> 676static Iter next_or_end(const Iter &I, const Iter &End) { 677 if (I == End) 678 return End; 679 return std::next(I); 680} 681 682template <typename Iter> 683static auto deref_or_none(const Iter &I, const Iter &End) 684 -> llvm::Optional<typename std::remove_const< 685 typename std::remove_reference<decltype(*I)>::type>::type> { 686 if (I == End) 687 return None; 688 return *I; 689} 690 691template <typename Iter> struct ZipLongestItemType { 692 using type = 693 llvm::Optional<typename std::remove_const<typename std::remove_reference< 694 decltype(*std::declval<Iter>())>::type>::type>; 695}; 696 697template <typename... Iters> struct ZipLongestTupleType { 698 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>; 699}; 700 701template <typename... Iters> 702class zip_longest_iterator 703 : public iterator_facade_base< 704 zip_longest_iterator<Iters...>, 705 typename std::common_type< 706 std::forward_iterator_tag, 707 typename std::iterator_traits<Iters>::iterator_category...>::type, 708 typename ZipLongestTupleType<Iters...>::type, 709 typename std::iterator_traits<typename std::tuple_element< 710 0, std::tuple<Iters...>>::type>::difference_type, 711 typename ZipLongestTupleType<Iters...>::type *, 712 typename ZipLongestTupleType<Iters...>::type> { 713public: 714 using value_type = typename ZipLongestTupleType<Iters...>::type; 715 716private: 717 std::tuple<Iters...> iterators; 718 std::tuple<Iters...> end_iterators; 719 720 template <size_t... Ns> 721 bool test(const zip_longest_iterator<Iters...> &other, 722 std::index_sequence<Ns...>) const { 723 return llvm::any_of( 724 std::initializer_list<bool>{std::get<Ns>(this->iterators) != 725 std::get<Ns>(other.iterators)...}, 726 identity<bool>{}); 727 } 728 729 template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const { 730 return value_type( 731 deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...); 732 } 733 734 template <size_t... Ns> 735 decltype(iterators) tup_inc(std::index_sequence<Ns...>) const { 736 return std::tuple<Iters...>( 737 next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...); 738 } 739 740public: 741 zip_longest_iterator(std::pair<Iters &&, Iters &&>... ts) 742 : iterators(std::forward<Iters>(ts.first)...), 743 end_iterators(std::forward<Iters>(ts.second)...) {} 744 745 value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); } 746 747 value_type operator*() const { 748 return deref(std::index_sequence_for<Iters...>{}); 749 } 750 751 zip_longest_iterator<Iters...> &operator++() { 752 iterators = tup_inc(std::index_sequence_for<Iters...>{}); 753 return *this; 754 } 755 756 bool operator==(const zip_longest_iterator<Iters...> &other) const { 757 return !test(other, std::index_sequence_for<Iters...>{}); 758 } 759}; 760 761template <typename... Args> class zip_longest_range { 762public: 763 using iterator = 764 zip_longest_iterator<decltype(adl_begin(std::declval<Args>()))...>; 765 using iterator_category = typename iterator::iterator_category; 766 using value_type = typename iterator::value_type; 767 using difference_type = typename iterator::difference_type; 768 using pointer = typename iterator::pointer; 769 using reference = typename iterator::reference; 770 771private: 772 std::tuple<Args...> ts; 773 774 template <size_t... Ns> 775 iterator begin_impl(std::index_sequence<Ns...>) const { 776 return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)), 777 adl_end(std::get<Ns>(ts)))...); 778 } 779 780 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const { 781 return iterator(std::make_pair(adl_end(std::get<Ns>(ts)), 782 adl_end(std::get<Ns>(ts)))...); 783 } 784 785public: 786 zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} 787 788 iterator begin() const { 789 return begin_impl(std::index_sequence_for<Args...>{}); 790 } 791 iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); } 792}; 793} // namespace detail 794 795/// Iterate over two or more iterators at the same time. Iteration continues 796/// until all iterators reach the end. The llvm::Optional only contains a value 797/// if the iterator has not reached the end. 798template <typename T, typename U, typename... Args> 799detail::zip_longest_range<T, U, Args...> zip_longest(T &&t, U &&u, 800 Args &&... args) { 801 return detail::zip_longest_range<T, U, Args...>( 802 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 803} 804 805/// Iterator wrapper that concatenates sequences together. 806/// 807/// This can concatenate different iterators, even with different types, into 808/// a single iterator provided the value types of all the concatenated 809/// iterators expose `reference` and `pointer` types that can be converted to 810/// `ValueT &` and `ValueT *` respectively. It doesn't support more 811/// interesting/customized pointer or reference types. 812/// 813/// Currently this only supports forward or higher iterator categories as 814/// inputs and always exposes a forward iterator interface. 815template <typename ValueT, typename... IterTs> 816class concat_iterator 817 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>, 818 std::forward_iterator_tag, ValueT> { 819 using BaseT = typename concat_iterator::iterator_facade_base; 820 821 /// We store both the current and end iterators for each concatenated 822 /// sequence in a tuple of pairs. 823 /// 824 /// Note that something like iterator_range seems nice at first here, but the 825 /// range properties are of little benefit and end up getting in the way 826 /// because we need to do mutation on the current iterators. 827 std::tuple<IterTs...> Begins; 828 std::tuple<IterTs...> Ends; 829 830 /// Attempts to increment a specific iterator. 831 /// 832 /// Returns true if it was able to increment the iterator. Returns false if 833 /// the iterator is already at the end iterator. 834 template <size_t Index> bool incrementHelper() { 835 auto &Begin = std::get<Index>(Begins); 836 auto &End = std::get<Index>(Ends); 837 if (Begin == End) 838 return false; 839 840 ++Begin; 841 return true; 842 } 843 844 /// Increments the first non-end iterator. 845 /// 846 /// It is an error to call this with all iterators at the end. 847 template <size_t... Ns> void increment(std::index_sequence<Ns...>) { 848 // Build a sequence of functions to increment each iterator if possible. 849 bool (concat_iterator::*IncrementHelperFns[])() = { 850 &concat_iterator::incrementHelper<Ns>...}; 851 852 // Loop over them, and stop as soon as we succeed at incrementing one. 853 for (auto &IncrementHelperFn : IncrementHelperFns) 854 if ((this->*IncrementHelperFn)()) 855 return; 856 857 llvm_unreachable("Attempted to increment an end concat iterator!"); 858 } 859 860 /// Returns null if the specified iterator is at the end. Otherwise, 861 /// dereferences the iterator and returns the address of the resulting 862 /// reference. 863 template <size_t Index> ValueT *getHelper() const { 864 auto &Begin = std::get<Index>(Begins); 865 auto &End = std::get<Index>(Ends); 866 if (Begin == End) 867 return nullptr; 868 869 return &*Begin; 870 } 871 872 /// Finds the first non-end iterator, dereferences, and returns the resulting 873 /// reference. 874 /// 875 /// It is an error to call this with all iterators at the end. 876 template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const { 877 // Build a sequence of functions to get from iterator if possible. 878 ValueT *(concat_iterator::*GetHelperFns[])() const = { 879 &concat_iterator::getHelper<Ns>...}; 880 881 // Loop over them, and return the first result we find. 882 for (auto &GetHelperFn : GetHelperFns) 883 if (ValueT *P = (this->*GetHelperFn)()) 884 return *P; 885 886 llvm_unreachable("Attempted to get a pointer from an end concat iterator!"); 887 } 888 889public: 890 /// Constructs an iterator from a squence of ranges. 891 /// 892 /// We need the full range to know how to switch between each of the 893 /// iterators. 894 template <typename... RangeTs> 895 explicit concat_iterator(RangeTs &&... Ranges) 896 : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {} 897 898 using BaseT::operator++; 899 900 concat_iterator &operator++() { 901 increment(std::index_sequence_for<IterTs...>()); 902 return *this; 903 } 904 905 ValueT &operator*() const { 906 return get(std::index_sequence_for<IterTs...>()); 907 } 908 909 bool operator==(const concat_iterator &RHS) const { 910 return Begins == RHS.Begins && Ends == RHS.Ends; 911 } 912}; 913 914namespace detail { 915 916/// Helper to store a sequence of ranges being concatenated and access them. 917/// 918/// This is designed to facilitate providing actual storage when temporaries 919/// are passed into the constructor such that we can use it as part of range 920/// based for loops. 921template <typename ValueT, typename... RangeTs> class concat_range { 922public: 923 using iterator = 924 concat_iterator<ValueT, 925 decltype(std::begin(std::declval<RangeTs &>()))...>; 926 927private: 928 std::tuple<RangeTs...> Ranges; 929 930 template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) { 931 return iterator(std::get<Ns>(Ranges)...); 932 } 933 template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) { 934 return iterator(make_range(std::end(std::get<Ns>(Ranges)), 935 std::end(std::get<Ns>(Ranges)))...); 936 } 937 938public: 939 concat_range(RangeTs &&... Ranges) 940 : Ranges(std::forward<RangeTs>(Ranges)...) {} 941 942 iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); } 943 iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); } 944}; 945 946} // end namespace detail 947 948/// Concatenated range across two or more ranges. 949/// 950/// The desired value type must be explicitly specified. 951template <typename ValueT, typename... RangeTs> 952detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) { 953 static_assert(sizeof...(RangeTs) > 1, 954 "Need more than one range to concatenate!"); 955 return detail::concat_range<ValueT, RangeTs...>( 956 std::forward<RangeTs>(Ranges)...); 957} 958 959//===----------------------------------------------------------------------===// 960// Extra additions to <utility> 961//===----------------------------------------------------------------------===// 962 963/// Function object to check whether the first component of a std::pair 964/// compares less than the first component of another std::pair. 965struct less_first { 966 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 967 return lhs.first < rhs.first; 968 } 969}; 970 971/// Function object to check whether the second component of a std::pair 972/// compares less than the second component of another std::pair. 973struct less_second { 974 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 975 return lhs.second < rhs.second; 976 } 977}; 978 979/// \brief Function object to apply a binary function to the first component of 980/// a std::pair. 981template<typename FuncTy> 982struct on_first { 983 FuncTy func; 984 985 template <typename T> 986 auto operator()(const T &lhs, const T &rhs) const 987 -> decltype(func(lhs.first, rhs.first)) { 988 return func(lhs.first, rhs.first); 989 } 990}; 991 992/// Utility type to build an inheritance chain that makes it easy to rank 993/// overload candidates. 994template <int N> struct rank : rank<N - 1> {}; 995template <> struct rank<0> {}; 996 997/// traits class for checking whether type T is one of any of the given 998/// types in the variadic list. 999template <typename T, typename... Ts> struct is_one_of { 1000 static const bool value = false; 1001}; 1002 1003template <typename T, typename U, typename... Ts> 1004struct is_one_of<T, U, Ts...> { 1005 static const bool value = 1006 std::is_same<T, U>::value || is_one_of<T, Ts...>::value; 1007}; 1008 1009/// traits class for checking whether type T is a base class for all 1010/// the given types in the variadic list. 1011template <typename T, typename... Ts> struct are_base_of { 1012 static const bool value = true; 1013}; 1014 1015template <typename T, typename U, typename... Ts> 1016struct are_base_of<T, U, Ts...> { 1017 static const bool value = 1018 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value; 1019}; 1020 1021//===----------------------------------------------------------------------===// 1022// Extra additions for arrays 1023//===----------------------------------------------------------------------===// 1024 1025/// Find the length of an array. 1026template <class T, std::size_t N> 1027constexpr inline size_t array_lengthof(T (&)[N]) { 1028 return N; 1029} 1030 1031/// Adapt std::less<T> for array_pod_sort. 1032template<typename T> 1033inline int array_pod_sort_comparator(const void *P1, const void *P2) { 1034 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 1035 *reinterpret_cast<const T*>(P2))) 1036 return -1; 1037 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 1038 *reinterpret_cast<const T*>(P1))) 1039 return 1; 1040 return 0; 1041} 1042 1043/// get_array_pod_sort_comparator - This is an internal helper function used to 1044/// get type deduction of T right. 1045template<typename T> 1046inline int (*get_array_pod_sort_comparator(const T &)) 1047 (const void*, const void*) { 1048 return array_pod_sort_comparator<T>; 1049} 1050 1051#ifdef EXPENSIVE_CHECKS 1052namespace detail { 1053 1054inline unsigned presortShuffleEntropy() { 1055 static unsigned Result(std::random_device{}()); 1056 return Result; 1057} 1058 1059template <class IteratorTy> 1060inline void presortShuffle(IteratorTy Start, IteratorTy End) { 1061 std::mt19937 Generator(presortShuffleEntropy()); 1062 std::shuffle(Start, End, Generator); 1063} 1064 1065} // end namespace detail 1066#endif 1067 1068/// array_pod_sort - This sorts an array with the specified start and end 1069/// extent. This is just like std::sort, except that it calls qsort instead of 1070/// using an inlined template. qsort is slightly slower than std::sort, but 1071/// most sorts are not performance critical in LLVM and std::sort has to be 1072/// template instantiated for each type, leading to significant measured code 1073/// bloat. This function should generally be used instead of std::sort where 1074/// possible. 1075/// 1076/// This function assumes that you have simple POD-like types that can be 1077/// compared with std::less and can be moved with memcpy. If this isn't true, 1078/// you should use std::sort. 1079/// 1080/// NOTE: If qsort_r were portable, we could allow a custom comparator and 1081/// default to std::less. 1082template<class IteratorTy> 1083inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 1084 // Don't inefficiently call qsort with one element or trigger undefined 1085 // behavior with an empty sequence. 1086 auto NElts = End - Start; 1087 if (NElts <= 1) return; 1088#ifdef EXPENSIVE_CHECKS 1089 detail::presortShuffle<IteratorTy>(Start, End); 1090#endif 1091 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 1092} 1093 1094template <class IteratorTy> 1095inline void array_pod_sort( 1096 IteratorTy Start, IteratorTy End, 1097 int (*Compare)( 1098 const typename std::iterator_traits<IteratorTy>::value_type *, 1099 const typename std::iterator_traits<IteratorTy>::value_type *)) { 1100 // Don't inefficiently call qsort with one element or trigger undefined 1101 // behavior with an empty sequence. 1102 auto NElts = End - Start; 1103 if (NElts <= 1) return; 1104#ifdef EXPENSIVE_CHECKS 1105 detail::presortShuffle<IteratorTy>(Start, End); 1106#endif 1107 qsort(&*Start, NElts, sizeof(*Start), 1108 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 1109} 1110 1111// Provide wrappers to std::sort which shuffle the elements before sorting 1112// to help uncover non-deterministic behavior (PR35135). 1113template <typename IteratorTy> 1114inline void sort(IteratorTy Start, IteratorTy End) { 1115#ifdef EXPENSIVE_CHECKS 1116 detail::presortShuffle<IteratorTy>(Start, End); 1117#endif 1118 std::sort(Start, End); 1119} 1120 1121template <typename Container> inline void sort(Container &&C) { 1122 llvm::sort(adl_begin(C), adl_end(C)); 1123} 1124 1125template <typename IteratorTy, typename Compare> 1126inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) { 1127#ifdef EXPENSIVE_CHECKS 1128 detail::presortShuffle<IteratorTy>(Start, End); 1129#endif 1130 std::sort(Start, End, Comp); 1131} 1132 1133template <typename Container, typename Compare> 1134inline void sort(Container &&C, Compare Comp) { 1135 llvm::sort(adl_begin(C), adl_end(C), Comp); 1136} 1137 1138//===----------------------------------------------------------------------===// 1139// Extra additions to <algorithm> 1140//===----------------------------------------------------------------------===// 1141 1142/// For a container of pointers, deletes the pointers and then clears the 1143/// container. 1144template<typename Container> 1145void DeleteContainerPointers(Container &C) { 1146 for (auto V : C) 1147 delete V; 1148 C.clear(); 1149} 1150 1151/// In a container of pairs (usually a map) whose second element is a pointer, 1152/// deletes the second elements and then clears the container. 1153template<typename Container> 1154void DeleteContainerSeconds(Container &C) { 1155 for (auto &V : C) 1156 delete V.second; 1157 C.clear(); 1158} 1159 1160/// Get the size of a range. This is a wrapper function around std::distance 1161/// which is only enabled when the operation is O(1). 1162template <typename R> 1163auto size(R &&Range, typename std::enable_if< 1164 std::is_same<typename std::iterator_traits<decltype( 1165 Range.begin())>::iterator_category, 1166 std::random_access_iterator_tag>::value, 1167 void>::type * = nullptr) 1168 -> decltype(std::distance(Range.begin(), Range.end())) { 1169 return std::distance(Range.begin(), Range.end()); 1170} 1171 1172/// Provide wrappers to std::for_each which take ranges instead of having to 1173/// pass begin/end explicitly. 1174template <typename R, typename UnaryPredicate> 1175UnaryPredicate for_each(R &&Range, UnaryPredicate P) { 1176 return std::for_each(adl_begin(Range), adl_end(Range), P); 1177} 1178 1179/// Provide wrappers to std::all_of which take ranges instead of having to pass 1180/// begin/end explicitly. 1181template <typename R, typename UnaryPredicate> 1182bool all_of(R &&Range, UnaryPredicate P) { 1183 return std::all_of(adl_begin(Range), adl_end(Range), P); 1184} 1185 1186/// Provide wrappers to std::any_of which take ranges instead of having to pass 1187/// begin/end explicitly. 1188template <typename R, typename UnaryPredicate> 1189bool any_of(R &&Range, UnaryPredicate P) { 1190 return std::any_of(adl_begin(Range), adl_end(Range), P); 1191} 1192 1193/// Provide wrappers to std::none_of which take ranges instead of having to pass 1194/// begin/end explicitly. 1195template <typename R, typename UnaryPredicate> 1196bool none_of(R &&Range, UnaryPredicate P) { 1197 return std::none_of(adl_begin(Range), adl_end(Range), P); 1198} 1199 1200/// Provide wrappers to std::find which take ranges instead of having to pass 1201/// begin/end explicitly. 1202template <typename R, typename T> 1203auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) { 1204 return std::find(adl_begin(Range), adl_end(Range), Val); 1205} 1206 1207/// Provide wrappers to std::find_if which take ranges instead of having to pass 1208/// begin/end explicitly. 1209template <typename R, typename UnaryPredicate> 1210auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { 1211 return std::find_if(adl_begin(Range), adl_end(Range), P); 1212} 1213 1214template <typename R, typename UnaryPredicate> 1215auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { 1216 return std::find_if_not(adl_begin(Range), adl_end(Range), P); 1217} 1218 1219/// Provide wrappers to std::remove_if which take ranges instead of having to 1220/// pass begin/end explicitly. 1221template <typename R, typename UnaryPredicate> 1222auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { 1223 return std::remove_if(adl_begin(Range), adl_end(Range), P); 1224} 1225 1226/// Provide wrappers to std::copy_if which take ranges instead of having to 1227/// pass begin/end explicitly. 1228template <typename R, typename OutputIt, typename UnaryPredicate> 1229OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { 1230 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P); 1231} 1232 1233template <typename R, typename OutputIt> 1234OutputIt copy(R &&Range, OutputIt Out) { 1235 return std::copy(adl_begin(Range), adl_end(Range), Out); 1236} 1237 1238/// Wrapper function around std::find to detect if an element exists 1239/// in a container. 1240template <typename R, typename E> 1241bool is_contained(R &&Range, const E &Element) { 1242 return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range); 1243} 1244 1245/// Wrapper function around std::count to count the number of times an element 1246/// \p Element occurs in the given range \p Range. 1247template <typename R, typename E> 1248auto count(R &&Range, const E &Element) -> 1249 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type { 1250 return std::count(adl_begin(Range), adl_end(Range), Element); 1251} 1252 1253/// Wrapper function around std::count_if to count the number of times an 1254/// element satisfying a given predicate occurs in a range. 1255template <typename R, typename UnaryPredicate> 1256auto count_if(R &&Range, UnaryPredicate P) -> 1257 typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type { 1258 return std::count_if(adl_begin(Range), adl_end(Range), P); 1259} 1260 1261/// Wrapper function around std::transform to apply a function to a range and 1262/// store the result elsewhere. 1263template <typename R, typename OutputIt, typename UnaryPredicate> 1264OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) { 1265 return std::transform(adl_begin(Range), adl_end(Range), d_first, P); 1266} 1267 1268/// Provide wrappers to std::partition which take ranges instead of having to 1269/// pass begin/end explicitly. 1270template <typename R, typename UnaryPredicate> 1271auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { 1272 return std::partition(adl_begin(Range), adl_end(Range), P); 1273} 1274 1275/// Provide wrappers to std::lower_bound which take ranges instead of having to 1276/// pass begin/end explicitly. 1277template <typename R, typename T> 1278auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) { 1279 return std::lower_bound(adl_begin(Range), adl_end(Range), 1280 std::forward<T>(Value)); 1281} 1282 1283template <typename R, typename T, typename Compare> 1284auto lower_bound(R &&Range, T &&Value, Compare C) 1285 -> decltype(adl_begin(Range)) { 1286 return std::lower_bound(adl_begin(Range), adl_end(Range), 1287 std::forward<T>(Value), C); 1288} 1289 1290/// Provide wrappers to std::upper_bound which take ranges instead of having to 1291/// pass begin/end explicitly. 1292template <typename R, typename T> 1293auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) { 1294 return std::upper_bound(adl_begin(Range), adl_end(Range), 1295 std::forward<T>(Value)); 1296} 1297 1298template <typename R, typename T, typename Compare> 1299auto upper_bound(R &&Range, T &&Value, Compare C) 1300 -> decltype(adl_begin(Range)) { 1301 return std::upper_bound(adl_begin(Range), adl_end(Range), 1302 std::forward<T>(Value), C); 1303} 1304 1305template <typename R> 1306void stable_sort(R &&Range) { 1307 std::stable_sort(adl_begin(Range), adl_end(Range)); 1308} 1309 1310template <typename R, typename Compare> 1311void stable_sort(R &&Range, Compare C) { 1312 std::stable_sort(adl_begin(Range), adl_end(Range), C); 1313} 1314 1315/// Binary search for the first iterator in a range where a predicate is false. 1316/// Requires that C is always true below some limit, and always false above it. 1317template <typename R, typename Predicate, 1318 typename Val = decltype(*adl_begin(std::declval<R>()))> 1319auto partition_point(R &&Range, Predicate P) -> decltype(adl_begin(Range)) { 1320 return std::partition_point(adl_begin(Range), adl_end(Range), P); 1321} 1322 1323/// Wrapper function around std::equal to detect if all elements 1324/// in a container are same. 1325template <typename R> 1326bool is_splat(R &&Range) { 1327 size_t range_size = size(Range); 1328 return range_size != 0 && (range_size == 1 || 1329 std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range))); 1330} 1331 1332/// Provide a container algorithm similar to C++ Library Fundamentals v2's 1333/// `erase_if` which is equivalent to: 1334/// 1335/// C.erase(remove_if(C, pred), C.end()); 1336/// 1337/// This version works for any container with an erase method call accepting 1338/// two iterators. 1339template <typename Container, typename UnaryPredicate> 1340void erase_if(Container &C, UnaryPredicate P) { 1341 C.erase(remove_if(C, P), C.end()); 1342} 1343 1344/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with 1345/// the range [ValIt, ValEnd) (which is not from the same container). 1346template<typename Container, typename RandomAccessIterator> 1347void replace(Container &Cont, typename Container::iterator ContIt, 1348 typename Container::iterator ContEnd, RandomAccessIterator ValIt, 1349 RandomAccessIterator ValEnd) { 1350 while (true) { 1351 if (ValIt == ValEnd) { 1352 Cont.erase(ContIt, ContEnd); 1353 return; 1354 } else if (ContIt == ContEnd) { 1355 Cont.insert(ContIt, ValIt, ValEnd); 1356 return; 1357 } 1358 *ContIt++ = *ValIt++; 1359 } 1360} 1361 1362/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with 1363/// the range R. 1364template<typename Container, typename Range = std::initializer_list< 1365 typename Container::value_type>> 1366void replace(Container &Cont, typename Container::iterator ContIt, 1367 typename Container::iterator ContEnd, Range R) { 1368 replace(Cont, ContIt, ContEnd, R.begin(), R.end()); 1369} 1370 1371//===----------------------------------------------------------------------===// 1372// Extra additions to <memory> 1373//===----------------------------------------------------------------------===// 1374 1375struct FreeDeleter { 1376 void operator()(void* v) { 1377 ::free(v); 1378 } 1379}; 1380 1381template<typename First, typename Second> 1382struct pair_hash { 1383 size_t operator()(const std::pair<First, Second> &P) const { 1384 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 1385 } 1386}; 1387 1388/// Binary functor that adapts to any other binary functor after dereferencing 1389/// operands. 1390template <typename T> struct deref { 1391 T func; 1392 1393 // Could be further improved to cope with non-derivable functors and 1394 // non-binary functors (should be a variadic template member function 1395 // operator()). 1396 template <typename A, typename B> 1397 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 1398 assert(lhs); 1399 assert(rhs); 1400 return func(*lhs, *rhs); 1401 } 1402}; 1403 1404namespace detail { 1405 1406template <typename R> class enumerator_iter; 1407 1408template <typename R> struct result_pair { 1409 using value_reference = 1410 typename std::iterator_traits<IterOfRange<R>>::reference; 1411 1412 friend class enumerator_iter<R>; 1413 1414 result_pair() = default; 1415 result_pair(std::size_t Index, IterOfRange<R> Iter) 1416 : Index(Index), Iter(Iter) {} 1417 1418 result_pair<R>(const result_pair<R> &Other) 1419 : Index(Other.Index), Iter(Other.Iter) {} 1420 result_pair<R> &operator=(const result_pair<R> &Other) { 1421 Index = Other.Index; 1422 Iter = Other.Iter; 1423 return *this; 1424 } 1425 1426 std::size_t index() const { return Index; } 1427 const value_reference value() const { return *Iter; } 1428 value_reference value() { return *Iter; } 1429 1430private: 1431 std::size_t Index = std::numeric_limits<std::size_t>::max(); 1432 IterOfRange<R> Iter; 1433}; 1434 1435template <typename R> 1436class enumerator_iter 1437 : public iterator_facade_base< 1438 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>, 1439 typename std::iterator_traits<IterOfRange<R>>::difference_type, 1440 typename std::iterator_traits<IterOfRange<R>>::pointer, 1441 typename std::iterator_traits<IterOfRange<R>>::reference> { 1442 using result_type = result_pair<R>; 1443 1444public: 1445 explicit enumerator_iter(IterOfRange<R> EndIter) 1446 : Result(std::numeric_limits<size_t>::max(), EndIter) {} 1447 1448 enumerator_iter(std::size_t Index, IterOfRange<R> Iter) 1449 : Result(Index, Iter) {} 1450 1451 result_type &operator*() { return Result; } 1452 const result_type &operator*() const { return Result; } 1453 1454 enumerator_iter<R> &operator++() { 1455 assert(Result.Index != std::numeric_limits<size_t>::max()); 1456 ++Result.Iter; 1457 ++Result.Index; 1458 return *this; 1459 } 1460 1461 bool operator==(const enumerator_iter<R> &RHS) const { 1462 // Don't compare indices here, only iterators. It's possible for an end 1463 // iterator to have different indices depending on whether it was created 1464 // by calling std::end() versus incrementing a valid iterator. 1465 return Result.Iter == RHS.Result.Iter; 1466 } 1467 1468 enumerator_iter<R>(const enumerator_iter<R> &Other) : Result(Other.Result) {} 1469 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) { 1470 Result = Other.Result; 1471 return *this; 1472 } 1473 1474private: 1475 result_type Result; 1476}; 1477 1478template <typename R> class enumerator { 1479public: 1480 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {} 1481 1482 enumerator_iter<R> begin() { 1483 return enumerator_iter<R>(0, std::begin(TheRange)); 1484 } 1485 1486 enumerator_iter<R> end() { 1487 return enumerator_iter<R>(std::end(TheRange)); 1488 } 1489 1490private: 1491 R TheRange; 1492}; 1493 1494} // end namespace detail 1495 1496/// Given an input range, returns a new range whose values are are pair (A,B) 1497/// such that A is the 0-based index of the item in the sequence, and B is 1498/// the value from the original sequence. Example: 1499/// 1500/// std::vector<char> Items = {'A', 'B', 'C', 'D'}; 1501/// for (auto X : enumerate(Items)) { 1502/// printf("Item %d - %c\n", X.index(), X.value()); 1503/// } 1504/// 1505/// Output: 1506/// Item 0 - A 1507/// Item 1 - B 1508/// Item 2 - C 1509/// Item 3 - D 1510/// 1511template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { 1512 return detail::enumerator<R>(std::forward<R>(TheRange)); 1513} 1514 1515namespace detail { 1516 1517template <typename F, typename Tuple, std::size_t... I> 1518auto apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence<I...>) 1519 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) { 1520 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...); 1521} 1522 1523} // end namespace detail 1524 1525/// Given an input tuple (a1, a2, ..., an), pass the arguments of the 1526/// tuple variadically to f as if by calling f(a1, a2, ..., an) and 1527/// return the result. 1528template <typename F, typename Tuple> 1529auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl( 1530 std::forward<F>(f), std::forward<Tuple>(t), 1531 std::make_index_sequence< 1532 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { 1533 using Indices = std::make_index_sequence< 1534 std::tuple_size<typename std::decay<Tuple>::type>::value>; 1535 1536 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t), 1537 Indices{}); 1538} 1539 1540/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N) 1541/// time. Not meant for use with random-access iterators. 1542template <typename IterTy> 1543bool hasNItems( 1544 IterTy &&Begin, IterTy &&End, unsigned N, 1545 typename std::enable_if< 1546 !std::is_same< 1547 typename std::iterator_traits<typename std::remove_reference< 1548 decltype(Begin)>::type>::iterator_category, 1549 std::random_access_iterator_tag>::value, 1550 void>::type * = nullptr) { 1551 for (; N; --N, ++Begin) 1552 if (Begin == End) 1553 return false; // Too few. 1554 return Begin == End; 1555} 1556 1557/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N) 1558/// time. Not meant for use with random-access iterators. 1559template <typename IterTy> 1560bool hasNItemsOrMore( 1561 IterTy &&Begin, IterTy &&End, unsigned N, 1562 typename std::enable_if< 1563 !std::is_same< 1564 typename std::iterator_traits<typename std::remove_reference< 1565 decltype(Begin)>::type>::iterator_category, 1566 std::random_access_iterator_tag>::value, 1567 void>::type * = nullptr) { 1568 for (; N; --N, ++Begin) 1569 if (Begin == End) 1570 return false; // Too few. 1571 return true; 1572} 1573 1574/// Returns a raw pointer that represents the same address as the argument. 1575/// 1576/// The late bound return should be removed once we move to C++14 to better 1577/// align with the C++20 declaration. Also, this implementation can be removed 1578/// once we move to C++20 where it's defined as std::to_addres() 1579/// 1580/// The std::pointer_traits<>::to_address(p) variations of these overloads has 1581/// not been implemented. 1582template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) { 1583 return P.operator->(); 1584} 1585template <class T> constexpr T *to_address(T *P) { return P; } 1586 1587} // end namespace llvm 1588 1589#endif // LLVM_ADT_STLEXTRAS_H 1590