Update prebuilt Clang to r416183b from Android.
https://android.googlesource.com/platform/prebuilts/clang/host/
linux-x86/+/06a71ddac05c22edb2d10b590e1769b3f8619bef
clang 12.0.5 (based on r416183b) from build 7284624.
Change-Id: I277a316abcf47307562d8b748b84870f31a72866
Signed-off-by: Olivier Deprez <olivier.deprez@arm.com>
diff --git a/linux-x64/clang/include/llvm/ADT/STLExtras.h b/linux-x64/clang/include/llvm/ADT/STLExtras.h
index 81dce01..c8c1aff 100644
--- a/linux-x64/clang/include/llvm/ADT/STLExtras.h
+++ b/linux-x64/clang/include/llvm/ADT/STLExtras.h
@@ -17,7 +17,6 @@
#define LLVM_ADT_STLEXTRAS_H
#include "llvm/ADT/Optional.h"
-#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Config/abi-breaking.h"
@@ -80,6 +79,79 @@
typename std::add_const<T>::type>::type;
};
+/// Utilities for detecting if a given trait holds for some set of arguments
+/// 'Args'. For example, the given trait could be used to detect if a given type
+/// has a copy assignment operator:
+/// template<class T>
+/// using has_copy_assign_t = decltype(std::declval<T&>()
+/// = std::declval<const T&>());
+/// bool fooHasCopyAssign = is_detected<has_copy_assign_t, FooClass>::value;
+namespace detail {
+template <typename...> using void_t = void;
+template <class, template <class...> class Op, class... Args> struct detector {
+ using value_t = std::false_type;
+};
+template <template <class...> class Op, class... Args>
+struct detector<void_t<Op<Args...>>, Op, Args...> {
+ using value_t = std::true_type;
+};
+} // end namespace detail
+
+template <template <class...> class Op, class... Args>
+using is_detected = typename detail::detector<void, Op, Args...>::value_t;
+
+/// Check if a Callable type can be invoked with the given set of arg types.
+namespace detail {
+template <typename Callable, typename... Args>
+using is_invocable =
+ decltype(std::declval<Callable &>()(std::declval<Args>()...));
+} // namespace detail
+
+template <typename Callable, typename... Args>
+using is_invocable = is_detected<detail::is_invocable, Callable, Args...>;
+
+/// This class provides various trait information about a callable object.
+/// * To access the number of arguments: Traits::num_args
+/// * To access the type of an argument: Traits::arg_t<Index>
+/// * To access the type of the result: Traits::result_t
+template <typename T, bool isClass = std::is_class<T>::value>
+struct function_traits : public function_traits<decltype(&T::operator())> {};
+
+/// Overload for class function types.
+template <typename ClassType, typename ReturnType, typename... Args>
+struct function_traits<ReturnType (ClassType::*)(Args...) const, false> {
+ /// The number of arguments to this function.
+ enum { num_args = sizeof...(Args) };
+
+ /// The result type of this function.
+ using result_t = ReturnType;
+
+ /// The type of an argument to this function.
+ template <size_t Index>
+ using arg_t = typename std::tuple_element<Index, std::tuple<Args...>>::type;
+};
+/// Overload for class function types.
+template <typename ClassType, typename ReturnType, typename... Args>
+struct function_traits<ReturnType (ClassType::*)(Args...), false>
+ : function_traits<ReturnType (ClassType::*)(Args...) const> {};
+/// Overload for non-class function types.
+template <typename ReturnType, typename... Args>
+struct function_traits<ReturnType (*)(Args...), false> {
+ /// The number of arguments to this function.
+ enum { num_args = sizeof...(Args) };
+
+ /// The result type of this function.
+ using result_t = ReturnType;
+
+ /// The type of an argument to this function.
+ template <size_t i>
+ using arg_t = typename std::tuple_element<i, std::tuple<Args...>>::type;
+};
+/// Overload for non-class function type references.
+template <typename ReturnType, typename... Args>
+struct function_traits<ReturnType (&)(Args...), false>
+ : public function_traits<ReturnType (*)(Args...)> {};
+
//===----------------------------------------------------------------------===//
// Extra additions to <functional>
//===----------------------------------------------------------------------===//
@@ -95,18 +167,6 @@
}
};
-template <class Ty> struct less_ptr {
- bool operator()(const Ty* left, const Ty* right) const {
- return *left < *right;
- }
-};
-
-template <class Ty> struct greater_ptr {
- bool operator()(const Ty* left, const Ty* right) const {
- return *right < *left;
- }
-};
-
/// An efficient, type-erasing, non-owning reference to a callable. This is
/// intended for use as the type of a function parameter that is not used
/// after the function in question returns.
@@ -131,10 +191,17 @@
function_ref(std::nullptr_t) {}
template <typename Callable>
- function_ref(Callable &&callable,
- typename std::enable_if<
- !std::is_same<typename std::remove_reference<Callable>::type,
- function_ref>::value>::type * = nullptr)
+ function_ref(
+ Callable &&callable,
+ // This is not the copy-constructor.
+ std::enable_if_t<
+ !std::is_same<std::remove_cv_t<std::remove_reference_t<Callable>>,
+ function_ref>::value> * = nullptr,
+ // Functor must be callable and return a suitable type.
+ std::enable_if_t<std::is_void<Ret>::value ||
+ std::is_convertible<decltype(std::declval<Callable>()(
+ std::declval<Params>()...)),
+ Ret>::value> * = nullptr)
: callback(callback_fn<typename std::remove_reference<Callable>::type>),
callable(reinterpret_cast<intptr_t>(&callable)) {}
@@ -142,18 +209,9 @@
return callback(callable, std::forward<Params>(params)...);
}
- operator bool() const { return callback; }
+ explicit operator bool() const { return callback; }
};
-// deleter - Very very very simple method that is used to invoke operator
-// delete on something. It is used like this:
-//
-// for_each(V.begin(), B.end(), deleter<Interval>);
-template <class T>
-inline void deleter(T *Ptr) {
- delete Ptr;
-}
-
//===----------------------------------------------------------------------===//
// Extra additions to <iterator>
//===----------------------------------------------------------------------===//
@@ -163,16 +221,14 @@
using std::begin;
template <typename ContainerTy>
-auto adl_begin(ContainerTy &&container)
- -> decltype(begin(std::forward<ContainerTy>(container))) {
+decltype(auto) adl_begin(ContainerTy &&container) {
return begin(std::forward<ContainerTy>(container));
}
using std::end;
template <typename ContainerTy>
-auto adl_end(ContainerTy &&container)
- -> decltype(end(std::forward<ContainerTy>(container))) {
+decltype(auto) adl_end(ContainerTy &&container) {
return end(std::forward<ContainerTy>(container));
}
@@ -187,14 +243,12 @@
} // end namespace adl_detail
template <typename ContainerTy>
-auto adl_begin(ContainerTy &&container)
- -> decltype(adl_detail::adl_begin(std::forward<ContainerTy>(container))) {
+decltype(auto) adl_begin(ContainerTy &&container) {
return adl_detail::adl_begin(std::forward<ContainerTy>(container));
}
template <typename ContainerTy>
-auto adl_end(ContainerTy &&container)
- -> decltype(adl_detail::adl_end(std::forward<ContainerTy>(container))) {
+decltype(auto) adl_end(ContainerTy &&container) {
return adl_detail::adl_end(std::forward<ContainerTy>(container));
}
@@ -210,6 +264,19 @@
return adl_begin(RangeOrContainer) == adl_end(RangeOrContainer);
}
+/// Returns true if the given container only contains a single element.
+template <typename ContainerTy> bool hasSingleElement(ContainerTy &&C) {
+ auto B = std::begin(C), E = std::end(C);
+ return B != E && std::next(B) == E;
+}
+
+/// Return a range covering \p RangeOrContainer with the first N elements
+/// excluded.
+template <typename T> auto drop_begin(T &&RangeOrContainer, size_t N) {
+ return make_range(std::next(adl_begin(RangeOrContainer), N),
+ adl_end(RangeOrContainer));
+}
+
// mapped_iterator - This is a simple iterator adapter that causes a function to
// be applied whenever operator* is invoked on the iterator.
@@ -227,7 +294,7 @@
ItTy getCurrent() { return this->I; }
- FuncReturnTy operator*() { return F(*this->I); }
+ FuncReturnTy operator*() const { return F(*this->I); }
private:
FuncTy F;
@@ -241,9 +308,7 @@
}
template <class ContainerTy, class FuncTy>
-auto map_range(ContainerTy &&C, FuncTy F)
- -> decltype(make_range(map_iterator(C.begin(), F),
- map_iterator(C.end(), F))) {
+auto map_range(ContainerTy &&C, FuncTy F) {
return make_range(map_iterator(C.begin(), F), map_iterator(C.end(), F));
}
@@ -271,8 +336,7 @@
// Note that the container must have rbegin()/rend() methods for this to work.
template <typename ContainerTy>
auto reverse(ContainerTy &&C,
- typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
- nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
+ std::enable_if_t<has_rbegin<ContainerTy>::value> * = nullptr) {
return make_range(C.rbegin(), C.rend());
}
@@ -286,11 +350,8 @@
// Note that the container must have begin()/end() methods which return
// bidirectional iterators for this to work.
template <typename ContainerTy>
-auto reverse(
- ContainerTy &&C,
- typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
- -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
- llvm::make_reverse_iterator(std::begin(C)))) {
+auto reverse(ContainerTy &&C,
+ std::enable_if_t<!has_rbegin<ContainerTy>::value> * = nullptr) {
return make_range(llvm::make_reverse_iterator(std::end(C)),
llvm::make_reverse_iterator(std::begin(C)));
}
@@ -477,7 +538,7 @@
early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
using BaseT::operator*;
- typename BaseT::reference operator*() {
+ decltype(*std::declval<WrappedIteratorT>()) operator*() {
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
assert(!IsEarlyIncremented && "Cannot dereference twice!");
IsEarlyIncremented = true;
@@ -494,12 +555,12 @@
return *this;
}
- using BaseT::operator==;
- bool operator==(const early_inc_iterator_impl &RHS) const {
+ friend bool operator==(const early_inc_iterator_impl &LHS,
+ const early_inc_iterator_impl &RHS) {
#if LLVM_ENABLE_ABI_BREAKING_CHECKS
- assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
+ assert(!LHS.IsEarlyIncremented && "Cannot compare after dereferencing!");
#endif
- return BaseT::operator==(RHS);
+ return (const BaseT &)LHS == (const BaseT &)RHS;
}
};
@@ -530,10 +591,6 @@
template <typename R, typename UnaryPredicate>
bool any_of(R &&range, UnaryPredicate P);
-template <size_t... I> struct index_sequence;
-
-template <class... Ts> struct index_sequence_for;
-
namespace detail {
using std::declval;
@@ -568,38 +625,38 @@
std::tuple<Iters...> iterators;
protected:
- template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
+ template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
return value_type(*std::get<Ns>(iterators)...);
}
template <size_t... Ns>
- decltype(iterators) tup_inc(index_sequence<Ns...>) const {
+ decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
}
template <size_t... Ns>
- decltype(iterators) tup_dec(index_sequence<Ns...>) const {
+ decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
}
public:
zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
- value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
+ value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
const value_type operator*() const {
- return deref(index_sequence_for<Iters...>{});
+ return deref(std::index_sequence_for<Iters...>{});
}
ZipType &operator++() {
- iterators = tup_inc(index_sequence_for<Iters...>{});
+ iterators = tup_inc(std::index_sequence_for<Iters...>{});
return *reinterpret_cast<ZipType *>(this);
}
ZipType &operator--() {
static_assert(Base::IsBidirectional,
"All inner iterators must be at least bidirectional.");
- iterators = tup_dec(index_sequence_for<Iters...>{});
+ iterators = tup_dec(std::index_sequence_for<Iters...>{});
return *reinterpret_cast<ZipType *>(this);
}
};
@@ -618,7 +675,8 @@
template <typename... Iters>
class zip_shortest : public zip_common<zip_shortest<Iters...>, Iters...> {
template <size_t... Ns>
- bool test(const zip_shortest<Iters...> &other, index_sequence<Ns...>) const {
+ bool test(const zip_shortest<Iters...> &other,
+ std::index_sequence<Ns...>) const {
return all_of(std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
std::get<Ns>(other.iterators)...},
identity<bool>{});
@@ -630,7 +688,7 @@
zip_shortest(Iters &&... ts) : Base(std::forward<Iters>(ts)...) {}
bool operator==(const zip_shortest<Iters...> &other) const {
- return !test(other, index_sequence_for<Iters...>{});
+ return !test(other, std::index_sequence_for<Iters...>{});
}
};
@@ -646,18 +704,21 @@
private:
std::tuple<Args...> ts;
- template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
+ template <size_t... Ns>
+ iterator begin_impl(std::index_sequence<Ns...>) const {
return iterator(std::begin(std::get<Ns>(ts))...);
}
- template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
+ template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
return iterator(std::end(std::get<Ns>(ts))...);
}
public:
zippy(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
- iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
- iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
+ iterator begin() const {
+ return begin_impl(std::index_sequence_for<Args...>{});
+ }
+ iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
};
} // end namespace detail
@@ -681,16 +742,15 @@
namespace detail {
template <typename Iter>
-static Iter next_or_end(const Iter &I, const Iter &End) {
+Iter next_or_end(const Iter &I, const Iter &End) {
if (I == End)
return End;
return std::next(I);
}
template <typename Iter>
-static auto deref_or_none(const Iter &I, const Iter &End)
- -> llvm::Optional<typename std::remove_const<
- typename std::remove_reference<decltype(*I)>::type>::type> {
+auto deref_or_none(const Iter &I, const Iter &End) -> llvm::Optional<
+ std::remove_const_t<std::remove_reference_t<decltype(*I)>>> {
if (I == End)
return None;
return *I;
@@ -727,20 +787,20 @@
template <size_t... Ns>
bool test(const zip_longest_iterator<Iters...> &other,
- index_sequence<Ns...>) const {
+ std::index_sequence<Ns...>) const {
return llvm::any_of(
std::initializer_list<bool>{std::get<Ns>(this->iterators) !=
std::get<Ns>(other.iterators)...},
identity<bool>{});
}
- template <size_t... Ns> value_type deref(index_sequence<Ns...>) const {
+ template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
return value_type(
deref_or_none(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
}
template <size_t... Ns>
- decltype(iterators) tup_inc(index_sequence<Ns...>) const {
+ decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
return std::tuple<Iters...>(
next_or_end(std::get<Ns>(iterators), std::get<Ns>(end_iterators))...);
}
@@ -750,17 +810,19 @@
: iterators(std::forward<Iters>(ts.first)...),
end_iterators(std::forward<Iters>(ts.second)...) {}
- value_type operator*() { return deref(index_sequence_for<Iters...>{}); }
+ value_type operator*() { return deref(std::index_sequence_for<Iters...>{}); }
- value_type operator*() const { return deref(index_sequence_for<Iters...>{}); }
+ value_type operator*() const {
+ return deref(std::index_sequence_for<Iters...>{});
+ }
zip_longest_iterator<Iters...> &operator++() {
- iterators = tup_inc(index_sequence_for<Iters...>{});
+ iterators = tup_inc(std::index_sequence_for<Iters...>{});
return *this;
}
bool operator==(const zip_longest_iterator<Iters...> &other) const {
- return !test(other, index_sequence_for<Iters...>{});
+ return !test(other, std::index_sequence_for<Iters...>{});
}
};
@@ -777,12 +839,13 @@
private:
std::tuple<Args...> ts;
- template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) const {
+ template <size_t... Ns>
+ iterator begin_impl(std::index_sequence<Ns...>) const {
return iterator(std::make_pair(adl_begin(std::get<Ns>(ts)),
adl_end(std::get<Ns>(ts)))...);
}
- template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) const {
+ template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) const {
return iterator(std::make_pair(adl_end(std::get<Ns>(ts)),
adl_end(std::get<Ns>(ts)))...);
}
@@ -790,8 +853,10 @@
public:
zip_longest_range(Args &&... ts_) : ts(std::forward<Args>(ts_)...) {}
- iterator begin() const { return begin_impl(index_sequence_for<Args...>{}); }
- iterator end() const { return end_impl(index_sequence_for<Args...>{}); }
+ iterator begin() const {
+ return begin_impl(std::index_sequence_for<Args...>{});
+ }
+ iterator end() const { return end_impl(std::index_sequence_for<Args...>{}); }
};
} // namespace detail
@@ -847,7 +912,7 @@
/// Increments the first non-end iterator.
///
/// It is an error to call this with all iterators at the end.
- template <size_t... Ns> void increment(index_sequence<Ns...>) {
+ template <size_t... Ns> void increment(std::index_sequence<Ns...>) {
// Build a sequence of functions to increment each iterator if possible.
bool (concat_iterator::*IncrementHelperFns[])() = {
&concat_iterator::incrementHelper<Ns>...};
@@ -876,7 +941,7 @@
/// reference.
///
/// It is an error to call this with all iterators at the end.
- template <size_t... Ns> ValueT &get(index_sequence<Ns...>) const {
+ template <size_t... Ns> ValueT &get(std::index_sequence<Ns...>) const {
// Build a sequence of functions to get from iterator if possible.
ValueT *(concat_iterator::*GetHelperFns[])() const = {
&concat_iterator::getHelper<Ns>...};
@@ -890,7 +955,7 @@
}
public:
- /// Constructs an iterator from a squence of ranges.
+ /// Constructs an iterator from a sequence of ranges.
///
/// We need the full range to know how to switch between each of the
/// iterators.
@@ -901,11 +966,13 @@
using BaseT::operator++;
concat_iterator &operator++() {
- increment(index_sequence_for<IterTs...>());
+ increment(std::index_sequence_for<IterTs...>());
return *this;
}
- ValueT &operator*() const { return get(index_sequence_for<IterTs...>()); }
+ ValueT &operator*() const {
+ return get(std::index_sequence_for<IterTs...>());
+ }
bool operator==(const concat_iterator &RHS) const {
return Begins == RHS.Begins && Ends == RHS.Ends;
@@ -928,10 +995,10 @@
private:
std::tuple<RangeTs...> Ranges;
- template <size_t... Ns> iterator begin_impl(index_sequence<Ns...>) {
+ template <size_t... Ns> iterator begin_impl(std::index_sequence<Ns...>) {
return iterator(std::get<Ns>(Ranges)...);
}
- template <size_t... Ns> iterator end_impl(index_sequence<Ns...>) {
+ template <size_t... Ns> iterator end_impl(std::index_sequence<Ns...>) {
return iterator(make_range(std::end(std::get<Ns>(Ranges)),
std::end(std::get<Ns>(Ranges)))...);
}
@@ -940,8 +1007,8 @@
concat_range(RangeTs &&... Ranges)
: Ranges(std::forward<RangeTs>(Ranges)...) {}
- iterator begin() { return begin_impl(index_sequence_for<RangeTs...>{}); }
- iterator end() { return end_impl(index_sequence_for<RangeTs...>{}); }
+ iterator begin() { return begin_impl(std::index_sequence_for<RangeTs...>{}); }
+ iterator end() { return end_impl(std::index_sequence_for<RangeTs...>{}); }
};
} // end namespace detail
@@ -957,6 +1024,243 @@
std::forward<RangeTs>(Ranges)...);
}
+/// A utility class used to implement an iterator that contains some base object
+/// and an index. The iterator moves the index but keeps the base constant.
+template <typename DerivedT, typename BaseT, typename T,
+ typename PointerT = T *, typename ReferenceT = T &>
+class indexed_accessor_iterator
+ : public llvm::iterator_facade_base<DerivedT,
+ std::random_access_iterator_tag, T,
+ std::ptrdiff_t, PointerT, ReferenceT> {
+public:
+ ptrdiff_t operator-(const indexed_accessor_iterator &rhs) const {
+ assert(base == rhs.base && "incompatible iterators");
+ return index - rhs.index;
+ }
+ bool operator==(const indexed_accessor_iterator &rhs) const {
+ return base == rhs.base && index == rhs.index;
+ }
+ bool operator<(const indexed_accessor_iterator &rhs) const {
+ assert(base == rhs.base && "incompatible iterators");
+ return index < rhs.index;
+ }
+
+ DerivedT &operator+=(ptrdiff_t offset) {
+ this->index += offset;
+ return static_cast<DerivedT &>(*this);
+ }
+ DerivedT &operator-=(ptrdiff_t offset) {
+ this->index -= offset;
+ return static_cast<DerivedT &>(*this);
+ }
+
+ /// Returns the current index of the iterator.
+ ptrdiff_t getIndex() const { return index; }
+
+ /// Returns the current base of the iterator.
+ const BaseT &getBase() const { return base; }
+
+protected:
+ indexed_accessor_iterator(BaseT base, ptrdiff_t index)
+ : base(base), index(index) {}
+ BaseT base;
+ ptrdiff_t index;
+};
+
+namespace detail {
+/// The class represents the base of a range of indexed_accessor_iterators. It
+/// provides support for many different range functionalities, e.g.
+/// drop_front/slice/etc.. Derived range classes must implement the following
+/// static methods:
+/// * ReferenceT dereference_iterator(const BaseT &base, ptrdiff_t index)
+/// - Dereference an iterator pointing to the base object at the given
+/// index.
+/// * BaseT offset_base(const BaseT &base, ptrdiff_t index)
+/// - Return a new base that is offset from the provide base by 'index'
+/// elements.
+template <typename DerivedT, typename BaseT, typename T,
+ typename PointerT = T *, typename ReferenceT = T &>
+class indexed_accessor_range_base {
+public:
+ using RangeBaseT =
+ indexed_accessor_range_base<DerivedT, BaseT, T, PointerT, ReferenceT>;
+
+ /// An iterator element of this range.
+ class iterator : public indexed_accessor_iterator<iterator, BaseT, T,
+ PointerT, ReferenceT> {
+ public:
+ // Index into this iterator, invoking a static method on the derived type.
+ ReferenceT operator*() const {
+ return DerivedT::dereference_iterator(this->getBase(), this->getIndex());
+ }
+
+ private:
+ iterator(BaseT owner, ptrdiff_t curIndex)
+ : indexed_accessor_iterator<iterator, BaseT, T, PointerT, ReferenceT>(
+ owner, curIndex) {}
+
+ /// Allow access to the constructor.
+ friend indexed_accessor_range_base<DerivedT, BaseT, T, PointerT,
+ ReferenceT>;
+ };
+
+ indexed_accessor_range_base(iterator begin, iterator end)
+ : base(offset_base(begin.getBase(), begin.getIndex())),
+ count(end.getIndex() - begin.getIndex()) {}
+ indexed_accessor_range_base(const iterator_range<iterator> &range)
+ : indexed_accessor_range_base(range.begin(), range.end()) {}
+ indexed_accessor_range_base(BaseT base, ptrdiff_t count)
+ : base(base), count(count) {}
+
+ iterator begin() const { return iterator(base, 0); }
+ iterator end() const { return iterator(base, count); }
+ ReferenceT operator[](unsigned index) const {
+ assert(index < size() && "invalid index for value range");
+ return DerivedT::dereference_iterator(base, index);
+ }
+ ReferenceT front() const {
+ assert(!empty() && "expected non-empty range");
+ return (*this)[0];
+ }
+ ReferenceT back() const {
+ assert(!empty() && "expected non-empty range");
+ return (*this)[size() - 1];
+ }
+
+ /// Compare this range with another.
+ template <typename OtherT> bool operator==(const OtherT &other) const {
+ return size() ==
+ static_cast<size_t>(std::distance(other.begin(), other.end())) &&
+ std::equal(begin(), end(), other.begin());
+ }
+ template <typename OtherT> bool operator!=(const OtherT &other) const {
+ return !(*this == other);
+ }
+
+ /// Return the size of this range.
+ size_t size() const { return count; }
+
+ /// Return if the range is empty.
+ bool empty() const { return size() == 0; }
+
+ /// Drop the first N elements, and keep M elements.
+ DerivedT slice(size_t n, size_t m) const {
+ assert(n + m <= size() && "invalid size specifiers");
+ return DerivedT(offset_base(base, n), m);
+ }
+
+ /// Drop the first n elements.
+ DerivedT drop_front(size_t n = 1) const {
+ assert(size() >= n && "Dropping more elements than exist");
+ return slice(n, size() - n);
+ }
+ /// Drop the last n elements.
+ DerivedT drop_back(size_t n = 1) const {
+ assert(size() >= n && "Dropping more elements than exist");
+ return DerivedT(base, size() - n);
+ }
+
+ /// Take the first n elements.
+ DerivedT take_front(size_t n = 1) const {
+ return n < size() ? drop_back(size() - n)
+ : static_cast<const DerivedT &>(*this);
+ }
+
+ /// Take the last n elements.
+ DerivedT take_back(size_t n = 1) const {
+ return n < size() ? drop_front(size() - n)
+ : static_cast<const DerivedT &>(*this);
+ }
+
+ /// Allow conversion to any type accepting an iterator_range.
+ template <typename RangeT, typename = std::enable_if_t<std::is_constructible<
+ RangeT, iterator_range<iterator>>::value>>
+ operator RangeT() const {
+ return RangeT(iterator_range<iterator>(*this));
+ }
+
+ /// Returns the base of this range.
+ const BaseT &getBase() const { return base; }
+
+private:
+ /// Offset the given base by the given amount.
+ static BaseT offset_base(const BaseT &base, size_t n) {
+ return n == 0 ? base : DerivedT::offset_base(base, n);
+ }
+
+protected:
+ indexed_accessor_range_base(const indexed_accessor_range_base &) = default;
+ indexed_accessor_range_base(indexed_accessor_range_base &&) = default;
+ indexed_accessor_range_base &
+ operator=(const indexed_accessor_range_base &) = default;
+
+ /// The base that owns the provided range of values.
+ BaseT base;
+ /// The size from the owning range.
+ ptrdiff_t count;
+};
+} // end namespace detail
+
+/// This class provides an implementation of a range of
+/// indexed_accessor_iterators where the base is not indexable. Ranges with
+/// bases that are offsetable should derive from indexed_accessor_range_base
+/// instead. Derived range classes are expected to implement the following
+/// static method:
+/// * ReferenceT dereference(const BaseT &base, ptrdiff_t index)
+/// - Dereference an iterator pointing to a parent base at the given index.
+template <typename DerivedT, typename BaseT, typename T,
+ typename PointerT = T *, typename ReferenceT = T &>
+class indexed_accessor_range
+ : public detail::indexed_accessor_range_base<
+ DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT> {
+public:
+ indexed_accessor_range(BaseT base, ptrdiff_t startIndex, ptrdiff_t count)
+ : detail::indexed_accessor_range_base<
+ DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT, ReferenceT>(
+ std::make_pair(base, startIndex), count) {}
+ using detail::indexed_accessor_range_base<
+ DerivedT, std::pair<BaseT, ptrdiff_t>, T, PointerT,
+ ReferenceT>::indexed_accessor_range_base;
+
+ /// Returns the current base of the range.
+ const BaseT &getBase() const { return this->base.first; }
+
+ /// Returns the current start index of the range.
+ ptrdiff_t getStartIndex() const { return this->base.second; }
+
+ /// See `detail::indexed_accessor_range_base` for details.
+ static std::pair<BaseT, ptrdiff_t>
+ offset_base(const std::pair<BaseT, ptrdiff_t> &base, ptrdiff_t index) {
+ // We encode the internal base as a pair of the derived base and a start
+ // index into the derived base.
+ return std::make_pair(base.first, base.second + index);
+ }
+ /// See `detail::indexed_accessor_range_base` for details.
+ static ReferenceT
+ dereference_iterator(const std::pair<BaseT, ptrdiff_t> &base,
+ ptrdiff_t index) {
+ return DerivedT::dereference(base.first, base.second + index);
+ }
+};
+
+/// Given a container of pairs, return a range over the first elements.
+template <typename ContainerTy> auto make_first_range(ContainerTy &&c) {
+ return llvm::map_range(
+ std::forward<ContainerTy>(c),
+ [](decltype((*std::begin(c))) elt) -> decltype((elt.first)) {
+ return elt.first;
+ });
+}
+
+/// Given a container of pairs, return a range over the second elements.
+template <typename ContainerTy> auto make_second_range(ContainerTy &&c) {
+ return llvm::map_range(
+ std::forward<ContainerTy>(c),
+ [](decltype((*std::begin(c))) elt) -> decltype((elt.second)) {
+ return elt.second;
+ });
+}
+
//===----------------------------------------------------------------------===//
// Extra additions to <utility>
//===----------------------------------------------------------------------===//
@@ -984,34 +1288,11 @@
FuncTy func;
template <typename T>
- auto operator()(const T &lhs, const T &rhs) const
- -> decltype(func(lhs.first, rhs.first)) {
+ decltype(auto) operator()(const T &lhs, const T &rhs) const {
return func(lhs.first, rhs.first);
}
};
-// A subset of N3658. More stuff can be added as-needed.
-
-/// Represents a compile-time sequence of integers.
-template <class T, T... I> struct integer_sequence {
- using value_type = T;
-
- static constexpr size_t size() { return sizeof...(I); }
-};
-
-/// Alias for the common case of a sequence of size_ts.
-template <size_t... I>
-struct index_sequence : integer_sequence<std::size_t, I...> {};
-
-template <std::size_t N, std::size_t... I>
-struct build_index_impl : build_index_impl<N - 1, N - 1, I...> {};
-template <std::size_t... I>
-struct build_index_impl<0, I...> : index_sequence<I...> {};
-
-/// Creates a compile-time integer sequence for a parameter pack.
-template <class... Ts>
-struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
-
/// Utility type to build an inheritance chain that makes it easy to rank
/// overload candidates.
template <int N> struct rank : rank<N - 1> {};
@@ -1045,6 +1326,16 @@
// Extra additions for arrays
//===----------------------------------------------------------------------===//
+// We have a copy here so that LLVM behaves the same when using different
+// standard libraries.
+template <class Iterator, class RNG>
+void shuffle(Iterator first, Iterator last, RNG &&g) {
+ // It would be better to use a std::uniform_int_distribution,
+ // but that would be stdlib dependent.
+ for (auto size = last - first; size > 1; ++first, (void)--size)
+ std::iter_swap(first, first + g() % size);
+}
+
/// Find the length of an array.
template <class T, std::size_t N>
constexpr inline size_t array_lengthof(T (&)[N]) {
@@ -1071,6 +1362,23 @@
return array_pod_sort_comparator<T>;
}
+#ifdef EXPENSIVE_CHECKS
+namespace detail {
+
+inline unsigned presortShuffleEntropy() {
+ static unsigned Result(std::random_device{}());
+ return Result;
+}
+
+template <class IteratorTy>
+inline void presortShuffle(IteratorTy Start, IteratorTy End) {
+ std::mt19937 Generator(presortShuffleEntropy());
+ std::shuffle(Start, End, Generator);
+}
+
+} // end namespace detail
+#endif
+
/// array_pod_sort - This sorts an array with the specified start and end
/// extent. This is just like std::sort, except that it calls qsort instead of
/// using an inlined template. qsort is slightly slower than std::sort, but
@@ -1092,8 +1400,7 @@
auto NElts = End - Start;
if (NElts <= 1) return;
#ifdef EXPENSIVE_CHECKS
- std::mt19937 Generator(std::random_device{}());
- std::shuffle(Start, End, Generator);
+ detail::presortShuffle<IteratorTy>(Start, End);
#endif
qsort(&*Start, NElts, sizeof(*Start), get_array_pod_sort_comparator(*Start));
}
@@ -1109,24 +1416,42 @@
auto NElts = End - Start;
if (NElts <= 1) return;
#ifdef EXPENSIVE_CHECKS
- std::mt19937 Generator(std::random_device{}());
- std::shuffle(Start, End, Generator);
+ detail::presortShuffle<IteratorTy>(Start, End);
#endif
qsort(&*Start, NElts, sizeof(*Start),
reinterpret_cast<int (*)(const void *, const void *)>(Compare));
}
+namespace detail {
+template <typename T>
+// We can use qsort if the iterator type is a pointer and the underlying value
+// is trivially copyable.
+using sort_trivially_copyable = conjunction<
+ std::is_pointer<T>,
+ std::is_trivially_copyable<typename std::iterator_traits<T>::value_type>>;
+} // namespace detail
+
// Provide wrappers to std::sort which shuffle the elements before sorting
// to help uncover non-deterministic behavior (PR35135).
-template <typename IteratorTy>
+template <typename IteratorTy,
+ std::enable_if_t<!detail::sort_trivially_copyable<IteratorTy>::value,
+ int> = 0>
inline void sort(IteratorTy Start, IteratorTy End) {
#ifdef EXPENSIVE_CHECKS
- std::mt19937 Generator(std::random_device{}());
- std::shuffle(Start, End, Generator);
+ detail::presortShuffle<IteratorTy>(Start, End);
#endif
std::sort(Start, End);
}
+// Forward trivially copyable types to array_pod_sort. This avoids a large
+// amount of code bloat for a minor performance hit.
+template <typename IteratorTy,
+ std::enable_if_t<detail::sort_trivially_copyable<IteratorTy>::value,
+ int> = 0>
+inline void sort(IteratorTy Start, IteratorTy End) {
+ array_pod_sort(Start, End);
+}
+
template <typename Container> inline void sort(Container &&C) {
llvm::sort(adl_begin(C), adl_end(C));
}
@@ -1134,8 +1459,7 @@
template <typename IteratorTy, typename Compare>
inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
#ifdef EXPENSIVE_CHECKS
- std::mt19937 Generator(std::random_device{}());
- std::shuffle(Start, End, Generator);
+ detail::presortShuffle<IteratorTy>(Start, End);
#endif
std::sort(Start, End, Comp);
}
@@ -1149,41 +1473,23 @@
// Extra additions to <algorithm>
//===----------------------------------------------------------------------===//
-/// For a container of pointers, deletes the pointers and then clears the
-/// container.
-template<typename Container>
-void DeleteContainerPointers(Container &C) {
- for (auto V : C)
- delete V;
- C.clear();
-}
-
-/// In a container of pairs (usually a map) whose second element is a pointer,
-/// deletes the second elements and then clears the container.
-template<typename Container>
-void DeleteContainerSeconds(Container &C) {
- for (auto &V : C)
- delete V.second;
- C.clear();
-}
-
/// Get the size of a range. This is a wrapper function around std::distance
/// which is only enabled when the operation is O(1).
template <typename R>
-auto size(R &&Range, typename std::enable_if<
- std::is_same<typename std::iterator_traits<decltype(
- Range.begin())>::iterator_category,
- std::random_access_iterator_tag>::value,
- void>::type * = nullptr)
- -> decltype(std::distance(Range.begin(), Range.end())) {
+auto size(R &&Range,
+ std::enable_if_t<
+ std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<decltype(
+ Range.begin())>::iterator_category>::value,
+ void> * = nullptr) {
return std::distance(Range.begin(), Range.end());
}
/// Provide wrappers to std::for_each which take ranges instead of having to
/// pass begin/end explicitly.
-template <typename R, typename UnaryPredicate>
-UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
- return std::for_each(adl_begin(Range), adl_end(Range), P);
+template <typename R, typename UnaryFunction>
+UnaryFunction for_each(R &&Range, UnaryFunction F) {
+ return std::for_each(adl_begin(Range), adl_end(Range), F);
}
/// Provide wrappers to std::all_of which take ranges instead of having to pass
@@ -1209,27 +1515,26 @@
/// Provide wrappers to std::find which take ranges instead of having to pass
/// begin/end explicitly.
-template <typename R, typename T>
-auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range)) {
+template <typename R, typename T> auto find(R &&Range, const T &Val) {
return std::find(adl_begin(Range), adl_end(Range), Val);
}
/// Provide wrappers to std::find_if which take ranges instead of having to pass
/// begin/end explicitly.
template <typename R, typename UnaryPredicate>
-auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
+auto find_if(R &&Range, UnaryPredicate P) {
return std::find_if(adl_begin(Range), adl_end(Range), P);
}
template <typename R, typename UnaryPredicate>
-auto find_if_not(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
+auto find_if_not(R &&Range, UnaryPredicate P) {
return std::find_if_not(adl_begin(Range), adl_end(Range), P);
}
/// Provide wrappers to std::remove_if which take ranges instead of having to
/// pass begin/end explicitly.
template <typename R, typename UnaryPredicate>
-auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
+auto remove_if(R &&Range, UnaryPredicate P) {
return std::remove_if(adl_begin(Range), adl_end(Range), P);
}
@@ -1245,6 +1550,13 @@
return std::copy(adl_begin(Range), adl_end(Range), Out);
}
+/// Provide wrappers to std::move which take ranges instead of having to
+/// pass begin/end explicitly.
+template <typename R, typename OutputIt>
+OutputIt move(R &&Range, OutputIt Out) {
+ return std::move(adl_begin(Range), adl_end(Range), Out);
+}
+
/// Wrapper function around std::find to detect if an element exists
/// in a container.
template <typename R, typename E>
@@ -1252,62 +1564,67 @@
return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
}
+/// Wrapper function around std::is_sorted to check if elements in a range \p R
+/// are sorted with respect to a comparator \p C.
+template <typename R, typename Compare> bool is_sorted(R &&Range, Compare C) {
+ return std::is_sorted(adl_begin(Range), adl_end(Range), C);
+}
+
+/// Wrapper function around std::is_sorted to check if elements in a range \p R
+/// are sorted in non-descending order.
+template <typename R> bool is_sorted(R &&Range) {
+ return std::is_sorted(adl_begin(Range), adl_end(Range));
+}
+
/// Wrapper function around std::count to count the number of times an element
/// \p Element occurs in the given range \p Range.
-template <typename R, typename E>
-auto count(R &&Range, const E &Element) ->
- typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
+template <typename R, typename E> auto count(R &&Range, const E &Element) {
return std::count(adl_begin(Range), adl_end(Range), Element);
}
/// Wrapper function around std::count_if to count the number of times an
/// element satisfying a given predicate occurs in a range.
template <typename R, typename UnaryPredicate>
-auto count_if(R &&Range, UnaryPredicate P) ->
- typename std::iterator_traits<decltype(adl_begin(Range))>::difference_type {
+auto count_if(R &&Range, UnaryPredicate P) {
return std::count_if(adl_begin(Range), adl_end(Range), P);
}
/// Wrapper function around std::transform to apply a function to a range and
/// store the result elsewhere.
-template <typename R, typename OutputIt, typename UnaryPredicate>
-OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P) {
- return std::transform(adl_begin(Range), adl_end(Range), d_first, P);
+template <typename R, typename OutputIt, typename UnaryFunction>
+OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F) {
+ return std::transform(adl_begin(Range), adl_end(Range), d_first, F);
}
/// Provide wrappers to std::partition which take ranges instead of having to
/// pass begin/end explicitly.
template <typename R, typename UnaryPredicate>
-auto partition(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range)) {
+auto partition(R &&Range, UnaryPredicate P) {
return std::partition(adl_begin(Range), adl_end(Range), P);
}
/// Provide wrappers to std::lower_bound which take ranges instead of having to
/// pass begin/end explicitly.
-template <typename R, typename T>
-auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
+template <typename R, typename T> auto lower_bound(R &&Range, T &&Value) {
return std::lower_bound(adl_begin(Range), adl_end(Range),
std::forward<T>(Value));
}
template <typename R, typename T, typename Compare>
-auto lower_bound(R &&Range, T &&Value, Compare C)
- -> decltype(adl_begin(Range)) {
+auto lower_bound(R &&Range, T &&Value, Compare C) {
return std::lower_bound(adl_begin(Range), adl_end(Range),
std::forward<T>(Value), C);
}
/// Provide wrappers to std::upper_bound which take ranges instead of having to
/// pass begin/end explicitly.
-template <typename R, typename T>
-auto upper_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range)) {
+template <typename R, typename T> auto upper_bound(R &&Range, T &&Value) {
return std::upper_bound(adl_begin(Range), adl_end(Range),
std::forward<T>(Value));
}
template <typename R, typename T, typename Compare>
-auto upper_bound(R &&Range, T &&Value, Compare C)
- -> decltype(adl_begin(Range)) {
+auto upper_bound(R &&Range, T &&Value, Compare C) {
return std::upper_bound(adl_begin(Range), adl_end(Range),
std::forward<T>(Value), C);
}
@@ -1326,7 +1643,7 @@
/// Requires that C is always true below some limit, and always false above it.
template <typename R, typename Predicate,
typename Val = decltype(*adl_begin(std::declval<R>()))>
-auto partition_point(R &&Range, Predicate P) -> decltype(adl_begin(Range)) {
+auto partition_point(R &&Range, Predicate P) {
return std::partition_point(adl_begin(Range), adl_end(Range), P);
}
@@ -1339,15 +1656,6 @@
std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
}
-/// Given a range of type R, iterate the entire range and return a
-/// SmallVector with elements of the vector. This is useful, for example,
-/// when you want to iterate a range and then sort the results.
-template <unsigned Size, typename R>
-SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
-to_vector(R &&Range) {
- return {adl_begin(Range), adl_end(Range)};
-}
-
/// Provide a container algorithm similar to C++ Library Fundamentals v2's
/// `erase_if` which is equivalent to:
///
@@ -1360,6 +1668,22 @@
C.erase(remove_if(C, P), C.end());
}
+/// Wrapper function to remove a value from a container:
+///
+/// C.erase(remove(C.begin(), C.end(), V), C.end());
+template <typename Container, typename ValueType>
+void erase_value(Container &C, ValueType V) {
+ C.erase(std::remove(C.begin(), C.end(), V), C.end());
+}
+
+/// Wrapper function to append a range to a container.
+///
+/// C.insert(C.end(), R.begin(), R.end());
+template <typename Container, typename Range>
+inline void append_range(Container &C, Range &&R) {
+ C.insert(C.end(), R.begin(), R.end());
+}
+
/// Given a sequence container Cont, replace the range [ContIt, ContEnd) with
/// the range [ValIt, ValEnd) (which is not from the same container).
template<typename Container, typename RandomAccessIterator>
@@ -1387,45 +1711,73 @@
replace(Cont, ContIt, ContEnd, R.begin(), R.end());
}
+/// An STL-style algorithm similar to std::for_each that applies a second
+/// functor between every pair of elements.
+///
+/// This provides the control flow logic to, for example, print a
+/// comma-separated list:
+/// \code
+/// interleave(names.begin(), names.end(),
+/// [&](StringRef name) { os << name; },
+/// [&] { os << ", "; });
+/// \endcode
+template <typename ForwardIterator, typename UnaryFunctor,
+ typename NullaryFunctor,
+ typename = typename std::enable_if<
+ !std::is_constructible<StringRef, UnaryFunctor>::value &&
+ !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
+inline void interleave(ForwardIterator begin, ForwardIterator end,
+ UnaryFunctor each_fn, NullaryFunctor between_fn) {
+ if (begin == end)
+ return;
+ each_fn(*begin);
+ ++begin;
+ for (; begin != end; ++begin) {
+ between_fn();
+ each_fn(*begin);
+ }
+}
+
+template <typename Container, typename UnaryFunctor, typename NullaryFunctor,
+ typename = typename std::enable_if<
+ !std::is_constructible<StringRef, UnaryFunctor>::value &&
+ !std::is_constructible<StringRef, NullaryFunctor>::value>::type>
+inline void interleave(const Container &c, UnaryFunctor each_fn,
+ NullaryFunctor between_fn) {
+ interleave(c.begin(), c.end(), each_fn, between_fn);
+}
+
+/// Overload of interleave for the common case of string separator.
+template <typename Container, typename UnaryFunctor, typename StreamT,
+ typename T = detail::ValueOfRange<Container>>
+inline void interleave(const Container &c, StreamT &os, UnaryFunctor each_fn,
+ const StringRef &separator) {
+ interleave(c.begin(), c.end(), each_fn, [&] { os << separator; });
+}
+template <typename Container, typename StreamT,
+ typename T = detail::ValueOfRange<Container>>
+inline void interleave(const Container &c, StreamT &os,
+ const StringRef &separator) {
+ interleave(
+ c, os, [&](const T &a) { os << a; }, separator);
+}
+
+template <typename Container, typename UnaryFunctor, typename StreamT,
+ typename T = detail::ValueOfRange<Container>>
+inline void interleaveComma(const Container &c, StreamT &os,
+ UnaryFunctor each_fn) {
+ interleave(c, os, each_fn, ", ");
+}
+template <typename Container, typename StreamT,
+ typename T = detail::ValueOfRange<Container>>
+inline void interleaveComma(const Container &c, StreamT &os) {
+ interleaveComma(c, os, [&](const T &a) { os << a; });
+}
+
//===----------------------------------------------------------------------===//
// Extra additions to <memory>
//===----------------------------------------------------------------------===//
-// Implement make_unique according to N3656.
-
-/// Constructs a `new T()` with the given args and returns a
-/// `unique_ptr<T>` which owns the object.
-///
-/// Example:
-///
-/// auto p = make_unique<int>();
-/// auto p = make_unique<std::tuple<int, int>>(0, 1);
-template <class T, class... Args>
-typename std::enable_if<!std::is_array<T>::value, std::unique_ptr<T>>::type
-make_unique(Args &&... args) {
- return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
-}
-
-/// Constructs a `new T[n]` with the given args and returns a
-/// `unique_ptr<T[]>` which owns the object.
-///
-/// \param n size of the new array.
-///
-/// Example:
-///
-/// auto p = make_unique<int[]>(2); // value-initializes the array with 0's.
-template <class T>
-typename std::enable_if<std::is_array<T>::value && std::extent<T>::value == 0,
- std::unique_ptr<T>>::type
-make_unique(size_t n) {
- return std::unique_ptr<T>(new typename std::remove_extent<T>::type[n]());
-}
-
-/// This function isn't used and is only here to provide better compile errors.
-template <class T, class... Args>
-typename std::enable_if<std::extent<T>::value != 0>::type
-make_unique(Args &&...) = delete;
-
struct FreeDeleter {
void operator()(void* v) {
::free(v);
@@ -1439,20 +1791,6 @@
}
};
-/// A functor like C++14's std::less<void> in its absence.
-struct less {
- template <typename A, typename B> bool operator()(A &&a, B &&b) const {
- return std::forward<A>(a) < std::forward<B>(b);
- }
-};
-
-/// A functor like C++14's std::equal<void> in its absence.
-struct equal {
- template <typename A, typename B> bool operator()(A &&a, B &&b) const {
- return std::forward<A>(a) == std::forward<B>(b);
- }
-};
-
/// Binary functor that adapts to any other binary functor after dereferencing
/// operands.
template <typename T> struct deref {
@@ -1461,8 +1799,7 @@
// Could be further improved to cope with non-derivable functors and
// non-binary functors (should be a variadic template member function
// operator()).
- template <typename A, typename B>
- auto operator()(A &lhs, B &rhs) const -> decltype(func(*lhs, *rhs)) {
+ template <typename A, typename B> auto operator()(A &lhs, B &rhs) const {
assert(lhs);
assert(rhs);
return func(*lhs, *rhs);
@@ -1483,6 +1820,8 @@
result_pair(std::size_t Index, IterOfRange<R> Iter)
: Index(Index), Iter(Iter) {}
+ result_pair<R>(const result_pair<R> &Other)
+ : Index(Other.Index), Iter(Other.Iter) {}
result_pair<R> &operator=(const result_pair<R> &Other) {
Index = Other.Index;
Iter = Other.Iter;
@@ -1531,6 +1870,7 @@
return Result.Iter == RHS.Result.Iter;
}
+ enumerator_iter<R>(const enumerator_iter<R> &Other) : Result(Other.Result) {}
enumerator_iter<R> &operator=(const enumerator_iter<R> &Other) {
Result = Other.Result;
return *this;
@@ -1580,8 +1920,7 @@
namespace detail {
template <typename F, typename Tuple, std::size_t... I>
-auto apply_tuple_impl(F &&f, Tuple &&t, index_sequence<I...>)
- -> decltype(std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...)) {
+decltype(auto) apply_tuple_impl(F &&f, Tuple &&t, std::index_sequence<I...>) {
return std::forward<F>(f)(std::get<I>(std::forward<Tuple>(t))...);
}
@@ -1591,11 +1930,8 @@
/// tuple variadically to f as if by calling f(a1, a2, ..., an) and
/// return the result.
template <typename F, typename Tuple>
-auto apply_tuple(F &&f, Tuple &&t) -> decltype(detail::apply_tuple_impl(
- std::forward<F>(f), std::forward<Tuple>(t),
- build_index_impl<
- std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
- using Indices = build_index_impl<
+decltype(auto) apply_tuple(F &&f, Tuple &&t) {
+ using Indices = std::make_index_sequence<
std::tuple_size<typename std::decay<Tuple>::type>::value>;
return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
@@ -1604,49 +1940,89 @@
/// Return true if the sequence [Begin, End) has exactly N items. Runs in O(N)
/// time. Not meant for use with random-access iterators.
-template <typename IterTy>
+/// Can optionally take a predicate to filter lazily some items.
+template <typename IterTy,
+ typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
bool hasNItems(
IterTy &&Begin, IterTy &&End, unsigned N,
- typename std::enable_if<
- !std::is_same<
- typename std::iterator_traits<typename std::remove_reference<
- decltype(Begin)>::type>::iterator_category,
- std::random_access_iterator_tag>::value,
- void>::type * = nullptr) {
- for (; N; --N, ++Begin)
+ Pred &&ShouldBeCounted =
+ [](const decltype(*std::declval<IterTy>()) &) { return true; },
+ std::enable_if_t<
+ !std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<std::remove_reference_t<
+ decltype(Begin)>>::iterator_category>::value,
+ void> * = nullptr) {
+ for (; N; ++Begin) {
if (Begin == End)
return false; // Too few.
- return Begin == End;
+ N -= ShouldBeCounted(*Begin);
+ }
+ for (; Begin != End; ++Begin)
+ if (ShouldBeCounted(*Begin))
+ return false; // Too many.
+ return true;
}
/// Return true if the sequence [Begin, End) has N or more items. Runs in O(N)
/// time. Not meant for use with random-access iterators.
-template <typename IterTy>
+/// Can optionally take a predicate to lazily filter some items.
+template <typename IterTy,
+ typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
bool hasNItemsOrMore(
IterTy &&Begin, IterTy &&End, unsigned N,
- typename std::enable_if<
- !std::is_same<
- typename std::iterator_traits<typename std::remove_reference<
- decltype(Begin)>::type>::iterator_category,
- std::random_access_iterator_tag>::value,
- void>::type * = nullptr) {
- for (; N; --N, ++Begin)
+ Pred &&ShouldBeCounted =
+ [](const decltype(*std::declval<IterTy>()) &) { return true; },
+ std::enable_if_t<
+ !std::is_base_of<std::random_access_iterator_tag,
+ typename std::iterator_traits<std::remove_reference_t<
+ decltype(Begin)>>::iterator_category>::value,
+ void> * = nullptr) {
+ for (; N; ++Begin) {
if (Begin == End)
return false; // Too few.
+ N -= ShouldBeCounted(*Begin);
+ }
return true;
}
+/// Returns true if the sequence [Begin, End) has N or less items. Can
+/// optionally take a predicate to lazily filter some items.
+template <typename IterTy,
+ typename Pred = bool (*)(const decltype(*std::declval<IterTy>()) &)>
+bool hasNItemsOrLess(
+ IterTy &&Begin, IterTy &&End, unsigned N,
+ Pred &&ShouldBeCounted = [](const decltype(*std::declval<IterTy>()) &) {
+ return true;
+ }) {
+ assert(N != std::numeric_limits<unsigned>::max());
+ return !hasNItemsOrMore(Begin, End, N + 1, ShouldBeCounted);
+}
+
+/// Returns true if the given container has exactly N items
+template <typename ContainerTy> bool hasNItems(ContainerTy &&C, unsigned N) {
+ return hasNItems(std::begin(C), std::end(C), N);
+}
+
+/// Returns true if the given container has N or more items
+template <typename ContainerTy>
+bool hasNItemsOrMore(ContainerTy &&C, unsigned N) {
+ return hasNItemsOrMore(std::begin(C), std::end(C), N);
+}
+
+/// Returns true if the given container has N or less items
+template <typename ContainerTy>
+bool hasNItemsOrLess(ContainerTy &&C, unsigned N) {
+ return hasNItemsOrLess(std::begin(C), std::end(C), N);
+}
+
/// Returns a raw pointer that represents the same address as the argument.
///
-/// The late bound return should be removed once we move to C++14 to better
-/// align with the C++20 declaration. Also, this implementation can be removed
-/// once we move to C++20 where it's defined as std::to_addres()
+/// This implementation can be removed once we move to C++20 where it's defined
+/// as std::to_address().
///
/// The std::pointer_traits<>::to_address(p) variations of these overloads has
/// not been implemented.
-template <class Ptr> auto to_address(const Ptr &P) -> decltype(P.operator->()) {
- return P.operator->();
-}
+template <class Ptr> auto to_address(const Ptr &P) { return P.operator->(); }
template <class T> constexpr T *to_address(T *P) { return P; }
} // end namespace llvm