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