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 42 namespace 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. 46 template <typename T, T> struct SameType; 47 48 namespace detail { 49 50 template <typename RangeT> 51 using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 52 53 } // end namespace detail 54 55 //===----------------------------------------------------------------------===// 56 // Extra additions to <type_traits> 57 //===----------------------------------------------------------------------===// 58 59 template <typename T> 60 struct negation : std::integral_constant<bool, !bool(T::value)> {}; 61 62 template <typename...> struct conjunction : std::true_type {}; 63 template <typename B1> struct conjunction<B1> : B1 {}; 64 template <typename B1, typename... Bn> 65 struct conjunction<B1, Bn...> 66 : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {}; 67 68 template <typename T> struct make_const_ptr { 69 using type = 70 typename std::add_pointer<typename std::add_const<T>::type>::type; 71 }; 72 73 template <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 82 template <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. 99 template<typename Fn> class function_ref; 100 101 template<typename Ret, typename ...Params> 102 class 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 112 public: 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>); 135 template <class T> 136 inline void deleter(T *Ptr) { 137 delete Ptr; 138 } 139 140 //===----------------------------------------------------------------------===// 141 // Extra additions to <iterator> 142 //===----------------------------------------------------------------------===// 143 144 namespace adl_detail { 145 146 using std::begin; 147 148 template <typename ContainerTy> 149 auto adl_begin(ContainerTy &&container) 150 -> decltype(begin(std::forward<ContainerTy>(container))) { 151 return begin(std::forward<ContainerTy>(container)); 152 } 153 154 using std::end; 155 156 template <typename ContainerTy> 157 auto adl_end(ContainerTy &&container) 158 -> decltype(end(std::forward<ContainerTy>(container))) { 159 return end(std::forward<ContainerTy>(container)); 160 } 161 162 using std::swap; 163 164 template <typename T> 165 void 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 172 template <typename ContainerTy> 173 auto 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 178 template <typename ContainerTy> 179 auto 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 184 template <typename T> 185 void 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. 191 template <typename T> 192 constexpr 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. 198 template <typename T> 199 auto 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 208 template <typename ItTy, typename FuncTy, 209 typename FuncReturnTy = 210 decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))> 211 class 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> { 216 public: 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 224 private: 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... 230 template <class ItTy, class FuncTy> 231 inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) { 232 return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F)); 233 } 234 235 template <class ContainerTy, class FuncTy> 236 auto 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(). 243 template <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 253 public: 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(). 258 template <typename Ty> 259 struct 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. 264 template <typename ContainerTy> 265 auto 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. 272 template <typename IteratorTy> 273 std::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. 280 template <typename ContainerTy> 281 auto 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. 306 template <typename WrappedIteratorT, typename PredicateT, typename IterTag> 307 class 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 321 protected: 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 339 public: 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. 350 template <typename WrappedIteratorT, typename PredicateT, 351 typename IterTag = std::forward_iterator_tag> 352 class filter_iterator_impl 353 : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> { 354 using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>; 355 356 public: 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. 363 template <typename WrappedIteratorT, typename PredicateT> 364 class 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 375 public: 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 389 namespace detail { 390 391 template <bool is_bidirectional> struct fwd_or_bidi_tag_impl { 392 using type = std::forward_iterator_tag; 393 }; 394 395 template <> 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. 402 template <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. 412 template <typename WrappedIteratorT, typename PredicateT> 413 using 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. 424 template <typename RangeT, typename PredicateT> 425 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 426 make_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. 453 template <typename WrappedIteratorT> 454 class 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 463 protected: 464 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 465 bool IsEarlyIncremented = false; 466 #endif 467 468 public: 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. 510 template <typename RangeT> 511 iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>> 512 make_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 520 template <typename R, typename UnaryPredicate> 521 bool all_of(R &&range, UnaryPredicate P); 522 template <typename R, typename UnaryPredicate> 523 bool any_of(R &&range, UnaryPredicate P); 524 525 namespace detail { 526 527 using 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. 531 template<typename... Iters> struct ZipTupleType { 532 using type = std::tuple<decltype(*declval<Iters>())...>; 533 }; 534 535 template <typename ZipType, typename... Iters> 536 using 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 551 template <typename ZipType, typename... Iters> 552 struct 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 558 protected: 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 573 public: 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 595 template <typename... Iters> 596 struct 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 606 template <typename... Iters> 607 class 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 616 public: 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 626 template <template <typename...> class ItType, typename... Args> class zippy { 627 public: 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 635 private: 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 646 public: 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. 658 template <typename T, typename U, typename... Args> 659 detail::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. 667 template <typename T, typename U, typename... Args> 668 detail::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 674 namespace detail { 675 template <typename Iter> 676 static Iter next_or_end(const Iter &I, const Iter &End) { 677 if (I == End) 678 return End; 679 return std::next(I); 680 } 681 682 template <typename Iter> 683 static 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 691 template <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 697 template <typename... Iters> struct ZipLongestTupleType { 698 using type = std::tuple<typename ZipLongestItemType<Iters>::type...>; 699 }; 700 701 template <typename... Iters> 702 class 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> { 713 public: 714 using value_type = typename ZipLongestTupleType<Iters...>::type; 715 716 private: 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 740 public: 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 761 template <typename... Args> class zip_longest_range { 762 public: 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 771 private: 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 785 public: 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. 798 template <typename T, typename U, typename... Args> 799 detail::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. 815 template <typename ValueT, typename... IterTs> 816 class 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 889 public: 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 914 namespace 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. 921 template <typename ValueT, typename... RangeTs> class concat_range { 922 public: 923 using iterator = 924 concat_iterator<ValueT, 925 decltype(std::begin(std::declval<RangeTs &>()))...>; 926 927 private: 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 938 public: 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. 951 template <typename ValueT, typename... RangeTs> 952 detail::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. 965 struct 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. 973 struct 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. 981 template<typename FuncTy> 982 struct 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. 994 template <int N> struct rank : rank<N - 1> {}; 995 template <> 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. 999 template <typename T, typename... Ts> struct is_one_of { 1000 static const bool value = false; 1001 }; 1002 1003 template <typename T, typename U, typename... Ts> 1004 struct 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. 1011 template <typename T, typename... Ts> struct are_base_of { 1012 static const bool value = true; 1013 }; 1014 1015 template <typename T, typename U, typename... Ts> 1016 struct 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. 1026 template <class T, std::size_t N> 1027 constexpr inline size_t array_lengthof(T (&)[N]) { 1028 return N; 1029 } 1030 1031 /// Adapt std::less<T> for array_pod_sort. 1032 template<typename T> 1033 inline 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. 1045 template<typename T> 1046 inline 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 1052 namespace detail { 1053 1054 inline unsigned presortShuffleEntropy() { 1055 static unsigned Result(std::random_device{}()); 1056 return Result; 1057 } 1058 1059 template <class IteratorTy> 1060 inline 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. 1082 template<class IteratorTy> 1083 inline 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 1094 template <class IteratorTy> 1095 inline 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). 1113 template <typename IteratorTy> 1114 inline 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 1121 template <typename Container> inline void sort(Container &&C) { 1122 llvm::sort(adl_begin(C), adl_end(C)); 1123 } 1124 1125 template <typename IteratorTy, typename Compare> 1126 inline 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 1133 template <typename Container, typename Compare> 1134 inline 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. 1144 template<typename Container> 1145 void 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. 1153 template<typename Container> 1154 void 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). 1162 template <typename R> 1163 auto 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. 1174 template <typename R, typename UnaryPredicate> 1175 UnaryPredicate 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. 1181 template <typename R, typename UnaryPredicate> 1182 bool 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. 1188 template <typename R, typename UnaryPredicate> 1189 bool 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. 1195 template <typename R, typename UnaryPredicate> 1196 bool 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. 1202 template <typename R, typename T> 1203 auto 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. 1209 template <typename R, typename UnaryPredicate> 1210 auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) { 1211 return std::find_if(adl_begin(Range), adl_end(Range), P); 1212 } 1213 1214 template <typename R, typename UnaryPredicate> 1215 auto 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. 1221 template <typename R, typename UnaryPredicate> 1222 auto 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. 1228 template <typename R, typename OutputIt, typename UnaryPredicate> 1229 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { 1230 return std::copy_if(adl_begin(Range), adl_end(Range), Out, P); 1231 } 1232 1233 template <typename R, typename OutputIt> 1234 OutputIt 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. 1240 template <typename R, typename E> 1241 bool 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. 1247 template <typename R, typename E> 1248 auto 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. 1255 template <typename R, typename UnaryPredicate> 1256 auto 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. 1263 template <typename R, typename OutputIt, typename UnaryPredicate> 1264 OutputIt 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. 1270 template <typename R, typename UnaryPredicate> 1271 auto 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. 1277 template <typename R, typename T> 1278 auto 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 1283 template <typename R, typename T, typename Compare> 1284 auto 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. 1292 template <typename R, typename T> 1293 auto 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 1298 template <typename R, typename T, typename Compare> 1299 auto 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 1305 template <typename R> 1306 void stable_sort(R &&Range) { 1307 std::stable_sort(adl_begin(Range), adl_end(Range)); 1308 } 1309 1310 template <typename R, typename Compare> 1311 void 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. 1317 template <typename R, typename Predicate, 1318 typename Val = decltype(*adl_begin(std::declval<R>()))> 1319 auto 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. 1325 template <typename R> 1326 bool 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. 1339 template <typename Container, typename UnaryPredicate> 1340 void 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). 1346 template<typename Container, typename RandomAccessIterator> 1347 void 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. 1364 template<typename Container, typename Range = std::initializer_list< 1365 typename Container::value_type>> 1366 void 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 1375 struct FreeDeleter { 1376 void operator()(void* v) { 1377 ::free(v); 1378 } 1379 }; 1380 1381 template<typename First, typename Second> 1382 struct 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. 1390 template <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 1404 namespace detail { 1405 1406 template <typename R> class enumerator_iter; 1407 1408 template <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 1430 private: 1431 std::size_t Index = std::numeric_limits<std::size_t>::max(); 1432 IterOfRange<R> Iter; 1433 }; 1434 1435 template <typename R> 1436 class 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 1444 public: 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 1474 private: 1475 result_type Result; 1476 }; 1477 1478 template <typename R> class enumerator { 1479 public: 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 1490 private: 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 /// 1511 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { 1512 return detail::enumerator<R>(std::forward<R>(TheRange)); 1513 } 1514 1515 namespace detail { 1516 1517 template <typename F, typename Tuple, std::size_t... I> 1518 auto 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. 1528 template <typename F, typename Tuple> 1529 auto 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. 1542 template <typename IterTy> 1543 bool 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. 1559 template <typename IterTy> 1560 bool 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. 1582 template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) { 1583 return P.operator->(); 1584 } 1585 template <class T> constexpr T *to_address(T *P) { return P; } 1586 1587 } // end namespace llvm 1588 1589 #endif // LLVM_ADT_STLEXTRAS_H 1590