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 38namespace 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. 42template <typename T, T> struct SameType; 43 44namespace detail { 45 46template <typename RangeT> 47using IterOfRange = decltype(std::begin(std::declval<RangeT &>())); 48 49template <typename RangeT> 50using 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 59template <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 69template <class Ty> struct less_ptr { 70 bool operator()(const Ty* left, const Ty* right) const { 71 return *left < *right; 72 } 73}; 74 75template <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. 87template<typename Fn> class function_ref; 88 89template<typename Ret, typename ...Params> 90class 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 100public: 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// 122template <class T> 123inline 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// 136template <class RootIt, class UnaryFunc> 137class mapped_iterator { 138 RootIt current; 139 UnaryFunc Fn; 140public: 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 209template <class Iterator, class Func> 210inline mapped_iterator<Iterator, Func> 211operator+(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// 220template <class ItTy, class FuncTy> 221inline 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(). 226template <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 236public: 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(). 241template <typename Ty> 242struct 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. 247template <typename ContainerTy> 248auto 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. 255template <typename IteratorTy> 256std::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. 263template <typename ContainerTy> 264auto 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 285template <typename WrappedIteratorT, typename PredicateT> 286class 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 325public: 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. 346template <typename RangeT, typename PredicateT> 347iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>> 348make_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 358template <typename R, typename UnaryPredicate> 359bool all_of(R &&range, UnaryPredicate P); 360 361template <size_t... I> struct index_sequence; 362 363template <class... Ts> struct index_sequence_for; 364 365namespace detail { 366using 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. 370template<typename... Iters> struct ZipTupleType { 371 typedef std::tuple<decltype(*declval<Iters>())...> type; 372}; 373 374template <typename ZipType, typename... Iters> 375using 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 390template <typename ZipType, typename... Iters> 391struct 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 397protected: 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 412public: 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 434template <typename... Iters> 435struct 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 445template <typename... Iters> 446class 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 454public: 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 464template <template <typename...> class ItType, typename... Args> class zippy { 465public: 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 473private: 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 483public: 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. 491template <typename T, typename U, typename... Args> 492detail::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. 500template <typename T, typename U, typename... Args> 501detail::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. 517template <typename ValueT, typename... IterTs> 518class 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 588public: 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 610namespace 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. 616template <typename ValueT, typename... RangeTs> class concat_range { 617public: 618 typedef concat_iterator<ValueT, 619 decltype(std::begin(std::declval<RangeTs &>()))...> 620 iterator; 621 622private: 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 633public: 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. 644template <typename ValueT, typename... RangeTs> 645detail::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. 658struct 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. 666struct 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. 675template <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. 682template <size_t... I> 683struct index_sequence : integer_sequence<std::size_t, I...> {}; 684 685template <std::size_t N, std::size_t... I> 686struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {}; 687template <std::size_t... I> 688struct build_index_impl<0, I...> : index_sequence<I...> {}; 689 690/// \brief Creates a compile-time integer sequence for a parameter pack. 691template <class... Ts> 692struct 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. 696template <int N> struct rank : rank<N - 1> {}; 697template <> 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. 701template <typename T, typename... Ts> struct is_one_of { 702 static const bool value = false; 703}; 704 705template <typename T, typename U, typename... Ts> 706struct 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. 713template <typename T, typename... Ts> struct are_base_of { 714 static const bool value = true; 715}; 716 717template <typename T, typename U, typename... Ts> 718struct 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. 728template <class T, std::size_t N> 729constexpr inline size_t array_lengthof(T (&)[N]) { 730 return N; 731} 732 733/// Adapt std::less<T> for array_pod_sort. 734template<typename T> 735inline 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. 747template<typename T> 748inline 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. 768template<class IteratorTy> 769inline 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 777template <class IteratorTy> 778inline 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. 797template<typename Container> 798void 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. 806template<typename Container> 807void 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. 815template <typename R, typename UnaryPredicate> 816bool 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. 822template <typename R, typename UnaryPredicate> 823bool 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. 829template <typename R, typename UnaryPredicate> 830bool 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. 836template <typename R, typename T> 837auto 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. 843template <typename R, typename UnaryPredicate> 844auto find_if(R &&Range, UnaryPredicate P) -> decltype(std::begin(Range)) { 845 return std::find_if(std::begin(Range), std::end(Range), P); 846} 847 848template <typename R, typename UnaryPredicate> 849auto 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. 855template <typename R, typename UnaryPredicate> 856auto 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. 862template <typename R, typename OutputIt, typename UnaryPredicate> 863OutputIt 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. 869template <typename R, typename E> 870bool 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. 877template <typename R, typename E> 878auto 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. 885template <typename R, typename UnaryPredicate> 886auto 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. 893template <typename R, typename OutputIt, typename UnaryPredicate> 894OutputIt 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. 900template <typename R, typename UnaryPredicate> 901auto 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. 907template <typename R, typename ForwardIt> 908auto 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. 915template <unsigned Size, typename R> 916SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size> 917to_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. 928template <typename Container, typename UnaryPredicate> 929void 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); 946template <class T, class... Args> 947typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type 948make_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. 960template <class T> 961typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0, 962 std::unique_ptr<T>>::type 963make_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. 968template <class T, class... Args> 969typename std::enable_if<std::extent<T>::value != 0>::type 970make_unique(Args &&...) = delete; 971 972struct FreeDeleter { 973 void operator()(void* v) { 974 ::free(v); 975 } 976}; 977 978template<typename First, typename Second> 979struct 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. 986struct 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. 993struct 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. 1001template <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 1014namespace detail { 1015template <typename R> class enumerator_iter; 1016 1017template <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 1034private: 1035 std::size_t Index; 1036 IterOfRange<R> Iter; 1037}; 1038 1039template <typename R> 1040class 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 1048public: 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 1077private: 1078 result_type Result; 1079}; 1080 1081template <typename R> class enumerator { 1082public: 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 1092private: 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/// 1112template <typename R> detail::enumerator<R> enumerate(R &&TheRange) { 1113 return detail::enumerator<R>(std::forward<R>(TheRange)); 1114} 1115 1116namespace detail { 1117template <typename F, typename Tuple, std::size_t... I> 1118auto 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. 1127template <typename F, typename Tuple> 1128auto 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