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