Line data Source code
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 "llvm/ADT/Optional.h"
21 : #include "llvm/ADT/SmallVector.h"
22 : #include "llvm/ADT/iterator.h"
23 : #include "llvm/ADT/iterator_range.h"
24 : #include "llvm/Config/abi-breaking.h"
25 : #include "llvm/Support/ErrorHandling.h"
26 : #include <algorithm>
27 : #include <cassert>
28 : #include <cstddef>
29 : #include <cstdint>
30 : #include <cstdlib>
31 : #include <functional>
32 : #include <initializer_list>
33 : #include <iterator>
34 : #include <limits>
35 : #include <memory>
36 : #include <tuple>
37 : #include <type_traits>
38 : #include <utility>
39 :
40 : #ifdef EXPENSIVE_CHECKS
41 : #include <random> // for std::mt19937
42 : #endif
43 :
44 : namespace llvm {
45 :
46 : // Only used by compiler if both template types are the same. Useful when
47 : // using SFINAE to test for the existence of member functions.
48 : template <typename T, T> struct SameType;
49 :
50 : namespace detail {
51 :
52 : template <typename RangeT>
53 : using IterOfRange = decltype(std::begin(std::declval<RangeT &>()));
54 :
55 : template <typename RangeT>
56 : using ValueOfRange = typename std::remove_reference<decltype(
57 : *std::begin(std::declval<RangeT &>()))>::type;
58 :
59 : } // end namespace detail
60 :
61 : //===----------------------------------------------------------------------===//
62 : // Extra additions to <type_traits>
63 : //===----------------------------------------------------------------------===//
64 :
65 : template <typename T>
66 : struct negation : std::integral_constant<bool, !bool(T::value)> {};
67 :
68 : template <typename...> struct conjunction : std::true_type {};
69 : template <typename B1> struct conjunction<B1> : B1 {};
70 : template <typename B1, typename... Bn>
71 : struct conjunction<B1, Bn...>
72 : : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
73 :
74 : //===----------------------------------------------------------------------===//
75 : // Extra additions to <functional>
76 : //===----------------------------------------------------------------------===//
77 :
78 : template <class Ty> struct identity {
79 : using argument_type = Ty;
80 :
81 0 : Ty &operator()(Ty &self) const {
82 0 : return self;
83 : }
84 0 : const Ty &operator()(const Ty &self) const {
85 0 : return self;
86 : }
87 : };
88 :
89 : template <class Ty> struct less_ptr {
90 0 : bool operator()(const Ty* left, const Ty* right) const {
91 5458462 : return *left < *right;
92 : }
93 : };
94 :
95 : template <class Ty> struct greater_ptr {
96 : bool operator()(const Ty* left, const Ty* right) const {
97 : return *right < *left;
98 : }
99 : };
100 :
101 : /// An efficient, type-erasing, non-owning reference to a callable. This is
102 : /// intended for use as the type of a function parameter that is not used
103 : /// after the function in question returns.
104 : ///
105 : /// This class does not own the callable, so it is not in general safe to store
106 : /// a function_ref.
107 : template<typename Fn> class function_ref;
108 :
109 : template<typename Ret, typename ...Params>
110 : class function_ref<Ret(Params...)> {
111 : Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
112 : intptr_t callable;
113 :
114 : template<typename Callable>
115 71143701 : static Ret callback_fn(intptr_t callable, Params ...params) {
116 63814052 : return (*reinterpret_cast<Callable*>(callable))(
117 71143681 : std::forward<Params>(params)...);
118 : }
119 6072522 :
120 5361062 : public:
121 6072521 : function_ref() = default;
122 : function_ref(std::nullptr_t) {}
123 10119785 :
124 9051752 : template <typename Callable>
125 61091659 : function_ref(Callable &&callable,
126 : typename std::enable_if<
127 6705828 : !std::is_same<typename std::remove_reference<Callable>::type,
128 6421488 : function_ref>::value>::type * = nullptr)
129 6705828 : : callback(callback_fn<typename std::remove_reference<Callable>::type>),
130 50972126 : callable(reinterpret_cast<intptr_t>(&callable)) {}
131 9741973 :
132 9466627 : Ret operator()(Params ...params) const {
133 22084989 : return callback(callable, std::forward<Params>(params)...);
134 : }
135 12697467 :
136 12458393 : operator bool() const { return callback; }
137 76112559 : };
138 8449199 :
139 1266774 : // deleter - Very very very simple method that is used to invoke operator
140 1040406 : // delete on something. It is used like this:
141 105588326 : //
142 63363561 : // for_each(V.begin(), B.end(), deleter<Interval>);
143 2125748 : template <class T>
144 43173 : inline void deleter(T *Ptr) {
145 29582812 : delete Ptr;
146 120988226 : }
147 633696 :
148 6897 : //===----------------------------------------------------------------------===//
149 2014207 : // Extra additions to <iterator>
150 26219463 : //===----------------------------------------------------------------------===//
151 414543 :
152 59443 : namespace adl_detail {
153 863136 :
154 962049 : using std::begin;
155 30204 :
156 27881 : template <typename ContainerTy>
157 12165231 : auto adl_begin(ContainerTy &&container)
158 10050 : -> decltype(begin(std::forward<ContainerTy>(container))) {
159 816184 : return begin(std::forward<ContainerTy>(container));
160 73407 : }
161 816698 :
162 11644949 : using std::end;
163 173922 :
164 123918 : template <typename ContainerTy>
165 147209 : auto adl_end(ContainerTy &&container)
166 0 : -> decltype(end(std::forward<ContainerTy>(container))) {
167 7258430 : return end(std::forward<ContainerTy>(container));
168 393797 : }
169 409476 :
170 0 : using std::swap;
171 1215719 :
172 1215719 : template <typename T>
173 34776105 : void adl_swap(T &&lhs, T &&rhs) noexcept(noexcept(swap(std::declval<T>(),
174 0 : std::declval<T>()))) {
175 1643876 : swap(std::forward<T>(lhs), std::forward<T>(rhs));
176 1637815 : }
177 2217560 :
178 354 : } // end namespace adl_detail
179 18165 :
180 1514 : template <typename ContainerTy>
181 18165 : auto adl_begin(ContainerTy &&container)
182 573705 : -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
183 194534 : return adl_detail::adl_begin(std::forward<ContainerTy>(container));
184 194276 : }
185 1249539 :
186 0 : template <typename ContainerTy>
187 5160 : auto adl_end(ContainerTy &&container)
188 1541 : -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
189 1541 : return adl_detail::adl_end(std::forward<ContainerTy>(container));
190 1055263 : }
191 3992 :
192 3982 : template <typename T>
193 1272539 : void adl_swap(T &&lhs, T &&rhs) noexcept(
194 0 : noexcept(adl_detail::adl_swap(std::declval<T>(), std::declval<T>()))) {
195 1301 : adl_detail::adl_swap(std::forward<T>(lhs), std::forward<T>(rhs));
196 1301 : }
197 1301 :
198 15 : // mapped_iterator - This is a simple iterator adapter that causes a function to
199 734 : // be applied whenever operator* is invoked on the iterator.
200 734 :
201 4937203 : template <typename ItTy, typename FuncTy,
202 0 : typename FuncReturnTy =
203 11369 : decltype(std::declval<FuncTy>()(*std::declval<ItTy>()))>
204 3195 : class mapped_iterator
205 3226 : : public iterator_adaptor_base<
206 0 : mapped_iterator<ItTy, FuncTy>, ItTy,
207 7327 : typename std::iterator_traits<ItTy>::iterator_category,
208 7296 : typename std::remove_reference<FuncReturnTy>::type> {
209 7274 : public:
210 237 : mapped_iterator(ItTy U, FuncTy F)
211 128224 : : mapped_iterator::iterator_adaptor_base(std::move(U)), F(std::move(F)) {}
212 11372 :
213 128145 : ItTy getCurrent() { return this->I; }
214 0 :
215 4822084 : FuncReturnTy operator*() { return F(*this->I); }
216 29587 :
217 35349 : private:
218 0 : FuncTy F;
219 504 : };
220 226 :
221 504 : // map_iterator - Provide a convenient way to create mapped_iterators, just like
222 3415 : // make_pair is useful for creating pairs...
223 550 : template <class ItTy, class FuncTy>
224 572 : inline mapped_iterator<ItTy, FuncTy> map_iterator(ItTy I, FuncTy F) {
225 550 : return mapped_iterator<ItTy, FuncTy>(std::move(I), std::move(F));
226 0 : }
227 1100 :
228 256 : /// Helper to determine if type T has a member called rbegin().
229 256 : template <typename Ty> class has_rbegin_impl {
230 0 : using yes = char[1];
231 4015 : using no = char[2];
232 1113 :
233 4015 : template <typename Inner>
234 0 : static yes& test(Inner *I, decltype(I->rbegin()) * = nullptr);
235 1751 :
236 1407 : template <typename>
237 1407 : static no& test(...);
238 0 :
239 9365978 : public:
240 483 : static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
241 483 : };
242 0 :
243 620 : /// Metafunction to determine if T& or T has a member called rbegin().
244 620 : template <typename Ty>
245 620 : struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
246 0 : };
247 1635 :
248 1635 : // Returns an iterator_range over the given container which iterates in reverse.
249 1635 : // Note that the container must have rbegin()/rend() methods for this to work.
250 0 : template <typename ContainerTy>
251 673 : auto reverse(ContainerTy &&C,
252 673 : typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
253 5354 : nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
254 36915114 : return make_range(C.rbegin(), C.rend());
255 60350 : }
256 1440 :
257 5726297 : // Returns a std::reverse_iterator wrapped around the given iterator.
258 0 : template <typename IteratorTy>
259 12716 : std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
260 12716 : return std::reverse_iterator<IteratorTy>(It);
261 1406 : }
262 14679665 :
263 565125 : // Returns an iterator_range over the given container which iterates in reverse.
264 444 : // Note that the container must have begin()/end() methods which return
265 444 : // bidirectional iterators for this to work.
266 0 : template <typename ContainerTy>
267 6238 : auto reverse(
268 583 : ContainerTy &&C,
269 583 : typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
270 0 : -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
271 41 : llvm::make_reverse_iterator(std::begin(C)))) {
272 41 : return make_range(llvm::make_reverse_iterator(std::end(C)),
273 28316 : llvm::make_reverse_iterator(std::begin(C)));
274 57 : }
275 41 :
276 41 : /// An iterator adaptor that filters the elements of given inner iterators.
277 2834958 : ///
278 : /// The predicate parameter should be a callable object that accepts the wrapped
279 1 : /// iterator's reference type and returns a bool. When incrementing or
280 1 : /// decrementing the iterator, it will call the predicate on each element and
281 1 : /// skip any where it returns false.
282 177835 : ///
283 1 : /// \code
284 4305 : /// int A[] = { 1, 2, 3, 4 };
285 1 : /// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
286 38 : /// // R contains { 1, 3 }.
287 543 : /// \endcode
288 543 : ///
289 543 : /// Note: filter_iterator_base implements support for forward iteration.
290 0 : /// filter_iterator_impl exists to provide support for bidirectional iteration,
291 1 : /// conditional on whether the wrapped iterator supports it.
292 1 : template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
293 2887660 : class filter_iterator_base
294 194 : : public iterator_adaptor_base<
295 1512 : filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
296 1512 : WrappedIteratorT,
297 1512 : typename std::common_type<
298 0 : IterTag, typename std::iterator_traits<
299 0 : WrappedIteratorT>::iterator_category>::type> {
300 0 : using BaseT = iterator_adaptor_base<
301 2575 : filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
302 0 : WrappedIteratorT,
303 128 : typename std::common_type<
304 2660 : IterTag, typename std::iterator_traits<
305 155 : WrappedIteratorT>::iterator_category>::type>;
306 0 :
307 76 : protected:
308 76 : WrappedIteratorT End;
309 76 : PredicateT Pred;
310 46 :
311 2110600 : void findNextValid() {
312 4215490 : while (this->I != End && !Pred(*this->I))
313 0 : BaseT::operator++();
314 2110600 : }
315 1820386 :
316 3637949 : // Construct the iterator. The begin iterator needs to know where the end
317 0 : // is, so that it can properly stop when it gets there. The end iterator only
318 1820386 : // needs the predicate to support bidirectional iteration.
319 21702 : filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
320 5122 : PredicateT Pred)
321 36550 : : BaseT(Begin), End(End), Pred(Pred) {
322 21702 : findNextValid();
323 1885 : }
324 2086 :
325 0 : public:
326 1885 : using BaseT::operator++;
327 1823687 :
328 669799 : filter_iterator_base &operator++() {
329 1823024 : BaseT::operator++();
330 1936569 : findNextValid();
331 1822686 : return *this;
332 1819454 : }
333 0 : };
334 1819454 :
335 1823037 : /// Specialization of filter_iterator_base for forward iteration only.
336 1819454 : template <typename WrappedIteratorT, typename PredicateT,
337 7897 : typename IterTag = std::forward_iterator_tag>
338 1130 : class filter_iterator_impl
339 3232 : : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
340 3232 : using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
341 3232 :
342 0 : public:
343 0 : filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
344 1 : PredicateT Pred)
345 0 : : BaseT(Begin, End, Pred) {}
346 420 : };
347 1 :
348 0 : /// Specialization of filter_iterator_base for bidirectional iteration.
349 0 : template <typename WrappedIteratorT, typename PredicateT>
350 170937 : class filter_iterator_impl<WrappedIteratorT, PredicateT,
351 0 : std::bidirectional_iterator_tag>
352 0 : : public filter_iterator_base<WrappedIteratorT, PredicateT,
353 0 : std::bidirectional_iterator_tag> {
354 0 : using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
355 76 : std::bidirectional_iterator_tag>;
356 39901 : void findPrevValid() {
357 111898 : while (!this->Pred(*this->I))
358 0 : BaseT::operator--();
359 39825 : }
360 12 :
361 64 : public:
362 0 : using BaseT::operator--;
363 7097 :
364 273 : filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
365 284 : PredicateT Pred)
366 0 : : BaseT(Begin, End, Pred) {}
367 72 :
368 74 : filter_iterator_impl &operator--() {
369 75 : BaseT::operator--();
370 21858 : findPrevValid();
371 74 : return *this;
372 0 : }
373 67 : };
374 0 :
375 64 : namespace detail {
376 64 :
377 64 : template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
378 0 : using type = std::forward_iterator_tag;
379 2131 : };
380 2131 :
381 2131 : template <> struct fwd_or_bidi_tag_impl<true> {
382 1822686 : using type = std::bidirectional_iterator_tag;
383 2131 : };
384 3645372 :
385 1821585 : /// Helper which sets its type member to forward_iterator_tag if the category
386 0 : /// of \p IterT does not derive from bidirectional_iterator_tag, and to
387 3641078 : /// bidirectional_iterator_tag otherwise.
388 5402 : template <typename IterT> struct fwd_or_bidi_tag {
389 2170 : using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
390 6464 : std::bidirectional_iterator_tag,
391 1413 : typename std::iterator_traits<IterT>::iterator_category>::value>::type;
392 1413 : };
393 1413 :
394 0 : } // namespace detail
395 0 :
396 0 : /// Defines filter_iterator to a suitable specialization of
397 0 : /// filter_iterator_impl, based on the underlying iterator's category.
398 0 : template <typename WrappedIteratorT, typename PredicateT>
399 90 : using filter_iterator = filter_iterator_impl<
400 90 : WrappedIteratorT, PredicateT,
401 90 : typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
402 :
403 94 : /// Convenience function that takes a range of elements and a predicate,
404 94 : /// and return a new filter_iterator range.
405 94 : ///
406 0 : /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
407 94 : /// lifetime of that temporary is not kept by the returned range object, and the
408 0 : /// temporary is going to be dropped on the floor after the make_iterator_range
409 94 : /// full expression that contains this function call.
410 0 : template <typename RangeT, typename PredicateT>
411 111 : iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
412 18386 : make_filter_range(RangeT &&Range, PredicateT Pred) {
413 111 : using FilterIteratorT =
414 : filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
415 36549 : return make_range(
416 0 : FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
417 0 : std::end(std::forward<RangeT>(Range)), Pred),
418 0 : FilterIteratorT(std::end(std::forward<RangeT>(Range)),
419 18342 : std::end(std::forward<RangeT>(Range)), Pred));
420 236 : }
421 67 :
422 : /// A pseudo-iterator adaptor that is designed to implement "early increment"
423 405 : /// style loops.
424 236 : ///
425 236 : /// This is *not a normal iterator* and should almost never be used directly. It
426 : /// is intended primarily to be used with range based for loops and some range
427 185 : /// algorithms.
428 1090 : ///
429 8 : /// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
430 0 : /// somewhere between them. The constraints of these iterators are:
431 1094 : ///
432 12 : /// - On construction or after being incremented, it is comparable and
433 12 : /// dereferencable. It is *not* incrementable.
434 : /// - After being dereferenced, it is neither comparable nor dereferencable, it
435 1190 : /// is only incrementable.
436 911451 : ///
437 433 : /// This means you can only dereference the iterator once, and you can only
438 0 : /// increment it once between dereferences.
439 108 : template <typename WrappedIteratorT>
440 433 : class early_inc_iterator_impl
441 108 : : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
442 0 : WrappedIteratorT, std::input_iterator_tag> {
443 3645480 : using BaseT =
444 433 : iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
445 108 : WrappedIteratorT, std::input_iterator_tag>;
446 237 :
447 624 : using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
448 624 :
449 861 : protected:
450 0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
451 3056657 : bool IsEarlyIncremented = false;
452 132 : #endif
453 369 :
454 90 : public:
455 2501 : early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
456 2501 :
457 2501 : using BaseT::operator*;
458 0 : typename BaseT::reference operator*() {
459 0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
460 0 : assert(!IsEarlyIncremented && "Cannot dereference twice!");
461 0 : IsEarlyIncremented = true;
462 0 : #endif
463 0 : return *(this->I)++;
464 520 : }
465 129559 :
466 0 : using BaseT::operator++;
467 520 : early_inc_iterator_impl &operator++() {
468 0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
469 0 : assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
470 125361 : IsEarlyIncremented = false;
471 520 : #endif
472 0 : return *this;
473 0 : }
474 :
475 0 : using BaseT::operator==;
476 0 : bool operator==(const early_inc_iterator_impl &RHS) const {
477 0 : #if LLVM_ENABLE_ABI_BREAKING_CHECKS
478 0 : assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
479 0 : #endif
480 : return BaseT::operator==(RHS);
481 0 : }
482 0 : };
483 0 :
484 0 : /// Make a range that does early increment to allow mutation of the underlying
485 0 : /// range without disrupting iteration.
486 : ///
487 0 : /// The underlying iterator will be incremented immediately after it is
488 0 : /// dereferenced, allowing deletion of the current node or insertion of nodes to
489 0 : /// not disrupt iteration provided they do not invalidate the *next* iterator --
490 0 : /// the current iterator can be invalidated.
491 0 : ///
492 : /// This requires a very exact pattern of use that is only really suitable to
493 0 : /// range based for loops and other range algorithms that explicitly guarantee
494 0 : /// to dereference exactly once each element, and to increment exactly once each
495 0 : /// element.
496 0 : template <typename RangeT>
497 0 : iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
498 : make_early_inc_range(RangeT &&Range) {
499 0 : using EarlyIncIteratorT =
500 0 : early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
501 0 : return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
502 0 : EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
503 0 : }
504 :
505 0 : // forward declarations required by zip_shortest/zip_first
506 0 : template <typename R, typename UnaryPredicate>
507 0 : bool all_of(R &&range, UnaryPredicate P);
508 0 :
509 0 : template <size_t... I> struct index_sequence;
510 :
511 0 : template <class... Ts> struct index_sequence_for;
512 0 :
513 0 : namespace detail {
514 0 :
515 0 : using std::declval;
516 :
517 0 : // We have to alias this since inlining the actual type at the usage site
518 0 : // in the parameter list of iterator_facade_base<> below ICEs MSVC 2017.
519 0 : template<typename... Iters> struct ZipTupleType {
520 0 : using type = std::tuple<decltype(*declval<Iters>())...>;
521 0 : };
522 :
523 0 : template <typename ZipType, typename... Iters>
524 0 : using zip_traits = iterator_facade_base<
525 0 : ZipType, typename std::common_type<std::bidirectional_iterator_tag,
526 0 : typename std::iterator_traits<
527 0 : Iters>::iterator_category...>::type,
528 : // ^ TODO: Implement random access methods.
529 0 : typename ZipTupleType<Iters...>::type,
530 2 : typename std::iterator_traits<typename std::tuple_element<
531 0 : 0, std::tuple<Iters...>>::type>::difference_type,
532 0 : // ^ FIXME: This follows boost::make_zip_iterator's assumption that all
533 0 : // inner iterators have the same difference_type. It would fail if, for
534 : // instance, the second field's difference_type were non-numeric while the
535 0 : // first is.
536 0 : typename ZipTupleType<Iters...>::type *,
537 2 : typename ZipTupleType<Iters...>::type>;
538 0 :
539 0 : template <typename ZipType, typename... Iters>
540 : struct zip_common : public zip_traits<ZipType, Iters...> {
541 0 : using Base = zip_traits<ZipType, Iters...>;
542 0 : using value_type = typename Base::value_type;
543 0 :
544 0 : std::tuple<Iters...> iterators;
545 0 :
546 0 : protected:
547 0 : template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
548 713493 : return value_type(*std::get<Ns>(iterators)...);
549 0 : }
550 0 :
551 0 : template <size_t... Ns>
552 0 : decltype(iterators) tup_inc(index_sequence<Ns...>) const {
553 0 : return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
554 0 : }
555 0 :
556 0 : template <size_t... Ns>
557 457712 : decltype(iterators) tup_dec(index_sequence<Ns...>) const {
558 0 : return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
559 0 : }
560 0 :
561 0 : public:
562 457712 : zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
563 0 :
564 8 : value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
565 0 :
566 0 : const value_type operator*() const {
567 0 : return deref(index_sequence_for<Iters...>{});
568 0 : }
569 0 :
570 0 : ZipType &operator++() {
571 0 : iterators = tup_inc(index_sequence_for<Iters...>{});
572 0 : return *reinterpret_cast<ZipType *>(this);
573 0 : }
574 8 :
575 16 : ZipType &operator--() {
576 0 : static_assert(Base::IsBidirectional,
577 4 : "All inner iterators must be at least bidirectional.");
578 8 : iterators = tup_dec(index_sequence_for<Iters...>{});
579 0 : return *reinterpret_cast<ZipType *>(this);
580 4 : }
581 8 : };
582 0 :
583 8 : template <typename... Iters>
584 0 : struct zip_first : public zip_common<zip_first<Iters...>, Iters...> {
585 0 : using Base = zip_common<zip_first<Iters...>, Iters...>;
586 0 :
587 0 : bool operator==(const zip_first<Iters...> &other) const {
588 0 : return std::get<0>(this->iterators) == std::get<0>(other.iterators);
589 0 : }
590 508180 :
591 0 : zip_first(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
592 0 : };
593 0 :
594 : template <typename... Iters>
595 0 : class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
596 0 : template <size_t... Ns>
597 0 : bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
598 8 : return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
599 8 : std::get<Ns>(other.iterators)...},
600 526066 : identity<bool>{});
601 526058 : }
602 526063 :
603 4 : public:
604 56842 : using Base = zip_common<zip_shortest<Iters...>, Iters...>;
605 56838 :
606 56842 : zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
607 4 :
608 469224 : bool operator==(const zip_shortest<Iters...> &other) const {
609 469254 : return !test(other, index_sequence_for<Iters...>{});
610 469220 : }
611 1 : };
612 0 :
613 : template <template <typename...> class ItType, typename... Args> class zippy {
614 0 : public:
615 0 : using iterator = ItType<decltype(std::begin(std::declval<Args>()))...>;
616 : using iterator_category = typename iterator::iterator_category;
617 0 : using value_type = typename iterator::value_type;
618 1 : using difference_type = typename iterator::difference_type;
619 0 : using pointer = typename iterator::pointer;
620 0 : using reference = typename iterator::reference;
621 0 :
622 0 : private:
623 0 : std::tuple<Args...> ts;
624 :
625 0 : template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
626 11 : return iterator(std::begin(std::get<Ns>(ts))...);
627 0 : }
628 0 : template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
629 0 : return iterator(std::end(std::get<Ns>(ts))...);
630 0 : }
631 14 :
632 0 : public:
633 0 : zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
634 0 :
635 0 : iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
636 0 : iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
637 0 : };
638 0 :
639 0 : } // end namespace detail
640 0 :
641 0 : /// zip iterator for two or more iteratable types.
642 : template <typename T, typename U, typename... Args>
643 0 : detail::zippy<detail::zip_shortest, T, U, Args...> zip(T &&t, U &&u,
644 0 : Args &&... args) {
645 0 : return detail::zippy<detail::zip_shortest, T, U, Args...>(
646 0 : std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
647 0 : }
648 0 :
649 0 : /// zip iterator that, for the sake of efficiency, assumes the first iteratee to
650 0 : /// be the shortest.
651 0 : template <typename T, typename U, typename... Args>
652 0 : detail::zippy<detail::zip_first, T, U, Args...> zip_first(T &&t, U &&u,
653 0 : Args &&... args) {
654 0 : return detail::zippy<detail::zip_first, T, U, Args...>(
655 10 : std::forward<T>(t), std::forward<U>(u), std::forward<Args>(args)...);
656 0 : }
657 0 :
658 0 : /// Iterator wrapper that concatenates sequences together.
659 2 : ///
660 0 : /// This can concatenate different iterators, even with different types, into
661 0 : /// a single iterator provided the value types of all the concatenated
662 0 : /// iterators expose `reference` and `pointer` types that can be converted to
663 0 : /// `ValueT &` and `ValueT *` respectively. It doesn't support more
664 : /// interesting/customized pointer or reference types.
665 0 : ///
666 0 : /// Currently this only supports forward or higher iterator categories as
667 : /// inputs and always exposes a forward iterator interface.
668 0 : template <typename ValueT, typename... IterTs>
669 18274 : class concat_iterator
670 : : public iterator_facade_base<concat_iterator<ValueT, IterTs...>,
671 2 : std::forward_iterator_tag, ValueT> {
672 1116469 : using BaseT = typename concat_iterator::iterator_facade_base;
673 :
674 1 : /// We store both the current and end iterators for each concatenated
675 1 : /// sequence in a tuple of pairs.
676 0 : ///
677 1 : /// Note that something like iterator_range seems nice at first here, but the
678 1 : /// range properties are of little benefit and end up getting in the way
679 : /// because we need to do mutation on the current iterators.
680 2 : std::tuple<IterTs...> Begins;
681 2 : std::tuple<IterTs...> Ends;
682 :
683 1 : /// Attempts to increment a specific iterator.
684 1 : ///
685 : /// Returns true if it was able to increment the iterator. Returns false if
686 1 : /// the iterator is already at the end iterator.
687 3809726 : template <size_t Index> bool incrementHelper() {
688 0 : auto &Begin = std::get<Index>(Begins);
689 0 : auto &End = std::get<Index>(Ends);
690 3809712 : if (Begin == End)
691 0 : return false;
692 0 :
693 9238 : ++Begin;
694 3023137 : return true;
695 0 : }
696 89419 :
697 0 : /// Increments the first non-end iterator.
698 0 : ///
699 89419 : /// It is an error to call this with all iterators at the end.
700 0 : template <size_t... Ns> void increment(index_sequence<Ns...>) {
701 0 : // Build a sequence of functions to increment each iterator if possible.
702 4 : bool (concat_iterator::*IncrementHelperFns[])() = {
703 89419 : &concat_iterator::incrementHelper<Ns>...};
704 0 :
705 1413076 : // Loop over them, and stop as soon as we succeed at incrementing one.
706 0 : for (auto &IncrementHelperFn : IncrementHelperFns)
707 0 : if ((this->*IncrementHelperFn)())
708 1413076 : return;
709 0 :
710 0 : llvm_unreachable("Attempted to increment an end concat iterator!");
711 9058 : }
712 1323657 :
713 0 : /// Returns null if the specified iterator is at the end. Otherwise,
714 282690 : /// dereferences the iterator and returns the address of the resulting
715 0 : /// reference.
716 0 : template <size_t Index> ValueT *getHelper() const {
717 282690 : auto &Begin = std::get<Index>(Begins);
718 1566525 : auto &End = std::get<Index>(Ends);
719 0 : if (Begin == End)
720 1566699 : return nullptr;
721 281641 :
722 0 : return &*Begin;
723 592857 : }
724 1777765 :
725 1777765 : /// Finds the first non-end iterator, dereferences, and returns the resulting
726 2159382 : /// reference.
727 3065 : ///
728 0 : /// It is an error to call this with all iterators at the end.
729 16 : template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
730 313232 : // Build a sequence of functions to get from iterator if possible.
731 0 : ValueT *(concat_iterator::*GetHelperFns[])() const = {
732 413435 : &concat_iterator::getHelper<Ns>...};
733 2090 :
734 1494467 : // Loop over them, and return the first result we find.
735 413451 : for (auto &GetHelperFn : GetHelperFns)
736 10820 : if (ValueT *P = (this->*GetHelperFn)())
737 1492377 : return *P;
738 10820 :
739 413435 : llvm_unreachable("Attempted to get a pointer from an end concat iterator!");
740 0 : }
741 1018235 :
742 100665 : public:
743 11285 : /// Constructs an iterator from a squence of ranges.
744 1029055 : ///
745 89626 : /// We need the full range to know how to switch between each of the
746 28 : /// iterators.
747 8 : template <typename... RangeTs>
748 614076 : explicit concat_iterator(RangeTs &&... Ranges)
749 4 : : Begins(std::begin(Ranges)...), Ends(std::end(Ranges)...) {}
750 1412027 :
751 222 : using BaseT::operator++;
752 541 :
753 1402969 : concat_iterator &operator++() {
754 1433101 : increment(index_sequence_for<IterTs...>());
755 9381 : return *this;
756 1432805 : }
757 331 :
758 0 : ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
759 8 :
760 1989972 : bool operator==(const concat_iterator &RHS) const {
761 1989413 : return Begins == RHS.Begins && Ends == RHS.Ends;
762 1424274 : }
763 1567713 : };
764 0 :
765 1566618 : namespace detail {
766 571153 :
767 748 : /// Helper to store a sequence of ranges being concatenated and access them.
768 569884 : ///
769 1778621 : /// This is designed to facilitate providing actual storage when temporaries
770 1778637 : /// are passed into the constructor such that we can use it as part of range
771 1566625 : /// based for loops.
772 843215 : template <typename ValueT, typename... RangeTs> class concat_range {
773 843160 : public:
774 569323 : using iterator =
775 21302 : concat_iterator<ValueT,
776 10301 : decltype(std::begin(std::declval<RangeTs &>()))...>;
777 21247 :
778 854440 : private:
779 10356 : std::tuple<RangeTs...> Ranges;
780 854401 :
781 31082 : template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
782 40388 : return iterator(std::get<Ns>(Ranges)...);
783 21257 : }
784 1146784 : template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
785 1146033 : return iterator(make_range(std::end(std::get<Ns>(Ranges)),
786 854413 : std::end(std::get<Ns>(Ranges)))...);
787 961 : }
788 1567082 :
789 10 : public:
790 746 : concat_range(RangeTs &&... Ranges)
791 172 : : Ranges(std::forward<RangeTs>(Ranges)...) {}
792 1576277 :
793 857 : iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
794 2307332 : iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
795 9511 : };
796 145 :
797 2308681 : } // end namespace detail
798 9511 :
799 1204 : /// Concatenated range across two or more ranges.
800 174 : ///
801 0 : /// The desired value type must be explicitly specified.
802 6 : template <typename ValueT, typename... RangeTs>
803 3703 : detail::concat_range<ValueT, RangeTs...> concat(RangeTs &&... Ranges) {
804 1467 : static_assert(sizeof...(RangeTs) > 1,
805 3288 : "Need more than one range to concatenate!");
806 0 : return detail::concat_range<ValueT, RangeTs...>(
807 0 : std::forward<RangeTs>(Ranges)...);
808 585 : }
809 3065 :
810 4087 : //===----------------------------------------------------------------------===//
811 2620 : // Extra additions to <utility>
812 0 : //===----------------------------------------------------------------------===//
813 1038 :
814 384 : /// Function object to check whether the first component of a std::pair
815 218 : /// compares less than the first component of another std::pair.
816 0 : struct less_first {
817 915 : template <typename T> bool operator()(const T &lhs, const T &rhs) const {
818 335234 : return lhs.first < rhs.first;
819 697 : }
820 6 : };
821 292735 :
822 1428 : /// Function object to check whether the second component of a std::pair
823 11209 : /// compares less than the second component of another std::pair.
824 921 : struct less_second {
825 724 : template <typename T> bool operator()(const T &lhs, const T &rhs) const {
826 593252 : return lhs.second < rhs.second;
827 11341 : }
828 11919 : };
829 605154 :
830 0 : /// \brief Function object to apply a binary function to the first component of
831 283 : /// a std::pair.
832 15 : template<typename FuncTy>
833 10955 : struct on_first {
834 414896 : FuncTy func;
835 10953 :
836 21591 : template <typename T>
837 413740 : auto operator()(const T &lhs, const T &rhs) const
838 21247 : -> decltype(func(lhs.first, rhs.first)) {
839 85611 : return func(lhs.first, rhs.first);
840 9511 : }
841 10671 : };
842 1048822 :
843 30885 : // A subset of N3658. More stuff can be added as-needed.
844 21247 :
845 1020311 : /// Represents a compile-time sequence of integers.
846 1513 : template <class T, T... I> struct integer_sequence {
847 1881 : using value_type = T;
848 688 :
849 414 : static constexpr size_t size() { return sizeof...(I); }
850 0 : };
851 742 :
852 904 : /// Alias for the common case of a sequence of size_ts.
853 730 : template <size_t... I>
854 111 : struct index_sequence : integer_sequence<std::size_t, I...> {};
855 1426768 :
856 0 : template <std::size_t N, std::size_t... I>
857 1423709 : struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
858 3049 : template <std::size_t... I>
859 987 : struct build_index_impl<0, I...> : index_sequence<I...> {};
860 0 :
861 2010330 : /// Creates a compile-time integer sequence for a parameter pack.
862 1989083 : template <class... Ts>
863 1423708 : struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
864 18274 :
865 39521 : /// Utility type to build an inheritance chain that makes it easy to rank
866 0 : /// overload candidates.
867 593585 : template <int N> struct rank : rank<N - 1> {};
868 24262 : template <> struct rank<0> {};
869 569323 :
870 878 : /// traits class for checking whether type T is one of any of the given
871 329 : /// types in the variadic list.
872 0 : template <typename T, typename... Ts> struct is_one_of {
873 843160 : static const bool value = false;
874 844256 : };
875 569434 :
876 0 : template <typename T, typename U, typename... Ts>
877 143 : struct is_one_of<T, U, Ts...> {
878 143 : static const bool value =
879 854749 : std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
880 : };
881 854386 :
882 331 : /// traits class for checking whether type T is a base class for all
883 6 : /// the given types in the variadic list.
884 0 : template <typename T, typename... Ts> struct are_base_of {
885 1145923 : static const bool value = true;
886 1145923 : };
887 855483 :
888 0 : template <typename T, typename U, typename... Ts>
889 0 : struct are_base_of<T, U, Ts...> {
890 1098 : static const bool value =
891 331 : std::is_base_of<T, U>::value && are_base_of<T, Ts...>::value;
892 0 : };
893 0 :
894 0 : //===----------------------------------------------------------------------===//
895 55 : // Extra additions for arrays
896 0 : //===----------------------------------------------------------------------===//
897 0 :
898 55 : /// Find the length of an array.
899 0 : template <class T, std::size_t N>
900 0 : constexpr inline size_t array_lengthof(T (&)[N]) {
901 0 : return N;
902 0 : }
903 601 :
904 1423708 : /// Adapt std::less<T> for array_pod_sort.
905 0 : template<typename T>
906 22393850 : inline int array_pod_sort_comparator(const void *P1, const void *P2) {
907 21544229 : if (std::less<T>()(*reinterpret_cast<const T*>(P1),
908 1423709 : *reinterpret_cast<const T*>(P2)))
909 19460 : return -1;
910 8305433 : if (std::less<T>()(*reinterpret_cast<const T*>(P2),
911 577083 : *reinterpret_cast<const T*>(P1)))
912 7692262 : return 1;
913 0 : return 0;
914 746 : }
915 30228 :
916 351 : /// get_array_pod_sort_comparator - This is an internal helper function used to
917 0 : /// get type deduction of T right.
918 20185 : template<typename T>
919 43 : inline int (*get_array_pod_sort_comparator(const T &))
920 725 : (const void*, const void*) {
921 10018 : return array_pod_sort_comparator<T>;
922 99 : }
923 0 :
924 49194 : /// array_pod_sort - This sorts an array with the specified start and end
925 47132 : /// extent. This is just like std::sort, except that it calls qsort instead of
926 507349 : /// using an inlined template. qsort is slightly slower than std::sort, but
927 504562 : /// most sorts are not performance critical in LLVM and std::sort has to be
928 24996 : /// template instantiated for each type, leading to significant measured code
929 0 : /// bloat. This function should generally be used instead of std::sort where
930 13260 : /// possible.
931 3049 : ///
932 2374 : /// This function assumes that you have simple POD-like types that can be
933 0 : /// compared with std::less and can be moved with memcpy. If this isn't true,
934 0 : /// you should use std::sort.
935 0 : ///
936 2909 : /// NOTE: If qsort_r were portable, we could allow a custom comparator and
937 394 : /// default to std::less.
938 529 : template<class IteratorTy>
939 0 : inline void array_pod_sort(IteratorTy Start, IteratorTy End) {
940 0 : // Don't inefficiently call qsort with one element or trigger undefined
941 0 : // behavior with an empty sequence.
942 498202 : auto NElts = End - Start;
943 757285 : if (NElts <= 1) return;
944 632 : #ifdef EXPENSIVE_CHECKS
945 0 : std::mt19937 Generator(std::random_device{}());
946 3072305 : std::shuffle(Start, End, Generator);
947 6144610 : #endif
948 548923 : qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
949 1799 : }
950 1332020 :
951 3516 : template <class IteratorTy>
952 1334168 : inline void array_pod_sort(
953 125054 : IteratorTy Start, IteratorTy End,
954 1824 : int (*Compare)(
955 1429 : const typename std::iterator_traits<IteratorTy>::value_type *,
956 1098 : const typename std::iterator_traits<IteratorTy>::value_type *)) {
957 7 : // Don't inefficiently call qsort with one element or trigger undefined
958 142 : // behavior with an empty sequence.
959 2552 : auto NElts = End - Start;
960 229426 : if (NElts <= 1) return;
961 0 : #ifdef EXPENSIVE_CHECKS
962 1029502 : std::mt19937 Generator(std::random_device{}());
963 1028756 : std::shuffle(Start, End, Generator);
964 : #endif
965 20656 : qsort(&*Start, NElts, sizeof(*Start),
966 1402 : reinterpret_cast<int (*)(const void *, const void *)>(Compare));
967 1969 : }
968 43000402 :
969 42551158 : // Provide wrappers to std::sort which shuffle the elements before sorting
970 0 : // to help uncover non-deterministic behavior (PR35135).
971 725 : template <typename IteratorTy>
972 2504498 : inline void sort(IteratorTy Start, IteratorTy End) {
973 1250 : #ifdef EXPENSIVE_CHECKS
974 7019 : std::mt19937 Generator(std::random_device{}());
975 0 : std::shuffle(Start, End, Generator);
976 : #endif
977 4795031 : std::sort(Start, End);
978 617 : }
979 :
980 131261 : template <typename Container> inline void sort(Container &&C) {
981 : llvm::sort(adl_begin(C), adl_end(C));
982 135514 : }
983 5366 :
984 : template <typename IteratorTy, typename Compare>
985 3582 : inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
986 111746 : #ifdef EXPENSIVE_CHECKS
987 0 : std::mt19937 Generator(std::random_device{}());
988 115757 : std::shuffle(Start, End, Generator);
989 2062 : #endif
990 859143 : std::sort(Start, End, Comp);
991 407 : }
992 0 :
993 : template <typename Container, typename Compare>
994 1240 : inline void sort(Container &&C, Compare Comp) {
995 407 : llvm::sort(adl_begin(C), adl_end(C), Comp);
996 1240 : }
997 0 :
998 0 : //===----------------------------------------------------------------------===//
999 1015 : // Extra additions to <algorithm>
1000 59 : //===----------------------------------------------------------------------===//
1001 0 :
1002 17 : /// For a container of pointers, deletes the pointers and then clears the
1003 142714 : /// container.
1004 0 : template<typename Container>
1005 6322 : void DeleteContainerPointers(Container &C) {
1006 7428 : for (auto V : C)
1007 431 : delete V;
1008 0 : C.clear();
1009 6452 : }
1010 9 :
1011 0 : /// In a container of pairs (usually a map) whose second element is a pointer,
1012 0 : /// deletes the second elements and then clears the container.
1013 0 : template<typename Container>
1014 3928429 : void DeleteContainerSeconds(Container &C) {
1015 10133514 : for (auto &V : C)
1016 6007370 : delete V.second;
1017 3928428 : C.clear();
1018 3928428 : }
1019 15 :
1020 1503 : /// Get the size of a range. This is a wrapper function around std::distance
1021 0 : /// which is only enabled when the operation is O(1).
1022 1710 : template <typename R>
1023 207 : auto size(R &&Range, typename std::enable_if<
1024 169 : std::is_same<typename std::iterator_traits<decltype(
1025 0 : Range.begin())>::iterator_category,
1026 0 : std::random_access_iterator_tag>::value,
1027 0 : void>::type * = nullptr)
1028 60 : -> decltype(std::distance(Range.begin(), Range.end())) {
1029 0 : return std::distance(Range.begin(), Range.end());
1030 236 : }
1031 0 :
1032 519 : /// Provide wrappers to std::for_each which take ranges instead of having to
1033 0 : /// pass begin/end explicitly.
1034 519 : template <typename R, typename UnaryPredicate>
1035 75 : UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
1036 80 : return std::for_each(adl_begin(Range), adl_end(Range), P);
1037 0 : }
1038 156 :
1039 363 : /// Provide wrappers to std::all_of which take ranges instead of having to pass
1040 207 : /// begin/end explicitly.
1041 1 : template <typename R, typename UnaryPredicate>
1042 1340582 : bool all_of(R &&Range, UnaryPredicate P) {
1043 1374553 : return std::all_of(adl_begin(Range), adl_end(Range), P);
1044 70 : }
1045 8370 :
1046 8252 : /// Provide wrappers to std::any_of which take ranges instead of having to pass
1047 0 : /// begin/end explicitly.
1048 30 : template <typename R, typename UnaryPredicate>
1049 181018207 : bool any_of(R &&Range, UnaryPredicate P) {
1050 181018428 : return std::any_of(adl_begin(Range), adl_end(Range), P);
1051 902 : }
1052 973 :
1053 71 : /// Provide wrappers to std::none_of which take ranges instead of having to pass
1054 0 : /// begin/end explicitly.
1055 1663 : template <typename R, typename UnaryPredicate>
1056 1660 : bool none_of(R &&Range, UnaryPredicate P) {
1057 0 : return std::none_of(adl_begin(Range), adl_end(Range), P);
1058 110 : }
1059 110 :
1060 0 : /// Provide wrappers to std::find which take ranges instead of having to pass
1061 1565 : /// begin/end explicitly.
1062 367723 : template <typename R, typename T>
1063 367498 : auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
1064 5465706 : return std::find(adl_begin(Range), adl_end(Range), Val);
1065 210 : }
1066 3734 :
1067 8558 : /// Provide wrappers to std::find_if which take ranges instead of having to pass
1068 10186 : /// begin/end explicitly.
1069 3827 : template <typename R, typename UnaryPredicate>
1070 168882 : auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1071 221422 : return std::find_if(adl_begin(Range), adl_end(Range), P);
1072 0 : }
1073 1 :
1074 0 : template <typename R, typename UnaryPredicate>
1075 201703 : auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1076 218078 : return std::find_if_not(adl_begin(Range), adl_end(Range), P);
1077 16375 : }
1078 0 :
1079 21636 : /// Provide wrappers to std::remove_if which take ranges instead of having to
1080 21824 : /// pass begin/end explicitly.
1081 13633478 : template <typename R, typename UnaryPredicate>
1082 14611339 : auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1083 952181 : return std::remove_if(adl_begin(Range), adl_end(Range), P);
1084 866124 : }
1085 688097 :
1086 688150 : /// Provide wrappers to std::copy_if which take ranges instead of having to
1087 : /// pass begin/end explicitly.
1088 141150 : template <typename R, typename OutputIt, typename UnaryPredicate>
1089 154311 : OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
1090 3181 : return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
1091 165055 : }
1092 53003 :
1093 0 : template <typename R, typename OutputIt>
1094 0 : OutputIt copy(R &&Range, OutputIt Out) {
1095 0 : return std::copy(adl_begin(Range), adl_end(Range), Out);
1096 52 : }
1097 52 :
1098 53177 : /// Wrapper function around std::find to detect if an element exists
1099 53209 : /// in a container.
1100 1073 : template <typename R, typename E>
1101 5723294 : bool is_contained(R &&Range, const E &Element) {
1102 28582614 : return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
1103 50766 : }
1104 45885 :
1105 32 : /// Wrapper function around std::count to count the number of times an element
1106 0 : /// \p Element occurs in the given range \p Range.
1107 0 : template <typename R, typename E>
1108 2 : auto count(R &&Range, const E &Element) ->
1109 0 : typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1110 18 : return std::count(adl_begin(Range), adl_end(Range), Element);
1111 0 : }
1112 0 :
1113 1254 : /// Wrapper function around std::count_if to count the number of times an
1114 1254 : /// element satisfying a given predicate occurs in a range.
1115 0 : template <typename R, typename UnaryPredicate>
1116 0 : auto count_if(R &&Range, UnaryPredicate P) ->
1117 0 : typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
1118 72 : return std::count_if(adl_begin(Range), adl_end(Range), P);
1119 725108 : }
1120 725108 :
1121 12884 : /// Wrapper function around std::transform to apply a function to a range and
1122 6194998 : /// store the result elsewhere.
1123 829 : template <typename R, typename OutputIt, typename UnaryPredicate>
1124 112 : OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
1125 462 : return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
1126 0 : }
1127 0 :
1128 : /// Provide wrappers to std::partition which take ranges instead of having to
1129 0 : /// pass begin/end explicitly.
1130 6658 : template <typename R, typename UnaryPredicate>
1131 1 : auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
1132 0 : return std::partition(adl_begin(Range), adl_end(Range), P);
1133 0 : }
1134 :
1135 10 : /// Provide wrappers to std::lower_bound which take ranges instead of having to
1136 10 : /// pass begin/end explicitly.
1137 0 : template <typename R, typename ForwardIt>
1138 16078 : auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1139 0 : return std::lower_bound(adl_begin(Range), adl_end(Range), I);
1140 : }
1141 70361 :
1142 58289 : template <typename R, typename ForwardIt, typename Compare>
1143 0 : auto lower_bound(R &&Range, ForwardIt I, Compare C)
1144 18 : -> decltype(adl_begin(Range)) {
1145 83185 : return std::lower_bound(adl_begin(Range), adl_end(Range), I, C);
1146 : }
1147 0 :
1148 0 : /// Provide wrappers to std::upper_bound which take ranges instead of having to
1149 : /// pass begin/end explicitly.
1150 0 : template <typename R, typename ForwardIt>
1151 2344 : auto upper_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
1152 : return std::upper_bound(adl_begin(Range), adl_end(Range), I);
1153 0 : }
1154 0 :
1155 0 : template <typename R, typename ForwardIt, typename Compare>
1156 0 : auto upper_bound(R &&Range, ForwardIt I, Compare C)
1157 72 : -> decltype(adl_begin(Range)) {
1158 116 : return std::upper_bound(adl_begin(Range), adl_end(Range), I, C);
1159 0 : }
1160 0 : /// Wrapper function around std::equal to detect if all elements
1161 0 : /// in a container are same.
1162 196124 : template <typename R>
1163 0 : bool is_splat(R &&Range) {
1164 0 : size_t range_size = size(Range);
1165 0 : return range_size != 0 && (range_size == 1 ||
1166 0 : std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
1167 0 : }
1168 :
1169 : /// Given a range of type R, iterate the entire range and return a
1170 : /// SmallVector with elements of the vector. This is useful, for example,
1171 : /// when you want to iterate a range and then sort the results.
1172 : template <unsigned Size, typename R>
1173 : SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
1174 2 : to_vector(R &&Range) {
1175 2 : return {adl_begin(Range), adl_end(Range)};
1176 : }
1177 :
1178 : /// Provide a container algorithm similar to C++ Library Fundamentals v2's
1179 : /// `erase_if` which is equivalent to:
1180 : ///
1181 : /// C.erase(remove_if(C, pred), C.end());
1182 : ///
1183 : /// This version works for any container with an erase method call accepting
1184 : /// two iterators.
1185 : template <typename Container, typename UnaryPredicate>
1186 4134 : void erase_if(Container &C, UnaryPredicate P) {
1187 4134 : C.erase(remove_if(C, P), C.end());
1188 4134 : }
1189 :
1190 : //===----------------------------------------------------------------------===//
1191 : // Extra additions to <memory>
1192 : //===----------------------------------------------------------------------===//
1193 0 :
1194 : // Implement make_unique according to N3656.
1195 327208 :
1196 655668 : /// Constructs a `new T()` with the given args and returns a
1197 327209 : /// `unique_ptr<T>` which owns the object.
1198 272253 : ///
1199 540170 : /// Example:
1200 304362 : ///
1201 37514 : /// auto p = make_unique<int>();
1202 40756 : /// auto p = make_unique<std::tuple<int, int>>(0, 1);
1203 3242 : template <class T, class... Args>
1204 52974 : typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
1205 45509174 : make_unique(Args &&... args) {
1206 53173512 : return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
1207 0 : }
1208 504 :
1209 504 : /// Constructs a `new T[n]` with the given args and returns a
1210 63 : /// `unique_ptr<T[]>` which owns the object.
1211 469 : ///
1212 563197 : /// \param n size of the new array.
1213 9787818 : ///
1214 9803861 : /// Example:
1215 79837 : ///
1216 240 : /// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
1217 21 : template <class T>
1218 60023 : typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
1219 0 : std::unique_ptr<T>>::type
1220 170161 : make_unique(size_t n) {
1221 2643183 : return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
1222 445 : }
1223 192 :
1224 192 : /// This function isn't used and is only here to provide better compile errors.
1225 333371 : template <class T, class... Args>
1226 343032 : typename std::enable_if<std::extent<T>::value != 0>::type
1227 336114 : make_unique(Args &&...) = delete;
1228 655708 :
1229 2964 : struct FreeDeleter {
1230 16738 : void operator()(void* v) {
1231 274 : ::free(v);
1232 203 : }
1233 549612 : };
1234 33548 :
1235 8615 : template<typename First, typename Second>
1236 10752 : struct pair_hash {
1237 6 : size_t operator()(const std::pair<First, Second> &P) const {
1238 6521184 : return std::hash<First>()(P.first) * 31 + std::hash<Second>()(P.second);
1239 2354 : }
1240 47287 : };
1241 349 :
1242 349 : /// A functor like C++14's std::less<void> in its absence.
1243 156 : struct less {
1244 944 : template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1245 122981 : return std::forward<A>(a) < std::forward<B>(b);
1246 18256 : }
1247 4 : };
1248 28 :
1249 24 : /// A functor like C++14's std::equal<void> in its absence.
1250 26 : struct equal {
1251 5041 : template <typename A, typename B> bool operator()(A &&a, B &&b) const {
1252 83722 : return std::forward<A>(a) == std::forward<B>(b);
1253 66 : }
1254 808 : };
1255 4730 :
1256 0 : /// Binary functor that adapts to any other binary functor after dereferencing
1257 3094 : /// operands.
1258 3460 : template <typename T> struct deref {
1259 420 : T func;
1260 491 :
1261 84 : // Could be further improved to cope with non-derivable functors and
1262 118 : // non-binary functors (should be a variadic template member function
1263 118 : // operator()).
1264 2 : template <typename A, typename B>
1265 1412 : auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
1266 2369 : assert(lhs);
1267 0 : assert(rhs);
1268 14 : return func(*lhs, *rhs);
1269 421048 : }
1270 843746 : };
1271 21 :
1272 21 : namespace detail {
1273 44 :
1274 117 : template <typename R> class enumerator_iter;
1275 116 :
1276 216 : template <typename R> struct result_pair {
1277 38932 : friend class enumerator_iter<R>;
1278 40 :
1279 77 : result_pair() = default;
1280 194 : result_pair(std::size_t Index, IterOfRange<R> Iter)
1281 92 : : Index(Index), Iter(Iter) {}
1282 0 :
1283 2 : result_pair<R> &operator=(const result_pair<R> &Other) {
1284 961 : Index = Other.Index;
1285 91915394 : Iter = Other.Iter;
1286 37 : return *this;
1287 61 : }
1288 24 :
1289 768 : std::size_t index() const { return Index; }
1290 1055 : const ValueOfRange<R> &value() const { return *Iter; }
1291 26476 : ValueOfRange<R> &value() { return *Iter; }
1292 414 :
1293 760 : private:
1294 765 : std::size_t Index = std::numeric_limits<std::size_t>::max();
1295 219 : IterOfRange<R> Iter;
1296 740 : };
1297 576 :
1298 29 : template <typename R>
1299 53351 : class enumerator_iter
1300 0 : : public iterator_facade_base<
1301 3060000 : enumerator_iter<R>, std::forward_iterator_tag, result_pair<R>,
1302 1118 : typename std::iterator_traits<IterOfRange<R>>::difference_type,
1303 2798 : typename std::iterator_traits<IterOfRange<R>>::pointer,
1304 1334 : typename std::iterator_traits<IterOfRange<R>>::reference> {
1305 1617 : using result_type = result_pair<R>;
1306 566 :
1307 37 : public:
1308 55 : explicit enumerator_iter(IterOfRange<R> EndIter)
1309 36 : : Result(std::numeric_limits<size_t>::max(), EndIter) {}
1310 2 :
1311 2 : enumerator_iter(std::size_t Index, IterOfRange<R> Iter)
1312 0 : : Result(Index, Iter) {}
1313 52578 :
1314 1307440 : result_type &operator*() { return Result; }
1315 182 : const result_type &operator*() const { return Result; }
1316 61 :
1317 7 : enumerator_iter<R> &operator++() {
1318 0 : assert(Result.Index != std::numeric_limits<size_t>::max());
1319 308 : ++Result.Iter;
1320 502 : ++Result.Index;
1321 210 : return *this;
1322 9358 : }
1323 10619 :
1324 0 : bool operator==(const enumerator_iter<R> &RHS) const {
1325 628 : // Don't compare indices here, only iterators. It's possible for an end
1326 628 : // iterator to have different indices depending on whether it was created
1327 0 : // by calling std::end() versus incrementing a valid iterator.
1328 33030 : return Result.Iter == RHS.Result.Iter;
1329 67190 : }
1330 4542 :
1331 424 : enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
1332 1343 : Result = Other.Result;
1333 1838 : return *this;
1334 0 : }
1335 129 :
1336 258 : private:
1337 2856 : result_type Result;
1338 6445 : };
1339 6648 :
1340 3762 : template <typename R> class enumerator {
1341 213 : public:
1342 213 : explicit enumerator(R &&Range) : TheRange(std::forward<R>(Range)) {}
1343 0 :
1344 261 : enumerator_iter<R> begin() {
1345 522 : return enumerator_iter<R>(0, std::begin(TheRange));
1346 0 : }
1347 30 :
1348 2628 : enumerator_iter<R> end() {
1349 2598 : return enumerator_iter<R>(std::end(TheRange));
1350 1852 : }
1351 1859 :
1352 0 : private:
1353 261 : R TheRange;
1354 261 : };
1355 41 :
1356 307 : } // end namespace detail
1357 0 :
1358 28 : /// Given an input range, returns a new range whose values are are pair (A,B)
1359 358 : /// such that A is the 0-based index of the item in the sequence, and B is
1360 648 : /// the value from the original sequence. Example:
1361 0 : ///
1362 196 : /// std::vector<char> Items = {'A', 'B', 'C', 'D'};
1363 196 : /// for (auto X : enumerate(Items)) {
1364 13 : /// printf("Item %d - %c\n", X.index(), X.value());
1365 342 : /// }
1366 658 : ///
1367 0 : /// Output:
1368 0 : /// Item 0 - A
1369 0 : /// Item 1 - B
1370 0 : /// Item 2 - C
1371 0 : /// Item 3 - D
1372 0 : ///
1373 0 : template <typename R> detail::enumerator<R> enumerate(R &&TheRange) {
1374 373782 : return detail::enumerator<R>(std::forward<R>(TheRange));
1375 0 : }
1376 0 :
1377 0 : namespace detail {
1378 0 :
1379 0 : template <typename F, typename Tuple, std::size_t... I>
1380 0 : auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
1381 : -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
1382 0 : return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
1383 0 : }
1384 0 :
1385 15 : } // end namespace detail
1386 0 :
1387 : /// Given an input tuple (a1, a2, ..., an), pass the arguments of the
1388 0 : /// tuple variadically to f as if by calling f(a1, a2, ..., an) and
1389 28 : /// return the result.
1390 201 : template <typename F, typename Tuple>
1391 0 : auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
1392 0 : std::forward<F>(f), std::forward<Tuple>(t),
1393 0 : build_index_impl<
1394 0 : std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
1395 0 : using Indices = build_index_impl<
1396 0 : std::tuple_size<typename std::decay<Tuple>::type>::value>;
1397 2 :
1398 2 : return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
1399 11 : Indices{});
1400 0 : }
1401 0 :
1402 0 : } // end namespace llvm
1403 1358 :
1404 1358 : #endif // LLVM_ADT_STLEXTRAS_H
|
