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