Index: include/lld/Core/File.h =================================================================== --- include/lld/Core/File.h +++ include/lld/Core/File.h @@ -14,7 +14,6 @@ #include "lld/Core/DefinedAtom.h" #include "lld/Core/SharedLibraryAtom.h" #include "lld/Core/UndefinedAtom.h" -#include "lld/Core/range.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/Twine.h" #include "llvm/Support/ErrorHandling.h" Index: include/lld/Core/LinkingContext.h =================================================================== --- include/lld/Core/LinkingContext.h +++ include/lld/Core/LinkingContext.h @@ -15,7 +15,6 @@ #include "lld/Core/Node.h" #include "lld/Core/Parallel.h" #include "lld/Core/Reference.h" -#include "lld/Core/range.h" #include "lld/Core/Reader.h" #include "llvm/Support/ErrorOr.h" #include "llvm/Support/raw_ostream.h" @@ -241,7 +240,7 @@ /// Return the list of undefined symbols that are specified in the /// linker command line, using the -u option. - range initialUndefinedSymbols() const { + ArrayRef initialUndefinedSymbols() const { return _initialUndefinedSymbols; } Index: include/lld/Core/Parallel.h =================================================================== --- include/lld/Core/Parallel.h +++ include/lld/Core/Parallel.h @@ -12,7 +12,6 @@ #include "lld/Core/Instrumentation.h" #include "lld/Core/LLVM.h" -#include "lld/Core/range.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/thread.h" Index: include/lld/Core/Pass.h =================================================================== --- include/lld/Core/Pass.h +++ include/lld/Core/Pass.h @@ -13,7 +13,6 @@ #include "lld/Core/Atom.h" #include "lld/Core/File.h" #include "lld/Core/Reference.h" -#include "lld/Core/range.h" #include namespace lld { Index: include/lld/Core/Simple.h =================================================================== --- include/lld/Core/Simple.h +++ include/lld/Core/Simple.h @@ -71,8 +71,8 @@ return _absolute; } - typedef range::iterator> DefinedAtomRange; - DefinedAtomRange definedAtoms() { return make_range(_defined); } + typedef llvm::MutableArrayRef DefinedAtomRange; + DefinedAtomRange definedAtoms() { return _defined; } private: AtomVector _defined; Index: include/lld/Core/range.h =================================================================== --- include/lld/Core/range.h +++ /dev/null @@ -1,740 +0,0 @@ -//===-- lld/Core/range.h - Iterator ranges ----------------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// \brief Iterator range type based on c++1y range proposal. -/// -/// See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3350.html -/// -//===----------------------------------------------------------------------===// - -#ifndef LLD_CORE_RANGE_H -#define LLD_CORE_RANGE_H - -#include "llvm/Support/Compiler.h" -#include -#include -#include -#include -#include -#include -#include - -namespace lld { -// Nothing in this namespace is part of the exported interface. -namespace detail { - -using std::begin; -using std::end; - -/// Used as the result type of undefined functions. -struct undefined {}; - -template class begin_result { - template static auto check(T &&t) -> decltype(begin(t)); - static undefined check(...); -public: - typedef decltype(check(std::declval())) type; -}; - -template class end_result { - template static auto check(T &&t) -> decltype(end(t)); - static undefined check(...); -public: - typedef decltype(check(std::declval())) type; -}; - -// Things that begin and end work on, in compatible ways, are -// ranges. [stmt.ranged] -template -struct is_range : std::is_same::type, - typename detail::end_result::type> {}; - -// This currently requires specialization and doesn't work for -// detecting \c range<>s or iterators. We should add -// \c contiguous_iterator_tag to fix that. -template struct is_contiguous_range : std::false_type {}; -template -struct is_contiguous_range : is_contiguous_range {}; -template -struct is_contiguous_range : is_contiguous_range {}; -template -struct is_contiguous_range : is_contiguous_range {}; - -template -struct is_contiguous_range : std::true_type {}; -template -struct is_contiguous_range : std::true_type {}; -template -struct is_contiguous_range > : std::true_type {}; -template -struct is_contiguous_range< - std::basic_string > : std::true_type {}; -template -struct is_contiguous_range > : std::true_type {}; - -// Removes cv qualifiers from all levels of a multi-level pointer -// type, not just the type level. -template struct remove_all_cv_ptr { - typedef T type; -}; -template struct remove_all_cv_ptr { - typedef typename remove_all_cv_ptr::type *type; -}; -template struct remove_all_cv_ptr { - typedef typename remove_all_cv_ptr::type type; -}; -template struct remove_all_cv_ptr { - typedef typename remove_all_cv_ptr::type type; -}; -template struct remove_all_cv_ptr { - typedef typename remove_all_cv_ptr::type type; -}; - -template -struct conversion_preserves_array_indexing : std::false_type {}; - -template -struct conversion_preserves_array_indexing : std::integral_constant< - bool, std::is_convertible::value && - std::is_same::type, - typename remove_all_cv_ptr::type>::value> {}; - -template -LLVM_CONSTEXPR auto adl_begin(T &&t) -> decltype(begin(t)) { - return begin(std::forward(t)); -} - -template LLVM_CONSTEXPR auto adl_end(T &&t) -> decltype(end(t)) { - return end(std::forward(t)); -} -} // end namespace detail - -/// A \c std::range represents a half-open iterator range -/// built from two iterators, \c 'begin', and \c 'end'. If \c end is -/// not reachable from \c begin, the behavior is undefined. -/// -/// The mutability of elements of the range is controlled by the -/// Iterator argument. Instantiate -/// range<Foo::iterator> or -/// range<T*>, or call -/// make_range(non_const_container), and you -/// get a mutable range. Instantiate -/// range<Foo::const_iterator> or -/// rangeT*>, or call -/// make_range(const_container), and you get a -/// constant range. -/// -/// \todo Inherit from std::pair? -/// -/// \todo This interface contains some functions that could be -/// provided as free algorithms rather than member functions, and all -/// of the pop_*() functions could be replaced by \c -/// slice() at the cost of some extra iterator copies. This makes -/// them more awkward to use, but makes it easier for users to write -/// their own types that follow the same interface. On the other hand, -/// a \c range_facade could be provided to help users write new -/// ranges, and it could provide the members. Such functions are -/// marked with a note in their documentation. (Of course, all of -/// these member functions could be provided as free functions using -/// the iterator access methods, but one goal here is to allow people -/// to program without touching iterators at all.) -template class range { - Iterator begin_, end_; -public: - /// \name types - /// @{ - - /// The iterator category of \c Iterator. - /// \todo Consider defining range categories. If they don't add - /// anything over the corresponding iterator categories, then - /// they're probably not worth defining. - typedef typename std::iterator_traits< - Iterator>::iterator_category iterator_category; - /// The type of elements of the range. Not cv-qualified. - typedef typename std::iterator_traits::value_type value_type; - /// The type of the size of the range and offsets within the range. - typedef typename std::iterator_traits< - Iterator>::difference_type difference_type; - /// The return type of element access methods: \c front(), \c back(), etc. - typedef typename std::iterator_traits::reference reference; - typedef typename std::iterator_traits::pointer pointer; - /// @} - - /// \name constructors - /// @{ - - /// Creates a range of default-constructed (not - /// value-initialized) iterators. For most \c Iterator types, this - /// will be an invalid range. - range() : begin_(), end_() {} - - /// \pre \c end is reachable from \c begin. - /// \post this->begin() == begin && this->end() == end - LLVM_CONSTEXPR range(Iterator begin, Iterator end) - : begin_(begin), end_(end) {} - - /// \par Participates in overload resolution if: - /// - \c Iterator is not a pointer type, - /// - \c begin(r) and \c end(r) return the same type, and - /// - that type is convertible to \c Iterator. - /// - /// \todo std::begin and std::end are overloaded between T& and - /// const T&, which means that if a container has only a non-const - /// begin or end method, then it's ill-formed to pass an rvalue to - /// the free function. To avoid that problem, we don't use - /// std::forward<> here, so begin() and end() are always called with - /// an lvalue. Another option would be to insist that rvalue - /// arguments to range() must have const begin() and end() methods. - template LLVM_CONSTEXPR range( - R &&r, - typename std::enable_if< - !std::is_pointer::value && - detail::is_range::value && - std::is_convertible::type, - Iterator>::value>::type* = nullptr) - : begin_(detail::adl_begin(r)), end_(detail::adl_end(r)) {} - - /// This constructor creates a \c range from any range with - /// contiguous iterators. Because dereferencing a past-the-end - /// iterator can be undefined behavior, empty ranges get initialized - /// with \c nullptr rather than \c &*begin(). - /// - /// \par Participates in overload resolution if: - /// - \c Iterator is a pointer type \c T*, - /// - \c begin(r) and \c end(r) return the same type, - /// - elements \c i of that type satisfy the invariant - /// &*(i + N) == (&*i) + N, and - /// - The result of &*begin() is convertible to \c T* - /// using only qualification conversions [conv.qual] (since - /// pointer conversions stop the pointer from pointing to an - /// array element). - /// - /// \todo The &*(i + N) == (&*i) + N invariant is - /// currently impossible to check for user-defined types. We need a - /// \c contiguous_iterator_tag to let users assert it. - template LLVM_CONSTEXPR range( - R &&r, - typename std::enable_if< - std::is_pointer::value && - detail::is_contiguous_range::value - // MSVC returns false for this in this context, but not if we lift it out of the - // constructor. -#ifndef _MSC_VER - && detail::conversion_preserves_array_indexing< - decltype(&*detail::adl_begin(r)), Iterator>::value -#endif - >::type* = nullptr) - : begin_((detail::adl_begin(r) == detail::adl_end(r) && - !std::is_pointer::value) - // For non-pointers, &*begin(r) is only defined behavior - // if there's an element there. Otherwise, use nullptr - // since the user can't dereference it anyway. This _is_ - // detectable. - ? nullptr : &*detail::adl_begin(r)), - end_(begin_ + (detail::adl_end(r) - detail::adl_begin(r))) {} - - /// @} - - /// \name iterator access - /// @{ - LLVM_CONSTEXPR Iterator begin() const { return begin_; } - LLVM_CONSTEXPR Iterator end() const { return end_; } - /// @} - - /// \name element access - /// @{ - - /// \par Complexity: - /// O(1) - /// \pre \c !empty() - /// \returns a reference to the element at the front of the range. - LLVM_CONSTEXPR reference front() const { return *begin(); } - - /// \par Ill-formed unless: - /// \c iterator_category is convertible to \c - /// std::bidirectional_iterator_tag. - /// - /// \par Complexity: - /// O(2) (Involves copying and decrementing an iterator, so not - /// quite as cheap as \c front()) - /// - /// \pre \c !empty() - /// \returns a reference to the element at the front of the range. - LLVM_CONSTEXPR reference back() const { - static_assert( - std::is_convertible::value, - "Can only retrieve the last element of a bidirectional range."); - using std::prev; - return *prev(end()); - } - - /// This method is drawn from scripting language indexing. It - /// indexes std::forward from the beginning of the range if the argument - /// is positive, or backwards from the end of the array if the - /// argument is negative. - /// - /// \par Ill-formed unless: - /// \c iterator_category is convertible to \c - /// std::random_access_iterator_tag. - /// - /// \par Complexity: - /// O(1) - /// - /// \pre abs(index) < size() || index == -size() - /// - /// \returns if index >= 0, a reference to the - /// index'th element in the range. Otherwise, a - /// reference to the size()+index'th element. - LLVM_CONSTEXPR reference operator[](difference_type index) const { - static_assert(std::is_convertible::value, - "Can only index into a random-access range."); - // Less readable construction for constexpr support. - return index < 0 ? end()[index] - : begin()[index]; - } - /// @} - - /// \name size - /// @{ - - /// \par Complexity: - /// O(1) - /// \returns \c true if the range contains no elements. - LLVM_CONSTEXPR bool empty() const { return begin() == end(); } - - /// \par Ill-formed unless: - /// \c iterator_category is convertible to - /// \c std::forward_iterator_tag. - /// - /// \par Complexity: - /// O(1) if \c iterator_category is convertible to \c - /// std::random_access_iterator_tag. O(size()) - /// otherwise. - /// - /// \returns the number of times \c pop_front() can be called before - /// \c empty() becomes true. - LLVM_CONSTEXPR difference_type size() const { - static_assert(std::is_convertible::value, - "Calling size on an input range would destroy the range."); - return dispatch_size(iterator_category()); - } - /// @} - - /// \name traversal from the beginning of the range - /// @{ - - /// Advances the beginning of the range by one element. - /// \pre \c !empty() - void pop_front() { ++begin_; } - - /// Advances the beginning of the range by \c n elements. - /// - /// \par Complexity: - /// O(1) if \c iterator_category is convertible to \c - /// std::random_access_iterator_tag, O(n) otherwise. - /// - /// \pre n >= 0, and there must be at least \c n - /// elements in the range. - void pop_front(difference_type n) { advance(begin_, n); } - - /// Advances the beginning of the range by at most \c n elements, - /// stopping if the range becomes empty. A negative argument causes - /// no change. - /// - /// \par Complexity: - /// O(1) if \c iterator_category is convertible to \c - /// std::random_access_iterator_tag, O(min(n, - /// #-elements-in-range)) otherwise. - /// - /// \note Could be provided as a free function with little-to-no - /// loss in efficiency. - void pop_front_upto(difference_type n) { - advance_upto(begin_, std::max(0, n), end_, - iterator_category()); - } - - /// @} - - /// \name traversal from the end of the range - /// @{ - - /// Moves the end of the range earlier by one element. - /// - /// \par Ill-formed unless: - /// \c iterator_category is convertible to - /// \c std::bidirectional_iterator_tag. - /// - /// \par Complexity: - /// O(1) - /// - /// \pre \c !empty() - void pop_back() { - static_assert(std::is_convertible::value, - "Can only access the end of a bidirectional range."); - --end_; - } - - /// Moves the end of the range earlier by \c n elements. - /// - /// \par Ill-formed unless: - /// \c iterator_category is convertible to - /// \c std::bidirectional_iterator_tag. - /// - /// \par Complexity: - /// O(1) if \c iterator_category is convertible to \c - /// std::random_access_iterator_tag, O(n) otherwise. - /// - /// \pre n >= 0, and there must be at least \c n - /// elements in the range. - void pop_back(difference_type n) { - static_assert(std::is_convertible::value, - "Can only access the end of a bidirectional range."); - advance(end_, -n); - } - - /// Moves the end of the range earlier by min(n, - /// size()) elements. A negative argument causes no change. - /// - /// \par Ill-formed unless: - /// \c iterator_category is convertible to - /// \c std::bidirectional_iterator_tag. - /// - /// \par Complexity: - /// O(1) if \c iterator_category is convertible to \c - /// std::random_access_iterator_tag, O(min(n, - /// #-elements-in-range)) otherwise. - /// - /// \note Could be provided as a free function with little-to-no - /// loss in efficiency. - void pop_back_upto(difference_type n) { - static_assert(std::is_convertible::value, - "Can only access the end of a bidirectional range."); - advance_upto(end_, -std::max(0, n), begin_, - iterator_category()); - } - - /// @} - - /// \name creating derived ranges - /// @{ - - /// Divides the range into two pieces at \c index, where a positive - /// \c index represents an offset from the beginning of the range - /// and a negative \c index represents an offset from the end. - /// range[index] is the first element in the second - /// piece. If index >= size(), the second piece - /// will be empty. If index < -size(), the first - /// piece will be empty. - /// - /// \par Ill-formed unless: - /// \c iterator_category is convertible to - /// \c std::forward_iterator_tag. - /// - /// \par Complexity: - /// - If \c iterator_category is convertible to \c - /// std::random_access_iterator_tag: O(1) - /// - Otherwise, if \c iterator_category is convertible to \c - /// std::bidirectional_iterator_tag, \c abs(index) iterator increments - /// or decrements - /// - Otherwise, if index >= 0, \c index iterator - /// increments - /// - Otherwise, size() + (size() + index) - /// iterator increments. - /// - /// \returns a pair of adjacent ranges. - /// - /// \post - /// - result.first.size() == min(index, this->size()) - /// - result.first.end() == result.second.begin() - /// - result.first.size() + result.second.size() == - /// this->size() - /// - /// \todo split() could take an arbitrary number of indices and - /// return an N+1-element \c tuple<>. This is tricky to - /// implement with negative indices in the optimal number of - /// increments or decrements for a bidirectional iterator, but it - /// should be possible. Do we want it? - std::pair split(difference_type index) const { - static_assert( - std::is_convertible::value, - "Calling split on a non-std::forward range would return a useless " - "first result."); - if (index >= 0) { - range second = *this; - second.pop_front_upto(index); - return make_pair(range(begin(), second.begin()), second); - } else { - return dispatch_split_neg(index, iterator_category()); - } - } - - /// \returns A sub-range from \c start to \c stop (not including \c - /// stop, as usual). \c start and \c stop are interpreted as for - /// operator[], with negative values offsetting from - /// the end of the range. Omitting the \c stop argument makes the - /// sub-range continue to the end of the original range. Positive - /// arguments saturate to the end of the range, and negative - /// arguments saturate to the beginning. If \c stop is before \c - /// start, returns an empty range beginning and ending at \c start. - /// - /// \par Ill-formed unless: - /// \c iterator_category is convertible to - /// \c std::forward_iterator_tag. - /// - /// \par Complexity: - /// - If \c iterator_category is convertible to \c - /// std::random_access_iterator_tag: O(1) - /// - Otherwise, if \c iterator_category is convertible to \c - /// std::bidirectional_iterator_tag, at most min(abs(start), - /// size()) + min(abs(stop), size()) iterator - /// increments or decrements - /// - Otherwise, if start >= 0 && stop >= 0, - /// max(start, stop) iterator increments - /// - Otherwise, size() + max(start', stop') - /// iterator increments, where \c start' and \c stop' are the - /// offsets of the elements \c start and \c stop refer to. - /// - /// \note \c slice(start) should be implemented with a different - /// overload, rather than defaulting \c stop to - /// numeric_limits::max(), because - /// using a default would force non-random-access ranges to use an - /// O(size()) algorithm to compute the end rather - /// than the O(1) they're capable of. - range slice(difference_type start, difference_type stop) const { - static_assert( - std::is_convertible::value, - "Calling slice on a non-std::forward range would destroy the original " - "range."); - return dispatch_slice(start, stop, iterator_category()); - } - - range slice(difference_type start) const { - static_assert( - std::is_convertible::value, - "Calling slice on a non-std::forward range would destroy the original " - "range."); - return split(start).second; - } - - /// @} - -private: - // advance_upto: should be added to , but I'll use it as - // a helper function here. - // - // These return the number of increments that weren't applied - // because we ran into 'limit' (or 0 if we didn't run into limit). - static difference_type advance_upto(Iterator &it, difference_type n, - Iterator limit, std::input_iterator_tag) { - if (n < 0) - return 0; - while (it != limit && n > 0) { - ++it; - --n; - } - return n; - } - - static difference_type advance_upto(Iterator &it, difference_type n, - Iterator limit, - std::bidirectional_iterator_tag) { - if (n < 0) { - while (it != limit && n < 0) { - --it; - ++n; - } - } else { - while (it != limit && n > 0) { - ++it; - --n; - } - } - return n; - } - - static difference_type advance_upto(Iterator &it, difference_type n, - Iterator limit, - std::random_access_iterator_tag) { - difference_type distance = limit - it; - if (distance < 0) - assert(n <= 0); - else if (distance > 0) - assert(n >= 0); - - if (abs(distance) > abs(n)) { - it += n; - return 0; - } else { - it = limit; - return n - distance; - } - } - - // Dispatch functions. - difference_type dispatch_size(std::forward_iterator_tag) const { - return std::distance(begin(), end()); - } - - LLVM_CONSTEXPR difference_type dispatch_size( - std::random_access_iterator_tag) const { - return end() - begin(); - } - - std::pair dispatch_split_neg(difference_type index, - std::forward_iterator_tag) const { - assert(index < 0); - difference_type size = this->size(); - return split(std::max(0, size + index)); - } - - std::pair dispatch_split_neg( - difference_type index, std::bidirectional_iterator_tag) const { - assert(index < 0); - range first = *this; - first.pop_back_upto(-index); - return make_pair(first, range(first.end(), end())); - } - - range dispatch_slice(difference_type start, difference_type stop, - std::forward_iterator_tag) const { - if (start < 0 || stop < 0) { - difference_type size = this->size(); - if (start < 0) - start = std::max(0, size + start); - if (stop < 0) - stop = size + stop; // Possibly negative; will be fixed in 2 lines. - } - stop = std::max(start, stop); - - Iterator first = begin(); - advance_upto(first, start, end(), iterator_category()); - Iterator last = first; - advance_upto(last, stop - start, end(), iterator_category()); - return range(first, last); - } - - range dispatch_slice(const difference_type start, const difference_type stop, - std::bidirectional_iterator_tag) const { - Iterator first; - if (start < 0) { - first = end(); - advance_upto(first, start, begin(), iterator_category()); - } else { - first = begin(); - advance_upto(first, start, end(), iterator_category()); - } - Iterator last; - if (stop < 0) { - last = end(); - advance_upto(last, stop, first, iterator_category()); - } else { - if (start >= 0) { - last = first; - if (stop > start) - advance_upto(last, stop - start, end(), iterator_category()); - } else { - // Complicated: 'start' walked from the end of the sequence, - // but 'stop' needs to walk from the beginning. - Iterator dummy = begin(); - // Walk up to 'stop' increments from begin(), stopping when we - // get to 'first', and capturing the remaining number of - // increments. - difference_type increments_past_start = - advance_upto(dummy, stop, first, iterator_category()); - if (increments_past_start == 0) { - // If this is 0, then stop was before start. - last = first; - } else { - // Otherwise, count that many spaces beyond first. - last = first; - advance_upto(last, increments_past_start, end(), iterator_category()); - } - } - } - return range(first, last); - } - - range dispatch_slice(difference_type start, difference_type stop, - std::random_access_iterator_tag) const { - const difference_type size = this->size(); - if (start < 0) - start = size + start; - if (start < 0) - start = 0; - if (start > size) - start = size; - - if (stop < 0) - stop = size + stop; - if (stop < start) - stop = start; - if (stop > size) - stop = size; - - return range(begin() + start, begin() + stop); - } -}; - -/// \name deducing constructor wrappers -/// \relates std::range -/// \xmlonly \endxmlonly -/// -/// These functions do the same thing as the constructor with the same -/// signature. They just allow users to avoid writing the iterator -/// type. -/// @{ - -/// \todo I'd like to define a \c make_range taking a single iterator -/// argument representing the beginning of a range that ends with a -/// default-constructed \c Iterator. This would help with using -/// iterators like \c istream_iterator. However, using just \c -/// make_range() could be confusing and lead to people writing -/// incorrect ranges of more common iterators. Is there a better name? -template -LLVM_CONSTEXPR range make_range(Iterator begin, Iterator end) { - return range(begin, end); -} - -/// \par Participates in overload resolution if: -/// \c begin(r) and \c end(r) return the same type. -template LLVM_CONSTEXPR auto make_range( - Range &&r, - typename std::enable_if::value>::type* = nullptr) - -> range { - return range(r); -} - -/// \par Participates in overload resolution if: -/// - \c begin(r) and \c end(r) return the same type, -/// - that type satisfies the invariant that &*(i + N) == -/// (&*i) + N, and -/// - \c &*begin(r) has a pointer type. -template LLVM_CONSTEXPR auto make_ptr_range( - Range &&r, - typename std::enable_if< - detail::is_contiguous_range::value && - std::is_pointer::value>::type* = - nullptr) -> range { - return range(r); -} -/// @} -} // end namespace lld - -#endif // LLD_CORE_RANGE_H Index: include/lld/ReaderWriter/LinkerScript.h =================================================================== --- include/lld/ReaderWriter/LinkerScript.h +++ include/lld/ReaderWriter/LinkerScript.h @@ -17,7 +17,6 @@ #include "lld/Core/Error.h" #include "lld/Core/LLVM.h" -#include "lld/Core/range.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" Index: unittests/CoreTests/CMakeLists.txt =================================================================== --- unittests/CoreTests/CMakeLists.txt +++ unittests/CoreTests/CMakeLists.txt @@ -1,4 +1,3 @@ add_lld_unittest(CoreTests ParallelTest.cpp - RangeTest.cpp ) Index: unittests/CoreTests/RangeTest.cpp =================================================================== --- unittests/CoreTests/RangeTest.cpp +++ /dev/null @@ -1,240 +0,0 @@ -//===- lld/unittest/RangeTest.cpp -----------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -/// -/// \file -/// \brief range.h unit tests. -/// -//===----------------------------------------------------------------------===// - -#include "gtest/gtest.h" -#include "lld/Core/range.h" -#include -#include -#include -#include -#include -#include -#include -#include -#include - -template struct AssertTypesSame; -template struct AssertTypesSame {}; -#define ASSERT_TYPES_SAME(T, U) AssertTypesSame() - -struct no_begin {}; -struct member_begin { - int *begin(); -}; -struct free_begin {}; -int *begin(free_begin); - -template -auto type_of_forward(T &&t) -> decltype(std::forward(t)) { - return std::forward(t); -} - -template To implicit_cast(To val) { return val; } - -void test_traits() { - using namespace lld::detail; - ASSERT_TYPES_SAME(begin_result::type, undefined); - // This causes clang to segfault. -#if 0 - ASSERT_TYPES_SAME( - begin_result::type, int *); -#endif - ASSERT_TYPES_SAME(begin_result::type, int *); -} - -TEST(Range, constructors) { - std::vector v(5); - std::iota(v.begin(), v.end(), 0); - lld::range::iterator> r = v; - EXPECT_EQ(v.begin(), r.begin()); - EXPECT_EQ(v.end(), r.end()); - - int arr[] = { 1, 2, 3, 4, 5 }; - std::begin(arr); - lld::range r2 = arr; - EXPECT_EQ(5, r2.back()); -} - -TEST(Range, conversion_to_pointer_range) { - std::vector v(5); - std::iota(v.begin(), v.end(), 0); - lld::range r = v; - EXPECT_EQ(&*v.begin(), r.begin()); - EXPECT_EQ(2, r[2]); -} - -template void takes_range(lld::range r) { - int expected = 0; - for (int val : r) { - EXPECT_EQ(expected++, val); - } -} - -void takes_ptr_range(lld::range r) { - int expected = 0; - for (int val : r) { - EXPECT_EQ(expected++, val); - } -} - -TEST(Range, passing) { - using lld::make_range; - using lld::make_ptr_range; - std::list l(5); - std::iota(l.begin(), l.end(), 0); - takes_range(make_range(l)); - takes_range(make_range(implicit_cast &>(l))); - std::deque d(5); - std::iota(d.begin(), d.end(), 0); - takes_range(make_range(d)); - takes_range(make_range(implicit_cast &>(d))); - std::vector v(5); - std::iota(v.begin(), v.end(), 0); - takes_range(make_range(v)); - takes_range(make_range(implicit_cast &>(v))); - static_assert( - std::is_same>::value, - "make_ptr_range should return a range of pointers"); - takes_range(make_ptr_range(v)); - takes_range(make_ptr_range(implicit_cast &>(v))); - int arr[] = { 0, 1, 2, 3, 4 }; - takes_range(make_range(arr)); - const int carr[] = { 0, 1, 2, 3, 4 }; - takes_range(make_range(carr)); - - takes_ptr_range(v); - takes_ptr_range(implicit_cast &>(v)); - takes_ptr_range(arr); - takes_ptr_range(carr); -} - -TEST(Range, access) { - std::array a = { { 1, 2, 3, 4, 5 } }; - lld::range r = a; - EXPECT_EQ(4, r[3]); - EXPECT_EQ(4, r[-2]); -} - -template struct CompileAssert; -template <> struct CompileAssert {}; - -#if __has_feature(cxx_constexpr) -constexpr int arr[] = { 1, 2, 3, 4, 5 }; -TEST(Range, constexpr) { - constexpr lld::range r(arr, arr + 5); - CompileAssert(); - CompileAssert(); - CompileAssert(); -} -#endif - -template void test_slice() { - Container cont(10); - std::iota(cont.begin(), cont.end(), 0); - lld::range r = cont; - - // One argument. - EXPECT_EQ(10, r.slice(0).size()); - EXPECT_EQ(8, r.slice(2).size()); - EXPECT_EQ(2, r.slice(2).front()); - EXPECT_EQ(1, r.slice(-1).size()); - EXPECT_EQ(9, r.slice(-1).front()); - - // Two positive arguments. - EXPECT_TRUE(r.slice(5, 2).empty()); - EXPECT_EQ(next(cont.begin(), 5), r.slice(5, 2).begin()); - EXPECT_EQ(1, r.slice(1, 2).size()); - EXPECT_EQ(1, r.slice(1, 2).front()); - - // Two negative arguments. - EXPECT_TRUE(r.slice(-2, -5).empty()); - EXPECT_EQ(next(cont.begin(), 8), r.slice(-2, -5).begin()); - EXPECT_EQ(1, r.slice(-2, -1).size()); - EXPECT_EQ(8, r.slice(-2, -1).front()); - - // Positive start, negative stop. - EXPECT_EQ(1, r.slice(6, -3).size()); - EXPECT_EQ(6, r.slice(6, -3).front()); - EXPECT_TRUE(r.slice(6, -5).empty()); - EXPECT_EQ(next(cont.begin(), 6), r.slice(6, -5).begin()); - - // Negative start, positive stop. - EXPECT_TRUE(r.slice(-3, 6).empty()); - EXPECT_EQ(next(cont.begin(), 7), r.slice(-3, 6).begin()); - EXPECT_EQ(1, r.slice(-5, 6).size()); - EXPECT_EQ(5, r.slice(-5, 6).front()); -} - -TEST(Range, slice) { - // -fsanitize=undefined complains about this, but only if optimizations are - // enabled. -#if 0 - test_slice>(); -#endif - test_slice>(); -// This doesn't build with libstdc++ 4.7 -#if 0 - test_slice>(); -#endif -} - -// This test is flaky and I've yet to pin down why. Changing between -// EXPECT_EQ(1, input.front()) and EXPECT_TRUE(input.front() == 1) makes it work -// with VS 2012 in Debug mode. Clang on Linux seems to fail with -03 and -02 -g -// -fsanitize=undefined. -#if 0 -TEST(Range, istream_range) { - std::istringstream stream("1 2 3 4 5"); - // MSVC interprets input as a function declaration if you don't declare start - // and instead directly pass std::istream_iterator(stream). - auto start = std::istream_iterator(stream); - lld::range> input( - start, std::istream_iterator()); - EXPECT_TRUE(input.front() == 1); - input.pop_front(); - EXPECT_TRUE(input.front() == 2); - input.pop_front(2); - EXPECT_TRUE(input.front() == 4); - input.pop_front_upto(7); - EXPECT_TRUE(input.empty()); -} -#endif - -//! [algorithm using range] -template void partial_sum(T &container) { - using lld::make_range; - auto range = make_range(container); - typename T::value_type sum = 0; - // One would actually use a range-based for loop - // in this case, but you get the idea: - for (; !range.empty(); range.pop_front()) { - sum += range.front(); - range.front() = sum; - } -} - -TEST(Range, user1) { - std::vector v(5, 2); - partial_sum(v); - EXPECT_EQ(8, v[3]); -} -//! [algorithm using range] - -//! [algorithm using ptr_range] -void my_write(int fd, lld::range buffer) {} - -TEST(Range, user2) { - std::string s("Hello world"); - my_write(1, s); -}