1 //===- llvm/ADT/STLExtras.h - Useful STL related functions ------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains some templates that are useful if you are working with the 11 // STL at all. 12 // 13 // No library is required when using these functions. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #ifndef LLVM_ADT_STLEXTRAS_H 18 #define LLVM_ADT_STLEXTRAS_H 19 20 #include <algorithm> // for std::all_of 21 #include <cassert> 22 #include <cstddef> // for std::size_t 23 #include <cstdlib> // for qsort 24 #include <functional> 25 #include <iterator> 26 #include <limits> 27 #include <memory> 28 #include <tuple> 29 #include <utility> // for std::pair 30 31 #include "llvm/ADT/Optional.h" 32 #include "llvm/ADT/SmallVector.h" 33 #include "llvm/ADT/iterator.h" 34 #include "llvm/ADT/iterator_range.h" 35 #include "llvm/Support/Compiler.h" 36 #include "llvm/Support/ErrorHandling.h" 37 38 namespace llvm { 39 40 // Only used by compiler if both template types are the same. Useful when 41 // using SFINAE to test for the existence of member functions. 42 template <typename T, T> struct SameType; 43 44 namespace detail { 45 46 template <typename RangeT> 47 using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 48 49 template <typename RangeT> 50 using ValueOfRange = typename std::remove_reference<decltype( 51 *std::begin(std::declval<RangeT &>()))>::type; 52 53 } // End detail namespace 54 55 //===----------------------------------------------------------------------===// 56 // Extra additions to <functional> 57 //===----------------------------------------------------------------------===// 58 59 template <class Ty> struct identity { 60 using argument_type = Ty; 61 Ty &operator()(Ty &self) const { 62 return self; 63 } 64 const Ty &operator()(const Ty &self) const { 65 return self; 66 } 67 }; 68 69 template <class Ty> struct less_ptr { 70 bool operator()(const Ty* left, const Ty* right) const { 71 return *left < *right; 72 } 73 }; 74 75 template <class Ty> struct greater_ptr { 76 bool operator()(const Ty* left, const Ty* right) const { 77 return *right < *left; 78 } 79 }; 80 81 /// An efficient, type-erasing, non-owning reference to a callable. This is 82 /// intended for use as the type of a function parameter that is not used 83 /// after the function in question returns. 84 /// 85 /// This class does not own the callable, so it is not in general safe to store 86 /// a function_ref. 87 template<typename Fn> class function_ref; 88 89 template<typename Ret, typename ...Params> 90 class function_ref<Ret(Params...)> { 91 Ret (*callback)(intptr_t callable, Params ...params); 92 intptr_t callable; 93 94 template<typename Callable> 95 static Ret callback_fn(intptr_t callable, Params ...params) { 96 return (*reinterpret_cast<Callable*>(callable))( 97 std::forward<Params>(params)...); 98 } 99 100 public: 101 function_ref() : callback(nullptr) {} 102 103 template <typename Callable> 104 function_ref(Callable &&callable, 105 typename std::enable_if< 106 !std::is_same<typename std::remove_reference<Callable>::type, 107 function_ref>::value>::type * = nullptr) 108 : callback(callback_fn<typename std::remove_reference<Callable>::type>), 109 callable(reinterpret_cast<intptr_t>(&callable)) {} 110 Ret operator()(Params ...params) const { 111 return callback(callable, std::forward<Params>(params)...); 112 } 113 114 operator bool() const { return callback; } 115 }; 116 117 // deleter - Very very very simple method that is used to invoke operator 118 // delete on something. It is used like this: 119 // 120 // for_each(V.begin(), B.end(), deleter<Interval>); 121 // 122 template <class T> 123 inline void deleter(T *Ptr) { 124 delete Ptr; 125 } 126 127 128 129 //===----------------------------------------------------------------------===// 130 // Extra additions to <iterator> 131 //===----------------------------------------------------------------------===// 132 133 // mapped_iterator - This is a simple iterator adapter that causes a function to 134 // be applied whenever operator* is invoked on the iterator. 135 // 136 template <class RootIt, class UnaryFunc> 137 class mapped_iterator { 138 RootIt current; 139 UnaryFunc Fn; 140 public: 141 typedef typename std::iterator_traits<RootIt>::iterator_category 142 iterator_category; 143 typedef typename std::iterator_traits<RootIt>::difference_type 144 difference_type; 145 typedef decltype(std::declval<UnaryFunc>()(*std::declval<RootIt>())) 146 value_type; 147 148 typedef void pointer; 149 //typedef typename UnaryFunc::result_type *pointer; 150 typedef void reference; // Can't modify value returned by fn 151 152 typedef RootIt iterator_type; 153 154 inline const RootIt &getCurrent() const { return current; } 155 inline const UnaryFunc &getFunc() const { return Fn; } 156 157 inline explicit mapped_iterator(const RootIt &I, UnaryFunc F) 158 : current(I), Fn(F) {} 159 160 inline value_type operator*() const { // All this work to do this 161 return Fn(*current); // little change 162 } 163 164 mapped_iterator &operator++() { 165 ++current; 166 return *this; 167 } 168 mapped_iterator &operator--() { 169 --current; 170 return *this; 171 } 172 mapped_iterator operator++(int) { 173 mapped_iterator __tmp = *this; 174 ++current; 175 return __tmp; 176 } 177 mapped_iterator operator--(int) { 178 mapped_iterator __tmp = *this; 179 --current; 180 return __tmp; 181 } 182 mapped_iterator operator+(difference_type n) const { 183 return mapped_iterator(current + n, Fn); 184 } 185 mapped_iterator &operator+=(difference_type n) { 186 current += n; 187 return *this; 188 } 189 mapped_iterator operator-(difference_type n) const { 190 return mapped_iterator(current - n, Fn); 191 } 192 mapped_iterator &operator-=(difference_type n) { 193 current -= n; 194 return *this; 195 } 196 reference operator[](difference_type n) const { return *(*this + n); } 197 198 bool operator!=(const mapped_iterator &X) const { return !operator==(X); } 199 bool operator==(const mapped_iterator &X) const { 200 return current == X.current; 201 } 202 bool operator<(const mapped_iterator &X) const { return current < X.current; } 203 204 difference_type operator-(const mapped_iterator &X) const { 205 return current - X.current; 206 } 207 }; 208 209 template <class Iterator, class Func> 210 inline mapped_iterator<Iterator, Func> 211 operator+(typename mapped_iterator<Iterator, Func>::difference_type N, 212 const mapped_iterator<Iterator, Func> &X) { 213 return mapped_iterator<Iterator, Func>(X.getCurrent() - N, X.getFunc()); 214 } 215 216 217 // map_iterator - Provide a convenient way to create mapped_iterators, just like 218 // make_pair is useful for creating pairs... 219 // 220 template <class ItTy, class FuncTy> 221 inline mapped_iterator<ItTy, FuncTy> map_iterator(const ItTy &I, FuncTy F) { 222 return mapped_iterator<ItTy, FuncTy>(I, F); 223 } 224 225 /// Helper to determine if type T has a member called rbegin(). 226 template <typename Ty> class has_rbegin_impl { 227 typedef char yes[1]; 228 typedef char no[2]; 229 230 template <typename Inner> 231 static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr); 232 233 template <typename> 234 static no& test(...); 235 236 public: 237 static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); 238 }; 239 240 /// Metafunction to determine if T& or T has a member called rbegin(). 241 template <typename Ty> 242 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> { 243 }; 244 245 // Returns an iterator_range over the given container which iterates in reverse. 246 // Note that the container must have rbegin()/rend() methods for this to work. 247 template <typename ContainerTy> 248 auto reverse(ContainerTy &&C, 249 typename std::enable_if<has_rbegin<ContainerTy>::value>::type * = 250 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) { 251 return make_range(C.rbegin(), C.rend()); 252 } 253 254 // Returns a std::reverse_iterator wrapped around the given iterator. 255 template <typename IteratorTy> 256 std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) { 257 return std::reverse_iterator<IteratorTy>(It); 258 } 259 260 // Returns an iterator_range over the given container which iterates in reverse. 261 // Note that the container must have begin()/end() methods which return 262 // bidirectional iterators for this to work. 263 template <typename ContainerTy> 264 auto reverse( 265 ContainerTy &&C, 266 typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr) 267 -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)), 268 llvm::make_reverse_iterator(std::begin(C)))) { 269 return make_range(llvm::make_reverse_iterator(std::end(C)), 270 llvm::make_reverse_iterator(std::begin(C))); 271 } 272 273 /// An iterator adaptor that filters the elements of given inner iterators. 274 /// 275 /// The predicate parameter should be a callable object that accepts the wrapped 276 /// iterator's reference type and returns a bool. When incrementing or 277 /// decrementing the iterator, it will call the predicate on each element and 278 /// skip any where it returns false. 279 /// 280 /// \code 281 /// int A[] = { 1, 2, 3, 4 }; 282 /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; }); 283 /// // R contains { 1, 3 }. 284 /// \endcode 285 template <typename WrappedIteratorT, typename PredicateT> 286 class filter_iterator 287 : public iterator_adaptor_base< 288 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 289 typename std::common_type< 290 std::forward_iterator_tag, 291 typename std::iterator_traits< 292 WrappedIteratorT>::iterator_category>::type> { 293 using BaseT = iterator_adaptor_base< 294 filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT, 295 typename std::common_type< 296 std::forward_iterator_tag, 297 typename std::iterator_traits<WrappedIteratorT>::iterator_category>:: 298 type>; 299 300 struct PayloadType { 301 WrappedIteratorT End; 302 PredicateT Pred; 303 }; 304 305 Optional<PayloadType> Payload; 306 307 void findNextValid() { 308 assert(Payload && "Payload should be engaged when findNextValid is called"); 309 while (this->I != Payload->End && !Payload->Pred(*this->I)) 310 BaseT::operator++(); 311 } 312 313 // Construct the begin iterator. The begin iterator requires to know where end 314 // is, so that it can properly stop when it hits end. 315 filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred) 316 : BaseT(std::move(Begin)), 317 Payload(PayloadType{std::move(End), std::move(Pred)}) { 318 findNextValid(); 319 } 320 321 // Construct the end iterator. It's not incrementable, so Payload doesn't 322 // have to be engaged. 323 filter_iterator(WrappedIteratorT End) : BaseT(End) {} 324 325 public: 326 using BaseT::operator++; 327 328 filter_iterator &operator++() { 329 BaseT::operator++(); 330 findNextValid(); 331 return *this; 332 } 333 334 template <typename RT, typename PT> 335 friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>> 336 make_filter_range(RT &&, PT); 337 }; 338 339 /// Convenience function that takes a range of elements and a predicate, 340 /// and return a new filter_iterator range. 341 /// 342 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the 343 /// lifetime of that temporary is not kept by the returned range object, and the 344 /// temporary is going to be dropped on the floor after the make_iterator_range 345 /// full expression that contains this function call. 346 template <typename RangeT, typename PredicateT> 347 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 348 make_filter_range(RangeT &&Range, PredicateT Pred) { 349 using FilterIteratorT = 350 filter_iterator<detail::IterOfRange<RangeT>, PredicateT>; 351 return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)), 352 std::end(std::forward<RangeT>(Range)), 353 std::move(Pred)), 354 FilterIteratorT(std::end(std::forward<RangeT>(Range)))); 355 } 356 357 // forward declarations required by zip_shortest/zip_first 358 template <typename R, typename UnaryPredicate> 359 bool all_of(R &&range, UnaryPredicate P); 360 361 template <size_t... I> struct index_sequence; 362 363 template <class... Ts> struct index_sequence_for; 364 365 namespace detail { 366 using std::declval; 367 368 // We have to alias this since inlining the actual type at the usage site 369 // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017. 370 template<typename... Iters> struct ZipTupleType { 371 typedef std::tuple<decltype(*declval<Iters>())...> type; 372 }; 373 374 template <typename ZipType, typename... Iters> 375 using zip_traits = iterator_facade_base< 376 ZipType, typename std::common_type<std::bidirectional_iterator_tag, 377 typename std::iterator_traits< 378 Iters>::iterator_category...>::type, 379 // ^ TODO: Implement random access methods. 380 typename ZipTupleType<Iters...>::type, 381 typename std::iterator_traits<typename std::tuple_element< 382 0, std::tuple<Iters...>>::type>::difference_type, 383 // ^ FIXME: This follows boost::make_zip_iterator's assumption that all 384 // inner iterators have the same difference_type. It would fail if, for 385 // instance, the second field's difference_type were non-numeric while the 386 // first is. 387 typename ZipTupleType<Iters...>::type *, 388 typename ZipTupleType<Iters...>::type>; 389 390 template <typename ZipType, typename... Iters> 391 struct zip_common : public zip_traits<ZipType, Iters...> { 392 using Base = zip_traits<ZipType, Iters...>; 393 using value_type = typename Base::value_type; 394 395 std::tuple<Iters...> iterators; 396 397 protected: 398 template <size_t... Ns> value_type deref(index_sequence<Ns...>) const { 399 return value_type(*std::get<Ns>(iterators)...); 400 } 401 402 template <size_t... Ns> 403 decltype(iterators) tup_inc(index_sequence<Ns...>) const { 404 return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...); 405 } 406 407 template <size_t... Ns> 408 decltype(iterators) tup_dec(index_sequence<Ns...>) const { 409 return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...); 410 } 411 412 public: 413 zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {} 414 415 value_type operator*() { return deref(index_sequence_for<Iters...>{}); } 416 417 const value_type operator*() const { 418 return deref(index_sequence_for<Iters...>{}); 419 } 420 421 ZipType &operator++() { 422 iterators = tup_inc(index_sequence_for<Iters...>{}); 423 return *reinterpret_cast<ZipType *>(this); 424 } 425 426 ZipType &operator--() { 427 static_assert(Base::IsBidirectional, 428 "All inner iterators must be at least bidirectional."); 429 iterators = tup_dec(index_sequence_for<Iters...>{}); 430 return *reinterpret_cast<ZipType *>(this); 431 } 432 }; 433 434 template <typename... Iters> 435 struct zip_first : public zip_common<zip_first<Iters...>, Iters...> { 436 using Base = zip_common<zip_first<Iters...>, Iters...>; 437 438 bool operator==(const zip_first<Iters...> &other) const { 439 return std::get<0>(this->iterators) == std::get<0>(other.iterators); 440 } 441 442 zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} 443 }; 444 445 template <typename... Iters> 446 class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> { 447 template <size_t... Ns> 448 bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const { 449 return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) != 450 std::get<Ns>(other.iterators)...}, 451 identity<bool>{}); 452 } 453 454 public: 455 using Base = zip_common<zip_shortest<Iters...>, Iters...>; 456 457 bool operator==(const zip_shortest<Iters...> &other) const { 458 return !test(other, index_sequence_for<Iters...>{}); 459 } 460 461 zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {} 462 }; 463 464 template <template <typename...> class ItType, typename... Args> class zippy { 465 public: 466 using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>; 467 using iterator_category = typename iterator::iterator_category; 468 using value_type = typename iterator::value_type; 469 using difference_type = typename iterator::difference_type; 470 using pointer = typename iterator::pointer; 471 using reference = typename iterator::reference; 472 473 private: 474 std::tuple<Args...> ts; 475 476 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const { 477 return iterator(std::begin(std::get<Ns>(ts))...); 478 } 479 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const { 480 return iterator(std::end(std::get<Ns>(ts))...); 481 } 482 483 public: 484 iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); } 485 iterator end() const { return end_impl(index_sequence_for<Args...>{}); } 486 zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {} 487 }; 488 } // End detail namespace 489 490 /// zip iterator for two or more iteratable types. 491 template <typename T, typename U, typename... Args> 492 detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u, 493 Args &&... args) { 494 return detail::zippy<detail::zip_shortest, T, U, Args...>( 495 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 496 } 497 498 /// zip iterator that, for the sake of efficiency, assumes the first iteratee to 499 /// be the shortest. 500 template <typename T, typename U, typename... Args> 501 detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u, 502 Args &&... args) { 503 return detail::zippy<detail::zip_first, T, U, Args...>( 504 std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...); 505 } 506 507 /// Iterator wrapper that concatenates sequences together. 508 /// 509 /// This can concatenate different iterators, even with different types, into 510 /// a single iterator provided the value types of all the concatenated 511 /// iterators expose `reference` and `pointer` types that can be converted to 512 /// `ValueT &` and `ValueT *` respectively. It doesn't support more 513 /// interesting/customized pointer or reference types. 514 /// 515 /// Currently this only supports forward or higher iterator categories as 516 /// inputs and always exposes a forward iterator interface. 517 template <typename ValueT, typename... IterTs> 518 class concat_iterator 519 : public iterator_facade_base<concat_iterator<ValueT, IterTs...>, 520 std::forward_iterator_tag, ValueT> { 521 typedef typename concat_iterator::iterator_facade_base BaseT; 522 523 /// We store both the current and end iterators for each concatenated 524 /// sequence in a tuple of pairs. 525 /// 526 /// Note that something like iterator_range seems nice at first here, but the 527 /// range properties are of little benefit and end up getting in the way 528 /// because we need to do mutation on the current iterators. 529 std::tuple<std::pair<IterTs, IterTs>...> IterPairs; 530 531 /// Attempts to increment a specific iterator. 532 /// 533 /// Returns true if it was able to increment the iterator. Returns false if 534 /// the iterator is already at the end iterator. 535 template <size_t Index> bool incrementHelper() { 536 auto &IterPair = std::get<Index>(IterPairs); 537 if (IterPair.first == IterPair.second) 538 return false; 539 540 ++IterPair.first; 541 return true; 542 } 543 544 /// Increments the first non-end iterator. 545 /// 546 /// It is an error to call this with all iterators at the end. 547 template <size_t... Ns> void increment(index_sequence<Ns...>) { 548 // Build a sequence of functions to increment each iterator if possible. 549 bool (concat_iterator::*IncrementHelperFns[])() = { 550 &concat_iterator::incrementHelper<Ns>...}; 551 552 // Loop over them, and stop as soon as we succeed at incrementing one. 553 for (auto &IncrementHelperFn : IncrementHelperFns) 554 if ((this->*IncrementHelperFn)()) 555 return; 556 557 llvm_unreachable("Attempted to increment an end concat iterator!"); 558 } 559 560 /// Returns null if the specified iterator is at the end. Otherwise, 561 /// dereferences the iterator and returns the address of the resulting 562 /// reference. 563 template <size_t Index> ValueT *getHelper() const { 564 auto &IterPair = std::get<Index>(IterPairs); 565 if (IterPair.first == IterPair.second) 566 return nullptr; 567 568 return &*IterPair.first; 569 } 570 571 /// Finds the first non-end iterator, dereferences, and returns the resulting 572 /// reference. 573 /// 574 /// It is an error to call this with all iterators at the end. 575 template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const { 576 // Build a sequence of functions to get from iterator if possible. 577 ValueT *(concat_iterator::*GetHelperFns[])() const = { 578 &concat_iterator::getHelper<Ns>...}; 579 580 // Loop over them, and return the first result we find. 581 for (auto &GetHelperFn : GetHelperFns) 582 if (ValueT *P = (this->*GetHelperFn)()) 583 return *P; 584 585 llvm_unreachable("Attempted to get a pointer from an end concat iterator!"); 586 } 587 588 public: 589 /// Constructs an iterator from a squence of ranges. 590 /// 591 /// We need the full range to know how to switch between each of the 592 /// iterators. 593 template <typename... RangeTs> 594 explicit concat_iterator(RangeTs &&... Ranges) 595 : IterPairs({std::begin(Ranges), std::end(Ranges)}...) {} 596 597 using BaseT::operator++; 598 concat_iterator &operator++() { 599 increment(index_sequence_for<IterTs...>()); 600 return *this; 601 } 602 603 ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); } 604 605 bool operator==(const concat_iterator &RHS) const { 606 return IterPairs == RHS.IterPairs; 607 } 608 }; 609 610 namespace detail { 611 /// Helper to store a sequence of ranges being concatenated and access them. 612 /// 613 /// This is designed to facilitate providing actual storage when temporaries 614 /// are passed into the constructor such that we can use it as part of range 615 /// based for loops. 616 template <typename ValueT, typename... RangeTs> class concat_range { 617 public: 618 typedef concat_iterator<ValueT, 619 decltype(std::begin(std::declval<RangeTs &>()))...> 620 iterator; 621 622 private: 623 std::tuple<RangeTs...> Ranges; 624 625 template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) { 626 return iterator(std::get<Ns>(Ranges)...); 627 } 628 template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) { 629 return iterator(make_range(std::end(std::get<Ns>(Ranges)), 630 std::end(std::get<Ns>(Ranges)))...); 631 } 632 633 public: 634 iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); } 635 iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); } 636 concat_range(RangeTs &&... Ranges) 637 : Ranges(std::forward<RangeTs>(Ranges)...) {} 638 }; 639 } 640 641 /// Concatenated range across two or more ranges. 642 /// 643 /// The desired value type must be explicitly specified. 644 template <typename ValueT, typename... RangeTs> 645 detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) { 646 static_assert(sizeof...(RangeTs) > 1, 647 "Need more than one range to concatenate!"); 648 return detail::concat_range<ValueT, RangeTs...>( 649 std::forward<RangeTs>(Ranges)...); 650 } 651 652 //===----------------------------------------------------------------------===// 653 // Extra additions to <utility> 654 //===----------------------------------------------------------------------===// 655 656 /// \brief Function object to check whether the first component of a std::pair 657 /// compares less than the first component of another std::pair. 658 struct less_first { 659 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 660 return lhs.first < rhs.first; 661 } 662 }; 663 664 /// \brief Function object to check whether the second component of a std::pair 665 /// compares less than the second component of another std::pair. 666 struct less_second { 667 template <typename T> bool operator()(const T &lhs, const T &rhs) const { 668 return lhs.second < rhs.second; 669 } 670 }; 671 672 // A subset of N3658. More stuff can be added as-needed. 673 674 /// \brief Represents a compile-time sequence of integers. 675 template <class T, T... I> struct integer_sequence { 676 typedef T value_type; 677 678 static constexpr size_t size() { return sizeof...(I); } 679 }; 680 681 /// \brief Alias for the common case of a sequence of size_ts. 682 template <size_t... I> 683 struct index_sequence : integer_sequence<std::size_t, I...> {}; 684 685 template <std::size_t N, std::size_t... I> 686 struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 687 template <std::size_t... I> 688 struct build_index_impl<0, I...> : index_sequence<I...> {}; 689 690 /// \brief Creates a compile-time integer sequence for a parameter pack. 691 template <class... Ts> 692 struct index_sequence_for : build_index_impl<sizeof...(Ts)> {}; 693 694 /// Utility type to build an inheritance chain that makes it easy to rank 695 /// overload candidates. 696 template <int N> struct rank : rank<N - 1> {}; 697 template <> struct rank<0> {}; 698 699 /// \brief traits class for checking whether type T is one of any of the given 700 /// types in the variadic list. 701 template <typename T, typename... Ts> struct is_one_of { 702 static const bool value = false; 703 }; 704 705 template <typename T, typename U, typename... Ts> 706 struct is_one_of<T, U, Ts...> { 707 static const bool value = 708 std::is_same<T, U>::value || is_one_of<T, Ts...>::value; 709 }; 710 711 /// \brief traits class for checking whether type T is a base class for all 712 /// the given types in the variadic list. 713 template <typename T, typename... Ts> struct are_base_of { 714 static const bool value = true; 715 }; 716 717 template <typename T, typename U, typename... Ts> 718 struct are_base_of<T, U, Ts...> { 719 static const bool value = 720 std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value; 721 }; 722 723 //===----------------------------------------------------------------------===// 724 // Extra additions for arrays 725 //===----------------------------------------------------------------------===// 726 727 /// Find the length of an array. 728 template <class T, std::size_t N> 729 constexpr inline size_t array_lengthof(T (&)[N]) { 730 return N; 731 } 732 733 /// Adapt std::less<T> for array_pod_sort. 734 template<typename T> 735 inline int array_pod_sort_comparator(const void *P1, const void *P2) { 736 if (std::less<T>()(*reinterpret_cast<const T*>(P1), 737 *reinterpret_cast<const T*>(P2))) 738 return -1; 739 if (std::less<T>()(*reinterpret_cast<const T*>(P2), 740 *reinterpret_cast<const T*>(P1))) 741 return 1; 742 return 0; 743 } 744 745 /// get_array_pod_sort_comparator - This is an internal helper function used to 746 /// get type deduction of T right. 747 template<typename T> 748 inline int (*get_array_pod_sort_comparator(const T &)) 749 (const void*, const void*) { 750 return array_pod_sort_comparator<T>; 751 } 752 753 754 /// array_pod_sort - This sorts an array with the specified start and end 755 /// extent. This is just like std::sort, except that it calls qsort instead of 756 /// using an inlined template. qsort is slightly slower than std::sort, but 757 /// most sorts are not performance critical in LLVM and std::sort has to be 758 /// template instantiated for each type, leading to significant measured code 759 /// bloat. This function should generally be used instead of std::sort where 760 /// possible. 761 /// 762 /// This function assumes that you have simple POD-like types that can be 763 /// compared with std::less and can be moved with memcpy. If this isn't true, 764 /// you should use std::sort. 765 /// 766 /// NOTE: If qsort_r were portable, we could allow a custom comparator and 767 /// default to std::less. 768 template<class IteratorTy> 769 inline void array_pod_sort(IteratorTy Start, IteratorTy End) { 770 // Don't inefficiently call qsort with one element or trigger undefined 771 // behavior with an empty sequence. 772 auto NElts = End - Start; 773 if (NElts <= 1) return; 774 qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start)); 775 } 776 777 template <class IteratorTy> 778 inline void array_pod_sort( 779 IteratorTy Start, IteratorTy End, 780 int (*Compare)( 781 const typename std::iterator_traits<IteratorTy>::value_type *, 782 const typename std::iterator_traits<IteratorTy>::value_type *)) { 783 // Don't inefficiently call qsort with one element or trigger undefined 784 // behavior with an empty sequence. 785 auto NElts = End - Start; 786 if (NElts <= 1) return; 787 qsort(&*Start, NElts, sizeof(*Start), 788 reinterpret_cast<int (*)(const void *, const void *)>(Compare)); 789 } 790 791 //===----------------------------------------------------------------------===// 792 // Extra additions to <algorithm> 793 //===----------------------------------------------------------------------===// 794 795 /// For a container of pointers, deletes the pointers and then clears the 796 /// container. 797 template<typename Container> 798 void DeleteContainerPointers(Container &C) { 799 for (auto V : C) 800 delete V; 801 C.clear(); 802 } 803 804 /// In a container of pairs (usually a map) whose second element is a pointer, 805 /// deletes the second elements and then clears the container. 806 template<typename Container> 807 void DeleteContainerSeconds(Container &C) { 808 for (auto &V : C) 809 delete V.second; 810 C.clear(); 811 } 812 813 /// Provide wrappers to std::all_of which take ranges instead of having to pass 814 /// begin/end explicitly. 815 template <typename R, typename UnaryPredicate> 816 bool all_of(R &&Range, UnaryPredicate P) { 817 return std::all_of(std::begin(Range), std::end(Range), P); 818 } 819 820 /// Provide wrappers to std::any_of which take ranges instead of having to pass 821 /// begin/end explicitly. 822 template <typename R, typename UnaryPredicate> 823 bool any_of(R &&Range, UnaryPredicate P) { 824 return std::any_of(std::begin(Range), std::end(Range), P); 825 } 826 827 /// Provide wrappers to std::none_of which take ranges instead of having to pass 828 /// begin/end explicitly. 829 template <typename R, typename UnaryPredicate> 830 bool none_of(R &&Range, UnaryPredicate P) { 831 return std::none_of(std::begin(Range), std::end(Range), P); 832 } 833 834 /// Provide wrappers to std::find which take ranges instead of having to pass 835 /// begin/end explicitly. 836 template <typename R, typename T> 837 auto find(R &&Range, const T &Val) -> decltype(std::begin(Range)) { 838 return std::find(std::begin(Range), std::end(Range), Val); 839 } 840 841 /// Provide wrappers to std::find_if which take ranges instead of having to pass 842 /// begin/end explicitly. 843 template <typename R, typename UnaryPredicate> 844 auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 845 return std::find_if(std::begin(Range), std::end(Range), P); 846 } 847 848 template <typename R, typename UnaryPredicate> 849 auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 850 return std::find_if_not(std::begin(Range), std::end(Range), P); 851 } 852 853 /// Provide wrappers to std::remove_if which take ranges instead of having to 854 /// pass begin/end explicitly. 855 template <typename R, typename UnaryPredicate> 856 auto remove_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 857 return std::remove_if(std::begin(Range), std::end(Range), P); 858 } 859 860 /// Provide wrappers to std::copy_if which take ranges instead of having to 861 /// pass begin/end explicitly. 862 template <typename R, typename OutputIt, typename UnaryPredicate> 863 OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) { 864 return std::copy_if(std::begin(Range), std::end(Range), Out, P); 865 } 866 867 /// Wrapper function around std::find to detect if an element exists 868 /// in a container. 869 template <typename R, typename E> 870 bool is_contained(R &&Range, const E &Element) { 871 return std::find(std::begin(Range), std::end(Range), Element) != 872 std::end(Range); 873 } 874 875 /// Wrapper function around std::count to count the number of times an element 876 /// \p Element occurs in the given range \p Range. 877 template <typename R, typename E> 878 auto count(R &&Range, const E &Element) -> typename std::iterator_traits< 879 decltype(std::begin(Range))>::difference_type { 880 return std::count(std::begin(Range), std::end(Range), Element); 881 } 882 883 /// Wrapper function around std::count_if to count the number of times an 884 /// element satisfying a given predicate occurs in a range. 885 template <typename R, typename UnaryPredicate> 886 auto count_if(R &&Range, UnaryPredicate P) -> typename std::iterator_traits< 887 decltype(std::begin(Range))>::difference_type { 888 return std::count_if(std::begin(Range), std::end(Range), P); 889 } 890 891 /// Wrapper function around std::transform to apply a function to a range and 892 /// store the result elsewhere. 893 template <typename R, typename OutputIt, typename UnaryPredicate> 894 OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) { 895 return std::transform(std::begin(Range), std::end(Range), d_first, P); 896 } 897 898 /// Provide wrappers to std::partition which take ranges instead of having to 899 /// pass begin/end explicitly. 900 template <typename R, typename UnaryPredicate> 901 auto partition(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 902 return std::partition(std::begin(Range), std::end(Range), P); 903 } 904 905 /// Provide wrappers to std::lower_bound which take ranges instead of having to 906 /// pass begin/end explicitly. 907 template <typename R, typename ForwardIt> 908 auto lower_bound(R &&Range, ForwardIt I) -> decltype(std::begin(Range)) { 909 return std::lower_bound(std::begin(Range), std::end(Range), I); 910 } 911 912 /// \brief Given a range of type R, iterate the entire range and return a 913 /// SmallVector with elements of the vector. This is useful, for example, 914 /// when you want to iterate a range and then sort the results. 915 template <unsigned Size, typename R> 916 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> 917 to_vector(R &&Range) { 918 return {std::begin(Range), std::end(Range)}; 919 } 920 921 /// Provide a container algorithm similar to C++ Library Fundamentals v2's 922 /// `erase_if` which is equivalent to: 923 /// 924 /// C.erase(remove_if(C, pred), C.end()); 925 /// 926 /// This version works for any container with an erase method call accepting 927 /// two iterators. 928 template <typename Container, typename UnaryPredicate> 929 void erase_if(Container &C, UnaryPredicate P) { 930 C.erase(remove_if(C, P), C.end()); 931 } 932 933 //===----------------------------------------------------------------------===// 934 // Extra additions to <memory> 935 //===----------------------------------------------------------------------===// 936 937 // Implement make_unique according to N3656. 938 939 /// \brief Constructs a `new T()` with the given args and returns a 940 /// `unique_ptr<T>` which owns the object. 941 /// 942 /// Example: 943 /// 944 /// auto p = make_unique<int>(); 945 /// auto p = make_unique<std::tuple<int, int>>(0, 1); 946 template <class T, class... Args> 947 typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 948 make_unique(Args &&... args) { 949 return std::unique_ptr<T>(new T(std::forward<Args>(args)...)); 950 } 951 952 /// \brief Constructs a `new T[n]` with the given args and returns a 953 /// `unique_ptr<T[]>` which owns the object. 954 /// 955 /// \param n size of the new array. 956 /// 957 /// Example: 958 /// 959 /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's. 960 template <class T> 961 typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 962 std::unique_ptr<T>>::type 963 make_unique(size_t n) { 964 return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]()); 965 } 966 967 /// This function isn't used and is only here to provide better compile errors. 968 template <class T, class... Args> 969 typename std::enable_if<std::extent<T>::value != 0>::type 970 make_unique(Args &&...) = delete; 971 972 struct FreeDeleter { 973 void operator()(void* v) { 974 ::free(v); 975 } 976 }; 977 978 template<typename First, typename Second> 979 struct pair_hash { 980 size_t operator()(const std::pair<First, Second> &P) const { 981 return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second); 982 } 983 }; 984 985 /// A functor like C++14's std::less<void> in its absence. 986 struct less { 987 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 988 return std::forward<A>(a) < std::forward<B>(b); 989 } 990 }; 991 992 /// A functor like C++14's std::equal<void> in its absence. 993 struct equal { 994 template <typename A, typename B> bool operator()(A &&a, B &&b) const { 995 return std::forward<A>(a) == std::forward<B>(b); 996 } 997 }; 998 999 /// Binary functor that adapts to any other binary functor after dereferencing 1000 /// operands. 1001 template <typename T> struct deref { 1002 T func; 1003 // Could be further improved to cope with non-derivable functors and 1004 // non-binary functors (should be a variadic template member function 1005 // operator()). 1006 template <typename A, typename B> 1007 auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) { 1008 assert(lhs); 1009 assert(rhs); 1010 return func(*lhs, *rhs); 1011 } 1012 }; 1013 1014 namespace detail { 1015 template <typename R> class enumerator_iter; 1016 1017 template <typename R> struct result_pair { 1018 friend class enumerator_iter<R>; 1019 1020 result_pair() : Index(-1) {} 1021 result_pair(std::size_t Index, IterOfRange<R> Iter) 1022 : Index(Index), Iter(Iter) {} 1023 1024 result_pair<R> &operator=(const result_pair<R> &Other) { 1025 Index = Other.Index; 1026 Iter = Other.Iter; 1027 return *this; 1028 } 1029 1030 std::size_t index() const { return Index; } 1031 const ValueOfRange<R> &value() const { return *Iter; } 1032 ValueOfRange<R> &value() { return *Iter; } 1033 1034 private: 1035 std::size_t Index; 1036 IterOfRange<R> Iter; 1037 }; 1038 1039 template <typename R> 1040 class enumerator_iter 1041 : public iterator_facade_base< 1042 enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>, 1043 typename std::iterator_traits<IterOfRange<R>>::difference_type, 1044 typename std::iterator_traits<IterOfRange<R>>::pointer, 1045 typename std::iterator_traits<IterOfRange<R>>::reference> { 1046 using result_type = result_pair<R>; 1047 1048 public: 1049 explicit enumerator_iter(IterOfRange<R> EndIter) 1050 : Result(std::numeric_limits<size_t>::max(), EndIter) { } 1051 1052 enumerator_iter(std::size_t Index, IterOfRange<R> Iter) 1053 : Result(Index, Iter) {} 1054 1055 result_type &operator*() { return Result; } 1056 const result_type &operator*() const { return Result; } 1057 1058 enumerator_iter<R> &operator++() { 1059 assert(Result.Index != std::numeric_limits<size_t>::max()); 1060 ++Result.Iter; 1061 ++Result.Index; 1062 return *this; 1063 } 1064 1065 bool operator==(const enumerator_iter<R> &RHS) const { 1066 // Don't compare indices here, only iterators. It's possible for an end 1067 // iterator to have different indices depending on whether it was created 1068 // by calling std::end() versus incrementing a valid iterator. 1069 return Result.Iter == RHS.Result.Iter; 1070 } 1071 1072 enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) { 1073 Result = Other.Result; 1074 return *this; 1075 } 1076 1077 private: 1078 result_type Result; 1079 }; 1080 1081 template <typename R> class enumerator { 1082 public: 1083 explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {} 1084 1085 enumerator_iter<R> begin() { 1086 return enumerator_iter<R>(0, std::begin(TheRange)); 1087 } 1088 enumerator_iter<R> end() { 1089 return enumerator_iter<R>(std::end(TheRange)); 1090 } 1091 1092 private: 1093 R TheRange; 1094 }; 1095 } 1096 1097 /// Given an input range, returns a new range whose values are are pair (A,B) 1098 /// such that A is the 0-based index of the item in the sequence, and B is 1099 /// the value from the original sequence. Example: 1100 /// 1101 /// std::vector<char> Items = {'A', 'B', 'C', 'D'}; 1102 /// for (auto X : enumerate(Items)) { 1103 /// printf("Item %d - %c\n", X.index(), X.value()); 1104 /// } 1105 /// 1106 /// Output: 1107 /// Item 0 - A 1108 /// Item 1 - B 1109 /// Item 2 - C 1110 /// Item 3 - D 1111 /// 1112 template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { 1113 return detail::enumerator<R>(std::forward<R>(TheRange)); 1114 } 1115 1116 namespace detail { 1117 template <typename F, typename Tuple, std::size_t... I> 1118 auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>) 1119 -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) { 1120 return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...); 1121 } 1122 } 1123 1124 /// Given an input tuple (a1, a2, ..., an), pass the arguments of the 1125 /// tuple variadically to f as if by calling f(a1, a2, ..., an) and 1126 /// return the result. 1127 template <typename F, typename Tuple> 1128 auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl( 1129 std::forward<F>(f), std::forward<Tuple>(t), 1130 build_index_impl< 1131 std::tuple_size<typename std::decay<Tuple>::type>::value>{})) { 1132 using Indices = build_index_impl< 1133 std::tuple_size<typename std::decay<Tuple>::type>::value>; 1134 1135 return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t), 1136 Indices{}); 1137 } 1138 } // End llvm namespace 1139 1140 #endif 1141