Update clang to r339409.
Change-Id: I800772d2d838223be1f6b40d490c4591b937fca2
diff --git a/linux-x64/clang/include/llvm/ADT/STLExtras.h b/linux-x64/clang/include/llvm/ADT/STLExtras.h
index 051b900..03109a0 100644
--- a/linux-x64/clang/include/llvm/ADT/STLExtras.h
+++ b/linux-x64/clang/include/llvm/ADT/STLExtras.h
@@ -21,6 +21,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
+#include "llvm/Config/abi-breaking.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
@@ -58,6 +59,19 @@
} // end namespace detail
//===----------------------------------------------------------------------===//
+// Extra additions to <type_traits>
+//===----------------------------------------------------------------------===//
+
+template <typename T>
+struct negation : std::integral_constant<bool, !bool(T::value)> {};
+
+template <typename...> struct conjunction : std::true_type {};
+template <typename B1> struct conjunction<B1> : B1 {};
+template <typename B1, typename... Bn>
+struct conjunction<B1, Bn...>
+ : std::conditional<bool(B1::value), conjunction<Bn...>, B1>::type {};
+
+//===----------------------------------------------------------------------===//
// Extra additions to <functional>
//===----------------------------------------------------------------------===//
@@ -271,60 +285,121 @@
/// auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
/// // R contains { 1, 3 }.
/// \endcode
-template <typename WrappedIteratorT, typename PredicateT>
-class filter_iterator
+///
+/// Note: filter_iterator_base implements support for forward iteration.
+/// filter_iterator_impl exists to provide support for bidirectional iteration,
+/// conditional on whether the wrapped iterator supports it.
+template <typename WrappedIteratorT, typename PredicateT, typename IterTag>
+class filter_iterator_base
: public iterator_adaptor_base<
- filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
+ filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
+ WrappedIteratorT,
typename std::common_type<
- std::forward_iterator_tag,
- typename std::iterator_traits<
- WrappedIteratorT>::iterator_category>::type> {
+ IterTag, typename std::iterator_traits<
+ WrappedIteratorT>::iterator_category>::type> {
using BaseT = iterator_adaptor_base<
- filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
+ filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>,
+ WrappedIteratorT,
typename std::common_type<
- std::forward_iterator_tag,
- typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
- type>;
+ IterTag, typename std::iterator_traits<
+ WrappedIteratorT>::iterator_category>::type>;
- struct PayloadType {
- WrappedIteratorT End;
- PredicateT Pred;
- };
-
- Optional<PayloadType> Payload;
+protected:
+ WrappedIteratorT End;
+ PredicateT Pred;
void findNextValid() {
- assert(Payload && "Payload should be engaged when findNextValid is called");
- while (this->I != Payload->End && !Payload->Pred(*this->I))
+ while (this->I != End && !Pred(*this->I))
BaseT::operator++();
}
- // Construct the begin iterator. The begin iterator requires to know where end
- // is, so that it can properly stop when it hits end.
- filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
- : BaseT(std::move(Begin)),
- Payload(PayloadType{std::move(End), std::move(Pred)}) {
+ // Construct the iterator. The begin iterator needs to know where the end
+ // is, so that it can properly stop when it gets there. The end iterator only
+ // needs the predicate to support bidirectional iteration.
+ filter_iterator_base(WrappedIteratorT Begin, WrappedIteratorT End,
+ PredicateT Pred)
+ : BaseT(Begin), End(End), Pred(Pred) {
findNextValid();
}
- // Construct the end iterator. It's not incrementable, so Payload doesn't
- // have to be engaged.
- filter_iterator(WrappedIteratorT End) : BaseT(End) {}
-
public:
using BaseT::operator++;
- filter_iterator &operator++() {
+ filter_iterator_base &operator++() {
BaseT::operator++();
findNextValid();
return *this;
}
-
- template <typename RT, typename PT>
- friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
- make_filter_range(RT &&, PT);
};
+/// Specialization of filter_iterator_base for forward iteration only.
+template <typename WrappedIteratorT, typename PredicateT,
+ typename IterTag = std::forward_iterator_tag>
+class filter_iterator_impl
+ : public filter_iterator_base<WrappedIteratorT, PredicateT, IterTag> {
+ using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT, IterTag>;
+
+public:
+ filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
+ PredicateT Pred)
+ : BaseT(Begin, End, Pred) {}
+};
+
+/// Specialization of filter_iterator_base for bidirectional iteration.
+template <typename WrappedIteratorT, typename PredicateT>
+class filter_iterator_impl<WrappedIteratorT, PredicateT,
+ std::bidirectional_iterator_tag>
+ : public filter_iterator_base<WrappedIteratorT, PredicateT,
+ std::bidirectional_iterator_tag> {
+ using BaseT = filter_iterator_base<WrappedIteratorT, PredicateT,
+ std::bidirectional_iterator_tag>;
+ void findPrevValid() {
+ while (!this->Pred(*this->I))
+ BaseT::operator--();
+ }
+
+public:
+ using BaseT::operator--;
+
+ filter_iterator_impl(WrappedIteratorT Begin, WrappedIteratorT End,
+ PredicateT Pred)
+ : BaseT(Begin, End, Pred) {}
+
+ filter_iterator_impl &operator--() {
+ BaseT::operator--();
+ findPrevValid();
+ return *this;
+ }
+};
+
+namespace detail {
+
+template <bool is_bidirectional> struct fwd_or_bidi_tag_impl {
+ using type = std::forward_iterator_tag;
+};
+
+template <> struct fwd_or_bidi_tag_impl<true> {
+ using type = std::bidirectional_iterator_tag;
+};
+
+/// Helper which sets its type member to forward_iterator_tag if the category
+/// of \p IterT does not derive from bidirectional_iterator_tag, and to
+/// bidirectional_iterator_tag otherwise.
+template <typename IterT> struct fwd_or_bidi_tag {
+ using type = typename fwd_or_bidi_tag_impl<std::is_base_of<
+ std::bidirectional_iterator_tag,
+ typename std::iterator_traits<IterT>::iterator_category>::value>::type;
+};
+
+} // namespace detail
+
+/// Defines filter_iterator to a suitable specialization of
+/// filter_iterator_impl, based on the underlying iterator's category.
+template <typename WrappedIteratorT, typename PredicateT>
+using filter_iterator = filter_iterator_impl<
+ WrappedIteratorT, PredicateT,
+ typename detail::fwd_or_bidi_tag<WrappedIteratorT>::type>;
+
/// Convenience function that takes a range of elements and a predicate,
/// and return a new filter_iterator range.
///
@@ -337,10 +412,94 @@
make_filter_range(RangeT &&Range, PredicateT Pred) {
using FilterIteratorT =
filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
- return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
- std::end(std::forward<RangeT>(Range)),
- std::move(Pred)),
- FilterIteratorT(std::end(std::forward<RangeT>(Range))));
+ return make_range(
+ FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
+ std::end(std::forward<RangeT>(Range)), Pred),
+ FilterIteratorT(std::end(std::forward<RangeT>(Range)),
+ std::end(std::forward<RangeT>(Range)), Pred));
+}
+
+/// A pseudo-iterator adaptor that is designed to implement "early increment"
+/// style loops.
+///
+/// This is *not a normal iterator* and should almost never be used directly. It
+/// is intended primarily to be used with range based for loops and some range
+/// algorithms.
+///
+/// The iterator isn't quite an `OutputIterator` or an `InputIterator` but
+/// somewhere between them. The constraints of these iterators are:
+///
+/// - On construction or after being incremented, it is comparable and
+/// dereferencable. It is *not* incrementable.
+/// - After being dereferenced, it is neither comparable nor dereferencable, it
+/// is only incrementable.
+///
+/// This means you can only dereference the iterator once, and you can only
+/// increment it once between dereferences.
+template <typename WrappedIteratorT>
+class early_inc_iterator_impl
+ : public iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
+ WrappedIteratorT, std::input_iterator_tag> {
+ using BaseT =
+ iterator_adaptor_base<early_inc_iterator_impl<WrappedIteratorT>,
+ WrappedIteratorT, std::input_iterator_tag>;
+
+ using PointerT = typename std::iterator_traits<WrappedIteratorT>::pointer;
+
+protected:
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+ bool IsEarlyIncremented = false;
+#endif
+
+public:
+ early_inc_iterator_impl(WrappedIteratorT I) : BaseT(I) {}
+
+ using BaseT::operator*;
+ typename BaseT::reference operator*() {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+ assert(!IsEarlyIncremented && "Cannot dereference twice!");
+ IsEarlyIncremented = true;
+#endif
+ return *(this->I)++;
+ }
+
+ using BaseT::operator++;
+ early_inc_iterator_impl &operator++() {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+ assert(IsEarlyIncremented && "Cannot increment before dereferencing!");
+ IsEarlyIncremented = false;
+#endif
+ return *this;
+ }
+
+ using BaseT::operator==;
+ bool operator==(const early_inc_iterator_impl &RHS) const {
+#if LLVM_ENABLE_ABI_BREAKING_CHECKS
+ assert(!IsEarlyIncremented && "Cannot compare after dereferencing!");
+#endif
+ return BaseT::operator==(RHS);
+ }
+};
+
+/// Make a range that does early increment to allow mutation of the underlying
+/// range without disrupting iteration.
+///
+/// The underlying iterator will be incremented immediately after it is
+/// dereferenced, allowing deletion of the current node or insertion of nodes to
+/// not disrupt iteration provided they do not invalidate the *next* iterator --
+/// the current iterator can be invalidated.
+///
+/// This requires a very exact pattern of use that is only really suitable to
+/// range based for loops and other range algorithms that explicitly guarantee
+/// to dereference exactly once each element, and to increment exactly once each
+/// element.
+template <typename RangeT>
+iterator_range<early_inc_iterator_impl<detail::IterOfRange<RangeT>>>
+make_early_inc_range(RangeT &&Range) {
+ using EarlyIncIteratorT =
+ early_inc_iterator_impl<detail::IterOfRange<RangeT>>;
+ return make_range(EarlyIncIteratorT(std::begin(std::forward<RangeT>(Range))),
+ EarlyIncIteratorT(std::end(std::forward<RangeT>(Range))));
}
// forward declarations required by zip_shortest/zip_first
@@ -649,7 +808,7 @@
// Extra additions to <utility>
//===----------------------------------------------------------------------===//
-/// \brief Function object to check whether the first component of a std::pair
+/// Function object to check whether the first component of a std::pair
/// compares less than the first component of another std::pair.
struct less_first {
template <typename T> bool operator()(const T &lhs, const T &rhs) const {
@@ -657,7 +816,7 @@
}
};
-/// \brief Function object to check whether the second component of a std::pair
+/// Function object to check whether the second component of a std::pair
/// compares less than the second component of another std::pair.
struct less_second {
template <typename T> bool operator()(const T &lhs, const T &rhs) const {
@@ -665,16 +824,29 @@
}
};
+/// \brief Function object to apply a binary function to the first component of
+/// a std::pair.
+template<typename FuncTy>
+struct on_first {
+ FuncTy func;
+
+ template <typename T>
+ auto operator()(const T &lhs, const T &rhs) const
+ -> decltype(func(lhs.first, rhs.first)) {
+ return func(lhs.first, rhs.first);
+ }
+};
+
// A subset of N3658. More stuff can be added as-needed.
-/// \brief Represents a compile-time sequence of integers.
+/// 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); }
};
-/// \brief Alias for the common case of a sequence of size_ts.
+/// Alias for the common case of a sequence of size_ts.
template <size_t... I>
struct index_sequence : integer_sequence<std::size_t, I...> {};
@@ -683,7 +855,7 @@
template <std::size_t... I>
struct build_index_impl<0, I...> : index_sequence<I...> {};
-/// \brief Creates a compile-time integer sequence for a parameter pack.
+/// Creates a compile-time integer sequence for a parameter pack.
template <class... Ts>
struct index_sequence_for : build_index_impl<sizeof...(Ts)> {};
@@ -692,7 +864,7 @@
template <int N> struct rank : rank<N - 1> {};
template <> struct rank<0> {};
-/// \brief traits class for checking whether type T is one of any of the given
+/// traits class for checking whether type T is one of any of the given
/// types in the variadic list.
template <typename T, typename... Ts> struct is_one_of {
static const bool value = false;
@@ -704,7 +876,7 @@
std::is_same<T, U>::value || is_one_of<T, Ts...>::value;
};
-/// \brief traits class for checking whether type T is a base class for all
+/// traits class for checking whether type T is a base class for all
/// the given types in the variadic list.
template <typename T, typename... Ts> struct are_base_of {
static const bool value = true;
@@ -943,7 +1115,7 @@
return std::lower_bound(adl_begin(Range), adl_end(Range), I);
}
-/// \brief Given a range of type R, iterate the entire range and return a
+/// 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>
@@ -964,13 +1136,25 @@
C.erase(remove_if(C, P), C.end());
}
+/// 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())) {
+ return std::distance(Range.begin(), Range.end());
+}
+
//===----------------------------------------------------------------------===//
// Extra additions to <memory>
//===----------------------------------------------------------------------===//
// Implement make_unique according to N3656.
-/// \brief Constructs a `new T()` with the given args and returns a
+/// Constructs a `new T()` with the given args and returns a
/// `unique_ptr<T>` which owns the object.
///
/// Example:
@@ -983,7 +1167,7 @@
return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
}
-/// \brief Constructs a `new T[n]` with the given args and returns a
+/// 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.